This chapter links to the course’s interactive demos and uses MathJax for its formulas. Read it through the course website (or download the file and open it in a browser); a Canvas inline preview will reach neither the demos nor the math. All chapters.

Curves and Surfaces: Bézier, B-Splines, Subdivision

Paul de Casteljau devised his curve algorithm at Citroën in 1959, in internal reports the company kept secret; Pierre Bézier published the same curves from Renault, and they carry his name. Farin, A History of Curves and Surfaces in CAGD, 2002

A triangle mesh is a list of flat pieces. A designer does not think in flat pieces; a designer moves a handful of points and expects a smooth shape to follow. This chapter is the mathematics of that expectation. A cubic Bézier curve is four control points blended by four polynomials, and de Casteljau’s construction evaluates it with nothing but repeated midpoints; the chapter works one curve both ways at \(t = 0.5\), reads its tangent off the construction, writes the same curve as a matrix product, and renders it by splitting until the pieces are flat. It measures the curve’s speed, arc length and curvature, since an animator and a tessellator both need them. Longer shapes are pieces joined with a continuity condition, or a B-spline whose control points act locally and whose knot vector is worked with de Boor’s algorithm, or a rational curve that can be an exact circle. The same ideas one dimension up give the bicubic patch of the Utah teapot, and the corner-cutting idea applied to a polygon, a cube and an icosahedron gives subdivision curves and surfaces, with one step of Catmull–Clark and one of Loop worked by hand. A last section gives the other way to define a smooth shape, as the zero set of a field. The meshes that get rendered are still triangles; these are the shapes they approximate.

1 · Parametric curves

The alternatives are worse for drawing. An explicit form \(y = f(x)\) cannot turn back on itself; an implicit form \(F(x, y) = 0\) says whether a point is on the curve but not how to walk along it (Section 12 returns to it, because for surfaces it has its own uses). A parametric curve is walked by stepping \(t\), which is exactly what a renderer needs to turn it into line segments and what an animator needs to move an object along it. Polynomials are the choice because they are cheap to evaluate, closed under the affine transforms of the affine chapter, and easy to differentiate. Cubics are the usual degree: the lowest that can bend twice (an S) and that can be joined with matching tangents at both ends.

2 · Bézier curves and de Casteljau’s construction

Four consequences read off the definition. The curve interpolates its ends, \(\mathbf{B}(0) = \mathbf{P}_0\) and \(\mathbf{B}(1) = \mathbf{P}_3\), and passes through no other control point in general. Its end tangents are \(\mathbf{B}'(0) = 3(\mathbf{P}_1 - \mathbf{P}_0)\) and \(\mathbf{B}'(1) = 3(\mathbf{P}_3 - \mathbf{P}_2)\): the curve leaves \(\mathbf{P}_0\) toward \(\mathbf{P}_1\) and arrives at \(\mathbf{P}_3\) from \(\mathbf{P}_2\), which is why dragging the inner points feels like bending the ends. Because the weights are a partition of unity, the curve stays in the convex hull of its control points, and an affine transform of the points transforms the curve (affine invariance): to move a curve, move its four points. And a straight line crosses the curve no more often than it crosses the control polygon (variation diminishing): the curve wiggles less than its polygon.

node -e "
const lerp=(a,b,t)=>a.map((x,i)=>x+(b[i]-x)*t);
let L=[[0,0],[1,2],[3,3],[4,0]]; const t=0.25;
while(L.length>1){L=L.slice(0,-1).map((p,i)=>lerp(p,L[i+1],t));console.log(JSON.stringify(L));}"

[[0.25,0.5],[1.5,2.25],[3.25,2.25]]
[[0.5625,0.9375],[1.9375,2.25]]
[[0.90625,1.265625]]

The same construction with \(n + 1\) control points and \(n\) levels gives the degree-\(n\) curve; degree 2 (three points) is common in fonts, degree 3 nearly everywhere else. A curve can also be raised in degree without changing its shape: the cubic’s five quartic control points are \(\mathbf{Q}_i = \tfrac{i}{4}\mathbf{P}_{i-1} + (1 - \tfrac{i}{4})\mathbf{P}_i\), which for the curve above gives \((0,0), (0.75, 1.5), (2, 2.5), (3.25, 2.25), (4, 0)\), a polygon closer to the curve than the original. Degree elevation is how two pieces of different degree are made compatible before they are joined or blended.

3 · The matrix form, and changing basis

Any cubic is \(\mathbf{c}(t) = \mathbf{a}t^3 + \mathbf{b}t^2 + \mathbf{c}t + \mathbf{d}\); the Bézier, Hermite and B-spline forms differ only in what the four vector coefficients are called. Writing the monomials as a row and the four control quantities as a column, each form is one constant \(4\times4\) basis matrix.

Two forms with the same power-basis coefficients are the same curve, so converting between them is a matrix product: \(\mathbf{G}_{\text{new}} = M_{\text{new}}^{-1} M_{\text{old}}\, \mathbf{G}_{\text{old}}\). Two conversions are used constantly.

The matrix form is also the fast way to evaluate many points: \(M\mathbf{G}\) is computed once per piece, and each point costs one dot product with \((t^3, t^2, t, 1)\). GPU tessellation shaders and font rasterizers do exactly this.

4 · Rendering a curve: subdivision and the flatness test

A curve is drawn as line segments, and the question is how many. Stepping \(t\) uniformly wastes segments where the curve is straight and starves it where it bends. De Casteljau’s construction answers better, because it also splits the curve: the points down the left edge of the triangle in the figure of Section 2 (\(\mathbf{P}_0\), \((0.5, 1)\), \((1.25, 1.75)\), \((2, 1.875)\)) are the control points of the piece on \([0, 0.5]\), and the right edge gives the piece on \([0.5, 1]\).

The test is in every vector-graphics rasterizer and font engine. In three dimensions the same rule tessellates a patch (Section 10): split in \(u\) and \(v\) until the sub-patch is flat to a fraction of a pixel, which is a screen-space tolerance and therefore a level of detail that follows the camera for free, the point made about the bunny in the meshes chapter.

5 · Speed, arc length, and curvature

The parameter \(t\) is not distance. The tangent \(\mathbf{B}'(t)\) has a length, the speed, and it varies along the curve; equal steps in \(t\) give unequal steps along the curve, which an animator moving an object along a path notices at once as unmotivated acceleration.

The animation chapter uses exactly this: a keyframed path is reparametrized by arc length so that easing controls the speed and the spline controls only the shape. Curvature is what a designer’s “fair curve” means, a curvature that varies smoothly, and the curvature comb (normals scaled by \(\kappa\)) is the tool CAD systems draw to show it.

6 · Joining pieces: continuity

One cubic cannot do much. Long shapes are chains of cubic pieces, and what matters is how each piece meets the next. Two pieces are \(C^0\) if they share the endpoint; \(C^1\) if their tangent vectors match there (same direction and same length, so a point moving along them at constant \(t\) has continuous velocity); \(G^1\) if only the tangent directions match (the shape is smooth, the speed may jump); \(C^2\) if the second derivatives match too, which is what a highlight sliding across a car body needs in order not to kink, and \(G^2\) if the curvature of Section 5 is continuous, which is what the eye reads as a fair curve.

Chains are usually specified differently. A Hermite piece is given by its two endpoints and the two tangent vectors there, the \(M_{\text{Herm}}\) form of Section 3, \[ \mathbf{h}(s) = (2s^3 - 3s^2 + 1)\,\mathbf{p}_a + (s^3 - 2s^2 + s)\,\mathbf{m}_a + (-2s^3 + 3s^2)\,\mathbf{p}_b + (s^3 - s^2)\,\mathbf{m}_b, \] which is the Bézier piece with \(\mathbf{P}_1 = \mathbf{p}_a + \mathbf{m}_a/3\) and \(\mathbf{P}_2 = \mathbf{p}_b - \mathbf{m}_b/3\). A Catmull–Rom spline through points \(\mathbf{p}_0, \mathbf{p}_1, \ldots\) is a chain of Hermite pieces with the tangent at each point set to half the chord between its neighbors, \(\mathbf{m}_i = \tfrac12(\mathbf{p}_{i+1} - \mathbf{p}_{i-1})\): \(C^1\) by construction and passing through every point, which is what an animator wants of a path through keyframes. The animation chapter works the keyframe demo’s spline this way. A Catmull–Rom spline is not \(C^2\); the B-spline of the next section is, at the price of not passing through its points.

7 · B-splines, knot vectors, and de Boor’s algorithm

A Bézier chain has a defect for design: moving one control point changes the whole piece, and \(C^2\) joins impose constraints the designer must maintain by hand. The B-spline trades interpolation for both. Its pieces use the same four-point blend with a different basis, and every control point influences exactly four consecutive pieces.

The general B-spline is defined over a knot vector \(u_0 \le u_1 \le \cdots\), a nondecreasing list of parameter values at which the pieces meet. The basis functions come from the Cox–de Boor recursion, each one a bump spanning four knot intervals, and the curve on any interval is the blend of the four control points whose bumps cover it.

Locality is the design consequence: a control point moves only the four pieces whose basis functions overlap its own, and a designer sculpts one part of a hull without disturbing the rest. Knots add a second kind of control: a repeated knot puts a corner into an otherwise smooth curve without splitting it into separate objects. Non-uniform knot spacing is what the N in NURBS stands for.

8 · Rational curves and NURBS

Polynomial pieces cannot represent a circle exactly: no polynomial parametrization traces a circle. The fix is to divide. Give each control point a weight \(w_i\), evaluate the polynomial curve on the weighted points in one dimension up, and divide by the polynomial of the weights: \[ \mathbf{r}(t) = \frac{\sum_i B_i(t)\, w_i\, \mathbf{C}_i}{\sum_i B_i(t)\, w_i}. \] The weight is a fourth homogeneous coordinate and the division is the projective divide of the affine chapter, which is why a rational curve is exactly a polynomial curve in homogeneous space projected down, and why a perspective projection of a rational curve is another rational curve (the projection is a linear map of the homogeneous points). With a knot vector as well, this is a NURBS curve, non-uniform rational B-spline, the representation of every CAD system and of the glTF and STEP file formats’ curves.

Raising a weight pulls the curve toward that control point without moving the point, a second handle on the shape; \(w_i \to \infty\) drags the curve through \(\mathbf{C}_i\), \(w_i = 0\) removes it. The price of rationality is that the curve’s parametrization is no longer polynomial, so the speed and arc length of Section 5 must be computed on the divided form, and that degree elevation and subdivision act on the homogeneous points.

9 · Corner cutting: subdivision curves

There is a third way to get a smooth curve from a polygon, and it needs no basis functions at all. Chaikin’s algorithm (1974) replaces every edge of the polygon by its points at one quarter and three quarters, discarding the old vertices. Each step doubles the point count and cuts every corner; the limit is a smooth curve. It is, in fact, exactly the uniform quadratic B-spline of the original polygon, and the subdivision rule is what the B-spline’s refinement property looks like when written as geometry.

The cubic B-spline has a corner-cutting rule too (the Lane–Riesenfeld algorithm: double every vertex, then take midpoints twice), and Section 4’s de Casteljau split is the same idea for a single Bézier piece. Subdivision is the mechanism that scales to surfaces in Section 11.

10 · Surfaces: the bicubic patch

The Utah teapot, the course’s test model since the 1970s at Utah, is 32 of these patches; a renderer tessellates each into a grid of triangles by evaluating \(\mathbf{S}\) on a lattice of \((u, v)\), exactly the sweep-and-index construction of the meshes chapter, and computes normals from the tangents rather than from the triangles. The flatness test of Section 4 applied in both directions decides how fine the lattice must be, and a GPU tessellation stage does exactly this with the tolerance set in pixels. Everything else in this chapter has a surface version by the same tensor-product step: a B-spline surface, a NURBS surface (a sphere is exact, as the circle was), a Hermite patch with sixteen quantities including four twist vectors at the corners.

Joining patches with continuity is harder than joining curves: \(C^1\) across an edge constrains two rows of control points, and around a vertex where other than four patches meet it cannot be done in general. That difficulty is what the next section removes.

11 · Subdivision surfaces: Catmull–Clark and Loop

Chaikin’s idea in two dimensions: start from any polygon mesh, insert points and reconnect by a fixed rule, repeat, and the limit is a smooth surface. Catmull and Clark’s rule (1978) works on meshes of arbitrary faces and produces quads; Loop’s rule (1987) works on triangles. Both give a surface that is \(C^2\) almost everywhere and \(C^1\) at the extraordinary vertices where the valence is not the regular one (four for quads, six for triangles), and neither needs the designer to manage continuity: a coarse control cage is the whole specification.

The limit surfaces are not spheres, but they are smooth blobs, and adding cage vertices near a corner sharpens it; tagging an edge as a crease modifies the rule along it to keep a sharp fold. Film characters have been Catmull–Clark cages since Pixar’s Geri’s Game (1997), every modeling tool has the button, and a renderer tessellates the cage to the pixel-appropriate depth with the counts above, a level-of-detail scheme for free. Loop is the choice when the input is already triangles, as scanned meshes are. The limit position of a vertex, where it ends up after infinitely many steps, has a closed form (a fixed weighted average of its one-ring), so the limit surface can be evaluated and its normal computed without subdividing at all, which is how the smooth surface is drawn exactly on the GPU. The output is, once more, triangles.

12 · Implicit surfaces and metaballs

Implicit surfaces are the natural representation for anything that merges and splits (liquids, organic blobs), for constructive solid geometry (union is \(\max\), intersection \(\min\)), and for the signed-distance fields that the sculpting tools and the learned representations of the learned-scenes chapter use. Their cost is that nothing walks along them: to render one, either march rays until \(F\) crosses \(T\) (the ray tracer’s approach, cheap when \(F\) is a distance) or convert to triangles with marching cubes (Lorensen and Cline, 1987), which samples \(F\) on a grid, classifies each cell’s eight corners as in or out, and emits the triangles of one of 15 cases (256 with symmetries) with vertices placed on the cell edges by linear interpolation of \(F\). The red contour in the figure is the two-dimensional version of exactly that test. The result is a mesh, and everything in the meshes chapter applies to it.

13 · Exercises

node -e "
const M=[[-1,3,-3,1],[3,-6,3,0],[-3,3,0,0],[1,0,0,0]], G=[[0,0],[1,2],[3,3],[4,0]];
const C=M.map(r=>[0,1].map(k=>r.reduce((a,m,j)=>a+m*G[j][k],0)));
const t=0.5, T=[t**3,t**2,t,1];
console.log(C, [0,1].map(k=>T.reduce((a,x,i)=>a+x*C[i][k],0)));"