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

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

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

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

Xлів  X  Xправ і Yниж  Y  Yверх.

Кожна кінцева точка відрізку V0V1 буде знаходитися в цих областях. Комбінація кодів кінців відрізка, називається кодом лінії, і використовується для визначення можливих варіантів розміщення відрізку і його відсікання. Код лінії формується з кодів кінця відрізка наступним чином:

LineCode (V0,V1) = (Code(V0) ×16) + Code (V1),

де Code(V1) означає код кінцевої точки V1, Code(V0) × 16 означає зсув коду початкової точки V0 вліво на 4 розряди.

Так як кожний код може приймати одно з 9 значень, то всього є 81 можливий варіантів розміщення відрізка. Але, якщо Code(V0) рівний Code(V1), то LineCode(V0,V1) рівний LineCode(V1,V0). Є всього 9 таких випадків: 1-1, 2-2,  9-9. Звідси слідує, що число різних випадків зменшується до 72.

Кожний LineCode вимагає свого набору обчислень для визначення відсікання відрізка за мінімальний час. Всього є 8 основних випадків відсікання, а інші симетричні до них.

Розглянемо ці 8 основних випадків. При цьому будемо використовувати наступні позначення:

• початкова точка відрізку вважається точкою номер 0 (V0),

• кінцева точка відрізка вважається точкою номер 1 (V1),

• ClipA_B означає алгоритм розрахунку переміщення кінцевої точки номер А на сторону вікна B (розрахунок перетинання прямої лінії, на якій розміщений відрізок, що відсікається зі стороною вікна B).

Ілюстрація до випадків 1-7 приведений на рис. 3, для випадку 8 - на рис. 4.

1. Початкова і кінцева точки відрізка обидві в області 5 (відрізок JK). Це простий випадок прийняття відрізка.

2. Початкова і кінцева точки відрізка обидві в області 4 (відрізок LA). Відрізок не перетинає видиму область, так що це простий випадок відкидання.

3. Початкова точка в області 4, кінцева - в області 1 (відрізок LB). Відрізок не перетинає видиму область, так що це простий випадок відкидання.

4. Початкова точка в області 4, кінцева - в області 2 (відрізки LC і LD). Відрізки явно перетинає Xлів, так що спочатку необхідно визначити відповідну координату, використовуючи алгоритм Clip0_Xleft. Для відрізка LC це дає V0y > Yверх, так що відрізок повинен бути відкинений без подальших обчислень. Відрізок LD входить в вікно з лівої сторони і може виходити через верх. Відповідно, наступне відсікання повинно бути Clip1_Top, після якого відрізок приймається.

5. Початкова точка в області 4, кінцева - в області 3 (відрізки LE, LF і LG). Відрізки явно перетинають Xлів. Так само як і для випадку 4 спочатку застосовується Clip0_Xleft і відрізок LE відкидається якщо V0y > Yверх. Якщо ж отримаємо V0y  Yверх, то відрізок повинен вийти з області видимості через верхнє або праве ребро. Використовуємо відсікання Clip1_Top і порівнюємо нове значення X-координати кінцевої точки - V1x з Xправ. Якщо V1x  Xправ, то відрізок (LF) проходить через верхню сторону, відрізок приймається і подальші обчислення не потрібні. Інакше відрізок (LG) проходить через праву сторону і вимагає відсікання Clip1_Right. Відсікання закінчено, відрізок приймається.

6. Початкова точка в області 4, кінцева - в області 6 (відрізок LH). Даний відрізок видимий. Спочатку використовуємо Clip0_Xleft потім Clip1_Right і приймає відрізок.

