Subdivision methods for curve generation are based upon a procedure which successively refines a control polygon into into a sequence of control polygons that, in the limit, converges to a curve. The curves are commonly called subdivision curves as the refinement methods are based upon the binary subdivision of uniform B-spline curves.
The uniform B-spline curves, surfaces and solids have been extensively studied in the literature and subdivision methods for these objects are well known. We develop here the refinement method for a quadratic uniform B-spline curve and show that the refinement is exactly that specified by Chaikin's Algorithm .
For a pdf version of these notes look here.
The Matrix Equation for the Quadratic Uniform B-Spline Curve
Given a set of control points the quadratic uniform B-spline curve defined by these control points can be defined in segments by the equations
Splitting and Refinement
We will begin by studying the binary subdivision of a quadratic uniform B-spline curve defined by the control polygon , containing only three points, and then extend this to control polygons containing larger numbers of points.
We can perform
a binary subdivision
of the curve, by applying one of two splitting
As it turns out, several of the control points for the two subdivided components are the same. Thus, we can combine these matrices, creating a matrix
i.e. at and along each of the lines of the control polygon. These are the same points as are developed in Chaikin's method
The General Refinement Procedure
The general procedure is - given a control polygon, we can generate a refinement of this set of points by constructing new points along each edge of the original polygon at a distance of and between the endpoints of the edge. The general idea behind subdivision curves is to assemble these points into a new control polygon which can then be used as input to another refinement operation, generating a new set of points and another control polygon - and then continue this process until a refinement is reached that accurately represents the curve to a desired resolution. The following illustration shown the second refinement in the case above.
Since this general refinement procedure is developed from the binary subdivision of a uniform B-spline curve, and the control points of the refined polygon are unions of those of the subdivided curves, we then have that the control points of the refined polygons must converge to the curve. That is, in the limit, the sequence of control polygons generated by the refinement procedure converges to a quadratic uniform B-spline curve. This shows that Chaikin's curve is really a quadratic uniform B-spline curve.
Given a control polygon we can specify a simple process that can be used to generate successive refinements of the control polygon and, in the limit, converges to the uniform B-spline curve defined by the original control polygon. This scheme is the basis for the development of the Doo-Sabin subdivision scheme which generalizes Chaikin's algorithm to surfaces.