Тема 13 Математичні основи комп’ютерної графіки

 

1.      Базові растрові алгоритми

 

Алгоритм зображення прямої лінії

Розглянемо растрові алгоритми для відрізків прямої лінії. Припустимо, що задані координати (х1, y1 - х2, у2) кінців відрізка прямої. Для виведення лінії необхідно зафарбувати певним кольором всі пікселі вздовж лінії. Для того щоб зафарбувати будь-який піксел, необхідно знати його координати.

Найбільш просто намалювати відрізок горизонтальної лінії. Обчислення поточних координат піксела виконується як прирріст по x (необхідно, щоб х1 ≤ х2), а вивід піксела забезпечується спеціальною функцією. Аналогічно малюється відрізок вертикалі. У циклі виведення горизонтального і вертикального відрізків виконуютьсянайпростіші операції - прирріст на одиницю, перевірка на "<=" та запис піксела в буфер растра. Тому операція малювання таких відрізків виконується швидко і просто. Її використовують як базову операцію для інших операцій, наприклад, в алгоритмах заповнення полігонів.

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

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

Перепишемо це співвідношення як х = f (y):

а також як 

Залежно від кута нахилу прямої виконується цикл по осі х або по у (рис. 13.1).

Рис. 13.1 Відрізок прямої.

Позитивні риси прямого обчислення координат.

1. Простота, ясність побудови алгоритму.

2. Можливість роботи з нецілим значеннями координат відрізка.

Недоліки.

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

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

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

Інкрементні алгоритми виконуються як послідовне обчислення координат сусідніх пікселів шляхом додавання збільшень координат. Прирости розраховуються на основі аналізу функції похибки. У циклі виконуються тільки цілочисельні операції порівняння і додавання/віднімання.

Розглянемо приклад роботи наведеного вище алгоритму Брезенхема для відрізка (х1у1 - х2у2) = (2, 3 - 8, 6). Цей алгоритм є восьмизв'язним, тобто при виконанні збільшень координат для переходу до сусіднього пікселу можливі вісім випадків (рис. 13.2).


Рис. 13.2 Восьмизв’язний алгоритм Брезенхема

 

Алгоритми побудови кривих Безьє

 

Криві Безьє описуються в параметричній формі:

Значення t виступає як параметр, якому відповідають координати окремої точки лінії. Параметрична форма опису може бути зручнішою для деяких кривих, ніж задання у вигляді функції у=ƒ(х), оскільки функція ƒ(х) може бути набагато складнішою, ніж Px(t) і Py(t), крім того, ƒ(x) може бути неоднозначною.

Многочлени Безьє для Рx і Рy мають такий вигляд:

де xi і yi - координати точок-орієнтирів Рi, а величини  - це відомі з комбінаторики, так звані поєднання (вони також відомі як коефіцієнти бінома Ньютона):

Розглянемо криві Безьє, класифікуючи їх за значеннями m.

m=1 (по двох точках) Крива вироджується у відрізок прямої лінії, яка визначається кінцевимиточками Ро і Р1, як показано на рис. 13. 3

 

Рис. 13.3 Крива Безьє (m = 1)

m=2 (по трьох точках, рис. 13.4):

Рис. 13.4 Крива Безьє (m = 2)

m=3 (по чотирьох точках, кубічна, рис 13.5). Використовується досить часто, вособливості в сплайнових кривих:

Рис. 13.5 Кубічні криві Безьє (m = 3)

 

Геометричний алгоритм для кривої дозволяє обчислити координати (х, у) точки кривої Безьє позначенню параметра t.

1. Кожна сторона контуру багатокутника, який проходить по точках-орієнтирах, ділиться пропорційно значенню t.

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

3. Сторони нового контуру знову діляться пропорційно значенню t. І так далі. Це продовжується до тих пір, поки не буде отримана єдина точка розподілу. Ця точка і буде точкою кривої Безьє (рис. 13.6).

Рис. 13.6 Геометричний алгоритм для кривих Безьє

 

 

 

 

 

Алгоритми зображення фігур

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


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

 

Рис. 13.7 Приклад фігури

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

