Материал: Lecture_notes_on_discipline_Meth

Якщо dx > dy, то d = dx, навпаки d = dy;

x = x1 , y = y1

Піксел (х,у) Цикл d разів:

{

xerr = xerr + dx; yerr = yerr + dy:

Якщо xerr > d, то xerr = xerr – d x = x + incx

Якщо yerr > d, то yerr = yerr – d y = y + incy

Піксел (х,у) }

}

Переваги: підвищення швидкодії; можливість використовувать різні випадки при обчисленні прирощень координат для переходу до сусідніх пікселів (чотирьохзв'язні – простіші, але генерують менш якісне зображення за більшу кількість тактів роботи).

2.2 Відсікання ліній

Це одна з основних задач комп’ютерної графіки, що застосовується для запобігання малювання частин об'єкту, які розташовуються поза заданою областю.

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

Програма приймає в якості параметрів дві 2D точки та вирівняний прямокутник (вікно), після чого відсікає межами вікна відрізок прямої, що визначається кінцевими точками р1, р2.

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

21

22

повертає одиницю; якщо пряма відсікається повністю – то функція повертає нуль.

АВ

Рисунок 2.4– Відсікання прямих межами вікна

На рис.2.12 наведені різні випадки розташування відрізків прямої щодо вікна:

відрізок CD – пряма повністю належить вікну ( функція повертає 1);

відрізок АВ – пряма повністю за межами вікна ( функція повертає 0);

відрізок ЕD – одна кінцева точка всередині, друга за межами ( функція відсікає частину відрізка за межами вікна і повертає 1);

відрізок АЕ – дві кінцеві точка поза межами вікна, але відрізок проходить крізь вікно ( функція відсікає два кінця і повертає

1);

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

Алгоритм Кохена-Сазерленда застосовує швидкий метод –

«розділяй і володарюй», виявляє і відкидає два розповсюджені випадки:

тривіальний прийом (обидві кінцеві точки відрізка розташовані усередині вікна, що означає і сам відрізок теж усередині вікна);

тривіальне відхилення(обидві кінцеві точки лежать по один бік вікна, що означає і відрізок поза вікном).

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

22

23

Етап 1: для кожної кінцевої точки відрізка обчислюється «кодове слово - всередині / зовні».

Рисунок 2.5 – Кодування розміщення точки Р відносно вікна

Таблиця 2.1 –Коди “всередині\зовні” для точки

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

Третій випадок – не мають місце ні тривіальний прийом, ні тривіальне відхилення.

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

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

Розглянемо приклад для правої межі вікна(рис.2.6 б). Вибір порядку не істотний, може навіть бути випадок, коли потрібні всі чотири відсікання (рис.2.6 а).

P2

23

24

Рисунок 2.6 – Відсікання відрізку відносно правої границі вікна

Розраховуємо положення точки А. Її координата по х дорівнює правій координаті вікна хА = хwпр, а координату у необхідно обчислити через подобу трикутників:

delyd delxе , де delx, dely – прирощення координат для пари кінцевих точок delx = xP2 –xP1, delу = уP2 –уP1;

е = xP1-xwпр; - поправка по координаті х;

d - шукана поправка по координаті y.

2.3 Алгоритми зафарбовування

2.3.1 Алгоритми заповнення для піксельно визначених областей

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

Алгоритм зафарбовування “пробирається навпомацки”, крізь задану область, від внутрішньої точки до границь фігури: знаходять піксел всередині контура фігури; змінюють колір цього піксела на необхідний; аналізують кольори сусідніх пікселів доти, доки всередині контуру усі пікселі не перефарбуються в колір заповнення.

24

25

При визначенні сусідніх пікселів може використовуватися два випадки: 4-х та 8-ми зв’язність(рис.2.3).

Пікселі контура – границя, за яку заборонено виходити в процесі послідовного перебору усіх сусідніх пікселів (але не будьякий контур може бути границею зафарбовування(рис.2.7а).

Алгоритм заливання. Заливання – це найлегший алгоритм зафарбовування, що використовується в інтерактивних системах малювання.

Етап1: визначити початкову точку всередині контура з координататми (х0,у0);

Етап2: виконати функцію. Функція зафарбовування (х,у)

{

Якщо колір піксела (х,у) не дорівнює границі, то

{

Встановити для піксела (х,у) коліром заливання; Зафарбовування (х+1,у); зафарбовування (х-1,у); зафарбовування (х,у+1); зафарбовування (х,у-1);

}

}

Недоліки алгоритму:

алгоритм рекурсивний, що спричиняє переповнення стеку комп’ютера в ході виконання програми та збій алгоритму;

алгоритм працює «всліпу», перевіряючи сусідів незалежно від того , чи тестувались вони раніше.

Переваги алгоритму:

простота;

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

25