Addig már eljutottunk, hogy tudunk függvényeket megjeleníteni, valamint egyszerűbb görbéket létrehozni. Most haladunk tovább, de már mindezt interaktívan a felhasználó teheti majd meg, a kontrollpontok mozgatásával. A mi feladatunk pedig az lesz, hogy ezt a kapcsolatot biztosítjuk a gép és a felhasználó között. Ezért a cikk elején általánosan tárgyaljuk a felhasznált rutinokat, majd külön-külön térünk ki az éppen tárgyalt interpolációs és approximációs eljárásokra. A források Delphi-ben készültek, de mellékelve van a Pascal és Java változat is.

Általános eljárások

A kontrollpontokat most is a kp tömbben tároljuk, ami pn darabú Tpoint típusú rekordot fog tartalmazni.

Const pn=4; Var   kp : Array [1..pn] of Tpoint;       Kivalasztott : integer;

Ha szükségünk lenne az egyes kontrolpontokhoz tartozó érintőkre is, akkor azokat ugyan így tárolhatjuk el, pl.: ep : Array [1..pn] of Tpoint; A form létrehozásakor meghatározzuk az alapábra pontjait, el lehet őket helyezni egy egyenes-, egy körmentén, de tetszőlegesen is. A skálázást, és koordináta transzformációt már a pontok megadásánál megtesszük, így később már nem lesz rá szükség. Inicializáljuk a kivalasztott értéket is, -1 alapértéket adunk meg, ezzel jelezve, hogy nincs kiválasztott kontrolpont a felhasználó által. Például:

procedure TForm1.FormCreate(Sender: TObject); begin // Létrehozzuk az alapábra pontjait   xk:=ClientWidth div 2; yk:=ClientHeight div 2;   kp[1].x:=xk+(-9*scale); kp[1].y:=yk-(0*scale);   kp[2].x:=xk+(-4*scale); kp[2].y:=yk-(0*scale);   kp[3].x:=xk+(4*scale); kp[3].y:=yk-(0*scale);   kp[4].x:=xk+(9*scale); kp[4].y:=yk-(0*scale);   kivalasztott:=-1; end;

A poligonok, kontrollpontok, görbék rajzolás ugyan úgy az OnPaint eseményben fog történni, mint eddig:

procedure TForm1.FormPaint(Sender: TObject);

A pontkeres függvénnyel fogjuk megkeresni az egérhez legközelebb álló kontrolpontot, így nem kell pontosan ráklikkelni, csak közel hozzá. A paraméterei a form koordináták lesznek, visszatérési értéke pedig a kontrolpont. Az ábráról látható, hogy a kontrolpont x és y koordinátájából vonjuk ki az egér koordinátáit, ez negatív érték is lehet, ezért négyzetre emeljük, majd az x és y értéket összegezzük. Ez jól fogja jellemezni a kontrolpontnak az egértől való távolságát. Ha megnézzük az összes pontra nézve ezt az értéket, a legkisebb lesz az, amely legközelebb áll az egérhez. Az ötlet nagyon jó, és a Programozzunk Delphi 5 rendszerben című könyvben megtalálható.

Function Pontkeres(x,y:integer):integer; // A függvény kikeresi az x,y ponthoz legközelebbi sarokpontot var tav,tav1,tav2,tav12:real;     i:integer; begin   tav:=10000;   Pontkeres:=-1;   for i:=1 to pn do   begin     tav1:=(kp[i].x-x);     tav2:=(kp[i].y-y);     tav1:=tav1*tav1;     tav2:=tav2*tav2;     tav12:=tav1+tav2;     if tav12<tav then     begin       tav:=tav12;       Pontkeres:=i;    end;   end; end;

Egérgomb lenyomásakor kikeressük az egérhez legközelebb álló kontrolpontot, hogy könnyedén el lehessen mozdítani majd:

procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer);
begin
  kivalasztott:=Pontkeres(x,y); //Gombnyomással pontot választunk
end;

