On-Line Geometric Modeling Notes
BIQUADRATIC UNIFORM B-SPLINE SURFACE REFINEMENT

Overview

Subdivision surfaces are based upon the binary subdivision of the uniform B-spline surface. In general, they are defined by a initial polygonal mesh, along with a subdivision (or refinement) operation which, given a polygonal mesh, will generate a new mesh that has a greater number of polygonal elements, and is hopefully ``closer'' to some resulting surface. By repetitively applying the subdivision procedure to the initial mesh, we generate a sequence of meshes that (hopefully) converges to a resulting surface.

As it turns out, this is a well known process when the mesh has a ``rectangular'' structure and the subdivision procedure is an extension of binary subdivision for uniform B-spline surfaces. In these notes we present a study of the quadratic uniform B-spline case, and develop the refinement rules that can be generalized into the Doo-Sabin subdivision method.

For a pdf version of these notes look here.

The Matrix Equation for a Uniform Biquadratic Spline Surface

Consider the biquadratic uniform B-spline surface ${\bf P} (u,v)$ defined by the $3 \times 3$ array of control points

$$P \: = \: \left[ \begin{array}{ccc} {\bf P} _{0,0} & {\bf P} _{0,... ...1,2} \\ {\bf P} _{2,0} & {\bf P} _{2,1} & {\bf P} _{2,2} \end{array}\right]$$

and the following equation (in matrix form)

$${\bf P} (u,v) \: = \: \left[ \begin{array}{ccc} 1 & u & u^2 \en... ...ay}\right] M P M^T \left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array}\right]$$

where $M$ is the $3 \times 3$ matrix

$$M \: = \: \frac{1}{2} \left[ \begin{array}{rrr} 1 & 1 & 0 \\ -2 & 2 & 0 \\ 1 & -2 & 1 \end{array}\right]$$

The matrix $M$ defines the quadratic uniform B-spline blending functions when multiplied by $\left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array} \right]$.

Subdividing the Surface

This patch can be subdivided into four subpatches, which can be generated from 16 unique sub-control points. We focus on the subdivision scheme for only one of the four (the subpatch corresponding to $0 \leq u,v \leq \frac{1}{2}$), as the others will follow by symmetry. The following figure illustrates the 16 points produced by subdividing into four subpatches. We have outlined the initial subpatch that we consider below. It should be noted that the four ``interior'' control points are utilized by each of the four subpatch components of the subdivision.

To subdivide the surface, we consider the reparameterization of the surface by $u'=\frac{u}{2}$ and $v'=\frac{v}{2}$ and define this new surface as ${\bf P} '(u,v)$. Substituting these into the equation, we obtain

$${\bf P} '(u,v) = {\bf P} ( \frac{u}{2}, \frac{v}{2} )$$

$$= \left[ \begin{array}{ccc} 1 & \frac{u}{2} & \left(\frac{u}{2}... ... \frac{v}{2} \\ \left(\frac{v}{2}\right)^2 \end{array}\right]$$

$$= \left[ \begin{array}{ccc} 1 & u & u^2 \end{array}\right] \lef... ...ht] ^T \left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array}\right]$$

$$= \left[ \begin{array}{ccc} 1 & u & u^2 \end{array}\right] M M^... ...^T M^T \left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array}\right]$$

$$= \left[ \begin{array}{ccc} 1 & u & u^2 \end{array}\right] M \l... ...t) M^T \left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array}\right]$$

$$= \left[ \begin{array}{ccc} 1 & u & u^2 \end{array}\right] M \l... ...^T M^T \left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array}\right]$$

$$= \left[ \begin{array}{ccc} 1 & u & u^2 \end{array}\right] M P' M^T \left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array}\right]$$

where $P' = S P S^T$ and

$$S \: = \: M^{-1} \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{4} \end{array}\right] M$$

Through this process, we have written the surface ${\bf P} '(u,v)$ as

$${\bf P} '(u,v) \: = \: \left[ \begin{array}{ccc} 1 & u & u^2 \e... ...ay}\right] M S M^T \left[ \begin{array}{c} 1 \\ v \\ v^2 \end{array}\right]$$

for some $3 \times 3$ control point array $S$. This implies that ${\bf P} '(u,v)$ is a uniform biquadratic B-spline patch. The matrix $S$ is typically called the ``splitting matrix'', and is given by

$$S = \frac{1}{2} \left[ \begin{array}{rrr} 2 & -1 & 0 \\ 2 & 1 & ... ...rrr} 1 & 1 & 0 \\ -2 & 2 & 0 \\ 1 & -2 & 1 \end{array}\right]$$

$$= \frac{1}{4} \left[ \begin{array}{rrr} 3 & 1 & 0 \\ 1 & 3 & 0 \\ 0 & 3 & 1 \end{array}\right]$$

and so the control point mesh $P'$ corresponding to the subdivided patch is related to the original control points mesh by

$$P' \: = \: S P S^T$$

