Огляд алгоритмів відсікання

Задачу відсікання можна розв’язувати різними методами.

За способом розв’язування цієї задачі всі алгоритми відсікання поділяються на 2 класи [7]:

• — алгоритми, що використовують коди кінців відрізка або самого відрізка;
• — алгоритми, що використовують параметричне задання самих відрізків і сторін вікна.

До першого класу алгоритмів належить алгоритми Сазерленда-Коена, FC-алгоритм, до другого класу — алгоритм Кіруса-Бека, Ейлера-Азертона і більш пізній алгоритм Ліанга-Барскі та ін. [Маценко].

Алгоритми з кодуванням застосовуються до прямокутних вікон, сторони яких паралельні осям координат, а алгоритми з параметричним заданням — до будь-яких вікон.

Алгоритм Сазерленда-Коена є стандартом для алгоритмів відсікання. Розглянемо тепер FC-алгоритм.

В цьому алгоритмі кодуються не кінці відрізка, а весь відрізок цілком. Схема кодування близька до тієї, що використовується в алгоритмі Сазерленда-Коена.

Площина з вікном розбивається на 9 областей і вони кодуються цифрами від 1 до 9 (рис. 1.3). Область з вікном має код 5.

Рис. 1.3 _ Коди областей для FC-алгоритму

Відрізок кодується наступним чином:

LineCode (ab) = Code (a)* 10 + Code (b),.

Code (a) — код області з початковою точкою відрізка,.

Code (b) — код області з кінцевою точкою відрізка,.

LineCode (ab) — код відрізка.

Оскільки кожний код може набувати дев’ять значень, то існує 81 можливий варіант розміщення відрізка і для кожного варіанту, тобто для кожного коду відрізка необхідно мати свій набір обчислень для відсікання відрізка.

Якщо Code (a) = Code (b), то LineCode (ab) = LineCode (ba). Існує 9 таких випадків: (1 — 1), (2 — 2), …, (9 — 9).

У випадку (5 — 5) (код відрізка 55) відрізок повністю видимий, у решті випадків — частково або повністю невидимий.

Отже, кількість різних варіантів тепер зменшується до 72, але і серед них існує всього 6 основних випадків відсікання, решта — симетричні їм. Для того, щоб виділити ці 6 випадків, потрібно розглянути різні варіанти розміщення відрізка для некутових та кутових областей.

Ілюстрації можливих варіантів розміщення відрізка для перших п’яти випадків наведені на рисунку 1.4, для шостого випадку — на рисунку. 1.5.

Випадок 1 — початкова точка відрізка знаходиться в області 4, а кінцева — в області 1 (відрізок AB, LineCode = 41). Відрізок не перетинає видиму область і відкидається.

Випадок 2 — початкова точка відрізка знаходиться в області 4, кінцева — в області 2. Це відрізки AC і AD, LineCode = 42. Вони перетинають ліву межу вікна. Знайдемо точки перетину відрізків AC і AD з лівою межею вікна — (x_лів, y_n). Якщо y_n > y_верхн, то це відрізок AC, він не перетинає відрізка з лівим ребром видимої області й відкидається.

Якщо y_n < y_верхн, то це відрізок AD, що перетинається також з верхньою межею вікна. Тому необхідно обчислити точку перетину відрізка AD з верхньою межею вікна й зобразити видиму частину відрізка.

Випадок 3 — початкова точка відрізка знаходиться в області 4, кінцева — в області 3 (відрізки AE, AF і AG, LineCode = 43). Обчислюємо точки перетину відрізків з лівим ребром вікна (x_лів, y_n). Якщо y_n > y_верхн, то це відрізок AE. Він не перетинає видиму область і відкидається, інакше це відрізки AF і AG. Для них обчислюємо точку перетину з правим ребром (x_пр, y_n). Якщо y_n > y_верхн, то це відрізок AF, тому необхідно обчислити точку перетину з верхнім ребром вікна і зобразити видиму частину відрізка. Інакше це відрізок AG, для нього вже точки перетину з ребрами вікна знайдені, залишається зобразити лише видиму частину відрізка.

Випадок 4 — початкова точка відрізка знаходиться в області 4, кінцева — в області 6 (відрізок AH, LineCode = 46). Обчислюємо точки перетину відрізка з лівим і правим ребрами вікна і зображаємо видиму частину відрізка.

Випадок 5 — початкова точка — в області 4, кінцева — в області 5 (відрізок AL, LineCode = 45). Обчислюємо точку перетину відрізка з лівим ребром і зображаємо видиму частину відрізка.

Випадок 6 — початкова точка знаходиться в області 7, кінцева — в області 3 (відрізки RW, SX, SY, TX, TY, UV, LineCode = 73). Обчислюємо точку перетину відрізка з лівим ребром (x_лів, y_n1). Якщо y_n1 > y_верхн, то це відрізок RW і він відкидається. Обчисляємо точку перетину з правим ребром (x_пр, y_n2). Якщо y_n2 < y_нижн, то це відрізок UV, він теж відкидається. При y_n1 > y_нижн це або відрізок SX, або SY. Далі, якщо y_n2 < y_верхн, то це відрізок SY і можемо зобразити його видиму частину. Інакше це відрізок SX, тому необхідно обчислити точку перетину з верхнім ребром вікна і зобразити його видиму частину. Залишилося розглянути відрізки TX, TY. Якщо y_n2 < y_верхн, то це відрізок TY і ми можемо зобразити його видиму частину. Інакше це відрізок TX, тому обчисляємо для нього точку перетину з верхньою стороною вікна і теж відображаємо його видиму частину.

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

