Реферат з інформатикиНА тему:
Відсікання відрізків
Якщо зображення виходить за межі екрані, то на частині дисплеїв збільшується час побудови за рахунок того, що зображення будується в "думці". В деяких дисплеях вихід за межі екрану призводять до спотворення картини, так як координати просто обмежуються при досягненні ними граничних значень, а не виконується точний розрахунок координат перетину (ефект "стягнення" зображення). Деякі, в основному, прості дисплеї просто не допускають виходу за межі екрана. Все це, особливо в зв’язку з широким використанням технології перегляду вікнами, потребує виконання відсікання сцени по границям вікна видимості.
В простих графічних системах достатньо двомірного відсікання, в трьохмірних пакетах використовується трьох і чотирьохмірне відсікання.
Програмне виконання відсікання достатньо повільний процес, тому в потужні дисплеї вбудовується відповідна апаратура. Перша згадка про апаратуру відсікання, який використовує алгоритм відсікання діленням відрізка навпіл з’явилося в 1968р. Ми розглянемо програмні реалізації алгоритму відсікання.
Відрізки відсікання можуть бути трьох класів - цілком видимі, цілком невидимі і ті, що перетинають вікно. Існує два основних типи алгоритмів відсікання - алгоритми, які використовують кодування кінців відрізка або всього відрізка і алгоритми, які використовують параметричне представлення відрізків, що відсікаються і вікна відсікання. Представники першого типу алгоритмів - алгоритм Коена-Сазерленда (Cohen-Sutherland, CS-алгоритм) і FC-алгоритм (Fast Clipping - алгоритм). Представники алгоритмів другого типу - алгоритм Ліанга-Барскі (Liang-Barsky, LB-алгоритм).
Алгоритми з кодуванням застосовуються для прямокутного вікна, сторони якого паралельні вісям координат, в той час як алгоритми з параметричним представленням застосовуються для вільного вікна.
Двомірний алгоритм Коена-Сазерленда
Цей алгоритм дозволяє швидко виявити відрізки, які можуть бути або прийняті або відкинуті цілком. Обчислення перетинів вимагається коли відрізок не потрапляє ні в один з цих класів. Цей алгоритм особливо ефективний в двох крайніх випадках:
· більшість примітивів міститься цілком в великому вікні,
· більшість примітивів лежить цілком поза відносно маленького вікна.
Ідея алгоритму полягає в наступному: вікно відсікання і частини площини, що прилягає до нього, разом утворюють 9 областей (рис. 1). Кожній з областей присвоєний 4-х розрядний код.
Дві кінцеві точки відрізка отримують 4-х розрядні коди, які відповідають областям, в які вони потрапили. Зміст розрядів коду:
1 рр = 1 - точка над верхнім краєм вікна;
2 рр = 1 - точка під нижнім краєм вікна;
3 рр = 1 - точка праворуч від правого краю вікна;
4 рр = 1 - точка зліва від лівого краю вікна.
Визначення того лежить відрізок цілком всередині вікна або цілком поза вікном виконується наступним чином:
· якщо коди обох кінців відрізка рівні 0 то відрізок цілком всередині вікна, відсікання не потрібне, відрізок приймається як тривіально видимий (відрізок AB на рис. 1);
· якщо логічне & кодів обох кінців відрізка не дорівнює нулю, то відрізок цілком поза вікном, відсікання не потрібне, відрізок відкидається як тривіально невидимий (відрізок KL на рис. 1);
· якщо логічне & кодів обох кінців відрізка дорівнює нулю, то відрізок підозрілий, він може бути частково видимим (відрізки CD, EF, GH) або цілком невидимим (відрізок IJ); для нього потрібно визначити координати перетинів зі сторонами вікна і для кожної отриманої частині визначити тривіальну видимість або невидимість. При цьому для відрізків CD і IJ необхідно буде обчислення одного перетину, для інших (EF і GH) - двох.
При розрахунку перетину використовується горизонтальність або вертикальність сторін вікна, що дозволяє визначити координату X або Y точки перетину без обчислень.
Рис. 1. Відсікання по методу Коена-Сазерленда
При безпосередньому використанні описаного вище способу відбору цілком видимого або цілком невидимого відрізка після розрахунку перетину необхідно було б обчислення коду розташування точки перетину. Для прикладу розглянемо відрізок CD. Точка перетину позначена як P. В силу того, що границя вікна вважається, що належить вікну, то можна просто прийняти тільки частину відрізка PD, яка потрапила у вікно. Частина ж відрізка CP, насправді виявилася поза вікном, потребує подальшого розглядання, так як логічне І кодів точок C і P дасть 0, тобто відрізок CP не можна просто відкинути. Для рішення цієї проблеми Коен і Сазерленд запропонували заміняти кінцеву точку з ненульовим кодом кінця на точку, що лежить з боку вікна, або на її продовженні.
В цілому схема алгоритму Коена-Сазерленда наступна:
1.Розрахувати коди кінцевих точок відрізка, що відсікається.
В циклі повторяти пункти 2-6:
2.Якщо логічне І кодів кінцевих точок не дорівнює 0, то відрізок цілком поза вікном. Він відкидається і відсікання закінчено.
3.Якщо обидва коди дорівнює 0, то відрізок цілком видимий. Він приймається і відсікання закінчено.
4.Якщо початкова точка всередині вікна, то вона міняється місцями з кінцевою точкою.
5.Аналізується код початкової точки для визначення сторони вікна з якою є перетин і виконується розрахунок перетину. При цьому обчислювальна точка перетину заміняє початкову точку.
6.Визначення нового коду початкової точки.
Двомірний FC-алгоритм
В 1987 г. Був запропонований алгоритм (Собков, Поспишил і Янг), який називається FC-алгоритмом (Fast Clipping), що використовує кодування не кінцевих точок, а ліній цілком.
Схема кодування подібна до тої, що використовується в алгоритмі Коена-Сазерленда (рис. 2). Простір поділяється на 9 областей, що перекриваються і пронумеровані арабськими цифрами від 1 до 9. Коди, які назначені кінцям відрізків, що потрапили в ту чи іншу область, приведені в двійковому і шістнадцятковому вигляді (запис вигляду 0xD).
Рис. 2. Завдання кодів для FC-алгоритму
Відрізок видимий тільки в області 5, тобто відрізок, координати якого задовольняють умовам: