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

У комп'ютерній графіці, відсікання відрізків — це процес видалення відрізків або частин відрізків за межами оброблюваної ділянки. Як правило, будь-який відрізок або його частина, розташована за межами зони огляду, видаляється.

Є два загальних алгоритми для відсікання відрізків: Коена — Сазерленда і Ляна — Барського.

Метод відсікання відрізка складається з різних частин. Спочатку перевіряється, чи дана частина відрізка потрапляє в область видимості. Потім розраховуються перетини з однією (або декількома) межами відсікання.^[1]

Міститься частина відрізка всередині чи за межами області відсікання, визначається опрацюванням кінців відрізка перетину.

Алгоритм Коена — Сазерленда

Докладніше: Алгоритм Коена — Сазерленда

Алгоритм Коена — Сазерленда (названий на честь Дена Коена^[en] і Айвена Сазерленда) — це алгоритм відсікання відрізка. Алгоритм ділить двовимірний простір на 9 ділянок, з яких тільки середня ділянка (вікно перегляду) є видимою.

1967 року робота Дена Коена з моделювання польоту привела до розвитку алгоритмів відсікання відрізків для дво- і тривимірної комп'ютерної графіки, створених з Айваном Сазерлендом.

Алгоритм Ляна — Барського

Докладніше: Алгоритм Ляна — Барського

Алгоритм Ляна — Барського використовує параметричне рівняння відрізків і нерівності, що описують діапазон області відсікання для визначення перетину між відрізком і областю відсікання. За допомогою цих перетинів визначається, яку частину відрізка слід намалювати. Цей алгоритм є значно ефективнішим, ніж алгоритм Коена — Сазерленда, але другий швидше виконує тривіальні прийняття і відкидння, тому його варто використовувати тоді, коли більшість відрізків слід повністю вилучити.

Кірус — Бек

Докладніше: Алгоритм Кіруса — Бека

Дуже схожий на алгоритм відсікання відрізків Ляна — Барського. Різниця полягає в тому, що алгоритм Ляна — Барського є спрощеним різновидом алгоритму Кіруса — Бека, оптимізованим для прямокутного вікна відсікання.

Алгоритм Кіруса — Бека зі складністю O(N), в першу чергу призначений для відсікання відрізків у параметричній формі відносно опуклого многокутника в 2-х вимірах або відносно опуклого многогранника в 3-х вимірах.^[2]

Алгоритм Нікола — Лі — Нікола

Алгоритм Нікола — Лі — Нікола — це алгоритмом швидкого відсікання відрізків, що зменшує ймовірність відсікання одної частини відрізка кілька разів, як це може статися в алгоритмі Коена — Сазерленда. Вікно відсікання розділене на безліч різних областей, в залежності від положення початкової точки відрізка, яку потрібно відсікти.

Алгоритм O(lg N)

Цей алгоритм класифікує вершини за прямою, заданою в неявному вигляді р: ах + by + с = 0. Оскільки многокутник вважається опуклим і вершини впорядковано за годинниковою стрілкою або проти годинникової стрілки, то можна застосувати двійковий пошук, що приводить до часової складності O(lg N).^[3]

Швидке відсікання

Цей алгоритм схожий з алгоритмом Коена — Сазерленда. Розташування початку і кінця класифікуються за тим, у якій із 9 частин площини вони лежать. Оператор-перемикач спрямовує їх до відповідних обробників. На противагу, алгоритм Коена —Сазерленда, один і той самий випадок може оброблятися кілька разів.^[4]

Алгоритм Скали

Цей алгоритм заснований на однорідних координатах і двоїстості.^[5] Його можна використати для відсікання прямої або відрізків прямокутним вікном або опуклим многокутником. Алгоритм заснований на класифікації вершини вікна відсікання відносно півплощини, заданої прямою р: Ax + By + С = 0. Результат класифікації визначає ребра, які перетинає пряма р. Алгоритм простий, легко реалізується і розширюється на опуклі вікна. Пряму або відрізок р можна обчислити за точками x1, x2, заданих однорідними координатами безпосередньо, за допомогою векторного добутку:

p = x1 x x2 = [x1,y1,w1] x [x2,y2,w2] або

p = x1 x x2 = [x1,y1,1] x [x2,y2,1]

Див. також

• Відсікання (комп'ютерна графіка)