# How do I find a Bezier curve that goes through a series of points?

When someone has the 4 control points P0, P1, P2, P3 of a 2D cubic Bézier curve, that person can calculate a series of hundreds of points along the curve that start from P0 at t=0 and end at P3 at t=1 (but, in general, those points never hit P1 or P2).

If that person gives me a series of distinct points along that curve (in order, starting with X0=P0 and ending with XN=P3), how do I recover the original 4 control points P0...P3 that were used to calculate those distinct points?

If I knew that one of those points X1 was at t=1/4 and X2 was at t=3/4, then I could calculate

P0 = X0
P1 = (1/9)*( -10*X0 + 24*X1 -  8*X2 +  3*X3 )
P2 = (1/9)*(   3*X0 -  8*X1 + 24*X2 - 10*X3 )
P3 = X3


Alternately, if I knew that one of those points X1 was at t=1/3 and X2 was at t=2/3, then I could find a cubic Bezier curve that goes through those 4 points using John Burkardt's approach:

P0 = X0
P1 = (1/6)*( -5*X0 + 18*X1 - 9*X2 + 2*X3 )
P2 = (1/6)*(  2*X0 -  9*X1 +18*X2 - 5*X3 )
P3 = X3.


But while I know t=0 for the first point, and t=1 for the last point, I don't know the t values used to produce any of the other intermediate points on the curve. The 4 points (without t information) don't uniquely define a cubic Bezier curve -- as you can see above, if I use the same 4 points X0...X3 and plug them into the two different approaches above, I get 2 slightly different Bezier curves (the estimated P1 and P2 control points are slightly different), both of which go through all 4 given points.

So when I don't have those t values, I need more than 4 points along the Bezier curve to uniquely determine the original 4 control points.

How do I determine the original 4 control points?

Say I had a series of 100 approximately evenly spaced points along a curve that I know originally came from a Bezier curve -- is there some easier way to determine the original 4 control points then?

(Motivation: When printing something out on a RepRap, often the part was originally designed in some CAD package with smooth surface splines that, when sliced, we would expect to give smooth 2D curves that more-or-less match up with a Bezier curve. However, exporting that model from the CAD package always seems to produce a faceted STL file composed entirely of flat triangles, so the slicer produces thousands of tiny straight lines with endpoints that touch that Bezier curve. I want to try to convert those series of tiny straight lines back into a single cubic Bezier curve. I suspect the Arduino can parse an line of ASCII text containing the 4 control points of a single cubic Bezier curve much faster than it could parse a few hundred lines of ASCII text, each one containing the 2 endpoints of a short straight line.)

-

As you say, four points (without their associated "t" values) are not enough to define a planar cubic Bezier curve.

In fact, 6 points are needed. But, on the other hand, the 6 points have to satisfy certain conditions, or else the required curve does not exist. In your case, you know that the curve exists, because it was used to generate the points in the first place.

The full story is given in this paper: J. Kozak, M. Krajnc, Geometric interpolation by planar cubic polynomial curves, Comput. Aided Geom. Des., 24 (2007), pp. 67-78. You can get a copy of the paper at the authors website.

Another approach (instead of the clever techniques suggested in the paper) is to use brute-force numerical methods. Start with 6 points $X_1, \ldots, X_6$ and 6 parameter values $t_1, \ldots, t_6$. We can assume that $t_1 = 0$ and $t_6 = 1$, but $t_2, t_3, t_4, t_5$ are unknown.We want to find control points $P_1, P_2, P_3, P_4$ for our curve. Obviously we can set $P_1 = X_1$ and $P_4 = X_6$, but $P_2$ and $P_3$ are unknown. We can (numerically) find values of $t_2, t_3, t_4, t_5$ and $P_2$ and $P_3$ that minimize the quantity

$$\sum_{i=2}^{i=5}\Vert C(t_i) - X_i \Vert^2$$

where $C(t)$ is the Bezier curve with control points $P_1, P_2, P_3, P_4$. This is a fairly nasty non-linear problem, but a good numerical algorithm will usually converge to the desired solution, given a decent starting point.

Another numerical approach: with the same notation we used above, solve the equations: $$C(t_i) = X_i \quad (i = 2,3,4,5)$$ Since the $X_i$ are 2D points, there are 8 equations here. We have 8 unknowns -- $t_2, t_3, t_4, t_5$ and the $x$ and $y$ coordinates of $P_2$ and $P_3$. The equations are non-linear, but a good numerical root-finding package should be able to handle them.

A much better approach is to get the Bezier curves from the CAD package. If the design guys won't give you the curves, you should charge them more money for your services, since they are making your life so much more difficult. Their choice -- curves or cash :-)

-
The design guys are not the problem. The problem is that nearly every 3D CAD package stores curves in its own proprietary binary 3D file format. They are happy to "export" their designs to some other format, but apparently their only choices are (a) some other proprietary binary file format, or (b) a STL made of thousands of tiny flat triangle facets. –  David Cary Feb 13 '13 at 19:57
Nice problem! Let me know if you found everything you needed in the article suggested by bubba or you still want someone to give it a shot. The point is that when you have a dozen points instead of just the minimal number of 6, there may be cheaper techniques available but I need some time to think of it and am reluctant to do so if you are no longer interested :) –  fedja Feb 13 '13 at 20:19
@David -- almost all CAD systems can export data in the standard IGES or STEP formats. Either of these would include the curves and surfaces, and they are just text files, so fairly easy to read. –  bubba Feb 14 '13 at 0:31
@fedja -- if there are cheaper techniques, then certainly I'd be interested to hear about them, even if David isn't. –  bubba Feb 14 '13 at 0:35
@bubba finding a way to get curves from STL is a big deal (and problem), I'm with David on this. The folks who have the STL and want curves simply do not have the original CAD file nor access to it. Rhino3d has primitive means to get curves from STLs projected to a Plane but even then it sometimes uses 100+ lines to draw a circle with 4mm diameter. When I rework peoples' STLs, I end up drawing it all over a gain from scratch. –  Chris K Aug 3 '13 at 4:26