Next: Recursive Interpolating Subdivision Up: Triangulation of Discrete 3D Surfaces Previous: Surface Representation

Reconstruction of Limit Surface

In order to obtain a smooth triangulation of a discrete 3D surface, its smooth representation, typically of continuity, has to be established. This can be achieved by using a suitable subdivision technique. The subdivision is based on the hierarchical recursive refinement of triangular simplices forming the control grid (Fig. 43). Each step of the refinement consists of two stages - splitting and averaging (Fig. 44). In the splitting stage, new nodes are introduced exactly in the middle of individual edges (on the current level of the refinement). During the averaging, the nodes are repositioned to a new location evaluated as a weighted average of nodes in the neighbourhood (according to the averaging mask). As the level of the refinement grows the resulting grid approaches the so called limit surface the smoothness of which depends on the adopted averaging.

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 as well as refined), the limit surface created by an approximating scheme does not generally interpolate any of the nodes. The averaging scheme may be also classified [69] as uniform (if the same averaging mask is used everywhere on the surface) or non-uniform (if not), and stationary (if for a given node the same averaging mask is used on each level of the subdivision) or non-stationary (if not).

The most simple triangular subdivision scheme is the Loop's scheme, in which the position of surface node of valence is given by


where are the nodes connected to node and


The coefficients and has been carefully chosen so that the Loop's scheme yields a  continuous limit surface [46]. The weights used in the averaging are referred as the averaging mask which is conveniently visualized5 in Figure 45. A repeated subdivision of a star-shaped polyhedron using the Loop's scheme is depicted in Figure 47 that clearly reveals that the Loop's scheme is an approximating scheme with rather poor geometric similarity between the initial control grid and the limit surface. It is therefore desirable to use an interpolating scheme.


... visualized5
Note that only the nominators of the actual weights are shown. The denominator is always taken to be their sum. This ensures that the weights always sum to one, which makes the scheme independent of the coordinate system used. This is known as the affine invariance [73].


Next: Recursive Interpolating Subdivision Up: Triangulation of Discrete 3D Surfaces Previous: Surface Representation

Daniel Rypl