Graphics Reference
In-Depth Information
The test simply checks the
k
/2 intervals for overlap. If any pair of intervals do not
overlap, the
k
-DOPs do not intersect. Only if all pairs of intervals are overlapping are
the
k
-DOPs intersecting.
int TestKDOPKDOP(KDOP &a, KDOP &b, int k)
{
// Check if any intervals are non-overlapping, return if so
for(inti=0;i<k/2;i++)
if (a.min[i] > b.max[i] || a.max[i] < b.min[i])
return 0;
// All intervals are overlapping, so k-DOPs must intersect
return 1;
}
As with oriented bounding boxes, the order in which axes are tested is likely to
have an effect on performance. As intervals along “near”directions are likely to have
similar overlap status, consecutive interval tests preferably should be performed on
largely different (perpendicular) directions. One way to achieve this is to preprocess
the order of the global axes using a simple greedy algorithm. Starting with any axis
to test first, it would order all axes so that the successor to the current axis is the one
whose dot product with the current axis is as close to zero as possible.
4.6.4
Computing and Realigning
k
-DOPs
Computing the
k
-DOP for an object can be seen as a generalization of the method
for computing an AABB, much as the overlap test for two
k
-DOPs is really a general-
ization of the AABB-AABB overlap test. As such, a
k
-DOP is simply computed from
the projection spread of the object vertices along the defining axes of the
k
-DOP.
Compared to the AABB calculation, the only differences are that the vertices have to
be projected onto the axes and there are more axes to consider. The restriction to keep
axis components in the set
makes a hardcoded function for computing the
k
-DOP less expensive than a general function for arbitrary directions, as the projec-
tion of vertices onto these axes now involves at most three additions. For example,
an 8-DOP is computed as follows:
{−
1, 0, 1
}
// Compute 8-DOP for object vertices v[] in world space
// using the axes (1,1,1), (1,1,-1), (1,-1,1) and (-1,1,1)
void ComputeDOP8(Point v[], int numPts, DOP8 &dop8)
{
// Initialize 8-DOP to an empty volume
