2.1.4 Алгоритм Брезенхема побудови елiпса

Опис алгоритму. Побудова ітераційного алгоритму типа Брезенхема побудови еліпса є аналогічною побудові алгоритму Брезенхема для прямої. Загальний алгоритм формування еліпсів, осі яких не є паралельними осям координат див. у [14].

Наведемо далi "алгоритм середньої точки" для еліпса з центром у початку координат i напiвосями, що паралельні осям координат. Тоді рівняння еліпса має вигляд

b2 x2 + a2 y2 - a2 b2 = 0, a, b>0.

(5)

Для визначення того, який з пiкселiв є найближчим до еліпсу алгоритм використовує значення рівняння еліпса у середній точці між пiкселами. Якщо це значення є від’ємним, то середня точка знаходиться у середині еліпса, додатним -- зовні еліпса.

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

Виникає питання, який з сусiднiх пiкселiв треба дослiджувати на k-му кроцi iтерацiйного алгоритму при переходi вiд пiксела A (інше позначення A₀₀[x_{k - 1}, y_{k - 1}]) до наступного пiксела. Цей вибiр залежить вiд вiдношення dy/dx, тобто вiд нахилу "дотичної до елiпса".

При dy/dx>-1, алгоритм здiйснює вибiр мiж двома пiкселами, що розташованi вертикально пiксел A₊₀[x_{k - 1}+1, y_{k - 1}] або пiксел A_+-[x_{k – 1} +1, y_{k – 1} - 1].

При dy/dx<-1 --- мiж двома пiкселями, що розташованi горизонтально пiксел A_0-[x_{k - 1}, y_{k - 1}-1] або пiксел A₊₀[x_{k – 1} + 1, y_{k - 1}].

При dy/dx>-1, алгоритм визначає для кожного пiкселя, що формується, яка з двох точок -- A₊₀ або A_+- -- розташована ближче до елiпса. Для цього перевiряємо, розташована середня точка B = (A₊₀ + A_+-)/2 вiдрiзка [A₊₀ A_+-] у серединi або зовнi елiпса.Легко перевiрити, що B[x_{k – 1} +1, y_{k – 1} - 1/2]. Тому все залежить вiд знаку функцiї вiдхилення

k = k (B) = b2(xk – 1 +1)2 + a2 (yk – 1 - 1/2)2 - a2 b2.

(6)

Так саме як у алгоритмi Брезенхема, значення _k обчислюються iтеративним чином.

_k - _{k – 1} = [b²(x_{k – 1} +1)² + a² (y_{k – 1} - 1/2)² - a² b²]

-[b²x²_{k – 1} + a²(y_{k – 1} -1/2)² - a² b²] = 2b² x_k-1+b².

Пiсля знаходження рiзницi _k i _k-1 (тобто _k y) ще треба множити x²_k на сталу. Але цього можна уникнути, обчислюючи _k x (також як _k y) додаючи 2b² на кожному iтерацiйному кроцi.

Якщо пiксел A₊₀ є ближчим до елiпса ( _k), то нове значення _k, яке буде обчислено, можна використати як _k-1 у наступнiй iтерацiї. Але, якщо до елiпса ближче точка A_+- , то _k треба скорегувати, зробивши зсув на один крок донизу.

Якщо [x_k ,y_k +1/2] -- середня точка мiж пікселами A₊₀ i A_+- , то [x_k-1, y_k-1 -1/2] - середня точка, що є нижчою пiкселя A_+- i

_k - _k-1 = [b²x²_k-1+a²(y_k-1-1/2)² -a²b²] - [b²x²_k-1+a²(y_k-1+1/2)² -a²b²]=-2a²y_k-1.

Якщо dy/dx<-1, то треба вибирати мiж пiкселями A₊₀ i A_+- , що розташованi горизонтально.

Якщо вибрано пiксел A₊₀, то треба скористатись точкою [x_k-1+1/2, y_k-1-1] i iнкремент (добавка) для дорівнює

_k- _k-1=[b²(x_k-1+1/2)²+a²(y_k-1-1/2)²-a²b²]-[b²(x_k-1+1/2)²+a²(y_k-1-1/2)²-a²b²]=

= - 2a² y_k-1+a².

Якщо вибрано пiксел A_0- , то треба значення _k-1 скорегувати на крок у правому напрямку

_k - _k-1 = [b²(x_k-1+1/2)²+a²y_k-1²-a²b²]-[b²(x_k-1-1/2)²+a²y²_k-1-a²b²]=2b²x_k-1.

Це вказує, як формувати вiдповiднi значення iтерацiйним чином з використанням лише додавання або вiднiмання при виконаннi iтерацiйних циклiв.

Попереднiй аналiз вiдрiзняє випадки, коли dy/dx<-1 i dy/dx>-1. Залишилось розглянути випадок, коли dy/dx=-1. Розглядаючи (5) як тотожнiсть, де y=y(x), отримаємо

2b²x+2a²yy'=0 dy/dx=-(2b²x)/(2a²y)=-1 2b²x=2a²y.

Але у алгоритмi вже використовуються величини 2b²x i 2a²y для обчислення приростiв _ky i _kx, то останнi можна використовувати для визначення моменту, коли значення dy/dx досягне значення -1.

