Bézierove krivky (BK)

Majme riadiaci polygón s vrcholmi V0, V1, .. , Vn ; Vi je (xi,yi) pre rovinu al. (xi,yi,zi) pre priestor a t : ∈ < 0,1 >.

Bézierova krivka n-tého stupňa je daná n+1 riadiacimi bodmi polygónu a rovnicou
, t ∈ < 0,1 >.
je Bernsteinov polynóm :
, t  ∈ < 0,1 > a i=0,1, ... n.

, kde n! je faktoriál čísla n, napr. 5!=5*4*3*2=120.
 
 

Výpočet BK pomocou Bersteinovho polynómu

Časť zdrojového kódu súboru  zobraz3d.java

// pomocné funkcie

 public double fact(int i4) // slúži na výpočet faktoriálu čísla na vstupe
  {
    x2=1;
    if (i4!=0) for (int i3=1;i3<i4+1;i3++){x2=x2*i3;};
    return x2;
  }

 public double fx(double x1,int i4) // slúži na výpočet čísla x1 na i4
  {
    x2=1; 
    if (x1>=0.001) {for (int i3=1;i3<i4+1;i3++){x2=x2*x1;};}
    return x2;
  }

 public double berst(int i4,int i5,double x1)  // 1.parameter = n; 2.par. 0 až n; 3.parameter t z intervalu (0,1)
  {
    po1=fact(i4);po2=fact(i5);
    po1=po1/po2;po2=fact(i4-i5);
    po1=po1/po2;po2=fx(1-x1,i4-i5);
    po1=po1*po2;po2=fx(x1,i5);
    po1=po1*po2;
    x2=po1;
    return x2;
  }

//// Samotný algoritmus BK, na vstupe riadiace vrcholy bod[i][0],bod[i][0],bod[i][0] - tj. x,y,z súradnice vrchola

    double p1,p2,p3,p4,p5;
    int pr1=0,pr2=0;
    for (int i=1;i<101;i++) //  počet krokov algoritmu = 100
     {
       t=i;t=t/101; // parameter t = <0,1>

       p2=0;p3=0;p5=0;

       for (int i1=0;i1<(st+1);i1++) //  sumujeme (vid. hore vzorec) čiastočné hodnoty - 0,..,n
        { p1=berst(st,i1,t); // výpočet Bersteinovho polynómu 

         p4=bod[i1][0];p2=p2+(p4*p1); // násobenie Berst. polyn * riadiaci vrchol pre x,y a z hodnotu riadiaceho vrchola
         p4=bod[i1][1];p3=p3+(p4*p1);
         p4=bod[i1][2];p5=p5+(p4*p1);
        }

// prevod vypočítaného bodu na obrazovku

       pix[0]=p2;pix[1]=p3;pix[2]=p5;
       osp = new objekt3d(pix,typpre); 
       i1=osp.x()+stredx;
       i2=stredy-osp.y();
       if (i==1){pr1=i1;pr2=i2;} // pretože získané vrcholy spájame úsečkou treba na začiatku prvý vrchol 2 krát
       g.drawLine(i1,i2,pr1,pr2); // spojenie nového a starého bodu
       pr1=i1;pr2=i2; // nový bod sa stane starý
   }
$$$APPLET

Bézierova krivka 3-stupňa

$$$APPLET

Applet Bezier curve . Set a news points with mouse button. Author: Galcik Peter

Applet for handling with Bezier Curves has simple layout and user interface. We can add, move points on canvas by mouse. No action on canvas can be made by keyboard. After every action the curve is redrawn and user can see immediately generated curve. Moreover if we want draw points precisely, we can activate coordinates of intermediate points. Interpolated lines in any point of bezier curve can be showed by moving "Position" slider. And last thing, we can activate animation of curve and set animation speed.

Specification

Applet of Bezier Curve is well designed. Consist of three well structured java files.

  • BezierCurveApplet.java - implements swing layout and event from applet ( + animation Thread).
  • BezierCurveAlgorithm.java - static class implementing DeCasteljau Algorithm.
  • BezierCurve.java - class,that hold all data of bezier curve and implements drawing of curve.

Universal architecture of java files support further development or implementing new features.

 

(c) Galcik Peter 2007

Casteljauov algoritmus (CA) pre BK 


Dané : riadiaci polygón s vrcholmi V0, V1, .. , Vn; Vi je (xi,yi) pre rovinu al. (xi,yi,zi) pre priestor a t : ∈ < 0,1 >.
           - V0, V1, .. , Vn je lomená čiara 

Algoritmus. : 

  1. V0,i (t) = Vi 
  2. Vr,i (t) = (1 - t). Vr-1,i(t) + t.V r-1,i+1 (t) , pre t : Î < 0,1 >.
  3. Bn  = Bn (t) = { Bn(t) = Vn,0 (t), t : Î < 0,1 >}, kde r = 1,...,n a i = 0,..., n-r.
Popis : 

V prvom kroku dosadíme za Vo,i = Vi, tj. vrcholy riadiaceho polygónu krivky. 
V druhom kroku rekurzívne počítame vrchol Vr,i (t)
V poslednom kroku je bod Vn,n (t) bodom Bézierovej krivky.

Vlastnosti Bersteinových polynómov

je Bernsteinov polynóm :

  1. B0,0 (t) = 1
  2. B i,n (t) = (1-t) B i,n-1 (t) + t B i-1,n-1 (t)
  3. Suma(i=0,...,n) B i,n (t) = 1
  4. B i,n (t) >=0 pre t : ∈ < 0,1 >.
Léma : Vr,i (t) = Suma(j=0,...,r) V j+i * B r,j (t), pre r = 1,...,n a i = 0,...,n-r
Dôkaz : z Casteljauovho algoritmu

Vlastnosti Bézierových kriviek

  1. Afinná invariantnosť

    2. Nech j : E -> E (afinné zobrazenie) a Bn(t) = Bn [V0, V1, ..., Vn,t]. Potom j [Bn[V0, V1, ...,Vn,t]] = Bn j(V0), j(V1), ..., j(Vn),t].
    Význam tejto vlastnosti je napríklad pri premietaní. Ako si môžete pozrieť na hore uvedenom algoritme na výpočet BK pomocou Bersteinových polynómov, kde najprv vypočítame BK a potom celú krivku niektorým afinným zobrazením zobrazujeme na obrazovku.
     
  2. Invariantnosť vzhľadom na afinnú transformáciu parametra

    3. t.j. ak prejdeme z parametra t na u [u = a + t (b-a)]tak sa nám krivka nezmení.
     
  3. Vlastnosť konvexného obalu : BK leží v konvexnom obale svojích riadiacich vrcholov. Toto vyplýva aj napr. z

    4. Casteljauovho algoritmu BK, kde interpolujeme riadiace body.
     
  4. Interpolácia koncových bodov. BK začína v bode V0 a končí v bode Vn. Toto vyplýva tiež z CA pre BK.

    5.  
  5. Symetria. BK = Suma (i=0,...,n) Vn-i * B n,i (1-t), tj. riadiaci polygón V0, V1, ..., Vn určuje tú istú krivku ako Vn, Vn-1, ..., V0.

    6.  

$$$APPLET

Bézierova krivka konštruovaná Castejauovým algoritmom
a ukážka postupnej konštrukcie jedného jej bodu.


$$$APPLET

Bézierova krivka stupňa 3 v 3D, interakcia umožnuje
zmeniť z-tové hodnoty bodov riadiaceho polygónu