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 $\mathrm{\Delta }x=x_2-x_1,\mathrm{\Delta }y=y_2-y_1,k=\frac{\mathrm{\Delta }y}{\mathrm{\Delta }x}$, potom
a) když $k\in <-1,1>$ (osa s větším přírůstkem je X) zvolíme tedy $dx=1$, dostáváme $dy=k\cdot dx=k$.
Souřadnice dalšího bodu $[x_{i+1},y_{i+1}]$ vypočítáme:
$x_{i+1}=x_i+dx=x_i+1$
$y_{i+1}=y_i+dy=y_i+k$
b) když $k<-1$ nebo $k>1$ (osa s větším přírustkem je Y) zvolíme tedy $dy=1$, dostáváme $dx=dy/k=1/k$.
A souřadnice dalšího bodu $[x_{i+1},y_{i+1}]$ vypočítáme:
$x_{i+1}=x_i+dx=x_i+1/k$
$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 $\mathrm{\Delta }x=x_2-x_1,\mathrm{\Delta }y=y_2-y_1,k=\frac{\mathrm{\Delta }y}{\mathrm{\Delta }x}$
Chybový člen $e_1=2\mathrm{\Delta }y-\mathrm{\Delta }x$
Rekurzivní výpočet $i+1$. kroku (poslední vykreslený bod $[x_i,y_i]$), pro pozici dalšího bodu jsou dvě možnosti:
1) $e_i<0$ - jako další bod zobrazíme bod $[x_i+1,y_i]$ a chybový člen $e_{i+1}=e_i+2\mathrm{\Delta }y$
2) $e_i>=0$ - jako další bod zobrazíme bod $[x_i+1,y_i+1]$ a chybový člen $e_{i+1}=e_i+2(\mathrm{\Delta }y-\mathrm{\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, $[x_1,y_1]$, další bod otočený o úhel $\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 $\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 $p_1=3-2r$
Rekurzivní výpočet $i+1$. kroku (poslední vykreslený bod $[x_i,y_i]$), pro pozici dalšího bodu jsou dvě možnosti:
1) $p_i<0$ - jako další bod zobrazíme bod $[x_i+1,y_i]$ a chybový člen $p_{i+1}=p_i+4x_i+6$
2) $p_i>=0$ - jako další bod zobrazíme bod $[x_i+1,y_i-1]$ a chybový člen $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.