Rasterizace úsečky algoritmem DDA

Algoritmus DDA (Digital Differential Analyzer) nám nabízí přímé vykreslení úsečky s použitím základního vzorce $$y=ax+b$$ Více o přímce, či úsečce, najdete zde.

DDA

Mějme přímku

pro kterou platí $$\Delta_y=y_B-y_A=1-0=1$$ $$\Delta_x=x_B-x_A=3-0=3$$ tedy $$a=\frac{\Delta_y}{\Delta_x}=\frac{1}{3}$$ Pro každý následující bod tedy musíme přidat jednu jednotku ve směru $y$ a tři ve směru $x$. Nezapomeňte, že pokud vykreslíte přímku jen mezi body $A$ a $B$ tak dostanete úsečku. Všimněte si, že není důležitá přesná velikost $\Delta_y$ a $\Delta_x$, ale jejich vzájemný poměr. Pro tyto dvě směrnice $$a=\frac{2}{6}$$ $$a=\frac{0,5}{1,5}$$ dostaneme úplně stejnou přímku, která prochází počátkem, jak můžete vidět na obrázku.

Rasterizací dle DDA posuneme následující bod o jednu jednotku v jednom směru pevně a ve druhém směru pak v závislosti na směrnici.

Rasterizace úseček se sklonem <= 45°

Dle DDA posuneme následující bod pouze o jednu jednotku $x$ a tomu odpovídající $y$ dle směrnice. Zkusme pro přímku výše vypočítat $\Delta_y$ pokud bude $\Delta_x=1$. $$a=\frac{1/3}{3/3}\doteq\frac{0,333}{1}$$ nebo prostě $$a=\frac{1}{3}\doteq0,333$$ Obecně pak můžeme říct, že $$x_{i}=x_{i-1}+1; y_{i}=y_{i-1}+a$$ Úsečku $AB$ bude rasterizovat pro $x=0..3$.

x	0	1	2	3
y	0	0,3 (0)	0,6 (1)	0,9 (1)

Do rastru nemůžeme přímo zanést body na reálných souřadnicích, musíme tedy zaokrouhlovat. Finální rasterizovaná úsečka je na obrázku.

Implementace

smernice = (yB-yA) / (xB-xA);
y = yA;

for(x = xA; x <= xB; x++) {
   putPixel(x,y);
   y = y + smernice;
}      

Jednoduše kreslíme od počátečního x ke koncovému x a v každém kroku přičteme smernice k y. Je důležité dát pozor, aby první zadaný bod měl souřadnici $x$ menší než druhý. Pokud by tomu tak nebylo, cyklus by neproběhl! Je tedy na začátku nutné body případně prohodit. Pro úsečku jako takovou je v našem případě jedno, je-li zadána $AB$ nebo $BA$.

Rasterizace úseček s jiným sklonem

Pokud nám hodnota směrnice vyjde jedna, dostaneme úsečku se sklonem 45°. Ještě aby ne - pokud posuneme bod o jednu jednotku ve směru $x$, musíme ji posunout o jednu jednotku ve směru $y$. Co když nám směrnice vyjde větší než jedna? Mějme $$a=\frac{3}{1}$$ tedy posun o jednu jednotku ve směru $x$ a o tři ve směru $y$. Pokud bychom použili pro vykreslení algoritmus uvedený výše, dostali bychom úsečku se spoustou děr. Pro první čtyři body by výpočet dopadl následovně

x	0	1	2	3
y	0	3	6	9

což by při vykreslení vypadalo takto

Protože musíme při vykreslení zajistit rasterizaci úsečky bod po bodu a tedy bez mezer, otočíme v tomto případě význam proměnných. O jednu jednotku budeme přidávat ve směru $y$ a dopočítávat dle směrnice krok ve směru $x$. Nezapomeňte, že pokud přičítáme směrnici pro směr $x$, musíme použít její převrácenou hodnotu! Tedy $$\frac{1}{a}=\frac{1}{3}$$ Vypočítáme prvních deset bodů.

x	0	0,3 (0)	0,6 (1)	0,9 (1)	1,2 (1)	1,5 (2)	1,8 (2)	2,1 (2)	2,4 (2)	2,7 (3)
y	0	1	2	3	4	5	6	7	8	9

Úsečka (část přímky) je na obrázku.

Při vykreslování úsečky algoritmem DDA je tedy nutné rozhodnout, který ze směrů bude pevně posouván o jedničku a který počítán.

Literatura a odkazy

KOLCUN, A. Základy počítačovej grafiky. Učební texty, Ostrava 2006.

http://www.netgraphics.sk/dda-algorithm - applet