Graphics Reference
In-Depth Information
Figure 5.42.
Octree subdivision.
(1) We could specify a cutoff depth below which we do not subdivide, or
(2) rather than requiring that the region either misses or covers a rectangle
completely, we can quit if it “almost” misses or quits, that is, one uses thresh-
olds on the percentage of area covered.
Octrees.
Octrees are the three-dimensional generalization of quadtrees. In the case
of octrees we divide a cube into eight octants. See Figure 5.42. We can then encode
objects with trees where each node has up to eight nonempty subtrees. Octrees are
generated for objects analogous to how quadtrees are generated.
One can show that the number of nodes in a quadtree or octree are typically
proportional to the size of the object's boundary, although it is possible to create
some worse cases. The intuitively obvious reason for that is that the only time one
needs to subdivide is when a cell is crossed by the boundary.
The quadtree and octree representations for objects have many nice properties
and they have been studied extensively in order to store and process them efficiently.
Boolean set operations are relatively easy. One traverses both trees in parallel and
takes the appropriate steps at each corresponding pair of nodes. Algorithms exist for
finding a pixel or voxel or finding neighboring pixels or voxels in the tree. These are
operations that one often needs. Some simple transformations, such as rotations by
90 degrees, scaling by powers of 2, and reflections are easy. Other transformations are
not. Aliasing is a big problem when performing these transformations. For more
details see the references in the spatial data structure section of the bibliography.
5.9
Converting Between Representations
The need for algorithms that convert from one representation to another exists not
only because modelers using different representations may want to exchange geo-
metric data but especially because modelers increasingly seem to maintain multiple
representations internally. By in large, the problem seems to have only been dealt with
in an ad hoc way. We begin by addressing the two classical CSG-to-b-rep and b-rep-
to-CSG problems. We end with some comments about the IGES data exchange
standard between modelers.
The CSG-to-b-rep problem is the boundary evaluation problem in CSG that was
first studied systematically in [ReqV85]. An early algorithm for polyhedral objects can
