A görbék "történelme"

Arról már szó esett, hogy görbéket hogyan írhatunk le általánosan, de arról még nem, hogy mi késztette a mérnököket a kifejlesztésükre. A probléma ott kezdődött, hogy a hagyományos geometriai ábrázolási módok és a rendelkezésre álló szerkesztések nem tették lehetővé tetszőleges térbeli alakzatok ábrázolását. Néhány kivételtől eltekintve csak a sík, az egyenes és a pont volt ábrázolható térbeli elem. Természetesen a mérnöki igényeket ezek nem elégítették ki, ennél jóval tovább mentek, és találtak is bizonyos, matematikailag nem értékelhető megoldásokat. Az egyik legfontosabb ilyen igény a görbék ábrázolásával kapcsolatosan merült fel. Ez már akkor probléma volt, amikor hajókat terveztek, és annak például a víztörő orrát kellett megrajzolni. Ez nagyon fontos darabja volt a hajónak, mert nagyban megszabta a hajó sebességét. A szerkesztéskor a hajó orrából már megtervezett néhány pontot kellett egy "szép", sima görbével összekötniük. Ezt még az ötvenes években is egy rugalmas faléccel, melyet az angolok "spline"-nak (ejtsd: "szplájn") neveztek, végezték el úgy, hogy azt a megadott pontokra ráfeszítették, majd mellette meghúzták a vonalat. Úgy működött, hogy bevertek néhány szöget a fába (kontrollpontok), amelyre rá akarták rajzolni a megfelelő görbét, méghozzá úgy, hogy a szögek a kívánt görbe pontjai voltak. Ezután jött a spline (ez végül is egy hajlékony vonalzó) amit ráhajlítottak a megfelelő szögekre és meg tudták rajzolni a kívánt görbét, majd a megrajzolt görbe mentén el vágták a fát. Ezt a technikát még a műszaki rajzban is alkalmazták. Hasonlóan van ez a miáltalunk használt spline-oknál is, mi a szögeket kontrolpontoknak nevezzük, majd egy függvény interpolálja a görbét a kontrolpontok közt. A görbe előállítás elméleti problémáját először Európában sikerült megoldani. Olyan görbékre volt szükség a fentebb már részletezett okokból, melyek aránylag kevés adattal megadhatók, de ugyanakkor elég flexibilisek ahhoz, hogy gyakorlatilag mindent le lehessen rajzolni velük. Fontos feltétel volt az is, hogy az a néhány meghatározó adat "emberileg" is követhetően írja le a görbét, és a számítógép is gyorsan, aránylag kevés művelettel tudja kiszámolni a görbét. További feltétel volt, hogy mivel a mérnöki gyakorlatban a térbeli alakzatot annak merőleges vetületével szokás ábrázolni (lásd axonometrikus és Monge-féle ábrázolás), a görbe merőleges vetületét is gyorsan lehessen számolni, rajzolni. A megoldás a Citroën és a Renault autógyáraknál gyakorlatilag egyidőben született meg. Azt, hogy a fenti feltételek mennyire egyértelműen meghatározzák a megoldást, jól mutatja, hogy mind a két helyen azonos eredményre jutottak. A Citroënnél de~Casteljau (ejtsd: "dökasztelzsó") 1959-ben, a Renaultnál Bézier (ejtsd: "bezié") 1962-ben fedezte fel az új görbéket, melyeket ma már az első nyilvános közlés alapján egyértelműen Bézier görbéknek neveznek. A vektorgrafikai szoftverek (melyek nem közvetlenül a képpontokat manipulálják, hanem egyenesekkel és görbékkel építik fel a képeket) kiterjedten használják a spline-okat. Ilyen szoftver például a CorelDRAW, vagy az MS Word rajzoló programrésze, de spline-okat lehet rajzolni az MS Paint-ben is, és a 3D Studio pedig a spline-technikára épül: a program egyenesek és körök helyett is speciális spline-okat használ.

