How do people come up with subdivision schemes?

Question

Be it chaikin subdivision, loop subdivision, catmull-clark subdivision...

How do people come up with the coefficients for an arbitrary subdivision scheme?

Answer 1

The subdivision schemes are not arbitrary. Catmull-Clark, arguably the most used subdivision scheme, generalizes bicubic B-splines to meshes of arbitrary topology.

Most, other subdivision schemes also generalize other degree B-splines to arbitrary topology. Doo-Sabin for biquadratic B-splines and Loop subdivision generalizes quartic box-splines defined over regular triangulations.

Most of the coefficients for subdivision are obtained by looking at knot-insertion. Knot-insertion is the process of adding knots into B-splines such that the same curve is obtained by expressing it as more curve pieces, i.e. subdividing the original curves. The rules for subdivision and thus the coefficients are derived from these algorithms. However, these rules only hold for the regular regions of the control mesh. For the irregular regions the rules are generalized, such that they give a satisfactory result.

Another way to look at it is through subdivision stencils and masks. The simplest subdivision stencil $[1,1]$ applied to the control polygon with points $P_i, \ldots, P_N$ will generate new points $Q_i = P_i$, will simply insert points at the same positions as the original points. We can convolve the stencil with itself $[1,1] * [1,1] = [1,2,1]$. We can decompose this stencil into an even [1,1] and an odd mask [2] and again apply it to the control polygon by multiplying the coefficients in the mask and dividing by the sum of coefficients. The odd mask $Q_{i*2} = 2 P_i / 2$ will keep the original points, but the even mask will generate points $Q_{i*2+1} = (1 P_i + 1 P_{i+1})/2$ half-way between points.

Continuing the convolution process to the second stencil $[1,2,1] * [1,1] = [1, 3, 3, 1]$ will generate odd $[1, 3]$ and even $[3,1]$ masks which will generate points one quarter and three quarters along the line piece between points $P_i$ and $P_{i+1}$. This are of course the exact coefficients used in Chaikin's corner cutting algorithm, which in the limit of subdivision will generate quadratic B-splines. Applying it again $[1,3, 3,1] * [1,1] = [1, 4, 6, 4, 1]$ will generate the stencils that generate cubic B-splines.

To generalize this again to surfaces we can apply this convolution process in two parametric directions to obtain bi-degree B-splines. In the cubic case we obtain this matrix of coefficients through convolution:

$$\begin{bmatrix}1 & 4 & 6 & 4 & 1\\ 4 & 16 & 24 & 16 & 4\\ 6 & 24 & 36 & 24 & 6\\ 4 & 16 & 24 & 16 & 4\\ 1 & 4 & 6 & 4 & 1\\ \end{bmatrix}$$

We can decompose this matrix into vertex mask:

$\begin{bmatrix}1 & 6 & 1\\ 6 & 36 & 6\\ 1 & 6 & 1\\ \end{bmatrix}$

edge point mask:

$\begin{bmatrix}4 & 24 & 4\\ 4 & 24 & 4\\ \end{bmatrix}$ and $\begin{bmatrix}4 & 4\\ 24 & 24\\ 4 & 4\\ \end{bmatrix}$

face point mask:

$\begin{bmatrix} 16 & 16 \\ 16 & 16 \\ \end{bmatrix}$

Applying these as control point masks to a regular control grid will obtain bicubic B-splines. The observation made for the Catmull-Clark algorithm is that the inserted points through the face stencils are the average of the surrounding vertices. This can easily be generalized for arbitrary polygons, the same thing goes for the edge stencil. The hard case is the vertex stencil as the original is only valid for vertices with valency 4. Catmull-Clark came up with this expression

$$\frac{Q}{N} + \frac{2R}{N} + \frac{S(N-3)}{N}$$

Where $S$ is the old vertex position $R$ is the average of the points created by the edge mask for the outgoing edges of the vertex and $Q$ the average of the points created by face mask for the surrounding faces. The ratios in this expression are such that it reproduces the regular vertex mask in the case $N=4$ and is aesthetically pleasing for other $N$.