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.

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.

Če je danih n+1 točk P_i v R³ je Bézierova krivulja stopnje n parametrična krivulja:

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

sestavljena iz Bernsteinovih baznih polinomov stopnje n:

${\displaystyle \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:

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

P_i 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 P₀ in koncem v P_n. Ta mnogokotnik se imenuje Bézierov mnogokotnik.

• Začetna točka krivulje je P₀, končna točka pa P_n
• 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.

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

Bézierova »krivulja« stopnje 1:

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

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

Bézierova krivulja stopnje 2:

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

${\displaystyle \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]

Š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:

${\displaystyle \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]

Za Bézierove krivulje četrte stopnje je moč skonstruirati vmesne točke Q₀, Q₁, Q₂ in Q₃, ki opišejo linearne Bézierove krivulje, točke R₀, R₁ in R₂, ki opišejo kvadratne Bézierove krivulje, in točke S₀ & S₁ kubičnih Bézierovih krivulj:

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

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.

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 );
  }

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 P_i, lahko racionalno Bézierovo krivuljo opišemo z:

${\displaystyle \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:

${\displaystyle \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}}}.}$

• de Casteljaujev algoritem
• zlepek
• Bézierov zlepek
• Bézierova površina
• Bézierov trikotnik
• NURBS

• Paul Bourke: Bézierove krivulje (Bézier curves), http://astronomy.swin.edu.au/pbourke/curves/Bézier/
• Donald Knuth: Metafont: the Program, Addison-Wesley 1986, pp. 123-131. Odlična razprava o podrobnostih uporabe; na voljo kot del distribucije TeX.
• Dr. Thomas Sederberg, BYU Bézierove krivulje (Bézier curves), http://www.tsplines.com/resources/class_notes/Bézier_curves.pdf^{[mrtva povezava]}

• Living Math Bézier applet^{[mrtva povezava]}
• 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ézierovo krivuljo; s pomočjo kubičnih zlepkov za interpolacijo slike in razlaga matematičnega ozadja teh krivulj.