Az ívdarabok folytonos csatlakozása

Ha majd a görbéinket ívdarabokból foglyuk összerakni, akkor fontos kérdés, hogy ezek milyen módon csatlakozhatóak folytonosan az illesztési pontokban. Nyilván azt szeretnénk, hogy az illeszkedés törésmentes legyen, vagyis "simán" történjen. Másképpen megfogalmazva a képernyőn ne lehessen észrevenni, hogy az ív több darabból épül fel. Ezt a követelményt matematikailag az illesztési pontokban történő folytonos átmenetekkel tudjuk kezelni. Ezeket az egzakt definíció helyett inkább ábrákon szemléljük meg.

C0 matematikai folytonosság

Ebben az esetben a két görbedarabnak az illesztési pontban lehet törése, viszont hézagmentesen kell csatlakozniuk egymáshoz.

C1 matematikai folytonosság

Ebben az esetben a két görbedarabnak az illesztési pontban az érintője is megegyezik, azaz első deriváltjuk azonos.

C2 matematikai folytonosság

Ebben az esetben a két görbedarabnak az illesztési pontban nem csak az érintőjük azonos, hanem a görbületük is megegyezik (azaz az első és második deriváltjuk is megegyezik).

G1 matematikai folytonosság

Ebben az esetben a két görbedarabnak az illesztési pontban nem kell, hogy megegyezzen az első és második deriváltja. Csak az érintő egyenes azonos, de a derivált vektor nagysága és előjele eltérő lehet.

 

Coons-Hermite interpoláció

Kezdetnek nézzünk meg egy összetettebb, de mégis egyszerűbb interpolációs eljárást, amin keresztül majd könnyebben tudjuk megérteni a többit. A Coons-Hermite interpoláció az illesztési feladatot a kontroll poligon (karakterisztikus keret) egy-egy szakaszára helyileg végzi el. Ehhez viszont szükség van még a görbe kontrolpontjaiban lévő érintővektorok értékeire is. A két szomszédos kontrolpontot összekötő görbeív analitikus előállítása a következő:

    r(n)=a3n3+a2n2+a1n1+a0nÎ[0,1]

Az ív két végének a két (p0 és p1) kontrolpontra kell támaszkodnia, a végpontokban az érintő egyenlő kell, hogy legyen az adott értékekkel. Ebből adódik, hogy meg lehet határozni a harmadfogú súlyfüggvényeket, amelyek majd kielégítik a feltételeket.

    Ś 1(n)=2n3-3n2-1

    Ś 2(n)=-2n3+3n2

    Ś 3(n)= n3-2n2+n

    Ś 4(n)=n3-n2

Legyen tehát most adva a térben p0 és p1 pont, valamint a generálandó ívdarab érintője p0-ban a p0nés p1-ben p1n. Ekkor a görbe előállítása a következő lesz:

r(n)= Ś 1(n)p0+Ś 2(n)p1+Ś 3(n)p0n+Ś 4(n)p1n

Szemléletesen látható, hogy a Hermite-ívekből törésmentesen (C1 matematikai folytonossággal) tudunk görbéket előállítani. Ezeket jellemzi, hogy a görbe áthalad a tartópontokon. Ugyanakkor a számítógépes grafikában történő alkalmazásában gondot okoz, hogy ezek a paramétertartományok affin transzformációkra nem invariánsak.

A fenti egyenletet külön-külön kell alkalmazni X,Y koordinátákra. Az érintő folytonosságának feltétele az, hogy a szomszédos íveknek a közös pontjakban azonos legyen az érintőjük. A görbe alakja tehát ebből adódóan a négy határfeltétel bármelyikének változtatásával megváltoztatható. Az érintők meghatározását könnyen megoldhatjuk úgy, hogy a program minden belső kontrolponthoz tartozó érintőt a két szomszédos kontrolpontot összekötő vektoraként számít ki. Tehát a fenti egyenletünk a pi és pi+1 pontokat összekötő görbeív esetén a következő: r(n)= Ś 1(n)pi+Ś 2(n)pi+1+Ś 3(n)pin+Ś 4(n)pi+1n Ennek az egyenletnek az előállításában :

    p0n=p1-p0

    pin=pi+1-pi-1 i=1,2,…,n-1

    pkn=pk-pk-1

