Geometrie/Rasterizace

Z Wikiknih
Skočit na navigaci Skočit na vyhledávání

Rasterizace[editovat]

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

DDA algoritmus[editovat]

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 , potom
a) když (osa s větším přírůstkem je X) zvolíme tedy , dostáváme .
Souřadnice dalšího bodu vypočítáme:


b) když nebo (osa s větším přírustkem je Y) zvolíme tedy , dostáváme .
A souřadnice dalšího bodu vypočítáme:


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

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 (v opačném případě by se postupovalo analogicky).

Označme
Chybový člen
Rekurzivní výpočet . kroku (poslední vykreslený bod ), pro pozici dalšího bodu jsou dvě možnosti:
1) - jako další bod zobrazíme bod a chybový člen
2) - jako další bod zobrazíme bod a chybový člen

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

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
a
Zvolíme libovolný bod na kružnici, , další bod otočený o úhel vypočteme rekurzivně:
,

Stačí zvolit krok a postupně spojovat vypočítané body nějakým úsečkovým algoritmem.

Bresenhamův algoritmus pro kružnici[editovat]

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 - poloměr kružnice.
Chybový člen
Rekurzivní výpočet . kroku (poslední vykreslený bod ), pro pozici dalšího bodu jsou dvě možnosti:
1) - jako další bod zobrazíme bod a chybový člen
2) - jako další bod zobrazíme bod a chybový člen

Kód v jazyce C#[editovat]

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

Autoři[editovat]

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.