Graphics Reference
In-Depth Information
the sphere (illustrated in Figure 8.7c by the triangle formed by
A
,
B
, and
C
). The result-
ing volume is then separated into five disjoint parts through four planes interior to
the sphere (illustrated by
D
,
E
, and
F
). One region corresponds to a solid tetrahe-
dron interior to the sphere. The remaining four regions (three in the 2D illustration)
are recursively subjected to the same separating procedure until all faces have been
processed. The resulting tree can be seen as providing a sequence of approximations
of the sphere through successive refinement, becoming more and more accurate with
each additional level of the tree. There are strong similarities between this approach
and the Dobkin-Kirkpatrick hierarchy described in Chapter 9.
Generalizing Naylor's approach to a full scene implies that an efficient way of
dealing with highly detailed objects within a scene is to provide bounding volume
approximations of the objects and autopartition through the faces of the bounding
volumes before performing any splitting involving the geometry within the bounding
volumes. Alternative candidate dividing planes — not autopartitioning — can be
made to include, for example:
Planes in a few predetermined directions (such as aligned with the coordinate
axes) going through a polygon vertex.
●
Planes in predetermined directions evenly distributed across the extents of the
input geometry (forming a grid across the geometry).
●
Planes through an edge of one polygon and a vertex of another.
●
Rather than relying exclusively on automatic selection of dividing planes, manu-
ally placed
hinting planes
can be used to guide the plane selection. These correspond
to specially marked polygons that are not output as geometry but serve only
to define planes considered dividing planes. Possible strategies for hint planes
include:
If a hint plane is present, pick a hint plane before anything else.
●
Allow picking of any plane, with the caveat that a hint plane is not allowed to
be split by a non-hint plane.
●
As an example, a good use of hint planes could be placing them aligned with the
floors of a multi-story building. Such hint planes would quickly localize the proper
floor within which search could then continue.
Finally, arbitrary planes can also be selected through a simple hill-climbing
approach. That is, after an initial dividing plane has been found (through what-
ever means), a small neighborhood of similar planes obtained from slight offsetting
and tilting is evaluated. If a better dividing plane is found, the new plane is kept and
the hill climbing is repeated until a (local) maximum is found or a specified time limit
is exceeded.