Az ezzel a módszerrel előállott görbéink lehetnek nyitottak és zártak. Nyílt görbe esetén az érintő az illető pontot a szomszédos kontrolponttal összekötő vektor. Ha az érintőszámítást elhagynánk, akkor csak a kontrolpontokat összekötő egyeneseket kapnánk meg, és nem a kívánt görbénket. Természetesen az érintőket mi magunk is megadhatjuk manuálisan nem szükséges ezt az eljárást használni.

Ha az érintőket megszorozzuk egy k0 számmal a görbe alakja megváltozik, viszont az érintő folytonos marad. Egyre kisebb k0 értékekre a görbe alakjának a változása fokozatosan csökken. Ezt talán úgy lehet elképzelni, mintha kifeszítenénk egyre jobban egy rugalmas huzalt. Nagyobb értékekre pedig megnövekedik a görbe változásának a mértéke, olyannyira hogy akár újabb hurkok is megjelenhetnek. Megfigyelhető még az is, hogy negatív k0 számokra görbén ugyancsak hurkok jelennek meg, amik várhatóak is voltak. Ha ez a k0 szám 0,5 értéknek megfelelő lesz, akkor eljutunk az Overhauser interpolációhoz. A Coons-Hermite interpolációs eljárás megvalósítását a ch_ip1.pas fájl tartalmazza.

 

Bézier-approximáció

A Bézier approximációt Pierre Beizer dolgozta ki az 1960-as években különböző tervezőprogramok (CAD/CAM) részére. A Bézier közelítés kifejlesztésének a lényege az volt, hogy sima görbéket és felületeket lehessen szerkeszteni a kontrolpontok segítségével. Ha feladjuk azt a megkötésünket, hogy a keletkezett görbének át kell mennie minden kontrolponton akkor a kontrolpontokból nem következő hullámosság eltüntethető. Azok a görbék és felületek simák lesznek, amelyek nem lépnek ki a kontrolpontok által határolt kontrol poligon konvex burkából. A konvex burkot úgy lehet a legjobban elképzelni, mintha becsomagolnánk egy ajándékot valaki részére. Ilyenkor a csomagolópapír a felületek konvex burkára simul rá. A konvex burokban való maradás feltétele az, hogy a súlyfüggvények értéke ne legyen negatív, és összegük mindenhol 1 legyen. A Renault műveknél ezt az eljárást a gépjárműkarosszéria tervezésére 1972-óta használja, és ha jól emlékezem a Quake3 is, felvonultatja!

Az előző szám végefelé, ha minden igaz elmondtam, a görbék előállításainak elvét. Ha valaki nem emlékezne, akkor most itt még egyszer röviden összefoglalom: ha adott n+1 pontból álló kontrollpontsor, a rájuk (interpoláció) vagy közéjük (approximáció) illeszkedő görbe a következő képen néz ki:

n

r(u)=S Ś k(u)pk

k=0

Ahol p0,p1, …, pn a kontrolpontok helyvektorai, Ś k, k=0,1,…n pedig egyváltozós függvények, úgynevezett keverő (blendig) függvények. Az ehhez hasonló függvények a következő feltételeknek tesznek eleget:

    • A görbe átmegy a szélső pontokon (p0, pn)
    • Az érintő a szélső pontokban p1-p0 illetve pn-1-pn legyen
    • A magasabb rendű deriváltak is hasonló módon álljanak elő
    • A súlyfüggvények szimmetrikusak legyenek, a sorrend megfordítása ne befolyásolja a görbe alakját.

