= Chaikin subdivision
{c}
{title2=$Q_i=\tfrac34P_i+\tfrac14P_{i+1},\quad R_i=\tfrac14P_i+\tfrac34P_{i+1}$}
= Chaikin's algorithm
{c}
{synonym}
= Chaikin corner cutting
{c}
{synonym}
<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.https://www.cs.unc.edu/~dm/UNC/COMP258/LECTURES/Chaikins-Algorithm.pdf[Kenneth I. Joy, Chaikin's Algorithms for Curves, §§Chaikin's Method and Example — A Closed Curve, UC Davis authored notes]{ref}
For a closed <control polygon> with $n\geq3$ <control points> $P_0,\ldots,P_{n-1}$, set $P_n=P_0$ and interpret indices cyclically. One refinement $S$ gives
$$
Q_i=\frac34P_i+\frac14P_{i+1},\qquad R_i=\frac14P_i+\frac34P_{i+1},\qquad 0\leq i<n,
$$
and the new <control polygon> is the ordered sequence
$$
S(P)=(Q_0,R_0,Q_1,R_1,\ldots,Q_{n-1},R_{n-1}).
$$
Close 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^kn$, 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 polygon>
$$
P_0=(0,0),\quad P_1=(4,0),\quad P_2=(4,2),\quad P_3=(0,2).
$$
The first edge gives $Q_0=\tfrac34(0,0)+\tfrac14(4,0)=(1,0)$ and $R_0=\tfrac14(0,0)+\tfrac34(4,0)=(3,0)$. Applying <Chaikin subdivision> to all four edges, including the closing edge, gives exactly eight <control points> in this order:
$$
(1,0),\ (3,0),\ (4,\tfrac12),\ (4,\tfrac32),\ (3,2),\ (1,2),\ (0,\tfrac32),\ (0,\tfrac12).
$$
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>.
\Image[/chaikin-corner-cutting-iterations.png]
{title=Chaikin corner cutting on a rectangle at iterations zero, one, two and five}
{description=The dashed rectangle is the original <control polygon> and its <convex hull>. Blue <line segments> and dots show the current <control polygon> and <control points>; no panel claims to be the exact limiting <curve>.}
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.https://www.cs.unc.edu/~dm/UNC/COMP258/LECTURES/Quadratic-B-Spline-Curve-Refinement.pdf[Kenneth I. Joy, Quadratic Uniform B-Spline Curve Refinement, §§Splitting and Refinement and The General Refinement Procedure, UC Davis authored notes]{ref}
Here is an explicit description of that closed limit, with cyclic indices and a unit parameter span for each original <control point>:
$$
C_i(u)=\frac{(1-u)^2}{2}P_{i-1}+\left(\frac12+u-u^2\right)P_i+\frac{u^2}{2}P_{i+1},\qquad 0\leq u\leq1.
$$
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'(0)=P_i-P_{i-1}$ and $C_i'(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)$ is
$$
C_1(u)=(2+4u-2u^2,\ u^2),\qquad C_1(\tfrac12)=(\tfrac72,\tfrac14),
$$
which 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$,
$$
T(Q_i)=A\left(\frac34P_i+\frac14P_{i+1}\right)+b=\frac34T(P_i)+\frac14T(P_{i+1}),
$$
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 $\tfrac34(5,-1)+\tfrac14(6,1)=(21/4,-1/2)$, the same <control point>.
\Image[/chaikin-affine-equivariance.png]
{title=Shearing and translating a control polygon commutes with one Chaikin refinement}
{description=Left: the rectangle and its first refinement. Right: the transformed <control polygon>, with blue dots from cutting after the <affine map> and orange rings from applying the <affine map> after cutting. All eight pairs coincide.}
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>.https://doi.org/10.1016/0146-664X(74)90028-8[G. M. Chaikin, An algorithm for high-speed curve generation, Computer Graphics and Image Processing 3(4), 346–349, 1974; publisher metadata and abstract]{ref}
Back to article page