Наведений далi алгоритм креслить за стрiлкою годинника дугу елiпса у першiй чвертi, тобто вiд точки (0,b) до точки (a,0) (на екранi це буде третя чверть).

Спочатку вважаємо, що dy/dx>-1 i вибiр здiйснюємо мiж вертикальними пiкселями, до того, коли стане dy/dx=-1.

При виконаннi умови dy/dx=1 старi значення знаходились для вертикальних пiкселiв, а треба перейти до вибору горизонтальних пiкселiв. У цей момент треба iнкремент для _k обчислити за виразом

_k - _k-1=[b²(x_k-1+1/2)²+a²(y_k-1-1)²-a²b²] -[b²(x_k-1+1)²+a²(y_k-1-1/2)²-a²b²]=

=3(a²-b²)/4-(b²x_k-1+a²y_k-1).

Оскільки алгоритм пiдраховує величини 2b²x_k-1 i 2a²y_k-1, то останнiй вираз можна пiдраховувати за формулою

_k - _k-1=3(a²-b²)/4-(2b²x_k-1+2a²y_k-1)/2.

При виконаннi умови dy/dx<-1 алгоритм здiйснює вибiр горизонтальних пiкселiв.

Реалiзацiя алгоритму. Програма, що наведена далi, є швидкою та ефективною, так як всi обчислення значень змiнних зведенi до додавання та вiднiмання. Внутрiшнi цикли не мiстять множень завдяки попередньому обчисленню значень a², b², 2a², 2b² (вiдповiдно, змiннi Sqr_a, Sqr_b, TwoSqr_a, TwoSqr_b). Початковi значення змiнних пiдраховуються при припущеннi, що перший пiксел виводимо у точцi (0,b).

Таким чином, початкове значення обчислюється для середньої точки мiж пiкселями з координатами (1,b) i (1,b-1), тобто у точцi (1,b-1/2):

:=b²(1)²+a²(b-1/2)²-a²b²=b²-a²b+a²/4.

Початковi значення для dy i dx (їм вiдповiдають змiннi _k i x опису алгоритму):

dx:=2b² 0=0, dy:=2a²(b)=2a²b=TwoSqr_a*b.

Процедура BresenhamEllipse є точною реалiзацiєю наведеного алгоритму.

Спочатку вона формує всi пік селі мiж (0,b) i точкою, де похiдна dy/dx стає рiвною -1.

Потiм процедура корегує значення d ( _k при dy/dx=-1).

Далi iтеративний вибiр пiкселiв продовжується до досягнення осi OX.

Процедура викликає процедуру Set4Pixels для малювання кожного з чотирьох пiкселiв, що вiдповiдають поточному сформованому пiкселю у чотирьох квадрантах вiдносно фактичного центру елiпса (x_c, y₀).

Вiдсiкання точок, яки не є видимими у клiєнтської частинi форми, при цьому не робиться (це здiйснюється системними засобами).

Вiдповiднi процедури.

Процедура виведення пiкселiв.

procedure Set4Pixels(x,y,xc,yc:Integer;Color:Tcolor);

begin {Set4Pixels}

Form1.Canvas.Pixels[xc+x,yc+y]:=Color;

Form1.Canvas.Pixels[xc+x,yc-y]:=Color;

Form1.Canvas.Pixels[xc-x,yc+y]:=Color;

Form1.Canvas.Pixels[xc-x,yc-y]:=Color;

end; {Set4Pixels}

Процедура виведення дуги елiпса у четвертому квадрантi.

procedure RastrBresEllipse(Xc,Yc,a,b,Color:integer);

var

Sqr_a,TwoSqr_a,Sqr_b,TwoSqr_b,x,y,d,dx,dy:integer;

begin {RastrBresEllipse}

if (a>0)and(b>0)

then begin {(a>0)and(b>0)}

// початкове встановлення змiнних

x:=0; y:=b;

Sqr_a:=sqr(a); Sqr_b:=sqr(b);

TwoSqr_a:=2*Sqr_a; TwoSqr_b:=2*Sqr_b;

dx:=0; dy:=b*TwoSqr_a;

// вивiд при dy/dx>-1

while (dx<dy) do

begin {while (dx<dy)}

Set4Pixels(x,y,xc,yc,Color);

if (d>0)

then begin {d>0}

y:=y-1; dy:=dy-TwoSqr_a; d:=d-dy;

end {d>0}

else begin {d<=0}

x:=x+1; dx:=dx+TwoSqr_b; d:=d+Sqr_b+dx;

end; {d<=0}

end; {while (dx<dy)}

// пiдправка при dy/dx=-1

d:=d+round(3*(Sqr_a-Sqr_b)/4+(dx+dy)/2);

// вивiд при dy/dx<-1

while (y>=0) do

begin {while (y>=0)}

Set4Pixels(x,y,xc,yc,Color);

if (d<0)

then begin {d<0}

x:=x+1; dx:=dx+TwoSqr_b; d:=d+dx;

end {d<0}

else begin {d>=0}

y:=y-1; dy:=dy-TwoSqr_a; d:=d-(Sqr_a+dy);

end; {d>=0}

end; {while (y>=0)}

end; {(a>0)and(b>0)}

end; {RastrBresEllipse}

Лiтература.[11]