Лабораторна робота №6

Алгоритм відсікання областей зображення

Мета роботи: освоїти алгоритми формування растрового представлення багатокутних областей, які відсікаються прямокутним вікном, ознайомитись з основними етапами використання алгоритму Коена-Зазерленда для відсікання ліній та областей

Постановка задачі

Дано: опис множини відрізків, які задано координатами вершин (x₁;y₁) та (x₂;y₂) та вікно видимості, задане у вигляді прямокутника.

Необхідно: сформувати растрове представлення тих відрізків або їх частин, які видно у заданому вікні за допомогою алгоритму Коена-Сазерленда.

Теоретичні відомості

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

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

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

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

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

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

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

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

В машинній графіці найбільш часто використовуються прямокутні вікна, які задаються рівняннями їх сторін (рис.4.1).

X = X_Л, Х = Х_П,

Y = Y_Л, Y = Y_П.

Підставляючи в рівняння відрізка прямої Y=k·Х+b значення X_Л, Х_П знаходять ординати перетину відповідно з лівою та правою границями вікна. Аналогічно знаходять і точки перетину з верхньою та нижньою границями вікна. Для цього в рівняння прямої підставляють відомі значення Y_Л, Y_П.

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

Провести тестування повної видимості чи невидимості відрізків можна за допомогою алгоритму Д. Коена і А. Сазерленда.

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

Рис. 4.1. Розміщення відрізків прямих відносно вікна

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

1 0 0 1 1 0 0 0 1 0 1 0

0 0 0 1 0 0 0 0 0 0 1 0

0 1 0 1 0 1 0 0 0 1 1 0

Одиниці у відповідних розрядах коду означають:

* першому – точка над верхнім краєм області індикації;

* у другому – точка під нижнім краєм області індикації;

* у третьому – точка праворуч від області індикації;

*; у четвертому – точка зліва від лівого краю області індикації.

Розглянемо характерні випадки.

1. Чотирьохрозрядні коди граничних точок відрізка прямої AB, який повністю належить вікну (рис.4.1), нульові.

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

2. Чотирьохрозрядні коди граничних точок відрізка прямої, який розміщений по одну із сторін вікна (рис. 4.1. Відрізок QL), співпадають. Для встановлення вказаного достатньо виконати операцію логічного множення цих двох кодів, яка для вказаного випадку дасть ненульовий результат.

3. Чотирьохрозрядні коди граничних точок відрізка прямої, який частково знаходиться в області індикації (рис. 4.1., відрізки KD, HZ) не співпадають. Тому, результат логічного множення цих кодів дасть нульовий результат.

Для вказаного випадку необхідно виконати відсікання. Координати точки відрізка, яка належить одній із границь вікна, знаходять із рівняння відрізка y=k·x+b підстановкою в нього відповідних координат граничних точок вікна і знаходженням невідомої координати.

Для відрізка HZ знаходять точку перетину F, яка ділить відрізок на два співставних. Надалі для кожного отриманого відрізка виконуємо алгоритм Коена-Сазерленда. В результаті аналізу відрізок FZ відкидається.

Найбільш складним для відсікання є випадок, коли відрізок прямої двічі перетинає границі вікна (рис. 4.1., відрізок KD). В цьому випадку алгоритм Коена-Сазерленда виконується для трьох співставних відрізків – KE, EP, PD.

4. Якщо відрізок прямої лежить за областю вікна і при цьому його граничні точки не належать однаковим підобластям (рис. 4.1., відрізок SV), то результат логічного множення чотирьохрозрядних кодів дасть нульовий результат. Для визначення повної видимості необхідно перевіряти значення кодів обох кінців окремо.

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

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

В алгоритмі відсікання методом ділення відрізка пополам використовуються коди кінцевих точок відрізка і перевірки, які виявляють повну видимість відрізків, наприклад відрізок a на рис.4.2, і тривіальну невидимість відрізків, наприклад відрізок b на рис.4.2.

Рис. 4.2. Реалізація відсікання згідно алгоритму

ділення відрізка пополам

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

X_m = (X2+X1)/2,

Y_m = (Y2+Y1)/2.

Аналогічні дії застосовуються до кожних одержаних половин відрізків до тих пір, поки не буде виявлено перетин з однією із сторін вікна або довжина відрізка, що розглядається, стане занадто малою, тобто, поки вона не перетвориться в точку. Кількість кроків даного алгоритму дорівнює log₂N, де N – довжина відрізку.

Даний метод проілюстрований на прикладі відрізка с (рис.4.2). Точка Р₁ запам’ятовується, як поточна видима точка, а відрізок с розбивається пополам точкою Pm₁. Відрізок Р₂Pm₁ відкидається, як невидимий, а відрізок Р₁Pm₁ розбивається пополам точкою Pm₂. Відрізок Pm₁Pm₂ відкидається, а в вікні залишається відрізок P₁Pm₂ тому, що перевірка по алгоритму Коена-Сазерленда виявляє, що даний відрізок повністю лежить в області індикації.

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

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

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

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

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

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

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

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

Завдання: Сформувати багатокутний контур деякої фігури і показати його сірим кольором. Рухаючи цей контур повз прямокутного вікна за допомогою стрілок, показувати червоним кольором ту частину контуру, яка потрапляє у область вікна. Відсікання виконувати за допомогою алгоритму Коена-Сазерленда.

Варіанти контурів до лабораторної роботи

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

Контрольні запитання

1. В чому полягає процедура відсікання?

2. Які типи алгоритмів відсікання областей ви знаєте?

3. Чим обумовлена поява метода ділення відрізка пополам?

4. Дати характеристику метода Коена-Сазерленда?

5. Яка схема виконання алгоритму Коена-Сазерленда?

Література

1. Роджерс Д.Алгоритмы машинной графики/ Д. Роджерс. – М.: Мир, 1989. – 230 с.

2. Аглоритмы растровой графики: http://www.fvn2009.narod.ru/Manuscripts/schedule/schedule8.htm

3. Романюк О. Н. Комп’ютерна графіка / О. Н. Романюк. – ВНТУ, 2001. – 200 с.

4. Роджерс Д. Алгоритмические основы машинной графики: Пер. с англ. / Д. Роджерс. – М.: Мир, 1989. – 512 с

Поиск по сайту: