Toto je jen tak nahrubo nastrelena kopie. Az bude cela stranka dopsana, tak ji sem prsknu v cele jeji krase. -- slady
Bresenhamův algoritmus
Bresenhamův algoritmus kreslení úsečky je vhodná aproximace vektorově zadané úsečky v mřížce bodů uspořádaných do čtverce.
Počáteční informace jsou dva body:
- bod v mřížce bodů, kde úsečka začíná
- bod v mřížce bodů, kde úsečka končí
Mezi těmito krajními body úsečky jsou body mřížky vyplňovány tak, že se dotýkají buď společnou hranou anebo společným vrcholem čtverečků.
Pro ilustraci se omezíme na pravou dolní polovinu prvního kvadrantu, tedy budeme kreslit doprava, případně mírně nahoru. Úprava algoritmu pro kreslení do ostatních směrů je pak velmi snadná.
Způsob vykreslení
V těchto úvahách se pro jednoduchost omezíme na směr kreslení doprava nahoru (maximálně pod úhlem 45 stupňů). Souřadnice mřížky, do které budeme kreslit, si označíme 0, 1, 2... zleva doprava a 0, 1, 2... zdola nahoru (tedy jako kartézské souřadnice, akorát označené celočíselnými nezápornými indexy).
Pro první představu si vykresleme úsečku z bodu (0;0) do bodu (10;0) – to je vodorovná úsečka směřující přímo vpravo. Dále si vykresleme úsečku z bodu (0;0) do bodu (10;10) – to je šikmá úsečka směřující doprava nahoru.
První z nakreslených úseček je ta, pod kterou nebudeme kreslit, druhá je úsečka, nad kterou nebudeme kreslit. Jde vlastně o vytyčení úhlu, do kterého můžeme naším algoritmem kreslit. Přijmeme-li tuto zjednodušující úvahu, bude vše mnohem názornější.
Úsečku můžeme vykreslovat v krůčcích – první nakreslený bod umístíme do levého dolního rohu (0;0), v každém dalším krůčku postoupíme buď: a) o jedno políčko šikmo doprava nahoru, anebo b) o jedno políčko přímo doprava.
Vizualizace algoritmu
Použijte ovládací prvky pro průchod vizualizací algoritmu.
Princip algoritmu
Při každém krůčku se rozhodujeme mezi dvěma alternativami: krokem šikmo směrem (1;1) a krokem rovně směrem (1;0). Vždy vše nebude tak průzračně jasné jako při kreslení vodorovné úsečky (0;0)—(10;0) a šikmé úsečky (0;0)—(10;10).
V nejasných krůčcích bude rozhodujícím předělem vektor (1;1/2) – co povede výš, přikloní se k vektoru (1;1), co povede níž, než vektor (1;1/2), přikloní se k vektoru (1;0).
Rovnici naší úsečky si můžeme vyjádřit jako
y = k * x, dosadíme za k: y = (dy/dx) * x = ((ykonce - ystart)/(xkonce - ystart)) * x
Důležitá je pro nás směrnice úsečky značená k. Budeme-li
úsečku kreslit po krůčcích zleva doprava, zvětšíme při každém
krůčku souřadnici x o jedničku, souřadnici y o k. Protože
však máme celočíselné souřadnice, musíme ještě souřadnici y zaokrouhlit,
například: co bude menší než 3,5 zaokrouhlíme na 3,
čísla větší než 3,5 zaokrouhlíme na 4.
Uvedeme si tedy první algoritmus zapsaný v pseudojazyce:
kreslíme od (x1;y1) do (x2;y2):
dx = x2 - x1
dy = y2 - y1
k = dy / dx
zavedeme x = x1, y = y1
opakujme dokud x nepřesáhne hodnotu x2:
vykreslit bod (x;y) na zaokrouhlené souřadnice
zvýšit x o 1
zvýšit y o k
{konec algoritmu 1}
Toto je vlastně celý funkční postup, jak zobrazit úsečku na mřížce bodů. Při zpracování na počítači nám na něm však vadí: a) při každém vykreslování bodu se musí zaokrouhlovat, což je otravné, b) neustále pracujeme s reálnými čísly, což počítače neovládají zrovna nejlépe.
Zaokrouhlování nejde odstranit – mřížka má pouze celočíselné označení bodů, takže je nutné polohu vykreslovaného bodu aproximovat, přestože známe jeho přesné umístění. Pokusíme se tedy odstranit alespoň práci s reálnými čísly.
Jako mezikrok uvedeme další algoritmus, kde nahradíme zaokrouhlování porovnáním testovaného čísla s číslem s hodnostou 0,5:
kreslíme od (x1;y1) do (x2;y2):
dx = x2 - x1
dy = y2 - y1
k = dy / dx
zavedeme ax = x1, ay = y1, sy = y1
opakujme dokud ax nepřesáhne hodnotu x2:
pokud je (sy - ay) větší než 0,5:
zvýšit ay o 1
vykreslit bod (ax;ay)
zvýšit ax o 1
zvýšit sy o k
{konec algoritmu 2}
Na chvilku se zastavíme u významu nových pomocných proměnných v algoritmu 2.
- ax – je složka x souřadnice, na kterou budeme kreslit
- ay – je složka y souřadnice, na kterou budeme kreslit
- sy – je skutečná složka y, na kterou bychom kreslili, kdyby nebylo označení mřížky celočíselné
Tím, že si udržujeme aktuálně vykreslovanou hodnotu ay i hodnotu sy, na kterou se má bod teoreticky umístit, ulehčíme počítači od zaokrouhlování. Celý trik je ukryt v nerovnici (sy-ay)>1/2.
Příklad na (ne)zaokrouhlování
Porovnání si ukážeme na jednoduchém příkladu. Pokud je směrnice úsečky k=0,4 a už jsme několik křůčků algoritmu provedli, jsme třeba na hodnotě sy=5,2 a ay=5. Kreslíme tedy na bod o výšce 5, zatímco bychom měli ve skutečnosti kreslit ve výšce 5,2.
Dalším krůčkem dostaneme hodnotu sy=5,6! Spočítáme rozdíl sy-ay, vyjde 5,6-5=0,6. Máme tedy 0,6>0,5. Zvýšíme hodnotu ay o jedna na ay=6 a kreslíme ve výšce 6. Vidíme, že v našem příkadu je 5 vhodné zaokrouhlení čísla 5,2 a hodnota 6 představuje zaokrouhlení čísla 5,6.
- - konec příkladu - -
Takto vlastně dostáváme bez zaokrouhlování hodnotu čísla zaokrouhleného, aniž by počítač musel cokoli počítat. Pro plné pochopení principu doporučuji tento algoritmus párkrát projít a odkrokovat s papírem a tužkou v ruce, než se vrhnete na další text.
Dále už zbývá jen odstranit počítání se zlomkem, čehož dosáhneme vynásobením výrazů s ay a sy výrazem 2*dx. Tím odstraníme potřebu směrnice a proměnné k.
Celočíselný algoritmus:
kreslíme od (x1;y1) do (x2;y2):
dx = x2 - x1
dy = y2 - y1
zavedeme ax = x1, ay = y1, py = y1
opakujme dokud ax nepřesáhne hodnotu x2:
pokud je py větší než dx:
snížit py o (2 * dx)
zvýšit ay o 1
vykreslit bod (ax;ay)
zvýšit ax o 1
zvýšit py o (2 * dy)
{konec algoritmu 3}
A máme vyřešeno obojí: zaokrouhlování i zlomky. Navíc pomocný čítač py se nám vhodně pohybuje kolem nuly, takže další úpravou převedeme porovnání oproti dx na vhodné porovnání oproti nule.
Ještě jednou připomínám: Kde se vzaly ony magické vzorce v algoritmu 3 by mělo být jasné, pokud do algoritmu 2 dosadíme za směrnici k=dy/dx a všechny výrazy s ay a sy přenásobíme výrazem 2*dx.
Závěr
Ukázali jsme si odvození algoritmu pro kreslení směrem doprava nahoru. Změna algoritmu pro kreslení doprava dolů je velmi jednoduchá: namísto přičítání jedničky k ay bychom při splnění podmínky odečítali. I změna pro kreslení doleva je prostá: odečítali bychom každém krůčku od ax.
Na vyřešení kreslení nahoru nebo dolů algoritmus změníme trochu více: zavedeme novou proměnnou, která označuje, jakým směrem vlastně kreslíme.
To je celá věda kolem kreslení úsečky, tak jak ji odvodil pan Bressenham.