загрузка...
загрузка...
На головну

I. Зображення кіл

Зображення кривих 2

лекція 3

СПИСОК ЛІТЕРАТУРИ

[Cyrus-Beck, 1978]Cyrus M., Beck J. Generalized Two- and Three-Dimensional Clipping // Computers & Graphics.- 1978.- Vol. 3.- pp. 23-28.

[Kuzmin, 1995]Kuzmin Y.P. Bresenham's Line Generation Algorithm with Built-in Clipping // Computer Graphics Forum.- 1995.- Vol. 14, No. 5 (Dec.).

Мал. 1. Симетрії при зображенні окружності.  Для початку перейдемо до канонічної системі координат, в якій центр окружності збігається з початком координат. Тоді можна помітити, в силу симетрії окружності щодо прямих поділяють октанти, що досить побудувати растрове подання в одному Октант, а потім за допомогою симетрій отримати зображення в інших октантах. Будемо користуватися завданням окружності у вигляді неявної функції: x2+ y2 - R2= 0 Нехай f (x, y) = x2+ y2 - R2Будемо малювати шматок окружності в 4 Октант, починаючи з точки (-R, 0) Нехай R I N, тоді f (x, y) I Z для x I Z, y I Z. Нехай функція plot8 (x, y) зображує все 8 точок, отриманих з (x, y) за допомогою симетрій.

Алгоритм Брезенхема. [Bresenham, 1977]

Будемо міркувати подібно алгоритму Брезенхема для відрізків (з відповідними поправками на 4 октант). З двох можливих пікселів в 4 Октант (відповідних вертикальному і діагональному зсувам, див. Рис. 4) будемо вибирати той, відстань від окружності до якого менше.

Мал. 2. Наближене порівняння відстаней.Мал. 3. Відстані до окружності.  Для того, щоб вибрати один з двох можливих пікселів, будемо порівнювати відстані від них до окружності, де відстань менше - той піксель і буде шуканим. У прикладі на Рис. 3 порівнюються відстані від точок S і d до кола з радіусом R. З евклідової метрики отримуємо: DRs= DRd= Але обчислення квадратного кореня - обчислювально трудомістка операція, тому при досить великих Rми будемо замінювати порівняння відстаней порівнянням наближених значень їх квадратів (див. Рис. 2):Зменшимо два доданків на приблизно однакові величини:, Отримаємо:1) D ближче до окружності, ніж S U (xs)2 + (ys)2 + (Xd)2 + (yd)2 - 2 * R2 > 0 2) S ближче до окружності, ніж D U (xs)2 + (ys)2 + (Xd)2 + (yd)2 - 2 * R2 <0  
Мал. 4. Алгоритм Брезенхема.  Нехай (x, y) - поточний піксель. позначимо FS= F (x, y + 1) = x2+ (Y + 1)2 - R2 > 0 Fd= F (x + 1, y + 1) = (x + 1)2+ (Y + 1)2 - R2 <0 F = FS+ FdDF (s) = (DFпрі переході s: (x, y) -> (x, y + 1)) = f (x, y + 2) + + f (x + 1, y + 2) - f (x , y + 1) - f (x + 1, y + 1) = 4y + 6 DF (d) = (DFпрі переході d: (x, y) -> (x + 1, y + 1)) = f ( x + 1, y + 2) + f (x + 2, y + 2) - f (x, y + 1) - f (x + 1, y + 1) = 4x + 4y + 10
       

Тоді з двох можливих зсувів d и sми виберемо:

1) F = FS+ Fd > 0 U FS > -Fd, Т. Е. (X + 1, y + 1)ближча до кола, ніж (X, y + 1):

d: переходимо в (X + 1, y + 1)і надаємо відповідні збільшення F, DF (s), DF (d)

F = F + DF (d); DF (s) = DF (s) +4; DF (d)=DF (d) + 8;

2) F = FS+ Fd <0 U FS <-Fd, Т. Е. (X, y + 1)ближча до кола, ніж (X + 1, y + 1):

s: переходимо в (X, y + 1)і надаємо відповідні збільшення F, DF (s), DF (d)

F = F + DF (s); DF (s) = DF (s) +4; DF (d)=DF (d) + 4;

Якщо ми починаємо з (-R, 0),то початкові значення будуть наступними:

F=FS +Fd = ((-R)2+12 - R2) + ((-R + 1)2+12 - R2) = 1 + (- 2 * R + 1 + 1) = 3-2 * R;

DF (s) = 4 * 0 + 6 = 6;

DF (d) = 4 * (- R) + 4 * 0 + 10 = 10 - 4 * R;

Легко бачити, що в алгоритмі всі величини, пов'язані з F,крім Fпочаткового, будуть кратні 2. Але, якщо ми поділимо всі ці величини на 2 (надалі, значення всіх величин вже розуміються в цьому сенсі), то Fнач =1/2 + 1-R.Т. к. Збільшення Fможуть бути тільки цілочисельними, то F = 1/2 + T, деTIZ; т. е. якщо відняти 1/2 від усіх значень, то знак F не зміниться для всіх T,крім T= 0. Для того, щоб результат порівняння залишився колишнім, будемо вважати, що F = 0 тепер відповідає зсуву s.

алгоритм:

x = -r;

y = 0;

F = 1-r;

dFs = 3; // DF (s)

dFd = 5-2 * r; // DF (d)

while (x + y <= 0)

{

plot8 (x, y);

if (F> = 0)

{

// d: Діагональне зміщення

F + = dFd;

x ++; y ++;

dFs + = 2;

dFd + = 4;

}

else

{

// s: Вертикальний зсув

F + = dFs;

y ++;

dFs + = 2;

dFd + = 2;

}

}

Розмірність обчислень цього алгоритму (т. Е. Ставлення максимальних модулів значень величин, з якими він оперує до модулів вихідних даних (в даному випадку R)) Дорівнює 2.

Алгоритм Кузьміна. [Kuzmin, 1990]

Швидше, використовує всього 3 змінні і має розмірність обчислень 1. Даний алгоритм фактично є модифікацією алгоритму Брезенхема і отриманий з нього розподілом відповідних змінних ще раз на 2, що призвело до необхідності використовувати поняття парності для визначення точки старту. Докладнішу інформацію можна знайти [Kuzmin, 1990].

алгоритм:

x = R;

y = 0;

e = -R / 2;

if (R & 1) {e--; goto odd; }

even:

plot8 (x, y);

if (y> = x) return;

e + = y ++;

if (e> = 0) e - = - x;

odd:

plot8 (x, y);

if (y> = x) return;

e + = ++ y;

if (e> = 0) e - = - x;

goto even;

Відсікання неопуклого многоугольником без самоперетинів. «-- попередня | наступна --» II. Зображення еліпсів та інших кривих другого порядку.
загрузка...
© om.net.ua