Hung Le: Bezier curve

Bézier curve is a parametric curve frequently used in computer graphics and related fields. Generalizations of Bézier curves to higher dimensions are called Bézier surfaces, of which the Bézier triangle is a special case.

In vector graphics, Bézier curves are used to model smooth curves that can be scaled indefinitely. "Paths," as they are commonly referred to in image manipulation programs, are combinations of linked Bézier curves. Paths are not bound by the limits of rasterized images and are intuitive to modify. Bézier curves are also used in animation as a tool to control motion.

In other projects, I have to work with a natural curve and the curve must pass through the given point is limited. After research on other sites, I decided to write this, I know all the other articles were given very specific examples ... but, you know, a thousand a situation, plus I want to keep my knowledge through this article.

Quadratic bezier
Let's go to Wikipedia, you see close to the top of the page that the formula for a quadratic b curve looks like this. Given points P₀ and P₁, a linear Bézier curve is simply a straight line between those two points. The curve is given by

B(t)=(1-t)²P₀+ 2(1-t)tP₁+ t²P₂, t ∈[0,1]

and is equivalent to linear interpolation.
Written in ActionScript then, we can get the x and y positions of our curve with the following couple lines:

//loop
t = 0; // t -> 1
P0 = new Point(10,  200);
P1 = new Point(150, 10);
P2 = new Point(260, 200);
//
var xp:Number = ( (1 - t) * (1 - t)) * P0.x + 2 * (1 - t) * t * P1.x + (t * t) * P2.x;
var yp:Number = ( (1 - t) * (1 - t)) * P0.y + 2 * (1 - t) * t * P1.y + (t * t) * P2.y;

Quadratic bezier - click and move red point

Cubic bezier.
With three points, we always identify a curve passing through(quadratic), how is four points the case?, we have again:

