The surface to be discretized is represented by a triangular control grid of arbitrary topology. The boundary edges of the grid form the boundary curves of the surface. The end nodes of each curve represent vertices. Nodes not representing vertices are called curve nodes if they form a curve, otherwise they are called surface nodes.

The limit surface is reconstructed using a subdivision technique. This method is based on hierarchical recursive refinement of triangular simplexes forming the control grid (Fig. 1). The position of a new node is evaluated as a weighted average of nodes in the neighbourhood. As the level of the refinement grows the resulting grid approaches the limit surface. The averaging scheme may be either interpolating or approximating. While an interpolating scheme produces limit surface which is passing through the nodes of the control grid (original and refined), the limit surface created by an approximating scheme does not generally interpolate any of the nodes.

In the presented approach, the interpolating subdivision based on the modified Butterfly scheme [2] has been employed. In this scheme, the position of a new node is calculated as

where stands for positional vector and are nodes connected to surface node of valence . The weights and corresponding to the surface averaging mask (Fig. 2a) are given by

(2) |

(3) |

(4) |

(5) |

The modified Butterfly scheme exhibits the following advantages:

- locality - uses only one-level neighbourhood,
- generality - works with any topology,
- smoothness - yields limit surfaces (even in a topologically irregular setting),
- simplicity - ensures easy evaluation.

Similarly, the limit boundary curves are recovered using a one-dimensional interpolating subdivision [1] producing curves. The adopted 4-point and 3-point averaging masks are depicted in Figures 2b and 2c.

The final interpolating procedure evaluates the position of a new node according to the classification and regularity of the end nodes of its parent edge (a surface node of valence 6 is called regular, otherwise it is called irregular):

- for every surface edge bounded by an irregular surface node and a regular surface node, compute the mid-node position using the surface averaging mask with respect to the irregular surface node,
- for every surface edge bounded by two irregular or regular surface nodes, compute the mid-node position using the surface averaging mask with respect to both end nodes and take the average,
- for every surface edge bounded by a surface node and a non-surface node, compute the mid-node position using the surface averaging mask with respect to the surface node,
- for every surface edge bounded by two non-surface nodes, compute the mid-node position as the average of positions of the end nodes,
- for every curve edge bounded by two curve nodes, compute the mid-node position using the 4-point curve averaging mask,
- for every curve edge bounded by a curve node and a vertex node, compute the mid-node position using the 3-point curve averaging mask,
- for every curve edge bounded by two vertex nodes, compute the mid-node position as the average of positions of these vertices.

The properties of the limit curves and surfaces have been derived by a standard examination of the eigenstructure of the local subdivision matrix corresponding to the adopted interpolating scheme [3]. Generally, evaluation mask for tangent vector at a curve node is related to the left eigenvector corresponding to the second largest eigenvalue of local subdivision matrix of the 4-point curve averaging scheme. Similarly, evaluation masks for two different tangent vectors at a surface node are associated with the two left eigenvectors corresponding to the second largest eigenvalue of local subdivision matrix of the surface averaging scheme. Since the calculation of these masks is rather expensive (standard eigenvalue problem with unsymmetric and positively semidefinite matrix has to be solved), all the masks have been precomputed for different values of nodal valence.

*Daniel Rypl
2005-12-03*