SZÁMÍTÓGÉPI GRAFIKA GYAKORLAT Összeállította: Várady Lajos
[email protected]
1
TARTALOM
1. HASZNÁLT ADATSZERKEZETEK...................................................................................................................4 2. RASZTERES ALGORITMUSOK ........................................................................................................................5 2.1 SZAKASZ RAJZOLÁSA ..........................................................................................................................................5 2.1.1 Egyszerû növekményes algoritmus .............................................................................................................5 2.1.2 Középpontos vonalalgoritmus ....................................................................................................................6 2.2 SZAKASZ LEHATÁROLÁSA ................................................................................................................................. 10 2.2.1 Cohen-Sutherland algoritmus .................................................................................................................. 10 2.3 POLIGONLEHATÁROLÁS (SUTHERLAND-HODGMAN) ........................................................................................... 12 2.4 KÖZÉPPONTOS KÖRRAJZOLÓ ALGORITMUS ......................................................................................................... 14 2.4.1 Elmélet .................................................................................................................................................... 14 2.4.2 Program {smidpcir.pas}........................................................................................................................... 15 2.5 KÖR KITÖLTÉSE {SFILLCIR.PAS} ........................................................................................................................ 17 2.6 TÉGLALAP KITÖLTÉSE {SFILLREC.PAS} .............................................................................................................. 17 2.7 REKURZÍV KITÖLTÉS {SFLOODFI.PAS} ................................................................................................................ 17 2.8 ÁLTALÁNOS POLIGON KITÖLTÉSE ...................................................................................................................... 18 2.8.1 Algoritmus ............................................................................................................................................... 19 2.8.2 Kitöltés mintával...................................................................................................................................... 21 3. SÍKBELI TRANSZFORMÁCIÓK {SLABDA?.PAS}........................................................................................ 23 3.1 WINDOW TO VIEWPORT TRANSZFORMÁCIÓ {SWINVIEW.PAS}.............................................................................. 23 4. KONVEX BUROK ALGORITMUSOK............................................................................................................. 25 4.1 GRAHAM PÁSZTÁZÁS (SÍKBAN) {SHULLGRH.PAS} ............................................................................................ 25 5. INTERPOLÁCIÓ, APPROXIMÁCIÓ................................................................................................................ 28 5.1 HERMITE-ÍV ..................................................................................................................................................... 28 5.1.1 Elsõ eset .................................................................................................................................................. 28 5.1.2 Második eset {shermit.pas} ...................................................................................................................... 30 5.1.3 Kezdeti érintõ meghatározása .................................................................................................................. 32 5.2 BEZIER GÖRBE .................................................................................................................................................. 32 5.2.1 de Casteljau algoritmus { sdecast.pas }.................................................................................................... 32 5.2.2 A görbe elõállítása Bernstein polinommal {sbezier.pas} .......................................................................... 33 5.2.3 Bezier görbe tulajdonságai ...................................................................................................................... 33 5.2.4 Interpoláció Bézier-görbével.................................................................................................................... 33 5.2.5 Kapcsolódó Bezier görbék ....................................................................................................................... 34 5.2.6 Bezier görbe bevezetése másképpen ......................................................................................................... 34 5.3 3-ADFOKÚ B-SPLINE GÖRBE {S3BSPLN.PAS} ....................................................................................................... 36 5.4 B-SPLINE GÖRBE ÁLTALÁNOS ALAKJA {SBSPLN.PAS, SCOXDEBU.PAS} .................................................................. 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
2
7.2 CENTRÁLIS PROJEKCIÓ, PERSPEKTÍVA ................................................................................................................ 43 7.2.1 Z tengelyen a C nézõpont az Origótól d távolságra .................................................................................. 43 7.2.2 Általános helyzetû nézõpont (alfa, béta, r, d)............................................................................................ 44 8. FELÜLETEK ÁBRÁZOLÁSA ........................................................................................................................... 45 8.1 LÁTHATÓSÁG SZERINTI ÁBRÁZOLÁS .................................................................................................................. 45 9. FELÜLET INTERPOLÁCIÓ, APPROXIMÁCIÓ............................................................................................. 46 9.1 BEZIER FELÜLET {BEZIERFE?.PAS}..................................................................................................................... 46 9.2 B-SPLINE FELÜLET ............................................................................................................................................ 47 9.2.1 Általános B-spline felület......................................................................................................................... 47 9.2.2 Harmadfokú B-spline felület {bspl3fe?.pas}............................................................................................. 47 10. SÍKLAPOKKAL HATÁROLT TESTEK ÁBRÁZOLÁSA ............................................................................. 48 10.1 TESTMODELLEZÉS .......................................................................................................................................... 48 10.1.1 Drótváz modell {\Polieder\Ztnezop\nemlathato\…} ................................................................................ 48 10.1.2 Felületmodell {\Polieder\Ztnezop\lathato\…}......................................................................................... 49 11. LÁTHATÓSÁG SZERINTI ÁBRÁZOLÁS ..................................................................................................... 52 11.1 HÁTSÓ LAPOK KISZÛRÉSE ................................................................................................................................ 52 11.2 Z BUFFER ALGORITMUS .................................................................................................................................. 52 11.3 SUGÁRKÖVETÉS (RAY TRACING) {POVRAY.DOC}......................................................................................... 52 11.3.1 Algoritmus ............................................................................................................................................. 52 11.3.2 A metszéspontok meghatározása. ........................................................................................................... 53 11.3.3 Hatékonyságot növelõ módszerek:.......................................................................................................... 53
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.1.1 Egyszerû növekményes algoritmus ∆y y 2 − y1 = ∆x x 2 − x1 y = m⋅ x + B yi +1 = m ⋅ xi +1 + B
m=
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.1.2 Középpontos vonalalgoritmus 2.1.2.1 Elmélet
∆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
m=
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 +
b ∆x = ∆y − . 2 2
A törtek elkerüléséhez szorozzuk meg az F függvény értékét 2-vel. 2.1.2.2 Algoritmus {smidplin.pas}
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); 3: begin transzXYt(x,y);transzYt(x,y);end; 8
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; end;
9
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.2.1 Cohen-Sutherland algoritmus 2.2.1.1 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 I V kódbeli egyenes
Yes
Kód (V ) ≠ ∅ No
K,V szakasz kirajzolása
Stop
2.2.1.2 Program {scohsuth.pas}
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
jfx then c:=[jobb]; if yjfy 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.4.1 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) = x2 + y 2 − R2
14
F(x,y)>0 P=(x p, y p ) R
E M
F(x,y)<0
SE
F(x,y)=0
M M
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 1 d p + 2 = F x p + 2, y p − = x p + 2 2 ∆E = d p + 2 − d p + 1 = 2 ⋅ x p + 3
(
)
2
2
1 + y p − − R2 2
b) SE-t választottuk az x p+1 pontban 2
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 + R2 − R + − R2 = − R. 2 4 4 2.4.2 Program {smidpcir.pas} 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 {sfillcir.pas} (-x,y) (-y,x)
R R , 2 2
(x,y)
(y,x)
R
(y,-x)
(-y,-x) (-x,-y)
(x,-y)
2.6 Téglalap kitöltése {sfillrec.pas} 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 {sfloodfi.pas} 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õ pixel
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 3.2 beli pontok közös él esetén? 3.4 Hogyan kezelhetõek a 3.2 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.8.1 Algoritmus Az ET (él tábla) lista: EF
nil
7
9
7
DE -5/2
11
7
6/4
nil
CD 5
11
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.8.2 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 Use these constants as fill patterns for GetFillSettings 21
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 \thick 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ó {swinview.pas}
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) {shullgrh.pas} 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 p1 ,..., 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 p1 ,..., 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 − z a ⋅ y b , z a ⋅ x b − x a ⋅ zb , x a ⋅ yb − 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.
yj − y0 , ha x j ≥ x 0 arcsin 2 2 x j − x 0 + y j − y0 polárszög = yj − y0 Π − arcsin , egyébként 2 2 x j − x 0 + y j − y0
(
) (
(
)
) (
)
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.1.1 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 0 u3 + 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) = t0 S& (1) = t1 Az egyenletrendszer megoldása:
28
S(0) = p 0 = a 3 S(1) = p 1 = a 0 + a 1 + a 2 + a 3 S& (0) = t 0 = a 2 S& (1) = t1 = 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 ⋅ a1 + t 0 −−−−−−−−−−−−−−−− t 1 = 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 ⋅ p 1 + t 0 + t1 ====================== 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 S(u) = = G H • M H • U = [p 0 ,p1 , t0 , t1 ] • M H • → M H = ? u y( u) 1 0 1 0 1 S(0) = p 0 = GH • M H • S(1) = p1 = G H • M H • 0 1 1 1 3 0 &S(0) = t 0 = G H • M H • 0 S& (1) = t1 = GH • M H • 2 1 1 0 0 0 0 = = • • p p t t G G M [ 0 1 0 1 ] H H H 0 1
1 1 1 1
0 0 1 0
3 0 0 2 ⇒ MH = 0 1 0 1
2 −3 − 2 3 x( u ) S(u) = = G • M • U = [ p , p , t , t ] • H H 0 1 0 1 1 −2 y( u) 1 −1
1 1 1 1
0 0 1 0
3 2 1 0
−1
0 1 u 3 0 0 u 2 • 1 0 u 0 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 u 2
1 p0 2 −2 1 − 3 3 − 2 − 1 p1 u 1) 0 0 1 0 t0 0 0 0 t1 1
5.1.2 Második eset {shermit.pas} 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 0 u3 + 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) = p1 S(1) = p 2 S& ( −1) = t1 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 = 3 ⋅ a − 2 ⋅ a + a 0
0
1
2
−−−−−−−−−−−−−−−− p 0 − p1 = − a 0 + a 1 − a 2 t0 = 3 ⋅ a 0 − 2 ⋅ a1 + a 2 p 2 − p1 = a 0 + a 1 + a 2 −−−−−−−−−−−−−−−− 3 ⋅ p 0 − 4 ⋅ p1 + p 2 + 2 ⋅ t 0 4 − 5 ⋅ p 0 + 4 ⋅ p1 + p 2 − 2 ⋅ t 0 3 ⋅ p 0 − 3 ⋅ p1 + t 0 = a1 − 2 ⋅ a 2 → a 2 = 4 p 0 + p 2 − 2 ⋅ p1 p 0 + p 2 − 2 ⋅ p1 = → a1 = 2 ⋅ a1 2 =====================
p 0 − p1
= −a 0 + a1 − a 2 → a 0 =
A megoldások behelyettesítése: 3p − 4p1 + p 2 + 2 t 0 3 p 0 − 2p1 + p 2 2 − 5p 0 + 4p1 + p 2 − 2 t 0 S(u) = 0 u + p1 u + u + 2 4 4 4 3p − 4p1 + p 2 + 2 t 0 3 2p 0 − 4p1 + 2p 2 2 − 5p 0 + 4p1 + p 2 − 2 t 0 S(u) = 0 u + p1 u + u + 4 4 4 4 u 3 2 x( u ) u S(u) = = G H • M H • U = [p 0 , p1 , p 2 , t 0 ] • M H • → M H = ? u y ( u) 1 − 1 0 1 0 S( −1) = p0 = 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 = GH • M H • 1 1 1 0 − 1 1 p p t G G M p = = • • [ 0 1 2 0 ] H H H − 1 1
3 − 1 1 0 1 −2 ⇒ MH = − 1 0 1 1 1 1 0 1 0 1
31
0 0 0 1
1 3 1 − 2 1 1 1 0
−1
1 5 3 0 3 − 4 u 2 4 − 1 − 1 1 1 2 x( u ) • u 1 1 S(u) = = G H • M H • U = [p 0 ,p1 , p2 , t 0 ] • 1 0 u y( u) 2 4 4 1 1 0 1 0 − 2 2 5.1.3 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.2.1 de Casteljau algoritmus { sdecast.pas } 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
p1 0
p
p2
p3 0
0
0
32
3
5.2.2 A görbe elõállítása Bernstein polinommal {sbezier.pas} 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.2.3 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(0) = n(p1 − p 0 ) p(1) = n(p n − p n −1 ) 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.2.4 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.2.5 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) kell, du du 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.2.6 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 ), t3 = S& (1) = 3(p 3 − p 2 ) GB = [p0 p1 p 2 p 3 ] GH = G B ⋅ M HB G H = [p 0 p 3
t0
t 3 ] = [p 0 p1 p2
1 0 p3 ] ⋅ 0 0
0 −3 0 0 3 0 = G B ⋅ M HB 0 0 − 3 1 0 3
A Bezier matrix: M B = M HB ⋅ M H S(u) = G H ⋅ M H ⋅ U = (G B ⋅ M HB ) ⋅ M H ⋅ U = GB ⋅ (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 ⋅ p0 + 3t(1 − t) 2 ⋅ p1 + 3t2 (1 − t) ⋅ p2 + t3 ⋅ p3
35
5.3 3-adfokú B-spline görbe {s3bspln.pas} 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 3 (0) = 0 X 1 (1) = X 0 (0) X 2 (1) = X 1 (0) X 3 (1) = 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 X1 (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 , r =0
t ∈[0,1] i = 3,..., m
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
3 0 0 0
[
BBs = M • T = B B B B Bs Bs − 3 Bs − 2 Bs − 1 Bs0 1 (1 − t )3 3t 3 − 6t 2 + 4 6
− 3t 3 + 3t 2 + 3t + 1
=
T 3 0 ≤ t < 1. t
5.4 B-spline görbe általános alakja {sbspln.pas, scoxdebu.pas}
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 0 0 1 0 0 1
Tükrözés az {x,y} síkra 1 0 M= 0 0
0 0 0 − 1 0 0 0 1
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
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 µ
j `
41
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 nx 1 + λt y n y λt y nz y ′ = λ t y nx z ′ λt z n x λ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.2.1 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 P c C Pxc C y c xc d d = ; = x ; = x d − z d − z P ′C P ′C y
xc = x ⋅
d ; d−z
z
yc = y ⋅
43
d ; zc = 0 d−z
7.2.2 Általános helyzetû nézõpont (alfa, béta, r, d)
44
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 {zfxy.pas} 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).
45
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 ) = j ∑ ∑ b i j ⋅ B mj ( v ) ⋅ B ni (u) i i = 0 j= 0 i = 0 j= 0
ahol (u, v) ∈[0,1] × [0,1]
46
9.2 B-spline felület 9.2.1 Á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.2.2 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 X1 (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.
47
10. Síklapokkal határolt testek ábrázolása 10.1 Testmodellezés 10.1.1 Drótváz modell {\Polieder\Ztnezop\nemlathato\…} test.txt V {csúcsok száma} x0 y0 z0 … 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
48
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.1.2 Felületmodell {\Polieder\Ztnezop\lathato\…} test.txt V {csúcsok száma} x0 y0 z0 … 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; 49
-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}
50
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;
51
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 {\Polieder\Ztnezop\lathato\brep3.pas}. Ez
a
technika
használható
a
test
laponként
egyszínû
árnyalására
{\Polieder\Ztnezop\lathato\shade.pas}.
11.2 Z Buffer algoritmus 11.3 Sugárkövetés (ray tracing) {POVRAY.DOC} 11.3.1 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;
52
is
11.3.2 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 = z1 − 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 ( y 0 − b) + ∆z ( z0 − 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:
Ax 0+By 0+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.3.3 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)
53
•
Hierarhia
•
Térbeli szeparálás
54