B(t) = t³(P₃+ 3(P₁- P₂) - P₀) + 3t²(P₀- 2P₁+ P₂)+ 3t(P₁- P₀₎, t ∈[0,1].

B represents the curve, Px represents one of the four points which makes the curve. P₀ and P₃ are points which we know as anchor points, where P₁ and P₂ are the control points, t is the position of the curve which we want to calculate.

A cubic Bezier curve is defined by four points. Two are endpoints. (x₀,y₀) is the origin endpoint. (x₃,y₃) is the destination endpoint. The points (x₁,y₁) and (x₂,y₂) are control points.
Two equations define the points on the curve. Both are evaluated for an arbitrary number of values of t between 0 and 1. One equation yields values for x, the other yields values for y. As increasing values for t are supplied to the equations, the point defined by x(t),y(t) moves from the origin to the destination. This is how the equations are defined in Adobe's PostScript references.

x(t) = a_xt³ + b_xt² + c_xt + x₀

x₁ = x₀ + c_x / 3
x₂ = x₁ + (c_x + b_x) / 3
x₃ = x₀ + c_x + b_x + a_x
y(t) = a_yt³ + b_yt² + c_yt + y₀

y₁ = y₀ + c_y / 3
y₂ = y₁ + (c_y + b_y) / 3
y₃ = y₀ + c_y + b_y + a_y

This method of definition can be reverse-engineered so that it'll give up the coefficient values based on the points described above:
c_x = 3 (x₁ - x₀)
b_x = 3 (x₂ - x₁) - c_x
a_x = x₃ - x₀ - c_x - b_x
c_y = 3 (y₁ - y₀)
b_y = 3 (y₂ - y₁) - c_y
a_y = y₃ - y₀ - c_y - b_y

Now, simply by knowing coordinates for any four points, you can create the equations for a simple Bézier curve:

//loop
t = 0; // t->1
P0 = new Point(10,  200);
P1 = new Point(70, 50);
P2 = new Point(200, 50);
P3 = new Point(260, 200);
//.....
var xp:Number = Math.pow(t,3)*(P3.x+3*(P1.x-P2.x)-P0.x) +3*Math.pow(t,2)*(P0.x-2*P1.x+P2.x) +3*t*(P1.x-P0.x)+P0.x;
var yp:Number = Math.pow(t,3)*(P3.y+3*(P1.y-P2.y)-P0.y) +3*Math.pow(t,2)*(P0.y-2*P1.y+P2.y) +3*t*(P1.y-P0.y)+P0.y;

Cubic bezier - click and move red point

So, back to our formulas, given 4 control points (P₀, P₁, P₂, P₃), we can derive the mathematical formula of the cubic bezier as follow:

We can use a nice optimization in term of number of operations, let the formula be:

B(t) = αt³+ βt²+ γt + P₀, t ∈[0,1].

Then the parameters can be calculated as:

B(t) = αt³+ βt²+ γt + P₀
α = P₃- P₀- γ - β
β =3(P₂- P₁) - β
γ =3(P₂- P₁)

Cubic bezier with degree n
Given n + 1 control Points P_j with j=0 to n, The bezier parametric curve is given by B(t) as follow:

Bezier curves are parametric curves, it means the formula above is applied independently to the x and y coordinate of the points for a 2D curve. The following shows a hybrid between a Math formula and a ActionScript dot syntax to make the formula easier to grab (hopefully it does):

There are a lot of very interesting property for bezier curves. Below are the fews that are relevant to us in this article:

At t=0, B(t) is P₀ and at t=1, B(t) is P_n. That means that the bezier curves begins at the first control point(j=0) and finishes at the last (j=n).
At t=0 the curve is tangent to the line (P₀, P₁) and at t=1, the curve is tangent to the line (P_n, P_n-1)
The curve is always contained within the convex shape described by the control points.
It is possible to ensure continuity of two bezier curves by making sure that the tangent to the last control point of the first curve is the same as the tangent to the first control point of the second curve. Which means that if P₁,j(j=0 to n) are the control points for the first curve and P₂,i (j=0 to m) are the control points for the second one, first order continuity of the two curves can be achieved if P₁,n is the same point as P₂,0 and if P₁,(n-1), P₁,n and P₂,1 belong to the same line.

For example, for n = 5:

//loop
t = 0;
P0 = new Point(88,  213);
P1 = new Point(10,  103);
P2 = new Point(82,  21);
P3 = new Point(178, 20);
P4 = new Point(242, 107);
P5 = new Point(174, 210);

var xp:Number = Math.pow(1 - t, 5)   * P0.x
       +5  *    t           * Math.pow(1 - t, 4) * P1.x
       +10 * Math.pow(t, 2) * Math.pow(1 - t, 3) * P2.x
       +10 * Math.pow(t, 3) * Math.pow(1 - t, 2) * P3.x
       + 5 * Math.pow(t, 4) * (1 - t) * P4.x + Math.pow(t, 5) * P5.x;
       
var yp:Number = Math.pow(1 - t, 5)   * P0.y
       +5  *    t           * Math.pow(1 - t, 4) * P1.y
       +10 * Math.pow(t, 2) * Math.pow(1 - t, 3) * P2.y
       +10 * Math.pow(t, 3) * Math.pow(1 - t, 2) * P3.y
       + 5 * Math.pow(t, 4) * (1 - t) * P4.y + Math.pow(t, 5) * P5.y;

With degree n=5 - click and move red point

Bézier curves can be defined for any degree n, you try to write a function with degree n and send to me, I'll very happy! :P

Here my processed for degree n:

//loop
t = 0;
P0 = new Point(112, 216);
P1 = new Point(216, 149);
P2 = new Point(50,  51);
P3 = new Point(140, 35);
P4 = new Point(228, 51);
P5 = new Point(57,  149);
P6 = new Point(154, 216);
Pn = ...

var ax:Array = [P0.x, P1.x, P2.x, P3.x, P4.x, P5.x, P6.x, Pn.x ...];
var ay:Array = [P0.y, P1.y, P2.y, P3.y, P4.y, P5.y, P6.y, Pn.y ...];

function bezierCurvesN(n:Number, t:Number, k:Array):Number {
    var b:Number = 0;            //binomial
    var p:Number = 0;            //position
    var e:Number = 0;            //exponent
    var f:Number = 0;              //floor
    var c:Number = 0;              //curves
    var z:Number = n - 1;          //floor 0-5 = 6
    for (var i:int = 0, j:int = 1; i <= (z - 1); i++, j++ ) { 
        //b = new Binomial().coef(z, i);        // 1 5 10 10 5 1 
        b = Pascal(z,i);                         // 1 5 10 10 5 1 
        p = k[i];            // P0 P1 P2 P3 P4
        e = z - i;            // 5 4 3 2 1
        f = b * Math.pow(t, i) * Math.pow(1 - t, e) * p;  // see wiki
        c = c + f;      
    }
    c = c + Math.pow(t, n) * k[n - 1];       // k[n =5] => k[n-1 =4] that of the end list
 
    return c;
}
public function Pascal(n:Number, r:Number):Number{ 
 if (n > 1 && r > 0 && r < n){
  return Pascal(n - 1, r - 1) + Pascal(n - 1, r)
 }
 return 1;
}

With degree n - click and move red point

Label

Bezier curve

Download class demo

Class reference

Reference

1 comments:

Post a Comment