7. Початкова точка в області 4, кінцева - в області 5 (відрізок LI). Даний відрізок видимий. Просто використовуємо Clip0_Xleft і приймаємо відрізок.8. Початкова точка V0 (R, S, T або U) в області 7, кінцева точка V1 (W, X, Y або Z) - в області 3 (див. рис. 4). В цьому випадку можуть бути відкинуті тільки два типи відрізків. Для мінімізації обчислень використовуємо Clip0_Xleft. Якщо V0y > Yверх, то це перший випадок відкидання (відрізок RW). Clip1_Xright і перевірка V1y < Yниж задають другий випадок відкидання (відрізок UZ). Всі інші відрізки повинні бути видимі. Якщо V0y < Yниж, тоді V0 = T, інакше V0 = S. Якщо V0y < Yниж, то Clip1_Ybottom дасть точку V0 на ребрі вікна. Аналогічно, якщо V1y > Yверх, то V1=X і тут необхідний Clip1_Ytop перед прийняттям відрізка. Якщо V1y < Yверх, тоді V1 = Y.

Рис. 3. Варіанти розміщення відрізка для не кутових областей

Рис. 4. Випадок кутових областей

З цих восьми випадків легко симетрично згенерувати всі інші випадки.

Головна різниця FC-алгоритму від алгоритмц Коена-Сазерленда полягає у впорядкуванні дій по відсіканню. Ефективність алгоритму Коена-Сазерленда обмежується послідовним характером і фіксованим порядком дій по відсіканню. Як приклад (див. рис. 4) відрізок RW буде відсікатися в порядку: зверху, знизу, праворуч і зліва. Число ж відсікань для визначення видимості рівно 2 - знизу і зліва. В FC-алгоритмі, напроти, для кожного значення LineCode є свій набір дій по відсіканню. Для приведеного вище прикладу необхідно тільки одне відсікання для визначення невидимості відрізка RW. Крім того, підвищення ефективності FC-алгоритму в порівнянні з CS-алгоритмом відповідає відсутності непотрібних циклів і переобчислень кодів кінцевих точок.

Двомірний алгоритм Ліанга-Барскі

В 1982 г. Ліанг і Барскі запропонували алгоритми відсікання прямокутним вікном з використанням параметричного представлення для двох, трьох і чотирьохмірного відсікання.

Розглянемо двомірний алгоритм відсікання. При 2D відсіканні прямі відсікаються по 2D області, яка називається вікном відсікання. Внутрішня частина вікна відсікання може бути виражена за допомогою наступних нерівностей (рис. 5).

Xлев



x



Xправ

Yверх



y



Yниз

(1)

Рис. 5. Внутрішня частина вікна відсікання

Продовжимо кожну з чотирьох границь вікна до нескінчених прямих. Кожна з таких прямих ділить площину на 2 області. Назвемо "видимою частиною" ту, в якій знаходиться вікно відсікання, як це показано на рис. 6. Видимій частині відповідає внутрішня сторона лінії границі. Невидимій частині площини відповідає зовнішня сторона лінії границі.

Рис. 6. Видима частина лінії границі

Таким чином, вікно відсікання може бути визначено як область, яка знаходиться на внутрішній стороні всіх ліній границь.

Відрізок прямої, що відсікається, може бути перетворений в параметричне представлення наступним чином. Нехай кінцеві точки відрізка V0 і V1 з координатами (x0,y0) і (x1,y1), відповідно. Тоді параметричне представлення лінії може бути задано наступним чином:

x = x0 + dx • t; y = y0 + dy • t,

(2)

де dx = x1 - x0; dy = y1 - y0.

(3)

Або в загальному вигляді для відрізка, заданого точками V0 і V1:

V(t) = V0 + (V1 - V0) • t

(4)

Для точок V0 і V1 параметр t дорівнює 0 і 1, відповідно. Змінюючи t від 0 до 1 рухаємося по відрізку V0V1 від точки V0 до точки V1. Змінюючи t в інтервалі від - до +, отримаємо безмежну пряму, орієнтація якої - від точки V0 до точки V1.

Повернемося до формального розгляду алгоритму відсікання.

Підставляючи параметричне представлення, яке задане рівняннями (2) і (3), в нерівність (1), отримаємо наступні співвідношення для частин безмежної лінії, яка знаходиться у вікні відсікання:

-dx•t



x0 - Xлів

і

