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

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

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

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

Реферат з інформатикиНА тему:

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

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

В простих графічних системах достатньо двомірного відсікання, в трьохмірних пакетах використовується трьох і чотирьохмірне відсікання.

Програмне виконання відсікання достатньо повільний процес, тому в потужні дисплеї вбудовується відповідна апаратура. Перша згадка про апаратуру відсікання, який використовує алгоритм відсікання діленням відрізка навпіл з'явилося в 1968р. Ми розглянемо програмні реалізації алгоритму відсікання.

Відрізки відсікання можуть бути трьох класів - цілком видимі, цілком невидимі і ті, що перетинають вікно. Існує два основних типи алгоритмів відсікання - алгоритми, які використовують кодування кінців відрізка або всього відрізка і алгоритми, які використовують параметричне представлення відрізків, що відсікаються і вікна відсікання. Представники першого типу алгоритмів - алгоритм Коена-Сазерленда (Cohen-Sutherland, CS-алгоритм) і FC-алгоритм (Fast Clipping - алгоритм). Представники алгоритмів другого типу - алгоритм Ліанга-Барскі (Liang-Barsky, LB-алгоритм).

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

Двомірний алгоритм Коена-Сазерленда

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

 більшість примітивів міститься цілком в великому вікні,

 більшість примітивів лежить цілком поза відносно маленького вікна.

Ідея алгоритму полягає в наступному: вікно відсікання і частини площини, що прилягає до нього, разом утворюють 9 областей (рис. 1). Кожній з областей присвоєний 4-х розрядний код.

Дві кінцеві точки відрізка отримують 4-х розрядні коди, які відповідають областям, в які вони потрапили. Зміст розрядів коду:

1 рр = 1 - точка над верхнім краєм вікна;

2 рр = 1 - точка під нижнім краєм вікна;

3 рр = 1 - точка праворуч від правого краю вікна;

4 рр = 1 - точка зліва від лівого краю вікна.

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

 якщо коди обох кінців відрізка рівні 0 то відрізок цілком всередині вікна, відсікання не потрібне, відрізок приймається як тривіально видимий (відрізок AB на рис. 1);

 якщо логічне & кодів обох кінців відрізка не дорівнює нулю, то відрізок цілком поза вікном, відсікання не потрібне, відрізок відкидається як тривіально невидимий (відрізок KL на рис. 1);

 якщо логічне & кодів обох кінців відрізка дорівнює нулю, то відрізок підозрілий, він може бути частково видимим (відрізки CD, EF, GH) або цілком невидимим (відрізок IJ); для нього потрібно визначити координати перетинів зі сторонами вікна і для кожної отриманої частині визначити тривіальну видимість або невидимість. При цьому для відрізків CD і IJ необхідно буде обчислення одного перетину, для інших (EF і GH) - двох.

При розрахунку перетину використовується горизонтальність або вертикальність сторін вікна, що дозволяє визначити координату X або Y точки перетину без обчислень.

Рис. 1. Відсікання по методу Коена-Сазерленда

При безпосередньому використанні описаного вище способу відбору цілком видимого або цілком невидимого відрізка після розрахунку перетину необхідно було б обчислення коду розташування точки перетину. Для прикладу розглянемо відрізок CD. Точка перетину позначена як P. В силу того, що границя вікна вважається, що належить вікну, то можна просто прийняти тільки частину відрізка PD, яка потрапила у вікно. Частина ж відрізка CP, насправді виявилася поза вікном, потребує подальшого розглядання, так як логічне І кодів точок C і P дасть 0, тобто відрізок CP не можна просто відкинути. Для рішення цієї проблеми Коен і Сазерленд запропонували заміняти кінцеву точку з ненульовим кодом кінця на точку, що лежить з боку вікна, або на її продовженні.

В цілому схема алгоритму Коена-Сазерленда наступна:

  • Розрахувати коди кінцевих точок відрізка, що відсікається.

    В циклі повторяти пункти 2-6:

  • Якщо логічне І кодів кінцевих точок не дорівнює 0, то відрізок цілком поза вікном. Він відкидається і відсікання закінчено.

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

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

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

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

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

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

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

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

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

    Xлів  X  Xправ і Yниж  Y  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,  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ниж, то Clip1_Ybottom дасть точку V0 на ребрі вікна. Аналогічно, якщо V1y > Yверх, то V1=X і тут необхідний Clip1_Ytop перед прийняттям відрізка. Якщо V1y < Yверх, тоді V1 = Y.

    Рис. 3. Варіанти розміщення відрізка для не кутових областей

    Рис. 4. Випадок кутових областей

  • Loading...

     
     

    Цікаве