Graphics Reference
In-Depth Information
dop8.min[0] = dop8.min[1] = dop8.min[2] = dop8.min[3] = FLT_MAX;
dop8.max[0] = dop8.max[1] = dop8.max[2] = dop8.max[3] = -FLT_MAX;
// For each point, update 8-DOP bounds if necessary
float value;
for(inti=0;i<numPts; i++) {
// Axis 0 = (1,1,1)
value = v[i].x + v[i].y + v[i].z;
if (value < dop8.min[0]) dop8.min[0] = value;
else if (value > dop8.max[0]) dop8.max[0] = value;
// Axis 1 = (1,1,-1)
value = v[i].x + v[i].y - v[i].z;
if (value < dop8.min[1]) dop8.min[1] = value;
else if (value > dop8.max[1]) dop8.max[1] = value;
// Axis 2 = (1,-1,1)
value = v[i].x - v[i].y + v[i].z;
if (value < dop8.min[2]) dop8.min[2] = value;
else if (value > dop8.max[2]) dop8.max[2] = value;
// Axis 3 = (-1,1,1)
value = -v[i].x + v[i].y + v[i].z;
if (value < dop8.min[3]) dop8.min[3] = value;
else if (value > dop8.max[3]) dop8.max[3] = value;
}
}
Although
k
-DOPs are invariant under translation, a rotation leaves the volume
unaligned with the predefined axes. As with AABBs,
k
-DOPs must therefore be
realigned whenever the volume rotates. A simple solution is to recompute the
k
-DOP
from scratch, as described. However, because recomputing the
k
-DOP involves trans-
forming the object vertices into the new space this becomes expensive when the
number of object vertices is large. A more effective realignment approach is to use a
hill-climbing method similar to that described in Section 4.2.5 for computing AABBs.
The only difference is that instead of keeping track of six references to vertices of the
convex hull the hill climber would for a
k
-DOP now keep track of
k
vertex references,
one for each facial direction of the
k
-DOP. If frame-to-frame coherency is high and
objects rotate by small amounts between frames, tracking vertices is a good approach.
However, the worst-case complexity of this method is
O
(
n
2
) and it can perform poorly
when coherency is low. Hill climbing results in a tight bounding volume.
Another, approximative, approach is based on computing and storing the vertices
of each
k
-DOP for its initial local orientation at preprocess time. Then at runtime