dx•t



Xправ - x0,

-dy•t



y0 - Yниж

і

dy•t



Yверх - y0.

(5)

Відмітимо, що співвідношення (5) – це нерівності, які описують внутрішню частину вікна відсікання, в той же час як рівність визначає його границі.

Розглядаючи нерівності (5), бачимо, що вони мають однакову форму вигляду:

Pi•t  Qi для i = 1,2,3,4.

(6)

де

P1

=

-dx;

Q1

=

x0

-

Xлів;

P2

=

dx;

Q2

=

Xправ

-

x0;

P3

=

-dy;

Q3

=

y0

-

Yниж;

P4

=

dy;

Q4

=

Yверх

-

y0.

(7)

Відмітимо, що кожне з нерівностей (6) відповідає одній з граничних ліній (лівій, правій, нижній і верхній, відповідно) і описує її видиму сторону. (Наприклад, для i=1 маємо: P1•t  Q1  -dx•t  x0 - Xлів x0 + dx•t  Xлів).Перетворимо V0V1 в безмежну пряму. Тоді кожна нерівність задає діапазон значень параметра t, для яких ця безмежна лінія знаходиться на видимій стороні відповідної лінії границі. Більш того, конкретне значення параметру t для точки перетину є t = Qi/Pi. Причому знак Qi показує на якій стороні відповідної лінії границі знаходиться точка V0. А саме, якщо Qi  0, тоді V0 знаходиться на видимій стороні лінії границі, включаючи і її. Якщо ж Qi < 0, тоді V0 знаходиться на невидимій стороні.

Розглянемо Pi у співвідношеннях (7). Ясно, що будь-яке Pi може бути менше 0, більше 0 і рівне 0.

Pi < 0

Якщо Pi < 0, тоді:

t  Qi / Pi.

(8)

Для пояснення на рис. 7 показаний перетин з лівою і правою границями при Pi < 0.

Рис. 7. Перетин безмежної лінії, яка визначається точками V0V1 і йде з невидимої на видиму сторону, з лівою і правою границями.

Діапазон значень параметру t, для яких безмежна лінія знаходиться на видимій стороні відповідної граничної лінії, має мінімум в точці перетину направленої безмежної лінії, яка задана вектором V0V1 і йде з невидимої на видиму сторону граничної лініх (так як тільки на границі t рівне Qi / Pi, а в іншій частині видимої сторони більше).

Pi > 0

Якщо Pi > 0, тоді:

t  Qi / Pi.

(9)

Для пояснення на рис. 8 показаний перетин з лівою і правою границями при Pi > 0.

Рис. 8. Перетин безмежної лінії, яка визначається точками V0V1 і йде з видимої на невидиму сторону, з лівою і правою границями.

Так як значення параметру t тільки на границі рівний Qi/Pi, а в іншій видимій частині менше Qi/Pi, то значення параметру t має максимум на границі.

Pi = 0

Якщо Pi = 0, тоді:

0  Qi.

(10)

Відмітимо, що тут нема залежності від t, тобто нерівність виконується для всіх t, якщо Qi  0 і не має рішення при Qi < 0. Для пояснення на рис. 9 ілюструється випадок Pi = 0.

Рис. 9. Відносне розміщення безмежної лінії, яка задана точками V0V1 і йде паралельно лівій і правій границям.

Геометрично, якщо Pi = 0, то нема точок перетину безмежної лінії, яка визначається точками V0V1, з лініями границі. Більш того, якщо Qi < 0, то безмежна лінія знаходиться на зовнішній стороні лінії границі, а при Qi  0 знаходиться на внутрішній стороні (включаючи її). В останньому випадку відрізок V0V1 може бути видимий або ні в залежності від того де знаходяться точки V0V1 на безмежній лінії. В попередньому ж випадку нема видимого сегмента, так як безмежна лінія поза вікном, тобто це випадок тривіального відкидання.

Всі ці випадки представлені на схемі:

Рис. 10. Схема алгоритму Ліанга-Барскі