Відсікання відрізків

Реферат з інформатики НА тему:

Відсікання відрізків

Якщо зображення виходить за межі екрані, то на частині дисплеїв збільшується час побудови за рахунок того, що зображення будується в "думці". В деяких дисплеях вихід за межі екрану призводять до спотворення картини, так як координати просто обмежуються при досягненні ними граничних значень, а не виконується точний розрахунок координат перетину (ефект "стягнення" зображення). Деякі, в основному, прості дисплеї просто не допускають виходу за межі екрана. Все це, особливо в зв’язку з широким використанням технології перегляду вікнами, потребує виконання відсікання сцени по границям вікна видимості.

В простих графічних системах достатньо двомірного відсікання, в трьохмірних пакетах використовується трьох і чотирьохмірне відсікання.

Програмне виконання відсікання достатньо повільний процес, тому в потужні дисплеї вбудовується відповідна апаратура. Перша згадка про апаратуру відсікання, який використовує алгоритм відсікання діленням відрізка навпіл з’явилося в 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.Аналізується код початкової точки для визначення сторони вікна з якою є перетин і виконується розрахунок перетину. При цьому о

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать