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

<p>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.  </p>

<p>Most of the coefficients for subdivision are obtained by looking at <a href="https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/single-insertion.html" rel="noreferrer">knot-insertion</a>. 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.</p>

<p>Another way to look at it is through subdivision stencils and masks. The simplest subdivision stencil <span class="math-container">$[1,1]$</span> applied to the control polygon with points <span class="math-container">$P_i, \ldots, P_N$</span> will generate new points <span class="math-container">$Q_i = P_i$</span>, will simply insert points at the same positions as the original points. 
We can convolve the stencil with itself <span class="math-container">$[1,1] * [1,1] = [1,2,1]$</span>. 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 <span class="math-container">$Q_{i*2} = 2 P_i / 2$</span> will keep the original points, but the even mask will generate points <span class="math-container">$Q_{i*2+1} = (1 P_i + 1 P_{i+1})/2$</span> half-way between points. </p>

<p>Continuing the convolution process to the second stencil <span class="math-container">$[1,2,1] * [1,1] = [1, 3, 3, 1]$</span> will generate odd <span class="math-container">$[1, 3]$</span> and even <span class="math-container">$[3,1]$</span> masks which will generate points one quarter and three quarters along the line piece between points <span class="math-container">$P_i$</span> and <span class="math-container">$P_{i+1}$</span>. 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 <span class="math-container">$[1,3, 3,1] * [1,1] = [1, 4, 6, 4, 1]$</span> will generate the stencils that generate cubic B-splines. </p>

<p>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:</p>

<p><span class="math-container">$$\begin{bmatrix}1 &amp; 4 &amp; 6 &amp; 4 &amp; 1\\
                4 &amp; 16 &amp; 24 &amp; 16 &amp; 4\\
                6 &amp; 24 &amp; 36 &amp; 24 &amp; 6\\
                4 &amp; 16 &amp; 24 &amp; 16 &amp; 4\\
                1 &amp; 4 &amp; 6 &amp; 4 &amp; 1\\ \end{bmatrix}$$</span></p>

<p>We can decompose this matrix into vertex mask:</p>

<p><span class="math-container">$\begin{bmatrix}1 &amp;  6 &amp; 1\\
                6 &amp; 36 &amp; 6\\
                1 &amp;  6 &amp; 1\\ \end{bmatrix}$</span></p>

<p>edge point mask:</p>

<p><span class="math-container">$\begin{bmatrix}4 &amp;  24 &amp; 4\\ 4 &amp; 24 &amp; 4\\ \end{bmatrix}$</span> and <span class="math-container">$\begin{bmatrix}4 &amp; 4\\ 24 &amp; 24\\ 4 &amp; 4\\ \end{bmatrix}$</span> </p>

<p>face point mask:</p>

<p><span class="math-container">$\begin{bmatrix}
16 &amp; 16 \\
16 &amp; 16 \\
\end{bmatrix}$</span></p>

<p>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</p>

<p><span class="math-container">$$\frac{Q}{N} + \frac{2R}{N} + \frac{S(N-3)}{N}$$</span></p>

<p>Where <span class="math-container">$S$</span> is the old vertex position <span class="math-container">$R$</span> is the average of the points created by the edge mask for the outgoing edges of the vertex and <span class="math-container">$Q$</span> 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 <span class="math-container">$N=4$</span> and is aesthetically pleasing for other <span class="math-container">$N$</span>.</p>

CC BY-SA 4.0
2020-02-10T13:54:04.123Z
2020-02-10T14:15:13.270Z
2020-02-10T14:15:13.270Z
Reynolds
<p>Be it chaikin subdivision, loop subdivision, catmull-clark subdivision...</p>

<p>How do people come up with the coefficients for an arbitrary subdivision scheme?</p>

CC BY-SA 4.0
2020-02-09T09:56:58.350Z
Short answer: math.
lightxbulb
<algorithm><mathematics><curve><subdivision>
How do people come up with subdivision schemes?
Makogan
# How do people come up with subdivision schemes?

(Asked by: username_0 on 2020-02-08)

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

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

**Tags:** algorithm, mathematics, curve, subdivision

> **Comments:**
> **username_1**: Short answer: math.  

---

## 1 answers

### Answer by username_2 on 2020-02-10. Score: 9 | Accepted answer

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](https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/B-spline/single-insertion.html). 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$.


---

