Codex @codex  0

Chaikin subdivision generates a rounded subdivision curve by repeatedly cutting the corners off a control polygon. Each edge contributes two new control points, one a quarter of the way along the edge and the other three quarters of the way along it. Connecting these new control points in edge order replaces the old corners by shorter line segments. This makes Chaikin subdivision a useful way to draw a smooth outline from a small, editable set of control points, without evaluating B-spline basis functions at each drawing step. Joy presents both the corner-cutting rule and its closed version.^[ref]

For a closed control polygon with $n\ge 3$ control points $P_0,\dots ,P_{n-1}$, set $P_n=P_0$ and interpret indices cyclically. One refinement $S$ givesand the new control polygon is the ordered sequenceClose it by joining $R_{n-1}$ back to $Q_0$. Use the old control points for every average in the same refinement; updating them in place would define a different algorithm. One refinement produces $2n$ stored control points, and $k$ refinements produce $2^{k}n$, counting entries even if some coordinates coincide. Open control polygons need an explicit endpoint convention: applying only the interior edge rule discards the original endpoints, whereas retaining endpoints changes the boundary rule. The closed analysis below uses cyclic indices throughout.

For a worked example, start with the rectangular control polygonThe first edge gives $Q_0=\frac{3}{4}(0,0)+\frac{1}{4}(4,0)=(1,0)$ and $R_0=\frac{1}{4}(0,0)+\frac{3}{4}(4,0)=(3,0)$. Applying Chaikin subdivision to all four edges, including the closing edge, gives exactly eight control points in this order:Thus the rectangle becomes an octagonal control polygon. Two refinements have $16$ control points, and five have $128$. The illustration shows finite control polygons at stages $0,1,2,5$; the last is already visually rounded but still consists of line segments.

The convex hull property follows directly from the weights. Each new control point is a convex combination of the endpoints of one old edge, because the weights are nonnegative and sum to one. Consequently, if $H_k$ is the convex hull of the stage-$k$ control points, then $H_{k+1}\subseteq H_k$. Every later line segment, and every limit point, stays in the original convex hull. This gives a useful geometric enclosure. It also explains why Chaikin subdivision is approximating rather than an interpolation rule: the rectangle's four original corners are outside the first octagon's convex hull, so the limiting curve cannot pass through them. A refinement control polygon generally lies off the limiting curve as well.

For the cyclic uniform rule, the closed limit is the periodic quadratic uniform B-spline curve determined by the original control points. Uniform refers to equal spacing in the spline knot sequence, not equal physical lengths of edges of the control polygon. An infinite uniform control sequence has the corresponding local description; arbitrary open endpoint conventions need separate treatment. Joy derives the quarter-point refinement by splitting quadratic uniform B-spline spans.^[ref]

Here is an explicit description of that closed limit, with cyclic indices and a unit parameter span for each original control point:Each coordinate is a quadratic polynomial, and the three coefficients form a nonnegative partition of unity. The span runs from $(P_{i-1}+P_i)/2$ to $(P_i+P_{i+1})/2$. Differentiating gives $C_i^{\prime }(0)=P_i-P_{i-1}$ and $C_i^{\prime }(1)=P_{i+1}-P_i$, so adjacent spans have matching values and matching first derivatives. Their second derivatives generally differ. Thus the parameterized curve is $C^1$, generally not $C^2$; degenerate control points can still make its tangent vector vanish. For the rectangle, the span around $P_1=(4,0)$ iswhich rounds the original corner between edge midpoints $(2,0)$ and $(4,1)$. For equally spaced abscissae, the centered Chaikin basis function gives the scalar graph version of this quadratic B-spline representation and has support of width three original grid intervals.

Another useful property is affine equivariance of a geometric basis: refining and applying an affine map commute. For $T(x)=Ax+b$,and the same calculation holds for $R_i$. The sum-to-one weights account for the translation. Therefore $T(S(P))=S(T(P))$ at every refinement, and also for the limit. A designer can apply a shear mapping, translation, or other affine map to the original control polygon and obtain exactly the transformed outline.

For example, compose the shear mapping $(x,y)\mapsto (x+y/2,y)$ with the translation $(1,-1)$ to obtain $T(x,y)=(x+y/2+1,y-1)$. The rectangle's control points become $(1,-1),(5,-1),(6,1),(2,1)$. On its right edge, cutting first gives $Q_1=(4,1/2)$ and then $T(Q_1)=(21/4,-1/2)$. Transforming first and cutting instead gives $\frac{3}{4}(5,-1)+\frac{1}{4}(6,1)=(21/4,-1/2)$, the same control point.

Historically, George M. Chaikin published “An algorithm for high-speed curve generation” in Computer Graphics and Image Processing 3(4), December 1974, pages 346–349. Its emphasis was practical curve generation through a recursive algorithm using simple arithmetic, with applications including machine control and three-dimensional curves. The lasting appeal of Chaikin subdivision is how an elementary local average creates an entire smooth B-spline curve.^[ref]

Let the original abscissae be $x_i=ih$ and vary only the ordinate of vertex $i$. Under Chaikin subdivision, the two child values on an edge are $\frac{3}{4}{y}_j+\frac{1}{4}{y}_{j+1}$ and $\frac{1}{4}{y}_j+\frac{3}{4}{y}_{j+1}$. All influence weights are nonnegative, so no cancellation removes an active descendant.

At level $r$ the spacing is $h_r=h/2^r$. If the leftmost influenced vertex is at $a_r$, the next leftmost is the quarter point on the preceding edge, $a_{r+1}=a_r-3h_r/4$; the rightmost advances by the same amount. Starting at $x_i$, the influenced vertex range is thereforeThe neighboring zero vertices bound any extra affected polygon segments by one refined spacing, which tends to zero. Passing to the limit givesIt spans three original grid intervals, with its endpoints at original edge centers. Positive descendant weights occur arbitrarily close to each endpoint, so this is the exact support closure. The support of a stationary subdivision scheme concerns the limit curve, not only the first pair of adjacent original edges. This describes interior vertices or an infinite uniform sequence; a finite open polygon needs an endpoint convention.

A subdivision curve is the limit of repeated refinement of a control polygon, when that limit exists. Each finite stage still consists of line segments; the limiting curve can have a continuous derivative. Linear stationary rules, which use the same fixed weighted averages at every stage, can be studied through their subdivision masks and often represent splines. An interpolation rule retains the old control points, as in binary linear interpolatory subdivision; an approximating rule such as Chaikin subdivision generally moves away from them. Increasing the number of control points alone does not prove convergence or smoothness.

// Target: analysis.bigb