Материал: Lecture_notes_on_discipline_Meth

26

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

ці вершини пов'язані з початковою;

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

початкової точки у вигляді ромбу (рис. 2.8).

Рисунок 2.8– Розповсюдження “хвилі” кольору

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

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

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

Перевага: не використовується рекурсія, що обумовлює ефективнішу послідовність обробки пікселів при зафарбовуванні.

Недолік: мала швидкість (особливо, якщо використовувати повільну функцію setPixel для малювання окремих пікселів в програмах для Windows).

26

27

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

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

(наприклад функція FloodFillАPІWindows)

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

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

а) за допомогою математичної формули y=f(x);

б) за допомогою множини точок (координат вершини полігону або багатокутника).

Алгоритми даного класу не передбачають обов'язкове попереднє створення пікселів контура растру (він може взагалі не виводитися в растр).

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

for(y=y1;y<=y2;y++);

//малюємо горизонтальну лінію з координатами (х1,у)-(х2,у)

Заповнення кола: можна виконати на основі інкрементного алгоритму Брезенхема. В процесі цього алгоритму послідовно розраховуються координати пікселів контура у межах одного октанта.

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

Заповнення полігонів виконується шляхом зафарбовування відрізками прямих ліній (горизонталями) на основі алгоритму ХУ

(рис.2.9). Р1 Р3

27

28

уimax

Р0 Р4

уimin

Р5

Рисунок 2.9 – Заповнення полігону

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

Крок 1: Знайти yimin i yimaх серед всіх вершин Рi; Крок 2: Виконати цикл по осі у від yimin до yimax;

{

Крок 3: Знаходження точок перетину всіх відрізків контура з горизонталлю уі . Координати хj точок перетину записуємо в масив;

Крок 4: Сортування масиву хj за збільшенням х;

Крок 5: Виведення горизонтальних відрізків з координатами

(х0,у)-(х1,у), (х2,у)-(х3,у)…(х2k,y)-(x2k+1,y). Кожен відрізок виводиться кольором заповнення.

}

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

Особливі випадки:

а) Р0,Р4- горизонталь проходить крізь вершину і перетинає контур (в масив записується тільки одна точка перетину, а іншавершина полігону).

б) Р1,Р2,Р3,Р5 – горизонталь торкається вершини контура (координати точки дотику або не записуються або записуються два рази)

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

а) змістити координати вершин контура або горизонталі заповнення так, щоб горизонталі не потрапляли у вершини (це призведе до спотворення форми полігону);

28

29

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

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

Координата перетину відрізка Рi - Pk з горизонталлю у може бути визначена так:

х = хi + (yk – y)(xk – xi) / (yk – yi)

Кількість тактів роботи цього алгоритму визначається таким чином

Nтактів ≈ (yimax - yimin) * Nгор,

де yimax, yimin – діапазон координат у;

Nгор≈k*n – кількість тактів для однієї горизонталі; n – число вершин полігону;

k – коефіцієнт пропорційності.

Якщо виконати попередній відбір ребер, то Nгор≈k*nр, де nр – кількість відібраних ребер. Наприклад, якщо розділити діапазон yimin ,

yimax навпіл, то кількість тактів алгоритму: Nтактів ≈ (yimax - yimin) * Nгор/2 + Nдоп, де Nдоп – кількість тактів для створення списку ребер. Цей

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

2.4 Стиль лінії. Перо

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

Малювання товстої лінії.

1 спосіб: можна побудувати алгоритм виведення товстої лінії на основі алгоритму Брезенхема, тільки замість виведення кожного окремого піксела поставити виведення фігури або лінії, яка відповідає перу (відрізок, прямокутник, коло). Спосіб ефективний для пір’їв у вигляді відрізків.

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

29

30

Недолік: підхід не ефективний для деяких форм пера( квадрат, коло) оскільки кількість тактів роботи алгоритму пропорційна квадрату товщини лінії.

2 спосіб: виведення товстої лінії, як полігону із заповненням. Перевага: немає розривів у вузлах полілінії і добре

промальовуються торці.

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

3 спосіб: малювання товстої лінії накладенням декількох тонких.

Малювання штрихової тонкої лінії: алгоритм базується на інкрементному алгоритмі Брезенхема, але вводиться нова змінна – лічильник пікселів лінії, а також логічна умова, що визначає стиль лінії

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

Малювання штрихової товстої лінії: здіснюється шляхом об’єднання попередніх алгоритмів.

2.5 Стиль заповнення. Кисть. Текстура

Кисть(2D) – поняття для визначення стилів заповнення, що відрізняються від суцільного стилю.

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

Якщо С=const, то одержуємо суцільне заповнення, а якщо будуємо візерунок, то:

С = f(x,y), де f(x,y) – функція, що визначає стиль заповнення. Наприклад, щоб отримати штрихування:

Сш, якщо(x y) mod S T f(x,y)= (для штрихування) =

Сф,інакше

де S –період, Т-товщина штрихів, Сш – колір штрихів, Сф – колір

фону.

Для ілюзії шорсткої матової поверхні, колір C обчислюють, як випадкове значення в певних межах С = random( ).

Для ілюзії напівпрозорої фігури: не малюють пікселі фону.

30