This is something I started many years ago and put on the shelf because I never had an immediate use for it. Two utilities are forthcoming in Degrafa; spline->Bezier anad function->Bezier. These utilities approximate functions and specific splines over an interval with quadratic Bezier curves. With these utilities, splines such as natural cubic, parametric, and Catmull-Rom will be easily plottable in the normal Degrafa geometry pipeline.

Following is a screen shot of work in progress on a natural cubic spline. This was originally a derivative test as the spline slope at various points is required for the algorithm. The derivative formula is covered in this TechNote. There is no overlap between successive knot intervals. The blue curve shows a simple point-to-point plot of the natural cubic spline. The red curve shows the quadratic Bezier approximation.

Well over a hundred small lines are used in the traditional plot. There are ten quads. in the above example.

Instead of trying to minimize the total number of quad. Bezier curves, the algorithm produces a modest number of quads in exchange for exact representation at knots and an integral number of quads. per spline segment. This makes it very easy to create specific shapes out of the quad. approximation between knots which could be useful in charting applications.

The spline approximation has many more details to be considered as some splines are cartesian (y as a function of x) and others are parametric (x and y as functions of t in [0,1]), so the Bezier approximation process and specific computations for stopping criteria are a bit different. It’s more complex than midpoint subdivision of a cubic Bezier as the original and approximating function are not always directly comparable.

Subdividing a single cubic Bezier curve is also different than approximating a spline which is represented by multiple cubic polynomials between each knot. I chose to exactly represent the spline data at the knots and produce an integral number of quad. Bezier curves in between knots. This makes it easy to create custom shapes based on the spline curve in between knots, which may be useful for charting applications.

Over the longer term, I’ll also add inflection points into the process as described in the TechNote, although that’s also more complex than just dealing with a cubic Bezier. In short, many, many more algorithmic and programming details to consider.

There are some additional works in the literature you may wish to consider for follow-up such as

Very impressive. Great job!

I would like to know how this relates to http://www.timotheegroleau.com/Flash/articles/cubic_bezier_in_flash.htm

That describes basic midpoint subdivision of only a cubic Bezier curve. More general strategies are discussed in this TechNote – http://www.algorithmist.net/subdivision.html .

The spline approximation has many more details to be considered as some splines are cartesian (y as a function of x) and others are parametric (x and y as functions of t in [0,1]), so the Bezier approximation process and specific computations for stopping criteria are a bit different. It’s more complex than midpoint subdivision of a cubic Bezier as the original and approximating function are not always directly comparable.

Subdividing a single cubic Bezier curve is also different than approximating a spline which is represented by multiple cubic polynomials between each knot. I chose to exactly represent the spline data at the knots and produce an integral number of quad. Bezier curves in between knots. This makes it easy to create custom shapes based on the spline curve in between knots, which may be useful for charting applications.

Over the longer term, I’ll also add inflection points into the process as described in the TechNote, although that’s also more complex than just dealing with a cubic Bezier. In short, many, many more algorithmic and programming details to consider.

There are some additional works in the literature you may wish to consider for follow-up such as

Click to access WileyChildsHamannJoyMax2002b.pdf

http://www.springerlink.com/content/5ftwchh6f3d4pdy6/

I have several other references, but they’re not bookmarked, so I’ll have to look them up and post at a later time.

regards,

– jim

btw, thanks Mario!