WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Відсікання відрізків - Реферат

Відсікання відрізків - Реферат

відрізку 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, 9-9. Звідси слідує, що число різних випадків зменшується до 72.
Кожний LineCode вимагає свого набору обчислень для визначеннявідсікання відрізка за мінімальний час. Всього є 8 основних випадків відсікання, а інші симетричні до них.
Розглянемо ці 8 основних випадків. При цьому будемо використовувати наступні позначення:
" початкова точка відрізку вважається точкою номер 0 (V0),
" кінцева точка відрізка вважається точкою номер 1 (V1),
" 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, після якого відрізок приймається.
5. Початкова точка в області 4, кінцева - в області 3 (відрізки LE, LF і LG). Відрізки явно перетинають Xлів. Так само як і для випадку 4 спочатку застосовується Clip0_Xleft і відрізок LE відкидається якщо V0y > Yверх. Якщо ж отримаємо V0y Yверх, то відрізок повинен вийти з області видимості через верхнє або праве ребро. Використовуємо відсікання Clip1_Top і порівнюємо нове значення X-координати кінцевої точки - V1x з Xправ. Якщо V1x Xправ, то відрізок (LF) проходить через верхню сторону, відрізок приймається і подальші обчислення не потрібні. Інакше відрізок (LG) проходить через праву сторону і вимагає відсікання Clip1_Right. Відсікання закінчено, відрізок приймається.
6. Початкова точка в області 4, кінцева - в області 6 (відрізок LH). Даний відрізок видимий. Спочатку використовуємо Clip0_Xleft потім Clip1_Right і приймає відрізок.
7. Початкова точка в області 4, кінцева - в області 5 (відрізок LI). Даний відрізок видимий. Просто використовуємо Clip0_Xleft і приймаємо відрізок.
8. Початкова точка V0 (R, S, T або U) в області 7, кінцева точка V1 (W, X, Y або Z) - в області 3 (див. рис. 4). В цьому випадку можуть бути відкинуті тільки два типи відрізків. Для мінімізації обчислень використовуємо Clip0_Xleft. Якщо V0y > Yверх, то це перший випадок відкидання (відрізок RW). Clip1_Xright і перевірка V1y < Yниж задають другий випадок відкидання (відрізок UZ). Всі інші відрізки повинні бути видимі. Якщо V0y < Yниж, тоді V0 = T, інакше V0 = S. Якщо V0y Yверх, то V1=X і тут необхідний Clip1_Ytop перед прийняттям відрізка. Якщо V1y -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, тоді:
t Qi / Pi.
(8)
Для пояснення на рис. 7 показаний перетин з лівою і правою границями при Pi 0
Якщо Pi > 0, тоді:
t Qi / Pi.
(9)
Для пояснення на рис. 8 показаний перетин з лівою і правою границями при Pi > 0.
Рис. 8. Перетин безмежної лінії, яка визначається точками V0V1 і йде з видимої на невидиму сторону, з лівою і правою границями.
Так як значення параметру t тільки на границі рівний Qi/Pi, а в іншій видимій частині менше Qi/Pi, то значення параметру t має максимум на границі.
Pi = 0
Якщо Pi = 0, тоді:
0 Qi.
(10)
Відмітимо, що тут нема залежності від t, тобто нерівність виконується для всіх t, якщо Qi 0 і не має рішення при Qi < 0. Для пояснення на рис. 9 ілюструється випадок Pi = 0.
Рис. 9. Відносне розміщення безмежної лінії, яка задана точками V0V1 і йде паралельно лівій і правій границям.
Геометрично, якщо Pi = 0, то нема точок перетину безмежної лінії, яка визначається точками V0V1, з лініями границі. Більш того, якщо Qi < 0, то безмежна лінія знаходиться на зовнішній стороні лінії границі, а при Qi 0 знаходиться на внутрішній стороні (включаючи її). В останньому випадку відрізок V0V1 може бути видимий або ні в залежності від того де знаходяться точки V0V1 на безмежній лінії. В попередньому ж випадку нема видимого сегмента, так як безмежна лінія поза вікном, тобто це випадок тривіального відкидання.
Всі ці випадки представлені на схемі:
Рис. 10. Схема алгоритму Ліанга-Барскі
Loading...

 
 

Цікаве