Informatika | Grafika » Várady Lajos - Számítógépes grafika gyakorlat

SZÁMÍTÓGÉPI GRAFIKA GYAKORLAT Összeállította: Várady Lajos varadyl@math.kltehu 1 TARTALOM 1. HASZNÁLT ADATSZERKEZETEK 4 2. RASZTERES ALGORITMUSOK 5 2.1 SZAKASZ RAJZOLÁSA 5 2.11 Egyszerû növekményes algoritmus 5 2.12 Középpontos vonalalgoritmus 6 2.2 SZAKASZ LEHATÁROLÁSA 10 2.21 Cohen-Sutherland algoritmus 10 2.3 POLIGONLEHATÁROLÁS (SUTHERLAND-HODGMAN) 12 2.4 KÖZÉPPONTOS KÖRRAJZOLÓ ALGORITMUS 14 2.41 Elmélet 14 2.42 Program {smidpcirpas} 15 2.5 KÖR KITÖLTÉSE {SFILLCIRPAS} 17 2.6 TÉGLALAP KITÖLTÉSE {SFILLRECPAS} 17 2.7 REKURZÍV KITÖLTÉS {SFLOODFIPAS} 17 2.8 ÁLTALÁNOS POLIGON KITÖLTÉSE 18 2.81 Algoritmus 19 2.82 Kitöltés mintával 21 3. SÍKBELI TRANSZFORMÁCIÓK {SLABDA?PAS} 23 3.1 WINDOW TO VIEWPORT TRANSZFORMÁCIÓ {SWINVIEWPAS} 23 4. KONVEX BUROK ALGORITMUSOK 25 4.1 GRAHAM PÁSZTÁZÁS (SÍKBAN) {SHULLGRHPAS} 25 5. INTERPOLÁCIÓ, APPROXIMÁCIÓ 28 5.1 HERMITE-ÍV 28 5.11 Elsõ eset 28 5.12 Második eset {shermitpas} 30 5.13

Kezdeti érintõ meghatározása 32 5.2 BEZIER GÖRBE 32 5.21 de Casteljau algoritmus { sdecastpas } 32 5.22 A görbe elõállítása Bernstein polinommal {sbezierpas} 33 5.23 Bezier görbe tulajdonságai 33 5.24 Interpoláció Bézier-görbével 33 5.25 Kapcsolódó Bezier görbék 34 5.26 Bezier görbe bevezetése másképpen 34 5.3 3-ADFOKÚ B-SPLINE GÖRBE {S3BSPLNPAS} 36 5.4 B-SPLINE GÖRBE ÁLTALÁNOS ALAKJA {SBSPLNPAS, SCOXDEBUPAS} 39 6. TÉRBELI PONTTRANSZFORMÁCIÓK 40 6.1 EGYBEVÁGÓSÁGI TRANSZFORMÁCIÓ 40 6.2 HASONLÓSÁGI TRANSZFORMÁCIÓK 41 6.3 AFFIN TRANSZFORMÁCIÓK 41 6.4 NYÍRÁS 42 7. TÉR SÍKRA VALÓ LEKÉPEZÉSE 43 7.1 AXONOMETRIA 43 7.2 CENTRÁLIS PROJEKCIÓ, PERSPEKTÍVA 43 7.21 Z tengelyen a C nézõpont az Origótól d távolságra 43 2 7.22 Általános helyzetû nézõpont (alfa, béta, r, d) 43 8. FELÜLETEK ÁBRÁZOLÁSA 44 8.1 LÁTHATÓSÁG SZERINTI ÁBRÁZOLÁS 44 9. FELÜLET INTERPOLÁCIÓ, APPROXIMÁCIÓ 45 9.1 BEZIER FELÜLET

{BEZIERFE?PAS} 45 9.2 B-SPLINE FELÜLET 46 9.21 Általános B-spline felület 46 9.22 Harmadfokú B-spline felület {bspl3fe?pas} 46 10. SÍKLAPOKKAL HATÁROLT TESTEK ÁBRÁZOLÁSA 47 10.1 TESTMODELLEZÉS 47 10.11 Drótváz modell {Poliedertnezop emlathato} 47 10.12 Felületmodell {Poliedertnezoplathato} 48 11. LÁTHATÓSÁG SZERINTI ÁBRÁZOLÁS 51 11.1 HÁTSÓ LAPOK KISZÛRÉSE 51 11.2 Z BUFFER ALGORITMUS 51 11.3 SUGÁRKÖVETÉS (RAY TRACING) {POVRAYDOC} 51 11.31 Algoritmus 51 11.32 A metszéspontok meghatározása 52 11.33 Hatékonyságot növelõ módszerek: 52 3 1. Használt adatszerkezetek Type Ponttype=Record X,Y:integer; end; Type rpoint2dtype=record x,y:real; end; rpoint3dtype=record x,y,z:real; end; Pontsor=array[1.N] of ponttype; 4 2. Raszteres algoritmusok 2.1 Szakasz rajzolása 2.11 Egyszerű növekményes algoritmus m= ∆y y2 − y1 = ∆x x2 − x1 y = m⋅ x + B yi +1 = m ⋅ xi +1 + B Ha az |m|<=1, akkor ∆x = 1 -re ∆y ≤ 1 lesz (azaz

1 lépés x-ben egynél kisebb egyenlő lépést jelent y-ban). yi +1 = m ⋅ ( xi + ∆x ) + B = yi + m ⋅ ∆x, Ha ∆x = 1, akkor yi +1 = yi + m így az ( xi , yi ) pont után a ( xi + 1, round ( yi + m)) pontot kell megjeleníteni. Ha a |m|>1, akkor ∆x = 1 -re ∆y > 1 lesz, (azaz 1 lépés x-ben egynél kisebb egyenlő lépést jelent y-ban). így ∆y = 1 esetén ∆x < 1 , azaz y szerint kell lépkednünk egyesével yi +1 − B yi + ∆y − B ∆y = = xi + , m m m 1 Ha ∆y = 1, akkor xi +1 = xi + m xi +1 = ⎛ 1⎞ így az ( xi , yi ) pont után a ( xi + round ⎜ ⎟ , yi + 1) pontot kell megjeleníteni ⎝ m⎠ Hátrány: ∆y ). ∆x • Ha egyszer is, de osztást kell végezni ( m = • Az m nem egész, így a programban sem tudunk egész típust használni. • A kerekítés szintén időigényes. 5 2.12 Középpontos vonalalgoritmus 2.121 Elmélet m= ∆y y2 − y1 = ∆x x2 − x1 y = m⋅ x + B y= ∆y ⋅x+ B ∆x F ( x , y ) = a ⋅ x

+ b ⋅ y + c ⋅ d = ∆y ⋅ x − ∆x ⋅ y + B ⋅ ∆x = 0 y F(x,y)=0 F(x,y)<0 x F(x,y)>0 Ha 0 ≤ m ≤ 1 , akkor ∆x = 1 -re ∆y < 1 lesz (azaz 1 lépés x-ben egynél kisebb lépést jelent yban). NE Q P=(x p, y p ) M E 1⎞ ⎛ Ha d p +1 = F ⎜ x p + 1, y p + ⎟ > 0 , akkor a P után az NE pontot gyújtjuk ki. ⎝ 2⎠ 1⎞ ⎛ Ha d p +1 = F ⎜ x p + 1, y p + ⎟ < 0 , akkor a P után az E pontot gyújtjuk ki. ⎝ 2⎠ 6 1⎞ ⎛ Ha d p +1 = F ⎜ x p + 1, y p + ⎟ = 0 , akkor a P után az E pontot gyújtjuk ki (megállapodás ⎝ 2⎠ szerint). Ha minden x szerinti lépésben az ( x p +1 , y p +1 ) pontot behelyettesítenénk az F-be, akkor a sok művelet miatt lassú lenne a számítás, ezért próbáljuk meg meghatározni a d p+2 értékét a d p+1 értékéből. Ennek meghatározásához két esetet kell figyelembe vennünk: a) E-t választottuk az x p+1 pontban 1⎞ 1⎞ ⎛ ⎛ d p + 2 = F ⎜ x p + 2, y p + ⎟ = a ⋅ x p + 2 + b

⋅ ⎜ y p + ⎟ + c ⎝ ⎝ 2⎠ 2⎠ ( ) 1⎞ 1⎞ ⎛ ⎛ d p +1 = F ⎜ x p + 1, y p + ⎟ = a ⋅ x p + 1 + b ⋅ ⎜ y p + ⎟ + c ⎝ ⎝ 2⎠ 2⎠ ( ) ∆E = d p + 2 − d p +1 = a = ∆y b) NE-t választottuk az x p+1 pontban 3⎞ 3⎞ ⎛ ⎛ d p + 2 = F ⎜ x p + 2, y p + ⎟ = a ⋅ x p + 2 + b ⋅ ⎜ y p + ⎟ + c ⎝ ⎝ 2⎠ 2⎠ ( ) 1⎞ 1⎞ ⎛ ⎛ d p +1 = F ⎜ x p + 1, y p + ⎟ = a ⋅ x p + 1 + b ⋅ ⎜ y p + ⎟ + c ⎝ ⎝ 2⎠ 2⎠ ( ) ∆NE = d p + 2 − d p +1 = a + b = ∆y − ∆x Meghatároztuk, hogy az x szerint lépkedve, hogyan változik a d az előző x d értékére alapozva. Mostmár csak a d kezdeti értékét kell meghatároznunk Az első képpontunk a szakasz egyik végpontja, legyen ez ( x0 , y 0 ) . 1⎞ ⎛ Az első középpont ⎜ x0 + 1, y0 + ⎟ -nél van, és így ⎝ 2⎠ 1⎞ b b ⎛ F ⎜ x0 + 1, y0 + ⎟ = a ⋅ x0 + b ⋅ y0 + c + a + = F ( x0 , y0 ) + a + . ⎝ 2 2⎠ 2 Mivel ( x0 , y0 ) a vonalon van, az F ( x0 ,

y0 ) = 0, így a d kezd = a + ∆x b = ∆y − . 2 2 A törtek elkerüléséhez szorozzuk meg az F függvény értékét 2-vel. 2.122 Algoritmus {smidplinpas} procedure MidpointLine(x0,y0,x1,y1:integer;color:word); Var x,y,dx,dy,incE,incNE,d:longint; begin dx:=x1-x0; dy:=y1-y0; d:= 2*dy-dx; 7 incE:=2*dy; incNE:=2*(dy-dx); x:=x0; y:=y0; setpixel(x,y,color); while x<x1 do begin if d<=0 then begin inc(d,incE);inc(x);end else begin inc(d,incNE);inc(x);inc(y);end; setpixel(x,y,color); end; end; Készítsük el a programot úgy, hogy tetszőleges meredekségű egyenesre működjön. 1. Lépés: A tetszőleges meredekségű szakasz végpontjait az első síknyolcadba transzformáljuk 2.-ból az 1-be = X tengelyre tükrözés ( x , y ) ⎯Y⎯⎯⎯⎯⎯⎯ ⎯ ( y , x ) 3.-ból az 1-be tengelyre tükrözés = X tengelyre tükrözés ( x , y ) ⎯Y⎯⎯⎯⎯⎯ ⎯ ( − x , y ) ⎯Y⎯⎯⎯⎯⎯⎯ ⎯ ( y ,− x ) 4.-ből az 1-be tengelyre tükrözés. ( x , y )

⎯Y⎯⎯⎯⎯⎯ ⎯ ( − x , y ) 2. Lépés: A szakasz végpontjait X koordinátájuk szerint rendezzük (p0,p1) 3. Lépés: Használjuk az eredeti Midpointline algoritmust procedure csere(var x0,y0,x1,y1:integer); var x,y:integer; begin x:=x0;x0:=x1;x1:=x; y:=y0;y0:=y1;y1:=y; end; Procedure transzYt(var x,y:integer); {X=0} var s:integer; begin x:=-x; end; Procedure transzXYt(var x,y:integer); {X=Y} var s:integer; begin s:=x;x:=y;y:=s; end; procedure linepoints(x,y:integer;color:word;nyolcad:nyolcadtipus); begin case nyolcad of 2: transzXYt(x,y); 8 3: begin transzXYt(x,y);transzYt(x,y);end; 4: transzYt(x,y); end; putpixel(x+origox,-y+origoy,color); end; procedure MidpLine(x0,y0,x1,y1:integer;color:word;nyolcad:nyolcadtipus); Var dx,dy,incE,incNE,d:longint; x,y:integer; begin dx:=x1-x0; dy:=y1-y0; d:= 2*dy-dx; incE:=2*dy; incNE:=2*(dy-dx); x:=x0; y:=y0; linepoints(x,y,color,nyolcad); while x<x1 do begin if d<=0 then begin inc(d,incE);inc(x);end else begin

inc(d,incNE);inc(x);inc(y);end; linepoints(x,y,color,nyolcad); end; end; Procedure Xsorba (var x0,y0,x1,y1:integer); begin if x0>x1 then csere(x0,y0,x1,y1); end; Procedure Teszt(var x0,y0,x1,y1:integer;var nyolcad:nyolcadtipus); Var dx,dy:integer; begin dx:=x1-x0; dy:=y1-y0; if DX=0 then begin nyolcad:=2;transzXYt(x0,y0);transzXYt(x1,y1);end else begin if (0<=DY/DX) AND (DY/DX<=1) then nyolcad:=1; if (-1<=DY/DX) AND (DY/DX<0) then begin nyolcad:=4;transzYt(x0,y0);transzYt(x1,y1);end; if (DY/DX>1) then begin nyolcad:=2;transzXYt(x0,y0);transzXYt(x1,y1);end; if (DY/DX<-1) then begin nyolcad:=3;transzYt(x0,y0);transzYt(x1,y1); transzXYt(x0,y0);transzXYt(x1,y1);end; end; 9 end; procedure MidpointLine(x0,y0,x1,y1:integer;color:word); Var nyolcad:nyolcadtipus; begin Teszt(x0,y0,x1,y1,nyolcad); Xsorba(x0,y0,x1,y1); MidpLine(x0,y0,x1,y1,yellow,nyolcad); end; A Pascalban: Line (x1, y1, x2, y2: Integer); Linerel (Dx, Dy: Integer); LineTo (X, Y: Integer); SetLineStyle

(LineStyle: Word; Pattern: Word; Thickness: Word); 2.2 Szakasz lehatárolása 2.21 Cohen-Sutherland algoritmus 2.211 Elmélet f R V [j] S V [] U a K [a] K [a,b] T K [] b j Az algoritmus folyamatábrája 10 Start R, S, U, T; K, V A sík 9 részre vágása, a kódok (b,a,j,f) hozzárendelése a síkrészekhez K-hoz és V-hez a kódok hozzárendelése Kód ( K ) I Kód (V ) ≠ ∅ Yes K,V I R, S ,U , T = ∅ Stop No K: = K ,V I K kódbeli egyenes Yes Kód ( K ) ≠ ∅ No V : = K ,V IV kódbeli egyenes Yes Kód (V ) ≠ ∅ No K,V szakasz kirajzolása Stop 2.212 Program {scohsuthpas} procedure Clip (bax,bay,jfx,jfy,x1,y1,x2,y2:real;color,linestyle,thickness:word ); type el=(bal,jobb,also,felso); kodok=set of el; Var c,c1,c2:kodok;x,y:real; label return; Procedure Kod(x,y:real;var c:kodok); begin c:=[]; if x<bax then c:=[bal] else if x>jfx then c:=[jobb]; if y<bay then c:=c+[also] else if y>jfy then c:=c+[felso]; end; 11 begin {Clip}

kod(x1,y1,c1);kod(x2,y2,c2); segment(round(x1),round(y1),round(x2),round(y2),color,dottedln,n ormwidth); while (c1<>[]) or (c2<>[]) do begin if (c1*c2)<>[] then goto return; c:=c1; if c=[] then c:=c2; if bal in c then {metszes a bal elen} begin y:=y1+(y2-y1)*(bax-x1) / (x2-x1); x:=bax; end else if jobb in c then {metszes a jobb elen} begin y:=y1+(y2-y1)*(jfx-x1) / (x2-x1); x:=jfx; end else if also in c then {metszes also elen} begin x:=x1+(x2-x1)*(bay-y1) / (y2-y1); y:=bay; end else if felso in c then {metszes felso elen} begin x:=x1+(x2-x1)*(jfy-y1) / (y2-y1); y:=jfy; end; if c=c1 then begin circle(origox+round(x),round(y)+origoy,4);x1:=x;y1:=y;kod(x,y,c1);end else begin circle(origox+round(x),round(y)+origoy,4);x2:=x;y2:=y;kod(x,y,c2);end; end; segment(round(x1),round(y1),round(x2),round(y2),color,linestyle, thickness); return: end; 2.3 Poligonlehatárolás (Sutherland-Hodgman) (Tetszőleges poligont vág konvex poligonra.) 12 1 vágandó poligon vágó

poligon III IV II I 3 2 4 1. eset Belseje Külseje 2. eset Belseje 3. eset Külseje Belseje 4. eset Külseje s Belseje Külseje p p s s r s p vágóél Output: p vágóél Output: r p vágóél Output:- vágóél Output: r, p Procedure SatHod(Input poligon:pontsor;Var output poligon:pontsor;inputhossz:integer; Var outputhossz:integer;vagoel:integer); {egy vágóélre vágja az input poligont} Var s,p,r:pointtype; j:integer; begin outputhossz:=0; s:=input poligon[inputhossz]; for j:=1 to inputhossz do begin p:=input poligon[j]; if belseje(p,vagoel) then {1,4 eset} begin if belseje(s,vagoel) then {1 eset} output(p,outputhossz,output poligon) else {4 eset} begin metszes(s,p,vagoel,r); ouput(r,outputhossz,output poligon); 13 r ouput(p,outputhossz, output poligon); end; end else {2,3 eset} if belseje(s,vagoel) then {2} begin metszes(s,p,vagoel,r); ouput(r,outputhossz, output poligon); end; s:=p; end; {for} end; Begin For VE=I to IV do begin SatHod(vágandó

poligon,vágott poligon,4,outputhossz,VE); vágandó poligon:= vágott poligon; end; End. A Pascalban: DrawPoly (NumPoints: Word; var PolyPoints); 2.4 Középpontos körrajzoló algoritmus 2.41 Elmélet (-x,y) (-y,x) (x,y) ⎛ R R⎞ ⎜ , ⎝ 2 2⎠ (y,x) R (y,-x) (-y,-x) (-x,-y) (x,-y) F ( x, y) = x 2 + y 2 − R2 14 F(x,y)>0 P=(x p, y p ) E R M F(x,y)<0 M SE M F(x,y)=0 ( 2 ) 2 1⎞ 1⎞ ⎛ ⎛ Ha d p +1 = F ( M ) = F ⎜ x p + 1, y p − ⎟ = x p + 1 + ⎜ y p + ⎟ − R 2 ≥ 0 , akkor SE-t, ⎝ ⎝ 2⎠ 2⎠ egyébként az E-t választjuk. a) E-t választottuk az x p+1 pontban d p+2 ( ) 2 ) 2 2 1⎞ 1⎞ ⎛ ⎛ = F ⎜ x p + 2, y p − ⎟ = x p + 2 + ⎜ y p − ⎟ − R 2 ⎝ ⎝ 2⎠ 2⎠ ∆E = d p + 2 − d p +1 = 2 ⋅ x p + 3 b) SE-t választottuk az x p+1 pontban ( 2 3⎞ 3⎞ ⎛ ⎛ d p + 2 = F ⎜ x p + 2, y p − ⎟ = x p + 2 + ⎜ y p − ⎟ − R 2 ⎝ ⎠ ⎝ 2⎠ 2 ∆SE = d p + 2 − d p +1 = 2 ⋅ x p − 2 ⋅ y p

+ 5 Meghatároztuk, hogy az x szerint lépkedve, hogyan változik a d az előző x d értékére alapozva. Mostmár csak a d kezdeti értékét kell meghatároznunk Az első képpontunk a (0, R) . 1⎞ ⎛ Az első középpont ⎜ 1, R − ⎟ -nél van, és így ⎝ 2⎠ 1⎞ 1 5 ⎛ d kezd = F ⎜ 1, R − ⎟ = 1 + R 2 − R + − R 2 = − R. ⎝ ⎠ 2 4 4 2.42 Program {smidpcirpas} procedure Circlepontok(centrumx,centrumy,x,y:integer;c:word); begin setpixel(x+centrumx,y+centrumy,c); setpixel(y+centrumx,x+centrumy,c); setpixel(y+centrumx,-x+centrumy,c); 15 setpixel(x+centrumx,-y+centrumy,c); setpixel(-x+centrumx,-y+centrumy,c); setpixel(-y+centrumx,-x+centrumy,c); setpixel(-x+centrumx,y+centrumy,c); setpixel(-y+centrumx,x+centrumy,c); end; procedure MidPointCircle(centrumx,centrumy,r:integer; szin:word); var d:integer;x,y:integer; begin x:=0; y:=r; d:=1-r; Circlepontok(centrumx,centrumy,x,y,szin); while y>x do begin if d<0 then begin d:=d+2*x+3; inc(x); end else begin

d:=d+2*(x-y)+5; inc(x); dec(y); end; Circlepontok(centrumx,centrumy,x,y,szin); end; end; A Pascalban: Arc (X,Y: Integer; StAngle, EndAngle, Radius: Word); Circle (X,Y: Integer; Radius: Word); GetArcCoords (var ArcCoords; ArcCoordsType ); 16 2.5 Kör kitöltése {sfillcirpas} (-x,y) (-y,x) (x,y) ⎛ R R⎞ ⎜ , ⎝ 2 2⎠ (y,x) R (y,-x) (-y,-x) (-x,-y) (x,-y) 2.6 Téglalap kitöltése {sfillrecpas} Csak a bal oldali, és az alsó éleket rajzoljuk ki. Procedure FillRec(xmin,ymin,xmax,ymax:integer;color:word); var x,y:integer; begin for y:=ymin to ymax do for x:=xmin to xmax do setpixel(x,y,color); end; 2.7 Rekurzív kitöltés {sfloodfipas} procedure flood fill(x,y:INTEGER;hatterszin,szin:word); begin if getpixel(x,y)=hatterszin then begin putpixel(x,y,szin) flood fill(x+1,y,hatterszin,szin); flood fill(x-1,y,hatterszin,szin); flood fill(x,y+1,hatterszin,szin); flood fill(x,y-1,hatterszin,szin); end; end; A Pascalban: procedure FloodFill (x,y: Word; BorderColor: Word);

17 2.8 Általános poligon kitöltése Szélső Belső pixelek A kitöltési algoritmus lépései: 1. A scan-line metszéspontjainak meghatározása a polygon minden élével 2. A metszéspontok rendezése x kordináta szerint 3. Azon pixelek kitöltése a metszéspontok között, melyek a poligon belsejében fekszenek, használva egy paritás bitet. 18 Problémák: 3.1 Nem egész kordinátájú metszéspont esetén hogyan állapítható meg, hogy melyik oldalon lévő pixel tartozik a poligon belsejébe? 3.2 Hogyan kezelhetők az egész koordinátájú metszéspontok? 3.3 Hogyan kezelhetőek a 32 beli pontok közös él esetén? 3.4 Hogyan kezelhetőek a 32 beli pontok vizszintes él esetén? Megoldások: 3.1 Bal oldal felfelé, jobb oldal lefelé kerekítéssel 3.2 A bal oldali pixelt belsőnek, a jobb oldalit külsőnek tekintjük 3.3 Egy élre vonatkozóan csak az ymin csúcsot rajzoljuk ki, az ymax csúcsa az élnek akkor lesz kirajzolva, ha az ymin csúcsa egy másik

élnek. 3.4 Hasonlóan a téglalaphoz az alsó élek ki lesznek rajzolva, a felső élek viszont nem 2.81 Algoritmus Az ET (él tábla) lista: EF nil 7 9 7 DE -5/2 11 7 6/4 nil CD 11 5 13 0 nil 0 nil FA 3 9 2 3 7 -5/2 Xmin 1/m y koord. 1 BC Ymax AB 3 7 -5/2 ET • Az y koordináták az élek alacsonyabb csúcsának y koordinátája • Az ymax az él maximális y koordinátája • Az xmin az él alacsonyabb csúcsának az x koordinátája • 1/m az él meredeksége 19 nil • A vizszintes lista élei xmin koordinátájuk szerint vannak rendezve Az AET (aktív él tábla) lista: 1. Töltsük fel az ET listát 2. Legyen y az ET lista első elemének az y-ja 3. Inicializáljuk üresnek az AET listát 4. Ismételjük a következőket, amíg az ET és AET listák üresek nem lesznek: 4.1 Tegyük az AET listába azokat az éleket, amelyekre y= ymin , majd rendezzük az az AET-ben lévő éleket az x koordináta szerint. 4.2 Rajzoljuk ki

az y scan line-t, az AET-ben lévő x koordinátapárok között, figyelembe véve a paritást. 4.3 y:=y+1 4.4 Távolítsuk el azokat az eleket az AET-ből, amelyekre y= ymax 4.5 Minden nem függőleges AET-beli élre x:=x+ Szükséges adatszerkezetek: {dfillpol.pas} Type Elmutato=^El; El=record ymax:integer; xmin:real; xmer:real; Elre:Elmutato; end; ETmutato=^ETelem; ETelem=record y:integer; ETre:ETmutato; Elre:Elmutato; end; 20 1 . m 2.82 Kitöltés mintával Kitöltés mintával Scan-konverziót használva Probléma: a minta melyik pixele rendelődjön hozzá az aktuális pixelhez. • a minta bal első pixelét rendeljük a poligon egy csúcsához. • SRGP esetén a teljes képernyőt az adott mintával kitöltöttnek feltételezzük, és a kitöltendő területen átlátszatjuk. MxN-es minta esetén a képernyő origójához a Minta(0,0) pixelét rendeljük, egy x,y ponthoz pedig a minta minta[x div M, y div N] pixelét. Kitöltés mintával ismételt Scan-converzió

nélkül • Átmásoljuk a kitöltenő területet egy téglalap tartományra, és ezen tartomány minden pixelét a megfelelő helyre írjuk. A Pascalban: procedure DrawPoly(NumPoints: Word; var PolyPoints); procedure FillPoly(NumPoints: Word; var PolyPoints); Sets the fill pattern and color. Declaration: procedure SetFillStyle(Pattern: Word; Color: Word); Selects a user-defined fill pattern. Declaration: procedure SetFillPattern(Pattern: FillPatternType; Color: Word); Gets the current fill pattern and color, as set by SetFillStyle or SetFillPattern. Declaration: procedure GetFillSettings(var FillInfo: FillSettingsType); FillPatternType Record that defines a user-defined fill pattern; used by GetFillPattern and SetFillPattern. Declaration: FillPatternType = array [1.8] of Byte; Fill Pattern Constants 21 Use these constants as fill patterns for GetFillSettings and SetFillStyle. Constant EmptyFill SolidFill LineFill LtSlashFill SlashFill BkSlashFill LtBkSlashFill HatchFill

XhatchFill InterleaveFill WideDotFill CloseDotFill UserFill Value 0 1 2 3 4 5 6 7 8 9 10 11 12 Meaning Uses background color Uses draw color --- fill /// fill /// thick fill hick fill fill Light hatch fill Heavy cross hatch Interleaving line Widely spaced dot Closely spaced dot User-defined fill 22 3. Síkbeli transzformációk {slabda?pas} • Window to Viewport • eltolás • forgatás tengelyek körül • skálázás 3.1 Window to Viewport transzformáció {swinviewpas} y ( xmax , ymax ) y v v (umax , vmax ) ( xmin , ymin ) x Világkoordináta rendszer x Eltolás az origóba 23 u Skálázás (umin , vmin ) Eltolás u ⎛u − u min v max − v min ⎞ M wv = T(u min , v min ) ⋅ S⎜ max , ⎟ ⋅ T( − x min ,− y min ) = ⎝ x max − x min y max − y min ⎠ ⎛ u max ⎜ ⎛ 1 0 u min ⎞ ⎜ x max ⎟ ⎜ ⎜ ⎜ 0 1 v min ⎟ ⋅ ⎜ ⎟ ⎜ 1 ⎠ ⎜ ⎝0 0 ⎜ ⎝ ⎛ u max ⎜ ⎜ x max ⎜ ⎜ ⎜ ⎜ ⎝ − u min − x min 0 0 −

u min − x min 0 0 0 v max − v min y max − y min 0 − x min ⋅ 0 v max − v min y max − y min 0 − y min⋅ ⎞ 0⎟ ⎟ ⎛ 1 0 − x min ⎞ ⎟ ⎜ 0⎟ ⋅ ⎜ 0 1 − y min ⎟ = ⎟ ⎜ ⎟ 1 ⎠ 1⎟ ⎝ 0 0 ⎟ ⎠ u max − u min ⎞ + u min ⎟ x max − x min ⎟ v max − v min + v min ⎟ ⎟ y max − y min ⎟ 1 ⎟ ⎠ ⎛ ⎞ u v − u min − v min P ′ = ⎜ (x − x min ) ⋅ max + u min , ( y − y min ) ⋅ max + v min , 1 ⎟ x max − x min y max − y min ⎝ ⎠ 24 4. Konvex burok algoritmusok 4.1 GRAHAM pásztázás (síkban) {shullgrhpas} Bonyolultság: O(n ⋅ log( n)) Adott: p 0 , p1 ,., p n síkbeli pontok Q halmaza Feladat: p 0 , p1 ,., p n pontok KB(Q) konvex burkát (az a legszűkebb konvex poligon, amely vagy belső pontként vagy csúcspontként tartalmazza az összes p 0 , p1 ,., p n pontot) előállítani. Szükséges adatszerkezetek: P: a p 0 , p1 ,., p n pontok S: verem, amiben a KB(Q) pontok keletkeznek. A P és S

implementálhatók tömbbel vagy kétirányú láncolt listával. Szükséges eljárások: procedure INIT(var S): Üresnek inicializálja a vermet. procedure PUSH(var S,E): a verem tetejére tesz egy E elemet. procedure POP(var S): eltávolítja a veremből a legfelső elemet. function TOP(S): visszaadja a verem a legfelső elemét, de nem távolítja el. function TOP2(S): visszaadja a verem a legfelső alatti elemét, de nem távolítja el. Algoritmus lépései: 1. Legyen p 0 a Q-nak minimális y koordinátájú pontjai közül a legbaloldalibb 25 2. Legyen p 1 ,, p n (Q többi pontja), a p 0 -ra vonatkozó polárszögeik szerint órajárással ellentétes sorrendben rendezve p 0 körül. Ha több pontnak is ugyanaz a polárszöge, akkor csak a p 0 -tól legtávolabbi pontot tartjuk meg további feldolgozásra. 3. INIT(S); 4. PUSH(S, p 0 ); 5. PUSH(S, p 1 ); 6. PUSH(S, p 2 ); 7. FOR j:=3 to n DO BEGIN WHILE TOP2(S),TOP(S), p j pontok alkotta szög nem bal fordulatot végez DO

POP(S); PUSH(S, p j ) END; Polárszög szerinti rendezés: 1. A rendezés miatt a P adatszerkezet elemei tartalmazzák a következő információkat: • x 26 • y • polárszög, • távolság p 0 -tól 2. Minden p j -re számoljuk ki a polárszöget, és a p 0 -tól való távolságot 3. Rendezzük a p 1 ,, p n pontokat polárszögeik szerint növekvő sorrendbe, majd az azonos polárszögű pontok közül csak a p 0 -tól legtávolabbit tartsuk meg. A vektoriális szorzást használjuk a polárszögek kiszámításához. r r r r r r a ,b = z ( y a ⋅ zb − za ⋅ y b , za ⋅ x b − x a ⋅ zb , x a ⋅ y b − y a ⋅ x b ) , ahol a , b és z jobbrendszert r r r r r alkotnak, és | z |= |a||⋅ b|⋅ sin(a , b) . [ ] Pj (xj,yj) b P0 a (x0,y0) Az ábra T (x0+1,y0) alapján a(1,0,0), b( x j - x 0 , y j - y 0 ,0) adódik. ⎧ ⎞ ⎛ y j − y0 ⎟ ⎜ ⎪ ⎟ , ha x j ≥ x 0 ⎪ arcsin⎜ 2 2 ⎟ ⎜ ⎪⎪ ⎝ x j − x0 + y j − y0 ⎠ polárszög

= ⎨ ⎞ ⎛ ⎪ y j − y0 ⎟ ⎜ ⎪Π − arcsin⎜ ⎟ , egyébként ⎪ ⎜ x j − x0 2 + y j − y0 2 ⎟ ⎠ ⎝ ⎪⎩ ( ) ( ( ) ) ( ) Balra fordulás: A vektoriális szorzattal könnyen eldönthető. 27 Így a p j -hez tartozó 5. Interpoláció, approximáció 5.1 Hermite-ív 5.11 Első eset Adott két pont, p0 és p1, valamint a két pontban az érintő vektorai, t0 és t1. t0 p 1 p 0 t1 Egy harmadfokú polinomiális görbét keresünk, melynek egyenlete a következő alakú: S(u) = a 0u 3 + a 1u 2 + a 2 u + a 3 u ∈[0,1] . Ebben az egyenletben négy ismeretlen szerepel, ugyanakkor meg tudunk adni négy egyenletet, melyek a kezdeti feltételeket írják le. Ezek: S(0) = p 0 S(1) = p1 S& (0) = t 0 S& (1) = t1 Az egyenletrendszer megoldása: 28 S(0) = p 0 = a 3 S(1) = p1 = a 0 + a 1 + a 2 + a 3 S& (0) = t = a 0 2 S& (1) = t 1 = 3 ⋅ a 0 + 2 ⋅ a 1 + a 2 −−−−−−−−−−−−−−−− p1 = a 0 + a 1 + t 0

+ p 0 a 0 = p1 − p 0 − t 0 − a 1 t1 = 3 ⋅ a 0 + 2 ⋅ a 1 + t 0 −−−−−−−−−−−−−−−− t1 = 3 ⋅ p1 − 3 ⋅ t 0 − 3 ⋅ p 0 − 3 ⋅ a 1 + 2 ⋅ a 1 + t 0 a 1 = 3 ⋅ p1 − 3 ⋅ p 0 − 2 ⋅ t 0 − t1 a 0 = 2 ⋅ p 0 − 2 ⋅ p1 + t 0 + t 1 ====================== A megoldások behelyettesítése: S ( u ) = ( 2 ⋅ p 0 − 2 ⋅ p 1 + t 0 + t 1 ) ⋅ u 3 + ( −3 ⋅ p 0 + 3 ⋅ p 1 − 2 ⋅ t 0 − t 1 ) ⋅ u 2 + t 0 ⋅ u + p 0 ⎡u 3 ⎤ ⎢ 2⎥ ⎡x(u ) ⎤ ⎢u ⎥ M = ? S( u) = ⎢ = G • M • U = [ p , p , t , t ] • M • H H 0 1 0 1 H H ⎥ ⎢u ⎥ ⎣ y( u) ⎦ ⎢ ⎥ ⎢⎣ 1 ⎥⎦ ⎡1⎤ ⎡0⎤ ⎢1⎥ ⎢0⎥ S(0) = p 0 = G H • M H • ⎢ ⎥ S(1) = p1 = G H • M H • ⎢ ⎥ ⎢1⎥ ⎢0⎥ ⎢⎥ ⎢ ⎥ ⎣1⎦ ⎣1⎦ ⎡3 ⎤ ⎡0⎤ ⎢2 ⎥ ⎢0⎥ &S(0) = t = G • M • ⎢ ⎥ S& (1) = t = G • M • ⎢ ⎥ 0 H H 1 H H ⎢1 ⎥ ⎢1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 ⎦ ⎣0⎦ ⎡0 ⎢0 [p0 p1 t 0

t1 ] = GH = GH • M H • ⎢⎢0 ⎢ ⎣1 1 0 3⎤ ⎡0 ⎢0 ⎥ 1 0 2 ⎥ ⇒ MH = ⎢ ⎢0 1 1 1⎥ ⎢ ⎥ 1 0 0⎦ ⎣1 1 0 3⎤ 1 0 2⎥ ⎥ 1 1 1⎥ ⎥ 1 0 0⎦ ⎡ 2 −3 0 ⎢− 2 3 0 ⎡x( u ) ⎤ ⎢ S( u) = ⎢ ⎥ = G H • M H • U = [p 0 , p1 , t 0 , t1 ] • ⎢ 1 − 2 1 ( ) y u ⎣ ⎦ ⎢ ⎣ 1 −1 0 −1 1⎤ ⎡ u 3 ⎤ ⎢ ⎥ 0⎥ ⎢u 2 ⎥ ⎥• 0⎥ ⎢ u ⎥ ⎥ ⎢ ⎥ 0⎦ ⎢⎣ 1 ⎥⎦ Az egyenlet átrendezése: S( u ) = ( 2u 3 − 3u 2 + 1)p 0 + ( −2u 3 + 3u 2 )p 1 + ( u 3 − 2u 2 + u ) t 0 + ( u 3 − u 2 ) t 1 29 u ∈ [ 0,1] Az egyenletben szereplő együttható polinomokat Hermite-polinomoknak nevezzük, és a következőképpen jelöljük: H 0 = 2u 3 − 3u 2 + 1 H1 = −2u 3 + 3u 2 H 2 = u 3 − 2u 2 + u H3 = u 3 − u 2 Az egységesebb szemléletmód miatt felírhatjuk a görbét mátrix alakban is: S( u) = ( u 3 u2 1 ⎞ ⎛ p0 ⎞ ⎛ 2 −2 1 ⎜ ⎟⎜ ⎟ ⎜ − 3 3 − 2 − 1⎟ ⎜ p1 ⎟ u 1)⎜ 0 0 1 0 ⎟ ⎜

t0 ⎟ ⎜ ⎟⎜ ⎟ 0 0 0 ⎠ ⎝ t1 ⎠ ⎝ 1 5.12 Második eset {shermitpas} Adott három pont, p0 és p1, p2 valamint az első pontban az érintő vektora, t0. p 1 t0 p 2 p 0 Egy harmadfokú polinomiális görbét keresünk, melynek egyenlete a következő alakú: S(u) = a 0u 3 + a 1u 2 + a 2 u + a 3 u ∈[0,1] . Ebben az egyenletben négy ismeretlen szerepel, ugyanakkor meg tudunk adni négy egyenletet, melyek a kezdeti feltételeket írják le. Ezek: S( −1) = p 0 S(0) = p 1 S(1) = p 2 S& ( −1) = t 1 Az egyenletrendszer megoldása: 30 S( −1) = p 0 = − a 0 + a 1 − a 2 + a 3 S(0) = p1 = a 3 S(1) = p 2 = a 0 + a 1 + a 2 + a 3 S& ( −1) = t 0 = 3 ⋅ a 0 − 2 ⋅ a 1 + a 2 −−−−−−−−−−−−−−−− p 0 − p1 = − a 0 + a 1 − a 2 t0 = 3 ⋅ a 0 − 2 ⋅ a1 + a 2 p 2 − p1 = a 0 + a1 + a 2 −−−−−−−−−−−−−−−− 3 ⋅ p 0 − 4 ⋅ p1 + p 2 + 2 ⋅ t 0 4 − 5 ⋅ p 0 + 4 ⋅ p1 + p 2 − 2

⋅ t 0 a1 − 2 ⋅ a 2 a 2 = 3 ⋅ p 0 − 3 ⋅ p1 + t 0 = 4 p 0 + p 2 − 2 ⋅ p1 2 ⋅ a1 p 0 + p 2 − 2 ⋅ p1 = a1 = 2 ===================== p 0 − p1 = −a 0 + a 1 − a 2 a 0 = A megoldások behelyettesítése: ⎛ 3p − 4p1 + p 2 + 2 t 0 ⎞ 3 ⎛ p 0 − 2p 1 + p 2 ⎞ 2 ⎛ − 5p 0 + 4p 1 + p 2 − 2 t 0 ⎞ S(u) = ⎜ 0 ⎟u + ⎜ ⎟u + ⎜ ⎟ u + p1 ⎝ ⎠ ⎝ ⎠ ⎠ ⎝ 4 2 4 4 ⎛ 3p − 4p1 + p 2 + 2 t 0 ⎞ 3 ⎛ 2p 0 − 4p 1 + 2p 2 ⎞ 2 ⎛ − 5p 0 + 4p 1 + p 2 − 2 t 0 ⎞ S(u) = ⎜ 0 ⎟u + ⎜ ⎟u + ⎜ ⎟ u + p1 ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 4 4 4 4 ⎡u 3 ⎤ ⎢ 2⎥ ⎡x( u) ⎤ ⎢u ⎥ M = ? = • • = • • S( u) = ⎢ G M U [ p , p , p , t ] M H H 0 1 2 0 H H ⎥ ⎢u ⎥ ⎣ y( u ) ⎦ ⎢ ⎥ ⎢⎣ 1 ⎥⎦ ⎡− 1⎤ ⎡0⎤ ⎢1⎥ ⎢0⎥ S( −1) = p 0 = G H • M H • ⎢ ⎥ S(0) = p1 = G H • M H • ⎢ ⎥ ⎢− 1⎥ ⎢0⎥ ⎢ ⎥ ⎢ ⎥ ⎣1⎦ ⎣1 ⎦ ⎡1⎤ ⎡3 ⎤ ⎢1⎥ ⎢− 2⎥ & ⎢ ⎥ S(1) = p 2 =

G H • M H • S( −1) = t 0 = G H • M H • ⎢ ⎥ ⎢1⎥ ⎢1 ⎥ ⎢⎥ ⎢ ⎥ ⎣1⎦ ⎣0 ⎦ ⎡− 1 ⎢1 [p0 p1 p2 t 0 ] = GH = GH • M H • ⎢⎢− 1 ⎢ ⎣1 0 1 3⎤ ⎡− 1 ⎢1 0 1 − 2⎥ ⎥ ⇒ MH = ⎢ ⎢− 1 0 1 1 ⎥ ⎥ ⎢ 1 1 0 ⎦ ⎣1 31 3⎤ 0 1 − 2⎥ ⎥ 0 1 1 ⎥ ⎥ 1 1 0 ⎦ 0 1 −1 1 5 ⎡3 − ⎢4 2 4 ⎢− 1 − 1 1 x ( u ) ⎡ ⎤ 1 1 S( u) = ⎢ = GH • M H • U = [p 0 , p1 , p 2 , t 0 ] • ⎢ 1 ⎥ ⎢ y ( u ) ⎣ ⎦ 2 4 ⎢4 1 1 ⎢ 0 − ⎢⎣ 2 2 ⎤ 0⎥ ⎡ 3 ⎤ u 1⎥ ⎢u 2 ⎥ ⎥•⎢ ⎥ 0⎥ ⎢u ⎥ ⎥ ⎢ ⎥ 0⎥ ⎢⎣ 1 ⎥⎦ ⎥⎦ 5.13 Kezdeti érintő meghatározása II. I. p e d/2 e 1 p 1 d p p 0 2 p p 0 2 5.2 Bezier görbe Adottak: p 0 ,., p n approximálandó pontok a síkban (vagy térben), és u ∈ R 5.21 de Casteljau algoritmus { sdecastpas } p 0i = p i (i = 0,1,., n) p ri (u) = (1 − u) ⋅ p ri −1 (u) + u ⋅ p ri +−11 (u) A görbe u = 1 3 (r = 1,., n és i =

0,1,, n − r ) paraméterhez tartozó pontjának megszerkesztése a de Casteljau algoritmussal. Az így meghatározott p n0 ( u ) pont a Bezier görbe u paraméterhez tarozó pontja. p p p1 1 1 2 p1 2 p2 p 1 p3 p1 0 p p2 0 0 0 32 3 5.22 A görbe előállítása Bernstein polinommal {sbezierpas} n S(u) = ∑ p j ⋅ B nj (u) (u ∈[0,1]) a Bezier görbe u paraméterhez tartozó pontja, ahol a j=0 ⎛ n⎞ B nj (u) = ⎜ ⎟ ⋅ u j ⋅ (1 − u) n − j a Bernstein polinom. ⎝ j⎠ 5.23 Bezier görbe tulajdonságai Bersnstein polinom tulajdonságai! • A Bezier görbe kontrollpontjainak affin transzformációjára invariáns (következik a de Casteljau-féle előállításból). • Ha u ∈[0,1] , akkor a Bezier görbe kontrollpontjainak konvex burkán belül van. • A Bezier görbe az első és utolsó kontrollponton áthalad. • Bezier görbe szimmetrikus. • Ha u ∈[0,1] akkor ezen görbe kezdő- és végérintője: d d p(1) = n( p n − p n

−1 ) p(0) = n( p1 − p 0 ) du du • Approximáló görbe ugyanakkor igaz a következő tulajdonság is: a Bézier-görbének bármely síkkal legfeljebb annyi metszéspontja van, ahány pontban a sík a kontrollpoligont metszi. • Az eljárás tehát, amint azt a képletből könnyen láthatjuk, n pontot n-1-edfokú görbével approximál, azaz a kontrollpontok számának növekedésével nő a poligon fokszáma is. 5.24 Interpoláció Bézier-görbével Mint már említettük, a Bézier-görbe a kontrollpontok közül csak az elsőre és az utolsóra illeszkedik, a többit approximálja. Most egy olyan eljárást mutatunk be, mely adott pontokhoz olyan Bézier-görbét számít ki, amely az adott pontok mindegyikén átmegy. Ezt úgy érjük el, hogy feltételezzük az adott pontokról, hogy a görbe pontjai, majd ebből visszaszámoljuk a kontrollpontokat. Legyen adott a p0,p1,p2,.,pn pontsorozat, valamint a u0 , u1 ,, un ∈[0,1] számok Keressük azt az S(t)

Bézier-görbét, amelyre S ( ui ) = p i i = 0,., n Ezek a feltételek a b0,b1,b2,.,bn kontrollpontokra a következő egyenleteket adják: n S(ui ) = ∑ b j B nj (ui ) i = 0,., n j =0 Ez az egyenletrendszer a Bernstein-polinomok lineáris függetlensége miatt egyértelműen megoldható a bj kontrollpontokra mint ismeretlenekre nézve, és az ezekkel felírt Béziergörbe az eredeti pontok mindegyikét interpolálni fogja. 33 5.25 Kapcsolódó Bezier görbék Tegyük fel, hogy két harmadfokú Bézier-görbe szegmenst akarunk csatolni. Ezek négy-négy kontrollponttal rendelkeznek, ezek helyzetére kell megszorításokat tennünk a csatlakozás folytonosságához. Tekintsük az a0,a1,a2,a3 és b0,b1,b2,b3 kontrollpontok által meghatározott a ( u) b ( u) u ∈[ 0,1] Bézier-szegmenseket. Ezek minden pontjukban másodrendben folytonosak, a kapcsolódásnál tehát megkövetelhetünk nulladrendű (C0), elsőrendű (C1), illetve másodrendű (C2) folytonosságot. A

nulladrendű folytonossághoz elegendő, hogy az első szegmens végpontja megegyezzen a második szegmens kezdőpontjával, azaz: a(1) = b(0) és mivel ezen görbepontok megegyeznek a megfelelő kontrollpontokkal, hiszen a Bézier-görbe a végpontokat interpolálja, ezért a3 = b0 kell, hogy teljesüljön. d d a (1) = b(0) du du kell, hogy teljesüljön. Ez a kontrollpontokra az (a3 - a2) = (b1 - b0) feltételt jelenti, azaz, amellett, hogy a két szegmens kezdő- és végpontja megegyezik, az a2, a3=b0, b1 pontoknak kollineárisaknak kell lenniük és az a3 pontnak feleznie kell az a2b1 szakaszt. Az elsőrendű folytonossághoz az érintőknek kell megegyezniük, azaz A másodrendben folytonos kapcsolódáshoz a fenti feltételeken kívül a következőnek kell d2 d2 teljesülnie: a( 1 ) = b(0) Ez a kontrollpontokra nézve a következőt jelenti: du 2 du 2 ((a3 - a2) - (a2 - a1)) = ((b2 - b1) - (b1 - b0)) ami geometriai szempontból azt jelenti, hogy az a1a2 egyenes és a b1b2

egyenes m metszéspontjára teljesül, hogy a2 felezi az a1m szakaszt, b1 pedig felezi az mb2 szakaszt. 5.26 Bezier görbe bevezetése másképpen Adottak: p 0 , p 1 , p 2 , p 3 approximálandó pontok a síkban (vagy térben), u ∈ R , 34 t = S& (0) = 3(p1 − p 0 ), t 3 = S& (1) = 3(p 3 − p 2 ) G B = [p 0 p1 p 2 G H = G B ⋅ M HB G H = [p 0 p 3 t0 p3 ] t 3 ] = [p 0 p1 p 2 ⎡1 ⎢0 p3 ] ⋅ ⎢ ⎢0 ⎢ ⎣0 0 −3 0 0 1 3 0 0 0⎤ 0⎥ ⎥ = G B ⋅ M HB − 3⎥ ⎥ 3⎦ A Bezier matrix: M B = M HB ⋅ M H S(u) = G H ⋅ M H ⋅ U = (G B ⋅ M HB ) ⋅ M H ⋅ U = G B ⋅ (M HB ⋅ M H ) ⋅ U = G B ⋅ M B ⋅ U ⎡− 1 3 − 3 ⎢ 3 −6 3 M B = M HB ⋅ M H = ⎢ ⎢− 3 3 0 ⎢ 0 0 ⎣1 1⎤ 0⎥ ⎥ 0⎥ ⎥ 0⎦ S(u) = G B ⋅ M B ⋅ U = (1 − t) 3 ⋅ p 0 + 3t(1 − t) 2 ⋅ p1 + 3t 2 (1 − t) ⋅ p 2 + t 3 ⋅ p 3 35 5.3 3-adfokú B-spline görbe {s3bsplnpas} Kontroll pontok: P0,P1,,Pm-1, Pm m≥3 A létrehozandó ívek: Q3,Q4,,Qm-1,

Qm A t paraméter:Qi ív esetében ti ≤ t ≤ ti+1, ahol 3 ≤ i ≤ m. A Qi ívet meghatározó pontok: Pi-3, Pi-2, ,Pi-1, Pi ,azaz [ ] G Bsi = Pi − 3 Pi − 2 Pi −1 Pi , 3 ≤ i ≤ m Q3 ív esetén: P0, P1, P2, P3 t3=0, t4=1 Q4 ív esetén: P1, P2, P3, P4 t4=1, t5=2 . Qi ív esetén: Pi-3, Pi-2, Pi-1, Pi ti=i-3, ti+1=i-2 . Qm ív esetén: Pm-3, Pm-2, Pm-1, Pm tm=m-3, tm+1=m-2 Az i. szegmens tehát t=t-ti paraméter transzformáció után: Qi (t ) = X 0 (t ) Pi − 3 + X 1 ( u) Pi − 2 + X 2 (u)Pi −1 + X 3 ( u) Pi i = 3,4,., m t ∈[ 0,1] alakú, ahol az Xj(u)-k egyelőre ismeretlen harmadfokú polinomok. Tudjuk azonban, hogy az egymás után következő szegmenseknek másodrendben kell kapcsolódniuk. A nulladrendű kapcsolódás miatt minden i-re teljesülnie kell, hogy Qi(1) = Qi+1(0), amiből: 36 X 0 (1) = X 1 (1) = X 2 (1) = X 3 (1) = X 3 (0) = 0 X 0 (0) X 1 (0) X 2 (0) Ehhez hasonlóan a C1 és C2 folytonossághoz valamennyi i-re teljesülnie

kell, hogy & i (1) = Q & i +1 (0) és Q && i (1) = Q && i +1 (0) , amikből: Q X& 0 (1) = X& (1) = X& 3 (0) = 0 X& (0) X& 2 (1) = X& (1) = X& 1 (0) X& (0) 1 3 0 2 és X&& 0 (1) = X&& (1) = X&& 3 (0) = 0 X&& (0) X&& 2 (1) = X&& (1) = X&& 1 (0) X&& (0) 1 3 0 2 Cauchy-egyenletet, hogy invariáns legyen a koordináta-transzformációra: X 0 (t ) + X 1 (t ) + X 2 (t ) + X 3 (t ) ≡ 1 akkor 16 lineárisan független egyenletet kapunk. Mivel az X j (t ) polinomokat harmadfokúaknak tételezzük fel, ezért összesen 16 ismeretlenünk van, tehát az egyenletrendszer egyértelműen megoldható. Megoldásként a következő polinomokat kapjuk: 1 X 0 (t ) = (1 − t ) 3 6 1 X 1 (t ) = (3t 3 − 6t 2 + 4) 6 1 X 2 (t ) = ( −3t 3 + 3t 2 + 3t + 1) 6 1 X 3 (t ) = t 3 6 3 Qi (t ) = ∑ X r (t )Pi −3+r , t ∈[0,1] i = 3,., m r =0 37 Ugyanez

mátrixos felírásban: T=[t3 t2 t 1]T 38 Qi (t ) = GBs • M Bs • Ti , 0 ≤ t < 1 i M Bs ⎡− 1 3 − 3 ⎢ 1⎢ 3 −6 3 = 3 6 ⎢− 3 0 ⎢ 4 1 ⎣1 BBs = M Bs [ •T = B 1⎡ (1 − t )3 3t 3 − 6t 2 + 4 ⎢ 6⎣ 3⎤ 0⎥ ⎥ 0⎥ ⎥ 0⎦ B Bs − 3 Bs − 2 B B Bs − 1 Bs0 − 3t 3 + 3t 2 + 3t + 1 = T t 3 ⎤ 0 ≤ t < 1. ⎥⎦ 5.4 B-spline görbe általános alakja {sbsplnpas, scoxdebupas} 39 ] T 6. Térbeli ponttranszformációk 6.1 Egybevágósági transzformáció Eltolás d(d x , d y , d z ) vektorral ⎛1 ⎜ 0 M=⎜ ⎜0 ⎜ ⎝0 0 0 dx ⎞ ⎟ 1 0 dy⎟ 0 1 dz ⎟ ⎟ 0 0 1⎠ Elforgatás α szöggel x tengely körül 0 ⎛1 ⎜ 0 cosα M=⎜ ⎜ 0 sin α ⎜ 0 ⎝0 0 − sin α cosα 0 y tengely körül ⎛ cosα ⎜ 0 M=⎜ ⎜ − sin α ⎜ ⎝ 0 0⎞ ⎟ 0⎟ 0⎟ ⎟ 1⎠ z tengely körül 0 sin α 1 0 0 cosα 0 0 0⎞ ⎟ 0⎟ 0⎟ ⎟ 1⎠ ⎛ cosα ⎜ sin α M=⎜ ⎜ 0 ⎜ ⎝ 0 40 − sin α cosα 0 0

0 0 1 0 0⎞ ⎟ 0⎟ 0⎟ ⎟ 1⎠ Tükrözés az {x,y} síkra ⎛1 ⎜ 0 M=⎜ ⎜0 ⎜ ⎝0 0⎞ ⎟ 1 0 0⎟ 0 − 1 0⎟ ⎟ 0 0 1⎠ 0 0 6.2 Hasonlósági transzformációk Kicsinyítés, nagyítás origó középponttal ⎛λ 0 0 ⎜ 0 λ 0 M=⎜ ⎜0 0 λ ⎜ ⎝0 0 0 i 0⎞ ⎟ 0⎟ 0⎟ ⎟ 1⎠ j ` 6.3 Affin transzformációk Skálázás ⎛λ ⎜ 0 M=⎜ ⎜0 ⎜ ⎝0 0 0⎞ ⎟ µ 0 0⎟ 0 ν 0⎟ ⎟ 0 0 1⎠ 0 i 41 j ` 6.4 Nyírás p ′ = p + λ d t = p + ( λn ⋅ p ) t Mátrix reprezentációban: λt x n y λt x nz ⎛ x ′ ⎞ ⎛ 1 + λt x n x ⎜ ⎟ ⎜ λt y nz 1 + λt y n y ⎜ y ′ ⎟ = ⎜ λt y n x ⎜ z ′ ⎟ ⎜ λt z nx λt z n y 1 + λt z nz ⎜ ⎟ ⎜ 0 0 0 ⎝ 1⎠ ⎝ 42 0⎞ ⎛ x ⎞ ⎟ ⎜ ⎟ 0⎟ ⎜ y⎟ ⋅ 0⎟ ⎜ z ⎟ ⎟ ⎜ ⎟ 1⎠ ⎝ 1⎠ 7. Tér síkra való leképezése 7.1 Axonometria Axonometria P (x, y, z) P ′(u, v ): ⎛ u⎞ ⎛ a 11 a 12 ⎜ ⎟ =⎜ ⎝ v ⎠ ⎝ a 21 a 22 ⎛ x⎞ a 13

⎞ ⎜ ⎟ ⎟⋅ y a 23 ⎠ ⎜⎜ ⎟⎟ ⎝ z⎠ Kavalier axonometria: ⎛ x⎞ ⎛ u⎞ ⎛ q ⋅ cos(α ) 1 0⎞ ⎜ ⎟ ⎜ ⎟ =⎜ ⎟⋅ y ⎝ v⎠ ⎝ q ⋅ sin(α ) 0 1⎠ ⎜⎜ ⎟⎟ ⎝ z⎠ q: az x szerinti rovidules α: x tengely y tengellyel bezárt szöge 7.2 Centrális projekció, perspektíva 7.21 Z tengelyen a C nézőpont az Origótól d távolságra y P x Pc y yc P’ Pxc z Pz d C O Pxc C Pxc C y c xc d d = = = ; ; x d − z d − z P ′C P ′C y xc = x ⋅ d ; d− z z yc = y ⋅ 7.22 Általános helyzetű nézőpont (alfa, béta, r, d) 43 d ; zc = 0 d− z 8. Felületek ábrázolása z = f (x, y) függvényfelületek (x, y) ∈[x a , x b ] × [ y a , y b ] r = r (u, v ) paraméteres egyenlettel adott felületek, ahol (u, v) ∈[u a , u b ] × [ v a , v b ] paramétertartomány paramétervonalakkal történő ábrázolás 8.1 Láthatóság szerinti ábrázolás Függvényfelületeknél 1. a hálószemeket balról jobbra, hátulról

előre rajzoljuk ki {zfxypas} 2. 3 1 getmaxx 1 Ymax 3 Ymin 1 Általában A hálószemeket a vetítési irányra rendezzük (párhuzamos vetítésnél) vagy a nézőponttól való távolság szerint rendezzük (centrális projekciónál). 44 9. Felület interpoláció, approximáció 9.1 Bezier felület {bezierfe?pas} Adottak a bij (i=0,,n; j=0,,m) kontrollpontok a térben. n a (u) = ∑ a i ⋅ B ni ( u), i =0 m ahol a i ( v ) = ∑ b i j ⋅ B m j ( v ), j= 0 így a Bezier felület egy (u, v) paraméterű pontjának előáálítása: n ⎛ m n m ⎞ n ⎟ ⋅ = b(u, v ) = ∑ ⎜⎜ ∑ b i j ⋅ B m ( v ) B ( u ) ∑ ∑ b i j ⋅ B mj ( v ) ⋅ B ni (u) j ⎟ i ⎠ i = 0 ⎝ j= 0 i = 0 j= 0 ahol (u, v) ∈[0,1] × [0,1] 45 9.2 B-spline felület 9.21 Általános B-spline felület a ( u) = ∑ a i ( ~ v ) ⋅ N ki (u), i ahol a i ( ~ v ) = ∑ b i j ⋅ N lj ( ~ v ), j így a B - spline felület egy (u, v) paraméterű pontjának előáálítása: ⎛ ⎞ b(u,

v ) = ∑ ⎜⎜ ∑ b i j ⋅ N lj ( v )⎟⎟ ⋅ N ki (u) = ∑ ∑ b i j ⋅ N lj ( v ) ⋅ N ki (u) ⎠ i ⎝ j i j 9.22 Harmadfokú B-spline felület {bspl3fe?pas} Legyenek b i j - k kontrollpontok, ahol i = 0,.,3; j = 0,,3 A harmadfok] B - spline felület egy (u, v) paraméterű pontjának előáálítása: 3 3 b(u, v ) = ∑ ∑ b i j ⋅ X i (u) ⋅ X j ( v ), i =0 j= 0 ahol (u,v) ∈[0,1] × [0,1] 1 X 0 (t ) = (1 − t ) 3 6 1 X 1 (t ) = (3t 3 − 6t 2 + 4) 6 1 X 2 (t ) = ( −3t 3 + 3t 2 + 3t + 1) 6 1 X 3 (t ) = t 3 6 Ha a bij kontrollpontok (i=0,,n; j=0,,m) alakban vannak adva, ahol n>3 ;s m>3, akkor az (n+1) X (m+1) -es kontrollhálóban az összes 4x4 -es kontrollhálószegmensre illeszteni kell egy harmadfokú B-spline felületet, és ezen felületek uniója lesz az (n+1) X (m+1) -es kontrollhálóra illesztett felület. 46 10. Síklapokkal határolt testek ábrázolása 10.1 Testmodellezés 10.11 Drótváz modell {Poliedertnezop emlathato} test.txt V

{csúcsok száma} x0 y0 z 0 xv-1 yv-1 zv-1 E {élek száma} Vs1 Vf1 C1 {csúcs1 index csúcs2 index szín} VsE-1 VfE-1 CE-1 kocka.txt 8 80 80 -80 80 -80 -80 80 -80 80 -80 80 80 -80 80 -80 -80 12 0 1 1 2 2 3 3 0 0 5 5 4 4 7 7 6 6 5 4 3 6 1 7 2 -80 -80 -80 -80 80 80 80 80 14 14 14 14 14 14 14 14 14 14 14 14 Const Vmax=50; Emax=50; Type rpoint3dtype=record x,y,z:real; end; edgetype=record VS,VE:integer; EC:word; end; Verticestype=array[0.Vmax] of rpoint3dtype; Edgestype=array[0.Emax] of edgetype; Var 47 vertices:Verticestype; edges:Edgestype; V,E:integer; procedure Hiba(msg:string); begin writeln(Futási hiba: ,msg); halt; end; procedure Beolvas(s:string); var af:text; i:integer; sz:integer; begin {$I-} assign(af,s);;reset(af); {$I+} if ioresult<>0 then hiba(Nem elérhetô file+s); {csucsok beolvasasa} readln(af,V); for i:=0 to V-1 do readln(af,vertices[i].x,vertices[i]y,vertices[i]z); {elek beolvasasa} readln(af,E); for i:=0 to E-1 do

readln(af,edges[i].VS,edges[i]VE,edges[i]EC); end; 10.12 Felületmodell {Poliedertnezoplathato} test.txt V {csúcsok száma} x0 y0 z 0 xv-1 yv-1 zv-1 F {lapok száma} első lapot alkotó csúcsok indexei utolsó lapot alkotó csúcsok indexei kocka.txt 8 80 80 -80 80 -80 -80 80 -80 80 -80 80 80 -80 80 -80 -80 6 0 1 7 6 0 5 0 3 7 4 1 6 Const Vmax=50; 48 -80 -80 -80 -80 80 80 80 80 2 5 6 4 3 7 3 4 1 5 2 2 0 7 0 0 7 1 Fmax=50; Type rpoint2dtype=record x,y:real; end; rpoint3dtype=record x,y,z:real; end; vertexpointertype=^vertexinfacelist; vertexinfacelist=record FV:integer; n:vertexpointertype; end; facetype=record normal:rpoint3dtype; head:vertexpointertype; end; Verticestype=array[0.Vmax] of rpoint3dtype; Facestype=array[0.Fmax] of facetype; Var vertices:Verticestype; faces:Facestype; V,F:integer; origox,origoy:integer; procedure Hiba(msg:string); begin writeln(Futási hiba: ,msg); halt; end; procedure Beolvas(s:string); var af:text; i,c1,c2,c3,c4:integer; sz:integer;

p,q:vertexpointertype; begin {$I-} assign(af,s);;reset(af); {$I+} if ioresult<>0 then hiba(Nem elérhetô file+s); {csucsok beolvasasa} readln(af,V); for i:=0 to V-1 do readln(af,vertices[i].x,vertices[i]y,vertices[i]z); {lapok beolvasasa} 49 readln(af,F); for i:=0 to F-1 do begin read(af,sz); new(faces[i].head);faces[i]head^FV:=sz; q:=faces[i].head; while not eoln(af) do begin read(af,sz); new(p);p^.FV:=sz; q^.n:=p; q:=p; end; p^.n:=nil; {lapok kifele mutato normalvektorainak kiszamitasa} with faces[i] do lapnormalis(vertices[head^.FV],vertices[head^n^FV],vertices[he ad^.n^n^FV],normal); end; end; 50 11. Láthatóság szerinti ábrázolás 11.1 Hátsó lapok kiszűrése Hátsó lapok kiszűrése a lapok kifelé mutató normálvektorai (n) és a centrumba mutató (c) vektor által bezárt szög alapján: cos(n, c) ⎧ ⎫ ⎪ ⎪ azaz Egy lap hátsó lap, ha 0 ≤ ⎨ ⎬ ≤ 1. ⎪⎩n x ⋅ c x + n y ⋅ c y + n z ⋅ c z ⎪⎭ A konvex poliéderek láthatóság

