1. 3.1. Введення в растеризування кривих
2. 3.2. Зображення відрізка з цілочисельними координатами кінців
3. Цифровий диференціальний аналізатор

Анотація: Введення в растеризування кривих. Зображення відрізка з цілочисельними координатами кінців. Цифровий диференціальний аналізатор. Алгоритм Брезенхема. Алгоритм Кастла-Пітвея. Зображення відрізка з нецілочисельне координатами кінців. Зображення кіл. Алгоритм Брезенхема. Зображення еліпсів. Побудова по неявній функції. Побудова шляхом стиску окружності

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

3.1. Введення в растеризування кривих

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

Мал.3.1.

Зображення кривих на растрі.

Нехай (x0, y0) - фіксований піксель, а (x, y) - деякий інший піксель на площині. Тоді для визначення їх близькості вводяться такі поняття:

1. 4-зв'язність 2. 8-зв'язність

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

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

Нехай наш відрізок - це AB. Перейдемо від системи координат Oxy до Ax'y '( см. рис. 3.2, етап 1 ). Відрізок може лежати в будь-якому з 8 октантів, але завжди існують симетрії щодо осей, що розділяють ці октанти, симетрії визначаються матрицями

і дозволяють звести задачу до випадку відрізка, що лежить в першому Октант (приклад см. на рис. 3.2, етап 2 , В ньому матриця має вигляд Назвемо такий випадок канонічним, надалі будуть розглянуті алгоритми для цього випадку. У канонічному випадку процес малювання 8 -связной лінії можна закодувати послідовністю виду: sdssd ... ( см. рис. 3.3 ), Де

• s - горизонтальний зсув;
• d - діагональне зміщення.

Перехід до канонічного нагоди в два етапи.

Еквівалентно цієї послідовності можна зіставити бінарний код, де 0 відповідає s, а 1 відповідає d. Такий код для малювання відрізка називається кодом Ротштейна [46] для .

Нехай plot (x, y) - функція, зафарбовувати точку растра з координатами (x, y).

Мал.3.3.

Кодування зафарбовування відрізка (або код Ротштейна).

Цифровий диференціальний аналізатор

Алгоритм Цифровий диференціальний аналізатор (англ. DDA - Digital Differential Analyzer) будує 8-зв'язну лінію.

Для початку, нехай P1 = (1, 0); P2 = (1, 1). Для визначення того, який з пікселів, - P1 або P2, - слід зафарбувати, зрівняємо відстані до них. У зв'язку з подібністю трикутників, утворених перетином мальованої відрізка, прямої x = 1 і перпендикулярами з P1 і P2 на відрізок ( см. рис. 3.4 ), Досить порівняти e (ординату перетинання відрізка c прямій x = 1) з . Далі, для наступного кроку алгоритм працює аналогічно з урахуванням зміни e - ординати перетинання відрізка з наступної вертикальної прямої .

Цифровий диференціальний аналізатор. // Координати кінців відрізка - (0,0) і (a, b) e = b / a; // Поточна ордината delta_e = b / a; // Приріст ординати // (x, y) - Координати поточної точки x = 0; y = 0; while (x <a) {plot (x, y); if (e> 1/2) {// d: діагональний зсув x ++; y ++; // тому що відбувся зсув по y на 1 нагору e + = delta_e - 1; } Else {// s: горизонтальний зсув x ++; e + = delta_e; }} Лістинг 3.1. Цифровий диференціальний аналізатор

Недоліком даного алгоритму є те, що він працює з числами з плаваючою точкою.