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

Якщо початкова точка всередині вікна, то вона міняється місцями з кінцевою точкою.

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

Визначення нового коду початкової точки.

Двомірний FC-алгоритм

В 1987 г. Був запропонований алгоритм (Собков, Поспишил і Янг), який називається FC-алгоритмом (Fast Clipping), що використовує кодування не кінцевих точок, а ліній цілком.

Схема кодування подібна до тої, що використовується в алгоритмі Коена-Сазерленда (рис. 2). Простір поділяється на 9 областей, що перекриваються і пронумеровані арабськими цифрами від 1 до 9. Коди, які назначені кінцям відрізків, що потрапили в ту чи іншу область, приведені в двійковому і шістнадцятковому вигляді (запис вигляду 0xD).



Рис. 2. Завдання кодів для FC-алгоритму

Відрізок видимий тільки в області 5, тобто відрізок, координати якого задовольняють умовам:

Xлів \xF0A3 X \xF0A3 Xправ    і    Yниж \xF0A3 Y \xF0A3 Yверх.





Кожна кінцева точка відрізку V0V1 буде знаходитися в цих областях. Комбінація кодів кінців відрізка, називається кодом лінії, і використовується для визначення можливих варіантів розміщення відрізку і його відсікання. Код лінії формується з кодів кінця відрізка наступним чином:

LineCode (V0,V1)    =   (Code(V0) *16) + Code (V1),



де Code(V1) означає код кінцевої точки V1, Code(V0) * 16 означає зсув коду початкової точки V0 вліво на 4 розряди.

Так як кожний код може приймати одно з 9 значень, то всього є 81 можливий варіантів розміщення відрізка. Але, якщо Code(V0) рівний Code(V1), то LineCode(V0,V1) рівний LineCode(V1,V0). Є всього 9 таких випадків: 1-1, 2-2, \xF0BC 9-9. Звідси слідує, що число різних випадків зменшується до 72.

Кожний LineCode вимагає свого набору обчислень для визначення відсікання відрізка за мінімальний час. Всього є 8 основних випадків відсікання, а інші симетричні до них.

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

\xF0B7 початкова точка відрізку вважається точкою номер 0 (V0),

\xF0B7 кінцева точка відрізка вважається точкою номер 1 (V1),

\xF0B7 ClipA_B означає алгоритм розрахунку переміщення кінцевої точки номер А на сторону вікна B (розрахунок перетинання прямої лінії, на якій розміщений відрізок, що відсікається зі стороною вікна B).

Ілюстрація до випадків 1-7 приведений на рис. 3, для випадку 8 - на рис. 4.

1. Початкова і кінцева точки відрізка обидві в області 5 (відрізок JK). Це простий випадок прийняття відрізка.

2. Початкова і кінцева точки відрізка обидві в області 4 (відрізок LA). Відрізок не перетинає видиму область, так що це простий випадок відкидання.

3. Початкова точка в області 4, кінцева - в області 1 (відрізок LB). Відрізок не перетинає видиму область, так що це простий випадок відкидання.

4. Початкова точка в області 4, кінцева - в області 2 (відрізки LC і LD). Відрізки явно перетинає Xлів, так що спочатку необхідно визначити відповідну координату, використовуючи алгоритм Clip0_Xleft. Для відрізка LC це дає V0y > Yверх, так що відрізок повинен бути відкинений без подальших обчислень. Відрізок LD входить в вікно з лівої сторони і може виходити через верх. Відповідно, наступне відсікання повинно бути Clip1_Top, після якого відрізок приймається.

8

\x2403\x1103\x1C84\x1202\x6864\x0101\x6000\x1C84\x6102\x0324

\x2403\x1103\x1C84\x1202\x6864\x0101\x6000\x1C84\x6102\x0324