Next: Mesh Generation
Up: Top
Previous: Introduction
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 the hierarchical recursive refinement
of triangular simplexes forming the control grid.
Each step of the refinement consists of two stages  splitting and
averaging (Fig. 1). In the splitting stage, new nodes
are introduced exactly in the middle
of individual edges. During the averaging, the nodes are repositioned
to a new location evaluated as a weighted average
of nodes in the neighbourhood (according to the so called averaging
mask). 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 the 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 recursive
subdivision based on the modified Butterfly scheme [1] has been
employed. It is the interpolating nonuniform stationary scheme, in
which the original nodes remain unchanged and the position of a new
node (see Fig. 2a) is calculated as

(1) 
where
stands for the positional vector and are nodes
connected to the surface node of valence .
The weights and
corresponding to the surface averaging mask (Fig. 2a) are
given by
The modified Butterfly scheme exhibits the following advantages:
 locality  uses only onelevel neighbourhood,
 generality  works with any topology,
 smoothness  yields limit surfaces,
 simplicity  ensures easy evaluation.
Similarly, the limit boundary curves are recovered using
a onedimensional interpolating subdivision [2] producing
curves. The adopted 4point and 3point 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 midnode 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 midnode 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 nonsurface node,
compute the midnode position using the surface averaging mask
with respect to the surface node,
 for every surface edge bounded by two nonsurface nodes, compute
the midnode position as the average of positions of the end
nodes,
 for every curve edge bounded by two curve nodes, compute the
midnode position using the 4point curve averaging mask,
 for every curve edge bounded by a curve node and a vertex node,
compute the midnode position using the 3point curve averaging mask,
 for every curve edge bounded by two vertex nodes, compute
the midnode 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,
the evaluation mask for the tangent vector at a curve node is related to the left
eigenvector corresponding to the second largest eigenvalue of the local
subdivision matrix of the 4point curve averaging scheme. Similarly,
the evaluation masks for two different tangent vectors at a surface node
are associated with the two left eigenvectors corresponding to the
second largest (double) eigenvalue of the local subdivision matrix of the surface
averaging scheme. Since the calculation of these masks is rather
expensive
all the masks have been
precomputed for different values of nodal valence.
Next: Mesh Generation
Up: Top
Previous: Introduction
Daniel Rypl
20051203