| 2005 tavaszi félév tételsora | 1. Grafikus output eszközök. A raszteres display m ködési elve. ............................... 2 2. Grafikus szabványok. SRGP standard. ................................................................... 2 3. Szakasz rajzolása. DDA, szimmetrikus DDA, inkrementális módszer...................... 4 4. Kör rajzolása inkrementális módszerrel .................................................................... 6 5. Szakasz vágása téglalap tartományra, Cohen Sutherland vágóalgoritmus.............. 8 6. Szakasz vágása konkáv poligonnal. ........................................................................ 9 7. Poligon vágása téglalap tartományra. ...................................................................... 9 8. Kitöltés. Scan-konverzió. ....................................................................................... 10 9. Él flag módszer. Rekurzív módszer. Kitöltés mintával. .......................................... 13 10. Antialiasing. ............................................................................................................ 14 11. Harmadrend paraméteres görbék mátrix-reprezentációja. .................................. 14 12. Hermite görbék. ..................................................................................................... 15 13. Harmadrend Bezier görbék. Harmadrend Bezier görbék csatolása. ................. 17 14. Bezier görbék el állítása Bernstein polinomokkal. De Casteljou algoritmus. ........ 18 15. Harmadrend B-spline görbe el állítása. ............................................................... 19 16. Kétdimenziós transzformációk. .............................................................................. 23 17. Window to viewport transzformáció. ...................................................................... 25 18. Térbeli pont transzformációk. Koordináta transzformációk. ................................... 26 19. Centrális vetítés. .................................................................................................... 29 20. Párhuzamos vetítés. Axonometria. ........................................................................ 30 21. 3D vágás. Kanonikus transzformáció. Vágás téglatestre, csonka gúlára. ............. 32 22. Felületmodellezés. Felületeket leíró adatstruktúrák. .............................................. 34 23. Regularizált halmazm veletek. Definiálás görbesereggel. .................................... 35 24. Drótváz modell. Felület modell. (B-rep). Euler formula. ......................................... 36 25. Cellamódszerek. Térfogat modell. (CSG). ............................................................. 37 26. Kétváltozós skalár vektor függvény (felület) paramétervonalas ábrázolása. .......... 27. Coons foltok, bikubikus felületek. ........................................................................... 39 28. Láthatósági algoritmusok hatékonyságát növel módszerek. ............................... 43 29. Robert, Appel, haloid módszer. .............................................................................. 46 30. Mélység rendezés (fest algoritmus). BSP algoritmus. ......................................... 47 31. Z-puffer algoritmus. ................................................................................................ 49 32. Scan-line algoritmus. ............................................................................................. 49 33. Terület-felosztásos algoritmus. (Warnock). ........................................................... 50 34. Sugárkövetés (Ray tracing). .................................................................................. 51 35. Színelméleti ismeretek. .......................................................................................... 53 36. Megvilágítási modellek, árnyalás. ........................................................................... 54 Felhasznált irodalom és javasolt irodalom .................................................................... 55
By Szendwich
1. Grafikus output eszközök
A raszteres display m ködési elve
Grafikus output eszközök A monitorok m ködési elv szerint lehetnek: raszteres vonalrajzoló monitorok. A monitorok által alkotott kép min séget meghatározó legfontosabb m szaki paraméterek a következ k: a felbontás megadja a raszteres képen megjeleníthet pixelek számat. Pl.: 800*600, 1024*768, 1280*1024, stb. +képátmér pl.: 14, 17, 21 inch, stb. kép-pontátmér : a képerny n beszínezhet pixelek nagyságát adja meg. a videosáv-szélesség az elektronika állapotváltozásainak maximális számát adja meg másodpercenként, és így meghatározza a másodpercenként kirajzolható pixelek számát is. a képfrissítési frekvencia megadja a másodpercenként kirajzolt teljes képerny k számát. képkirajzolási üzemmód szerint interlace vagy noninterlace. Az el bbi frissítési lépésenként a pixelsorok közül egyszerre csak a páros majd a páratlan sorokat rajzolja ki, az utóbbi folyamatosan rajzolja ki a sorokat. A raszteres display m ködési elve Más néven katódsugárcsöves képerny . Ebben a képerny bels oldalán van egy foszforréteg, amit a megfelel helyen elektronágyú megl , és az ott felvillanó fényfolt lesz a pixel. rajzgépek
analóg
digitális elektrosztatikus
digitális
inkrementális
dobos
digitális-analóg
egyéb
síkrajzgép
2. Grafikus szabványok - SRGP standard Grafikus szabványok 3D Core Graphics System (1977) ANSI-American National Standards Institute ISO-International Standards Organization GKS: Graphical Kernel System -2D az els hivatalos grafikai szabvány (1985) GKS 3D kiterjesztése (1988) PHIGS Programmer's Hierarchical Interactive Graphic System (ANSI sz. 1988) PHIGS PLUS (ANSI/ISO 1992) SRGP Simple Raster Graphics
-2-
Rasztergrafikus szabvány (SRGP) Ezt a szabványt egyszer raszter-grafikus programcsomagnak, vagy az angol megnevezése után rövidítve SRGP-nek (Simple Raster Graphic Package) nevezik. Az SRGP tulajdonképpen a legalapvet bb raszter-grafikus funkciókra, megvalósító programegységekre vonatkozó szabvány. Az SRGP legfontosabb alkotóelemei a raszter-grafikus primitívek, melyek vonalak, ellipszisek, sokszögek és szövegek lehetnek. A primitívek tulajdonképpen képelem generátorok, melyeket felhasználásukkor kell felparaméterezni (például kör esetén a középpont és sugár megadásával). Az SRGP egyes program-realizációi a szokásos raszter-grafikus funkcionalitást biztosítják. Ezek a: Grafikákhoz o szín, o vonalvastagság, o vonalstílus, o kitölt szín és textúra rendelhet , lehet ség van bittérképes bet formák kezelésére, logikai eszköz- és eseménykezelés biztosított, a képerny kezelés ismeri a vásznakat, a háttérszínt, a kivágó téglalapot, a raszter-grafikus objektumok között megengedettek a logikai raszterm veletek. A raszter grafika néhány jellemz je A képpontokból (pixelekb l) felépül képet raszteres képnek, ezek számítógépes feldolgozását pedig raszter-grafikának nevezzük. A pixel a kép elemi, tovább fel nem bontható részét jelenti. A megjeleníthet színek mennyisége alapján 4 fajta raszteres kép típust különböztethetünk meg: bittérképes képek, szürke árnyalatú képek, színpalettávál indexelt képek, valódi színezet képek. Bittérképes kép esetén minden egyes képponthoz tartozó színinformációt egy biten (1=fekete, 0=feher) kódoljuk, így ezek a képek fekete fehérek. Szürke árnyalatú kép képpontonként 8 biten kódolva 256-féle fekete fehér átmeneti színt tartalmazhat. Színpalettával indexelt képek pixeljeihez egy színindex értéket rendelünk hozzá, mely egy 256 elem színtáblázatra hivatkozik, melyet palettának nevezünk. A színpaletta minden 8 bites indexe egy konkrét színárnyalatot határoz meg egy pixel számára. A valódi színezet képek esetében a színtér alapszíneinek megfelel színcsatornánként adjuk meg az alapszínek intenzitását. Ez RGB vagy CMYK. Az RGB színtér eseten 3*8=24 bit, a CMYK színtér esetén pedig 4*8=32 bit megadását jelenti. A raszteres képfájlok a számítógép tárolóeszközein általában a következ részekb l épülnek fel: a fejlécb l, mely megadja a kép formátumát, méretét pixelekben, és az adatrészb l, mely pixelenként tartalmazza a színkódokat. Ebb l következik, hogy a raszteres kép csak teljes egészében kereshet vissza és csak felülírással módosítható. Vagyis a raszteres képen lév elkülönült grafikus objektumokat egyedileg nem tudjuk visszakeresni.
-3-
3. Szakasz rajzolása. DDA, szimmetrikus DDA, inkrementális módszer Szimmetrikus DDA Az egyenes r(t) = r0 + tv skalár vektor el állításán alapszik. A szakaszt meghatározó A(x1, y1) és B(x1, y2) pontokból képezzük a x = x2 x1 és y =y2 y1 különbségeket. Meghatározásra kerül az = 2-n érték, ahol 2n 1 max(| x|, | y|) < 2n és egy x és y változó tartalmát növeljük az x és y értékekkel. Az egész túlcsordulásoknál megjelenítse kerül a pont.
Ideális növekményes módszer egyenes generálásra
Szimmetrikus DDA-val rajzolt egyenes
A szimmetrikus DDA elrendezése
Egyszer DDA Ekkor az x vagy y irányban egyesével kell lépkedni, azaz a
x = 1 vagy
y = 1.
Midpoint algoritmus Bárhogyan is származtassuk az egyenest, az egyenlete a x + b y + c = 0 alakra hozható, ahol a és b egyszerre nem lehet nulla.
Legyenek az egyenest meghatározó pontok P1(x1, y1) és P2(x2, y2). Az algoritmus ismertetetéséhez tegyük fel, hogy a meredekség 0 m 1. Az egyenest balról jobbra haladva rajzoljuk ki. A kitöltött körök a megvilágított pixeleket jelentik.
-4-
Legyen az éppen megjelenített pont P(xp, yp), ekkor a következ megrajzolandó raszterpont az E (East) és az NE (North East) pontok valamelyike lehet. Közülük azt a pontot kell kigyújtani, amelyik közelebb van az elméleti egyeneshez. A választás a két rácspont között elhelyezked felez pont (M) segítségével történik. Ha az egyenes az M pont felett halad el, akkor az NE pontot jelenítjük meg, különben pedig az E-t. Az M pont helyzetét analitikusan határozzuk meg. Az egyenes egyenletét az F(x, y)=a x + b y + c = 0 formában tekintjük, ahol a = (y2 - y1), b = -( x2 - x1), és c = (y2 - y1) x1 - ( x2 - x1) y1. Feltehetjük, hogy b pozitív, különben a pontokat felcseréljük, ezért F(x, y) > 0, ha az (x, y) pont az egyenes felett helyezkedik el, illetve F(x, y) < 0, ha az egyenes alatt. Jelöljük az M-hez tartozó függvényértéket d-vel: 1 1 d = F(M) = F(xp +1, yp + ) = a(xp +1) + b(yp + ) + c. 2 2 Ha d < 0, akkor NE-t választjuk. Ha d > 0, akkor E-t. Ha d = 0, akkor választhatjuk bármelyiket, de megegyezés szerint E-t választjuk. Ezután d új értékét a régi értékéb l számoljuk ki. Jelölje ezt dold, az új érteket dnew. Ekkor a dnew függ az új pont meg választásától. Ha az E pontot választjuk, akkor 1 1 dnew = F(ME) = F(xp +2, yp + ) = a(xp + 2) + b(yp + ) + c= dold + a 2 2 azaz ekkor d-t E = dnew - dold = a -val kell növelni. Ha az NE pontot választjuk, akkor 3 3 dnew = F(MNE) = F(xp + 2, yp + ) = a(xp + 2) + b(yp + ) + c = dold + a + b 2 2 Ekkor d-t NE = dnew - dold = a + b -vel növeljük. Most már ha ismerjük xp, yp és d aktuális értékét, akkor tovább tudunk lépni, meg tudjuk határozni az újabb értékeket. Az elinduláshoz meg kell határoznunk a kezdeti értékeket. Az els kirajzolandó pont a P1 (x1, y1), azaz (x0, y0) (x1,y1), ekkor a d kezd értéke: 1 b b d0 = F (x1 + 1, y1 + ) = a x1 + b y1 + c + = F (x1, y1) + a + , 2 2 2 de a P1 (x1,y1) pont rajta van az egyenesen, így d0= a+b/2. Ahhoz, hogy a kett vel való osztást elkerüljük definiáljuk át az F(x, y) függvényt: F(x, y)=2 (a x + b y + c). Ezt megtehetjük, mert csak a d el jelére van szükség és a 2-vel való szorzás ezt nem változtatja meg.
-5-
Ekkor d0 = 2 a + b E = 2 a NE = 2 (a+b) egyenleteket kapjuk, minden más változatlan. Az iterációs lépést addig kell ismételni, amíg az utolsó pontot is ki nem rajzoljuk. 4. Kör rajzolása inkrementális módszerrel Kör scan-konverziója A kör azon pontok halmaza a síkban, amelyek egy adott, a síkra illeszked C ponttól egyenl (r > 0) távolságra vannak. A C pontot a kör középpontjának, az r távolságot a kör sugarának nevezzük. Egy pontot a kör bels (illetve küls ) pontjának nevezünk, ha a pont távolsága a kör középpontjától kisebb (illetve nagyobb) a kör sugaránál.
Ha rögzítünk egy [x, y] koordináta-rendszert, akkor az origó középpontú, r sugarú kör egyenlete: x2 + y2 = r2. Ebb l pedig könnyen levezethet az (u, v) középpontú, r sugarú kör egyenlete: (x - u)2 + (y - v)2 = r2. Az egyenletekben xy-os tag nem szerepel, és a négyzetes tagok együtthatója megegyezik. Az utóbbi egyenletet átrendezve a következ összefüggést kapjuk: F(x, y) = (x - u)2 + (y - v)2 - r2 = 0. Az F(x, y) függvénybe a körre illeszked pontok koordinátáit helyettesítve nulla értéket kapunk. Az (x1, y1) pont akkor és csak akkor bels pont, ha F(x1, y1)<0 és a (x2, y2) pont akkor és csakis akkor küls pont, ha F(x2, y2)>0. Nyolcas szimmetria elve Tekintsünk egy origó középpontú kört. Ha egy (x, y) pont rajta van a körön, akkor könnyen meghatározhatunk három másik pontot, ami szintén rajta van a körön.
-6-
Ezért ha meghatározzuk a kör egy megfelel nyolcadának pontjait (pl. az ábrán satírozott részhez tartozó körív pontjait), akkor tulajdonképpen a teljes kört is meghatároztuk. Ezt kihasználva az algoritmus gyorsítható. Egyedüli feltétel az, hogy a kör középpontja az origóba essen. Ha egy nem origó középpontú kört akarunk rajzolni (az esetek többségében ez teljesül), akkor koordináta transzformációt alkalmazunk. A koordináta-rendszer origóját a kör (u, v) középpontjába visszük. Vagyis a kör pontjait úgy határozzuk meg, mintha a középpontja az origóban lenne, de kirajzolás el tt a pontokat az (u, v) vektorral eltoljuk, s így a kívánt helyzet kört kapjuk. Els rend differenciák módszere Az elmondottak alapján a midpoint algoritmus origó középpontú kört feltételez, és csak a kitüntetett nyolcad körív pontjait határozza meg.
Legyen az aktuális kivilágított pixel P(xp, yp), az elméleti körhöz legközelebb es pont. A módszer ugyanaz, mint a vonalrajzoló algoritmus esetében: a következ pixelt két pont (E, SE) közül kell kiválasztani. A kiszámolt körív minden pontjában a kör érint jének meredeksége -1 és 0 között van. Ezáltal a következ kirajzolandó pont az (xp + 1, yp), vagy az (xp + 1, yp - 1) lehet. Jelöljük az E, SE pontok által meghatározott szakasz felez pontját M-mel. Ha a körív az M pont felett halad el, akkor (a körív megválasztása miatt) az M a kör bels pontja, azaz F(M) < 0. Megmutatható, hogy ebben az esetben az E pont van közelebb a körhöz, így ekkor E-t választjuk, különben az SE pont van közelebb a körhöz és SE-t választjuk. Jelöljük d-vel az F(M) értékét: 1 1 d = dold = F(M) = F(xp + 1, yp - ) = (xp + 1)2 + (yp - )2 - r2 2 2 Ha d < 0, akkor az E-t választjuk, és ekkor 1 1 dnew = F(ME) = F (xp + 2, yp - ) = (xp + 2)2 + (yp - )2 - r2 = dold + (2 xp + 3) 2 2 lesz a d új értéke, vagyis E = dnew - dold = 2 xp + 3. Ha d
0, akkor az SE-t választjuk, és ekkor 3 3 2 2 dnew = F(MSE) = F(xp + 2, yp - ) = (xp + 2)2+(yp ) - r = dold + (2 (xp - yp) + 5) 2 2
vagyis SE
= 2(xp - yp)+5. -7-
Vegyük észre, hogy míg az egyenes rajzolásánál a E, SE els rend differenciák konstans értékek voltak, most a E és SE az xp, yp lineáris függvénye. Ez azt jelenti, hogy minden egyes lépésben a E és SE értékeket (még az aktuális pont koordinátái alapján) újra kell számolni. El ször meg kell határoznunk a kezdeti értékeket. Az algoritmus a (0,r) pontból indul, így 1 5 d0 = F(1, r - ) = -r. 2 4 Látható, hogy ekkor d0 nem egész. Ahhoz, hogy egészekkel tudjunk számolni d 1 helyett, tekintsük a d = d változót. Így d 0 = 1 - r. Ekkor a d < 0 feltétel helyett 4 1 d < - feltételt kell vizsgálni, viszont ez is valós aritmetikát feltételez. Mivel d 0, E és 4 SE is egészek d' mindig egész lesz, így egyszer en tekinthetjük a d < 0 feltételt. 5. Szakasz vágása téglalap tartományra, Cohen Sutherland vágóalgoritmus A leghatékonyabb vágóalgoritmus. Ez a síkot 9 részre osztja. A középs 9-ed a képerny (ablak). Egy négyjegy bináris kód minden ponthoz hozzárendelhet . 1001
1000
1010
0001
0000
0010
0101
0100
0110
A nulladik bit egyes, ha a pont balra esik a baloldali képerny élt l. Az els bit egyes, ha a pont jobbra esik a baloldali képerny élt l. A második bit egyes, ha a pont alá esik a baloldali képerny élt l. A harmadik bit egyes, ha a pont felé esik a baloldali képerny élt l. Ha a szakasz 2 végpontjához rendelt kód csupa nulla, akkor a szakasz a képerny n belül van. Ha a szakasz két végpontja közül valamelyik kódjában van egyes, akkor az egyes helyi értékének megfelel képerny éllel el kell metszeni a szakaszt, és a metszéspontra módosítani a szakasz végpontját, és az új kódot újból meg kell vizsgálni. Ezt addig folytatjuk, amíg a szakasz végpontjaihoz rendelt kódok csupa nullák nem lesznek. Ha egy szakasznak van olyan bitje, hogy mind a két végponthoz rendelt kódon egyes van, akkor az a szakasz eldobható, mert a képen kívülre esik. El nyei: hatékony, ha nagy valószín séggel kívül esnek a szakaszok a képerny n; jól általánosítható 3D-ben, itt 6 bitesek a kódok. Hátránya az, hogy a poligon ablakra nem általánosítható.
-8-
6. Szakasz vágása konkáv poligonnal Behelyettesítjük a poligont alkotó csúcsok koordinátáit a vágandó szakasz egyenesének egyenletébe. A kapott értékek el jeleit figyelve az el jelváltások esetén az aktuális poligon él metszi a szakasz egyenesét. Kiszámoljuk a szakasz egyenesének és a poligonnak a metszéspontjait, és ezeket x (vagy y) koordináta szerint rendezzük. Majd beszúrjuk a szakasz két végpontját a rendezett sorba, és megnézzük, hogy hol van a két végpont a metszéspontokhoz képest. A szakasz egyik végpontjától számítva a páratlan és páros metszéspontok közötti szakaszokat kell rajzolni, a két végpont között. Ha az egyenes párhuzamos az y tengellyel, akkor y szerint kell rendeznünk.
7. Poligon vágása téglalap tartományra
Sudherland-Hodgman poligon vágó algoritmus téglalap alakú ablakra Nem elég csak a poligon éleit vágni, mert úgy csak az élek egy halmazát kapjuk meg, ami nem poligon. Az ablak négy élével egymás után elvágjuk az alakzatot. Minden ablak élre vonatkozóan egymásután létrehozunk az eredeti éleket sorba véve egy új listát. A poligon minden AB (irányított) élére vonatkozóan az alábbi esetek lehetségesek: 1. Minkét csúcs kívül van: nincs output 2. Mindkét csúcs benn van: B csúcs felkerül a listára (Ha nem az els élr l van szó, A már rajta volt) 3. A bent van, B kinn: Az ablak él és AB metszéspontja felkerül a listára 4. B benn van, A kinn: el ször AB és az ablak él metszéspontja, majd B is felkerül a listára. Konkáv alakzat esetén az is el fordulhat, hogy több poligon lesz a vágás végeredménye.
-9-
1
2
kinn
benn
3 kinn
benn
A
4 kinn
A
benn A
kinn A
B B
benn
B
B
Eredmény
Vágandó alakzat
Vágás az egymás utáni élekre
8. Kitöltés - Scan-konverzió Általános módszer ebben az esetben is az él-flag módszer. A legdélibb és legészakibb csúcsok között indított minden vízszintes scan-line-ra az alábbi lépéseket tesszük: 1. A scan-line metszéspontjainak meghatározása a poligon minden élével. 2. A metszéspontok rendezése x koordináta szerint. 3. Egy paritás bitet használva azon pixelek kitöltése a metszéspontok között, melyek a poligon belsejében fekszenek A poligon csúcsai meg vannak adva egész koordinátákkal. A feladat itt is a bels pixelek meghatározása. A poligon éleit pl. a middlepoint algoritmussal meg lehet határozni. Kérdés, hogy az egyenes rajzoló által generált pixelek közül melyeket tekintsük bels és melyeket küls pixeleknek. Erre az a megoldás, hogy megkülönböztetünk úgynevezett baloldali és jobb oldali éleket, aszerint hogy páratlanadik vagy párosadik metszéspontról van szó. Baloldali él esetén felfelé, jobb oldali él esetén lefelé kerekítünk.. Azaz kerekített midlepointot alkalmazunk.
- 10 -
Széls pixel
Bels pixelek
A kitöltési algoritmus lépései: A scan-line metszéspontjainak meghatározása a poligon minden élével. A metszéspontok rendezése x koordináta szerint. Azon pixelek kitöltése a metszéspontok között, melyek a poligon belsejében fekszenek, használva egy paritás bitet. Problémák: Nem egész koordinátájú metszéspont esetén hogyan állapítható meg, hogy melyik oldalon lév pixel tartozik a poligon belsejébe? Hogyan kezelhet k az egész koordinátájú metszéspontok? Hogyan kezelhet ek az egész koordinátájú metszéspontok közös él esetén? Hogyan kezelhet ek az egész koordinátájú metszéspontok vízszintes él esetén? Megoldások: Bal oldal felfelé, jobb oldal lefelé kerekítéssel A bal oldali pixelt bels nek, a jobb oldalit küls nek tekintjük. 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. Hasonlóan a téglalaphoz az alsó élek ki lesznek rajzolva, a fels élek viszont nem.
- 11 -
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
nil
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 A vízszintes lista élei xmin koordinátájuk szerint vannak rendezve Az AET (aktív él tábla) lista:
1. 2. 3. 4.
Töltsük fel az ET listát. Legyen y az ET lista els elemének az y-ja. Inicializáljuk üresnek az AET listát. 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áta párok között, figyelembe véve a paritást. 4.3 y:=y+1 4.4 Távolítsuk el azokat az elemeket az AET-b l, amelyekre y= ymax . 1 4.5 Minden nem függ leges AET-beli élre x:=x+ . m - 12 -
9. Él flag módszer, Rekurzív módszer, Kitöltés mintával Él flag módszer Határszínnel adott zárt tartományon dolgozunk. Vízszintes scan-line mentén határszín pixelhez érve állítunk egy flag-et. Ha true az értéke benn vagyunk, egyébként kinn. A vízszintes élek esetén a flag-et nem állítjuk, ennek az esetnek a kezelése külön megoldandó. Pseudo kód: for(y = ymin; y <= ymax; y++) for(x = xmin; x <= xmax; x++) { if(getpixel(x, y) == hatarszin); flag = !flag; if(flag) putpixel(x, y, szin); }
Rekurzív módszer Háttérszín , zárt tartomány színezésére való. Bemen paraméterként egy bels pixelt kell megadni. Rekurzívan megvizsgálja a szomszédos pixeleket, és amelyik háttérszín , kiszínezi. A rekurzió miatt nagy stack (verem) igénye van, és viszonylag lassú. Pseudo kód: void floodFill(int x, int y) { if(getpixel(x, y) == hatterszin) { putpixel(x, y, szin); floodFill(x + 1, y); floodFill(x 1, y); floodFill(x, y + 1); floodFill(x, y 1); } }
8 6 5 7 0 11
9 4 3 1 2 10
Kitöltés mintával Az alakzatokat különböz mintákkal is ki lehet tölteni. Ehhez egy n*m-es (általában 8*8-as) kitölt kép szükséges, amely színinformációkat tartalmaz.
- 13 -
Módszerek A mintát gondolatban fölmásoljuk a teljes képerny re (0, 0)-tól, és ahol az alakzat van, ott átlátszóvá tesszük a képerny t. Ekkor a minta a képerny pixeleihez van rendelve, tehát ha az objektum mozog, a minta nem fog vele együtt mozogni. Ha a minta egy m × n-es tömbben van tárolva, akkor az alakzat egy (x,y) koordinátájú pixelének színe a mintát tároló táblázat (x mod m, y mod n) elemének megfelel szín lesz. A minta egy meghatározott pixelét az alakzat egy pixeléhez kell hozzárendelni, így eltolásnál a minta az alakzattal mozog. (Ha a koordináta rendszert is hozzárendeljük, akkor még forgatható is lesz.) 10. Antialiasing
A midpoint algoritmus a ferde egyeneseket töredezetten ábrázolja, nem pontos. Az anit-aliasing módszer a ferde vonalak képének és fényének javítására szolgál. Itt különböz színintenzitással vesznek részt a pixlek az egyenes kirajzolásánál, így enyhíteni lehet az egyenes töredezettségét. A lényege, hogy a vonal melletti és a vonal szélein lév pixelek színét átlagolja, és ezzel a vonalat tulajdonképpen egy téglalappal közelíti. súlyozatlan antialiasing Itt azt nézzük, hogy az adott pixelnek hány százaléka van lefedve a téglalappal. súlyozott antialiasing A pixelekre kúpokat teszünk, a téglalaptartományra pedig hasábot, és a térfogatarányokat nézzük (kúp/hasáb). Ez lényegében ugyanaz, mint a súlyozatlan antialiasing, csak ez súlyozva van az elméleti egyenest l vett távolsággal. 11. Harmadrend paraméteres görbék mátrix-reprezentációja Általános alakban a koordináta függvények az alábbiak: x(t) = a3t3 + a2t2 + a1t + a0 y(t) = b3t3 + b2t2 + b2t + b0 z(t) = c3t3 + c2t2 + c1t + c0 Vezessük be az alábbi jelöléseket: t3 a 3 a 2 a1 a 0 x(t ) t2 C = b3 b 2 b1 b 0 ; T = ; Q(t) = y (t ) = C T t c 3 c 2 c1 c 0 z (t ) 1 Célunk általában a C mátrix meghatározása. A különböz típusú interpolációk és approximációk esetén eltér geometriai jellemz kkel rendelkez görbéket állítunk
- 14 -
el , természetesen különböz meghatározó paraméterekkel. Az ismeretlenek száma 12 (vagy 8, ha síkban vagyunk). Ehhez 4 geometriai adat tartozhat, ezek általában pontok, de lehetnek el írt érint k is. Jelölje G a geometria adatokból álló sorvektort, azaz: g 11 g 12 g 13 g 14 G = G1 G 2 G 3 G 4 = g 21 g 22 g 23 g 24 g 31 g 32
g 33 g 34
A C mátrixot GM alakban keressük, ahol M 4x4-s valós elem mátrix. Így a görbe általános alakja: x(t ) Q(t) = y (t ) = C
T=G
M
T
z (t )
Az B(t)=MT harmadfokú polinomokat súlyfüggvényeknek nevezzük. A görbe valamely t0 paraméter pontjában az érint vektor egyszer en származtathat: 3t 2 x' (t ) 2t Q (t) = y ' (t ) = C T = G M T = G M 1 z ' (t ) 0 12. Hermite görbék Legyen adva 4 geometriai adat (pontok vagy érint k) G = [ G1 G2 G3 G4] és a t1, t2, t, t4 skalárok. Keressük az M 4×4-es mátrixot, melyre teljesedik: G=G M [T1 T2 T3 T4], ahol T1 T2 T3 T4 oszlopvektorok, értékük pedig vagy a 3 t 3t 2 T=
t2 t
vagy a T =
2t 1
képlet alapján számolandó, aszerint, hogy pontról vagy
1 0 el írt érint r l van szó. A G = G M [T1 T2 T3 T4] egyenl ség akkor állhat fenn, ha M [T1 T2 T3 T4] = E, azaz M = [T1 T2 T3 T4]-1
Konkrét esetek: 4 pontra illeszked Hermit-ív G = [P1 P2 P3 P4] valamint t1 = -1, t2 = 0, t3 = 1, t4 = 2 1 1 1 0 -1 6 2 3 1 0 1 8 1 1 1 1 1 0 1 4 2 2 M = 1 1 1 0 1 2 1 0 2 2 1 1 1 1 1 1 0 0 6 6
- 15 -
1 6 1 2 1 2 1 6
Q(t) = [P1 P2 P3 P4]
1 3 t 6 [-1, 2]
P1 ( t
1 2 t 2
1 2
1 0 3 1 1 2
1 1 2
1
1 1 t) P2 ( t 3 3 2
=
t
0
1
1 6
0
t3 t2
0
1 1 t 1) P3 ( t 3 2 2
t2
3 pontra illeszked Hermit-ív, ha adott az els pontban az érint G = [P1 P2 P3 R1] valamint legyen t1 = -1, t2 = 0, t3 =1 3 1 5 0 1 0 1 3 -1 4 2 4 1 1 1 1 1 0 1 2 1 1 M = 1 0 1 0 1 1 4 2 4 1 1 1 1 1 0 0 0 2 2 3 1 5 0 t3 4 2 4 1 1 1 1 t2 1 1 1 Q(t) = [P1 P2 P3 R4] = 0 t 4 2 4 1 1 1 0 0 2 2 3 3 1 2 5 1 1 2 P1 ( t t t ) P 2 ( t 3 t 2 t 1) P 3 ( t 3 t 4 2 4 4 2 t [-1, 2] 2 pontra illeszked Hermit-ív, ha adottak az érint k is GH = [P1 P2 R1 R2] valamint legyen t1 = 0, t2 = 1 0 1 0 3 -1 2 3 0 1 MH =
0 1 0 2
=
0 1 1 1 1 1 0 0
Q(t) = [P1 P2 R1 R2]
P1 (2t 3
t
3t 2
1)
2
3
2 1 0
1
1 0 0
2
3 0 1 0 0
t3 t2
1
2 1 0
t
1
1 0 0
1
P 2 ( 2t 3
3
3t 2 )
[0, 1]
- 16 -
1 t ) P4 ( t 3 6
1 1 t) R4 ( t 3 4 2
0 0
1
2
1 2 t 2
R1 (t 3
=
2t 2
t)
R 2 (t 3
t2)
1 t) 2
1 t) 6
Ha 2 helyett n darab pontot és érint t adunk meg, akkor a Hermiteívekb l egy egész görbét tudunk el állítani. Ekkor az el z eljárást sorban el kell végeznünk az egymást követk pont párokra. Ekkor a görbe els rendbeli folytonossága a kapcsolódási pontokban automatikusan érvényesül, mivel az i. ív végérint je megegyezik az (i+1). Ív kezd érint jével (i = 1, 2, , n-1) A Hermite-íveknek a számítógépes grafikában történ alkalmazásában gondot okoz, hogy ezek a paramétertartományok affin transzformációra nem invariánsak.
13. Harmadrend Bézier-görbék - Harmadrend Bezier görbék csatolása Harmadrend Bézie- görbék A Bézier-görbék egy igen speciális esete az n = 3, amikor tehát négy kontrollpont van, melyek egy harmadrend görbét határoznak meg. A Bézier-görbék hullámzás kiegyenlít tulajdonsága következtében szoros kapcsolat van a kontrollpoligon és a görbe alakja között. Harmadrend síkgörbék esetén a kontrollpoligon és a lehetséges szingularitások közötti kapcsolat is jól látható.
- 17 -
Jelölje b0, b1, b2, b3 a kontrollpontokat, m pedig a b0, b1, b2, b3 pontok által meghatározott egyenesek metszéspontját. Ilyen feltételek esetén: ha az m, valamint a b0 és b3 pontok a b1, b2 egyenes ugyanazon oldalán vannak, akkor nincs szingularitás. ha b0 és b3 a b1, b2 egyenes különböz oldalán van, akkor egy inflexiós pont van. ha az m, b0 és b3 pontok a b1, b2 egyenes ugyanazon oldalán van, akkor a következ szingularitások lehetségesek: önmetszéspont, csúcspont, két inflexiós pont. A görbe Bernstein-polinom alakja: 3
b (t )
bi i 0
b 0( t 3
3 i
3t 2
t i (1 t ) 3
i
b 0(1 t ) 3
3t 1) b1(3t 3
3b1t (1 t ) 2
3b 2t 2 (1 t ) b 3t 3
6t 2
3t ) b 2( 3t 3
1
3
3t 2 ) b 3t 3
mátrix reprezentációja b(t) = [t3 t2 t 1]
3 3 1
a kezd illetve végpontbeli érint : b(0) = 3(b1
6
3 1
b0
3
0
b1
3
0
0
b2
0
0
0
b3
b0) ; b(1) = 3(b3
b2 )
Harmadrend Bézier-görbék csatolása Legyenek A1, A2, A3, A4 és B1, B2, B3, B4 kontrollpontok és Q1(t), Q2(t), t [0,1] a megfelel Bézier-szegmensek. Képezve Q(t) t szerinti deriváltjait és helyettesítve a t = 0 és t = 1 értékeket az alábbi eredményt kapjuk: Nulladrend folytonosság esetén: Q1(1) = Q2(0), azaz A4 = B1 d d Els rend folytonosság esetén: Q1(1) Q 2(0) , azaz A4 A3 = B2 B1 dt dt d2 d2 Másodrend folytonosság esetén: 2 Q1(1) Q 2 ( 0) , dt dt 2 azaz (A4 A3) (A3 A2) = (B3 B2) (B2 B1) 14. Bezier görbék el állítása Bernstein polinomokkal - De Casteljau algoritmus A Bézier-görbe paraméteres alakja a Bin (t )
n
t i (1 t ) n i i Bernstein-polinomok segítségével állítható el . A Bernstein-polinomok a következ rekurzív tulajdonságokkal rendelkeznek: Bin (t ) (1 t ) Bin 1 (t ) tBin 11 (t ) , valamint B00 (t ) 1 és Bin 1 0 , ha i < 0 vagy i > n.
- 18 -
A Bernstein-polinomok összege 1 t
R, azaz n
Bin (t ) 1 i 0
A Bin (t ) , t
[0, 1] Bernstein-polinom maximuma a t
i értéknél van. n
A Bézier-görbe néhány tulajdonsága: A Bézier-görbe a kontrollpontjainak affin transzformációjával szemben invariáns. A Bézier-görbe kontrollpontjainak konvex burkán belül van, ha t [0, 1] A Bézier-görbe a paramétertartomány affin transzformációjával szemben invariáns. A Bézier-görbe az els és utolsó kontrollponton áthalad, azaz a végpontokban interpolál. A Bézier-görbe szimmetrikus, azaz a b0, b1, , bn és bn, bn-1, , b0 kontrollpontok ugyanazt a görbét határozzák meg. A Bézier-görbe globálisan változtatható, vagyis egyetlen kontrollpont pozíciójának megváltoztatása az egész görbe alakjának változását eredményezi. A Bézier-görbe pontosan akkor lesz egyenes szakasz, ha a kontrollpontok kollineárisak. A de Casteljau algoritmus bir (t ) pontjai r
bir (t )
bj 1Bir (t ) (r = 0, 1,
, n; i = 0, 1,
,n
r)
j 0
alakban írhatók fel az r-ed fokú Bir (t ) polinomok segítségével. A de Casteljau-algoritmus Adottak a tér b0, b1, , bn pontjai és t [0, 1]. Legyen bir (t ) (1 t )bir 1 (t ) tbir 11 (t ) ; r = 1, , n és i = 0, 1, valamint bi0 bi (i = 0, 1, , n)
,n
r
Ezen ismételt felosztással kapott b0n (t ) pont a b0, b1, , bn pontok által meghatározott Bézier-görbe t paraméterhez tartozó pontja. A b0, b1, , bn pontokat a Bézier-pontoknak vagy kontrollpontoknak nevezzük, az általuk definiált poligont pedig Bézier-poligonnak vagy kontrollpoligonnak. 15. Harmadrend B-spline görbe el állítása Uniform (egyen köz ) nem racionális harmadfokú B-spline Kontroll pontok: P0, P1, , Pm-1, Pm A létrehozandó ívek: Q3, Q4, , Qm-1, Qm A t paraméter: Qi ív esetében ti t ti+1, ahol 3
- 19 -
m i
m.
3
csomópont kontrollpont
A Qi ívet meghatározó pontok: Pi-3, Pi-2, ,Pi-3, Pi ,azaz
G Bsi Q3 ív esetén: Q4 ív esetén: Qi ív esetén: Qm ív esetén:
Pi
P0, P1, P2, P3 P1, P2, P3, P4 Pi-3, Pi-2, Pi-1, Pi Pm-3, Pm-2, Pm-1, Pm
3
Pi 2 Pi 1 Pi , 3 i
m
t3=0, t4=1 t4=1, t5=2 ti=i-3, ti+1=i-2 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: X 0 (1)
X 3 (0)
X 1 (1)
X 0 (0)
X 2 (1)
X 1 (0)
X 3 (1)
X 2 (0)
0
Ehhez hasonlóan a C1 és C2 folytonossághoz valamennyi i-re teljesülnie kell, hogy Qi (1) Qi 1 (0) és Qi (1) Qi 1 (0) , amikb l: X 0 (1)
X 3 (0)
X 1 (1)
X 0 (0)
X 2 (1)
X 1 (0)
X 3 (1)
X 2 (0)
és
- 20 -
0
X 0 (1)
X 3 (0)
X 1 (1)
X 0 (0)
X 2 (1)
X 1 (0)
X 3 (1)
X 2 (0)
X1 (t )
X 2 (t )
0
Cauchy-egyenletet:
X 0 (t )
X 3 (t ) 1
akkor 15 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 (1 t ) 3 6 1 3 X 1 (t ) (3t 6t 2 4) 6 1 X 2 (t ) ( 3t 3 3t 2 3t 1) 6 1 3 X 3 (t ) t 6 X 0 (t )
3
Qi ( t )
X r (t )Pi
3 r,
r 0
- 21 -
t [0,1] i
3,..., m
csomópont kontrollpont
Ugyanez mátrixos felírásban: T=[t3 t2 t 1]T
Qi (t )
GBs i
M Bs Ti , 0 t 1 1
M Bs
BBs
M
Bs
T
1 (1 t ) 3 3t 3 6t 2 6
3
1 3 6 3 1
B
4
6
3 3 3
0
0
3
0
4
1
0
B
Bs 3 Bs 2 3t 3 3t 2
- 22 -
B
T
B
Bs 1 Bs0
3t 1
t3
T 0 t 1.
16. Kétdimenziós transzformációk Eltolás Inhomogén alak: x = x + dx ; y = y + dy mátrix alakban: x P= ;P = y Homogén alak x x' P = y ; P = y' ; T = 1
1
x' y'
;T=
dx
P =P+T
dy
1 0 dx 0 1 dy 0 0 1
x'
P =T
P
1 0 dx
x
y ' = 0 1 dy 1 0 0 1
y 1
y
P`(x`,y`) P(x,y)
x Forgatás origó körül Inhomogén alak: x = x cos( ) y
sin( ) ; y = x
sin( ) + y
cos( )
Mert x = r cos( ) ; y = r sin( ) x = r cos( + ) x = r (cos( ) cos( ) - sin( ) sin( )) y = r sin( + ) y =r (sin( ) cos( ) + sin( ) cos( )) mátrix alakban: x x' cos( ) P= ;P = ;R= y y' sin( ) Homogén alak: x x' cos( ) P = y ; P = y ' ; R = sin( ) 1
1
0
- 23 -
sin( )
P =R
cos( )
P
sin( ) 0 cos( )
0
0
1
P =R
P
x'
cos( )
y ' = sin( ) 1 0
sin( ) 0 cos( ) 0
x
0 1
y 1
Skálázás Inhomogén alak: x = sx x ; y = sy y mátrix alakban: x x' sx 0 P= ;P = ;S= y y' 0 sy Homogén alak: x
x'
P = y ; P = y' ; S = 1
1
P =S
sx
0
0
sy 0
0
0
x'
sx
0
0
x
y' = 1
0 0
sy 0 0 1
y 1
P
x'
=
y'
sx
0
x
0
sy
y
0
P =S
P
1
Ha az sx = sy akkor hasonlóságról, egyébként affinitásról beszélünk.
y
x
- 24 -
17. Window to viewport transzformáció A valós világ leképezése a rajzolási területre. A kép generálásához fel kell vennünk egy ablakot az (u,v) síkban, melyen keresztül a 3D-s modellteret látjuk. Mindazon objektumok, melyek képe az (u,v) síkra vetítve az ablakon kívül esik, a jelenet képén nem fog szerepelni. Azaz egy megjelenítend szakasznak csak a képerny n lév részét kell kirajzolni. A vágás el tt egy vetítés történik az (u,v) síkra. Els lépés a világ koordináta-rendszerbeli rajzterület eltolása az origóba, majd a két rajzterület megfelel élei arányának megfelel en skálázás és visszatolás. Ami kilóg a windowból, az a viewport-ból is ki fog, azaz vágni kell.
y y
( xmax , ymax ) v
v
(umax , vmax )
( xmin , ymin )
x
x
Világkoordináta rendszer
u
Eltolás az origóba
Skálázás 1 0
x min
Az Window origóba való eltolásának mátrixa: T1 = 0 1 0 0
y min 1
u max u min x max x min A skálázás: S =
0 0
0 v max v min y max y min 0 1 0 u min
Visszatolás a viewport-ba: T2 =
0 1 v min 0 0 1
- 25 -
0 0 1
(umin , vmin ) Eltolás
u
u max u min x max x min P = (T2ST1)
P=
0 v max v min y max y min 0
0 0
u max x max v max y min y max 1
x x min P = y
u max x max v max y min y max
u min u min x min v min v min y min
x min
1
x y 1
u min u min x min v min v min y min
18. Térbeli pont transzformációk - Koordináta transzformációk Térbeli pont transzformációk Ebben az esetben, a koordináta-rendszerben ábrázolt test minden egyes tárgypontjához hozzárendelünk egy másik test pontjait. Ezt a leggyakrabban a test eltolásával, forgatásával hajtjuk végre. Matematikailag a pont-transzformációkat az r = N" r' + b transzformációs egyenlettel tudjuk kifejezni. Egybe vágósági transzformációk (mérettartó transzformációk) Eltolás d(dx, dy, dz) vektorral k 1 0 0 dx M=
i
0 1 0 dy 0 0 1 dz 0 0 0
Elforgatás
1
0
0
0 cos
sin
0
0 sin
cos
0
0
1
0
0
j
d i`
szöggel
x tengely körül 1 0 M=
k`
- 26 -
j`
y tengely körül cos 0
M=
sin 0
z tengely körül
0 sin
0
1
0
0
0 cos
0
0
1
0
M=
cos
sin
0 0
sin
cos
0 0
0
0
1 0
0
0
0 1
Tükrözés az {x,y} síkra
M=
1 0
0
0
0 1
0
0
0 0 0 0
k
1 0 0
i=i`
j=j`
1 k`
Hasonlósági transzformációk (arányosságtartó transzformációk) Kicsinyítés, nagyítás origó középponttal 0 M=
0
k`= k
0 0 0 0
0
0
0
0
0
0 1
i`= i
j`= j
Ha nagyobb mint egy, akkor nagyítás, ha pedig kisebb mint egy, akkor kicsinyítés történik. Ha a f átlóbeli elemek nem egyeznek meg, akkor a tengelyek irányában összenyomás vagy széthúzás történik.
- 27 -
Affin transzformációk Skálázás 0 M=
0
k`= k
0 0 0 0
0
0
0
0
0
0 1
i`= i
j`= j
Nyírás Adott egy origón átmen fix sík n normálvektorával, egy a síkkal párhuzamos t irány, valamint egy > 0 valós szám. A hozzárendelés: P = P + d t = P + ( n P)t Mátrix reprezentációban: x' y' z' 1
1 =
txnx tynx
txny 1
tyny
tznx
tzny
0
0
1
txnz
0
x
tynz
0
y
tznz 0
z
0
1
1
Koordináta-transzformációk A 3D-s euklideszi térben egy K koordináta-rendszerr l egy K' koordinátarendszerre térünk át és feltételezzük, hogy ortonormált Descartes-féle koordinátarendszerekr l van szó. Jelölje i, j, k illetve i , j , k a két koordinátarendszer egységvektorait, valamint d mutasson az eredeti rendszer kezd pontjából az új - 28 -
rendszer kezd pontjába. El ször meghatározzuk egy pont eredeti rendszerbeli koordinátát, ha ismerjük az új rendszerben a koordinátákat. Az i , j , k vektorok i, j, k rendszerbeli koordinátáit rendre jelölje ix , iy , iz , jx , jy , jz , kx , ky , kz . p = d + p = x i + y j + z k , vagy mátrix reprezentációban: x y
=
z
ix '
jx ' kx ' dx
x'
iy '
jy ' ky ' dy
y'
iz '
jz ' kz ' dz
z'
0
0
1
1
0
1
k i p
k
P j
d i j
Ha ez eredeti rendszerben ismertek egy pont koordinátái, és az új rendszerbeli el állítás szükséges, akkor a p = p - d egyenl ségb l indulunk ki. Egy pont valamely koordinátája az adott tengelyhez tartozó normál egységvektornak és a pontba mutató vektornak a skaláris szorzataként áll el . Tehát: x = p i = (p d)i = pi di y = p j = (p d)j = pj pj z = p z = (p d)z = pz pz Mátrix reprezentációban az eredmény: x' ix ' jx ' kx ' di ' x ix ' jx ' kx ' y' z' 1
=
iy '
jy ' ky '
dj '
y
iz '
jz ' kz '
dk '
z
0
0
1
1
0
=
dxix ' dyiy ' dziz '
x
iy '
jy ' ky '
dxjx ' dyjy ' dzjz '
y
iz '
jz ' kz '
dxkx ' dyky ' dzkz '
z
0
0
0
1
1
19. Centrális vetítés
A képsík legyen a Descartes-féle koordinátarendszer {x,y} koordináta síkja, a vetítési centrumot helyezzük a z tengelyre, az origótól s távolságra. A megfelel hasonló háromszögekb l: Pxc C Pxc C y c xc s s ; ; x s z s z PC PC y
xc
x
s s z
; yc
- 29 -
y
s s z
; zc
0
Mátrix alakban: xc
1 0
0
0
x
x
yc
0 1
0
0
y
y
0 0 1 1 s
z
0
= 0 0
1
0 0
20. Párhuzamos vetítés
=
x = y
0 z 1 s
1
s s
z s
s 0 1
z
Axonometria
Párhuzamos vetítés Legyen a vetítés iránya adott a v vektorral. y
P
v
~ P
x
P
P
p
x
p
P
v
z
v
- 30 -
z
P =P+ v x = x + vx y = y + vy z =z+
R
vz = 0
=-
z vz
x =x-
z vz
vx ; y = y -
z vz
x
x
vy
Mátrix alakban:
1 0
x' y' 0
= 0 1
0 0 0 0
1
vx vz vy vz 0 0
0 0 0 1
y z
= y
1
z vz vz z vy vz 0 1
Axonometria Megadjuk a képsíkon a tengelykereszt képét. E x(a11, a21) ; E y(a12, a22) ; E z(a13, a23) P(x, y, z) P (u, v) x u a11 a12 a13 a11 x a12 y a13 z = y = v a 21 a 22 a 23 a 21 x a 22 y a 23 z z
Kavalier axonometria u v q
=
q cos
1 0
q sin
0 1
x y z
rövidülés az x tengelyen x tengely képének y tengely képével bezárt szöge
- 31 -
21. 3D vágás - Kanonikus transzformáció - Vágás téglatestre, csonka gúlára Kanonikus transzformáció (centrális eset)
Vágás téglatestre (paralel projekció) y
1. 2. 3. 4. 5. 6.
bit: felette bit: alatta bit jobbra bit: balra bit: mögötte bit: el tte
x
z P0 x0 , y 0 , z 0 és P1 x1 , y1 , z1 pontok esetén a P1 P2 egyenes paraméteres egyenlete : x
x0
t ( x1
x0 )
y
y0
t ( y1
y0 )
z
z0
t ( z1
z0 ) 0
t
1.
y 1 síkkal metszve a metszéspontra : t=(1 y 0 ) /( y1 x
x0
(1 y 0 ) /( x1 x 0 ) y1 y 0
y
y0
(1 y 0 ) /( z1 z 0 ) y1 y 0
- 32 -
y0 )
y 1 y -1 x 1 x < -1 z < -1 z 0
Vágás csonka gúlára (centrális projekció) y
1. 2. 3. 4. 5. 6.
bit: felette bit: alatta bit jobbra bit: balra bit: mögötte bit: el tte
zmin x z y t= x
z síkkal metszve a metszéspontra : y 0 ( y1 x0
z 0 y0 y 0 ) ( z1
t ( y1
y0 )
z0
z0 )
( x1 x0 )( z 0 y 0 ) ( y1 y 0 ) ( z1 z 0 )
y
y0
( y1 y 0 )( z 0 z 0 ) ( y1 y 0 ) ( z1 z 0 )
- 33 -
t ( z1
z0 )
y -z y z x -z x
22. Felületmodellezés - Felületeket leíró adatstruktúrák Poligonokkal határolt felületek Explicit reprezentáció Minden poligont csúcsainak koordinátáival adunk meg, az egymásra következ csúcsok (+az els és utolsó) adják az éleket:
P
(( x1 , y1 , z1 ),( x2 , y2 , z2 ),....,( xn , yn , zn ))
Mutatók a csúcslistába Itt már van a poligonoknak is egy listája, ahol az elemek mutatók, és a csúcslista elemeire mutatnak. a. Csúcsok listája
V
(( x1 , y1 , z1 ),( x2 , y2 , z2 ),....,( xn , yn , zn ))
b. Poligonok listája, mutatókkal a csúcslistába (k db poligon)
P1
(i11 , i12 ,..., i1m )
P2
(i21 , i22 ,..., i2m )
1
2
. . Pk
(ik1 , ik2 ,..., ikm ) k
Mutatók az él listába Itt van egy él lista is, melyben két mutató a csúcslista 1-1 elemére mutat, melyek az él végpontjai; két mutató pedig a poligonok listájába mutat, melyekkel az él határos. a. Csúcsok listája
V
(( x1 , y1 , z1 ),( x2 , y2 , z2 ),....,( xn , yn , zn ))
b. Élek listája (l db él. Ha egy él csak egy poligonhoz tartozik, nullát írunk)
E1
(i11 , i12 , P11 , P12 )
E2
(i21 , i22 , P21 , P22 )
. El
(il1 , il2 , Pl1 , Pl 2 )
c. Poligonok listája (k db poligon)
P1
( E11 , E12 ,..., E1p )
P2
( E 21 , E 22 ,..., E 2p )
1
2
. Pk
( E k1 , E k2 ,..., E kp ) 2
- 34 -
23. Regularizált halmazm veletek - Definiálás görbesereggel Regularizált halmazm veletek (*): Aop * B
int( Aop B)
A regularizált halmazm veleteket elméletileg úgy valósíthatjuk meg, hogy az eredetileg zárt halmazokból elvesszük a határukat. Az így kapott nyílt halmazokon végrehajtjuk az el írt halmazm veleteket, majd az eredményhalmazt lezárjuk, azaz hozzáadjuk a halmaz határát. Definiálás görbesereggel Egy egyparaméteres görbesereggel definiálhatunk felületet. A görbesereget úgy állítjuk el , hogy egy generáló görbét mozgatunk egy vezérgörbe mentén. Ezek mellett meg kell adni a generáló görbe tájolását is. Szokásos tájolás, hogy a generáló görbét önmagával párhuzamosan toljuk el, azaz a generáló görbe orientációja a görbék definiálásánál használt koordináta rendszerhez képest változatlan. Egy másik megoldás, hogy a generáló görbét a vezérgörbe kísér triéderéhez kapcsoljuk. A generáló görbe a felület vagy test egy metszete a vezérgörbe pedig a gerince . Ha egy tetsz leges görbét mozgatunk, akkor felületet kapunk, ha pedig egy zárt generáló görbe által határolt síkrészt, akkor testet.
- 35 -
24. Drótváz modell - Felületmodell (B-rep) - Euler formula Drótváz modell A drótváz- vagy élmodell a legegyszer bb, de nem minden esetben egyértelm leírása térbeli objektumoknak. Egy drótváz modellben az objektumokat az ket meghatározó pontok (csúcspontok) és az ezeket összeköt élek írják le. Az élek nem feltétlenül egyenes szakaszok. Ezzel a módszerrel kevés adattal egyszer en írhatók le térbeli alakzatok. Az így leírt alakzatok gyorsan megjeleníthet k, a láthatóság szerinti ábrázolás azonban általában nem lehetséges. A modell egyik legnagyobb hátránya, hogy leírhatunk vele nonszensz testeket (pl. Necker-féle kocka), másik lényeges hiányossága, hogy a leírás nem egyértelm , azaz több különböz testnek lehet megegyez modellje.
Necker-féle kocka Felületmodell (B-rep) A felületmodell a drótváz modell továbbfejlesztésének tekinthet . Azon a feltételezésen alapszik, hogy egy objektumot lapok határolnak, a lapokat élek, az éleket pedig két csúcspont. A lap, ami lehet sík vagy görbült felületfolt, az t tartalmazó felület egyenletével, valamint a határoló élekre történ hivatkozással reprezentálható. Az él az t tartalmazó görbe egyenletével, valamint a két határoló pontjára való hivatkozással reprezentálható. A csúcspont pedig koordinátáival írható le. Egy objektumot leíró adatstruktúra topológiai és geometriai információkat tartalmaz. Topológiai információn a lapok, élek, csúcspontok közötti kapcsolatot értjük, amit hivatkozásokkal írhatunk le.
- 36 -
Euler formula A bels lyukat nem tartalmazó, a gömbbel homeomorf poliéderekre a c e+l=2 úgynevezett Euler-egyenlet érvényes, ahol c a csúcsok, e az élek, l pedig a lapok száma. Ennek a következ általánosítása érvényes a bels lyukat is tartalmazó poliéderekb l álló testcsoportra c e + l = 2(n ly) + h ahol n az egymáshoz nem kapcsolódó testek száma, ly az egész objektumon áthaladó lyukak száma, h pedig a lapokon lév lyukak (hurkok) száma. Ezt EulerPoincaré-féle összefüggésnek szokás nevezni. 25. Cellamódszerek - Térfogat modell (CSG) Cellamódszerek Volume visualisation A teret egybevágó kockákkal töltjük ki, azaz egy háromdimenziós rácsot hozunk létre. Ezeket a kockákat voxeleknek nevezik, a pixel analógiájaként. Minden kockáról meg kell határozni, hogy a testen belül vagy kívül van. Azokat a kockákat is az el z két csoport valamelyikéve kell sorolni amelyeknek csak egy része van a testben. Ez történhet pl. annak alapján, hogy a kocka középpontja, vagy a kocka térfogatának több mint fele belül van a testen.
Octree felépítése Ennél a módszernél egy olyan kockából indulunk ki, amely a testet tartalmazza. Ezt a kockát az oldalfelez síkokkal 8 egybevágó kockára bontjuk. Az egyes kockát lehetnek a testen kívül, a testen belül vagy metszhetik azt. Az utóbbi esetben a kockákat újabb 8 egybevágó kockára bontjuk. Ezt az eljárást addig folytatjuk míg, vagy minden kocka a testen belül vagy kívül van, vagy az újabb kockák mérete el nem ér egy el re megadott alsó határt. Így tehát egy oktális fa gráfot építünk fel.
- 37 -
A cella módszerek el nyei: egyszer adatszerkezet jól megfelel néhány alkalmazásnak térfogatszámítás) Hátrányai: csak approximálja a modellezend testet viszonylag nagy a tárolási igénye
(pl.
egyszer
a
tömeg-
és
Térfogat modell (CSG) Ez a modellezési módszer egyszer testekb l halmazm veletek (Boole m veletek: unió, metszet, különbség) segítségével állítja el az összetett objektumokat. Az épít elemként használt egyszer testeket primitíveknek is szokás nevezni. A gúla, hasáb, gömb, kúp, henger és a tórusz a leggyakrabban használt primitív. A primitívek félterekb l és implicit egyenletek által meghatározott ponthalmazokból halmazm veletekkel származtathatók. Egy CSG modellez segítségével a felhasználó az alábbi módon definiálhat egy összetett alakzatot: Kiválasztja a megfelel primitíveket és megadja az azokhoz szükséges paramétereket. A primitívek saját, lokális koordináta-rendszerükben vannak definiálva. Annak érdekében, hogy a megfelel pozícióba kerüljenek mozgási transzformációkat kell végrehajtani rajtuk. Ezt a primitív pozícionálásának szokás nevezni. Végül a primitívekb l a regularizált halmazm veletekkel egy összetett test hozható létre. A CSG reprezentáció egy bináris fa gráffal írható le. A CSG modellezés el nyei: Tömör, kompakt reprezentálás, kis memória igény Könnyen biztosítható a modell érvényessége, azaz a modell megvalósíthatósága Testek széles skálája könnyen definiálható Hátránya: Nincs közvetlen hozzáférés a csúcs, él, lap információkhoz, így a megjelenítés bonyolultabb, a vizuális visszacsatolás lassabb.
- 38 -
27. Coons foltok - Bikubikus felületek Coons foltok A Coons foltok definiálásánál két, egymást páronként metsz görbepárból, vagy egy görbeoldalú térbeli négyszögb l indulunk ki. Erre a négyszögre illesztünk egy felületet. Adottak az a1(u), a2(u), u [0, 1], és b1(v), b2(v), v [0, 1] egymást páronként metsz görbe párok a térben. Keresünk olyan s(u, v) u,v [0, 1] felületet, amelyre s(u, 0) = a1(u) s(u, 1) = a2(u) s(v, 0) = b1(v) s(v, 1) = b2(v) teljesül. A megoldáshoz vonalfelületeket használunk. Tekintsük az a1(u) és a2(u) által meghatározott la(u, v) = (1 v)a1(u) + va2(u) valamint a b1(v) és b2(v) által meghatározott lb(u, v) = (1 u)b1(v) + ub2(v) vonalfelületeket. Ezek a felületek a szemben fekv görbéket interpolálják, ezonban a másik két határoló görbén nem haladnak át. Ezen probléma megoldása érdekében tekintsük a négy metszéspont (csúcspont) bilineáris interpolációját, az s (0,0) s (0,1) 1 v lab(u, v) = 1 u u s (1,0) s (1,1) v felületet. Ez a felületfolt mind a négy határoló görbére illeszkedik. A bilineráis elnevezés az el állítás módjára utal, nem a kapott eredményre.
- 39 -
- 40 -
Bikubikus felületek Kiindulás:harmadrend paraméteres térgörbe általános alakja: Q(t ) T M G , ahol T [t 3 t 2 t1] (paraméter), M a bázis mátrix, G a geometriai vektor. Felület esetén:
r (u , v )
U
M
G (v )
U
G 1(v ) G 2 (v ) G 3 (v )
M
G és G i ( v ) (A
B
G i (v )
r (u , v )
V
C )T G
T i
U
M
G i , ahol
CTB
T
A
T
V
T
M
M
T
G
g
M
i4
g 13 g 23
g 14 g 24
g g
g 32 g 42
g 33 g 43
g g
T
U
M
G
x (u , v )
U
M
G
M
T
V
T
x
y (u , v )
U
M
G
M
T
V
T
y
z (u , v )
U
M
G
z
M
2 MH
3
v 3 v 2 v1
,V
V
T
V
2 3
T
M
V
T
T
V
T
vagy
34 44
T
r (u , v )
Hermite görbe esetén:
i3
g 12 g 22
M
T i4
alapján
g 11 g 21 41
u 3 u 2 u1
U
(v )
4
g i1 g i 2 g i 3 g
i
g i1 g i 2 g
31
ahol
T
1 2
1 1
0
0
1
0
1
0
0
0
Gh
Q(t ) [ x(t ) y (t ) z (t )]
- 41 -
[P1 , P4 , R 1 , R 4 ]T
T MH GH
Hermite felület: P1 ( v ) x (u , v )
U M
G H x (v )
H
U M
P4 ( v ) H
ahol U
R 1 (v ) R 4 (v )
x
A P1 ( v ), P 4 ( v ), R 1 ( v ), R 4 ( v ) Hermite függvények g 11 P1 x ( v )
V M
, P2 x (v )
g 13 g 14
V M
g 22 H
g 24
,R 4 ( v ) = V M
g 33 g 34
V M
x
g 11
g 12
g 13
g 14
g 21
g 22
g 23
g 24
g 31
g 32
g 33
g 34
g 41
g 42
g 43
g 44 g 13
g 14
P4 (v )
g 21
g 22
g 23
g 24
R 1 (v )
g 31
g 32
g 33
g 34
g 41
g 42
g 43
g 44
x (u , v )
U M
G Hx M
H
x ( 0 ,0 )
x ( 0 ,1)
x (1, 0 )
x (1,1)
V
G Hx u u
x ( 0 ,0 ) x (1, 0 )
u u
x ( 0 ,1) x (1,1)
T Hx
x
, ahol
x
g 12
T H
G
H
g 11
x
g 43 g 44
P1 ( v )
R 4 (v )
g 42 H
x
P1 ( v ) P 4 ( v ) R 1 ( v ) R 4 ( v )
G Hx
x
g 41
g 32 H
g 23
x
g 31 R 1 (v ) = V M
el l álítá (x komponense ik) :
g 21
g 12 H
u 3 u 2 u1
M TH V T
G H x M TH V T
x
T
v v
x ( 0 ,0 ) x (1, 0 )
u v u v
x ( 0 ,0 ) x (1, 0 )
x(u , v) U M B G Bx M TB V T
Bézier-felületek: y (u , v) U M B G By M TB V T z (u , v) U M B G Bz M TB V T
- 42 -
v v
x ( 0 ,1) x (1,1)
u v u v
x ( 0 ,1) x (1,1)
x(u , v) U M BS G BS x M TBS V T B-Spline-felületek: y (u , v) U M BS G BS M TBS V T y
z (u , v) U M BS G B
Sz
M TBS V T
(U M G M T V T )
r (u , v)
u u 2 3u 2u10 M G M T V T
Felületi normálisok:
v
r (u , v)
u
r (u , v)
T
v
xu y u z u
(U M G M T V T ) U M G M T
v
U M G M
u
(U) M G M T V T
2
3v 2v10 r (u , v)
T
yu z v
u
(V T )
xv y v z v y v z u z u xv
z v xu xu y v
xv y u
28. Láthatósági algoritmusok hatékonyságát növel módszerek Normalizált perspektív transzformáció (hullám transzformáció) 1 0 0 0
M
0 1
0 0 z min 1 z min 0 0 1 z min 1 z min 0 0 1 0 1 x 1 ; 1 y 1; 1 z 0
1
Átlapolás vizsgálatok (bounding boksz, boundin volume, min-max testing) A térbeli objektumok takarási viszonyainak meghatározását esetenként segítheti, ha ezeket egyszer bb formájú testekbe zárjuk, melyek térbeli elhelyezkedését hatékonyabb algoritmusokkal tudjuk tesztelni. Ezeket befoglaló testeknek nevezik. A leggyakrabban alkalmazott befoglaló test a téglatest, de esetenként a céloknak jobban megfelelhet a henger vagy a gömb. A látható felületek meghatározásának m veletigényét ez azért csökkentheti, mert azokkal a vetít sugarakkal, melyek a befoglaló testet nem metszik, az eredeti testünknek sem lehet közös pontja. (Így ezeknek a vetít sugaraknak a vizsgálatát a megjelenít algoritmusból kiküszöbölhetjük.) Hasonló az alapgondolata a kivágó ablak x, y síkjában az objektumok vetületeit tesztel min/man eljárásnak. Ennél az objektumok vetületeit téglalapokkal vessük körül, és ha ezeknek a téglalapokkal nincs közös része, akkor biztos lehetünk abban, hogy a vetületeknek megfelel felületek sem fedik egymást. Így ha az A poligonvetület legnagyobb x értéke kisebb, mint a B poligonvetület legkisebb x értéke, vagy ha az A poligonvetület legnagyobb y értéke kisebb, mint a B poligonvetület legkisebb y értéke akkor az A és B poligonok takarását nem kell vizsgálnunk.
- 43 -
Hátsólapok eltávolítása(backface culling) A zárt, sokszögekb l felépül objektumokat teljesen körbezárják a felületüket alkotó poligonok. Ha a poligonok normálvektorai: úgy állítjuk be, hogy az objektumból kifelé mutassanak, akkor azok a poligonok, melyek normálvektorai nem a néz félé mutatnak, biztosan takarva lesznek az objektum közelebbi felületei által. Ezeket a takarásba kerül , úgymond hátrafelé néz poligonokat back-face poligonoknak nevezzük és az objektumokat leíró adatbázisból való eltávolításukat eredményez eljárást pedig back-face culling-nak. Analóg módon az el re néz poligonokat frontface-nek nevezzük. A back-face poligonok könnyen azonosíthatók kifelé mutató normálvektoruk és a vetítés középpontjából a poligon egy pontjához mutató vektor skalárszorzatának vizsgálatával: a pozitív érték hátrafelé néz poligonra utal. Ha az ábrázolandó jelenet egyetlen, konvex poliéderb l áll, akkor a látható felületek meghatározása back-face culling m veletre egyszer södik. Más esetekben további vizsgálatok szükségesek, hiszen a front-face poligonok is takarhatják egymást. Egy poligonális objektumot metsz vetít sugár pontosan annyi back-face poligonon megy át, mint ahány front-face poligonon. A back-face poligonok eltávolítása tehát éppen megfelezi a képpontosság algoritmusa által egy-egy pixel esetén megvizsgálandó poligonok számát. Átlagos esetben a jeleneteket alkotó poligonok nagyjából fele hátrafelé néz, így a back-face culling a tárgypontosság algoritmusok által vizsgálandó poligonok számát is nagyjából megfelezi. Ha egy lap kifelé mutató normálvektora n és a lap egy pontjából a centrumba mutató vektor c, akkor a lap hátsó, ha 0>cos(n,c), A konvex poliéderek láthatóság szerinti megjelenítéséhez elegend a hátsó lapokat eltávolítani.
- 44 -
Térbeli szeparáció Nem a teljes teret kell vizsgálni, hanem fel kell osztani azt tartományokra, ahová a leképezés történik. Ha lehetséges a teret szeparálni, s el re tudható, hogy majd hova esik az alakzat, akkor a tér többi részét nem kell majd vizsgálni.
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 egyenes párok által határolt konvex lapokkal)
- 45 -
29. Robert algoritmusa
Appel algoritmusa
Haloid vonalak módszer
Robert algoritmusa (1963) Konvex poliéderekb l álló objektum takarási viszonyinak meghatározására szolgál. Minden konvex objektum hátsó lapjait eltávolítjuk. Meghatározzuk a konvex poliéderek kontúrjait a képen. A kontúrok takarási viszonyainak figyelembevételével megvágjuk a poligonokat (vagy éleket), ha szükséges. Kontúr él: ha egy elüls és egy hátulsó lapnak egy él közös éle, akkor az kontúr, s így lehet meghatározni a konvex kontúrt.
Appel algoritmusa (1967) Olyan poliéderekre használható, amelyek nem feltétlenül konvexek. Egy kvantitatív láthatósági mutatót használ, amely: Hányszorosan takart az elüls lapok által az adott szakasz Ahol a mutató nulla, ott nem történt takarás Ott változik a mutató ahol, ahol kontúr él van Halid vonalak módszere Páronként összehasonlítást kell végezni az élekkel, hogy metszik-e egymást. Ha metszik egymást, akkor a z koordinátát kiszámolva el kell dönteni, hogy melyik él takarja a másikat. B C
M
A
0
1
P (1 ) A B az M pont bels metszéspont
- 46 -
D
30. Mélység rendezés (fest algoritmus) - BSP algoritmus Fest algoritmus (Newell,1972) A fest algoritmus csak poliéder modellek esetén használható. Nevét onnan kapta, hogy az objektumok lapjait hátulról el re haladva jeleníti meg, vagy minden lapot az t eltakaró (eltakarható) lapok megjelenítése el tt. Ehhez az algoritmushoz tehát a lapokat a hátsók elhagyása után z koordinátájuk szerint rendezni kell, majd hátulról el re haladva meg kell jeleníteni ket. A megjelenítés azt jelenti, hogy a poligon határát megrajzoljuk és kitöltjük (befestjük) a megfelel színárnyalattal. A rendezés során két komolyabb probléma merülhet fel. Az egyik a ciklikus átfedés a másik a két lap kölcsönös átfedése. Mindkét esetet úgy oldhatjuk fel, hogy valamelyik lapot kettévágjuk az átfed lap síkjával, vagy vetít hasábjával. Az algoritmus el nye, hogy egyszer , könnyen megvalósítható. Hátránya, hogy a rendezés id igényes, valamint az, hogy összetett alakzat vagy alakzat csoport esetén sok olyan lapot kell feldolgozni, amely végül nem lesz része a képnek.
BSP algoritmus (Bináris térfelosztási fa Fuchs, 1980) A háromdimenziós objektumok tetsz leges néz ponthoz tartozó megjelenítésére használt algoritmusok közül az. egyik leghatékonyabb a bináris térfelosztó fákat (BSP fák) alkalmazó eljárás. Bár az algoritmusnak az objektumok térbeli helyzetét feltáró, el feldolgozó része meglehet sen id igényes, kés bb, új néz pont definiálásakor gyorsan képes el állítani az új képet, hiszen ekkor már csak a frame-bufferbe kell konvertálnia a takaráshelyes objektumokat. A BSP fa algoritmusok azon alapulnak, hogy az ábrázolandó jeleneteket úgy is tekinthetjük, mint objektumcsoportok gy jteményét. Ha található olyan sík, amely elválaszt egymástól két objektumcsoportot, akkor az a csoport, amely oldalán a néz pont is van, eltakarhatja a másik csoportot, de a másik csoport által sohasem kerülhet fedésbe. Minden egyes objektumcsoport rekurzívan tovább osztható, ha megfelel szeparáló síkok találhatók. A jelenet felosztását reprezentálhatjuk olyan bináris fával, melynek gyökere az els ként választott szeparáló síknál van. A fa bels csomópontjai a szeparáló síkokat jelentik, a fa levelei pedig a felosztás során keletkezett térrészeket. Minden térrészhez hozzárendelhetjük az objektumcsoportok olyan sorrendjét, amely az adott térrészben elhelyezked néz ponthoz tartozó helyes takarási viszonyokat rögzíti a megjelenítés során. Bár az algoritmus helyes m ködése nem függ attól, hogy hogyan választjuk meg a szeparáló síkjainkat, a síkok által végrehajtandó vágások száma azonban jelent sen befolyásolja az algoritmus id igényét. A BSP fa algoritmusok, a mélységi-rendez algoritmusokhoz hasonlóan az objektumok vágását és rendezését tárgypontosság módszerekkel végzik, képpontosság technikákhoz pedig csak a megjelenítés során nyúlnak. Az itt elvégzett objektum felosztásokat, ellentétben a mélységi-rendez algoritmusokkal, - 47 -
csak akkor kell újra elvégezni, ha a jelenet megváltozik. Másként fogalmazva, a néz pont megváltoztatása esetén nem kell a BSP fát módosítani.
A BSP fa elkészítése Rendelkezésünkre áll a feldolgozandó lapok egy listája. 1. Válasszunk ki egy alkalmas lapot a listából. Ez lesz a fa gyökéreleme (gyökérlap). 2. Ha nem maradt több lap (egyelem volt a lista), akkor kész vagyunk. 3. Majd a maradék lapokat két újabb listába rendezzük aszerint, hogy: o A gyökérlap által generált pozitív fél térben helyezkedik-e el - front listába tesszük. o A gyökérlap által generált negatív fél térben helyezkedik-e el - back listába tesszük. o A gyökérlap síkja vágja a vizsgált lapot ekkor a vizsgált lapot vágjuk a gyökérlap síkjával és a front ill. back listába tesszük ezeket. 4. A két új listára végrehajtjuk az 1.-4. pontokat. Kész.
A BSP fa bejárása 1. Kiszámoljuk a korábban megismert módszer szerint, hogy a néz pont a gyökérIap melyik oldalára esik. 2. Ha a gyökérfap által generált pozitív fél térbe esik, akkor: o Bejárjuk a back ágat, ha van. o Kirajzoljuk az aktuális gyökérlapot. o Bejárjuk a front ágat, ha van. o Kész. 3. Egyébként: o Bejárjuk a front ágat, ha van. o Kirajzoljuk az aktuális gyökérlapot. o Bejárjuk a back ágat, ha van. o Kész.
- 48 -
31. Z-puffer algoritmus Ez az algoritmus nem az ábrázolandó objektum, hanem a kép fel l közelíti meg a problémát, ezért is szokták úgynevezett képtér algoritmusok közé sorolni. Azt használja ki, hogy a kép pixelekb l tev dik össze, ezért a láthatósági vizsgálatot pixelenként végzi el. Azt vizsgálja, hogy egy-egy pixelen mi látszik, csupán két értéket kell összehasonlítani. Az algoritmus a pixelek színének tárolása (frame buffer) mellett meg kell oldani a mélységek (z érték) tárolását is. Erre szolgál az ún. mélység-puffer (z buffer). Az algoritmus f bb lépései a következ k: A mélység-puffert a maximális mélységre állítjuk, vagyis arra a mélységre amelyt l távolabbi pontokat már nem veszünk figyelembe. Az objektumok határoló felületén végighaladva (a határoló felületet pixelekké konvertálva) minden pontra: o Meghatározzuk a pont mélységét. o Ha ez az érték kisebb, mint a pont vetületébe es pixelekhez a mélység-pufferben rendelt érték, vagyis az új pont látszik, akkor Meghatározzuk a pont színét és ezt rendeljük a pixelhez. A pixel mélységét a pont mélységére állítjuk be. A mélység-puffer algoritmus egyszer sége miatt széles körben elterjedt, létezik hardver implementációja is. Hátránya a nagy tárolási igény, valamint az, hogy olyan felületek is fel kell dolgozni amelyek nem lesznek részei a képnek. z meghatározása: scan konverzió Sík egyenlete : Ax z z new
By Cz
D
0( z
0)
D
Ax By C A z old x, ahol általában x 1 C
32. Scan-line algoritmus Ez az algoritmus pixelsoronként (képpont soronként) számolja a láthatóságot úgy, hogy az ábrázolandó alakzatokat elmetszi a pixelsor vetít síkjával. A mélység-puffer algoritmussal ellentétben nem kell egyidej leg tárolni a képerny összes pixelének mélységét, csupán az aktuális sor pixeleiét. Pixelsoronként a következ ket kell végrehajtani: A mélység-puffert a maximális mélységre kell állítani. Az objektum minden lapjára: o Elmetsszük a pixelsor vetít síkjával o A metszet vetületére es minden pixelre: Ha az új pont látszik, azaz közelebb van, mint a mélységpufferben tárolt érték, akkor az új pont színét és mélységét rendeljük a pixelhez.
- 49 -
Növelhetjük a hatékonyságot ha a pixelsorokhoz meghatározzuk az aktív lapok listáját, azaz meghatározzuk azokat a lapokat, amelyeket metsz a pixelsor vetít síkja (ez elérhet pl. a lapok ymax szerinti rendezésével). Az algoritmus nem nagy tárolási igény , és alkalmas hardver implementációra is. Párhuzamos feldolgozásra is alkalmas.
33. Terület-felosztásos algoritmus. (Warnock) A területfelosztó algoritmusok alapgondolata, hogy néhány esetben (például a képen csak egy objektumot kell ábrázolni) nagyon egyszer en megállapítható a képerny n megjelenítend kép, eltért a bonyolultabb takarási vizsgálatokat a kép területének kisebb részekre való rekurzív, felosztásával vezessük vissza az egyszer en kezelhet esetekre. A képfelosztás történhet a raszteres képerny koordinátarendszerben, illetve a vektoros látótér koordináta-rendszerben. Warnock (1969) A rekurzió után maradó lehetséges helyzetek:
1. Minden poligon a vizsgált területen kívül esik. Háttérszínnel befestjük a területet. 2. Csak egy metsz vagy tartalmazott poligon van a vizsgált területen. El ször a területet kitöltjük háttérszínnel, majd a poligon területen belüli részét scankonvertáljuk. 3. Csak egy, a vizsgált területet teljesen tartalmazó poligon van. Befestjük a területet a poligonnak megfelel színnel. 4. Több mint egy poligonnak van közös része a tartománnyal, de van olyan, a tartományt teljesen tartalmazó poligon, amely a többi el tt van.
- 50 -
34. Sugárkövetés A fénysugár követ módszer (ray tracing) alapja az, hogy meghatározzuk az ábrázolandó objektumoknak azt a pontját amely egy adott pixelen látszik. Az algoritmus a következ lépésekb l áll: A néz pontot (vetítési centrumot) összekötjük a kép pixeleivel. Ezekkel a félegyenesekkel (sugarakkal) elmetsszük az ábrázolandó objektumokat. Meghatározzuk a néz ponthoz legközelebbi metszéspontot, majd ennek a pontnak a színét és a pixelt erre a színre állítjuk be. Ez az eljárás mind a B-rep, mind a CSG modellek esetén használható. Ez az algoritmus, bár alapötletét tekintve egyszer , sok számítást kíván ezért id igényes. Az egyes pixelek színének meghatározása független egymástól, ezért az algoritmus alkalmas a párhuzamos feldolgozásra, amivel jelent sen felgyorsítható. Ezzel az algoritmussal lehet a legjobb min ség képet el állítani. Modellezhet vele a fényvisszaver dés, a fénytörés (átlátszóságot) és az árnyékokat is.
A vetít sugár meghatározása: C ( x0 , y 0 , z 0 ) a vetítési centrum, P ( x1 , y1 , z1 ) egy pixel közepe. x=x0
t ( x1 x
x0 ), y=y 0 x1
x=x0
x0 , y
t ( y1 y1
t x, y=y 0
- 51 -
y 0 ), z=z 0 y0 , z y, z=z 0
t ( z1
z1
z0 z
z0 )
A t paraméter 0 és 1 közé es értékei a néz pont és a vizsgált pixel közé es fénysugárpontokat definiálják, negatív értékek esetén a néz pont mögött vagyunk, míg 1-nél nagyobb t értékekre a képsík túlsó oldalára kerülünk. A fénysugár és az objektumok metszéspontjainak meghatározásához minden egyes, a jelenetet alkotó objektumtípust matematikailag le kell írnunk. Pl. gömb esetében: ( x a) 2
( x
( y b) 2 y
( z c) 2
z) 2 t 2 ( x0
a)
r 2 , behelyettesítve x, y, és z - t :
2t x( x0 2
( y0
A gömb normálisa : P( x, y, z ) - ben :
b)
a) 2
( z0
x a /r
y( y0
b)
2
2
c)
r
y b /r
z( z0
c)
0
z c /r
Poligon esetén: A poligon síkjának egyenlete: Ax+By+Cz+D=0 . Behelyettesítés után t-re adódik:
t
Ax0+By0+Cz0+D , hacsak A x+B y+C z A x+B y+C z
0.
Ekkor levetítjük a poligont a legnagyobb képet el állító koordinátasíkra, ahol a metszéspontra elvégezzük a bent van tesztet.
- 52 -
35. Színelméleti ismeretek Színérzet: a fény elektromágneses hullámainak spektrális tulajdonságai által keltett hatás. Színtér: a lehetséges színérzetek alkotta háromdimenziós tér. Tristimulus: a beérkez fényenergiát leíró skalár érték. Színformátumok: Black and White: egy képpontnak két állapota van, fekete és fehér, egy képpont állapotának rögzítése 1 bitet igényel. 16 color: 16 megadott színe lehet egy képpontnak, 4 biten tárolja a képpont állapotát. Greyscale: egy képpont a szürke 256 árnyalatával rendelkezhet, a képpont állapotát 8 biten tárolja. 256 color: 256 színe lehet egy képpontnak, a képpont állapotát 8 biten tárolja. CMYK: egy képpont a türkiz (Cyan), a bíbor (Magenta), a sárga (Yellow) és a fekete (black) 256 * 4 féle árnyalataiból áll össze.
- 53 -
36. Megvilágítási modellek - Árnyalás Egy pont színét illetve egy szín árnyalatát a pontba beérkez fény mennyisége és a felület színe határozza meg. Színes display esetén egy színt többnyire a piros, zöld és kék színkomponensek intenzitásának megadásával állíthatunk el . A megvilágítással kapcsolatos felületi konstansokat is a piros, zöld és kék színek szerinti komponensekkel kell megadni. Egy felületi pontból a néz pontba érkez fényeknek egyetlen pontszer fényforrás esetén három összetev je van: Szórt megvilágítás vagy környezeti fény Szórt visszaver dés Visszatükrözött fény A szórt megvilágítás komponens mindenütt ugyanakkora, és egy felületi pontból a néz pontba eljutó fénymennyiség csak a felülett l függ. Ea = ka Ia alakban írható fel, ahol a ka (0, 1) a felületre jellemz konstans Ia pedig a szórt megvilágítás intenzitása (konstans). A szórt visszaver dés komponens függ a fényforrás Il intenzitásától, a felületi pontba beérkez fénysugárnak a felületi normálissal bezárt szögét l, valamint a pontnak a fényforrástól mért D távolságától. Az összefüggés Ed = kd Il cos / (C + D) alakban írható fel, ahol C egy empirikus konstans, kd pedig a felület szórt visszaver dési együtthatója.
Gouroud-féle árnyalás Ehhez az árnyalási modellhez meg kell határozni a felületi normálisokat a csúcspontokban. Ezt a csúcspontokban találkozó lapok normálisainak átlagolásával érhetjük el. Ezután a csúcspontokban a megvilágítási modellnek megfelel en kiszámíthatjuk a fény intenzitást. A lap élei mentén a csúcspontok intenzitásának lineáris interpolációjával határozzuk meg, a lap valamely bels pontjának pedig a lenti ábra szerinti kett s interpolációval, azaz el ször az A és B pontokban, majd ezek lineáris interpolációjával a P pontban.
- 54 -
Hátránya, hogy a test körvonala nem lesz sima. További hátránya mutatkozik a nagy tükröz visszaver dés részeknél, valamint jelentkezhet az úgynevezett Mach-sáv hatás (az emberi szem által észlelt ugrásszer fény intenzitás változás). Phog-féle árnyalás A Phong-féle árnyalás csak abban különbözik a Gouroud-félét l, hogy nem a fény intenzitást interpolálja, hanem a normálisokat. Így minden egyes pontban ki kell számítani a fény intenzitást az interpolációval kapott normálist felhasználva. Ez természetesen több számítást igényel, de az eredmény is jobb min ség lesz. Egyetlen negatív jelenség marad, a határgörbe szögletessége .
Felhasznált irodalom Juhász Imre. Számítógépi geometria és grafika. Miskolc. Miskolci Egyetemi Kiadó, 1995. Szirmay-Kalos L. Számítógépes grafika. ComputerBooks, 1999. http://www.fsz.bme.hu/~szirmay/szg.htm Schwarcz Tibor. Bevezetés a számítógépes grafikába (el adás segédanyaga) Debrecen, 2005. http://www.inf.unideb.hu/grafika/schwarcz/infok.htm Várady Lajos. Számítógépi grafika gyakorlat Debrecen, 1998. El adásokon készült kéziratok
Javasolt irodalom (f leg gyakorlat) Tornai Róbert. Bevezetés a számítógépi grafikába. Debrecen. Debreceni Egyetem Informatikai Kar - mobiDIÁK, 2003. A jegyzet C++ példa programjai letölthet k innen: http://mobidiak.inf.unideb.hu/mobi prog.hu http://www.prog.hu/cikkek/katalog/4120/3D+jatek-grafika.html
- 55 -