Egy fontos súlyfüggvény készlethez juthatunk a (t+(1-t))n binomális tétel szerinti kifejtésével. A kifejtés egyes tagjait Bernstein polinomnak hívják, amik kielégítik a fenti feltételeket. Alakja:

(A B(n)k(t) kifejezésben az "n" nem hatványkitevő, hanem felső index, ami a polinom fokszámát jelöli). A Bézier görbék előállítása tehát a következő:

Ezek után ismerkedjünk meg a Bézier görbe legegyszerűbb formájával a harmadfokú Bézier görbével. A helyi alakmódosítást leggyakrabban ezzel a módszerrel valósítják meg, mégpedig úgy, hogy egy harmadfokú Bézier görbét szerkesztenek 2-2 kontrollponttal, és ezeket illesztik. A kontrolpontok közül egy kezdő, egy végpont, a maradék kettő pedig iránypontként fogható fel. Az egyszerűség kedvéért azt az esetet nézzük, amikor csak 4 alappont (kontrollpont) van. Ekkor a görbe áthalad az elsőn és az utolsón, s a közbülsőket csak közelíti, approximálja. P0 és P3 legyen a két szélső kontrollpont. Ekkor a köztük lévő görbeív minden pontja megadható x(u), y(u) alakban, ahol u 0-tól 1-ig nő. x(u), y(u) ,ahol 0Ł u Ł 1

Tegyük fel, hogy adottak a következő alappontok: P0(x0,y0), P1(x1,y1), P2(x2,y2), P3(x3, y3). Ekkor a P0 és P3 pont közti görbeív úgy határozható meg, hogy kiszámítjuk az x(u), y(u) értékét (ahol ugye u 0-tól 1-ig nő). Összevonva így is írhatnánk: C(t) = (u3 u2 u 1) * B * (P0 P1 P2 P3)T Ahol a B mátrix:

|-1 +3 -3 +1|
|+3 -6 +3 +0|
|-3 +3 +0 +0|
|+1 +0 +0 +0|

Jelöljük az egyes pontok x koordinátáit X0, X1, X2, X3-al, míg az y koordinátákat Y0, Y1, Y2, Y3-vel. Ekkor a mátrixszorzást elvégezve a következőt kapjuk x(t)-re:

x(t) = ( -t3 + 3*t2 - 3*t + 1) * X0 +( 3*t3 - 6*t2 + 3*t ) * X1 +(-3*t3 + 3*t2 ) * X2 +( t3 ) * X3

Hasonlóan kapnánk meg y(t) -t is, csak ott X0, ..., X3 helyett Y0, ..., Y3-al kell számolni. Tehát az összevonások és mátrixszorzások után a fenti görbét egy harmadfokú egyenlet írja le:

r(u)=(1-u)3p0+3u(1-u)2p1+3u2(1-u)p2+u3p3

A p0,p1,p2,p3 betűk természetesen pontokat (kontrolpontokat) jelentenek, ezt fogjuk majd a megvalósítás során is használni.

 

B-spline approximáció

A spline interpoláció lényeges előnye a Coons-Hermite interpolációval, hogy nem kell megadni az érintőket a kontrolpontokban. Elegendő a kontrollpontok koordinátái is. Viszont hátrányos tulajdonsága, hogy egyetlen pont elmozdítása hatással van az egész görbe alakjára. Ezt a hiányosságát próbálja kiköszörülni a B-spline approximáció.

Bár ugyan a Bézier-ívek a vetítésekre vonatkozó invarianciától eltekintve a görbék modellezésével szemben támasztott összes követelménynek eleget tesznek, kivéve a következőket:

  • ha a kontrolpontok száma nagy, az algoritmusok számításigénye nagyon megnőhet.
  • A kontrolpontok megváltoztatása az egész göbe alakjára kihat.

Ezeket a nehézséget küszöböli ki a B-spline görbék alkalmazása. A görbealak helyi ellenőrzése, és az úgynevezett globális simaság követelményeit legjobban és egyidejűleg a B-spline közelítés valósítja meg. Ez azt jelenti, hogy egy vezérlőpont, csak az összetett görbe 4 legközelebbi szegemsének alakjára hat, a távolabbi részekre tehát nem. Tehát egy vezérlőpont megváltoztatása csak egy kicsit módosít a görbén.