Алгоритм Кіруса-Бека реалізує відсікання довільним опуклим вікном і базується на методі визначення орієнтації лінії, яка містить відрізок, що відсікається, по відношенню до сторони многокутника, а також на методі визначення місцезнаходження точки відрізка відносно вікна — всередині, на границі або зовні вікна. Для цього в алгоритмі Кіруса-Бека використовується вектор внутрішньої нормалі до ребра вікна.

Розглянемо опуклу двовимірну область P, тобто опуклий многокутник. Внутрішньою нормаллю n до сторони вікна називається нормаль, яка направлена в бік області, що складає вікно відсікання. Як видно з рисунка 1.6, внутрішня нормаль n у точці a, що лежить на границі, задовольняє умову.

(n (b — a))? 0, (1.2).

де b — будь-яка інша точка границі опуклої області P.

Скалярний добуток в (1.2) для внутрішньої нормалі n невід'ємний тому, що и? [0,2р ], тобто cosи? 0.

Зазначимо, що внутрішні нормалі можна обчисляти й іншим способом. Для цього необхідно полігон обходити за годинниковою стрілкою і вибирати нормалі, які направлені вправо від кожного ребра Нехай n_{i — внутрішня нормаль до i-ї граничної лінії многокутного вікна, а V = b — a — вектор, що визначає орієнтацію відрізка ab, який відсікається вікном P. Тоді орієнтація відрізка ab відносно i-ї сторони вікна визначається знаком скалярного добутку ri = (ni V):}

при r_i < 0 відрізок ab направлений з внутрішньої сторони на зовнішню сторону i-ї граничної лінії вікна (рис. 1.7, а).

при r_i = 0 точки a, b або збігаються (відрізок вироджується в точку) або відрізок ab паралельний i-й стороні вікна (рис. 1.7, б).

при r_i > 0 відрізок ab направлений із зовнішньої сторони на внутрішню сторону i-ї граничної лінії вікна (рис. 1.7, в).

Для визначення розміщення точки V(t) відрізка ab відносно i-ї сторони вікна розглянемо скалярний добуток внутрішньої нормалі n_{i на вектор}

Q_{i = V (t) — Pi, (1.3)}

що починається в початковій точці P_i ребра вікна і закінчується в деякій точці V(t) відрізка ab, а саме.

q_i = (n_{i Qi), i =1, 2, … (1.4)}

Аналогічно попередньому маємо (рис. 1.8):

• ? якщо q_i < 0, то точка V(t) лежить із зовнішньої сторони границі;
• ? якщо q_i = 0, то точка V(t) лежить на лінії границі вікна;
• ? якщо q_i > 0, то точка V(t) лежить із внутрішньої сторони i-ї границі

вікна.

Згадаємо векторно-параметричне рівняння відрізка ab

V(t) = a + (b — a) t, t? [0, 1]. (1.5).

Оскільки многокутник опуклий, то може бути дві точки перетину відрізка ab із вікном P і нам необхідно знайти два значення параметра t, що відповідають початковій і кінцевій точкам видимої частини відрізка.

З умови належності точки V(t) границі вікна, тобто з умови q_i = 0, враховуючи (9.5) та (9.6), маємо.

(n_{i (a + (b — a)t — Pi))) = 0,}

або.

(n_{i (a — Pi)) + (ni (b — a)t) = 0.}

Звідки.

Алгоритм Кіруса-Бека має наступний вигляд. Шукані значення параметрів t₀, t₁ точок перетину відрізка з вікном ініціалізуємо значеннями 0, 1, що відповідають початку і кінцю відрізка ab.

В циклі по i для кожної сторони вікна відсікання обчислюємо значення скалярних добутків.

r_i = (n_{i (b — a)). (1.7)}

Якщо r_i = 0, то відрізок ab або вироджується в точку, або паралельний i-й стороні вікна. При цьому проаналізуємо значення.

q_i = (n_{i (a — Pi)). (1.8)}

Якщо q_i < 0, то відрізок знаходиться зовні вікна і відсікання закінчено, інакше переходимо до наступної сторони вікна.

Якщо r_i? 0, то за формулою (1.7) обчисляємо значення t для точки перетину відрізка ab з i-ю границею вікна. Оскільки точки відрізка ab відповідають значенням t? [0, 1], то t [0, 1] відкидаємо.

При r_i < 0 лінія ab направлена з внутрішньої сторони і-граничної лінії на зовнішню і знайдені значення t визначатимуть кінцеву точку видимої частини відрізка ab. В цьому випадку визначається min t серед всіх одержаних t (рис. 1.9). Воно дає значення t1 для кінцевої точки шуканого відрізка.

Якщо поточне значення t₁ стане меншим за t₀, то відрізок ab відкидається, оскільки не виконується умова t₀? t₁.

При r_i > 0 лінія ab направлена із зовнішньої сторони граничної лінії на внутрішню, тому знайдені значення t визначатимуть початкову точку видимої частини відрізка ab. В цьому випадку визначається max t серед всіх одержаних t. Воно дає значення t₀ для початкової точки видимої частини відрізка.

Якщо поточне значення t₀ стане більшим за t₁, то відрізок відсікається.

На заключному етапі алгоритму значення t₀, t₁ використовуються для знаходження координат точок перетину відрізка ab з вікном P, тобто для побудови видимої частини відрізка. При цьому, якщо t₀ = 0, то початкова точка залишається та сама й обчислення V(t₀) не потрібні. Аналогічно при t₁ = 1 кінцева точка — b. Обчислення V(t₁) теж не потрібні.