Geometrie/Rasterizace

Rasterizace

Při zobrazení reálného modelu ve světových souřadnicích na výstupní zařízení (rastrové, vektorové) potřebujeme zajistit co nejvěrnější podobnost reálného a zobrazovaného modelu. Omezíme se v tomto textu na rastrové výstupní zařízení, jehož nejjednodušším grafickým prvkem je bod. Protože složitější objekty jsou jen skládankou jednodušších objektů, potřebujeme mít k dispozici algoritmy na výpočet polohy bodů jednoduchých objektů jako úsečky, kružnice, elipsy, oblouků, atd... Ukážeme si některé algoritmy pro výpočet bodů úsečky a kružnice.

Popis algoritmů

DDA algoritmus

Jedna se o přírustkový algoritmus. Jednoduchý algoritmus pro výpočet bodů úsečky. Ve směru jedné osy s větším přírůstkem inkrementuje o krok 1 a ve směru druhé osy o krok menší než 1 podle poměru délky úsečky ve směru x a ve směru y. Algoritmus je jednoduchý, ale relativně pomalý protože pracuje v oboru reálných čísel.

Označme $\Delta x=x_{2}-x_{1},\Delta y=y_{2}-y_{1},k={\frac {\Delta y}{\Delta x}}$, potom
a) když $k\in <-1,1>$ (osa s větším přírůstkem je X) zvolíme tedy ${\mathcal {}}dx=1$, dostáváme ${\mathcal {}}dy=k\cdot dx=k$.
Souřadnice dalšího bodu ${\mathcal {}}[x_{i+1},y_{i+1}]$ vypočítáme:
${\mathcal {}}x_{i+1}=x_{i}+dx=x_{i}+1$
${\mathcal {}}y_{i+1}=y_{i}+dy=y_{i}+k$
b) když ${\mathcal {}}k<-1$ nebo ${\mathcal {}}k>1$ (osa s větším přírustkem je Y) zvolíme tedy ${\mathcal {}}dy=1$, dostáváme ${\mathcal {}}dx=dy/k=1/k$.
A souřadnice dalšího bodu ${\mathcal {}}[x_{i+1},y_{i+1}]$ vypočítáme:
${\mathcal {}}x_{i+1}=x_{i}+dx=x_{i}+1/k$
${\mathcal {}}y_{i+1}=y_{i}+dy=y_{i}+1$

Bresenhamův algoritmus pro úsečku

Mnohem rychlejší algoritmus pro generování bodů úsečky poskytuje tento algoritmus, používající pouze celočíselnou aritmetiku. Ve směru osy s větším přírustkem (nezávislé) inkremtentuje opět s krokem 1, ale ve směru druhé osy (závislé) vypočte chybový člen a podle něj určí bližší pixel k úsečce.

Předpokládejme že nezávislá souřadnice je souřadnice X, tedy $k\in <0,1>$ (v opačném případě by se postupovalo analogicky).

Označme $\Delta x=x_{2}-x_{1},\Delta y=y_{2}-y_{1},k={\frac {\Delta y}{\Delta x}}$
Chybový člen ${\mathcal {}}e_{1}=2\Delta y-\Delta x$
Rekurzivní výpočet ${\mathcal {}}i+1$. kroku (poslední vykreslený bod ${\mathcal {}}[x_{i},y_{i}]$), pro pozici dalšího bodu jsou dvě možnosti:
1) ${\mathcal {}}e_{i}<0$ - jako další bod zobrazíme bod ${\mathcal {}}[x_{i}+1,y_{i}]$ a chybový člen ${\mathcal {}}e_{i+1}=e_{i}+2\Delta y$
2) ${\mathcal {}}e_{i}>=0$ - jako další bod zobrazíme bod ${\mathcal {}}[x_{i}+1,y_{i}+1]$ a chybový člen ${\mathcal {}}e_{i+1}=e_{i}+2(\Delta y-\Delta x)$

Kresba kružnice pomocí otáčení bodu

Jednoduchá metoda pro výpočet bodů kružnice spočívá v tom, že vezmeme jeden bod ležící na kružnici (dána středem a poloměrem) a otáčíme jej o zadaný úhel proti směru hodinových ručiček. Body postupně spojujeme úsečkami (např. DDA). Je vidět, že kružnice je v tomto případě pouze aproximována nějakým pravidelným mnohoúhelníkem. Čím menší úhel, o který otáčíme, tím "věrnější" kružnici dostaneme.

Body na kružnici splňují v polárních souřadnicích rovnice
$x=r\cdot \cos(\alpha )$ a $y=r\cdot \sin(\alpha )$
Zvolíme libovolný bod na kružnici, ${\mathcal {}}[x_{1},y_{1}]$, další bod otočený o úhel ${\mathcal {}}\alpha$ vypočteme rekurzivně:
$x_{i+1}=x_{i}\cdot \cos(\alpha )-y_{i}\cdot \sin(\alpha )$,
$y_{i+1}=x_{i}\cdot \sin(\alpha )+y_{i}\cdot \cos(\alpha )$
Stačí zvolit krok ${\mathcal {}}\alpha$ a postupně spojovat vypočítané body nějakým úsečkovým algoritmem.

Bresenhamův algoritmus pro kružnici

Opět rychlejší algoritmus pracující podobně jako pro úsečku a jen v celočíselné aritmetice. Počítáme body pouze jednoho oktantu (zbylých 7 oktantů stačí vykreslit pomocí symetrie).

Algoritmus vypočte body na kružnici se středem v počátku a zadaným poloměrem pouze ve druhém oktantu. Body ostatních oktantů vykreslí symetricky a všechny posune o souřadnice středu kružnice.

Označme $r$ - poloměr kružnice.
Chybový člen ${\mathcal {}}p_{1}=3-2r$
Rekurzivní výpočet ${\mathcal {}}i+1$. kroku (poslední vykreslený bod ${\mathcal {}}[x_{i},y_{i}]$), pro pozici dalšího bodu jsou dvě možnosti:
1) ${\mathcal {}}p_{i}<0$ - jako další bod zobrazíme bod ${\mathcal {}}[x_{i}+1,y_{i}]$ a chybový člen ${\mathcal {}}p_{i+1}=p_{i}+4x_{i}+6$
2) ${\mathcal {}}p_{i}>=0$ - jako další bod zobrazíme bod ${\mathcal {}}[x_{i}+1,y_{i}-1]$ a chybový člen ${\mathcal {}}p_{i+1}=p_{i}+4(x_{i}-y_{i})+10$

Kód v jazyce C#

Příklad řešení v jazyce C#.

Autoři

Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako součást zápočtového úkolu do předmětu Počítačová geometrie.