Lekce 1 - Rasterizace úsečky
Rasterizace úsečky patří k úplným základům počítačové grafiky, ať už jde o vykreslování dvourozměrných tvarů nebo 3D mnohoúhelníků. Tento článek má za úkol osvětlit nejčastější způsoby implementace této operace.
Úsečku v paměti typicky reprezentujeme dvěma koncovými body se souřadnicemi x a y. Při převodu na rastrovou reprezentaci potřebujeme spojit tyto dva body nepřerušovaně a nejkratší cestou. Jak to uděláme? Způsobů je hned několik, avšak všechny zpravidla počítají s tím, že úhel úsečky s osou x je mezi 0 a 45 stupni. Pokud má úsečka jakýkoli jiný sklon, jednoduše daný případ převedeme na ten, kterým se zabýváme. Na následujícím obrázku vidíme všechny možné případy poloh úsečky a informaci o tom, jak transformovat souřadnice, abychom je převedli na náš uvažovaný případ.
Transformace úsečky
Jak souřadnice převedeme, je na nás. Nejdřív musíme zjistit polohu úsečky, např. vypočítáním úhlu, porovnáváním velikostí hodnot dx a dy (rozdílů souřadnic bodů v obou osách) nebo podobným způsobem, který můžeme vhodně zapsat jako funkci. Dále si můžeme napsat další, transformační funkci, které sdělíme zjištěnou polohu úsečky, a ona nám souřadnice převede buď tam anebo zpět. Této funkci předáme souřadnice vždycky před tím, než s nimi začneme pracovat, a stejně tak zpracované souřadnice vždycky převedeme před vykreslením zpět. Transformační funkce může vypadat např. takto:
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še, co potřebujeme na úvod vědět a nyní se pojďme podívat na to, co je pro tento článek hlavním tématem - konkrétní algoritmy rasterizace.
DDA algoritmus
Název algoritmu znamená digital diferential analyser. Jde o jednoduchý algoritmus, který by asi vymyslel každý z nás. Byl jednou z prvních implementací, která se objevila a jak to tak bývá, nejjednodušší řešení nepatří k nejefektivnějším. Avšak pokud není rychlost kritickým aspektem naší aplikace, lze jej použít.
Principem algoritmu je pohyb po ose x od prvního bodu k druhému po jednom pixelu, přičemž v každém kroku počítáme hodnotu y přičítáním směrnice úsečky (ta je samozřejmě tangens sklonu úsečky, neboli poměr dy/dx). Tuto hodnotu zaokrouhlujeme a vykreslujeme pixely. Kód algoritmu může vypadat např. takto:
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; }
Připomeňme, že v reálném kódu bychom souřadnice nejspíš obalili transformační funkcí, což by zde ale působilo nepřehlednost.
Error control DDA
Jde o variantu předchozího algoritmu. Princip je podobný s tím rozdílem, že v každém kroku vypočítáváme chybu, které se dopouštíme zaokrouhlováním. Pokud chyba přesáhne hodnotu 0,5 pixelu, posuneme se o řádek výš a od chyby odečteme 1, aby zůstala relativní k danému řádku.
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í zde to samé, co pro předchozí algoritmus - není příliš efektivní, protože používá výpočty v plovoucí řádové čárce.
Bresenhamův algoritmus
Předchozí algoritmy měly jednu chybu - potřebovaly počítat v plovoucí řádové čárce. Ač nám to nemusí připadat jako nevýhoda, je faktem, že floating point operace jsou mnohem náročnější než celočíselná aritmetika. Pokud má grafická karta vykreslovat stokrát za sekundu složitý 3D drátěný model, jistě to potřebuje dělat efektivně, nemluvě o tom, že jednodušší hardware nemusí floating point operace vůbec podporovat. Tento problém řeší právě Bresenhamův algoritmus, který se dnes používá nejčastěji.
Prvním krokem je zavedení tzv. prediktoru:
p0 = 2 * dy - dx
Dále opět postupujeme v ose x po jednotlivých pixelech a podle prediktoru se rozhodujeme, co dělat dál:
- pokud je prediktor větší nebo roven 0: pi + 1 = pi + 2dy - 2dx, a posun o řádek výš
- v opačném případě: pi + 1 = pi + 2dy
Kód tedy může vypadat 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 pro lepší optimalizaci předpočítat a uložit do zvláštních proměnných, čemuž jsem se zde opět pro účel přehlednosti dovolil vyhnout.
Pokud vás zajímá odvození rovnic pro prediktor, vězte, že jde o jednoduchou úpravu rovnic algoritmu Error control DDA. U něj 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 nerovnic hodnotou 2dx a převedením jednoho členu na levou 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 přejmenujeme na prediktor a jsme hotovi.
Závěrem
Vidíme, že nejlepší volbou je pro nás Bresenhamův algoritmus, protože využívá pouze celočíselnou aritmetiku a obejde se dokonce bez dělení. Pokud ale nenavrhujeme hardwarovou desku, která musí být co nejvíce optimalizovaná, tak se obejdeme i s ostatními metodami. Tak jako tak je vždy dobré znát alespoň tyto základní algoritmy.
V další lekci, Plechovka aneb Flood fill či seed seed, si ukážeme algoritmus Flood fill, který určuje a mění oblast spojenou s daným uzlem ve vícerozměrném poli s některým shodným.
