Reconstruction of Limit Surface

The smooth surface over the original STL triangulation is reconstructed using a suitable subdivision technique which is based on the hierarchical recursive refinement of triangular simplices forming the STL mesh (Figure 6). Each step of the refinement consists of two stages -- splitting and averaging (Figure 7). In the splitting stage, new bg nodes are introduced exactly in the middle of individual bg edges. During the averaging, the bg nodes are repositioned to a new location evaluated as a weighted average of bg nodes in the neighbourhood (according to the so called averaging mask). As the level of the refinement grows, the resulting grid approaches the so called limit surface. The averaging scheme may be either interpolating or approximating. While an interpolating scheme produces the limit surface which is passing through the bg nodes of the control background grid (original and refined), the limit surface created by an approximating scheme does not generally interpolate any of the bg nodes. The other classification [2] of the averaging scheme may be uniform (if the same averaging mask is used everywhere on the surface) or non-uniform (if not), and stationary (if for a given bg node the same averaging mask is used on each level of the refinement) or non-stationary (if not).

In the presented implementation, the recursive subdivision based on the modified Butterfly scheme [3] has been employed. It is the interpolating non-uniform stationary scheme, in which the existing bg nodes (on the current level of refinement) remain unchanged and the position of a new bg node on the next level (Figure 8a) is calculated as

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

The modified Butterfly scheme exhibits favourable properties:

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

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

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

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

An example of the application of the modified Butterfly scheme to a simple domain is depicted in Figure 9. The control grid is derived from 24 triangular facets covering a regular 12-sided polygon by shifting two interior nodes (opposite with respect to the polygon center) out of the plane of the polygon (each one in the other direction).

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 [5]. 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 bg node of the control grid. These tangent vectors are then in turn used for the evaluation of limit surface normal.

An important aspect is that the above 7 rules for the evaluation of the limit position of new bg 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 bg edge bounded by non-surface bg nodes was found too restrictive (rigid) and was replaced by the following rule:

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

The effect of the proposed modification, namely the rule I, is demonstrated on a bended surface. The original STL geometry with a close-up frame is depicted in Figure 10a. The close-up detail of the shaded limit surface obtained with the original and modified subdivision scheme is drawn in Figures 10b and 10c, respectively. The effect of rule II is visualized on a simple surface shown in Figure 11a. The shaded limit surface generated with the original and modified strategy together with the contours of the original STL geometry is presented in Figures 11b and 11c, respectively. The effect of the adopted modifications is apparent in both cases.

It can be concluded that the modifications are beneficial for surfaces with curvature in both directions. The regularization effect can be also observed on surfaces with the curvature only in one (principal) direction (such as cylindrical or conical surfaces). In this case, rule II is applied because STL representation of such a surface is accomplished by triangles spanning the whole dimension of the surface in the direction of no curvature. However, neither the original nor the modified scheme is capable to recover the original surface, as it is demonstrated on the example of cylindrical surface in Figure 12a. The modified approach in this case produces a smooth surface without distinct contours of bg faces of the original STL representation (clearly vissible in Figure 12b generated with the original scheme), but with significant slimming in the central part of the surface (Figure 12c). This phenomenon can be eliminated by the enhancement of the STL mesh of the surface in terms of representing it by two rows of bg faces in the direction of no curvature as it is illustrated in Figure 13. Note however that such an enrichment can make the extraction of the boundary representation even more complicated.

*Daniel Rypl
2005-11-05*