Rasterizácia úsečky
Rasterizácia úsečky patrí k úplným základom počítačovej grafiky, či už ide o vykresľovanie dvojrozmerných tvarov alebo 3D mnohouholníkov. Tento článok má za úlohu osvetliť najčastejšie spôsoby implementácie tejto operácie.
Úsečku v pamäti typicky reprezentujeme dvoma koncovými bodmi so súradnicami x a y. Pri prevode na rastrovou reprezentáciu potrebujeme spojiť tieto dva body neprerušovane a najkratšou cestou. Ako to urobíme? Spôsobov je hneď niekoľko, avšak všetky spravidla počítajú s tým, že uhol úsečky s osou x je medzi 0 a 45 stupňami. Pokiaľ má úsečka akýkoľvek iný sklon, jednoducho daný prípad prevedieme na ten, ktorým sa zaoberáme. Na nasledujúcom obrázku vidíme všetky možné prípady polôh úsečky a informáciu o tom, ako transformovať súradnice, aby sme ich previedli na náš uvažovaný prípad.
transformácia úsečky
Ako súradnice prevedieme, je na nás. Najskôr musíme zistiť polohu úsečky, napr. Výpočtom uhla, porovnávaním veľkostí hodnôt dx a dy (rozdielov súradníc bodov v oboch osiach) alebo podobným spôsobom, ktorý môžeme vhodne zapísať ako funkciu. Ďalej si môžeme napísať ďalšie, transformačný funkciu, ktoré oznámime zistenú polohu úsečky, a ona nám súradnice prevedie buď tam alebo späť. Tejto funkcii odovzdáme súradnice vždy pred tým, než s nimi začneme pracovať, a rovnako aj spracované súradnice vždycky prevedieme pred vykreslením späť. Transformačný funkcia môže vyzerať napr. Nasledovne:
void transformuj(int x, int y, int *nove_x, int *nove_y, int poloha, int smer_prevodu) { if (smer_prevodu == SMER_TAM) // prevod tam { switch (poloha) { case 0: *x_nove = x; *y_nove = y; break; // 0 - 45 stupnu case 1: *x_nove = y; *y_nove = x; break; // 46 - 90 stupnu case 2: *x_nove = y; *y_nove = -1 * x; break; // 91 - 135 stupnu //... } } else // prevod zpet { switch (poloha) { case 0: *x_nove = x; *y_nove = y; break; // 0 - 45 stupnu case 1: *x_nove = y; *y_nove = x; break; // 46 - 90 stupnu case 2: *x_nove = -1 * y; *y_nove = * x; break; // 91 - 135 stupnu //... } //... } }
To je všetko, čo potrebujeme na úvod vedieť a teraz sa poďme pozrieť na to, čo je pre tento článok hlavnou témou - konkrétne algoritmy rasterizácia.
DDA algoritmus
Názov algoritmu znamená digital diferential analyser. Ide o jednoduchý algoritmus, ktorý by asi vymyslel každý z nás. Bol jednou z prvých implementácií, ktorá sa objavila a ako to tak býva, najjednoduchšie riešenie nepatrí k najefektívnejším. Avšak pokiaľ nie je rýchlosť kritickým aspektom našej aplikácie, možno ho použiť.
Princípom algoritmu je pohyb po osi x od prvého bodu k druhému po jednom pixelu, pričom v každom kroku počítame hodnotu y pričítaním smernice úsečky (tá je samozrejme tangens sklonu úsečky, čiže pomer dy / dx). Túto hodnotu zaokrúhľujeme a vykresľujú pixely. Kód algoritmu môže vyzerať napr. Nasledovne:
int x, dx, dy; double y = y1; dx = x2 - x1; dy = y2 - y1; double smernice = dy / (double) dx; for (x = x1; x <= x2; x++) { vykresli_bod(x,(int) y); y = y1 + smernice; }
Pripomeňme, že v reálnom kóde by sme súradnice nejspíš obalili transformačný funkcií, čo by tu však pôsobilo neprehľadnosť.
Error control DDA
Ide o variant predchádzajúceho algoritmu. Princíp je podobný s tým rozdielom, že v každom kroku vypočítavame chybu, ktorej sa dopúšťame zaokrúhľovaním. Ak chyba presiahne hodnotu 0,5 pixelu, posunieme sa o riadok vyššie a od chyby odpočítame 1, aby zostala relatívna k danému riadku.
int x, y, dx, dy; dx = x2 - x1; dy = y2 - y1; double smernice = dy / (double) dx; double chyba = 0; y = y1; for (x = x1; x <= x2; x++) { vykresli_bod(x,(int) y); chyba += smernice; if (chyba => 0.5) { y++; // posun na dalsi radek chyba -= 1.0; // aby chyba zustala relativni k radku } }
Platí tu to isté, čo pre predchádzajúce algoritmus - nie je príliš efektívne, pretože používa výpočty v plávajúcej rádovej čiarke.
Bresenhamův algoritmus
Predchádzajúci algoritmy mali jednu chybu - potrebovali počítať v plávajúcej rádovej čiarke. Hoci nám to nemusí pripadať ako nevýhoda, je faktom, že floating point operácie sú oveľa náročnejšie ako celočíselná aritmetika. Pokiaľ má grafická karta vykresľovať stokrát za sekundu zložitý 3D drôtený model, určite to potrebuje robiť efektívne, nehovoriac o tom, že jednoduchšie hardvér nemusí floating point operácie vôbec podporovať. Tento problém rieši práve Bresenhamův algoritmus, ktorý sa dnes používa najčastejšie.
Prvým krokom je zavedenie tzv. Prediktorom:
p 0 = 2 * dy - dx
Ďalej opäť postupujeme v osi x po jednotlivých pixeloch a podľa prediktor sa rozhodujeme, čo robiť ďalej:
- ak je prediktor väčší alebo rovný 0: p i + 1 = p i + 2dy - 2DX, a posun o riadok vyššie
- v opačnom prípade: p i + 1 = p i + 2dy
Kód teda môže vyzerať takto:
int x, y, dx, dy, p; dx = x2 - x1; dy = y2 - y1; y = y1; p = 2 * dy - dx; // prediktor for (x = x1; x <= x2; x++) { vykresli_bod(x,(int) y); if (p => 0) { y++; // presun na dalsi radek p = p + 2 * dy - 2 * dx; } else { p = p + 2 * dy; } }
Hodnoty 2 * dy a 2 * dx môžeme pre lepšiu optimalizáciu předpočítat a uložiť do zvláštnych premenných, čomu som sa tu opäť pre účel prehľadnosti dovolil vyhnúť.
Ak vás zaujíma odvodenie rovníc pre prediktor, vedzte, že ide o jednoduchú úpravu rovníc algoritmu Error control DDA. Pri ňom platí:
error[i] + dy/dx: < 0,5 error[i + 1] := error[i] + dy/dx >= 0,5 error[i + 1] := error[i] + dy/dx - 1, y++
Vynásobením nerovníc hodnotou 2DX a prevedením jedného člena na ľavú stranu dostaneme:
2 * dx * error[i] + 2 * dy - dx: < 0 error[i + 1] := error[i] + 2 * dy >= 0 error[i + 1] := error[i] + 2 * dy - 2 * dx, y++
Pole error premenujeme na prediktor a sme hotoví.
Záverom
Vidíme, že najlepšou voľbou je pre nás Bresenhamův algoritmus, pretože využíva iba celočíselnú aritmetiku a zaobíde sa dokonca bez delenia. Pokiaľ ale nenavrhujeme hardvérovú dosku, ktorá musí byť čo najviac optimalizovaná, tak sa zaobídeme aj s ostatnými metódami. Tak ako tak je vždy dobré poznať aspoň tieto základné algoritmy.
