Graphics Reference
In-Depth Information
Figure 14.9.
Ambiguous cell data.
the curve to use as the next start point. This approach becomes difficult when applied
to surfaces. A more common approach is to determine which collection of tetrahedra
([AllS85], [AllG87], [AllG90], [AllG91]) or cubes ([WyMW86]) covers the surface. One
again finds this collection by marching out from a given start point.
After one has the partition data, one tries to create the faceted approximation to
the surface from it. Unfortunately, this is where one can run into ambiguity problems
in general. The problem is that the cells may not satisfy an important condition,
namely, that the intersection of the object and the cell is simple enough so that one
can establish its topology. One first determines how the object intersects the bound-
ary of the cell and then tries to “fill in” the part of the intersection that lies in the inte-
rior of the cell by some sort of interpolation. Typically, when working with a cell the
only information that one has to determine the intersection are values at the vertices
of the cell that say on which “side” of the object the vertex lies. The “side” is specified
by the sign of the value. This is not always enough to determine the connectivity of
the intersection in the cell interior. Figure 14.9 shows the problem in the case of
curves. The “¥'s” indicate the computed intersection of the curve with the boundary
of the cell, but the given data does not allow one to know how to connect them. There
are three legitimate interpretations.
Ning and Bloomenthal ([NinB93]) divide the methods that have been used to dis-
ambiguate into three types: topology inference, preferred polarity, and cell decompo-
sition. The
topology inference
approach tries to disambiguate with some more data
sampling or interpolation. For example, one could sample the data at the center of
each cell in addition to the values at the corners. The
preferred polarity
approach
tries to disambiguate by adding some rules on how to connect boundary values. For
example, one could specify that “+” corner values should always be separated. This
rule would choose Figure 14.9(b) over 14.9(a). The
cell decomposition
approach pro-
ceeds by subdividing the cell that generated the ambiguity until, hopefully, it disap-
pears. Tetrahedral cells never have any ambiguity, so that one could subdivide any
cubical cell into tetrahedra or one could have started with tetrahedra in the first place.
Unfortunately, tetrahedral subdivisions generate much more data than subdivisions
into cubes. [NinB93] shows that tetrahedral decompositions generate roughly twice
as many triangles in the polygonized surface as would a cubical decomposition. On
the other hand, subdividing a cube into smaller cubes means that one might have
to recursively do this subdivision an arbitrary number of times before the ambiguity
disappears.
The decompositions above do not have to have all the cells of the same size
although this is the most popular choice because it is easiest to implement. There are