Ha elengedjük az egérgombot, akkor nem kell kiválasztott kontrollpont, -1 értéket töltünk a változóba vissza:

procedure TForm1.FormMouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); begin   kivalasztott:=-1; end;

Lenyomott egérgömb esetén a kiválasztott pont koordinátái változnak, és ezért újra festjük a formot:

procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X, Y: Integer); begin   // Ha van kiválasztott pont (lenyomott egérgomb), akkor az mozog   if (kivalasztott>-1) then   begin     if (kivalasztott<>0) and (kivalasztott<>pn+1) then     begin       kp[kivalasztott].x:=x;       kp[kivalasztott].y:=y;     end;     Refresh;   end; end;

Az elméleti részben az eljárások során, a formulákban számos négyzetre, köbre emelést láthatunk. Eddig ezeket az értékeket úgy számoltuk ki, hogy előre egy változóban tároltuk el őket. Így viszont rengeteg változott kellett megadnunk, ami valljuk be nem egy elegáns megoldás. Most írjunk mi magunk egy olyan függvényt, amely magától kiszámolja az értékeket a fokszámtól függően. A függvényünknek első lépésben meg kell majd adnunk azt, amit majd hatványra emelünk, majd a fokszámot. Az első legyen x, míg a második n változó.

Function sk(x : real; n : word) : real; Var nt : word;     res : real; begin   res := 1;   for nt := 1 to n do     res:= res * x;   sk := res; end;

Láthatjuk, hogy egy ciklussal számoltatjuk ki egytől n-ig a kívánt értéket, úgy hogy a hatvány alapot önmagával szorozzuk össze. Kezdő értéknek az egyet adtuk meg, mert egyszer valami, az valami lesz. És valami szorozva valamivel az nem más, mint valami négyzete, és így tovább. Miután a ciklus befejeződött, a végeredményt a sk nevű változóba töltjük.

Coons-Hermite interpoláció

Legyen 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

A fenti egyenletet külön-külön kell alkalmazni X,Y koordinátákra. Az n értékét 0-tól 1-ig kell léptetni, tetszőleges lépésközzel, attól függően, hogy hány pontot akarunk a görbéből. Nyílt görbe estén x és y koordinátákra felírva a következő képen néz ki:

n:=j/PontSz; xp:=round(((2*sk(n,3)-3*sk(n,2)+1)*kp[i].x+(2*sk(n,3)+3*sk(n,2))*kp[i+1].x+     (sk(n,3)-2*sk(n,2)+n)*ep[i].x+(sk(n,3)-sk(n,2))*ep[i+1].x)); yp:=round(((2*sk(n,3)-3*sk(n,2)+1)*kp[i].y+(2*sk(n,3)+3*sk(n,2))*kp[i+1].y+     (sk(n,3)-2*sk(n,2)+n)*ep[i].y+(sk(n,3)-sk(n,2))*ep[i+1].y));

Zárt görbe estén annyi a különbség, hogy amikor elérkezzük a pn-edik ponthoz akkor a felírásba a pn-edik és az első kontrolpont, valamint azok érintője kerül kiszámításra, más esetben minden marad ugyan úgy. Az érintőket két kontrolpont távolságaként számoljuk ki. Természeten manuálisan is megadhatjuk őket, nem muszáj ezt az eljárást használni:

Procedure ErintoSz; {Érintőszámítás} begin   case ch of   'n':begin {nyílt görbe esetére}         ep[1].x:=round( (kp[2].x-kp[1].x )*k0);         ep[1].y:=round( (kp[2].y-kp[1].y )*k0);         ep[pn].x:=round((kp[pn].x-kp[pn-1].x)*k0);         ep[pn].y:=round((kp[pn].y-kp[pn-1].y)*k0);       end;   'z':begin {zárt görbe esetére}         ep[1].x:=round((kp[2].x-kp[pn].x)*k0);         ep[1].y:=round((kp[2].y-kp[pn].y)*k0);         ep[pn].x:=round((kp[1].x-kp[pn-1].x)*k0);         ep[pn].y:=round((kp[1].y-kp[pn-1].y)*k0);       end;   end;   for k:=2 to pn-1 do   begin {mindkét görbe esetén}     ep[k].x:=round((kp[k+1].x-kp[k-1].x)*k0);     ep[k].y:=round((kp[k+1].y-kp[k-1].y)*k0);   end; end;