szerinti megjelenítéséhez elegendő a hátsó lapokat eltávolítani {Poliedertnezoplathatorep3.pas} Ez a technika használható a test laponként egyszínű árnyalására {Poliedertnezoplathatoshade.pas} 11.2 Z Buffer algoritmus 11.3 Sugárkövetés (ray tracing) {POVRAYDOC} 11.31 Algoritmus for minden scan-line-ra a képsíkon do for minden pixelre a scan line-on do begin a centrumból a pixelhez vezető sugár meghatározása; for minden megjelenítendő objektumjára a térrésznek do if van metszéspont és közelebb van, mint az előző then feljegyezni a metszéspontot és az objektumot; a pixel szinét beállítani end; 51 is 11.32 A metszéspontok meghatározása A vetítősugár meghatározása: C(x 0 , y 0 , z 0 ) a vetítési centrum, P (x 1 , y 1 , z1 ) egy pixel közepe. x=x 0 + t(x 1 − x 0 ), y=y 0 + t( y 1 − y 0 ), z=z 0 + t( z1 − z 0 ) ∆x = x 1 − x 0 , ∆y = y 1 − y 0 , ∆ z = z 1 − z 0 x=x 0 + t∆x, y=y 0 + ∆y, z=z 0 + ∆z

Gömb esetében: ( x − a )2 + ( y − b)2 + ( z − c )2 = r 2 , behelyettesítve x, y, és z - t: ( ∆x + ∆y + ∆z )2 t 2 + 2t[ ∆x ( x0 − a ) + ∆y ( y0 − b) + ∆z ( z 0 − c )] + ( x 0 − a )2 + ( y 0 − b )2 + ( z 0 − c )2 − r 2 = 0 A gömb normálisa : P( x , y , z ) - ben: (( x − a) / r + ( y − b) / r + ( z − c) / r ) Poligon esetén: A poligon síkjának egyenlete: t= Ax+By+Cz+D=0 . Behelyettesítés után t-re adódik: Ax0+By0+Cz0+D , hacsak A∆x+B∆y+C∆z ≠ 0 . A∆x+B∆y+C∆z Ekkor levetítjük a poligont a ‘legnagyobb’ képet előállító koordinátasíkra, ahol a metszéspontra elvégezzük a bentvan tesztet. 11.33 Hatékonyságot növelő módszerek: • A metszéspontok kiszámításának optimalizálása A sugarak transzformálása z tengellyel párhuzamos helyzetbe. Határoló objektumok bevezetése (pl konvex poliéderek, párhuzamos egyenespárok által határolt konvex lapokkal) 52 • Hierarhia • Térbeli

szeparálás 53