Bevezetés a számítógépi grafikába - Schwarcz Tibor

Országok listájaHungaryDebreceni EgyetemInformatikai KarProgramtervező informatikusBevezetés A Számítógépi GrafikábaJegyzetekBevezetés a számítógépi grafikába - Schwarcz Tibor

Schwarcz Tibor

BEVEZETÉS A SZÁMÍTÓGÉPI GRAFIKÁBA

mobiDIÁK könyvtár

Schwarcz Tibor

BEVEZETÉS A SZÁMÍTÓGÉPI GRAFIKÁBA

2

mobiDIÁK könyvtár SOROZATSZERKESZT Fazekas István

3

Schwarcz Tibor

BEVEZETÉS A SZÁMÍTÓGÉPI GRAFIKÁBA
Jegyzet
Els kiadás

mobiDIÁK könyvtár
Debreceni Egyetem

4

Lektor: Dr. Szabó József

Copyright Schwarcz Tibor, 2005 Copyright elektronikus közlés mobiDIÁK könyvtár, 2005 mobiDIÁK könyvtár Debreceni Egyetem Informatikai Intézet 4010 Debrecen, Pf. 12. Hungary http://mobidiak.inf.unideb.hu/

A m egyéni tanulmányozás céljára szabadon letölthet. Minden egyéb felhasználás csak a szerz elzetes írásbeli engedélyével történhet. A m ,,A mobiDIÁK önszervez mobil portál" (IKTA, OMFB-00373/2003) és a ,,GNU Iterátor, a legújabb generációs portál szoftver" (ITEM, 50/2003) projektek keretében készült.

5

1

Történeti áttekintés, grafikus hardwer eszközök, szabványok .... 11
1.1 1.2 1.3 A számítógépi grafika történetének néhány kiemelked eseménye:..... 11 Néhány lehetséges felhasználói terület: ................................................ 12 Grafikus output eszközök:..................................................................... 12 Monitorok...................................................................................... 12 Rajzgépek ...................................................................................... 14 Egyéb grafikus eszközök:.............................................................. 15 A legfontosabb grafikus szabványok: ................................................... 16 Rasztergrafikus szabvány (SRGP) ................................................ 16 Vektorgrafikus szabványok........................................................... 19

1.3.1 1.3.2 1.3.3 1.4 1.4.1 1.4.2

2

Alapvet rasztergrafikai algoritmusok......................................... 21
2.1 2.1.1 2.1.2 2.1.3 2.2 Szakasz rajzolása................................................................................... 21 Szimmetrikus DDA ....................................................................... 21 Egyszer DDA .............................................................................. 22 Midpoint algoritmus ...................................................................... 22

Kör rajzolása.......................................................................................... 25 Midpoint algoritmus ...................................................................... 26

2.2.1 2.3

Vágó algoritmusok ................................................................................ 30 Cohen-Sutherland szakasz vágóalgoritmus (vágás téglalapra) ..... 30 Szakasz vágása konvex poligonra: ................................................ 31 Szakasz vágása konkáv poligonra: ................................................ 31 6

2.3.1 2.3.2 2.3.3

2.3.4 ablakra 2.4

Sudherland-Hodgman poligon vágó algoritmus 32

téglalap alakú

Kitöltés .................................................................................................. 33 Színinformáción alapuló eljárások ................................................ 33 Csúcsaival adott poligon kitöltése................................................. 35 Kitöltés mintával ........................................................................... 39 Élsimítás (Anti-aliasing)........................................................................ 39 Súlyozatlan antialiasing:................................................................ 40 súlyozott antialiasing:.................................................................... 40 Super-sampling.............................................................................. 40

2.4.1 2.4.2 2.4.3 2.5 2.5.1 2.5.2 2.5.3

3

Tanszformációk............................................................................ 41
3.1 3.2 3.2.1 3.2.2 3.2.3 3.3 2D-s transzformációk ............................................................................ 42 Eltolás.................................................................................................... 42 Forgatás origó körül ...................................................................... 43 Skálázás ......................................................................................... 43 Window to viewport-transzformáció............................................. 44

Térbeli pont-transzformációk ................................................................ 45 Egybevágósági transzformációk (mérettartó transzformációk): ... 45 Hasonlósági transzformációk (arányosságtartó transzformációk): 46 Affin transzformációk: .................................................................. 46 Koordináta-transzformációk.................................................................. 47 7

3.3.1 3.3.2 3.3.3 3.4

4

Paraméteres görbék ...................................................................... 48
4.1 4.2 4.3 4.4 4.5 4.5.1 4.5.2 4.5.3 4.6 Interpoláció............................................................................................ 49 Approximáció........................................................................................ 49 Harmadrend paraméteres görbék......................................................... 50 Matematikai folytonosságok ................................................................. 52 Hermite-interpoláció (3. rend)............................................................. 52 4 pontra illeszked Hermit-ív........................................................ 53 3 pontra illeszked Hermit-ív, ha adott az els pontban az érint:54 2 pontra illeszked Hermit-ív, ha adottak az érintk is:................ 55

Bézier-approximációs ívek.................................................................... 56 Harmadrend Bézier görbék csatolása. ......................................... 57

4.6.1 4.7 4.8

B-spline görbe elállítása ...................................................................... 58 Bézier-görbe elállítása Berstein polinommal ...................................... 61 A kontrollpontok multiplicitása..................................................... 61 Bézier-görbe elállítása de Casteljau-algoritmussal ..................... 62 Interpoláló Bézier-görbe elállítása .............................................. 63

4.8.1 4.8.2 4.8.3

5

Tér síkra való leképezései ............................................................ 64
5.1 5.2 Centrális vetítés ..................................................................................... 64 Axonometria.......................................................................................... 65 Kavalier axonometria: ................................................................... 65

5.2.1 5.3

Párhuzamos vetítés ................................................................................ 66 8

6

Felületek ....................................................................................... 66
6.1 6.2 Coons-foltok (felület interpoláció)........................................................ 67 Bikubikus felületek................................................................................ 69 Hermite felület............................................................................... 71 Felületi normálisok........................................................................ 72

6.2.1 6.2.2 6.3

Poligonokkal határolt felületek ............................................................. 73 Explicit reprezentáció.................................................................... 73 Mutatók a csúcslistába................................................................... 74 Mutatók az éllistába....................................................................... 74

6.3.1 6.3.2 6.3.3

7

Testmodellezés ............................................................................. 75
7.1 7.2 7.3 7.4 7.5 Reguralizált halmazmveletek .............................................................. 75 Sepert testek (SWEEP representation) .................................................. 76 Felületmodell (Boundary representation, B-rep)................................... 77 Cella módszerek (Volume visualisation) .............................................. 77 Térfogat modell (CSG: Constructive Solid Geometry)......................... 79

8

Láthatósági algoritmusok ............................................................. 80
8.1 8.2 8.3 Hátsó lapok eltávolítása (back-face culling) ......................................... 80 Robert-féle algoritmus........................................................................... 81 Listaprioritásos algoritmusok ................................................................ 81 Mélységi rendez algoritmus (fest algoritmus, Newell, 1972) ... 81 Bineáris térfelosztási fa (BSP) ...................................................... 82 9

8.3.1 8.3.2

8.4 8.5 8.6 8.7 8.7.1

Scan-line algoritmusok.......................................................................... 85 A z-buffer vagy mélység tároló algoritmus........................................... 87 Terület-felosztásos algoritmus .............................................................. 88 Sugárkövetéses algoritmusok (raytracing) ............................................ 89 Rekurzív sugárkövetés .................................................................. 91 A raytracing mveletigényét csökkent eljárások......................... 92

8.7.2

9

Színelméleti alapok ...................................................................... 93
9.1 9.2 9.3 9.4 9.5 RGB színrendszer:................................................................................. 93 CMY színrendszer:................................................................................ 94 CMYK (vagy 32 Bit Color): ................................................................. 94 HLS szinrendszer: ................................................................................. 95 Egyéb lehetségek................................................................................. 95

10
10.1 10.2 10.3 10.4 10.5 10.6

Egyszer megvilágítás és árnyalási technikák ......................... 95
Szórt háttérvilágítás (ambient light) ...................................................... 96 Diffúz fényvisszaverõdés (diffuse light) ............................................... 96 Fényvisszaverdés (specular light) ....................................................... 96 Konstans árnyalás (Flat shading) .......................................................... 96 Gouraud féle árnyalás............................................................................ 96 Phong árnyalás ...................................................................................... 97

10

1 Történeti áttekintés, grafikus hardwer eszközök, szabványok
1.1 A számítógépi grafika történetének néhány kiemelked eseménye:

· ·

·
· ·

1950. A Whirlwind Computer által kifejlesztett els valósidej grafikus megjelenít 1963. IVAN E. SUTHERLAND 'Sketchpad' rajzoló rendszerének kifejlesztése. Az els ,,on line" mköd grafikus rendszer. 1964. GM DAC rendszer-az els grafikus konzol, grafikus parancsokat is értelmez rendszer. Fénytoll bevezetése. 1964 Az els CAD rendszer kifejlesztése az IBM és GM közös projektjében. 1965 Az egér bevezetése (fából és manyagból készítette Douglas Engelbart.)

· 1973 Sharp (Japán) kifejlesztetee az LCD (Liquid Crystal Display) monitort. 20 év kellett az elterjedéséhez. · 1974 A Phillips cég els videó-telefonja. · 1975 Az els fraktállal kapcsolatos publikációja Mandelbrotnak.

11

· ·

1977 A személyi számítógépek korszakának kezdete. Megalakul a Microsoft cég. 1980 A PC-k elterjedése beépített raszter grafikával (IBM,APPLE) bittérképek (pixel vagy pel), desktop-felület, window manager elterjedése.

1.2 Néhány lehetséges felhasználói terület:
· · · · · · · Felhasználói felületek (Pl. Windows) Interaktív diagrammok, hisztogrammok (2D vagy 3D ) Térképészet Orvostudomány Tervezés (AutoCAD) Multimédia rendszerek Tudományos kísérletek eredményeinek megjelenítése

1.3 Grafikus output eszközök:
1.3.1 Monitorok
A monitorok mködési elv szerint lehetnek · · raszteres vonalrajzoló vagy vektorgrafikus monitorok.

1.3.1.1 A monitorok által alkotott kép minséget meghatározó legfontosabb mszaki paraméterek
· · · · · · 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éppont-átmér: a képernyn 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épernyk számát. képkirajzolási üzemmód szerint interlace vagy noninterlace. Az elbbi 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.

1.3.1.2 A raszteres display mködési elve
Egyik fajtája a 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ó 12

fényfolt lesz a pixel. Az elektronágyúk elektronsugarat bocsátanak ki, amelyet vízszintes és függleges irányban elektromágnesek segítségével eltérítenek. Színes képerny esetén 3 alapszínbl épül fel egy pixel. (RGB)

Az LCD (Liquid Crystal Display, folyadékkristályos kijelz) monitorok. Mködési elvük: a hátulról érkez fehér fényt az adott képpontban elhelyezked olyan szerkezet ereszti át vagy zárja el, amely a fényátereszt képességét az áramersség függvényében változtja

1.3.1.3 Monitor és videokártya típusok
Legfontosabb jellemzje a frissítési frekvencia, színmélység, felbontás, melyek nem független adatok. Egy pixel színinformációjának tárolására rendelkezésre álló bitek száma határozza meg a színek számát, azaz a rendelkezésre álló videó-memória nagysága határozza meg a maximális felbontást is. 1 bit, 2 szín 4 bit 16 szín 8 bit, 256 szín 16 bit, 65536 szín = High color 24 bit, 16 millió szín. = True Color Idrendi kialakulás: 1980-ban CGA : 320 * 200-as felbontásnál 4 szín , 640*200-as felbontásnál 2 szín

13

· · · ·

1984-ban MDA/HERKULES : 720*348-as felbontásnál 2 szín 1984-ban EGA : 640*350-as felbontásnál 16 szín 1987-ban VGA : 640*480-as felbontásnál 16 szín, 320*200-as felbontásnál 256 szín 1990-ban SVGA VESA szabvány

640*480 800*600 1024*768 1280*1024 1600*1200

256 szín 32K 64K 164 ezer szín 16M 16 millió szín TRUE COLOR

1.3.2 Rajzgépek
A rajzgépek egy íróhegyet vezetnek a papíron. A rajz a toll két egymásra merleges, X-Y irányú mozgásával jön létre. Síkplotterek esetében a rajzlapot egy táblán rögzítik, mely fölött az írócsúcs két, egymásra merleges irányban mozog. A görgs papírmozgatású rajzgépnél a toll csak egy irányban mozog, a rá merleges irányú vezérlést görgk végzik, behúzva a rajzlapot a megfelel helyzetbe.

Egy plottert a következ jellemzk alapján minsíthetünk: - befogható rajzlap mérete - rajzlap anyaga (papír, film, pausz, manyag, stb.) - tollak száma (színek, különböz vonalvastagságok változtathatósága)

14

- használható tollfajta (meghatározza a rajz minségét; lehet: tustoll, golyóstoll, rostirón, kerámiahegy toll, stb.); - gyorsulás (a toll nyugalmi helyzetbl indulva mennyi id alatt éri el a maximális sebességét); - tengelyirányú tollsebesség (ez a toll maximális rajzolási sebessége); - pontosság ;

rajzgépek

analóg digitális elektrosztatikus

digitális

digitális-analóg egyéb

inkrementális

Sík asztalos

dobos

1.3.3 Egyéb grafikus eszközök:
fénytoll egér pozícionáló-gomb scanner printerek

15

1.4 A legfontosabb grafikus szabványok:
3D Core Graphics System ­alacsony szint, eszközfüggetlen grafikus rendszer (1977) SRGP-Simple Raster Graphics Package GKS: Graphical Kernel System -2D az els hivatalos grafikai szabvány (1985) GKS 3D kiterjesztése (1988) PHIGS Programmer's Hierarchical Interactive Graphic System (1988) PHIGS PLUS (ANSI/ISO 1992)

