Klár Gergely

´ as ´ Vag ´ o´ Raszterizac

´ ıtog ´ epes ´ Szam´ Grafika ´ Gergely Klar [email protected] ¨ os ¨ Lorand ´ ´ Eotv Tudomanyegyetem Informatikai Kar

˝ ´ ev ´ 2010/2011. oszi fel

https://eLearning.elte.hu

˝ as ´ 7. eload


´ as ´ Szakaszvag ´ as ´ Poligonvag

Tartalom

1

´ as ´ Vag ´ as ´ Szakaszvag ´ ´ Poligonvagas

2

´ o´ Raszterizac


˝ as ´ 7. eload



´ as ´ Vag

´ beszel ´ unk, ´ anos´ ´ ´ 3D-ra 2D algoritmusokrol altal ıthatok ¨ ´ Mit akarunk vagni? pont szakasz poligon

´ Mire akarunk vagni? poligon ´ ablak, teglalap ´ ık fels´


˝ as ´ 7. eload



´ as ´ az ablakra Vag ´ as: ´ (x, y) ∈ R2 . Akkor tartjuk meg a pontot, ha Pont vag (x, y ) ∈ [xmin , xmax ] × [ymin , ymax ]. ´ negy ´ osszehasonl´ ¨ ´ Megoldas: ıtas. ´ as: ´ a szakasznak csak azokat a pontjai Szakasz vag akarjuk megtartani, amik benne vannak [xmin , xmax ] × [ymin , ymax ]-ban. ´ az ablak negy ´ el ´ evel, ´ ´ fels´ ´ ıkkal vagjuk ´ Megoldas: mint negy a szakaszt. ´ as: ´ a poligonbol ´ egy uj Poligon vag ´ poligont akarunk ´ ´ ki az ablakbol. ´ csinalni, ami nem log ´ ´ (mint szakaszt) Megoldas: A poligon minden oldalat ´ vagjuk.


˝ as ´ 7. eload



´ asa ´ fels´ ´ ıkra Szakasz vag ´ ık: egyenes + egy oldala Fels´ ´ esetet nezz ´ uk, ´ o´ egyenes Csak azt a specialis ¨ amikor a vag ´ parhuzamos valamelyik tengellyel. (x1 , y1 ) − (x2 , y2 ) szakasz egyenlete: x(t) = x1 + t(x2 − x1 ) y(t) = y1 + t(y2 − y1 ) ´ o´ egyenes: pl. x = xmin Vag ´ xmin = x1 + t(x2 − x1 ) ⇒ t = Megoldas: ´ Metszespont: x = xmin , y = y1 +


xmin −x1 x2 −x1

xmin −x1 x2 −x1 (y2

˝ as ´ 7. eload

− y1 )



´ asa ´ - nehezs ´ egek ´ Szakasz vag

´ kezelese: ´ Eredmeny t ≤ 0 vagy t ≥ 1 ⇒ nincs is igazi ´ as. ´ vag ´ ´ ´ asa. ´ Kivetelek: tengelyekkel parhuzamos szakaszok vag ´ fels´ ´ ık, ket ´ vegpont, ´ Rengeteg eset: negy mindketto˝ eshet ´ barhova. ´ ´ ık(ok)ra kell vagni? ´ Feladat: Kell-e vagni? Melyik fels´ ´ Trivialisan bent/kint van-e a szakasz? ´ Cohen–Sutherland vag ´ as ´ Megoldas:


˝ as ´ 7. eload



´ as ´ Cohen–Sutherland vag

´ Az egyenesekkel osszuk kilenc reszre a s´ıkot! ´ Mindegyikhez rendeljunk TBRL ¨ egy bit-kodot: ´ ıtsuk ki ezt a kodot ´ ´ Szam´ a szakasz vegpontjaira! ¨ ott ¨ van T - 1, ha a pont az ablak fol B -1, ha a pont az ablak alatt van ´ jobbra van R -1, ha a pont az ablaktol ´ balra van L -1, ha a pont az ablaktol


˝ as ´ 7. eload




code = Top, Bottom, Right, Left


˝ as ´ 7. eload




code = (y > ymax , y < ymin , x > xmax , x < xmin ) ´ ´ vegpont ´ ´ ´ codeb -t! Vizsgaljuk a ket bit-kodjait, codea -t es Ha codea OR codeb == 0: a szakasz az ablakban van ⇒ megtartjuk. Ha codea AND codeb != 0: a szakasz az ablak valamelyik ´ (fol ¨ ul, oldalan ¨ alul, jobbra, balra), k´ıvul ¨ van ⇒ eldobjuk. ¨ ´ ´ meg, hogy melyik Kul vagni kell: az 1-es bitek adjak ¨ onben ´ ıkra, utana ´ ´ ´ ´ az uj fels´ ujra a bit-kodokat, es ´ szamoljuk ´ szakasszal ujrakezdj uk ´ ¨ az algoritmust.


˝ as ´ 7. eload




codea OR codeb == 0:


˝ as ´ 7. eload




codea AND codeb != 0:


˝ as ´ 7. eload




¨ Kul ¨ onben:


˝ as ´ 7. eload



´ as ´ Poligonvag

Feladat ´ ´ egy vag ´ o´ poligon. Keressuk Adott egy vagand o´ es ¨ azt a ´ ´ ol ´ kapunk, ha csak a vag ´ o´ poligonba poligont, amit a vagand ob ´ ¨ ¨ os ¨ tartozo´ reszeit vesszuk. keressuk ¨ Roviden: ¨ a ketto˝ koz ´ et. ´ resz Algoritmusok: ´ o´ poligon, convex Sutherland–Hodgman: convex vag ´ ´ al ´ hibak; ´ gyorsabb vagand on ¨ Weiler–Atherton: nem onmetsz o˝ poligonokra; lassabb, nem vesszuk ¨


˝ as ´ 7. eload



´ as ´ Sutherland-Hodgeman poligonvag ¨ Legyen p tomb a bemeneti-, q a kimeneti-poligon ¨ csucsainak tombje! ´ ´ ´ p[0] = p[n]! Legyen n a csucsok szama, es ´ ´ as ´ egyenesre: Vag ´ p[i + 1] is: Ha p[i] bent van az alablakban, es ⇒ adjuk hozza´ p[i]-t a q-hoz. Ha p[i] bent van az alablakban, de p[i + 1] nincs: ´ ıtsuk ki p[i], p[i + 1] ⇒ adjuk hozza´ p[i]-t a q-hoz, szam´ ´ ´ a vag ´ o´ egyenessel, majd ezt is szakasz metszespontj at adjuk hozza´ q-hoz. Ha p[i] nincs bent az alablakban, de p[i + 1] benne van: ´ ıtsuk ki p[i], p[i + 1] szakasz metszespontj ´ ´ a vag ´ o´ ⇒ szam´ at ´ ezt adjuk hozza´ q-hoz. egyenessel, es ´ p[i + 1] sincs: Ha p[i] nincs bent az alablakban, es ⇒ SKIP https://eLearning.elte.hu

˝ as ´ 7. eload



´ as ´ - Pszedudo´ kod ´ Sutherland-Hodgeman poligonvag PolygonClip(in p[n], out q[m], in line) { m = 0; for( i=0; i < n; i++) { if (IsInside(p[i])) { q[m++] = p[i]; if (!IsInside(p[i+1])) q[m++] = Intersect(p[i], p[i+1], line); } else { if (IsInside(p[i+1])) q[m++] = Intersect(p[i], p[i+1], line); } } } https://eLearning.elte.hu

˝ as ´ 7. eload



´ poligonok Sutherland-Hodgeman: konkav

´ poligonokra atfed ´ ´ ´ Konkav o˝ eleket hoz letre.


˝ as ´ 7. eload






˝ as ´ 7. eload






˝ as ´ 7. eload






˝ as ´ 7. eload






˝ as ´ 7. eload






˝ as ´ 7. eload






˝ as ´ 7. eload






˝ as ´ 7. eload


´ o´ Szakasz raszterizaci ´ o´ Poligon raszterizaci

Tartalom

1

´ as ´ Vag

2

´ o´ Raszterizac ´ o´ Szakasz raszterizaci ´ o´ Poligon raszterizaci


˝ as ´ 7. eload



´ Szakasz rajzolas Egyik leggyakrabb primit´ıv. ´ Fontos, hogy szepen tudjuk rajzolni. ´ Megjobb, ha gyorsan is.

Jason Thielke, jasonthielke.com


˝ as ´ 7. eload



Hogyan rajzolunk szakaszt? ´ vegpont. ´ Adott a ket ¨ ¨ oket? ˝ Hogyan tudjuk osszek otni ´ Csak miniatur vannak (amiket pixelnek ˝ teglalapjaink nevezunk). ¨


˝ as ´ 7. eload





˝ as ´ 7. eload





˝ as ´ 7. eload





˝ as ´ 7. eload





˝ as ´ 7. eload



´ (sokadszor) Szakasz megadasa

´ Vegpontok: (x1 , y1 ), (x2 , y2 ) ˝ Tfh. nem fugg x1 6= x2 . ¨ oleges: Szakasz egyenlete: y = mx + b, x ∈ [x1 , x2 ] y2 − y1 m= x2 − x1 b = y1 − mx1


˝ as ´ 7. eload



Na´ıv algoritmus

d e f l i n e 1 ( x1 , y1 , x2 , y2 , draw ) : m = f l o a t ( y2−y1 ) / ( x2−x1 ) x = x1 y = f l o a t ( y1 ) w h i l e x<=x2 : draw . p o i n t ( ( x , y ) ) x += 1 y += m


˝ as ´ 7. eload



Na´ıv algoritmus

m = float(y2-y1)/(x2-x1) nem pontos y += m → a hiba gyulik ˝ y -ban draw.point((x,y)) → ´ lassu´ a konverzio´ int-eket var, ¨ csak |m| < 1-re muk ˝ odik helyesen


˝ as ´ 7. eload



Na´ıv algoritmus



˝ as ´ 7. eload



Na´ıv algoritmus



˝ as ´ 7. eload



Na´ıv algoritmus



˝ as ´ 7. eload



Na´ıv algoritmus



˝ as ´ 7. eload



Jav´ıtsuk az algoritmust 1. d e f l i n e 2 ( x1 , y1 , x2 , y2 , draw ) : m = f l o a t ( y2−y1 ) / ( x2−x1 ) x = x1 y = y1 e = 0.0 w h i l e x<=x2 : draw . p o i n t ( ( x , y ) ) x += 1 e += m i f e >= 0 . 5 : y += 1 e −= 1 . 0


˝ as ´ 7. eload



Jav´ıtsuk az algoritmust 1. Na´ıv:

´ Mindig ”eltalalja” ´ Jo: a ´ vegpontokat ´ Egyenletesebben lep ´ az y Jo: ´ iranyban.

´ Jav´ıtas:

´ mindig hasznalunk ´ Rossz: Meg float-okat


˝ as ´ 7. eload



Jav´ıtsuk az algoritmust 2. d e f l i n e 3 ( x1 , y1 , x2 , y2 , draw ) : x = x1 y = y1 e = −0.5←− w h i l e x<=x2 : draw . p o i n t ( ( x , y ) ) x += 1 e += f l o a t ( y2−y1 ) / ( x2−x1 ) ←− i f e >= 0 . 0 : ←− y += 1 e −= 1 . 0


˝ as ´ 7. eload



Jav´ıtsuk az algoritmust 3. d e f l i n e 4 ( x1 , y1 , x2 , y2 , draw ) : x = x1 y = y1 e = −0.5∗( x2−x1 ) ←− w h i l e x<=x2 : draw . p o i n t ( ( x , y ) ) x += 1 e += y2−y1←− i f e >= 0 . 0 : y += 1 e −= ( x2−x1 ) ←−


˝ as ´ 7. eload



Jav´ıtsuk az algoritmust 4. d e f l i n e 5 ( x1 , y1 , x2 , y2 , draw ) : x = x1 y = y1 e = −(x2−x1 ) ←− w h i l e x<=x2 : draw . p o i n t ( ( x , y ) ) x += 1 e += 2 ∗ ( y2−y1 ) ←− i f e >= 0 : y += 1 e −= 2 ∗ ( x2−x1 ) ←−


˝ as ´ 7. eload



Jav´ıtsuk az algoritmust 4.

´ esete) Ez a Bresenham algoritmus (egyik specialis ¨ gyujtj ´ e-ben Kul ¨ on ˝ uk ¨ a hibat ´ Nem hasznalunk float-okat ˝ ´ u˝ szakaszokra altal ´ anos´ ´ ´ Tetszoleges meredekseg ıthato.


˝ as ´ 7. eload



Bresenham algoritmus

´ ¨ eset. Nyolcadokra kene felbontani a s´ıkot, mindegyik kul ¨ on ˝ ok ˝ vegig: ´ (Eloz jobbra-le) ¨ El kell donten unk, hogy |x2 − x1 | vagy |y2 − y1 | a nagyobb ¨ (merre meredekebb a szakasz). ´ uk ´ rajzolasn ´ al ´ Ha |y2 − y1 | a nagyobb, cserelj ¨ fel xi ↔ yi , es ´ is ford´ıtva hasznaljuk! Ha x1 > x2 , akkor csere: x1 ↔ x2 , y1 ↔ y2 . ¨ ´ esben ´ Az e hibatagot |y2 − y1 |-nal novelj uk ¨ minden lep ˝ y-nal y2 − y1 elojele szerint haladunk.


˝ as ´ 7. eload



Bresenham algoritmus


˝ as ´ 7. eload



Teljes Bresenham algoritmust 1. d e f Bresenham ( x1 , y1 , x2 , y2 , draw ) : steep = abs ( y2−y1)>abs ( x2−x1 ) i f steep : x1 , y1 = y1 , x1 x2 , y2 = y2 , x2 i f x1>x2 : x1 , x2 = x2 , x1 y1 , y2 = y2 , y1 Dy = abs ( y2−y1 ) i f y1

˝ as ´ 7. eload



Teljes Bresenham algoritmust 2. x = x1 y = y1 e = −(x2−x1 ) w h i l e x<=x2 : i f steep : draw . p o i n t ( ( y , x ) ) else : draw . p o i n t ( ( x , y ) ) x += 1 e += 2∗Dy i f e >= 0 : y += Sy e −= 2 ∗ ( x2−x1 )


˝ as ´ 7. eload



´ ´ ¨ es ´ Flood-fill – elaraszt asos kitolt

˝ ´ raszterizalt ´ poligon kitolt ¨ es ´ ere ´ alkalmas. Tetszoleges, mar ´ + annak egy pontja Bemenet: raszter kep ´ kiindulva rekurz´ıvan haladunk: A megadott pontbol ´ pont sz´ıne megegyezik a kiindulasi ´ pont Az aktualis ´ sz´ınevel? ´ nem megallunk ´ ınezzuk, ´ igen atsz´ ¨ es

´ minden szomszedra ujrakezdj uk ´ ¨ az algoritmust.


˝ as ´ 7. eload



´ asgok ´ Flood-fill – szomszed

´ szomszed: ´ fent, lent, jobbra, balra Negy ´ az eloz ˝ o˝ negy ´ + a sarkak Nyolc szomszed:


˝ as ´ 7. eload



´ ¨ kitolt ¨ es ´ Haromsz og

¨ ıtett ert ´ ekkel ´ ¨ Nem egy rogz´ akarunk kitolteni, a hanem a ´ ekeket ´ ´ csucsokban adott ert akarjuk interpolalni. ´ ´ asai: ´ ´ ´ Felhasznal sz´ın (Gouraud-arnyal as), textura ´ ´ normalvektorok ´ koordintak, Legyen a felulet ¨ egy pontja p = αp1 + βp2 + γp3 , az α, β, γ ´ akkal ´ baricentrikus koordinat adott. ´ ´ ert ´ eket ´ ´ ´ Ekkor barmilyen mas is vegig tudunk interpolalni ugyan ´ıgy: c = αc1 + βc2 + γc3 ´ o´ (nem veletlen ´ Ez az ugy ul) ´ nevezett Gouraud interpolaci ¨


˝ as ´ 7. eload



´ ¨ kitolt ¨ es ´ 1. Haromsz og

for all x : for all y : α, β, γ = b a r y c e n t r i c ( x , y ) i f α ∈ [0, 1] and β ∈ [0, 1] and γ ∈ [0, 1] : c = αc 1 + β c 2 + γ c 3 draw . p o i n t ( ( x , y ) , c )


˝ as ´ 7. eload



´ ak ´ Baricentrikus koordinat ´ ak ´ szam´ ´ ıthatok ´ a kovetkez ¨ A baricentrikus koordinat o˝ ´ kepletekkel: f01 (x, y ) = (y0 − y1 )x + (x1 − x0 )y + x0 y1 − x1 y0 f12 (x, y ) = (y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 f20 (x, y ) = (y2 − y0 )x + (x0 − x2 )y + x2 y0 − x0 y2 ´ ak: ´ Ekkor az x, y ponthoz tartozo´ baricentrikus koordinat α = f12 (x, y )/f12 (x0 , y0 ) β = f20 (x, y )/f20 (x1 , y1 ) γ = f01 (x, y )/f01 (x2 , y2 )


˝ as ´ 7. eload



´ ¨ kitolt ¨ es ´ 2. Haromsz og x min = min ( f l o o r ( x i ) ) x max = max ( c e i l i n g ( x i ) ) y min = min ( f l o o r ( y i ) ) y max = max ( c e i l i n g ( y i ) ) f o r y i n [ y min . . y max ] : f o r x i n [ x min . . x max ] : α = f12 (x, y)/f12 (x0 , y0 ) β = f20 (x, y )/f20 (x1 , y1 ) γ = f01 (x, y)/f01 (x2 , y2 ) i f α>0 and β>0 and γ >0: c = αc 1 + β c 2 + γ c 3 draw . p o i n t ( ( x , y ) , c )


˝ as ´ 7. eload




´ felesleges minden x, y -t vizsgalni, ´ ´ a Gyors´ıtas: eleg ´ ¨ ´ ´ haromsz oget tartalazo´ teglalapon vegig menni. ´ ´ etel: ´ Inkrementaliss at ´ lassu, ´ Most meg ki hogy sorban megyunk ´ nem hasznaljuk, ¨ x-en, y-on. Milyenek is ezek az f -ek? Mind f (x, y ) = Ax + By + C alaku. ´ Ekkor f (x + 1, y ) = f (x, y) + A, ill. f (x, y + 1) = f (x, y ) + B

´ ıtas: ´ Megvalos´


˝ as ´ 7. eload







˝ as ´ 7. eload







˝ as ´ 7. eload







˝ as ´ 7. eload







˝ as ´ 7. eload





´ ıtas: ´ hazi ´ feladat Megvalos´


˝ as ´ 7. eload

Klár Gergely

Recommend Documents