[24 Jan 2013]

# Usage and visualization of Bezier curves and splines

Bezier curve consists of control points. The curve passes only through first and last control points. Calculation of intermediate points is performed with help of parametric value t[0,1], with 0 representing first point of the curve, and 1 - last point on the curve. Formula for point calculation:
where:

n - number of control points per curve minus 1

t - parametric value for required position

Pi - i-th curve control point

R - calculated point that corresponds to t value

(n,i) - binomial coefficient

It's required to take into account each control point of the curve with its influence on searched point R. Binomial coefficient is calculated as (n,i) = n!/(i!(n-i)!) and can be precomputed and saved to two dimensional array. To work with curve that has three control points its required to calculate binomial coefficients for n=0,1,2, for curve which has 4 points - n=0,1,2,3, and so on. For example, curve with three points: // n = numControlPointsInCurve-1 = 3-1 = 2
// binoms[n][i] = (n,i) = n!/(i!(n-i)!)
binoms[2][0] = 1;   // 2!/(0!(2-0)!)
binoms[2][1] = 2;   // 2!/(1!(2-1)!)
binoms[2][2] = 1;   // 2!/(2!(2-2)!)
Calculate binomial coefficients for all levels of curves (simple line, quadratic, cubic, etc), which you want to use. For example n=1 - curve (straight line) with two points, n=2 - quadratic Bezier curve with 3 points, n=3 - cubic Bezier curve with 4 points.
Function that computes arbitrary point on Bezier curve: vec2 bezierPos(QVector<vec2> controlPoints,int numPointsPerCurve,float t)
{
float ti=1.0-t;
vec3 res=vec2(0);
for(int i=0; i<numPointsPerCurve; i++)
{
float binom = binoms[numPointsPerCurve][i];
float level = pow(t,i) * pow(ti,numPointsPerCurve-1-i);
res+=controlPoints[i+partOffset] * binom * level;
}
return res;
}
And actual calculation of point at t=0.15: numPointsPerCurve = 3; // points per curve
controlPoints = { vec2(0,0), vec2(1,1), vec2(2,0) }; // array of points
t = 0.15; // any value in [0,1]

vec2 P = bezierPos(controlPoints,numPointsPerCurve,t);
Function requires some changes to be used with Bezier splines. Bezier spline consists of connected Bezier curves. An end of one Bezier curve is a beginning of another bezier curve. In place where two bezier curves are connected, derivatives (tangents) of that curves must be equal. Namely control point at connection and two adjacent control points should lie on straight line:
For example, spline contains numCurves Bezier curves. Then value of t=[0...1*numCurves] is used to calculate arbitrary position. Integer part of t represents index of curve in spline, and floating point part represents position([0,1] range) on that curve. Control points of two splines (and more) can be arranged in one array. For example, spline that contains two quadratic bezier curves has 5 control points: numPointsPerCurve = 3;
controlPoints = {vec2(0,0),vec2(1,1),vec2(2,0),vec2(3,-1),vec2(4,0)};
t = 1.15; // any value in [0,2], calculate position on 2nd curve at t=0.15
where point vec2(2,0) is shared by both curves, and forms straight line with adjacent control points.
Also to calculate arbitrary point on the spline you have to find first vertex of the bezier curve on which the point lies (partOffset), and parametric t value in [0,1] range that defines position on bezier curve.
Code to calculate arbitrary point on Bezier spline: vec3 bezierPos(QVector<vec3>controlPoints,int numPointsPerCurve,float t)
{
int partOffset= int(t) * (numPointsPerCurve-1);
t = t - int(t);
float ti=1.0-t;
vec3 res=vec3(0,0,0);
for(int i=0; i<numPointsPerCurve; i++){
float binom = binoms[numPointsPerCurve][i];
float level = pow(t,i) * pow(ti,numPointsPerCurve-1-i);
res+=controlPoints[i+partOffset] * binom * level;
}
return res;
}
You have to tesselate bezier curve in order to visualize it. For example, spline is transformed to 10 line segments: float step = 1.0/10;
for(short i=0;i<9;i++)
{
float t1 = step*(i);
float t2 = step*(i+1);
vec2 A = bezierPos(controlPoints,numPointsPerCurve,t1);
vec2 B = bezierPos(controlPoints,numPointsPerCurve,t2);
drawLine(A,B);
}

You can also tesselate bezier spline with more complex tesselation algorithm, for example, taking into account angle epsilon (angle between tangents of adjacent points) and distance epsilon (distance between adjacent points).

Sun and Black Cat- Igor Dykhta () © 2007-2014