Graphics Reference
In-Depth Information
These failure conditions can also be treated as stopping criteria. Before stopping,
however, it is reasonable to try other partitioning criteria. For instance — for a box-
based tree — after failing to split along the longest side, first the next longest side and
then the shortest side can be tested. Only if all three fail would splitting stop. Stopping
early with
k
rather than just one primitive per leaf node has the benefit of using less
memory. Unfortunately, during leaf-leaf tests instead of a single primitive-primitive
test now
O
(
k
2
) tests must be performed.
The choice of a partitioning plane is usually further broken down in two steps.
First an axis is selected, and then a position along this axis. These choices are
covered next.
6.2.1.2 Choice of Partitioning Axis
Out of an infinite number of possible axes, somehow a single axis must be selected
as the partitioning axis. Theoretically, it is possible to apply an iterative optimization
method (for example, hill climbing) to locate the best possible axis. Practically, such
an approach is usually too expensive even for a preprocessing step. Consequently, the
search must be limited to a small number of axes from which the best one is picked.
Common choices of axes for inclusion in this limited set are:
1.
Local
x, y,
and
z
coordinate axes.
These are usually included as they are easy to
perform operations with. They also form an orthogonal set, guaranteed to cover
widely different directions.
2.
Axes from the intended aligned bounding volume.
The local axes of item 1 correspond
to the face normals of an AABB. Some bounding volumes, such as
k
-DOPs, have
additional fixed axes that also form a natural choice for partitioning axes.
3.
Axes of the parent bounding volume.
If the hierarchy is built of OBBs, the defining axes
of the bounding OBB of the current set under partitioning are good candidate axes.
Even if the hierarchy is built from, say, spheres (which do not have any apparent
associated axes), a temporary OBB could still be computed for the parent's data
set, from which splitting axes candidates would be extracted.
4.
Axis through the twomost distant points.
Partitioning along the axis that goes through
the two most distant points in the input set corresponds to an attempt at minimiz-
ing the volume of the child volumes. A near-optimal approximation to the most
distant points is given by the simple
O
(
n
) heuristic implemented as the function
MostSeparatedPointsOnAABB()
in Section 4.3.2.
5.
Axis along which variance is greatest.
Splitting along the dimension in which the
input data has the largest spread also serves to minimize the volume of the child
volumes. In an OBB hierarchy in which OBBs are covariance fitted, the axis of
largest variance simply corresponds to the axis defining the longest side of the
parent OBB.
