Відсікання відрізків, Детальна інформація

\x0300\x0124\x8411\x021C\x6412\x0168\x2640\x6002\x1C84\x6102\x0124

ight. Відсікання закінчено, відрізок приймається.

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лев

\xF0A3

x

\xF0A3

Xправ

Yверх

\xF0A3

y

\xF0A3

Yниз

(1)



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

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