1.4.1 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 legalapvetbb 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 paramé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 rasztergrafikus funkcionalitást biztosítják.
A Borland cég úgynevezett BGI grafikájának felépítése: Primitívek:

· · · · ·

szakaszok, poligonok, körök, ellipszisek, szöveg

16

Konstansok és típusok

Konstansok · · · · · · · · · · · Bar3D Constants BitBlt Operators Clipping Constants Color Constants Graphics Colors for the 8514 Fill Pattern Constants Graphics Drivers Graphics Modes for Each Driver Justification Constants Line-Style and Width Constants Text-Style Constants

Típusok · · · · · · · · · ArcCoordsType FillPatternType FillSettingsType Memory Pointers LineSettingsType PaletteType PointType TextSettingsTyp ViewPortType

ATTRIBÚTUMOK

Színek: procedure SetColor(Color: Word); Sötét színek: (Tinta & Papír) · · · · · · · · Black Blue Green Cyan Red Magenta Brown LightGray 0 1 2 3 4 5 6 7 · · · · · · · · Világos színek: (Tinta) DarkGray LightBlue LightGreen LightCyan LightRed LightMagenta Yellow White 8 9 10 11 12 13 14 15

17

Kitöltések és minták: Procedure SetFillStyle(Pattern: Word; Color: Word); Konstans · · · · · · · · · · · · · EmptyFill SolidFill LineFill LtSlashFill SlashFill BkSlashFill LtBkSlashFill HatchFill XhatchFill InterleaveFill WideDotFill CloseDotFill UserFill Érték 0 1 2 3 4 5 6 7 8 9 10 11 12 Jelentés Háttérszín Tintaszín ---- kitöltés /// kitöltés /// sr kitöltés \sr kitöltés \ kitöltés Négyzetrács kitöltés Négyzetrács kitöltés Interleaving line Widely spaced dot Closely spaced dot User-defined fill

Minták:

Vonal fajták és vastagságok: procedure SetLineStyle(LineStyle: Word; Pattern: Word; Thickness: Word);

Line Styles: · · · · · SolidLn 0 DottedLn 1 CenterLn 2 DashedLn 3 UserBitLn 4 (User-defined line style)

Line Widths: · NormWidth 1 · ThickWidth 3

18

1.4.2 Vektorgrafikus szabványok

1.4.2.1 A GKS és a GKS-3D:
Az els nemzetközi grafikai szabvány a német kezdeményezés alapján kidolgozott grafikus magrendszer (Graphical Kernel system = GKS), mely a 2D-s vektorgrafikára vonatkozott. A célkitzések és követelmények, melyeket a GKS szabvánnyal el akartak érni a következk voltak: · · · egységes illesztési helyet meghatározni a grafikus rendszerek és az egyedi alkalmazások között, a felhasználástól független, számítástechnikailag hatékonyan realizálható könyvtár definiálása a vektorgrafikus rendszerek fontosabb funkcióira, a grafika területén minél több általánosítható követelményt lefedni a szabvánnyal, elválasztania grafikus rendszerek alap- (ún. mag) funkcióit a magasabb szint modellezési funkcióktól, a szabvánnyal egy fejlesztési irányt mutatni a készülékgyártók számára. Az egyre teljesítképesebb hardverek eredményezték a GKS szabvány továbbfejlesztését. Így jött létre a GKS-3D szabvány, melyben a GKS-t 3D eljárásokkal és funkciókkal bvítették. A GKS szabványt több hardver és operációs rendszer platformon is megvalósították. Ezek számítógépes megjelenési formájukat tekintve legtöbbször egy alprogram könyvtárban öltenek testet. Ezért a grafikus szoftverfejlesztk a GKS-t tulajdonképpen egy felhasználói programozói interfész (APl) formájában látják.

A GKS a GKS-3D funkciókkal kiegészítve a vektorgrafika következ területeit fedi le: · · · · · színkezelés (színpaletta definiálása), transzformációk (vetítés, 3D-s ablak definiálás stb.), grafikus primitívek (sokszög, kitöltött terület, 2 és 3D-s szöveg stb.), koordináta-rendszer, skálázás, rácsok, objektumok definiálása (kör, téglatest, ellipszoid stb.), 19

· · ·

térgörbék és felületek definiálása (kontúrvonalak, háromszög közelítés felületek, függvénnyel megadott felület háromszög-közelítéssel stb.), láthatósági eljárások (huzalvázas megjelenítés, árnyalt felületek, poligonok rendezése, fedettség szerint stb.).

Ezeket a funkciókat a programozó a GKS könyvtárban lév programok felhívásával érheti el, mely alprogramokat fordítást követen bekapcsol a programjába.

1.4.2.2 A PHIGS, PHIGS+ és a PEX:
A PHIGS a szabvány angol elnevezésének: Programmers Hierarchical Interactive Graphics System rövidítésébl származik. Ezek szerint a PHIGS programozók hierarchikus, interaktív grafikus rendszere. A PHIGS szabvánnyal fként a tervezszoftverek egységesítését szerették volna elérni, a norma funkcionalitását tekintve dönten megegyezik a GKS-3D-vel. A lényeges különbségeket a szabvány neve is kifejezi: a PHIGS támogatja a vektorgrafikus objektumok közötti hierarchikus kapcsolatok felépítését, ezeket egy modell-adatbankban az ún. CSS-be (Central Structure Storage) a központi struktúra-tárolóba integrálja az adatbázis-szerkezet a szabványban úgy került megfogalmazásra, hogy a programok a modelltér mveleteket interaktív módon is képesek legyenek végrehajtani. A PHIGS szabvány - melynek kapcsolata a legfontosabb programnyelvekkel, így például FORTRAN, ADA, C is kidolgozásra került - a programozó számára egy hatékony eszközt biztosított a 3D-s objektumok adatbázisban való feldolgozásához. Az 1990-es évek elejére viszont a grafikus hardver teljesítményének növekedése és a realisztikus képelállítást biztosító renderelés igénye egyaránt szükségessé tette a szabvány továbbfejlesztését. A PHIGS+ szabványt 1992 végén adták ki. Ez már a túl absztrakt huzalvázas megjelenítést meghaladva kitér a különböz megvilágítási és árnyalási modellekre és eljárásokra is, és beépíti a szabványba a térbeli görbék és felületek modellezésének legújabb eredményeit. A PHIGS a PHIGS+ bvítéssel a következ elemekbl épül fel:

20

· A primitívek egyik csoportja geometriai, ide tartoznak a szokásos poligonok, poliéderek kitöltött felületek, NURBS stb. Emellett a szabvány ismeri a szöveges és raszteres primitívek mellett a különböz mennyiségi (matematikai, statisztikai) primitíveket és a speciális szervezési primitíveket is (például egy úthálózat gráfja). a primitívekhez egyedi és csoporttulajdonságok is hozzárendelhetk, például színmodellek. · A primitívekbl tárgymodelleket állíthatunk össze és ezeket struktúrákba szervezhetjük. A CSS lehetvé teszi a primitívek, tárgymodellek és struktúrák adatbázisszer feldolgozását. · A CSS objektumaira a szokásos adatbázis-mveletek (visszakeresés, létesítés, törlés, csoportosítás) mellett végrehajthatjuk a vektorgrafikában szokásos transzformációkat is (skálázás, mozgatás, koordináta-rendszer választása stb.). · A modelltér jeleneteit különböz nézpontokból ábrázolhatjuk, ehhez a szabvány biztosítja a szükséges 3D-2D-s vetítéseket és kivágást. · A megjelenítéshez a PHIGS ismeri a láthatósági és megvilágítási és árnyalási modelleket. · A felhasználóval való kapcsolattartás eszközeként alkalmazhatók a lokátor eszközök, a poligon rajzolás, a kijelölés, értékadás stb.
A PEX (PHIGS Extension on X) az X-Windows-System bvítése a PHIGS-hez, illetve a PHIGS+ -hoz. Ez egy illesztési helyet ad meg a PHIGS és a XII között, ami lehetvé teszi az X szerver szolgáltatások igénybevételét a PHIGS-en belül. A PEX által támogatott elemek: képerny, pixeles bitmap-ek, billentyzet és egér, és CSS.

2 Alapvet rasztergrafikai algoritmusok
A modellezés során arra a kérdésre keressük a választ, hogy hogyan lehet folytonos geometriai alakzatokat képpontokkal közelíteni. Azokat az algoritmusokat, melyek erre megadják a választ, digitális differenciaelemz (DDA) algoritmusoknak nevezzük

2.1 Szakasz rajzolása
2.1.1 Szimmetrikus DDA
Az egyenes r (t ) = r0 + tv vektor-skalár elállításán alapszik. A szakasz meghatározó A( x1 , y1 ) és B( x2 , y2 ) pontokból képezzük a x = x2 - x1 és y = y2 - y1 különbségeket. Meghatározzuk az

= 2- n értéket, ahol 2n -1 max( x , y ) < 2n és egy x és y regiszter
21

tartalmát növeljük az x és y értékekkel. Az egész túlcsordulásoknál megjelenítjük a pontot.

2.1.2 Egyszer DDA
Ekkor az x vagy y irányban egyesével lépkedünk, azaz a x = 1vagy y = 1
Csak egy regisztert használunk, és egész túlcsordulás esetén lépünk a megfelel irányba.

2.1.3 Midpoint algoritmus
Bárhogyan is származtassuk az egyenest, az egyenlete: ax+by+c=0 alakra hozható, ahol a és b egyszerre nem lehet nulla.

22

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.

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 felezpont (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 az E-t. Az M pont helyzetét analitikusan határozzuk meg. Az egyenes egyenletét az F ( x, y ) = ax + by + c = 0 formában tekintjük, ahol a = ( y2 - y2 ), 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:

23

1 1 d = F ( M ) = F ( x p + 1, y p + ) = a( x p + 1) + b( y p + ) + 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ébl 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 d new = F ( M E ) = F ( x p + 2, y p + ) = a( x p + 2) + b( y p + ) + c = d old + a, 2 2 azaz ekkor d-t E = dnew - dold = a -val kell növelni. Ha az NE pontot választjuk, akkor 3 3 d new = F ( M NE ) = F ( x p + 2, y p + ) = a( x p + 2) + b( y p + ) + c = d old + 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 P ( x1 , y1 ), azaz ( x0 , y0 ) := ( x1 , y1 ), ekkor a d kezd értéke: 1
b b 1 d 0 = F ( x1 + 1, y1 + ) = ax1 + by1 + c + = F ( x1 , y1 ) + a + , 2 2 2

de a P ( x1 , y1 ) pont rajta van az egyenesen, így d0= a+b/2. Ahhoz, hogy a 1 kettvel való osztást elkerüljük definiáljuk át az F(x,y) függvényt:
F ( x, y ) = 2 ( ax + by + c )

Ezt megtehetjük, mert csak a d eljelére van szükség és a 2-vel való szorzás ezt nem változtatja meg. Ekkor d0=2a+b,

E =2a, és 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.

24

A rutin kódja:
procedure Line(x1,y1,x2,y2:integer); var a,b,x,y,d,deltaE,deltaNE:integer; begin a:=y1-y2; b:=x2-x1; d:=2*a+b; { d kezdértéke } deltaE:=2*a; { d növekménye E esetén } deltaNE:=2*(a+b); { és NE esetén } x:=x1; { a kezdpont } y:=y1; { koordinátái } WritePixel(x,y); while x=0 then begin { E } d:=d+deltaE; x:=x+1; end else begin { NE } d:=d+deltaNE; x:=x+1; y:=y+1; end; WritePixel(x,y); end; { while } end;

2.2 Kör rajzolása
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

25

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. Ebbl 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

2.2.1 Midpoint algoritmus
Szeretnénk meghatározni egy adott (u,v) középpontú és r sugarú kör adott raszterhez tartozó pontjait. Az egyik lehetséges megoldás, ami eszünkbe juthat a trigonometrikus függvényeket használja az x = r cos(t ) + u , y = r sin(t ) + v

összefüggések segítségével határozza meg a kör pontjait. Számunkra ez a módszer most nem megfelel, mert a trigonometrikus függvények kiszámolása, ami valós aritmetikát követel meg, túlságosan sok idt vesz igénybe. Rekurziót alkalmazva lehet valamelyest gyorsítani az algoritmuson, de az így kapott algoritmus sem elég gyors, és a vonalrajzolásra megfogalmazott követelményeinknek sem tesz eleget. Semmi sem garantálja azt, hogy a vonal vastagsága egyenletes és folytonos lesz. De ahelyett, hogy számba vennénk a számunkra nem megfelel módszereket, nézzünk meg egy igen hatékony algoritmust és annak egy gyorsítását. Ez az algoritmus a szakasz rajzolásnál tárgyalt midpoint algoritmus továbbfejlesztése.
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.

26

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 a helyzet), 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 eltt a pontokat az (u,v) vektorral eltoljuk, s így a kívánt helyzet kört kapjuk
Elsrend 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 érintjé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 felezpontjá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:

27

1 1 d = d old = F ( M ) = F ( x p + 1, y p - ) = ( x p + 1) 2 + ( y p - ) 2 - r 2 2 2

· Ha d<0, akkor az E-t választjuk, és ekkor
1 1 d new = F ( M E ) = F ( x p + 2, y p - ) = ( x p + 2) 2 + ( y p - ) 2 - r 2 = d old + 2 x p + 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 d new = F ( M SE ) = F ( x p + 2, y p - ) = ( x p + 2) 2 + ( y p - ) 2 - r 2 = d old + 2( x p - y p ) + 5 2 2 vagyis

SE = 2(xp-yp)+5.
Vegyük észre, hogy míg az egyenes rajzolásánál a E, SE elsrend 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.Elször meg kell határoznunk a kezdeti értékeket. Az algoritmus a (0,r) pontból indul, így: d0 = F(1,r-1/2)= 5/4-r . Látható, hogy ekkor d0 nem egész. Ahhoz, hogy egészekkel tudjunk számolni d helyett, tekintsük a d' = d - 1/4 változót. Így d'0 = 1 - r. Ekkor a d<0 feltétel helyett d' < -1/4 feltételt kell vizsgálni, viszont ez is valós aritmetikát feltételez. Mivel d'0, E és SE is egészek d' mindig egész lesz, így egyszeren tekinthetjük a d'<0 feltételt.

28

procedure CircleFirst(u,v,r:integer); var xp,yp,d:integer; begin xp:=0; { kezd értékek } yp:=r; d:=1-r; CirclePoints(u,v,xp,yp); while yp>xp do begin if d<0 then begin { E } d:=d+xp*2+3; xp:=xp+1; end else begin { SE } d:=d+(xp-yp)*2+5; xp:=xp+1; yp:=yp-1; end; CirclePoints(u,v,xp,yp); end; end;

29

2.3 Vágó algoritmusok
2.3.1 Cohen-Sutherland szakasz vágóalgoritmus (vágás téglalapra)
A leghatékonyabb a Cohen-Sutherland 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 0. bit egyes, ha a pont balra esik a baloldali képernyéltl. Az els bit egyes, ha a pont jobbra esik a jobboldali képernyéltl. A második bit egyes, ha a pont az alsóíél alatt van. A harmadik bit egyes, ha a pont a fels él felett van. Ha a szakasz 2 végpontjához rendelt kód csupa nulla, akkor a szakasz a képernyn belül van. Ha a két kódnak van olyan bitje, hogy azonos helyi értéken egyes van, akkor az a szakasz eldobható, mert a képen kívülre esik. 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. Elnyei: hatékony, ha nagy valószínséggel kívül esnek a szakaszok a

30

képernyn; 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ó.

2.3.2 Szakasz vágása konvex poligonra:
A vizsgált egyenes egyenletébe behelyettesítjük a poligon csúcsainak

koordinátáit, és tároljuk az eredmény eljelét.. Ha mindenhol azonos az eljel, akkor az egyenes a poligonon kívül esik. Ha a kapott eljelsorozat egymást követ elemei különböznek, akkor a két csúcs által meghatározott szakaszt metszi a vágandó szakasz egyenese. Csak két helyen lehet eljelváltás, mivel konvex a poligon. Kiszámítjuk a szakasz egyenesének és a poligonnak a metszéspontjait, majd valamely (nem nulla) koordináta szerint rendezzük a négy pontot. Megrajzoljuk a megfelel két pont között a szakaszt.

2.3.3 Szakasz vágása konkáv poligonra:
Behelyettesítjük a poligont alkotó csúcsok koordinátáit a vágandó szakasz egyenesének egyenletébe. A kapott értékek eljeleit figyelve az eljelváltások esetén az aktuális poligon él metszi a szakasz egyenesét. Kiszámítjuk 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.

31

2.3.4 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 élrl van szó, A már rajta volt) 3. A bennt van, B kinn: Az ablak él és AB metszéspontja felkerül a listára 4. B benn van, A kinn: elször AB és az ablak él metszéspontja, majd B is felkerül a listára.
KINN A
BENN

KINN A

BENN

KINN A

BENN

KINN A

BENN

B

B

B

B

32

Konkáv alakzat esetén az is elfordulhat, hogy több poligon lesz a vágás végeredménye.

2.4 Kitöltés
Egy kitöltend zárt alakzat (poligon) kétféle módon lehet megadva. Az alakzatot határoló ,,görbe" ­azaz szomszédos pixelek sorozata ismert, a háttérszíntl eltér határszín által, vagy a poligon csúcsainak koordinátái ismertek. Ezek alapján kell a bels pixeleket megtalálni, melyeket színezni akarunk.

2.4.1 Színinformáción alapuló eljárások

2.4.1.1 É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 to ymax for x=xmin to xmax do begin if ( getpixel(x,y)=hatarszin ) flag:=!flag; if (flag) putpixel(x,y,szin); end;

2.4.1.2 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 igénye van, és viszonylag lassú.

33

A kód:
flood_fill(x,y) if (getpixe(x,y) == hatterszin begin putpixel(x,y,szin) flood_fill(x+1,y); flood_fill(x-1,y); flood_fill(x,y+1); flood_fill(x,y-1); end;

Vagy közvetlen memóriacímekre való hivatkozással
flood_fill(cim) if (read_pixel(cim) == hatterszin begin write_pixel(cim,szin) flood_fill(cim+1); flood_fill(cim-1); flood_fill(cim+M); flood_fill(cim-M); end;

8 9 6 5 4 3 7 0 1 2 1 1

34

2.4.2 Csúcsaival adott poligon kitöltése

2.4.2.1 Téglalap kitöltése
Legegyszerbb egy a koordináta-tengelyekkel párhuzamos él téglalap kitöltése, ekkor ugyanis egy dupla ciklussal, melyek a 2-2 párhuzamos határoló élek között futnak, egyszer megtalálni a bels pixeleket. Az egymással közös élben érintkez téglalapoknál problémát jelent, hogy a két téglalap fillezésének sorrendjétl függen más szín lesz a közös él darab, és fellép egy ,,szrösödési" hatás. A probléma kezelésére megoldás, hogy a bels pixel definícióját úgy adjuk meg, hogy a déli és nyugati határoló élt bels élnek, míg az északi és keleti élt külsnek tekintjük.

2.4.2.2 Poligon-fillez módszer
Á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.

35

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 midle-pointot alkalmazunk

A midle-point szerinti széls pixelek

Az új ,,széls" pixelek

Felmerül problémák: · · · Az egész koordinátájú metszéspontok esetén bels vagy küls pixelként tekintsük a metszéspontot? Mi a teend ha csúcsponton halad át a scin-line? (A flag kétszer kapcsolna!) Mi a teend vízszintes élek esetén?

36

Megoldások: · · · Baloldali élnél belsként, jobb oldali élnél külsként definiáljuk. (Mint a téglalapnál) A paritásbitet csak a déli csúcs esetén állítjuk. A déli élet belsként, az északi élet külsként definiáljuk. Ez automatikusan bekövetkezik az elz pont alapján. F

G I H

E J

K

C

D

A Algoritmus:

B

Az algoritmus során használunk egy éltáblát (ET), melynek tulajdonságai: · · · az éltábla annyi elem, ahány scanline-unk van a tábla elemei listák, melyekben azon élekrl van adat, melyek az adott scanline-t metszik a vízszintes lista élei xmin koordinátájuk szerint vannak rendezve az adatok az élekrl: 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.

C-ben a megfelel adatstruktúra a következ: 37

typedef struct ETstruct{ int y; struct ETLstruct *etl; struct ETstruct *next; }ET; // eltabla typedef struct ETLstruct{ int x1,y2; double m; struct ETLstruct *next; }ETL; // eltablahoz tartozo //ellista typedef struct AETstruct{ double x; int y2; double m; struct AETstruct *next; }AET; // aktiv eltabla
Van egy aktív éltábla (AET) is hasonló tulajdonságokkal, csak ebben nem annyi elem van, ahány scan-line. Ez a tábla az algoritmus folyamán mindig változó

Az algoritmus lépései:

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övetkezket, 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 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 éleket az AET-bl, amelyekre y= ymax. 4.5. Minden nem függleges AET-beli élre x:=x+1/m

38

2.4.3 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.

Módszerek: 1. A mintát gondolatban fölmásoljuk a teljes képernyre (0,0)-tól, és ahol az alakzat van, ott átlátszóvá tesszük a képernyt. Ekkor a minta a képerny pixeljeihez van rendelve, tehát ha az objektum mozog, a minta nem fog vele együtt mozogni. Ha a minta egy mxn-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. 2. 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.)

2.5 Élsimítás (Anti-aliasing)
A szakasz rajzoló alap algoritmusok a ferde egyeneseket töredezetten ábrázolják. Az anit-aliasing módszer a ferde vonalak töredezettség mentes képének és a látványnak a javítására szolgál. A megtalált pixeleken túl különböz színintenzitással további pixelek vesznek részt az egyenes kirajzolásánál, így enyhíteni lehet az egyenes töredezettségét. Az elméleti szakaszra egy egy pixel szélesség téglalap tartományt fektetünk. Ha egy pixelnek van a téglalaptartománnyal közös része, akkor megfelel színintenzitással kirajzoljuk.

39

5 4 3 2 1
0

5 4 3 2 1 1 2 3
4 5 6 7 8 9 10 11
0

1 2 3

4 5 6 7

8 9 10 11

2.5.1 Súlyozatlan antialiasing:
Itt azt nézzük, hogy az adott pixelnek hány százaléka van lefedve a téglalappal, azaz a színintenzitás mértéke területarányos.

2.5.2 súlyozott antialiasing:
A pixeleket kör alakúnak feltételezzük, és egységnyi magasságú kúpokat illesztünk feléjük. A téglalaptartományra pedig ugyancsak egységnyi magasságú hasábot fektetünk, és a színintenzitást a térfogatarányoknak megfelelen állítjuk be. Ezzel a módszerrel nem csak a lefedettség mértéke, hanem a pixelnek az elméleti egyenestl való távolsága is figyelembe vevdik.

2.5.3 Super-sampling
Ez az elsimításnak egy másik módszere, melynek lényege, hogy az éleken elhelyezked pixeleket felbontjuk 4*4=16 darab további részre, melyeket subpixeleknek nevezünk. Ezek nem valódi képpontok. Ez azt jelenti, hogy a raszteres képpontokat elvileg egy nagyobb felbontásnak megfelelen számítjuk ki. Egy megjelenített pixel színe vagy szürkeségértéke ezt követen a hozzátartozó részpixelekhez rendelt értékek átlagaként kerül kiszámításra.

Elsimítás nélkül 40

Élsimítással

3 Tanszformációk
A r ( x, y, z ) r ( x , y , z ) hozzárendelést 3D-s transzformációnak nevezzük, ahol x = f1 ( x, y, z ) y = f 2 ( x, y , z ) z = f 3 ( x, y , z ) Az r vektor végpontjának megfelel pontokat tárgypontoknak, az r' vektorok végpontjának megfelel pontokat pedig képpontoknak nevezzük. A számítógépes grafikában két olyan transzformációval találkozunk, amelyek matematikailag teljesen azonos formában írhatók le, ugyanakkor lényegüket tekintve eltérek. Ezek a koordináta-transzformáció és a pont-transzformáció. Koordináta-transzformációról akkor beszélünk, ha a tárgypont egy új koordinátarendszerre vonatkozó koordinátáit határozzuk meg, a régiek ismeretében. Ilyenkor tehát a vizsgált tárgy változatlan, csupán nézpontunkat változtatjuk meg. A grafikus objektum változatlan marad. Ilyenre például akkor van szükség, ha a nézpontunkat változtatjuk 3D-ben. Pont-transzformációról akkor beszélünk, ha a grafikus objektum pontjaihoz új pontokat rendelünk hozzá. A hozzárendelés módjától függen a tárgyalandó transzformációk lehetnek egybevágósági, hasonlósági, affin vagy projektív transzformációk. A dimenzió vesztéssel járó transzformációkat leképezéseknek nevezzük.

41

A térbeli tárgyaknak a számítógépes grafikában való feldolgozása során koordináta- és pont-transzformációt is alkalmazunk. Elbbi jellegzetesen a tárgyhoz képest elfoglalt nézpontunk változtatása esetén szükséges, utóbbi pedig a testek különböz mozgatásainak, nagyításának, vetítésének matematikai leírására szolgál. Koordináta-transzformációt végezve a transzformáció kölcsönösen egyértelm, hiszen új koordináták is maradéktalanul rzik az eredeti információtartalmat. A pont-transzformációknál viszont elfordulhat, hogy a tárgy és a kép pontjainak kapcsolata nem mindig kölcsönösen egyértelm. Gondoljunk például a 3D-s modelltér leképzésére 2D-s nézetre. Ez tipikus esete az elfajuló transzformációnak. A transzformációk egységes kezelése végett úgynevezett homogén koordinátákat vezetünk be. A 3 dimenziós projektív teret a valós 4 dimenziós vektortérbe ágyazzuk be, a projektív tér pontjainak reprezentálása a zérus vektortól különböz 4 dimenziós vektortér vektorainak egy-egy osztályával történik. Egy osztályba tartoznak a lineárisan függ vektorok, vagy másképp az egymással arányos számnégyesek ugyanazt a pontot reprezentálják. Ezeket a koordinátákat nevezzük homogén koordinátáknak. Ha a pont negyedik koordinátája nem zérus, akkor a pont E 3 -nak is pontja, egyébként a pontot végtelen távoli pontnak nevezzük. A végesben lév pontok inhomogén koordinátáit megkapjuk, ha a negyedik koordinátával elosztjuk a pont els három koordinátáját: yi =
xi , ahol x4 0 . A x4

síkbeli homogén koordinátákat hasonlóan értelmezzük, a pontokat és az egyeneseket valós számhármasok egy-egy osztályával jellemezzük.

3.1 2D-s transzformációk 3.2 Eltolás
Inhomogén alak:
x = x + d x , y = y + d y

42

mátrix alakban: dx x x P = , P = , T = y y d y P = P + T

Homogén alak:
x x 1 0 d x y , P = y , T = 0 1 d P= y 1 1 0 0 1 P = T · P x 1 0 d x x y = 0 1 d · y y 1 0 0 1 1

3.2.1 Forgatás origó körül
x = x cos( ) - y sin( ), y = x sin( ) + y cos( ) mátrix alakban: Inhomogén alak : x cos( ) - sin( ) x y = sin( ) cos( ) y P = R P Homogén alak : x cos( ) - sin( ) 0 x y = sin( ) cos( ) 0 y 1 0 0 1 1

3.2.2 Skálázás
y

Inhomogén alak:
x = s x x, y = s y y mátrix alakban: x sx 0 x y = 0 s y y P = S P

sx = 4; sy = 2

x

Homogén alak:
43

 x sx y = 0 1 0

0 sy 0

0 x 0 y 1 1

Ha sx=sy, akkor hasonlóságról, egyébként affinitásról beszélünk.

3.2.3 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épernyn lév részét kell kirajzolni. A vágás eltt 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 megfelelen skálázás és visszatolás. Ami kilóg a window-ból, az a viewport-ból is ki fog, azaz vágni kell.
y y (xmax,ymax) v v (umax,vmax)

(xmin,ymin) x Window x

(umin,vmin)

Eltolás az origóba

u

Skálázás

Viewport

u

1 0 - xmin Az Window origóba való eltolásának mátrixa: T1 = 0 1 - ymin . 0 0 1

umax x max A skálázás: S =

- umin - xmin 0 0

0 vmax - vmin ymax - ymin 0

0 0 1

1 0 umin Visszatolás a Viewportba: T2 = 0 1 vmin 0 0 1

44

Az eredményt e 3 mátrix szorzata adja: P = (T2 ST1 ) · P = umax x max - umin - xmin 0 0 0 vmax - vmin ymax - ymin 0 - xmin - ymin umax - umin umax - umin + umin ( x - xmin ) x - x + umin xmax - xmin max min x vmax - vmin vmax - vmin + vmin · y = ( y - ymin ) + vmin ymax - ymin ymax - ymin 1 1 1

3.3 Térbeli pont-transzformációk
A térbeli pont transzformációk mátrix reprezentációban homogén koordinátákat használva adjuk meg.

3.3.1 Egybevágósági transzformációk (mérettartó transzformációk):

3.3.1.1 Eltolás
Az eltolást a d(d x , d y , d z ) vektorral adjuk meg. Az eltolást leíró mátrix: 1 0 M = 0 0

0 1 0 0

0 dx 0 dy 1 dz 0 1

3.3.1.2 Forgatás szöggel
A térbeli forgatás nem pont körül, hanem egyenes körül értelmezett. Az alábbi mátrixok a koordináta tengelyek körüli forgatásokat írják le. 0 1 0 cos M = 0 sin 0 0 0 - sin cos 0 0 0 0 1
45

· x tengely körül

· y tengely körül

· z tengely körül

cos 0 sin 0 1 0 M = - sin 0 cos 0 0 0 cos - sin 0 sin cos 0 M = 0 0 1 0 0 0

0 0 0 1 0 0 0 1

3.3.1.3 Tükrözés az {x,y} síkra
1 0 M = 0 0

0 0 1 0 0 -1 0 0

0 0 0 1

3.3.2 Hasonlósági transzformációk (arányosságtartó transzformációk):

3.3.2.1 Kicsinyítés, nagyítás origó középponttal:
0 0 0 0 0 0 M = 0 0 0 0 0 0 1

Ha nagyobb mint egy, akkor nagyítás, ha pedig kisebb mint egy, akkor kicsinyítés történik.

3.3.3 Affin transzformációk:

3.3.3.1 Skálázás
Origóból történ, tengelyek menti nyújtás.

46

 0 M = 0 0

0 0 µ 0 0 0 0 0 0 1 0

3.3.3.2 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 + idt = P + i(np)t

tx ny t x nz x 1 + t x nx y t n 1 + t y ny t y nz y x = z t z nx 1 + t z nz tz ny 0 0 0 1

0 x 0 y 0 z 1 1

3.4 Koordináta-transzformációk
A 3D-s euklideszi térben egy K koordináta-rendszerrl egy K' koordinátarendszerre térünk át és feltételezzük, hogy ortonormált Descartes-féle koordinátarendszerekrl van szó. Jelölje i, j,k illetve i , j,k a két

koordinátarendszer egységvektorait, valamint d mutasson az eredeti rendszer kezdpontjából az új rendszer kezdpontjába. Elszö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 , i y , iz' , j x , j y , j z' , k x' ,k y ,k z' .

47

p = d + p = x i + y j + z k , vagy mátrix reprezentációban:
' x ix y ' = i y z iz' 1 0 ' jx ' jy

k x' ' ky k z' 0

jz' 0

d x x d y y d x z 1 1

Ha ez eredeti rendszerben ismertek egy pont koordinátái, és az új rendszerbeli elállítás szükséges, akkor

p = p - d egyenlségbl 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' - dj' z = p k ' = (p - d)k ' = pk ' - dk '

Mátrixreprezentációban az eredmény:
' x ix y ' = jx ' z kx 1 0 ' iy ' jy ' ky

iz' jz' k z' 0

0

' -di x ix ' -dj y jx = ' -dk z k x 1 1 0

' iy ' jy ' ky

iz' jz' k z' 0

0

' ' -d x ix - d y i y - d z iz' x ' ' - d x jx - d y j y - d z jz' y ' -d x k x' - d y k y - d z k z' z 1 1

4 Paraméteres görbék
A térbeli görbék modellezésének legfontosabb eszköze a paraméteres vektor függvény, mely alkalmazásával a síkbeli és térbeli görbéket hasonló módon írhatjuk le. Ez egy t r (t ), t [ a, b ] paraméteres vektor-skalár függvény megadását jelenti, ahol [a,b] a paramétertartomány. Az egyenlet

komponensekben:
x = x(t ) y = y (t ) z = z (t )

48

Síkgörbék esetében természetesen csak két komponens szükséges. Ezek szerint minden egyes t konkrét számértéket behelyettesítve, a függvény egy olyan konkrét r vektort állít el, mely a térgörbe egy pontjába mutat. Az r(t) függvényrl általában feltételezzük, hogy kölcsönösen egyértelm és folytonos leképzés, azaz egy konkrét t0 értékhez egy és csak egy r0 vektort rendelünk hozzá. Azt is feltételezzük, hogy t-szerint folytonosan differenciálható és deriváltja nem nulla. Az utóbbi kikötés szemléletesen azt jelenti, hogy a görbén nincsenek csúcsok, hegyes részek és az érintvektort a görbe bármely pontjában meg lehet húzni. Az érintvektort az r deriválásával kapjuk, azaz az x(t ), y (t ), z (t ) skalárfüggvény komponensekbl képzett differenciálhányadosából.

4.1 Interpoláció
A térbeli görbék közül azok kiválasztását, melyek a tér elre megadott P0 , P ,..., Pn 1 pontjain áthaladnak, egy interpolációs feladat megoldásának nevezzük. A síkbeli görbék esetében legyen adott a P0 , P ,..., Pn pontsorozat az r0 , r1 ,..., rn vektorokkal . 1 Keressük azt az t r (t ), t [ a, b ] vektor-skalár függvényt, mely kielégíti a következ feltételt: találhatóak olyan t0 , t1 ,..., tn paraméterértékek, hogy

r0 = r (t0 ) r1 = r (t1 )
. . . rn = r (tn ) teljesül. Ebben az esetben az r (t ) vektor-skalár függvényt interpolációs görbének, P0 , P ,..., Pn pontokat pedig az interpolációs görbe kontrollpontjainak nevezzük. 1

4.2 Approximáció
Ekkor egy görbecsaládból azt a görbét választjuk ki, mely az elre megadott P0 , P ,..., Pn térbeli pontokat megközelíti. Az approximációs görbe általában nem 1

49

halad át a megadott kontrollpontokon, hanem a kontrollpontok valamilyen módon hatnak a görbe alakjára. Ahhoz, hogy az interpolációs vagy approximációs eljárás a gyakorlatban is használható legyen, valamilyen módon szkítenünk kell a szóba jöhet végtelen sok r = r (t ) vektor-skalár függvény halmazát. Ezért az összes lehetséges r = r (t ) függvények közül csak a polinomokat vesszük figyelembe, azaz az
x(t ) = an t n + an -1t n -1 + ... + a0 y (t ) = bn t n + bn -1t n -1 + ... + b0 z (t ) = cn t n + cn -1t n -1 + ... + c0

alakú függvények között keressük a feladatnak megfelelket. Minél kisebb a polinom fokszáma, annál kevesebb mvelettel számíthatjuk ki a függvényértékeket, de túl alacsony fokszámú polinomot nem választhatunk, mivel akkor a bonyolultabb görbéket és felületeket nem lehetne jól közelíteni. Másodfokú polinom esetén:
x(t ) = a2 t 2 + a1t + a0 y (t ) = b2 t 2 + b1t + b0 z (t ) = c2 t 2 + c1t + c0

Ha másodfokúak a koordinátafüggvények, akkor a generált görbe síkbeli lesz. Ezért a térgörbék és felületek modellezésére a legalább harmadfokú polinomokat választották. Harmadfokú polinomokkal modellezhetk olyan geometriai tulajdonságok is, mint az önmetszés, csúcspont vagy az inflexiós pont.

4.3 Harmadrend paraméteres görbék
Általános alakban a koordináta függvények az alábbiak:
x(t ) = a3 t 3 + a2 t 2 + a1t + a0 y (t ) = b3 t 3 + b2 t 2 + b1t + b0 z (t ) = c3 t 3 + c2 t 2 + c1t + c0

Vezessük be az alábbi jelöléseket: 50

 a3 a2 C = b3 b2 c3 c2

a1 a0 b1 b0 , c1 c0

t 3 2 t T= t 1

x(t ) Q(t ) = y (t ) = C · T z (t ) 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 jellemzkkel rendelkez görbéket állítunk 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 érintk is. Jelölje G a geometria adatokból álló sorvektort, azaz
g11 G 4 ] = g 21 g31 g12 g 22 g32 g13 g 23 g33 g14 g 24 g 34

G = [G 1

G2

G3

A C matrixot 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 )

A B(t)=MT harmadfokú polinomokat súlyfüggvényeknek nevezzük. A görbe valamely t0 paraméter pontjában az érint vektor egyszeren származtatható:
3t 2 x(t ) y(t ) = C · T = G · M · T = G · M · 2t Q(t ) = 1 z (t ) 0

51

4.4 Matematikai folytonosságok
· C0 matematikai folytonosság: Ebben az esetben a két görbe darabnak az illesztési pontban lehet törése, de hézagmentesen csatlakozik a két rész. · C1 matematikai folytonosság: A két ívdarabnak az érintje is megegyezik, azaz koordinátafüggvényeik els deriváltja a csatlakozási pontban egyenl. · C2 matematikai folytonosság: Ebben az esetben a két ívdarabnak a csatlakozási pontban az érintje és a görbülete is megegyezik. Azaz a koordinátafüggvények els és második deriváltjának értéke is azonos. · G1 geometriai folytonosság: Ebben az esetben a két ívdarabnak a csatlakozási pontban nem kell azonos deriváltakkal rendelkeznie. Csak az érint egyenes azonos, de a derivált vektor nagysága és eljele ellenkez lehet.

4.5 Hermite-interpoláció (3. rend)
geometriai adat (pontok vagy érintk) g11 g12 g13 g14 G = [G 1 G 2 G 3 G 4 ] = g 21 g 22 g 23 g 24 és a t1 , t2 , t3 , t4 skalárok. g31 g32 g33 g 34 Keressük az M 4x4-es mátrixot, melyre teljesedik:
G1 = G iM iT1 G 2 = G iM iT2 G 3 = G iM iT3 G 4 = G iM iT3 vagy röviden G = G iM i[ T1 T2 T3 T4 ] , ahol T1 T2 T3 T4 oszlopvektorok, értékük vagy a t 3 3t 2 2 t vagy a T = 2t T= t 1 1 0 képlet alapján számolandó, aszerint, hogy pontról vagy elírt érintrl van szó. 52

Legyen

adva

4

A G = G iM i[ T1 T2 T3 T4 ] egyenlség akkor állhat fenn, ha

M i[ T1 T2 T3 T4 ] = E, azaz M = [ T1 T2 T3 T4 ] Konkrét esetek:

-1

4.5.1 4 pontra illeszked Hermit-ív
Adottak a
G = [ P1 P2 P3 P4 ]

pontok,

valamint

elírjuk,

hogy

a

t1 = -1, t2 = 0, t3 = 1, t4 = 2 paraméterekre:

Q(-1) = P , Q(0) = P2 , Q(1) = P3 , Q(2) = P4 1 Ekkor: 1 1 1 - 6 2 - 3 1 -1 - 1 2 =2 - 1 1 1 2 2 1 1 0 6 6 0 1 0 0

-1 1 M= -1 1

0 0 0 1

1 1 1 1

8 4 2 1

-1

1 1 1 - 6 2 - 3 0 t 3 1 -1 - 1 1 2 t 2 2 Q(t ) = [ P1 P2 P3 P4 ]i i = - 1 1 1 0 t 2 2 1 1 1 0 0 6 6 1 3 1 2 1 1 3 2 1 1 3 1 2 1 1 P1 i(- t + t - t ) + P2 i( t - t - t + 1) + P3 i(- t + t + t ) + P4 i( t 3 - t ), t [ -1, 2] 6 2 3 2 2 2 2 6 6

53

4.5.2 3 pontra illeszked Hermit-ív, ha adott az els pontban az érint:
G = [ P1 P2 P3 R 1 ] valamint legyen t1 = -1, t2 = 0, t3 = 1. Ekkor
-1

5 3 1 4 2 - 4 0 -1 0 1 3 1 0 1 -2 -1 -1 1 1 = 1 1 1 M= -1 0 1 1 0 4 2 4 1 1 1 0 1 1 0 0 2 2 5 3 1 4 2 - 4 0 3 t -1 -1 1 1 t 2 i = Q(t ) = [ P1 P2 P3 R 4 ]i 1 1 1 0 t 4 2 4 1 1 1 0 0 2 2 3 1 5 1 1 1 1 1 P1 i( t 3 + t 2 - t ) + P2 i(-t 3 - t 2 + t + 1) + P3 i( t 3 + t 2 + t ) + R 4 i( t 3 - t ), t [ -1,1] 4 2 4 4 2 4 2 2

54

4.5.3 2 pontra illeszked Hermit-ív, ha adottak az érintk is:
G H = [ P1 P2 R1 R 2 ] valamint legyen t1 = 0, t2 = 1. Ekkor 1 1 1 1 0 0 1 0 3 2 1 0
-1

2 -3 0 1 -2 3 0 0 = 1 -2 1 0 1 -1 0 0 2 -3 0 1 t 3 -2 3 0 0 2 i t = Q(t ) = [ P1 P2 R1 R 2 ]i 1 -2 1 0 t 1 -1 0 0 1 P1 i(2t 3 - 3t 2 + 1) + P2 i(-2t 3 + 3t 2 ) + R1 i(t 3 - 2t 2 + t ) + R 2 i(t 3 - t 2 ), t [ 0,1] Ha 2 helyett n darab pontot és érintt adunk meg, akkor a Hermite-ívekbl egy egész görbét tudunk elállítani. Ekkor az elz eljárást sorban el kell végeznünk az egymás után következ pontpárokra. Ekkor a görbe elsrendbeli folytonossága a kapcsolódási pontokban automatikusan érvényesül, mivel az i. ív végérintje megegyezik az (i+1). ív kezdérintjével (i=1, ... , n-1). A Hermite-íveknek a számítógépi grafikában történ alkalmazásában gondot okoz, hogy ezek a paramétertartomány affin transzformációira nem invariánsak.

0 0 MH = 0 1

55

Hermite-ívek összekapcsolása

4.6 Bézier-approximációs ívek
A harmadrend Bézier íveket a két pontjával és két érintjével adott Hermite ívre vezetjük vissza. A Hermit-ívtl eltéren itt az érintvektorok helyett is pontokat adunk meg, melyek befolyásolják a görbe alakját, bár a görbe nem megy át ezeken a pontokon. Legyen adva a Bézier ív 4 kontrollpontja, G B = [ P1
P2 P3 P4 ] . Elállítjuk azt

a Hermite-ívet, mely meghatározó adatai közül a két adott pont P1 és P4 ,és a hozzájuk tartozó érintk pedig a P1 P2 valamint a P3 P4 vektorok háromszorosa, azaz 3(P2 - P1 ) illeteve 3(P4 - P3 ) . A két mátrix között tehát a következ összefüggés van:
0 0 , 0 0 -3 1 0 3 1 0 0 0 Q(t ) = G B iM B iT = G H iM H iT = G B i 0 0 0 1 1 0 MB = 0 0 0 -3 0 1 0 -3 0 2 -3 0 0 3 0 -2 3 0 3 0 i iM H = 0 0 0 -3 1 -2 0 0 -3 1 0 3 0 1 0 3 1 -1 1 0 G H = G B i 0 0 0 -3 0 3

-3 0 3 0 iM H iT, 0 -3 0 3 0 1 -1 3 -3 1 0 0 3 -6 3 0 = 1 0 -3 3 0 0 0 0 1 0 0 0

56

A Bézier görbe elállításában szerepl MBT szorzat tulajdonképpen négy harmatfokú polinom, melyek az úgynevezett Bernstein-féle polinomok, n=3 esetben. Ez alapján a Bézier görbe így is felírható:
-1 3 -3 1 t 3 3 -6 3 0 2 i t = Q(t ) = G B iM B iT = G B i -3 3 0 0 t 1 0 0 0 1 P1 i(1 - t )3 + P2 i3(1 - t ) 2 t + P3 i3(1 - t )t 2 + P4 it 3 A Bézier-ívek tartópontjai közül kett P1 és P4 a görbén helyezkedik el, a P2 P3 pedig a görbe két végpontjába húzott érintkön található. A görbe íve mindig a P1, P2, P3, P4, kontrollpontok által meghatározott négyszög belsejében helyezkedik el.

4.6.1 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 megfel Bézier-szegmensek. Képezve Q(t) t-szerinti deriváltjait és helyettesítve a t=0 illetve t=1 értékeket az alábbi eredményt kapjuk: · · Nulladrend folytonosság esetén: Q1 (1)= Q2 (0), azaz A4=B1. Elsrend folytonosság esetén:

d d Q1 (1) = Q 2 (0),azaz A 4 - A 3 = B 2 - B1 dt dt
· Másodrend folytonosság esetén:

d2 d2 Q1 (1) = Q 2 (0), azaz (A 4 - A 3 ) - (A 3 - A 2 ) = (B 3 - B 2 ) - (B 2 - B1 ) dt 2 dt 2

57

4.7 B-spline görbe elállítása
Legyen adott a P0 , P1 , ..., Pn .pontsorozat, azaz n+1 pont. A kontrollpontok közül rendre tekintjük az egymást követ négyet, azaz az n-3 pontnégyest. Keresünk négy harmadfokú súlyfüggvényt, melyek eleget tesznek a következ feltételnek: az egymást követ pontnégyesekhez tartozó ívek csatlakozzanak, a csatlakozási pontban els és másodrendben legyenek folytonosak. Az i. ívet jelöljük Qi-vel, mely ív függjön a t paramétertl, ahol
t [ 0,1] , i = 3, 4,..., n .
G i = [ Pi -3 Pi - 2 Pi -1

A
Pi ] .

Qi

ívet A

meghatározó

geometriai

adatok

tehát

keresett

súlyfüggvényeket

(harmadfokú

polinomokat) jelölje X 0 (t ), X 1 (t ), X 2 (t ), X 3 (t ) . Az i. szegmens tehát az alábbi alakú: Qi (t ) = Pi -3 X 0 (t ) + Pi - 2 X 1 (t ) + Pi -1 X 2 (t ) + Pi X 3 (t ) i = 3, 4..., n t [0,1] . Mivel Qi (1) = Qi +1 (0), i = 3, 4..., n - 1 ,ezért 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) Az elsrend és másodrend csatlakozásra tekintettel, hasonlóan:
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)

és
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)

Ez összesen 15 egyenlet, 16 ismeretlennel. Hozzávesszük a koordináta transzformációval szembeni invarianciát biztosító Cauchy-egyenletet: 58

X 0 (t ) + X 1 (t ) + X 2 (t ) + X 3 (t ) 1

Az egyenletrendszert megoldva a keresett súlyfüggvények:
1 (1 - t )3 6 1 X 1 (t ) = (3t 3 - 6t 2 + 4) 6 1 X 2 (t ) = (-3t 3 + 3t 2 + 3t + 1) 6 1 3 X 3 (t ) = t 6 X 0 (t ) =

Mátrix-reprezentációban az eredmény:
-1 3 -3 1 t 3 1 3 -6 0 4 t 2 = Q(t ) = G Bz iM Bz iT = G Bz i i 6 -3 3 3 1 t 1 0 0 0 1 1 (P1 i(1 - t )3 + P2 i(3t 3 - 6t 2 + 4t ) + P3 i(-3t 3 + 3t 2 + 3t + 1) + P4 it 3 ) 6 1 1 1 1 Az B Bs1 = (1 - t )3 , B Bs2 = (3t 3 - 6t 2 + 4t ), B Bs3 = (-3t 3 + 3t 2 + 3t + 1), B Bs4 = t 3 6 6 6 6 súlyfüggvényeket koordinátarendszerben ábrázolva:

59

Az alábbi ábrán az egymást követ szegmenseket eltér színnel rajzoltuk.

60

4.8 Bézier-görbe elállítása Berstein polinommal
Legyen n>0, i=0,1,...n. Berstein polinomnak nevezzük a következ alakú n-ed fokú polinomokat: n Bin ( t ) = t i (1 - t ) n -i i A Berstein polinomokra igaz a következ azonosság:

B ( t ) = 1, t R
i =0 n i

n

Ennek igazolása a binomiális tétel alapján nyilvánvaló:

( t + (1 - t ) )

n

= Bin ( t ) = 1
i =0 n

n

Legyen adott a P0 , P1 , ..., Pn pontsorozat. A Q(t ) = Pi Bin ( t ) , t [ 0,1] görbét
i =0

Bézier-görbének nevezzük. A harmadrend Bézier görbe speciális esetként adódik. A Bézier ívek kontrollpontjai affin transzformációval szemben invariánsak. Ez azt jelenti, hogy például a görbe mozgatásakor elegend a kontrollpontokat transzformálni, mellyel igen sok számítás megtakarítható. A Bézier-ívek a paramétertartomány affin transzformációira is invariánsak. A Bézier-ívek globálisan változtathatók, azaz ha a kontrollpontok közül egyet elmozgatunk, az az egész görbére kihat. A görbe áthalad a kezd és végponton.

4.8.1 A kontrollpontok multiplicitása
A
P0 , P1 , ..., Pn

közül

k

egymást

követ

pont

megegyezhet,

azaz
Pi

Pi = Pi +1 = ... = Pi + k -1 , (i > 0, i n - k + 1) . Ekkor azt mondjuk, hogy a

kontrollpont multiplicitása k. A görbe alakulásában az ilyen pontok nagyobb súllyal vesznek részt.
61

4.8.2 Bézier-görbe elállítása de Casteljau-algoritmussal
Legyen adva egy n-edrend Bézier-ív a Definiáljuk a következ rekurzív összefüggést:
Pir (t ) = (1 - t )Pir -1 + tPir+-1 , ahol 1 P0 , P1 , ..., Pn

kontrollpontokkal.

r = 1, 2, ... , n;

és

i = 0, 1, ... , n - r ,

valamint Pi0 = Pi , i = 0, 1, ... , n Ezzel a rekurzív képlettel kapott Pir (t ) pont a t paraméterértékhez tartozó görbepont, amit a gyakorlatban szakaszok adott arányú felosztásával kapunk meg. Vagyis a Pir (t ) -nek megfelel pont a Pir -1 (t ) és Pir+-1 (t ) -nek megfelel pontokat 1 összeköt szakasz egy bels pontja, melyet az 1-t és t súlyok jelölnek ki. Vagyis például t=0.5-nél a kontroll poligon oldalainak felezpontjait kötjük össze, majd a kapott szakaszok felezpontjait, stb.. n=4 esetben a rekurziónak a 3. lépésnél van vége.

P P0 P0
1

1

1 P1 3

P2 P1
2

P1 2

P2 0

P0

P3

Egy konkrét t0 értéket és négy kontrollpontot választva a harmadik felosztás már görbepontot eredményez. Természetesen belátható, hogy ez az elállítás ugyanazt a görbét eredményezi, mint a Berstein-polinomokkal való számolás.
P0
1 P0

P1 P11 P2
1 P2

P02 P03 P12

P3

62

A Bézier-görbe a megadott pontok közül átmegy a kezd- és végponton, azaz interpolálja azokat. Ezen pontokban az érint egyenese megegyezik a kontrollpoligon els, illetve utolsó szakaszának egyenesével. Azt, hogy a görbe mennyire jól aproximálja az adott pontokat, az úgynevezett konvex burok tulajdonság mutatja. Egy ponthalmaz konvex burkán az ezen pontokat tartalmazó konvex ponthalmazok metszetét értjük, lényegében a legkisebb olyan konvex alakzatot, melyben mindegyik pont benne van. A konvex burok tulajdonság azt mondja ki, hogy a görbe sosem hagyja el az t definiáló kontrollpontok konvex burkát.

4.8.3 Interpoláló Bézier-görbe elállítása
Adottak a P0 , P1 , ..., Pn kontrollpontok, valamint a t0 , t1 ,..., tn (különböz)

paraméterek. Határozzuk meg a B 0 , B1 , ..., Bn pontokat, hogy az általuk elállított
Q(t ) = B i Bin ( t ) , t [ 0,1] Bézier görbe áthaladjon az adott pontokon, azaz:
i =0 n

P j = B i Bin ( t j ) , j = 0,1,..., n
i =0

n

Ugyanez mátrix reprezentációban: P0 B0n (t0 ) B1n (t0 ) P n n 1 B0 (t1 ) B1 (t1 ) . . . = . . . . . . n n Pn B0 (tn ) B1 (tn ) . . . . . .
n Bn (t0 ) B 0 Bnn (t1 ) B1 . . i . . . . n Bn (tn ) B n

.

.

.

A fenti inhomogén lineáris egyenletrendszert (minden koordinátára vonatkozóan) megoldva kapjuk a keresett pontokat. A lineáris egyenletrendszer mindig megoldható, mivel igazolható, hogy a rendszer determinánsa nem nulla.

63

5 Tér síkra való leképezései
Ha raszteres képpé konvertálva a 3D-s tárgyakat meg akarjuk jeleníteni a monitor képernyjén, akkor ezeket a 3D-s modelltérbl egy 2D-s nézetre kell leképezni. Ezért a számítógépi grafikában kiemelt jelentség transzformációk a vetítések. Vetítésnek nevezzük azokat a dimenzióveszteséggel járó pont-transzformációkat, amelyeknél a képpont és a neki megfelel tárgypont egy egyenesen helyezkedik el. A tárgy- és képpontokon áthaladó egyenest vetítsugárnak nevezzük. A vetítés eredménye a vetület, ami a képsíkon képzdik. Az egyes tárgypontok képe a vetítsugarak döféspontja a képsíkkal. A vetítés két alaptípusa a párhuzamos és a középpontos vetítés. Párhuzamos vetítésrl beszélünk, ha a vetítsugarak egymással párhuzamosak. Ha ezen kívül a vetítsugarak még merlegesek is a képsíkra, akkor merleges a vetítés, egyébként pedig a ferde vetítés elnevezést használjuk. Középpontos vetítés esetén a vetítsugarak mindegyike áthalad a vetítési középponton, a centrumon. Perspektivikus hatás elssorban a tárgy és a centrum és a pont távolságától függ. Ha ez a távolság minden határon túl n, a középpontos vetítés párhuzamos vetítésbe megy át.

5.1 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
y P(x,y,z)

y yc x z xc

Pc(x,y,z)

x

s z 64

megfelel hasonló háromszögekbl: x c = x

s s ; yc = y ; s-z s-z

Ugyanez homogén koordinátákkal mátrix-reprezentációban:
1 xc c 0 y = 0 0 1 0 0 1 0 0 0 0 1 0 - s s 0 x x x s-z 0 y y = 0 = y s 0i z s- z z 1 1 1 - 0 s 1

5.2 Axonometria
Megadjuk a képsíkon a tengelykereszt képét.
' ' Ex (a11 , a21 ), E y (a12 , a22 ), Ez' (a13 , a23 )

P( x, y, z ) P(u , v) u a11 v = a 21 a12 a22 x a13 a11 x + a12 y + a13 z y = a23 a21 x + a22 y + a23 z z

5.2.1 Kavalier axonometria:
u -q cos v = -q sin x 1 0 y 0 1 z

z

Ez - q: rövidülés a x tengelyen - : x tengely képének y tengely képével bezárt szöge

Ey

x Ex y

65

5.3 Párhuzamos vetítés
Legyen a vetítés iránya adott egy v vektorral. Ekkor:
P = P + v alapján x = x + vx , y = y + v y , z = z + vz = 0, amibl

=-

z z z x = x - v x , y = y - v y vz vz vz 0 - 1 - 0 0 vx vz vy vz 0 0 z 0 x - vx vz x y z 0i = y - vy vz z 0 0 1 1 1

1 x y = 0 0 1 0 0

6 Felületek
A térbeli felületeket kétparaméteres r=r(u,v) vektor-skalár függvényekkel modellezhetjük, ahol
u [u1 , u2 ] és v [ v1 , v2 ]

paramétertartománynak.

Ez

komponensekben felírva: x = x(u, v) y = y (u, v) z = z (u, v) Minden egyes konkrét u és v paraméterérték a felület egy pontjához vezet helyvektort határoz meg. A térbeli felületeket paramétervonalaikkal ábrázolhatjuk. Azaz megadjuk a felületen azon pontok halmazát, melyek egy konkrét u és v értékhez tartoznak. Ez egy térgörbe lesz, amit paramétervonalnak nevezünk. A vektorgrafikus objektumok képét csak egyenes szakaszokból összerakott alakzatokból tudjuk összeállítani. Ezért a görbék és felületek modellezésében fontos szerepet töltenek be az egymáshoz kapcsolódó egyenes szakaszokból felépített poligonok és a sokszöglapokból álló térbeli alakzatok, a poliéderek, mivel a térbeli görbéket mindig poligonokból, a felületeket pedig sokszöglapokból felépített alakzatokkal közelítjük. 66

Ha a modellezni kívánt felület r = r ( u , v ) vektor-skalár egyenlete adott, akkor az u illetve v irányú paramétervonalak megjelenítése két-két egymásba ágyazott ciklussal történhet.

6.1 Coons-foltok (felület interpoláció)
Adott 4, egymást páronként metsz térgörbe, melyeknek ismerjük a vektor-skalár elállítását. Ezek a görbék legyenek:
a1 (u ), a 2 (u ), u [ 0,1] és b1 (v), b 2 (v), v [ 0,1] Ezek egy térbeli négyszöget alkotnak, amelyre illeszteni akarjuk az r ( u , v ) felületet, ahol u , v [ 0,1] . A felületet úgy kell meghatározni, hogy a határokon pontosan a határoló görbéket adja vissza. Vagyis:
r ( u , 0 ) = a1 (u ) r ( u ,1) = a 2 (u ) r ( 0, v ) = b1 (v) r (1, v ) = b 2 (v)

A coons-foltot 3 felületbl állítjuk el. Ebbl kett az a1 és a 2 , valamint a b1 és b 2 által meghatározott vonalfelület, a harmadik pedig egy nyeregfelület. Vonalfelületek leírása: Adott a1 (u ) és a 2 (u ) térgörbe, melyek ugyanazon az intervallumon kell hogy legyenek definiálva, ez általában: u [ 0,1] , de tetszleges [a,b] intervallum is lehet. A két görbe adott u értékekhez tartozó pontjait kötjük össze, azaz a paramétervonalak egyenes szakaszok. A két térgörbe által kifeszített
I a (u , v), ahol u , v [ 0,1] felület egyenesekbl áll és igaz rá, hogy

67

I a (u , 0) = a1 ( u ) , és I a (u ,1) = a 2 ( u )

A felület az a1 ( u ) és a 2 ( u ) térgörbék lineáris interpolációja, melynek egyenlete:
I a (u , v) = (1 - v)a1 ( u ) + va 2 ( u )

A felület az a1 ( u ) és a 2 ( u ) , egymással szemben fekv két görbét interpolálja, de a másik két határoló görbén
b1 ( v ) , b 2 ( v ) -n nyilván nem halad át.A

b1 ( v ) , b 2 ( v ) által meghatározott vonalfelület hasonlóképpen állítható el. Ennek

egyenlete: I b (u , v) = (1 - u )b1 ( v ) + ub 2 ( v ) A négy görbe metszéspontjai négy pontot határoznak meg a térben, melyek meghatároznak egy nyeregfelületet, a kitér egyenesek affin pontsorai megfelel elemeinek összekötése által. A négy metszéspont bilineáris interpolációja: r (0, 0) r (0,1) 1 - v I ab (u, v) = [1 - u u ] r (1, 0) r (1,1) v A coons-foltot a 3 felületbl úgy kapjuk meg, hogy a két vonalfelület összegébl kivonjuk a nyeregfelületet: r ( u , v ) = I a (u, v) + I b (u , v) - I ab (u, v)

68

Azaz:
r (0, v) 1 - v r (0, 0) r (0,1) 1 - v r (u , v) = [1 - u u ] + [r (u , 0) r (u,1) ] v + [1 - u u ] r (1, 0) r (1,1) v r (1, v)

6.2 Bikubikus felületek
A harmadrend paraméteres görbék

Q(t ) = [ x(t )

y (t ) z (t ) ] = G · M · T
T

elállításából indulunk ki. Q-t sorvektorként tekintve:
Q(t ) = [ x(t ) y (t ) z (t ) ] = TT · MT · G T .

G-t magát is harmadfokú paraméteres függvényként állítjuk el, akkor bikubikus
felületet kapunk.
G1 ( v ) G (v ) T T 2 , ahol U = u 3 u 2 u1T r (u, v) = U M G (v) = U M G 3 (v ) G 4 (v ) és G i (v) = V T M T G i , ahol G i = gi1 gi 2 g i 3 gi 4 , V = v3 v 2 v1 T T T T ( A B C) = C B A alapján G i (v) = G T M V = g i1 gi 2 gi 3 gi 4 M V i g11 g T T 21 r (u, v) = U M g31 g 41 g14 g 24 M V vagy g34 g 44 T T r (u, v) = U M G M V g12 g 22 g32 g 42 g13 g 23 g33 g 43
T T

x(u , v) = UT MT G x M V y (u , v) = UT MT G y M V z (u , v) = UT MT G z M V A fenti módon elálló felületek közül a B-spline és Bezier felületek esetében a geometriai adatok 16 kontrolpontot jelentenek. Hasonló a helyzet, ha 16 pontot interpoláló Hermite-féle felületet állítunk el. A két pont és két érint alapján elálló Hermite ívhez tartozó alapmátrix esetében a geometriai adatok jelentése

69

összetettebb. A felület ábrázolásakor érdemes a MT G M szorzatot elre, a szükséges dupla cikluson kívül kiszámítani. Mindkét irányú paramétervonalat egy-egy egymásba ágyazott ciklussal számítjuk ki.

Bezier felület

B-spline felület

70

Hermite felület 16 pontra

6.2.1 Hermite felület
Induljunk ki a Hermite-görbe alapmátrixából, mely két pont két érint adatokhoz tartozik.
P1 (v) P (v ) x(u, v) = UT MT G H x (v) = UT M T 4 , H H R 1 (v ) R 4 (v ) x ahol U = u 3 u 2 u1 , V = v3 v 2 v1 A P1 (v), P4 (v), R1 (v), R 4 (v) függvények elállítása (x komponenseik): P1 x (v) = [ g11 P2 x (v) = [ g 21 R1x (v) = [ g31 R 4 x (v) = [ g 41 g12 g 22 g32 g 42 g13 g 23 g33 g 43 g14 ]x M H V
T T

g 24 ]x M H V g34 ]x M H V g 44 ]x M T V H

71



P1 (v) g11 g12 g13 g g 22 g 23 P4 (v) = G M V, ahol G = 21 Hx H Hx g31 g32 g33 R 1 (v ) R 4 (v ) x g 41 g 42 g 43 g11 g12 g13 g14 P1 (v) g P (v ) g 22 g 23 g 24 M V = G M 4 = 21 H Hx H g31 g32 g33 g34 R 1 (v ) R 4 (v) x g 41 g 42 g 43 g 44 x x(u, v) = UT MT G H x M H V H

g14 g 24 g34 g 44 x

V

G Hx

x(0,1) x(0, 0) x(0,1) x(0, 0) v v x(1, 0) x(1,1) x(1, 0) x(1,1) v v = x(0, 0) x(0,1) x(0, 0) x(0,1) u u u v u v x(1, 0) x(1,1) x(1, 0) x(1,1) u u v u v u

A GH

els oszlopában szerepl adatok határozzák meg az u irányú

paramétervonalat v=0 mellett. Az els sorvektor hasonlóan a v irányú paramétervonalat határozza meg. Fontos szerepe van a felület alakjának alakításában a jobb alsó 2x2 kettes mátrixnak. Ezek az úgynevezett twist vektorok, melyeknek a Hermite-féle foltok egymáshoz illesztésében van szerepük.

6.2.2 Felületi normálisok
Általában gyakorta szükséges a felületek valamely pontjában a felületi normálisok kiszámítása. A felületi normálist a paramétervonalak adott pontbeli érintinek vektoriális szorzataként számítjuk ki.

72

 ( UT M T G M V ) = ( UT ) M T G M V = r (u, v) = u u u
3u 2 2u 1 0 M T G M V = [ xu yu zu ]

( UT M T G M V ) = UT M T G M (V ) = r (u, v) = v v u
UT M T G M 3v 2 2v = [ xv yv zv ] 1 0

r (u, v) × r (u, v) = ( yu zv - yv zu ) u v

( zu xv - zv xu ) ( xu yv - xv yu )

6.3 Poligonokkal határolt felületek
6.3.1 Explicit reprezentáció
Minden poligont csúcsainak koordinátáival adunk meg, az egymásra következ csúcsok, az els és az utolsó adják az éleket. Redundáns adattárolás, mivel egy csúcs annyiszor szerepel, ahány poligonhoz tartozik. Ha egy P poligonnak n csúcsa van, akkor az alábbi módon tároljuk a csúcsokat:
P = ( ( x1 y1 z1 ) , ( x2 y2 z2 ) ,..., ( xn yn zn ) )

V2

V1

P1

P2

V3

V4

A fenti ábrához tartozó adatszerkezetben két poligont adunk meg, mindegyikben 3-3 csúcsot sorolunk fel. A V2 és V4 csúcsok kétszer szerepelnek a listában. 73

6.3.2 Mutatók a csúcslistába
Két listában tároljuk az adatokat. Az egyik lista a csúcsok listája, melyben megadjuk az összes csúcsot. Ezek az úgynevezett geometriai adatok. A másik listában felsoroljuk a poligonokat, ahol a listaeelemek mutatók (vagy esetleg indexek) és a csúcslista megfelel elemeire mutatnak. Ezek a topológiai adatok. Csúcsok listája:
V = ( ( x1 y1 z1 ) , ( x2 y2 z2 ) ,..., ( xn yn zn ) )

Poligonok listája (pl. k darab poligon estén):

( ) P = ( i , i ,..., i )
1 1 1 P = i1 , i2 ,..., im1 1 2 2 1 2 2 2 m2

. . .
k k Pk = i1k , i2 ,..., imk

(

)

6.3.3 Mutatók az éllistába
A csúcslistán kívül megadunk egy éllistát és a poligonok listáját is. Az élek listájában két mutató a csúcslista 1-1 elemére mutat, melyek az él két végpontját határozza meg. Másik két mutató pedig a poligonok listájába mutat, arra a legfeljebb két poligonra, melyek az adott élben találkoznak. Széls él esetén az egyik mutató null is lehet. A struktúra akkor is hasonló, ha több mint két poligon találkozik egy élben. E1 V1 P1 E5 P2 P2 E4 E3 V4 74 V2 E2

V3

A poligonok listájában szerepl mutatók az éllistára mutatnak, a körüljárásnak megfelelen felsorolva az adott poligonhoz tartozó éleket. A fenti ábrához tartozó struktúra az alábbi: V = (V1 , V2 , V3 , V4 ) = ( ( x1 y1 z1 ) , ( x2 y2 z2 ) ,..., ( x4 y4 z4 ) )

E1 = (1, 2,1, ) E2 = ( 2,3, 2, ) E3 = ( 3, 4, 2, ) E4 = ( 4, 2,1, 2 ) E5 = ( 4,1,1, ) P = (1, 4,5 ) 1 P2 = ( 2,3, 4 ) Az élek esetén az els két index a csúcslistába, a második kett pedig a poligonok listájába mutat. Általánosan, ha n csúcs, k poligon és m él van:

V = ( ( x1

y1

z1 ) , ( x2

y2

z2 ) ,..., ( xn

yn

Ei = (V1i , V2i , P i , P2i ) , i = 1, 2,.., m 1 Pj = E1j , E2j ,..., E pj j , j = 1, 2,.., k

zn ) )

(

)

Bármely poligon éleinek a száma eltér lehet, ebben az esetben dinamikus adatszerkezetre van szükség. Ha egyez élszámú poligonokról van szó, (pl háromszögek) akkor az adatszerkezet egyszerbb is lehet.

7 Testmodellezés
7.1 Reguralizált halmazmveletek
Testek modellezésekor elfordulhat, hogy a szokásos értelemben vett

halmazmveletek eredménye nem test lesz. Például poliéderek esetén metszet vagy különbség képzéskor az eredmény lehet egy lap is. Ezt elkerülend, bevezetjük a regularizált halmazmvelet fogalmát, amit a * szimbólummal jelölünk, és a következ módon értelmezünk:
75

Aop B = int ( AopB )
Az op szimbólum jelöli az unió, metszet, különbség képzés valamelyikét, int pedig a bels pontok halmazát. Azaz vesszük a szokásos halmazmveletet, az eredmény bels pontjait, majd a lezártat.

7.2 Sepert testek (SWEEP representation)
Mozgassunk a térben egy objektumot folytonosan valamilyen pályán. A mozgás során az objektum egy térrészt súrol, ami egy új objektumként fogható fel. A legegyszerbb eset az, amikor egy 2d-s zárt tartományt mozgatunk például egy szakasz mentén önmagával párhuzamosan, ekkor hengert (poligon mozgatása esetén hasábot) kapunk. Hasonlóan felületek is elállíthatók, ekkor nyílt alakzatot (görbét) mozgatunk. A mozgó objektumot 2d-s esetben generátor görbének, a mozgás pályáját vezérgörbének nevezzük. Megengedett a generátor görbe alakváltozása is. A mozgás gyakran kötdik a vezérgörbe kísér triéderéhez, ami a görbe egy pontjában értelmezett ortonormált bázis. Az érint vektor, f normális és binormális vektorok alkotják. Bizonyos görbék esetén (pl. splinok) könnyen számítható.

76

7.3 Felületmodell (Boundary representation, B-rep)
A legismertebb és leggyakrabban használt módszer testek modellezésére. A 6.3 fejezetben leírt adatstruktúra alapján poliédereket definiálunk, az által, hogy megadjuk a határoló poligonjaikat. A ,,görbült" testeket gyakran elég kicsi poligonokkal közelítjük. Elvileg a B-rep adatstruktúrában megengedett nem síkfelületek kezelése is. A leggyakoribb a háromszögekre való bontás, mert ezek kezelése gyors. Itt említjük meg a közönséges egyszer poliéderekre vonatkozó Euler formulát, miszerint l + c = e + 2 , ahol l a lapok, c a csúcsok és e az élek számát jelenti. Ennek teljesülése a legtöbb modellez rendszer esetében szükséges.

7.4 Cella módszerek (Volume visualisation)
Egység kockákból épül fel a test. Ha a test az egységkocka térfogatának több mint a felét elfoglalja, akkor azt a kockát hozzávesszük a testhez. Elnye, hogy a halmazmveletek nagyon egyszeren kezelhetek. Az egységkockák elnevezése

voxel. A legegyszerbb adatszerkezet a voxelek tárolására egy háromdimenziós
tömb, melynek elemei igaz-hamis értékek lehetnek. Hátrány a nagy memória igény, a megfelel pontosság eléréséhez kis egységkockákat kell megadnunk. Optimalizálni lehet az adatstruktúrát az Octree felépítéssel. Ez egy speciális fa. Az els csomópont a gyökér cella, mely 8 elembl áll. Az elemek mindegyike egy másik 8 elem blokkra mutathat. Ez folytatható mindaddig, amíg a szükséges mélységet el nem értük. Az utolsó szint a levélelemek szintje ahol a voxeleket tároljuk.

(a)

(b)

A fenti ábrán 2d-ben szemléltetjük egy objektum két módszerszerinti felbontását. Az a ábrán minden voxel tárolódik, a b ábrát egy quadtree-vel adhatjuk meg. Csak akkor végzünk további felbontást, ha szükséges. A háromdimenziós adatstruktúrát a következ ábra szemlélteti:

77

78

7.5 Térfogat modell (CSG: Constructive Solid Geometry)
F(x, y, z) típusú implicit egyenletekkel primitívek vannak megadva, melyeken (reguralizált) halmazmveleteket végezve létrehozhatók más testek. A legtöbb rendszer az alábbi primitíveket használja: · · · · · · Gúla Hasáb Gömb Kúp Henger Tórusz

A primitiveken különböz transzformációk végezhetek, pl. eltolás, forgatás, skálázás stb. Az alábbi ábra transzformált hasábok uniója és különbségeképpen áll el. hasab(16,.8)hasab(16,.6)(1.1)hasab(10,.4){1.57,,}//hasab(10,.3){1.57,,}/

79

8 Láthatósági algoritmusok
A modelltér objektumaihoz tartozó látható élek és felületek meghatározása, valamint a takart élek és felületek eltávolítása a cél. Ennek lényege, hogy adott 3 dimenziós objektumok és a nézpont esetén el kell döntenünk, hogy mi látható az alakzatokból a vetítés középpontjából vagy irányából nézve. Ennek eldöntését segít algoritmusokat takart vonal, illetve takart felület (hidden-line, hiddensurface) meghatározó eljárásoknak nevezik.

8.1 Hátsó lapok eltávolítása (back-face culling)
A zárt, sokszögekbl felépül objektumokat teljesen körbezárják a felületüket alkotó poligonok. Ha a poligonok normálvektorait ú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 elre néz poligonokat front-face-nek nevezzük. A back-face poligonok könnyen azonosíthatók kifelé mutató normálvektoruk és lap egy pontjából a centrumba mutató vektor skalárszorzatának vizsgálatával: a negatív érték hátrafelé néz poligonra utal, hiszen ekkor a két vektor szöge nagyobb a derékszögnél. Ha az ábrázolandó jelenet egyetlen, konvex poliéderbl áll, akkor a látható felületek meghatározása back-face culling mveletre egyszersödik. Más esetekben további vizsgálatok szükségesek, hiszen a front-face poligonok is takarhatják egymást. Egy poligoniális objektumot metsz vetítsugá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. A konvex poliéderek láthatóság szerinti megjelenítéséhez elegend a hátsó lapokat eltávolítani. 80

8.2 Robert-féle algoritmus
Konvex poliéderekbl á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.

8.3 Listaprioritásos algoritmusok
8.3.1 Mélységi rendez algoritmus (fest algoritmus, Newell, 1972)
Ennek a tárgypontosság algoritmusnak az az alapgondolata, hogy a

megjelenítend objektumokat a nézponttól való távolság függvényében sorba kell állítani. Az algoritmus a helyes takarási viszonyokat úgy alakítja ki, hogy a nézhöz közelebb es objektum képe felülírja a távolabbi objektum képét. Ennek legegyszerbb változata az úgynevezett fest algoritmus, mely a képfestés technikájához hasonlóan a távolabbi objektumokra ráfesti a közelebbieket. Ezek az algoritmusok általában az objektumok poligonfelületekkel, legtöbbször háromszögekkel való közelítését tételezik fel. Ha egy háromszög z irányban egyértelmen takarja a másikat, akkor a megjelenítésnél ennek képével felül kell írni a távolabbi háromszöget. Ha két háromszög mindegyike takarja a másikat, akkor ezeket úgy kell felbontani részháromszögekre, hogy a takarási viszonyok egyértelmek legyenek A mélység rendez algoritmusokat általában valamilyen képpontosság eljárással együtt alkalmazzák. Ekkor az objektumok sorba rendezése és szükségszerinti feldarabolását követen a pixeles megjelenítés például egy z-bufferrel kombinált scan-line algoritmussal történhet. Lépések: · · · Rendezzük a poligonokat a legkisebb (legtávolabbi pontjaik) z koordinátáik szerint ha kell, a poligonok darabolásával az átlapolásokat szüntessük meg hátulról elre haladva scan konverzióval fessük ki a poligonokat 81

8.3.2 Bineáris térfelosztási fa (BSP)
A háromdimenziós objektumok tetszleges nézponthoz 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 meglehetsen idigényes, késbb, új nézpont 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 gyjtemé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ézpont 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 elské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ézponthoz tartozó helyes takarási viszonyokat rögzíti a megjelenítés során. Bár az algoritmus helyes mkö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 jelentsen befolyásolja az algoritmus idigé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, csak akkor kell újra elvégezni, ha a jelenet megváltozik. Másként fogalmazva, a nézpont megváltoztatása esetén nem kell a BSP fát módosítani.

82

8.3.2.1 A BSP fa elkészítése
Rendelkezésünkre án 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: · · · A gyökérlap által generált pozitív féltérben helyezkedik-e el -front listába tesszük. - A gyökérlap által generált negatív féltérben helyezkedik-e el -back listába tesszük. 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.

83

8.3.2.2 A BSP fa bejárása
1. Kiszámoljuk a korábban megismert módszer szerint, hogy a nézpont a gyökérIap melyik oldalára esik. 2. Ha a gyökérlap által generált pozitív féltérbe esik, akkor: · · · · Bejárjuk a back ágat, ha van. Kirajzoljuk az aktuális gyökérlapot. Bejárjuk a front ágat, ha van. Kész.

3. Egyébként: · · · · Bejárjuk a front ágat, ha van. Kirajzoljuk az aktuális gyökérlapot. Bejárjuk a back ágat, ha van. Kész.

Bonyolultsága O(n), ahol n a BSP fa elemeinek száma. A korábbi példa két különböz nézpont esetén (A vastagon szedett számok a kirajzolási sorrendet jelentik, a fekete kör pedig a nézpont):

84

8.4 Scan-line algoritmusok
A scan-line algoritmusok képpontosság mveleteket használva, pixelsorokként készítik a képet, és a poligonok (háromszögek), frame-bufferbe történ, soronkénti konvertálásának módszerén alapulnak. Az algoritmus, a jelenetet felépít objektumokról gyjtött információkat táblázatokban tárolja: a képsíkra vetített, nem vízszintes éleket az él táblázat, a poligonok fontosabb paramétereit a poligon táblázat, az éppen vizsgált pixelsorhoz tartozó éleket az aktív él táblázat tartalmazza. Egy-egy pixelsor vizsgálatakor az él táblázat azok az elemei, melyek metszik a sort, áttöltdnek az aktív él táblázatba a pixelsor és a háromszögek közös részét szegmenseknek nevezzük. Ha a pixelsor egy szegmense csak egy háromszöghöz tartozik, akkor ezt egyszeren meg kell csak jeleníteni. Ha egy pixel több szegmenshez tartozik, akkor a megfelel háromszögek mélységi vizsgálatával kell eldönteni, hogy melyik háromszög felületi pontját kell kirajzolni. Ebbl látható a scan-line algoritmusoknak az a nagy elnye, hogy az objektumok közötti geometriai összefüggéseket figyelembe véve a látható pixelek meghatározásához szükséges tesztelésekbl a feleslegeseket képes kiszrni. Így például, ha két egymást követ pixelsorhoz tartozó aktív élek és ezek sorrendje megegyezik, akkor nem történt változás az objektumok takarási viszonyaiban, így nem szükséges a háromszögek újabb mélységi vizsgálata. A levetített poligonok minden nem vízszintes élére vonatkozóan ET létrehozása, a kisebb y koordináta szerint rendezetten. y E B +2 +1 A F x 85

D

C

ET

x

ymax

x

ID

·

PT

ID

Sík egyenlet

Szin inf.

Flag

AET: ,+1 AB AB AB AB AC AC DE CB FD CB DE FE FE FE

y E B

D y= A

C F x

86

8.5 A z-buffer vagy mélység tároló algoritmus
Az algoritmus két tárolóterületet használ:
frame-buffert, mely a képerny pixeleihez rendelt színértékeket tárolja, induló

feltöltése a képerny háttérszíne,
z-buffert, mely az egyes pixelekhez rendelt z értékeket tárolja a normalizált

látótérbl, kezdeti értéke a hátsó vágósík z koordinátája. Ezt követen a jelenet minden egyes normalizált látótérbeli objektumának minden levetített lapjára a következ algoritmus kerül végrehajtásra: A lap minden (x, y) koordinátájú bels pixeléhez tartozó vetítsugárhoz

kiszámoljuk a laphoz tartozó z értéket, majd ha z értéke nagyobb mint egy korábban a z-bufferben letárolt érték (azaz a pont közelebb van a nézponthoz), akkor ezzel felülírjuk a korábban letárolt értéket a z-bufferben, és egyúttal a neki megfelel színértékkel, felülírjuk a frame-buffer (x, y) koordinátájú tárolóhelyét. Az alapalgoritmus szempontjából közömbös, hogy az objektumokat, illetve a raszterpontokat milyen sorrendben teszteljük. Ha a levetített lapok összes bels (x, y) képpontjára végrehajtjuk az eljárást, akkor ennek végén a frame-bufferben a kívánt képet kapjuk. A raszterpontok száma a korszerbb monitorok esetén milliós nagyságrend. Ennek megfelel számú z-érték tesztelést kell végezni az algoritmus végrehajtása során és ezzel arányos az eljárás memóriaigénye is. Vegyük észre, hogy a z-buffer algoritmus a modelltér elemeinek formájától független, így háromszög, poliéder vagy görbült felületek láthatóságának megállapítására egyaránt alkalmas. Alkalmazhatóságának egyetlen feltétele, hogy az objektumok felületi pontjaiban a nézponttól való z távolság és az árnyalási információk (szín, megvilágítás, textúrák) meghatározhatók legyenek. Az algoritmus jelents erforrásigénye, valamint tiszta formájában való alkalmazásánál egyes további eljárások anti-aliasing, az átlátszóság stb.) elvi megvalósíthatatlansága (ugyanis a z-bufferben csak egy z értéket tároljunk) miatt a z-buffert általában más eljárásokkal kombinálva szokták alkalmazni.

87

Az algoritmus Pseudo-kódja:
procdure zBuffer; var pz:integer; begin for y:=0 to YMAX do for x:=0 to XMAX do begin WritePixel(x,y,HATTER_SZIN); WriteZ(x,y,0); end for minden poligon do for minden pixelje a poligon képének do begin pz:=a poligon (x,y) pontjának z koordinátája; if pz>=ReadZ(x,y) then begin WriteZ(x,y,pz) WritePixel(x,y,szin) end; end; end;

8.6 Terület-felosztásos algoritmus
A területfelosztó algoritmusok alapgondolata, hogy néhány esetben (például a képen csak egy objektumot kell ábrázolni) nagyon egyszeren megállapítható a képernyn 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 egyszeren rendszerben. A legismertebb algoritmus ebben a csoportban Warnock (1969) algoritmusa. A rekurzió után maradó lehetséges helyzetek: kezelhet esetekre. A illetve képfelosztás a történhet látótér a raszteres koordinátaképernykoordináta-rendszerben, vektoros

88

1. Minden poligon a vizsgált területen kívül esik. Háttérszinnel befestjük a területet. 2. Csak egy metsz vagy tartalmazott poligon van a vizsgált területen. Elször a területet kitöltjük háttérszínnel, majd a poligon területen belüli részét scan-konvertáljuk. 3. Csak egy, a vizsgált területet teljesen tartalmazó poligon van Befestjük a területet a poligonnak megfelel szinnel. 4. Több mint egy poligonnak van közös része a tartománnyal, de van olyan, a tarományt teljesen tartalmazó poligon, amely a többi eltt van. A rekurzív felosztás egybevágó téglalapokra vagy egy alkalmas bels pont választásával négy nem egybevágó téglalapra történhet. Ez utóbbi esetben a pont alkalmas választásával az algoritmus hatékonysága jelentsen növelhet.