Розглянемо алгоритми зафарбовування довільного контуру, який вже намальований в растрі. Спочатку визначаються координати довільного пікселя,що знаходиться всередині окресленого контуру фігури. Колір цього пікселя змінюємо напотрібний колір заповнення. Потім проводиться аналіз квітів усіх сусідніх пікселів. Якщоколір деякого сусіднього пікселя НЕ дорівнює кольору границі контуру або кольору заповнення, то колір цього пікселя змінюється на колір заповнення. Потім аналізується колір пікселів, сусідніх з попередніми. І так далі, поки всередині контуру всі піксел і НЕ перефарбуються в колір заповнення. Піксели контуру утворюють межу, за яку не можна виходити в ході послідовного перебору всіх сусідніх пікселів. Сусідніми можуть вважатися тільки чотири пікселя або вісім пікселів (восьми-зв'язність).

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

Рис. 13.8 Алгоритм зафарбовування лініями

Алгоритми заповнення, які використовують математичний опис контуру. Математичним описом контуру фігури може служити рівняння у=f(x) для контypa кола, еліпса або інший кривої. Для багатокутника (полігону) контур задається безліччю координат вершин (хi, уi). Можливі й інші форми опису контуру. Спільним для розглянутих нижче алгоритмів є те, що для генерації точок заповнення не потрібні попередньо сформовані в растрі пікселі контуру фігури. Контур може взагалі не малюватися в растрі ні до, ні після заповнення.

 

2.      Математичні основи векторної графіки

 

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

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

У векторній графіці точці відповідає вузол. На площині цей об'єкт представляється двома числами (X, Y), що задають його положення щодо початкуко ординат.

Для опису прямої лінії використовується рівняння

Y = аХ + b.

Тому для побудови даного об'єкта потрібно задання всього двох параметрів: а і b. Результатом буде побудова нескінченної прямої в декартових координатах. На відміну від прямої, відрізок прямої вимагає для свого опису двох додаткових параметрів, що відповідають початку і кінцю відрізка (наприклад, X1 і Х2).

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

Для побудови відрізка кривої потрібно задати два додаткові параметри.

На відміну від кривих другого порядку криві третього порядку можуть мати точку перегину. Наприклад, графік функції (Рис. 13.9) має точку перегину на початку координат (0, 0). Саме ця особливість даного класу функцій дозволяє використовувати їх в якості основних кривих для моделювання різних природних об'єктів у векторній графіці.

Слід зазначити, що згадані раніше прямі і криві другого порядку є окремим випадком кривих третього порядку. Канонічне рівняння, яке використовується для опису рівняння третього порядку,вимагає для свого завдання дев'яти параметрів:

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

Криві Безьє - це окремий вид кривих третього порядку, що вимагає для свого опису меншої кількості параметрів - восьми замість одинадцяти. В основі побудови кривих Безьє лежить використання двох дотичних, проведених до крайніх точок відрізка лінії (рис. 13.9, праворуч). На кривизну (форму) лінії впливає кут нахилу і довжина відрізка дотичної, значеннями яких можна управляти в інтерактивному режимі шляхом перетягування їх кінцевих точок. Таким чином, дотичні виконують функції віртуальних важелів, що дозволяють керувати формою кривої.


Рис. 13.9 Представлення кривої третього порядку в класичному виді (зліва) та у вигляді кривої Безьє (справа)

 

3.      Алгоритми фрактальної графіки

 

В даний час алгоритми, використовувані для генерації зображень фрактальної графіки, знаходять застосування і в традиційних видах комп'ютерної графіки: растрової та векторної. Наприклад, в CorelDRAW ці алгоритми використовуютьсядля створення текстурних заливок. Фрактал можна визначити як об'єкт досить складної форми, яка отриманав результаті виконання простого ітераційного циклу. Ітераційність, рекурсивність процедури створення обумовлюють такі властивості фракталів, як самоподібність -окремі частини схожі за формою на весь фрактал в цілому. Латинське fractus означає"складено з фрагментів". Слово "фрактал" стало модним, і залишається таким і понині.

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

 де k = 0, 1, ..., п. Величини zk - це комплексні числа, zk = хk + 1уk, причому стартові значення х0 і у0 - це координати точки зображення. Для кожної точки зображення ітерації виконуються обмежену кількість разів (n) або до тих пір, поки модульчисла zk не перевищує 2. Модуль комплексного числа дорівнює кореню квадратному з х22. Для обчислення квадрата величини zk можна скористатися формулою z2 = (Х + iy) (x + iy) = x22+і2xyЦикл ітерацій для фрактала Мандельброта можна виконувати в діапазоні x = (від -2. 2, до 1), у = (від -1. 2 до 1. 2). Для того щоб отримати зображення в растрі, необхідно перераховувати координати цього діапазону в піксельні (рис. 13.10).

Рис. 13.10 Фрактал Мандельброта

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

Рис. 13.11. Геометричні інтерпретації для кривої Коха

 

Наступну групу складають фрактали, які генеруються відповідно до методу"систем ітеративних функцій" - IFS (Iterated Functions Systems). Цей метод може бутио писаний, як послідовний ітеративний розрахунок координат нових точок упросторі:

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

Метод IFS використовується не тільки для створення зображень. його використовували Барнслі і Слоан для ефективного стиснення графічних зображень при записі у файл. Основна ідея така: оскільки фрактали можуть представляти дуже складні зображення за допомогою простих ітерацій, то опис цих ітерацій вимагає значно меншого обсягу інформації, ніж відповідні растрові зображення. Для кодування зображень необхідно вирішувати зворотну задачу – для зображення (або його фрагмента) підібрати відповідні коефіцієнти афінного перетворення. Цей метод використовується для запису кольорових фотографій у файли зі стисненням в десятки і сотні разів без помітного погіршення зображення. Формат таких графічних файлів був названий FIF (Fractal Image Format) і запатентований фірмою IteratedSystems.