Bézierova krivulja

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Kubična Bézierova krivulja

Bézierova krivulja [bezjêjeva krivúlja] 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ézierovih krivulj je de Castaljaujev algoritem.

Posplošitve Bézierovih krivulj na višje razsežnosti se imenujejo Bézierove površine. Tu je Bézierov trikotnik poseben primer.

Bézierove krivulje lahko nastanejo tudi pri različnih splošnih oblikah strunske umetnosti, kjer se strune zavijejo okoli okvirja z žeblji.

Zgodovina[uredi | uredi kodo]

Bézierove 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.

Definicija[uredi | uredi kodo]

Če je danih n+1 točk Pi v R3 je Bézierova krivulja stopnje n parametrična krivulja:

\mathbf{B}:[0,1] \to \mathbb{R}^3 \; ,

sestavljena iz Bernsteinovih baznih polinomov stopnje n:

\mathbf{B}(t)= \sum_{i=0}^n \mathbf{P}_{i} b_{i,n}(t) \mbox{ , } t \in [0,1] \; ,

kjer so Bernsteinovih bazni polinomi določeni kot:

b_{i,n}(t):= {n \choose i} t^i (1-t)^{n-i} \qquad \mbox{ , } i=0,\ldots n.

Pi se imenuje nadzorna točka Bézierove krivulje. S povezavo Bézierovih točk in premice se lahko določi mnogokotnik z začetkom v P0 in koncem v Pn. Ta mnogokotnik se imenuje Bézierov mnogokotnik.

Opombe[uredi | uredi kodo]

  • Začetna točka krivulje je P0, končna točka pa Pn
  • Bézierovo krivuljo v celoti vsebuje konveksna ogrinjača 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ézierovega mnogokotnika.
  • Krivuljo lahko v vsaki točki razdelimo na dve podkrivulji, oziroma na poljubno mnogo podkrivulj, od katerih je vsaka spet Bézierova krivulja.
  • Krožnice natančno ne moremo tvoriti z Bézierovo krivuljo. Ne moremo tvoriti niti krožnega loka. (Velikokrat pa je Bézierova krivulja ustrezna aproksimacija dovolj majhnega krožnega loka).
  • Krivulje na dani razdalji od Bézierove krivulje (»vzporedne« tej krivulji, kakor je stalna razdalja med tračnicami pri železniški progi) ne moremo natančno tvoriti z Bézierovo krivuljo (razen v nekaterih enoličnih primerih). Obstajajo pa hevristične metode, ki po navadi dajo ustrezno aproksimacijo za praktične namene.

Zgledi[uredi | uredi kodo]

Linearne Bézierove krivulje[uredi | uredi kodo]

Animacija linearne Bézierove krivulje, t v [0,1]
Animacija linearne Bézierove krivulje, t v [0,1]

Bézierova »krivulja« stopnje 1:

Če sta dani dve nadzorni točki P0 in P1, je linearna Bézierova krivulja kar premica med točkama. Krivulja je dana z:

\mathbf{B}(t)=(1-t)\mathbf{P}_0 + t\mathbf{P}_1 \mbox{ , } t \in [0,1].

Kvadratne Bézierove krivulje[uredi | uredi kodo]

Bézierova krivulja stopnje 2:

Kvadratno Bézierovo krivuljo opiše funkcija B(t). Za točke A, B in C je dana z:

\mathbf{B}(t) = (1 - t)^{2}\mathbf{A} + 2t(1 - t)\mathbf{B} + t^{2}\mathbf{C} \mbox{ , } t \in [0,1].

V črkah iz nabora TrueType se uporabljajo Bézierovi zlepki, ki jih sestavljajo kvadratne Bézierove krivulje.

Konstrukcija kvadratne Bézierove krivulje Animacija kvadratne Bézierove krivulje, t v [0,1]
Konstrukcija kvadratne Bézierove krivulje Animacija kvadratne Bézierove krivulje, t v [0,1]

Kubične Bézierove krivulje[uredi | uredi kodo]

Štiri točke A, B, C in D v ravnini ali v trirazsežnem prostoru določajo kubično Bézierovo 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:

\mathbf{B}(t)=\mathbf{A}(1-t)^3+3\mathbf{B}t(1-t)^2+3\mathbf{C}t^2(1-t)+\mathbf{D}t^3 \mbox{ , } t \in [0,1].

Sodobni grafični programi kot so PostScript, Metafont in GIMP za risanje ukrivljenih oblik uporabljajo Bézierove zlepke, ki jih sestavljajo kubične Bézierove krivulje.

Konstrukcija kubične Bézierove krivulje Animacija kubične Bézierove krivulje, t v [0,1]
Konstrukcija kubične Bézierove krivulje Animacija kubične Bézierove krivulje, t v [0,1]

Bézierove krivulje višjih stopenj[uredi | uredi kodo]

Za Bézierove krivulje četrte stopnje je moč skonstruirati vmesne točke Q0, Q1, Q2 in Q3, ki opišejo linearne Bézierove krivulje, točke R0, R1 in R2, ki opišejo kvadratne Bézierove krivulje, in točke S0 & S1 kubičnih Bézierovih krivulj:

Konstrukcija Bézierove krivulje četrte stopnje Animacija Bézierove krivulje četrte stopnje, t v [0,1]
Konstrukcija Bézierove krivulje četrte stopnje Animacija Bézierove krivulje četrte stopnje, t v [0,1]

Uporaba v računalniški grafiki[uredi | uredi kodo]

Bézierove krivulje se na široko uporabljajo v računalniški grafiki za modeliranje gladkih krivulj. Ker krivuljo v celoti vsebuje konveksna ogrinjača 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ézierove 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ézierove krivulje nižjih stopenj, ki morajo zadovoljiti nekaterim pogojem gladkosti, v obliki Bézierovih zlepkov.

Zgled računalniškega programa[uredi | uredi kodo]

Naslednja koda je preprost praktični primer, ki kaže kako preprosto praktično izrisati kubično Bézierovo 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 procesorsko 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 kode in daje enak rezultat.

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 Bézierove krivulje
  *   
  ***/
 
  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 PointOnCubicBézier( 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;
  }
 
 /***
  * ComputeBézier 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	ComputeBézier( 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] = PointOnCubicBézier( cp, t );
  }

Racionalne Bézierove krivulje[uredi | uredi kodo]

Nekatere krivulje, ki se zdijo preproste, kot je krožnica, ne moremo opisati z Bézierovo krivuljo ali z delom Bézierove 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ézierova krivulja doda uteži, ki jih lahko prilagajamo. Števec je utežena Bernsteinova oblika Bézierove krivulje, imenovalec pa je utežena vsota Bernesteinovih polinomov.

Če imamo n+1 nadzornih točk Pi, lahko racionalno Bézierovo krivuljo opišemo z:

 
\mathbf{B}(t) =
\frac{\sum_{i=0}^n b_{i,n}(t) \mathbf{P}_{i}w_i} {\sum_{i=0}^n b_{i,n}(t) w_i} \; ,

oziroma preprosto:

 
\mathbf{B}(t) =
\frac{\sum_{i=0}^n {n \choose i} t^i (1-t)^{n-i}\mathbf{P}_{i}w_i} {\sum_{i=0}^n {n \choose i} t^i (1-t)^{n-i}w_i}.

Glej tudi[uredi | uredi kodo]

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]