11 - Metody rasterizace 2D vektorových objektů

Definice
Rasterizace je proces převodu vektorové reprezentace dat na jejich rastrovou formu s cílem dosáhnout maximální možnou kvalitu a zároveň rychlost výsledného zobrazení.

Úsečka

Popis
Úsečka Úsečka je základní geometrická vektorová entita definovaná: souřadnicemi dvou koncových bodů rovnicí přímky popisující geometrii Obecná rovnice úsečky Parametrické vyjádření Směrnicový tvar Algoritmy pro vykreslení úsečky Jsou odvozeny pro případ, kdy: úsečka leží v prvním kvadrantu je rostoucí od P1 ke koncovému P2 ostatní kvadranty vykreslujeme prohozením souřadnic, výměnou os

DDA - Digital Differential Analyser

Popis
Používá ”floating-point aritmetiku”, pak se zaokrouhluje Nízká efektivita, náročná implementace do HW … směrnice LineDDA(int x1, int y1, int x2, int y2) { int k = (y2-y1)/(x2-x1); int y = y1; for (int x = x1; x <= x2; x++) { draw_pixel( x, y); y += k; } }

Error control DDA

Popis
modifikace DDA LineEC(int x1, int y1, int x2, int y2) { double k = (y2-y1) / (x2-x1); double E = 0; int y = y1; for (int x = x1; x <= x2; x++) { draw_pixel( x, y); E += k; if (E >= 0.5) { y++; E -= 1; } } }

Bresenhamův algoritmus

Popis
nejpoužívanější, velmi efektivní, snadná implementace do HW používá celočíselnou aritmetiku, sčítání, porovnání posun v ose Y podle znaménka prediktoru Pokud , potom Pokud potom Takze po vynásobení rovnic : LineBres(int x1, int y1, int x2, int y2) { int dx = x2-x1, dy = y2-y1; int P = 2*dy – dx; int P1 = 2*dy, P2 = P1 - 2*dx; int y = y1; for (int x = x1; x <= x2; x++) { draw_pixel( x, y); if (P >= 0) { P += P2; y++; } else P += P1; } }

Kružnice

Popis
Kružnice je základní geometrická vektorová entita definovaná: Kružnice souřadnicemi středu hodnotou poloměru R rovnicí kružnice popisující geometrii: Kružnice je 8*symetrická⇒výpočet pro polovinu bodů jednoho kvadrantu, zbytek prohozením souřadnic a/nebo znamének souřadnice. Algoritmy jsou odvozeny pro kružnice se středem v počátku [0,0].

Vykreslení po bodech

Popis
Používá ”floating-point aritmetiku” nízká efektivita, náročná implementace v HW od bodu [0,R] po pixelech dokud není x=y

Vykreslení kružnice jako N-úhelník

Popis
varianta DDA pro kružnici-floating point, nízka efektivita, vysoká náročnost implementace v HW rekurentní posun o konstaní přírůstek úhlu(sin a cos se počítají pouze jednou)

Midpoint algoritmus

Popis
variace na Bresenhamův ⇒celočíselná aritmetika, vysoká efektivita, snadná implementace po pixelu od [0,R] dokud startovací hodnota je CircleMid(int s1, int s2, int R) { int x = 0, y = R; int P = 1-R, X2 = 3, Y2 = 2*R-2; while (x < y) { draw_pixel_circle(x, y); if (P >= 0) { P += -Y2; Y2 -= 2; y--; } P += X2; X2 += 2; x++; } }

Elipsa

Popis
Elipsa je základní geometrická vektorová entita definovaná: souřadnicemi středu hodnotami hlavní a vedlejší poloosy úhlem natočení hlavní poloosy rovnicí elipsy popisující geometrii: Je 4x symetrická.

Midpoint algoritmus

Popis
ekvivalent midpointu pro kružnici efektivní, snadná implementace v HW, celočíselná aritmetika oblast I od[0,b] do 2b2x=2a2y. Oblast II do [a,0] založen na určování polohy midpointu vůči elipse V ose X/Y postupujeme o 1, v Y/X o posunu rozhoduje znaménko prediktoru.

Křivky

