Graphics Reference
In-Depth Information
Figure 5.38.
Optimal combinations of adjacency relations.
Figure 5.39.
Another useful adjacency relation.
See [NiBl94] for additional observations. The authors point out that in some situa-
tions, the face-edge-vertex structure shown in Figure 5.39 is one worth considering
because the algorithms used with it are simpler than the corresponding ones one
would use with the related winged-edge representation.
Of course, as our final observation, in general the way one chooses a data struc-
ture for an algorithm is by
first
seeing what operations are needed by the algorithm
and
then
choosing an optimal data structure for these operations. In the discussion
above we evaluated data structures in terms of efficiency with respect to
all
possible
adjacency queries which were possible with a given set of adjacency relations. In a
particular context one may not need to answer all such queries however.
5.8.2
Data Structures for Volume Modeling
Encoding techniques based on tree structures have been used to cut down on
the amount of data one needs when objects are represented by pixels or voxels. The
recursive step in the basic algorithm for the general (n-dimensional) volume case is
the following:
(1) If the volume is empty or completely covered by the object, then no further
subdivision is necessary. Mark the volume as EMPTY or FULL, respectively.
(2) Otherwise, subdivide the volume and recursively repeat these two steps on
each of the subvolumes.
