HTML5 Tutorial: How to draw n grade Bézier curve with Canvas API

Awesome! Now, let draw curve through 6 points. Ups, not possible.

That is the dead end I encountered while trying to draw connectors for the flowchart software I play with. They (connectors) can have more than 3 or 4 points so Quadratic and Cubic curves are out of the question.

Also you can not simply join a few Quadratic or Cubic curves to generate a higher degree curves.

Not that my solution can be applied to N grade (N number of points) but it works for Quadratic and Cubic curves too.

Each Bézier curve is actually a parametric curve, a curve that depends on a parameter t,

If you vary t in very small steps you will be able to find the proper x an y coordinates.

So for Quadratic curve you have 3 points: one start point (), one control point () and an end point ().

The equation for quadratic curve is:

So, the x and y of any point on the curve depends on t like this:

For cubic curves you have 4 points: one start point (), two control points (and ) and an end point ().

The equation for cubic curve is:

So, the x and y of any point on the curve depends on t like this:

Equation for a N grade Bézier curve is:

So the x and y for any point on the curve is:

Now, if you vary the t from 0 to 1 you will be able to actually draw the Bézier curve. Not only you can draw the Bézier curve but you can also compute it's nearness, collision or intersections.

The code to do that is pretty simple

/**Computes factorial*/
function fact(k){
    if(k==0 || k==1){
	return 1;
    }
    else{
	return k * fact(k-1);
    }
}

/**Computes Bernstain
*@param {Integer} i - the i-th index
*@param {Integer} n - the total number of points
*@param {Number} t - the value of parameter t , between 0 and 1
**/
function B(i,n,t){
    //if(n < i) throw "Wrong";
    return fact(n) / (fact(i) * fact(n-i))* Math.pow(t, i) * Math.pow(1-t, n-i);
}                            


/**Computes a point's coordinates for a value of t
*@param {Number} t - a value between o and 1
*@param {Array} points - an {Array} of [x,y] coodinates. The initial points
**/
function P(t, points){
    var r = [0,0];
    var n = points.length-1;
    for(var i=0; i <= n; i++){
	r[0] += points[i][0] * B(i, n, t);
	r[1] += points[i][1] * B(i, n, t);
    }                
    return r;
}
                    

Ok, all that you have to do is to variate t between 0 and 1.

Not so fast.

The problem is to find the proper step for this iteration. For some cases a step of 0.2 will be enough, while for other (long curves) is not.

Bellow is a Bézier of grade 5 with a step of 0.2. See the sharp/jagged curve shape.

A very rude solution is to compute the length of the polyline P0, P1, P2, ....Pn and use that length to find a proper step (Ex: 1 / length(P0P1...Pn))

The code is again pretty simple:

function distance(a, b){
        return Math.sqrt(Math.pow(a[0]-b[0], 2) + Math.pow(a[1]-b[1], 2));
}


/**Compute the incremental step*/
var tLength = 0;
for(var i=0; i< points.length-1; i++){
    tLength += distance(points[i], points[i+1]);
}
var step = 1 / tLength;

//compute the support points
var temp = [];
for(var t=0;t<=1; t=t+step){
    var p = P(t, points);
    temp.push(p);
}
return temp;
                    

Bellow see the "rude" solution in action:

Pretty good; as you can see, the curve is smooth enough. Well it should be, it was drawn using 849 intermediate points.

This solution will produce "good enough" results for rendering but if you are like me and you do not want to let chance play tricks on it there is a better solution: recursively split the Bezier curves into smaller and smaller pieces until the distance between 2 adjacent point is no greater than 1 - which means 1 pixel.

This means that the number of points will not be evenly distributed among the 0 to 1 interval.

This will be covered in a following article.

As canvas does not support this option I added a patch so you can use it to draw your curves.

You can download whole code from here