Рис. 3. Варіанти розміщення відрізка для не кутових областей
Рис. 4. Випадок кутових областей
З цих восьми випадків легко симетрично згенерувати всі інші випадки.
Головна різниця FC-алгоритму від алгоритмц Коена-Сазерленда полягає у впорядкуванні дій по відсіканню. Ефективність алгоритму Коена-Сазерленда обмежується послідовним характером і фіксованим порядком дій по відсіканню. Як приклад (див. рис. 4) відрізок RW буде відсікатися в порядку: зверху, знизу, праворуч і зліва. Число ж відсікань для визначення видимості рівно 2 - знизу і зліва. В FC-алгоритмі, напроти, для кожного значення LineCode є свій набір дій по відсіканню. Для приведеного вище прикладу необхідно тільки одне відсікання для визначення невидимості відрізка RW. Крім того, підвищення ефективності FC-алгоритму в порівнянні з CS-алгоритмом відповідає відсутності непотрібних циклів і переобчислень кодів кінцевих точок.
Двомірний алгоритм Ліанга-Барскі
В 1982 г. Ліанг і Барскі запропонували алгоритми відсікання прямокутним вікном з використанням параметричного представлення для двох, трьох і чотирьохмірного відсікання.
Розглянемо двомірний алгоритм відсікання. При 2D відсіканні прямі відсікаються по 2D області, яка називається вікном відсікання. Внутрішня частина вікна відсікання може бути виражена за допомогою наступних нерівностей (рис. 5).
| | | | | | | | | |
| (1) | Рис. 5. Внутрішня частина вікна відсікання
Продовжимо кожну з чотирьох границь вікна до нескінчених прямих. Кожна з таких прямих ділить площину на 2 області. Назвемо "видимою частиною" ту, в якій знаходиться вікно відсікання, як це показано на рис. 6. Видимій частині відповідає внутрішня сторона лінії границі. Невидимій частині площини відповідає зовнішня сторона лінії границі.
Рис. 6. Видима частина лінії границі
Таким чином, вікно відсікання може бути визначено як область, яка знаходиться на внутрішній стороні всіх ліній границь.
Відрізок прямої, що відсікається, може бути перетворений в параметричне представлення наступним чином. Нехай кінцеві точки відрізка V0 і V1 з координатами (x0,y0) і (x1,y1), відповідно. Тоді параметричне представлення лінії може бути задано наступним чином:
(2) |
(3) | Або в загальному вигляді для відрізка, заданого точками V0 і V1:
(4) | Для точок V0 і V1 параметр t дорівнює 0 і 1, відповідно. Змінюючи t від 0 до 1 рухаємося по відрізку V0V1 від точки V0 до точки V1. Змінюючи t в інтервалі від -¥ до +¥, отримаємо безмежну пряму, орієнтація якої - від точки V0 до точки V1.
Повернемося до формального розгляду алгоритму відсікання.
Підставляючи параметричне представлення, яке задане рівняннями (2) і (3), в нерівність (1), отримаємо наступні співвідношення для частин безмежної лінії, яка знаходиться у вікні відсікання:
| | | | | | | | | | | | | |
| (5) | Відмітимо, що співвідношення (5) – це нерівності, які описують внутрішню частину вікна відсікання, в той же час як рівність визначає його границі.
Розглядаючи нерівності (5), бачимо, що вони мають однакову форму вигляду:
(6) | де
| | | | | | | | | | | | | | | |
| | | | | | | | |
| | | | | | | | |
| (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, тоді:
(8) | Для пояснення на рис. 7 показаний перетин з лівою і правою границями при Pi < 0.
Рис. 7. Перетин безмежної лінії, яка визначається точками V0V1 і йде з невидимої на видиму сторону, з лівою і правою границями.
Діапазон значень параметру t, для яких безмежна лінія знаходиться на видимій стороні відповідної граничної лінії, має мінімум в точці перетину направленої безмежної лінії, яка задана вектором V0V1 і йде з невидимої на видиму сторону граничної лініх (так як тільки на границі t рівне Qi / Pi, а в іншій частині видимої сторони більше).
Pi > 0
Якщо Pi > 0, тоді: