Mindenkit sok szeretettel üdvözlök. Újabb elméleti alapozás fog következni. Természetesen a teljes mértékű tárgyalás most sem lesz célunk, inkább egy erős vázlatot és iránymutatást szeretnénk az olvasóknak nyújtani. Sajnos ettől a számtól kezdve egyre gyakrabban fogunk szorítkozni a matematikára, ez elkerülhetetlen, hiszen mindennek az alapja. Megpróbálom csak a legszükségesebbeket tárgyalni olyan formában, hogy az "átlag olvasó" számára is érthető legyen. A mostani témánk keretein belül a geometriai modellezés feladataival, koordinátarendszerekkel, pontokkal, görbékkel, felületekkel, függvényekkel és azok ábrázolásával foglalkozunk. Kezdjünk is hozzá.

Geometriai modellezés

A követezőekben a két illetve háromdimenziós geometria definiálásával fogunk foglalkozni. Ugyanis a modellezés során fő feladatunk az lesz, hogy a kívánt geometriát megfelelően meg tudjuk majd adni. Ezen kívül még foglakoznunk kell a transzformációkkal, színekkel, felületekkel, optikai tulajdonságokkal, azok definiálásával, és kezelésével.

Kezdésként létre kell hoznunk egy vonatkoztatási rendszert, virtuális világunkban. Mert ahhoz, hogy a térben meg tudjuk adni egy objektum helyzetét, szükségszerűen alkalmazni kell egy koordinátarendszert, mint már azt említettük. Ha már van egy rögzített koordinátarendszerünk, akkor a tárgyaink koordinátáit, megadhatjuk 2D esetén az x és y, 3D esetén az x, y, z számhármassal. A leggyakrabban használt koordinátarendszer a Descartes-koordináta-rendszer. Magát a rendszert ebben az eseten három egymásra merőleges egyenes alkotja. Ezek közös metszéspontja az origó. A koordinátatengelyekkel azonosan álló vektorokat, amelyek egymásra kölcsönösen merőlegesek, alapvektoroknak nevezzük. Jelölésük i, j, k. Az origótól a vizsgálandó P pontig húzott r vektort helyvektornak nevezzük. Ez a vektor mindig előállítható a három alapvektor kombinációjából: r=xi+yj+zk. Ha ez az összefüggés igaz, akkor a P pont és az r vektor koordinátái a következők (x,y,z). Az irányokat irány koszinuszokkal adjuk meg. Azoknak a szögeknek a koszinuszai ezek, amelyeket a vektor az egyes koordinátatengelyekkel zár be.

A másik gyakran használt koordinátarendszer a síkbeli Polár. Ezt két dimenzióban úgy képzeljük el, hogy adott a sugár (r) ami nem más, mint a helyvektor nagysága, és (f ) a félegyenessel bezárt szög. Ezzel a két koordinátával már pontosan megadható, pl. egy tömegközéppont helyzete. A fizikában körmozgások, parabola, ellipszis (pl. Bolygó mozgás) mentén létrejövő mozgások tárgyalásához előszeretettel használja. Ez alapján a henger koordinátarendszer már könnyen elképzelhető, hiszen egyrészt áll az x és y síkban lévő síkbeli polár koordinátarendszerből, és egy az erre ráillesztett z-tengelyből (k-egységvektort). Egy pont koordinátáit egy ilyen rendszerben az (r,f ,z) számhármas írja le.

Legvégül pedig ismerkedjünk meg a homogén koordinátarendszerrel, ami talán a legismeretlenebb az átlag olvasó előtt. Tömören arról lenne itt szó, hogy a 3D-s helyvektorainkat egy formális lépéssel négydimenzióssá egészítjük ki. A tér egy P pontjához vezető r=(x,y,z) vektort ezen túl (w*x, w*y, w*z,w) alakban írjuk. Természeten w egy nem nulla tetszőleges szám. Emiatt érdemes w-nek egy konkrét értéket választani, mondjuk az egyet. Ekkor az x,y,z,1 koordinátanégyest a P pont normalizált homogén koordinátáinak nevezzük. Sajnos a 3D-s tér homogén koordinátáit szemléletesen nem tudjuk bemutatni, de 2D-s koordináták esetén már megoldható az ábrázolás (lásd az ábrán). A lényege ennek a rendszernek vázlatosan ez volna. Ezt a nem csupán formális konstrukciót matematikailag az euklideszi tér ügynevezett projektiv lezárása teszi szükségessé. Ami alatt az értjük, hogy a teret kiegészítjük ideális térelemekkel. A számítógépes grafikában az ideális vagy "végtelen" távoli térelemek bevezetése azért volt érdekes, mert így a párhuzamos és nem párhuzamos térelemek kezelése egységes módon megoldhatóvá vált. Ami által sokkban leegyszerűsödtek a transzformációk programalgoritmusai!

Függvények

Csak pár szó erejéig szeretnék ezzel a fejezettel foglalkozni, mert úgy gondolom már mindenki halott élete során valamilyen függvényről, ezért annak általános magyarázatától eltekintenék. A figyelmet azért szeretném felhívni rájuk, mert ismeretük nélkülözhetetlen, másrészt meg felfoghatjuk úgy őket, mint görbéket. Mi pedig görbéket szeretnénk majd létrehozni. A mindennapi életbe a görbe fogalmán egy folytonos vonalat értünk, ami pontok halmaza. Ezt a halmazt pedig vektor vagy skalár egyenletekkel lehet definiálni. Gondoljunk csak egy, kör vagy egyenes egyenletére. Függvényeinket többféle alakban is megadhatjuk, mindegyiknek meg van a maga előnye. Mivel számos magyar irodalom is megemlíti az explicit, implicit alakot, érdemes ezeket a fogalmakat tisztázunk.

A függvények felírási alakja, lehet explicit, ilyenkor y mint x függvénye adott, vagyis az egyenlőség egyik oldalán csak y míg a másikon csak x áll. A függvénykapcsolat akkor implicit, ha abból y-t nem fejeztük ki. Meg lehet még említeni a parametrikus alakot is. Ilyenkor x és y összetartozó értékei valamilyen harmadik mennyiség (paraméter) segítségével adottak. Az ugyanazon a t paraméter által meghatározott x és y értékek tartoznak össze. Ilyen típusú függvénymegadást alkalmaznak síkbeli és térbeli mozgások leírására a fizikában, ilyenkor a t paraméter az időt jelenti. Először a függvények (síkgörbék) ún. explicit megadási módját fogjuk megismerni. Egy síkgörbe explicit egyenlete: y=f(x)

Azért, hogy mindenki jobban megértse írjuk fel a gimnáziumból már jól ismert R sugarú (x0,y0) koordinátájú kör explicit egyenletét: x=x0+R× cos2p t y=y0+R× cos2p t tÎ [ 0,1] Illetve implicit egyenletét: (x-x0)2+(y-y0)2-R2=0

Ezek alapján egy paraméteres előállítású síkgörbét a következő módon adhatunk meg:

x=x(t) y=y(t) tÎ [ 0,1] Ě R

Ebben az esetben a görbe pontjainak mindkét koordinátája egy-egy paraméter függvénye. A t a paraméter azt a tartományt futja be, amelyen szeretnénk a függvényt ábrázolni. Ezt a görbét simának nevezzük az intervallumon, ha minden pontjában, azaz a t paraméternek minden, az intervallum belsejéhez tartozó értékére létezik deriváltjai és ezek folytonosak.

Szabadformájú görbékről általánosan

A modellezés során számos olyan probléma vetődhet fel, amit majd nem tudunk megoldani, az előbb tárgyalt klasszikus görbékkel, mint amilyen például a kör, a szakasz, vagy az ellipszis. Gondoljunk csak a formatervezésre, az építészetre, ahol az objektumok alakjának esztétikusnak kell, hogy legyenek. Meghatározott formát kell, hogy kövessenek. Ezt viszont az eddigiek alapján nehezen tudnánk elérni.

Ezért más megoldást kell keresnünk. Ha jobban belegondolunk, akkor bármely görbe kellő pontossággal megközelíthető, megfelelő számú kis szakasszal. Ez igaz is, viszont ezek a görbék nem mindenütt differenciálhatóak, ami viszont nélkülözhetetlen a műszaki életben, pl. a mechanikában. Pontosan ezért az egyik feladatköre számos műszaki területnek, hogy bizonyos sorrendben elhelyezett pontsorozatra görbét vagy felületet illesszen. Azaz olyan görbéket (függvényeket) előállítani, amelyek alakját tetszőlegesen tudjuk alakítani. A síkbeli, és térbeli görbék modellezésének legfontosabb eszköze pedig a paraméteres vektor egyenlet. Egy r=r(t) tÎ [ t1,t2] paraméteres vektor-skalár függvény megoldását jelenti, ahol [ t1,t2] a paramétertartomány. Az egyenletet felírhatjuk komponensenként is: x=x(t), y=y(y), z=z(t) ahol t1< t< t2. Ezek alapján minden egyes t konkrét számértéket behelyettesítve, az egyenlet egy olyan r vektort állít elő, amely a térgörbe egy pontjába mutat. Az r(t) függvényről általában pedig azt feltételezzük, hogy folytonos, kölcsönösen egyértelmű, valamint t szerint differenciálható, és deriváltja nem nulla. Igen ám, de ezek alapján rengeteg vektor-skalár függvény szóba jöhetne a modellezés során. Ezért a legésszerűbb, ha a polinomok függvényosztályát választjuk, amelyben egy görbét az, ai, bi polinomegyütthatók megadásával specifikálhatjuk:

Hogy miért pont ezt választottuk, annak a matematikai alapját a Taylor-sorbafejtésben kell keresni. Röviden csak annyit róla, hogy így bármely végtelen sokszor differenciálható f(x) függvény tetszőlegesen megközelíthető. Nyilvánvalóan fontos kérdés még az, hogy hányad fokú polinomokkal érdemes közelíteni. Általánosan elmondható, hogy ha minél kisebb a fokszám annál könnyebb kiszámítani a függvény értékét, viszont túl alacsony fok szám esetében nem tudjuk megfelelően közelíteni a kívánt görbéket. Több ok miatt is, a harmadfokú polinomok terjedtek el a számítástechnikában. Most már általánosan fel tudunk írni egy szabadformájú görbét, de sajnos a polinom együtthatóknak nincsen szemléletes tartalma. Ami annyit tesz, hogy az együtthatókat magának a felhasználónak kellene megadnia, ami elégé kényelmetlené teszi használatukat a modellezés során. Pontosan ezért találták ki azt a megoldást, hogy az együtthatók közvetlen megadása helyett, vezérlőpontokat adunk meg, amik majd meg fogják határozni görbéink alakját. Tetszőleges sima görbék legkényelmesebb szerkesztési módja is ez. A szerkesztett görbe a pontok alakjából is jól kivehető lesz, hiszen a görbe bizonyos mértékben követni fogja a kontrolpontokat összekötő törtvonalakat (karakterisztikus keret).

Ami az illesztés módjait illeti, két alapvető módszer létezik. Amennyiben elvárjuk azt, hogy az illesztett görbe átmenjen minden kontrolponton, akkor interpolációs eljárásról beszélünk. Az approximációs módszerek esetében ez nem mindig áll fent, csak azt tudják garantálni, hogy nagyjából követni fogják az általuk kijelölt irányvonalat. Vagyis a kontroll pontsorozat között fog áthaladni nagy valószínűséggel a görbe. Az engedmények fejében számos jó tulajdonságot kapunk, mint pl. a kapott görbe simább lesz, és az előállításának együtthatói esetenként egyszerűbben meghatározhatóak.

Ezek alapján a későbbiekben a polinomiális közelítésekkel fogunk foglakozni, vagyis a felhasznált súlyfüggvények algebrai polinomok lesznek. Ezért tisztázzuk először azt, hogy mi is a súlyfüggvény. Legyen adott n+1 pontból álló kontrollpontsor, a rájuk vagy közéjük illeszkedő görbe a következő képen fog kinézni:

Az ábrán p0,p1, …, pn a kontrolpontok helyvektorai, ahol Ś k, k=0,1,…n pedig egyváltozós függvények, úgynevezett keverő (blendig) függvények. Súlyfüggvényeknek is szokták nevezni őket, ugyanis a fenti összefüggés rögzített t értékre a kontrolpontok helyvektorainak súlyozott közepét adja.

Lagrange-interpoláció

Talán az eddigiek kicsit nehezen érthetőek voltak, most megpróbálok tisztavizet önteni a pohárba, mielőtt a komolyabb görbeszerkesztési eljárásokkal megismerkednénk. Tegyük fel, hogy van nekünk egy adott vezérlőpontsorozatunk, p0(x0, y0), p1(x1, y1), p2(x2, y2), … pn(xn, yn). A feladatuk pedig az, hogy kössük össze úgy ezeket a pontokat, hogy a görbe keresztülmenjen az összesen, és közben közelítsünk is az egyes pontokhoz.

Vajon, hogyan oldható meg ez a feladat? Gondoljunk csak bele, hogy két pontra hányadfokú polinomot tudunk felírni, természetesen elsőfokút, háromra másodfokút, ezek alapján négyre pedig harmadfokút, stb. Tehát keressük azt a minimális fokszámú L(x) polinomot, amely x0-nál y0, x1-nél y1 … xn-nél yn értéket vesz fel. Figyelembe véve a feltételek számát, a megfelelő polinom n-1-d fokú lesz. Ezek alapján felírhatjuk a következő egyenletet:

L(x)=anxn+an-1xn-1+…+a1x+an ahol xÎ R vagy xÎ [x0,xn]

Ahhoz, hogy mindenki megértse vegyünk egy konkrét példát, amit matematikailag oldunk meg először. Legyen adott négy pontunk, mégpedig a p0(-1,1), p1(0,2), p2(1,1), p3(2,3). A fenti összefüggés a következő képen fog kinézni (négy pontunk van ezért a polinom fokszáma három): L(x)=a3x3+a2x2+a1x+a0 ahol xÎ R vagy xÎ [x0,x3] Ezután nincs más hátra mint, hogy behelyettesítjük a kontrolpontok x koordinátáit:

Mivel L(x0)=y0 így

L(x0)=a3(-1)3+a2(-1)2+a1(-1)+a0=1

L(x1)=a3(0)3+a2(0)2+a1(0)+a0=2 azaz a0=2

L(x2)=a3(1)3+a2(1)2+a1(1)+a0=1 azaz a3+a2+a1+a0=1

L(x3)=a3(2)3+a2(2)2+a1(2)+a0=3 azaz 8a3+4a2+2a1+a0=3

Ha az alábbi egyenletrendszert megoldjuk, az a3,a2,a1,a0 értékére a következőket kapjuk: a3=5/6, a2=-1, a1=-5/6, a0=-2. Ezeket visszahelyettesítve kapjuk meg a kereset függvényt L(x)=5/6x3-x2-5/6x+2 mely áthalad az általunk megadott kontrolpont sorozaton. A gyakorlati részben megírt függvényábrázoló rutinunkkal nagyszerűen meg tudjuk jeleníteni az ily módon előállított Lagrange görbénket, csak ezt a függvényt kell a számára megadni.

Mindez nagyon szép, de már négy pont esetén is eléggé körülményes megoldani az egyenletrendszereket. Másrészt mi azt szeretnénk, ha bármely kontrolpont sorozatra elvégezné a számítást automatikusan a gép. Szerencsére a megoldást egyből fel lehet írni:

A mi adott kontrolpontsorozatunk p0(-1,1), p1(0,2), p2(1,1), p3(2,3) esetén, a megoldás ezek alapján a következő:

P0(x)=(x-x1)*(x-x2)*(x-x3)/ (x0-x1)*(x0-x2)*(x0-x3)

P1(x)=(x-x0)*(x-x2)*(x-x3)/ (x1-x0)*(x1-x2)*(x1-x3)

P2(x)=(x-x0)*(x-x1)*(x-x3)/ (x2-x0)*(x2-x1)*(x2-x3)

P3(x)=(x-x0)*(x-x1)*(x-x2)/(x3-x0)*(x3-x1)*(x3-x2)

vagyis

L(x)=y0*p0(x)+y1*p1(x)+y2*p2(x)+y3*p3(x)

A fenti formulák megvalósításra egymásba ágyazott ciklusok ajánlhatóak, a gyakorlati részben majd látni is fogjuk, hogy hogyan. Érdekességként jegyzem csak meg, hogy a Li(t) lényegében az i. pont súlyát határozza meg a paraméter függvényében, ezért súly függvénynek nevezzük (blendig function). Sajnos bizonyos tartományokban a súlyfüggvények negatív értékűek ezért taszítják a görbét. Ebből származik az a szomorú tény, hogy a Lagrange-interpoláció hajlamos az oszcillációra, azaz olyan kanyarulatokat is felvehet, amik nem következnének a vezérlőpont sorozatból. Másik nagy hibája ennek az eljárásnak, hogy nehezen alakíthatóak ezek a görbék, hiszen egy vezérlőpont a görbe egészére kihat. Hogy mindezek ellenére miért foglalkoztunk vele ennyire részletesen, annak az volt az oka, hogy ez megfelelő alapot nyújt majd a további eljárásokhoz.

 

 

Gauss-approximáció

Az előzőekben az interpolációra néztünk meg egy feladatott, most egy egyszerű approximációt fussunk végig. Szokás ezt még lineáris- és nem lineáris (pl.: kvadratikus) regressziónak is nevezni, az alapján, hogy milyen függvénnyel közelítünk. Bár görbeszerkesztésre a mi szempontunkból ez nem igazán alkalmas, a matematikai alapok miatt célszerű vele foglalkozni, és abszolút nem haszontalan. Az elve a következő: legyen adott a x és y síkban p1, p2, p3… pn pontsorozat. A pi pont koordinátáit jelölje (xi,yi), ahol i=1,2,3…n és xjš xi, ha iš j. Vegyünk fel egy tetszőleges y=mx+b egyenest. Húzzunk párhuzamost pi-ből az y tengellyel, pi és az egyenes közti szakasz hosszát jelöljük di-vel. A feladatunk tehát az, hogy adjuk meg azt az y=mx+b egyenletű egyenest, amelyre: Ś (m,b)=S di2 minimális lesz. Ezt nevezzük a legkisebb négyzetek módszerének.

A függvény minimumának megfelelő egyenest regressziós egyenesnek fogjuk hívni. Az ábráról könnyen leolvasható, hogy di=ç mxi+b-yiç mikor lesz egyenlő. Ha ezt a fenti szummás részbe behelyettesítjük, akkor a következő kétváltozós függvényt kapjuk meg: Ś (m,b)=S (mxi+b-yi)2 Nincs más hátra, mint ennek a függvénynek a szélsőérték helyeit kell megkeresnünk, ezért képeznünk kell a parciális deriváltjait:

Ś "m(m,b)=2S (mxi+b-yi)xi2=0

Ś "b(m,b)=2S (mxi+b-yi)2=0

A szorzásokat, és az összegzéseket elvégezve kapjuk a következő formulákat:

mS xi2+bS xi= S xi*yi

mS xi+nb= S yi

Az átalakítások, és az egyenletrendszer megoldása után a következő képleteket kaphatjuk meg:

Természetesen a formulák helyett könnyebb azt megjegyezni, hogy hogyan lehet őket kiszámolni, vagyis az egyenletrendszerek megoldását. Megmutatható még az is, hogy a kapott regressziós egyenes mindig átmegy a pontrendszer súlypontján is, azaz az Sp((S xi)/n), (S yi)/n)) ponton. Így ha a koordinátarendszert eltoljuk a pontrendszer súlypontjába, akkor az egyenes egyenlete y=mx, azaz egyváltozós problémát kapunk. Ezt az eljárást alkalmazzák lineáris trendek felvételére például, persze a függvény nem csak y=mx+b alakú lehet, hanem 2,3,..n-ed fokú polinom, vagy logaritmikus, exponenciális függvény. A fenti képletek alapján könnyedén megvalósítható ez az eljárás, a kapott eredmény pedig egyszerűen leellenőrizhető, pl. az MS Excelben trend vonal felvételével.

Ennyit gondoltam mára, legközelebb a további interpolációs és approximációs eljárásokkal fogunk foglalkozni, addig is bátran forgassátok a könyveket.

Felhasznált és ajánlott irodalom:

Foley, van Dam, Feiner, and Hughes: "Számítógépes grafika: Alapelvek és gyakorlat" c. (Fordította: Gombás Áron - 1996)

Dr. Szirmay-Kalos László: Számítógépes grafika, 2001

Bárczy-Barnabás: Differenciálszámítás, 2001

Turcsányi Tamás, Debreceni Egyetem, 2000

Budai Attila: Számítógépes grafika, 1999

Füzi János: Interaktív grafika, 1997