Smooth Surface Recovery

The 3D 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.

In order to obtain a smooth triangulation (independent of the control grid e.g. due to different element size specifications), a smooth representation of the discrete surface (typically continuity is sufficient), called the limit surface, is derived. The limit surface is reconstructed using a suitable subdivision technique which is based on the hierarchical recursive refinement of triangular simplices 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 smoothness of the limit surface is fully controlled by the adopted averaging mask. 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 non-uniform stationary scheme, in which the existing nodes (on the current level of refinement) remain unchanged and the position of a new node on the next level (see Fig. 2a) is calculated as

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

Similarly, the limit boundary curves are recovered using a one-dimensional interpolating subdivision [2] 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 2b and 2c.

The properties of the limit surface (and curve as well) can been deduced by a standard examination of the eigenstructure of the local subdivision matrix corresponding to the adopted subdivision scheme [3]. This includes especially the derivation of the so called derivatives masks used for the calculation of vectors tangent to the limit surface at the limit position of node of the control grid. These tangent vectors are then in turn used for the evaluation of limit surface normal.

The modified Butterfly scheme exhibits favourable properties: (i) generality - it works with control grid of any topology, (ii) smoothness - it yields continuous limit surface, (iii) locality - it uses only one/two-level neighbourhood (on the given level of the refinement) for the evaluation of the averaging/derivation mask and (iv) simplicity - it ensures easy and efficient evaluation.

The final interpolating procedure evaluates the position of the 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):

1. 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,
2. 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,
3. for every surface edge bounded by a surface node and a non-surface node, compute the midnode position using the surface averaging mask with respect to the surface node,
4. for every surface edge bounded by two non-surface nodes, compute the midnode position as the average of positions of the end nodes,
5. for every curve edge bounded by two curve nodes, compute the midnode position using the 4-point curve averaging mask,
6. for every curve edge bounded by a curve node and a vertex node, compute the midnode position using the 3-point curve averaging mask,
7. for every curve edge bounded by two vertex nodes, compute the midnode position as the average of positions of these vertex nodes.

An important aspect is that the above 7 rules for the evaluation of the limit position of new nodes were derived for more or less isotropic control grids, this means for control grids with elements of approximately unit aspect ratio. However the STL meshes typically consist of elements of very large aspect ratio, which is the consequence of the curvature based tessellation procedure used to generate them. In this context, the 4th rule for the subdivision of surface edge bounded by non-surface nodes was found too restrictive (rigid) and was replaced by the following rule:

4. for every surface edge bounded by two non-surface nodes, find the off-diagonal nodes of the quadrilateral formed by two faces sharing that edge and compute the midnode position
1. according to appropriate from rules 1 - 3 using the temporarily swapped edge, if any of the off-diagonal nodes is a surface node,
2. as the weighted average of positions calculated according to the original rule 4 for the existing (weight 0.75) and temporarily swapped edge (weight 0.25), if both off-diagonal nodes are non-surface nodes.

It should be emphasized that the topological change to the control grid by swapping the edge should be of temporary character only (just for the evaluation of the position of the corresponding midnode). Otherwise the change of connectivity (in the case of STL meshes often regular) induced by the swapping may seriously deteriorate the quality of the recovered limit surface.