Bezierova krivulja

Iz Wikipedije, proste enciklopedije

Kubična Bezierova krivulja
Kubična Bezierova krivulja

Bezierova 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 Bezierovih krivulj je de Castaljaujev algoritem.

Posplošitve Bezierovih krivulj na višje razsežnosti se imenujejo Bezierove površine. Tu je Bezierov trikotnik poseben primer.

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

Vsebina

[uredi] Zgodovina

Bezierove 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 Bezierova 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 Bezierove krivulje. S povezavo Bezierovih točk in premice se lahko določi mnogokotnik z začetkom v P0 in koncem v Pn. Ta mnogokotnik se imenuje Bezierov mnogokotnik.

[uredi] Opombe

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

[uredi] Zgledi

[uredi] Linearne Bezierove krivulje

Animacija linearne Bezierove krivulje, t v [0,1]
Animacija linearne Bezierove krivulje, t v [0,1]

Bezierova »krivulja« stopnje 1:

Če sta dani dve nadzorni točki P0 in P1, je linearna Bezierova 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 Bezierove krivulje

Bezierova krivulja stopnje 2:

Kvadratno Bezierovo 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 Bezierovi zlepki, ki jih sestavljajo kvadratne Bezierove krivulje.

Konstrukcija kvadratne Bezierove krivulje Animacija kvadratne Bezierove krivulje, t v [0,1]
Konstrukcija kvadratne Bezierove krivulje Animacija kvadratne Bezierove krivulje, t v [0,1]

[uredi] Kubične Bezierove krivulje

Štiri točke A, B, C in D v ravnini ali v trirazsežnem prostoru določajo kubično Bezierovo 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 Bezierove zlepke, ki jih sestavljajo kubične Bezierove krivulje.

Konstrukcija kubične Bezierove krivulje Animacija kubične Bezierove krivulje, t v [0,1]
Konstrukcija kubične Bezierove krivulje Animacija kubične Bezierove krivulje, t v [0,1]

[uredi] Bezierove krivulje višjih stopenj

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

Konstrukcija Bezierove krivulje četrte stopnje Animacija Bezierove krivulje četrte stopnje, t v [0,1]
Konstrukcija Bezierove krivulje četrte stopnje Animacija Bezierove krivulje četrte stopnje, t v [0,1]

[uredi] Uporaba v računalniški grafiki

Bezierove 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 Bezierove 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 Bezierove krivulje nižjih stopenj, ki morajo zadovoljiti nekaterim pogojem gladkosti, v obliki Bezierovih zlepkov.

[uredi] Zgled računalniškega programa

Naslednji kod je preprost praktični primer, ki kaže kako preporsto praktično izrisati kubično Bezierovo 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 koda 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 Bezierove 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 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 Bezierove krivulje

Nekatere krivulje, ki se zdijo preproste, kot je krožnica, ne moremo opisati z Bezierovo krivuljo ali z delom Bezierove krivulje. V praksi je razlika sicer majhna in jo lahko dopuščamo. Za opis takšnih drugačnih krivulj potrebujemo dodatne prostostne stopnje.

Racionalna Bezierova krivulja doda uteži, ki jih lahko prilagajamo. Števec je utežena Bernsteinova oblika Bezierove krivulje, imenovalec pa je utežena vsota Bernesteinovih polinomov.

Če imamo n+1 nadzornih točk Pi, lahko racionalno Bezierovo 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
  • Bezierov zlepek
  • Bezierova površina
  • Bezierov trikotnik
  • NURBS

[uredi] Viri

[uredi] Zunanje povezave