Az ilyen típusú görbéket lokálisan vezérelhető görbéknek is nevezhetjük. A számítógépes programok is ezt az eljárást használják előszeretettel. A szokásos alakban fogjuk keresni a görbeszegmenst, ahol a négy vezérlőpont súlyozásával kapjuk meg a görbét. Legyen tehát adva P0, P1, … ,Pn (n+1) db kontrolpont a p0 p1 … pk vektorokkal (B-spline görbék esetén ezeket Boor-pontoknak nevezzük). Ekkor a B-spline görbék előállítása a következő:

n

r(t)=S Bk,i(t)pk

k=0

Az összefüggésben szereplő Bk,i(t) B-spline bázisfüggvényeket súlyfüggvényeknek is nevezik (blending functions). A P0 … Pn kontrolpontok által meghatározott poligont Boor-poligonnak nevezik. Az i értékét a B-spline görbe rendjének nevezzük. (A gyakorlatban i értéke 4, ebben az esetben köbös polinomokat használunk.) A B-spline függvények szakaszonként értelmezett polinomok, amelyeknek foka i nem függ a kontrolpontok számától, hanem a felhasználó adja meg. Legelterjedtebb a másod, és harmadfokú B-spline közelítés. Mi most csak a harmadfokú B-spline görbékkel foglalkozunk. A fenti formulát tehát akkor írjuk le négy kontrolpont esetére, ami a következő lesz: r(t)=B0(t)*p0+ B1(t)*p1+ B2(t)*p2+ B3(t)*p3
Láthatjuk, hogy a kiszámításhoz még a B-spline súlyfüggvényeket kell meghatároznunk, szerencsére ezeket már elvégezte előttünk C. de Boor, M. Cox és L. Mansfield matematikusok. Az ő munkásságuknak köszönhető egyébként, hogy felfedezték a bázisfüggvények rekurzív tulajdonságait, és megalkották a számítógépes kezelésükhöz szükséges algoritmusokat is.

Ezek alapján egy harmadfokú periodikus B-spline függvények segítségével előállított görbeív, az átalakítások után:
Az egész görbét itt is úgy állítjuk elő, hogy i index értékét növelve megkapjuk az egymáshoz másodrendű folytonos görbülettel illeszkedő íveket. Tulajdonképpen a pi-1 pi és a pi-1 pi+1 szakaszok felezőpontját összekötő parabolaív, amelynek az említett szakaszok a végpontjaiban érintői. Bár az B-spline görbe alapvetően approximációs jellegű, interpolációs feladatokra is alkalmazható. A B-spline görbék már majdnem minden igényt kielégítenek a modellezéssel kapcsolatosan, de még mindig nem rendelkeznek a centrális vetítésekre vonatkozó invariancia tulajdonságával. Ezért vezették be a racionális görbéket a számítógépes grafikában. A legfontosabb közülük a NURBS (Non Uniform Rational B-spline) görbéket melyek öröklik a B-spline görbék összes előnyös tulajdonságát. Ez egy eléggé összetett terület, ezért mi most csak megemlítettük. Ha lesz rá igény, később foglalkozhatunk velük. Én mára csak ennyit gondoltam. Legközelebb már a térben fogunk dolgozni és előkerülnek a felületek is.

Felhasznált és ajánlott irodalom:

Foley, van Dam, Feiner, and Hughes: "Számítógépes grafika: Alapelvek és gyakorlat" c.
Dr. Szirmay-Kalos László: Számítógépes grafika, 2001
L. Ammeraal: Programming Principles in Computer Graphics
Bárczy-Barnabás: Differenciálszámítás, 2001
Turcsányi Tamás, Debreceni Egyetem, 2000
Füzi János: Interaktív grafika, 1997