Recursive Interpolating Subdivision

The first smooth interpolating scheme was introduced in [20] which is known as the butterfly scheme. Like all interpolating schemes, each step of the butterfly subdivision scheme leaves the existing nodes unmoved and uses the local averaging (Fig. 46) to compute the position of midside nodes introduced during the splitting. However, the butterfly scheme exhibits degeneracies when applied to grids of arbitrary topology, which makes its use quite limited. Therefore, in the presented approach, the recursive subdivision based on the modified butterfly scheme [72] is employed. This is the interpolating non-uniform stationary scheme, in which the position of existing nodes (on the current level of the subdivision) remains unchanged and the position of a new node on the next level (Fig. 48) is calculated as

where are nodes connected to the surface node of valence . The weights and corresponding to the surface averaging mask (Fig. 48) are given by

The application of the modified butterfly scheme to a star-shaped polyhedron is presented in Figure 50. The geometric similarity of the refined grid with the initial control grid is maintained through the whole process of the subdivision up to the limit surface.

The modified butterfly scheme exhibits favourable properties which make the scheme very powerful and which can be identified as:

- generality - it works with the control grid of any nodal topology,
- smoothness - it yields the continuous limit surface,
- locality - it uses only the one-level neighbourhood and
- simplicity - it ensures easy and efficient evaluation.

Similarly, the limit boundary curves are recovered using
a one-dimensional interpolating subdivision [10] producing
continuous curves. The adopted 4-point (for a new node between two curve nodes)
and 3-point (for a new node between vertex node and curve node)
averaging masks are depicted in Figures 49a and 49b.

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:

- the position of the midnode on a surface edge, bounded by an irregular surface node and a regular surface node, is computed using the surface averaging mask with respect to the irregular surface node,
- the position of the midnode on a surface edge, bounded by two irregular or regular surface nodes, is taken as the average of positions computed using the surface averaging mask with respect to both end nodes,
- the position of the midnode on a surface edge, bounded by a surface node and a non-surface node, is evaluated using the surface averaging mask with respect to the surface node,
- the position of the midnode on a surface edge, bounded by two non-surface nodes, is taken as the average of positions of the end nodes,
- the position of the midnode on a curve edge, bounded by two curve nodes, is computed using the 4-point curve averaging mask,
- the position of the midnode on a curve edge, bounded by a curve node and a vertex node, is evaluated using the 3-point curve averaging mask,
- the position of the midnode on a curve edge, bounded by two vertex nodes, is taken as the average of positions of these vertices.

*Daniel Rypl
2005-12-07*