Graphics Reference
In-Depth Information
T
Figure 4.13
8-DOP for triangle (3, 1), (5, 4), (1, 5) is {1, 1, 4, −4, 5, 5, 9, 2} for axes (1, 0), (0, 1),
(1, 1), (1, −1).
Note that the
k
-DOP is not just any intersection of slabs, but the tightest slabs that
form the body. For example, the triangle (0, 0), (1, 0), (0, 1) can be expressed as several
slab intersections, but there is only one
k
-DOP describing it. If and only if the slab
planes have a common point with the volume formed by the intersection of the slabs
are the slabs defining a
k
-DOP. This tightness criterion is important, as the overlap
test for
k
-DOPs does not work on the intersection volume but solely on the slab
definitions. Without the given restriction, the overlap test would be quite ineffective.
Compared to oriented bounding boxes, the overlap test for
k
-DOPs is much faster
(about an order of magnitude), even for large-numbered DOPs, thanks to the fixed-
direction planes. In terms of storage, the same amount of memory required for an
OBB roughly corresponds to a 14-DOP.
k
-DOPs have a (probable) tighter fit than
OBBs, certainly as
k
grows and the
k
-DOP resembles the convex hull. For geometry
that does not align well with the axes of the
k
-DOP, OBBs can still be tighter. OBBs
will also perform better in situations of close proximity.
The largest drawback to
k
-DOPs is that even if the volumes are rarely colliding the
k
-DOPs must still be updated, or “tumbled.”As this operation is expensive, whenever
possible the tumbling operation should be avoided. This is usually done by pretesting
the objects using bounding spheres (not performing the
k
-DOP test if the sphere test
fails). In general,
k
-DOPs perform best when there are few dynamic objects being
tested against many static objects (few
k
-DOPs have to update) or when the same
object is involved in several tests (the cost of updating the
k
-DOP is amortized over
the tests).
A slightly different
k
-DOP is examined in [Zachmann00]. Here, the
k
-DOP axes
are selected using a simulated annealing process in which
k
points are randomly
distributed on a unit sphere, with the provision that for each point
P
,
−
P
is also in
the set. A repelling force among points is used as the annealing temperature.
4.6.3
k
-DOP-
k
-DOP Overlap Test
Due to the fixed set of axes being shared among all objects, intersection detection
for
k
-DOPs is similar to and no more difficult than testing two AABBs for overlap.
