© 2013 All rights reserved.
0

Rasterizace objetů #1: Digital Differential Analyzer

Rasteriace je proces, při kterém převádíme základní grafické objekty do systému posloupnosti obrazových bodů. Toto je důležité při práci s různými výstupními zařízeními, které nejsou schopny zobrazit přesně daný objekt, ale při svém zobrazení používají rastr.

Při rasterizaci se snažíme co nejvěrněji převést obraz do podoby rastru, a to tak, aby vznikala co nejmenší chyba (pixelizace).

Pixelizaci je možné ovlivnit použitou metodou, v případě že jí nejde zabránit, se používá například antialiasing pro její částečné odstranění.

V tomto, prvním článku, se zaměříme na rasterizaci úsečky, konkrétně na DDA Algoritmus (Digital Differential Analyzer)

Úsečka je základním grafickým prvkem, se kterým se setkáváme všude a při téměř všech operacích. Ovšem ani úsečka není v rastru dána jednoznačně a při jejím vykreslování se musíme neustále rozhodovat, kterými body (pixely) bude úsečka procházet a které z těchto, nebo okolních, bodů se vykreslí.

Všechny algoritmy, kterých existuje celá řada, vycházejí ze základní rovnice přímky:

Úsečka je většinou zadána dvěma body, koncovými body:

nebo souřadnicí jednoho bodu a vektorem:

Dále může být zadání úsečky doplněno o různé atributy, upřesňující její zobrazení, jako barva, tloušťka a podobně.

Pro většinu algiritmů je důležitý výpočet směrnice takové úsečky:

a posunutí úsčky:

DDA algoritmus (Digital Differential Analyzer)

DDA algoritmus je jednoduchý přírustkový algoritmus, který je založen na postupném přičítání přírustku k hodnotám obou os, vycházejících z jednoho bodu a jdoucí k druhému bodu, kterými je úsečka zadána.


dda

Algoritmus jde rozdělit na několik situací, které mohou nastat. První v nich je, kdy je úsečka rovnoběžná s některou z obou os x nebo y. V takovémto případě není potřeba jednotlivé body dopočítávat, protože je samozřejmě jasné, kterými body bude úsečka procházet a které body se v tomto případě vykreslí.

Pokud je úsečka rovnoběžná s osou x, budou všechny hodnoty na ose x stejné a hodnoty na ose y se budou postupně zvyšovat o přírustek 1, v opačném případě, kdy bude úsečka rovnoběžná
s osou y, budou všechny hodnoty na ose y stejné a hodnoty na ose x se budou postupně zvyšovat o přírustek 1.

V takovém případě se budou vykreslovat jednotlivé pixely sousedící a nebude se měnit některá z jejich souřadnic.

Další dvě možnosti, kdy úsečka není rovnoběžná ani s jednou z obou os, rozdělujeme podle směrnice m.
Pokud je hodnota směrnice m < 1, budeme počítat přírustek na ose y podle vzorce:

a hodnoty na ose se budou postupně zvyšovat o 1.

Druhý případ nastane, pokud je směrnice m > 1. V tomto případě budeme dopočítávat přírustek na ose x a hodnoty na ose y se budou postupně zvyšovat o 1:

Samozřejmě, že podle obou vzorců nebudou vycházet celá čísla, ale ve většině případů bude hodnota desetinné číslo. Hodnoty se zaokrouhlují na celá čísla podle pravidel matematiky, abychom dostali souřadnice pixelů pro vykreslení.

V hodnotě směrnice může nastat ještě jeden případ, kdy bude m = 1. V takovémto případě je možno počítat hodnoty přírustku oběma případy, protože přírustek bude roven hodnotě 1 na obou osách.

Celý princip výpočtu souřadnic je jednoduše pochopitelný na následující funkci, která je napsána tak, jak algoritmus funguje.

Funkce obsahuje 4 vstupní parametry – souřadnice dvou bodů, určující úsečku. Dle těchto bodů funkce vypisuje souřadnice nutné pro rasterizaci.

Pro volání funkce například:

Vrací funkce hodnoty:

Tyto hodnoty representují x-ové a y-ové souřadnice, ve kterých se vykreslí úsečka.

Závěrem

DDA algoritmus je jeden z nejjednodušších algoritmů pro rasterizaci úsečky. V příštím článku se zaměříme na Bresenhamův algoritmus

Comments are closed for this page

About
Hi, i am programmer from the Czech Republic. I love web development (Ruby, Ruby on Rails, PHP, Nette) and iOS development (Objective-C, Cocoa).
To cooperate, here is my phone:
+420 608 836