By carrying out the algebra, we have that

$$P' = \frac{1}{4} \left[ \begin{array}{rrr} 3 & 1 & 0 \\ 1 & 3 & 0... ...rr} 3 & 1 & 0 \\ 1 & 3 & 0 \\ 0 & 3 & 1 \end{array}\right] ^T$$

$$= \frac{1}{16} \left[ \begin{array}{ccc} 3 {\bf P} _{0,0} + {\b... ...}{rrr} 3 & 1 & 0 \\ 1 & 3 & 3 \\ 0 & 0 & 1 \end{array}\right]$$

$$= \frac{1}{16} \left[ \begin{array}{ccc} {\bf P} _{0,0}' & {\bf... ...,0}' & {\bf P} _{2,1}' & {\bf P} _{2,2}' \\ \end{array}\right]$$

where the ${\bf P} '_{i,j}$ can be written as

$${\bf P} _{0,0}' = \frac{1}{16} \left( 3 ( 3 {\bf P} _{0,0} + {\bf P} _{1,0} ) + ( 3 {\bf P} _{0,1} + {\bf P} _{1,1} ) \right)$$

$${\bf P} _{0,1}' = \frac{1}{16} \left( ( 3 {\bf P} _{0,0} + {\bf P} _{1,0} ) + 3 ( 3 {\bf P} _{0,1} + {\bf P} _{1,1} ) \right)$$

$${\bf P} _{0,2}' = \frac{1}{16} \left( 3 ( 3 {\bf P} _{0,1} + {\bf P} _{1,1} ) + ( 3 {\bf P} _{0,2} + {\bf P} _{1,2} ) \right)$$

$${\bf P} _{1,0}' = \frac{1}{16} \left( 3 ( {\bf P} _{0,0} + 3 {\bf P} _{1,0} ) + ( {\bf P} _{0,1} + 3 {\bf P} _{1,1} ) \right)$$

$${\bf P} _{1,1}' = \frac{1}{16} \left( ( {\bf P} _{0,0} + 3 {\bf P} _{1,0} ) + 3 ( {\bf P} _{0,1} + 3 {\bf P} _{1,1} ) \right)$$

$${\bf P} _{1,2}' = \frac{1}{16} \left( 3 ( {\bf P} _{0,1} + 3 {\bf P} _{1,1} ) + ( {\bf P} _{0,2} + 3 {\bf P} _{1,2} ) \right)$$

$${\bf P} _{2,0}' = \frac{1}{16} \left( 3 ( 3 {\bf P} _{1,0} + {\bf P} _{2,0} ) + ( 3 {\bf P} _{1,1} + {\bf P} _{2,1} ) \right)$$

$${\bf P} _{2,1}' = \frac{1}{16} \left( ( 3 {\bf P} _{1,0} + {\bf P} _{2,0} ) + 3 ( 3 {\bf P} _{1,1} + {\bf P} _{2,1} ) \right)$$

$${\bf P} _{2,2}' = \frac{1}{16} \left( 3 ( 3 {\bf P} _{1,1} + {\bf P} _{2,1} ) + ( 3 {\bf P} _{1,2} + {\bf P} _{2,2} ) \right)$$

These equations can be looked at in two ways:

1.

Each of these points ${\bf P} _{i,j}$ utilizes the four points on a certain face of the rectangular mesh, and calculates a new point by weighing the four points in the ratio of 9-3-3-1. Thus, this algorithm can be specified by using subdivision masks, which specify the ratios of the points on a face to generate the new points. In this case, the subdivision masks are as follows

2.

Each of these equations is built from weighing the points on an edge in the ratio of 3-1. and then weighing the resulting points in the ratio 3-1. These are exactly the ratios of Chaikin's curve and so this method can be looked upon as a extension of Chaikin's curve to surfaces.

Generating the Refinement Procedure

To generate the subdivision surface, we consider all 16 of the possible points generated through the binary subdivision of the quadratic patch. It is easily seen that each of these points can be generated through considering other subdivisions of the patch $P(u,v)$ and can be defined by the same subdivision masks

Summary

The extension of Chaikin's Curve to surfaces is quite straightforward. The analysis has produced a simple mask that can be utilized to define the new points on each face (one per vertex). Connecting up these vertices into a new mesh is straightforward.

The interesting extension of this algorithm is when the control point mesh does not have a rectangular topological structure. In this case, we can still utilize the same paradigm and this was accomplished by Donald Doo and Malcolm Sabin in their Doo-Sabin surfaces

Bibliography

1

CHAIKIN, G.
An algorithm for high speed curve generation.
Computer Graphics and Image Processing 3 (1974), 346-349.

2

DOO, D.
A subdivision algorithm for smoothing down irregularly shaped polyhedrons.
In Proced. Int'l Conf. Ineractive Techniques in Computer Aided Design (1978), pp. 157-165.
Bologna, Italy, IEEE Computer Soc.