8.7 Sugárkövetéses algoritmusok (raytracing)
A sugárkövetéses (raytracing) algoritmusok a felületek láthatóságát a nézpontból kiinduló, képzeletbeli fénysugarak követésével határozzák meg. Tipikus képpontosság algoritmusok. Mködésükhöz a nézpontot és egy tetszleges vetítési síkon felvett ablakot kell definiálni. Az ablak téglalap alakú területét felosztó szabályos rács a képerny pixeleinek, felel meg. A raytracing algoritmussal a nézpontból vetítsugarat indítunk az ablak minden egyes pixelén keresztül a jelenet objektumai felé. Az adott pixel színét a sugár által a nézponthoz legközelebb metszett objektum színe határozza meg. Minden raytracing algoritmussal szemben támasztott legfontosabb követelmény, hogy képes legyen fénysugarak és objektumok metszéspontjait megtalálni. A feladat megoldásához a fénysugarat a nézpont és egy pixel által definiált vektor segítségével paraméteres egyenletével formában írjuk fel. Ha a nézpont a 89

C ( x0 , y0 , z0 ) , a vizsgált képpont pedig a P ( x1 , y1 , z1 ) , akkor a rájuk illeszked
sugár bármely (x, y, z) pontja megadható az egyenes paraméteres egyenletével:

x = x0 + t ( x1 - x0 ), y = y0 + t ( y1 - y0 ), z = z0 + t ( z1 - z0 )
x = x1 - x0 , y = y1 - y0 , z = z1 - z0

x = x0 + t x, y = y0 + y, z = z0 + z
A t paraméter 0 és 1 közé es értékei a nézpont és a vizsgált pixel közé es fénysugárpontokat definiálják, negatív értékek esetén a nézpont 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 a metszéspont az alábbi t-re másodfokú egyenlet alapján számítható::
( x - a ) 2 + ( y - b) 2 + ( z - c) 2 = r 2 , behellyettesítve x, y, és z -t: (x + y + z ) 2 t 2 + 2t [ x( x0 - a) + y ( y0 - b) + z ( z0 - c) ] + ( x0 - a ) 2 + ( y0 - b) 2 + ( z0 - c) 2 - r 2 = 0

Poligon esetén a metszéspont egyszerbben számolható:: 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 Ax + By + C z 0 . Ax+ By +C z

A z-buffer algoritmushoz hasonlóan a raytracing-nek is megvan az az elnyös tulajdonsága, hogy metszéseket csak objektumok és fénysugarak között kell elvégeznünk, objektumok egymás közti helyzetének közvetlen meghatározására nincs szükség. A raytracing algoritmus legegyszerbb (egyben legdrágább) változata a pixelekhez tartozó sugarakkal elmetszi a jelenetben szerepl összes objektumot. Egy száz objektumból álló jelentrl készítend 1024x1024-es felbontású kép tehát több mint 100 millió metszési mveletet igényel! Nem meglep tehát, hogy az átlagos jeleneteket ábrázoló képek elállítási idejének dönt része is a metszéspontok meghatározására fordítódhat. Ezért a raytracing algoritmusok idigényének csökkentését célzó kutatások f iránya a metszések 90

hatékonyságának növelése, illetve a felesleges metszési mveletek teljes elkerülése. Az algoritmus pszeudó-kódja:
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 objektumára a térrésznek do if van metszéspont és közelebb van, mint az elz then feljegyezni a metszéspontot és az objektumot, a pixel színét beállítani end;

8.7.1 Rekurzív sugárkövetés
A rekurzív raytracing a számítógépes grafika fotorealisztikus képábrázolásának legelterjedtebb algoritmusa, legintenzívebben fejld területe. Felhasználják a filmiparban, a reklámkészítésben, a videoclip-gyártásban, tervek fotorealisztikus bemutatásában, st a mvészetben is. A raytracing algoritmussal készített képek jellegzetességei könnyen felismerhetk. Ezek: · · · objektumok egymásra vetett árnyékai, többszörös tükrözdések, átlátszóság kezelése fénytöréssel.

A felületi pontoknak megfeleltetett pixel színének kiszámításához általános esetben több típusú másodlagos sugarat is nyomon kell követni. Ezek lehetnek a visszatükrözdött sugarak, megtör sugarak, és a fényforrással összeköt sugarak. Ha a fényforrással összeköt sugarak (ezekbl annyit kell indítani, ahány fényforrás van definiálva a modelltérben), melyeket árnyéksugaraknak is neveznek, beleütköznek valamilyen objektumba mieltt a fényforrást elérnék, 91

akkor a felületi pont árnyékban van és a megfelel fényforrást ki kell hagyni a felületi pontot árnyaló megvilágítási egyenletbl.

8.7.2 A raytracing mveletigényét csökkent eljárások

8.7.2.1 Backward Raytracing
Mivel a fényforrásokból kiinduló fénysugarak többsége olyan, hogy nem jut el az ablakon keresztül a nézpontba, jelentsen csökken a számításigény, ha ezekkel nem foglalkozunk. Ezért az algoritmus csak azokat a fénysugarakat veszi figyelembe, melyek az ablak celláin keresztül e jutnak a nézpontba. Ezt úgy éri el, hogy a fény terjedésével ellentétben nem a fényforrásokból kiinduló sugarakat kezdi vizsgálni, hanem azokat a nézpontból indított vetítsugarakat elemzi, melyek visszafelé eljutnak a fényforrásba. Ezt a megoldást "hátrafelé történ sugárkövetésnek", vagy Backward Raytracing-nek nevezik.

8.7.2.2 Bounding Volumes
A raytracing legmveletigényesebb része a vetítsugarak és az objektumok metszéspontjainak kiszámítása, célszer ezek számát tehát csökkenteni. Ezt célozza a raytracing sorári a befoglaló testek alkalmazása. Ennek során legtöbbször gömböket használunk fel. Ez azt jelenti, hogy olyan legkisebb méret gömböket definiálunk a modelltérben, melyek objektumainkat teljes mértékben tartalmazzák. A befoglaló gömbökkel úgy tudjuk csökkenteni a metszéspontok számításának mennyiségét, hogy csak azokat a vetít sugarakat vesszük figyelembe a metszéspontszámításnál, melyek a befoglaló gömböket is metszik.

8.7.2.3 A sugarak transzformálása z tengellyel párhuzamos helyzetbe.
A térpontjait egy megfelel projektív transzformácóval olyan helyzetbe hozzuk, hogy a sugarak párhuzamosak legyenek a z-tengellyel. Ha az 5.1 fejezetbeli speciális centrális vetítésbl indulunk ki, akkor a megfelel transzformációs mátrix az alábbi lesz:

92

1 0 A = 0 0

0 1 0 0 0 1 0 1 0 - 1 s 0 0

Az

A mátrixú transzformáció után a pontok képei a z-koordinátáik

elhagyásával elállnak. Az objektumok és a speciális vetítsugarak kölcsönös helyzetének vizsgálata nagyban leegyszersödik, sok teszt 2d-ben elvégezhet.

9 Színelméleti alapok
· · · Színérzet:A fény elektromágneses hullám spektrális tulajdonságai által keltett hatás Tristimulus: a beérkez fényenergiát leíró skalár érték Szintér: A lehetséges színérzetek alkotta három dimenziós tér

Pl.piros (red), zöld (green) és kék (blue) színérzetet okozó hullámhosszakból álló bázis:



red
·

= 700nm, green = 561nm, = 436nm, blue

színilleszt függvények: Egy hullámhosszú monokromatikus fénynyaláb keltette ekvivalens színérzetet elállító (r(), g() és b()) függvények (fiziológiai mérések eredménye)

9.1 RGB színrendszer:
Egy képpont a piros, a kék és a zöld 256-256-256 féle árnyalatából áll össze, összesen 16 millió színárnyalattal. 24 biten tárolja az információt. Ez additív színrendszer, tehát a három alapszín egyforma keverése fehér, hiányuk fekete színt eredményez. Ezeket a színeket használja minden elektronikus kivetíteszköz (monitor, kivetít).

93

9.2 CMY színrendszer:
Az RGB rendszer alap színeinek kiegészít színeit használja. Elssorban a nyomtatóknál alkalmazzák ezt a színrendszert. Ez úgynevezett szubtraktív színrendszer. Egy képpont a türkiz (Cyan), a bíbor (Magenta) a sárga (Yellow) (másodlagos alapszínek) árnyalataiból áll össze. A színek hiánya fehéret eredményez.

9.3 CMYK (vagy 32 Bit Color):
Az elz szírendszer kiegészül a fekete (blacK) 256*4 féle árnyalatával. 32 biten (4 byte) tárolja az információt. 4,3 milliárd árnyalata lehet egy képpontnak.

94

9.4 HLS szinrendszer:
Színárnyalat-fényesség-telítettség hármas határozza meg a színt.

9.5 Egyéb lehetségek
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 az információt.
Ilyen pl. a BGI grafika.

Grayscale: Egy képpont a szürke 256
árnyalatával rendelkezhet, 8 biten tárolja az információt.

256 Color: 256 megadott színe lehet egy képpontnak, 8 biten tárolja az
információt. (Régebben weblapok képeihez ajánlották ezt a színtartomány)

10 Egyszer megvilágítás és árnyalási technikák
Fotorealisztikus képek elállítása nagyon nagy számításigény probléma. Minden pixelben meg kell határozni az objektum színét, ami bonyolult szinmodell esetén sok idt jelent. A számítások egyszersítésére megalkotott módszerek közül ismertetünk néhányat.

95

10.1 Szórt háttérvilágítás (ambient light)
Ekkor az objektumok egyenletesen, minden irányból kapnak fényt. Hatása a nappali fényviszonyoknak felel meg, ha nincs napsütés. Ebben a modellben nincs fényforrás, az objektumok "saját" fényüket bocsátják ki. Ez megfelel annak, hogy a jelenetet egy irányfüggetlen, szórt fény világítja meg. Plasztikus képek elállítására nem alkalmas.

10.2 Diffúz fényvisszaverõdés (diffuse light)
A diffúz fényvisszaverdés a matt felületek jellemzje. Ekkor a megvilágított felület minden irányban ugyanannyi fényt ver vissza.

10.3 Fényvisszaverdés (specular light)
A sima felületekre általában az a jellemz, hogy rajtuk fényes foltokat is látunk, melyek helye nézpontunkkal együtt változik. Ezek a felületek bizonyos irányokban visszatükrözik a fényforrásokat. A fényforrás távolságától és irányától is függ komponens, a spekuláris visszaverdésbl származó színt adja meg.

10.4 Konstans árnyalás (Flat shading)
Síklapok árnyalására a leggyorsabb módszer. Feltételezi, hogy a fényforrás végtelentávoli, így a sík lap minden pontjába azonos szögben érkezik. A legegyszerbb esetben tehát a bees fénysugár és a felületi normális szögének függvényében határozzuk meg a szinintenzitást, minél közelebbi van a szög a derékszöghöz, annál intenzívebb árnyalatot rendelünk a ponthoz. A szín tehát csak laponként számolandó.

10.5 Gouraud féle árnyalás
Elssorban poligonok árnyalására kidolgozott eljárás. A poligon minden csúcsában meghatározunk egy vektort, melynek koordinátái az adott csúcsban találkozó lapokhoz tartozó normálvektorok megfelel koordinátáinak számtani közepe. A színmodellnek megfelelen kiszámítjuk a színeket a csúcsokban. Elször az poligon éleinek színét interpoláljuk, majd a poligon bels pixeleinek 96

szinét határozzuk meg lineáris interpolációval. Érdemes összekötni a módszert a polligon fillezésre vonatkozó algoritmussal (2.4 fejezet).

Flat shading

Gouraud

10.6 Phong árnyalás
A Goruaud árnyalástól abban különbözik, hogy magát a normálvektorokat határozza meg lineáris interpolációval, a színek kiszámítása a színmodellnek megfelelen pixelenként történik.

97



Hasonló témájú dokumentumok

Egyelőre még egyetlen hasonló témájú file sincs feltöltve a rendszerbe

A mások által feltöltött dokumentumokat értékelheted. Ha úgy ítéled meg, hogy a vizsgára való felkészülés szempontjából hasznos volt egy dokumentum, akkor adj rá sokcsillagos értékelést.
Ha hibákat tartalmaz, vagy egyéb probléma van vele, akkor keveset.
A dokumentumok sorrendje az értékelések alapján adódik. Ami fentebb van a listában, azt hasznosabbnak ítélték társaid. Az új dokumentumok pedig (értékelések hiányában) szintén a lista tetején kezdenek.

Hozzászólások

Ha észrevételed van egy dokumentummal kapcsolatban (például hibát találtál benne), akkor a Hozzászólások részben jelezheted. Az olyan jellegű kérdéseket mint pl.: A 2. feladat 4. sorából milyen átalakítással jutottunk az 5. sorban szereplő képlethez? - szintén ide érdemes írni

Egy tipp az oldalhoz! - Csakúgy mint amikor könyvtárakat/mappákat hozol létre a számítógépeden, egy tantárgyon belül is hasonló analógiával tetszőleges kategóriák és alkategóriák hozhatóak létre. Próbálj mindig a legmegfelelőbb kategóriába tölteni, hogy átlátható legyen a feltöltött dokumentumok szerkezete.

2006-os zh 2010 5. előadás agg zoltán atkinson bakteriólógia diffúzió dinamika elektro élet erdeiné török zsuzsa eu eu ismeretek gazd.töri tétel6 gepalap globalizáció integrálás irodalomesztétika jogelmélet jogszabályok kémia kéri bálint kidolgozott anyag kik kötelmi jog közig közigtöri légzés médiaismeretek merőpiac növényszervezettan jegyzetek numerikus objektum órai előadás politikatudomány pszichológia röviditett sejtbiosz számítógép architektúrák tájékoztató tematika természet tervezés torlódási hely turizmus turizmus szak urbán vallás valószínűségszámítás vizsgasor