Алгоритм Сазерленда-Коена відсікання прямокутною областю

Розглянемо плоску сцену, що складається з відрізків різної довжини й напрямків, у якій треба виділити частину, що перебуває усередині прямокутника. Прямокутник заданий списком ребер: t<op>, b<ottom>, l<eft>, r<ight>, відрізки також задаються координатами кінцевих крапок. Область, що відтинається вікном (з урахуванням його границі), складається із крапок , що задовольняють співвідношенням

(7.1)

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

Рис. 7.1. Коди Сазерленда-Коена для областей

Відрізок повністю не бачимо, якщо обоє його кінця лежать

1. праворуч від ребра ;

2. ліворуч від ребра ;

3. знизу від ребра ;

4. зверху від ребра .

У всіх інших випадках відрізок може (але не зобов'язаний) перетинати прямокутне вікно.

Для виконання аналізу повної видимості або невидимості відрізка А.Сазерленд і Д.Коен запропонували наступний алгоритм. Прямі, яким належать ребра прямокутника, розбивають площина на дев'ять областей, кожної з яких привласнюється чотирьохразрядний код. Кожний біт цього коду "відповідає" за одну із прямих: 1-й (старший) біт - за пряму , 2-й - за пряму , 3-й - за , 4-й - за . Якщо в коді області який-небудь біт установлений в 1, то це означає, що вона відділена від вікна відповідної прямої. Схема ідентифікації областей наведена на мал. 7.1.

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

Таблиця 7.1. Значення істинності для логічного множення кодів областей
	T	F	F	F	T	T	F	F
	F	T	F	F	F	F	T	T
	F	F	T	F	T	F	T	F
	F	F	F	T	F	T	F	T
	T	F	T	F	T	T	T	F
	T	F	F	T	T	T	F	T
	F	T	T	F	T	F	T	T
	F	T	F	T	F	T	T	T

Із зіставлення таблиці з малюнком видно, що якщо добуток кодів кінців відрізка приймає значення T<rue>, те відрізок цілком лежить по одну сторону якоїсь із прямих, причому зовнішню сторону стосовно вікна, отже, він повністю невидимий. У всіх інших випадках відрізок може частково лежати усередині вікна, тому для визначення їхньої видимої частини треба вирішувати завдання про перетинання відрізків з ребрами вікна. При цьому бажано по можливості скоротити число пар, що перебираються, " відрізок-ребро".

У самому загальному випадку існує дві крапки перетинання відрізка з ребрами, і ці дві крапки приймаються за нові кінцеві крапки зображуваного відрізка. Але спочатку можна виділити деякі більше прості окремі випадки, пошук перетинань для яких є більше ефективним. Насамперед це горизонтальні й вертикальні відрізки, для яких пошук крапки перетинання тривіальний. Далі, якщо код одного з кінців відрізка дорівнює нулю, то існує тільки одне перетинання цього відрізка з ребром (або із двома ребрами, якщо відрізок проходить через кутову крапку вікна). На мал. 7.2 наведена загальна блок-схема алгоритму відсікання для одного довільно спрямованого відрізка.

Рис. 7.2. Блок-схема алгоритму Сазерленда-Коэна

У блок-схемі використовуються наступні угоди й позначення:

- вхідними даними є крапки , масив координат вікна ;

- на виході одержуємо нові кінцеві крапки , а також значення змінної IsVisible (0 - відрізок видимий);

- використовуються наступні допоміжні функції:

GetCode(r) - визначення коду крапки;

Intersec0(r1,l) - пошук перетинання відрізка зі сторонами вікна за умови, що обидві крапки лежать поза вікном; якщо перетинання ні, установлює змінну IsVisible в 0;

Intersec(r1,l) - пошук перетинання відрізка зі сторонами вікна за умови, що крапка r1 лежить у вікні;

C1, C2 - коди крапок r1, r2.

У наведеному алгоритмі тепер залишається тільки деталізувать функції Intersec0 і Intersec, ефективність роботи яких є ключовим моментом. Розглянемо один з методів пошуку перетинань, що використовує параметричне рівняння прямої, що проходить через крапки :

або в координатному виді

Спробуємо визначити крапку перетинання відрізка з верхньою границею вікна. Оскільки ця границя описується співвідношеннями

та умова перетинання з нею кліпованого відрізка виглядає в такий спосіб:

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

Цей алгоритм реалізований у вигляді функції Intersec, блок-схема якої наведена на мал. 7.3.

Тепер розглянемо випадок, коли жоден з кінців відрізка не лежить усередині вікна. Тут ми можемо знайти першу крапку перетинання, замінити нею один з кінців відрізка й використовувати попередній алгоритм знаходження другої крапки. Помітимо, що в цьому випадку перший крок не завжди кінчається успішно, оскільки попередній аналіз не дозволяє повністю виключити всі невидимі відрізки. Як і в попередньому алгоритмі, спочатку виконується перевірка на горизонтальне й вертикальне напрямки відрізка. Оскільки частина відрізків ми вже виключили з розгляду завдяки попередньому аналізу, то для цих простих ситуацій залишаються тільки дві можливості, наведені на мал. 7.4. Тут крапки перетинання визначаються зовсім очевидним образом, причому відразу обидві.

Потім послідовно розглядаються чотири випадки розташування крапки відносно прямих, що обмежують вікно. Якщо в якімсь із варіантів буде знайдена крапка перетинання, то аналіз припиняється, крапка заміняється новою крапкою й викликається функція Intersec. У випадку ж, коли всі чотири варіанти не дали позитивного результату, змінної IsVisible привласнюється значення 0. Алгоритм реалізується функцією Intersec0 (блок-схема на мал. 7.5).

Запропонована реалізація алгоритму відсікання не є єдиною у своєму роді. Існують і інші підходи, зокрема використання методу розподілу відрізка навпіл для пошуку крапок перетинання й виявлення видимої частини відрізка. Такий варіант алгоритму був запропонований Сазерлендом і Спрулом для апаратної реалізації, але він може бути реалізований і на програмному рівні, хоча при цьому ефективність його буде нижче, ніж у попередні. У ньому немає прямого обчислення координат нової крапки по явних алгебраїчних співвідношеннях. Пошук здійснюється ітераційним методом, у якому на кожному кроці для відрізка, "підозрюваного" у частковій видимості, перебуває його середня крапка, визначається її код, потім із двох відрізків залишаються або обоє (якщо вони обоє не виявляться повністю невидимими), або тільки один, після чого операції тривають із новими відрізками. Ситуація, коли подальшому дробленню піддаються відразу два знову отриманих відрізки, може виникнути тільки на першому ітераційному кроці в тих випадках, коли вихідний відрізок має дві крапки перетинання із границями вікна. На наступних ітераційних кроках кількість аналізованих відрізків уже не буде збільшуватися. Процес триває доти, поки довжина чергового відрізка не стане менше наперед заданій точності. Після цього знайдена крапка перевіряється на предмет перетинання зі стороною вікна. На мал. 7.6 наведені три варіанти відрізків, попередній аналіз яких не класифікує їх як повністю невидимі, і показаний перший ітераційний крок. Відрізок a після першого розподілу дає два частково видимих відрізки, після чого шукаються дві крапки перетинання. В інших випадках залишається лише один із двох відрізків, причому у випадку відрізка c крапка перетинання зі стороною вікна відсутній, тобто виявляється повна невидимість відрізка. По суті справи загальний алгоритм, показана на мал. 7.3, зберігається, змінюється лише метод пошуку крапки перетинання.

Рис. 7.3. Блок-схема функції Intersec

Рис. 7.4. Відрізки паралельні сторонам вікна

Рис. 7.5. Блок-схема функції Intrsec0

Рис. 7.6. Довільне розташування відрізків