Bézierjeva krivulja
Iz Wikipedije, proste enciklopedije
Bézierjeva krivulja je v matematičnem področju numerične analize parametrična krivulja pomembna v računalniški grafiki. Numerično stabilna metoda za izračunavanje Bézierjevih krivulj je de Castaljaujev algoritem.
Posplošitve Bézierjevih krivulj na višje razsežnosti se imenujejo Bézierjeve površine. Tu je Bézierjev trikotnik poseben primer.
Bézierjeve krivulje lahko nastanejo tudi pri različnih splošnih oblikah strunske umetnosti, kjer se strune zavijejo okoli okvirja z žeblji.
Vsebina |
[uredi] Zgodovina
Bézierjeve krivulje je leta 1962 razširil francoski inženir Pierre Etienne Bézier, ki jih je uporabil pri oblikovanju avtomobilskih teles. Krivulje je leta 1959 uvedel Paul de Casteljau s pomočjo de Casteljaujevega algoritma.
[uredi] Definicija
Če je danih n+1 točk Pi v R3 je Bézierjeva krivulja stopnje n parametrična krivulja:
sestavljena iz Bernsteinovih baznih polinomov stopnje n:
kjer so Bernsteinovih bazni polinomi določeni kot:
Pi se imenuje nadzorna točka Bézierjeve krivulje. S povezavo Bézierjevih točk in premice se lahko določi mnogokotnik z začetkom v P0 in koncem v Pn. Ta mnogokotnik se imenuje Bézierjev mnogokotnik.
[uredi] Opombe
- Začetna točka krivulje je P0, končna točka pa Pn
- Bézierjevo krivuljo v celoti vsebuje konveksna lupina nadzornih točk.
- Če in samo če vse nadzorne točke ležijo na krivulji, je krivulja premica.
- Začetek (konec) krivulje je tangenta prvemu (zadnjemu) preseku Bézierjevega mnogokotnika.
- Krivuljo lahko v vsaki točki razdelimo na dve podkrivulji, oziroma na poljubno mnogo podkrivulj, od katerih je vsaka spet Bézierjeva krivulja.
- Krožnice natančno ne moremo tvoriti z Bézierjevo krivuljo. Ne moremo tvoriti niti krožnega loka. (Velikokrat pa je Bézierjeva krivulja ustrezna aproksimacija dovolj majhnega krožnega loka).
- Krivulje na dani razdalji od Bézierjeve krivulje (»vzporedne« tej krivulji, kakor je stalna razdalja med tračnicami pri železniški progi) ne moremo natančno tvoriti z Bézierjevo krivuljo (razen v nekaterih enoličnih primerih). Obstajajo pa hevristične metode, ki po navadi dajo ustrezno aproksimacijo za praktične namene.
[uredi] Primeri
[uredi] Linearne Bézierjeve krivulje
Bézierjeva »krivulja« stopnje 1:
Če sta dani dve nadzorni točki P0 in P1, je linearna Bézierjeva krivulja kar premica med točkama. Krivulja je dana z:
[uredi] Kvadratne Bézierjeve krivulje
Bézierjeva krivulja stopnje 2:
Kvadratno Bézierjevo krivuljo opiše funkcija B(t). Za točke A, B in C je dana z:
V črkah iz nabora TrueType se uporabljajo Bézierjevi zlepki, ki jih sestavljajo kvadratne Bézierjeve krivulje.
[uredi] Kubične Bézierjeve krivulje
Bézierjeva krivulja stopnje 3:
Štiri točke A, B, C in D v ravnini ali v trirazsežnem prostoru določajo kubično Bézierjevo krivuljo. Krivulja se začne v A, poteka proti B in dospe v D iz smeri od C. V splošnem ne bo potekala skozi B ali C; ti točki sta le za določitev smeri. Razdalja med A in B določa »kako dolgo« poteka krivulja proti B preden ne zavije proti D.
Parametrična oblika krivulje je:
Sodobni grafični programi kot so PostScript, Metafont in GIMP za risanje ukrivljenih oblik uporabljajo Bézierjeve zlepke, ki jih sestavljajo kubične Bézierjeve krivulje.
[uredi] Uporaba v računalniški grafiki
Bézierjeve krivulje se na široko uporabljajo v računalniški grafiki za modeliranje gladkih krivulj. Ker krivuljo v celoti vsebuje konveksna lupina njenih nadzornih točk, se lahko točke grafično prikažejo in uporabijo za intuitivno urejanje krivulje. Pri krivulji se lahko uporabijo afine transformacije kot so vzporedni premik, skaliranje in vrtenje in to kar s transformacijami nadzornih točk krivulje.
Najpomembnejše Bézierjeve krivulje so kvadratne in kubne. Krivulje višjih stopenj so računsko potratnejše in tudi ni analitičnih enačb za izračun ničel polinomov stopnje 5 ali več. Če so potrebne še zahtevnejše oblike, se skupaj zgladijo Bézierjeve krivulje nižjih stopenj, ki morajo zadovoljiti nekaterim pogojem gladkosti, v obliki Bézierjevih zlepkov.
Naslednji kod je preprost praktični primer, ki kaže kako izrisati Bézierjevo krivuljo v C. Program preprosto izračunava koeficiente polinoma in spreminja vrednosti t od 0 do -1, kar je tudi v praksi tako, čeprav se pogosto omenjajo boljši algoritmi kot je npr. de Casteljaujev. To je zaradi tega, ker je v praksi linearni algoritem kot je ta, hitrejši in manj potraten kot rekurzivni, kakor je de Casteljaujev. Program je razčlenjen, da je razvidnejši. V praksi bi se ga optimiralo tako, da bi izračunal koeficiente enkrat in bi jih ponovno uporabil v zanki, ki izračunava nadzorne točke. Tukaj se izračunavajo vsakokrat, kar je manj učinkovito, vendar pomaga pri boljšemu razumevanju koda.
Dobljena krivulja se lahko izriše z risanjem premic med zaporednimi točkami krivulje. Več točk se nariše, bolj gladka je krivulja.
/****************************************************** Program za tvorjenje kubične Bezierjeve krivulje Opozorilo - nepreskušen kod *******************************************************/ typedef struct { float x; float y; } Point2D; /****************************************************** cp je polje s štirimi elementi, kjer so: cp[0] začetna točka, oziroma A v zgornji risbi cp[1] prva nadzorna točka, oziroma B cp[2] druga nadzorna točka, oziroma C cp[3] končna točka, oziroma D t je vrednost parametra, 0 <= t <= 1 *******************************************************/ Point2D PointOnCubicBezier( Point2D* cp, float t ) { float ax, bx, cx; float ay, by, cy; float tSquared, tCubed; Point2D result; /* izračun koeficientov polinoma */ cx = 3.0 * (cp[1].x - cp[0].x); bx = 3.0 * (cp[2].x - cp[1].x) - cx; ax = cp[3].x - cp[0].x - cx - bx; cy = 3.0 * (cp[1].y - cp[0].y); by = 3.0 * (cp[2].y - cp[1].y) - cy; ay = cp[3].y - cp[0].y - cy - by; /* izračun točke krivulje pri vrednosti parametra t */ tSquared = t * t; tCubed = tSquared * t; result.x = (ax * tCubed) + (bx * tSquared) + (cx * t) + cp[0].x; result.y = (ay * tCubed) + (by * tSquared) + (cy * t) + cp[0].y; return result; } /***************************************************************************** ComputeBezier napolne polje strukture Point2D s točkami krivulje, ki se izračunajo iz nadzorne točke cp. Za rezultat se mora dodeliti dovolj pomnilnika - <sizeof(Point2D) * numberOfPoints> ******************************************************************************/ void ComputeBezier( Point2D* cp, int numberOfPoints, Point2D* curve ) { float t, dt; int i; dt = 1.0 / ( numberOfPoints - 1 ); for( i = 0, t = 0; i < numberOfPoints; i++, t += dt) curve[i] = PointOnCubicBezier( cp, t ); }
[uredi] Racionalne Bézierjeve krivulje
Nekatere krivulje, ki se zdijo preproste, kot je krožnica, ne moremo opisati z Bézierjevo krivuljo ali z delom Bézierrjeve krivulje. V praksi je razlika sicer majhna in jo lahko dopuščamo. Za opis takšnih drugačnih krivulj potrebujemo dodatne prostostne stopnje.
Racionalna Bézierjeva krivulja doda uteži, ki jih lahko prilagajamo. Števec je utežena Bernsteinova oblika Bézierjeve krivulje, imenovalec pa je utežena vsota Bernesteinovih polinomov.
Če imamo n+1 nadzornih točk Pi, lahko racionalno Bézierjevo krivuljo opišemo z:
oziroma preprosto:
[uredi] Glej tudi
- de Casteljaujev algoritem
- zlepek
- Bézierjev zlepek
- Bézierjeva površina
- Bézierjev trikotnik
- NURBS
[uredi] Viri
- Paul Bourke: Bézierjeve krivulje (Bézier curves), http://astronomy.swin.edu.au/pbourke/curves/bezier/
- Donald Knuth: Metafont: the Program, Addison-Wesley 1986, pp. 123-131. Odlična razprava o podrobnostih uporabe; na voljo kot del distribucije TeX-a.
- Dr. Thomas Sederberg, BYU Bézierjeve krivulje (Bézier curves), http://www.tsplines.com/resources/class_notes/Bezier_curves.pdf
[uredi] Zunanje povezave
- Living Math Bézier applet
- Living Math Bézier applets of different spline types, JAVA programming of splines in An Interactive Introduction to Splines
- Don Lancaster's Cubic Spline Library opisuje kako aproksimirati krožnico (ali krožni lok, oziroma hiperbolo) z Bézierjevo krivuljo; s pomočjo kubičnih zlepkov za interpolacijo slike in razlaga matematičnega ozadja teh krivulj.