Rasterizace

Z Wikiknih

Obsah

1 Rasterizace
- 1.1 Popis algoritmů
- 1.2 Kód v jazyce C#
2 Autoři

[editovat] 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.

[editovat] Popis algoritmů

[editovat] 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$

[editovat] 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)$

yxcyxcyxc

[editovat] 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.

[editovat] 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$

[editovat] Kód v jazyce C#

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

[editovat] 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.

Rasterizace

Z Wikiknih

Obsah

[editovat] Rasterizace

[editovat] Popis algoritmů

[editovat] DDA algoritmus

[editovat] Bresenhamův algoritmus pro úsečku

[editovat] Kresba kružnice pomocí otáčení bodu

[editovat] Bresenhamův algoritmus pro kružnici

[editovat] Kód v jazyce C#

[editovat] Autoři

Zobrazení

Osobní nástroje

Hledat

Navigace

Tisk/export

Nástroje