Ha az érintőket megszorozzuk egy k0 számmal a görbe alakja megváltozik, viszont az érintő folytonos marad. Így ezzel is "szerkeszthető" a görbe alakja, nem csak a kontrolpontokkal.

Bézier-approximáció

Az összevonások és mátrixszorzások után a keresett görbét egy harmadfokú egyenlet írja le amint azt, beláttuk már:

r(t)=(1-t)3p0+3t(1-t)2p1+3t2(1-t)p2+t3p3

 

A p0,p1,p2,p3 betűk természetesen pontokat (kontrolpontokat) jelentenek. Az egyenletet természetesen külön-külön kell alkalmazni X és Y koordinátákra, kicsit leegyszerűsítve:

x(u)=(1-t)3* X0+3*t*(1-t)2* X1+3*t2*(1-t)* X2+t3* X3;
y(u)=(1-t)3* Y0+3*t*(1-t)2* Y1+3*t2*(1-t)* Y2+t3* Y3
;

A P1 és P4 közti részt felosztjuk N részre (N==30 vagy N==40 már elég a folytonos ívhez), tehát az t értékét 0-tól 1-ig kell léptetni, tetszőleges lépésközzel, attól függően, hogy hány pontot akarunk a görbéből. Ha N darab pontot akarunk, akkor a lépésköz értelemszerűen 1/(N-1). Ezek után kiszámoljuk az egyes X és Y koordinátákat, s azokat egyenesekkel összekötjük. Térbeli görbék előállítása során az X, Y koordináták mellett a Z koordinátára is el kell végezni számítást, ilyenkor 9 állandók lesz majd. Delphi-ben valahogy, így néznének ki a fenti egyenletek:

Procedure Bezier(t : real; var x, y : integer); begin // r(u)=((1-t)^3)P0+(3t(1-t)^2)P1+3(t^2)(1-t)P2+(t^3)P3   x:= round(sk(1-t,3)*kp[1].X+3*t*sk(1-t,2)*+kp[2].X+3*t*t*(1-t)*kp[3].X+sk(t,3)*kp[4].X);   y:= round(sk(1-t,3)*kp[1].Y+3*t*sk(1-t,2)*+kp[2].Y+3*t*t*(1-t)*kp[3].Y+sk(t,3)*kp[4].Y); end;

Természetesen a Delphi-ben ezt a fajta görbét kényelmesen előállíthatjuk a procedure PolyBezier(const Points: array of TPoint); metódussal, a Points tartópontok által meghatározott Bezier görbe rajzolására. Le lehet ellenőrizni, hogy mi görbénk, és Delphi-é egyforma eredményt fog e adni.

B-spline approximáció

Az elméletben már megkaptuk a kívánt együtthatókat, így azokkal most nem foglalkozunk. A változatosság kedvéért ez alkalommal java forrást fogunk boncolgatni a megvalósítás során. A többi görbeillesztő algoritmushoz hasonlóan a lényege most is ugyan az. Meg kell adnunk néhány kontrollpontot (legalább 4-et), s a pontok pozíciója alapján ezekre egy harmadfokú görbét illeszteni. Ez egy approximációs, közelítő módszer, vagyis a görbe nem fog átmenni a pontokon, csupán közelíti azokat (ez az ára annak, hogy a görbe szép, egyenletes). Két egymást követő pont közti görbeív pontjainak meghatározásához fel kell még használni ezek szomszédjait is, ezért kell tehát legalább 4 pont. P és Q legyen két egymást követő pont. Ekkor a köztük lévő görbeív minden pontja megadható x(t), y(t) alakban, ahol t 0-tól 1-ig nő.