Popis
Rovnost přímek a kulatost kružnic je ideál, ve skutečnosti potřebujeme popsat křivé tvary. Parametrické vyjádření není pro grafiku vhodné, používá se maticový zápis. Další použití:definice modelů, šablonování, definice fontů, určování dráhy objektů v animaci.Požadované vlastnosti: Invariance k lineárním transformacím(rotace řídících bodů nesmí ovlivnit průběh křivky) Konvexní obálka - křivka leží v konvexní obálce svých řídících bodů Interpolace krajních bodů Lokalita změn - pokud posuneme řídící bod, mělo by se změnit jen jeho okolí ne celá křivka INTERPOLAČNÍ KŘIVKA(prochází body) vs. APROXIMAČNÍ KŘIVKA(neprochází řídícími body) Racionální křivka - řídící body mají váhové koeficienty (Neracionální - váhové koef.o velikosti 1) Spojitost: C0 - totožnost navazujících koncových bodů C1 - totožnost tečných vektorů v navazujících bodech C2 - totožnost vektorů 2.derivace v navazujicích bodech Spline křivky - po částech polynomiální křivka, používá se s cílem minimalizace křivosti křivky(délku, energii) Přirozený spline - interpoluje své řídící body

Interpolační

Fergusonova kubika

Popis
Nejčastější interpolační křivka Určena dvěma koncovými body a dvěma tečnými vektory Pro navázání segmentů je třeba definovat stejný bod i tečný vektor v obou segmentech (segment=křivka mezi dvěma body) Pro definici se používá maticový zápis Hermitových polynomů

Kochanek Bartels spline

Popis
interpolační spline křivka využívající Fergusonových kubik určena množinou interpolačních bodů a jejich koeficientů, které určují chování v daném bodě použití v animaci pro definici dráhy pohybu objektů

Catmull-Rom spline

Popis
interpolační spline křivka určená množinou bodů Kochanek-Bartels spline s nulovými koeficienty vychází z druhého bodu a končí v předposledním⇒k interpolaci okrajových bodů se použije zdvojení neleží v konvexní obálce tečný vektor je rovnoběžný s přímkou procházející sousedními body

Aproximační

Beziérovy křivky

Popis
Aproximační polynomiální křivka stupně n je určena n+1 body používá Bernsteinovy polynomy definované rekurentě prochází koncové body, leží v konvexní obálce možno pro vykreslení použít algoritmus de Casteljau⇒dělení úseků řídícího polynomu na části t a 1 - t, spojování rekurzivně spočtených bodů úsečkami⇒body úsečky jsou rovnoměrně rozprostřené body pro rovné i křivé části.

Beziérovy kubiky

Popis
jeden segment popsán 4 řídícími body při napojovánní segmentů je nutno mít totožné koncové body i tečné vektory v těchto bodech invariantní k lineárním transformacím vykreslování pomocí de Casteljau s koeficientem t=0.5

Racionální beziérové křivky

Popis
místo neracionálních Bersteinových polynomů se používají racionální polynomy křivka leží v konvexní obálce nelze použít algoritmus de Casteljau

Coonsova kubika

Popis
aproximační křivka, která neprochází koncovými řídícími body polynomiální křivka n-tého stupně určena n+1 řídícími body s křivkou se dá pracovat jen po segmentech, nelze přidávat jen samostatné body

B-spline křivky

Popis
zobecnění Coonsových kubik křivka určena n+1 body a má spojitost k+1, kde k je stupněm křivky mají nezápornou hodnotu a jednotkový součet⇒leží v konvexním obálce vykreslování algoritmem de Boor(obdoba de Casteljau) uzlový vektor představuje hodnoty parametru t v uzlech, čímž umožňuje lokální změnu křivky uniformní je když je přírůstek t konstantní(např uzlový vektor 0,0.2,0.4,0.6,0.8,1)

NURBS Non Uniform Rational B-Spline

Popis
zobecnění B-spline křivek přírůstek hodnoty parametru uzlového vektrou nemusí být konstantní(neuniformita) každý bod má váhový koeficient(racionální) invariantí vůči lineárním transformacím umožnuje přesně vyjádřit kuželosečky

Pro zájemce

odkazy
http://en.wikipedia.org/wiki/Bézier_curve http://en.wikipedia.org/wiki/B-spline http://en.wikipedia.org/wiki/Bézier_surface http://en.wikipedia.org/wiki/Conic_section http://en.wikipedia.org/wiki/Cubic_Hermite_spline http://en.wikipedia.org/wiki/Steven_Anson_Coons http://en.wikipedia.org/wiki/Kochanek–Bartels_spline