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:

\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é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:

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

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

\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ézierjevi zlepki, ki jih sestavljajo kvadratne Bézierjeve krivulje.

[uredi] Kubične Bézierjeve krivulje

Bézierjeva krivulja stopnje 3:

Slika:bezier.png

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

\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é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:

\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}.

[uredi] Glej tudi

  • de Casteljaujev algoritem
  • zlepek
  • Bézierjev zlepek
  • Bézierjeva površina
  • Bézierjev trikotnik
  • NURBS

[uredi] Viri

[uredi] Zunanje povezave