Comp.Graphics.Algorithms
Frequently Asked Questions

Section 4. Curve Computations

Subject 4.01: How do I generate a bezier curve that is parallel to another bezier?

You can't. The only case where this is possible is when the bezier can be represented by a straight line. And then the parallel 'bezier' can also be represented by a straight line.

Subject 4.02: How do I split a bezier at a specific value for t?

A Bezier curve is a parametric polynomial function from the interval [0..1] to a space, usually 2-D or 3-D. Common Bezier curves use cubic polynomials, so have the form

f(t) = a3 t^3 + a2 t^2 + a1 t + a0,

where the coefficients are points in 3-D. Blossoming converts this polynomial to a more helpful form. Let s = 1-t, and think of tri-linear interpolation:

F([s0,t0],[s1,t1],[s2,t2]) =
       s0(s1(s2 c30 + t2 c21) + t1(s2 c21 + t2 c12)) +
       t0(s1(s2 c21 + t2 c12) + t1(s2 c12 + t2 c03))
       =
       c30(s0 s1 s2) +
       c21(s0 s1 t2 + s0 t1 s2 + t0 s1 s2) +
       c12(s0 t1 t2 + t0 s1 t2 + t0 t1 s2) +
       c03(t0 t1 t2).

The data points c30, c21, c12, and c03 have been used in such a way as to make the resulting function give the same value if any two arguments, say [s0,t0] and [s2,t2], are swapped. When [1-t,t] is used for all three arguments, the result is the cubic Bezier curve with those data points controlling it:

f(t) = F([1-t,t],[1-t,t],[1-t,t])
     = (1-t)^3 c30 +
       3(1-t)^2 t c21 +
       3(1-t) t^2 c12 +
       t^3 c03.

Notice that

F([1,0],[1,0],[1,0]) = c30,
F([1,0],[1,0],[0,1]) = c21,
F([1,0],[0,1],[0,1]) = c12, _
F([0,1],[0,1],[0,1]) = c03.

In other words, cij is obtained by giving F argument t's i of which are 0 and j of which are 1. Since F is a linear polynomial in each argument, we can find f(t) using a series of simple steps. Begin with

f000 = c30, f001 = c21, f011 = c12, f111 = c03.

Then compute in succession:

f00t = s f000 + t f001, f01t = s f001 + t f011,
f11t = s f011 + t f111,
f0tt = s f00t + t f01t, f1tt = s f01t + t f11t,
fttt = s f0tt + t f1tt.

This is the de Casteljau algorithm for computing f(t) = fttt.

It also has split the curve for the intervals [0..t] and [t..1]. The control points for the first interval are f000, f00t, f0tt, fttt, while those for the second interval are fttt, f1tt, f11t, f111.

If you evaluate 3 F([1-t,t],[1-t,t],[-1,1]) you will get the derivate of f at t. Similarly, 2*3 F([1-t,t],[-1,1],[-1,1]) gives the second derivative of f at t, and finally using 1*2*3 F([-1,1],[-1,1],[-1,1]) gives the third derivative. This procedure is easily generalized to different degrees, triangular patches, and B-spline curves.

Subject 4.03: How do I find a t value at a specific point on a bezier?

In general, you'll need to find t closest to your search point. There are a number of ways you can do this. Look at [Gems I, 607], there's a chapter on finding the nearest point on the bezier curve. In my experience, digitizing the bezier curve is an acceptable method. You can also try recursively subdividing the curve, see if you point is in the convex hull of the control points, and checking is the control points are close enough to a linear line segment and find the nearest point on the line segment, using linear interpolation and keeping track of the subdivision level, you'll be able to find t.

Subject 4.04: How do I fit a bezier curve to a circle?

Interestingly enough, bezier curves can approximate a circle but not perfectly fit a circle.

Michael Goldapp, "Approximation of circular arcs by cubic polynomials" Computer Aided Geometric Design (#8 1991 pp.227-238)

Tor Dokken and Morten Daehlen, "Good Approximations of circles by curvature-continuous Bezier curves" Computer Aided Geometric Design (#7 1990 pp. 33-41).