____ __ __
/ __ \ / / /_/\
/ /L/ /,_____ _______ _,__ / /_ ____,__,_,__ __ \_\/_ __
/ __ / __/ _ \/ __/ _ \/ __ \/ __ \/ __ / _ _ \/ / / / / / /\
/ /L/ / /\/ ___L\ \/ ___/ /\/ / / / / /L/ / // // / /_/ /\ \/ / /
/_____/_/ /\___/___/\___/_/ /_/_/ /_/\__._/_//_//_/\____/ /\__/ /
\_____\_\/ \__\___\/\__\_\/\_\_\/\_\/\_\_\_\\_\\_\/\___\/ \_\/
/ /\ /_/ /\
____,_/ /_/_,_____ _,___\/ __/,_,__ __ ______
/ __ / / __ / __ \/ __/ / /\/ _ _ \/ / / / __/\
/ /L/ / / /L/ / /L/ / /\/ / /_/ // // / /_/ L\ \_\/
\__._/_/\__ /\____/_/ /_/\__/_// // /\____/___/\
\_\_\_/____/ /\___\_\/\_\/\_\_\\_\\_\/\___\___\/
\____\/
Když jsem pročítal minulá čísla Výhně, konkrétně rubriku
programování, objevil jsem jeden malý nedostatek všech těch návodů na
vektorovou grafiku. Všichni totiž asi předpokládají, že znáte nějaký
použitelný algoritmus na kreslení čar a lineární interpolaci
čehokoliv vůbec. Pro ty z vás, kteří umí kreslit čáry zatím jenom
knihovními funkcemi, ReDoxím tetragonem a případně nějakou šíleností
se tedy chci pokusit popsat jeden naprosto geniální a přitom kupodivu
pochopitelný algoritmus, který se podle autora nazývá bresenhamův.
ČISTĚ MATEMATICKÝ POSTUP
Každou přímku v rovině můžeme matematicky popsat jako množinu bodů,
které vyhovují rovnici
a x + b y + c = 0 (a, b, c ε R). (1)
Z této rovnice můžeme vyjádřit jednu proměnnou v závislosti na druhé
y = k x + q (k, q ε R) (2)
a postupným dosazováním získat souřadnice jednotlivých bodů.
Doporučuje se při tom vyjadřovat tu proměnnou, která roste/klesá
pomaleji (má větší absolutní hodnotu koeficientu), abychom mohli
dosazovat pouze celočíselné hodnoty řídící proměnné a hodnoty závislé
proměnné se nikdy nelišily o více než 1 (jinak vzniknou v čáře díry!)
Tenhle postup má jednu kolosální vadu. Násobení reálnou konstantou k
v (2) je hrozně pómálé.
PRINCIP BRESENHAMOVA ALGORITMU
o------- +
P1 -------- |
-------- | deltaY
-------- P2 |
-------o +
+--------------------------------------+
deltaX
Pro každou úsečku však platí, že když se X změní deltaX-krát, Y se
změní deltaY-krát. Takže vytvoříme proměnou d (d jako rozhodovací),
která se při změně x o jedna změní o deltaY (jenom x*deltaY). No a
až se tahle proměnná změní o deltaX, je čas změnit také Y. Já vím, že
to vysvětlení je zmatené, ale když si to zkusíte, tak to tak vážně
funguje.
ZÁKLADNÍ POSTUP
Takže tady je popis postupu:
1) Inicializace proměnných: D = 0, X = X1, Y = Y1, deltaX = |X2-X1|,
deltaY = |Y2 - Y1| (zatím předpokládáme, že deltaY < deltaX a
deltaX i deltaY jsou kladné)
2) Nakreslíme bod na souřadnicích [X,Y]
3) Pokud X == X2 skončíme (na Y == Y2 se můžeme spolehnout)
4) Zvýšíme X (X++)
5) K D přidáme deltaY
6) Když D >= deltaX, D -= deltaY, Y++
7) Skok na bod 2
Ještě poznámka - takhle nakreslená čára bude nesymetrická. Proto je
výhodnější nainicializovat proměnnou D na hodnotu deltaX/2. A protože
testovat D >= deltaX je složitější, než testovat přetečení při
přičítání, je zvlášť při kódování v asembleru lepší inicializovat D
na -deltaX/2 a testovat přetečení při přičítání proměnné D.
ODSTRANĚNÍ OMEZENÍ PRO deltaX A deltaY
1) První možností je napsat osm variant pro případy:
X roste, Y roste, |deltaX| > |deltaY| (a)
X klesá, Y klesá, |deltaX| > |deltaY| (b)
X roste, Y klesá, |deltaX| > |deltaY| (c)
X klesá, Y roste, |deltaX| > |deltaY| (d)
Y roste, X roste, |deltaX| < |deltaY| (e)
Y klesá, X klesá, |deltaX| < |deltaY| (f)
Y roste, X klesá, |deltaX| < |deltaY| (g)
Y klesá, X roste, |deltaX| < |deltaY| (h)
2) Zkrátit na polovinu můžeme tak, že případy (b,d,f,h) převedeme
na případy (a,c,e,h) tím, že setřídíme počáteční a koncový bod
podle X resp. Y souřadnice (případy (e,f,g,h) používají řídící
proměnou Y). Jinak řečeno počáteční bod je ten, který má menší
hodnotu řídící proměnné. Takže se rutina zkrátí na čtyři případy:
Y roste, |deltaX| > |deltaY| (i)
Y klesá, |deltaX| > |deltaY| (j)
X roste, |deltaX| < |deltaY| (k)
X klesá, |deltaX| < |deltaY| (l)
3) Případy (j,l) lze převést na případy (i,k) tak, že si pamatujeme,
jestli Y respektive X má růst nebo klesat a podle toho místo
pevného INC nebo DEC přičítáme proměnnou obsahující ±1. Bohužel
pak už bývá docela nouze o registry. Je však možné využít fintu se
sebe přepisujícím kódem. Někam sranou si necháme přeložit
instrukce INC a DEC s příslušnými registry a potom, když dostaneme
souřadnice bodů, vybereme si příslušnou instrukci a MOVneme ji na
příslušné místo kódu. (Tuto možnost doporučuji hlavně pro šílence)
4) Můžeme stáhnout řešení na jediný případ tak, že když dojde při
přičítání proměnné D k přetečení, zvyšujeme Y než opět dojde k
přetečení (tentokrát opačným směrem). Problémem této varianty je
správně zvolit pořadí jednotlivých operací cyklu a koncových
podmínek tak, aby rutina fungovala i v případě svislé čáry.
Bohužel jsem to nezkoušel, takže vám neřeknu jak na to. Na
obyčejné čáry jsou ty ostatní metody lepší. Výhoda této metody se
však projeví při texture mappingu nebo shadingu, kdy bodů textury
nebo barev potřebujeme jenom tolik, kolik bodů kreslíme na
obrazovku a jejich vzdálenosti mohou být větší než jedna (každý
druhý pixel textury, barva skákající po 2)
5) Poslední možnost je převést řešení přímky na parametrický problém.
Abych pravdu řekl, je to pěkná vopičárna, ale může se vám to hodit
při texturování nebo nějakých jiných relativně šílených
interpolacích čehosi. Princip je asi takovýhle. Spočítáme si
absolutní hodnoty deltaX a deltaY a také přičítací proměnné
(znaménka deltaX a deltaY). Potom si zavedeme deltaT, které musí
být největší z trojice deltaX, deltaY, deltaT (doporučuje se vzít
větší z deltaX, deltaY), jako rozsah řídící proměnné. Potom se
chováme, jako kdybychom kreslili dvě čáry, jednu se souřadnicemi
T a X a jednu se souřadnicemi T a Y. Musíme je samozřejmě počítat
v jedné smyčce. Potřebujeme však více proměnných, které se těžko
cpou do registrů.
Všech 5 postupů je prakticky aplikovatelných. 1., 4. a 5. možnost
jsou však spíše opičárny než cokoliv jiného a jejich použití se proto
nedoporučuje (i když v nějakém speciálním případě mohou mít svoje
výhody - zatím nevím jaké, ale třeba někdo na nějaké narazíte. V
takovém případě bych o nich rád slyšel. Možná se to bude hodit pro
antialiasing (takovej pseudo - prostě průměrování barev z textury)
Stejně tak se nedoporučuje použití finty z bodu 3. Jedná se sice o
velice elegantní řešení (prasárna na kvadrát:-)), ale mohou s tím být
problémy v P-módu. Bohužel nevím, jak to dopadne, pokud to napíšete v
real-módu a pustíte pod nějakým DPMI ovladačem (např. Wokna:-(). Na
druhou stranu CRT0 (zaváděcí kód) některých P-módových kompilátorů
(DJGPP - D.J.'s GNU Programming Package (GNU C pro DOS)) se postarají
o to, aby se DataSegment a CodeSegment kryly, takže stejné labely
jsou platné v obou, a potom to zapíšte přes DS a spustíte přes CS a
ono to chodí. (V DJGPP to někdo zkoušel (myslim self-rewriting) -
fakt to fachá)
Pro lineární texture mapping, gouraud nebo phong shading a další
techniky je také velmi výhodné používat Bresenhamův algoritmus.
Vzhledem k většímu počtu počítaných souřadnic (od 3 - gouroud - přes
4 - mapping - až po 5 - phong - a třeba i víc (kombinované metody,
bůhvíco:-))) je nutné algoritmus mírně upravit. První možností je
využití parametrického přístupu. Ten má tu výhodu, že máme jnom jednu
obecnou rutinu i pro velké počty souřadnic a nevýhodu, že když
mapujeme velikou texturu na malinkatej trojúhelníček někde kdesi :-),
kreslíme zbytečně moc bodů. Druhá metoda, která v takovém případě
připadá v úvahu, je, že na X a Y použijeme klasickou metodu 2 nebo 3
s variantami pro 2 nebo 4 samostatné případy a pro přičítání
souřadnic v textuře použijeme metodu 4 s vnitřní smyčkou, která
umožňuje v jednom kroku změnit souřadnici o více než ±1. V každém
případě nedoporučuji pro velká množství souřadnic psát rutiny pro
jednotlivé případy zvlášť (počet případů roste geometrickou řadou).
PŘÍKLADY IMPLEMENTACE
viz Druhá stránka
- Bulb -
výheň