x(t), y(t) ,ahol 0Ł t Ł 1

Tegyük fel, hogy adottak a következő alappontok:

P0(x0,y0)
P1(x1,y1)
...
Pn(xn, yn)

Ekkor a Pi és Pi+1 pont közti görbeív harmadfokú B-spline függvények segítségével úgy határozható meg, hogy kiszámítjuk az x(t), y(t) értékét (ahol t nő 0-tól 1-ig):

x(t)=((a3t+a2)t+a1)t+a0
y(t)=((b3t+b2)t+b1)t+b0
Az együtthatók:

a3=(-xi-1+3xi-3xi+1+xi+2)/6
a2=(xi-1-2xi+xi+1)/2
a1=(-xi-1+xi+1)/2
a0=(xi-1+4xi+xi+1)/6

b3=(-yi-1+3yi-3yi+1+yi+2)/6
b2=(yi-1-2yi+yi+1)/2
b1=(-yi-1+yi+1)/2
b0=(yi-1+4yi+yi+1)/6

Két pont közti görbe pontjainak meghatározásához az a3,a2,a1,a0 és b3,b2,b1,b0 értékeket elég egyszer meghatározni! A pontok x és y koordinátáját tömbben tároljuk el itt is (tomb_x[] és tomb_y[]). Ha zárt görbét akarunk kialakítani, akkor ezt a tömböt "ciklikussá" kell tenni, vagyis:

D A B C D A B

Adott 4 pont: A, B, C, D. Ekkor az első (A) elé felvesszük az utolsót (D), az utolsó (D) után pedig felvesszük az első kettőt (A, B). Így kapjuk meg az előző tömböt. (Hiszen emlékszünk: 2 pont közti ívhez 4 pont koordinátáját használjuk fel: a megelőzőt, ill. a rákövetkezőt. AB esetén kell az előző: D, a D-t pedig A-val kell összekötni, így a DA ív esetén kell a C,D,A,B). A következő kódrészlet ezt a feladatot látja el:

  tomb_x[0]=tomb_x[pos] ; tomb_y[0]=tomb_y[pos] ;   tomb_x[pos+1]=tomb_x[1]; tomb_y[pos+1]=tomb_y[1];   tomb_x[pos+2]=tomb_x[2]; tomb_y[pos+2]=tomb_y[2];

Az int pos; változóban tartjuk nyilván a pontok számát. Ezután jön egy ciklus: A,B,C,D esetén például 4 ívdarabot kell rajzolnunk: AB, BC, CD, DA-t. Minden ilyen ívdarabhoz 4 pont kell, ezek koordinátáját xA,...,xD, yA,...,yD fogja tartalmazni. Kiszámoljuk az együtthatókat, majd az ívdarabot felosztjuk N részre. Ha N-et elég nagynak választjuk (N==30, N==40 már elegendő), akkor szép egyenletes ívhez jutunk. X, Y a görbe x, ill. y koordinátáit fogja megadni. Ezt összekötjük az előzővel (X_prev, Y_prev) egy egyenessel, és készen is vagyunk. A w2v_x(X_prev),w2v_y(Y_prev) függvényhívás csupán egy "window to viewport" transzformáció, ami a világ koordináta rendszerből végrehajt egy leképezést a képernyőnkre. Mivel az ablakunk mérete módosítható átméretezéssel, ezért valóban szükség van egy ilyenre. A B-spline eljárásra megoldás található a bspline1.jav és bspline2.jav (Java 1.1 kompatíbilis böngészők számára, offscreen módszert használva, nem villog.) fájlokban.

Remélem sikerült nagyjából elmagyarázni mindent, ha valahol valamit elszúrtam azért elnézést kérek. Mára ennyit gondoltam, legközelebb már kilépünk a térbe görbéinkkel együtt.

A cikkhez kapcsolódó forráskódok letölthetők innen.

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
Programozzunk Delphi 5 rendszerben!, 2002
Füzi János: Interaktív grafika, 1997