Graphics Reference
In-Depth Information
During bottom-up construction an alternative to the rather costly operation of fitting
the bounding volume directly to the data is to merge the child volumes themselves
into a new bounding volume. This section presents such merging operations for
AABBs, spheres, OBBs, and
k
-DOPs.
6.5.1
Merging Two AABBs
Computing the enclosing AABB for two given AABBs is trivial: the sides of the encom-
passing AABB are selected to coincide with the minimum and maximum sides of the
two given volumes. For instance, for the min-max AABB representation, the enclosing
AABB is computed by the following code.
// Computes the AABB a of AABBs a0 and a1
void AABBEnclosingAABBs(AABB &a, AABB a0, AABB a1)
{
for(inti=0;i
<
2; i++) {
a.min[i] = Min(a0.min[i], a1.min[i]);
a.max[i] = Max(a0.max[i], a1.max[i]);
}
}
Other AABB representations result in equally trivial implementations.
6.5.2
Merging Two Spheres
To compute the minimum sphere bounding two other spheres, the calculation is
best split into two cases: where either sphere is fully enclosed by the other and
where they are either partially overlapping or disjoint. To distinguish between the
two cases, let the two spheres be
S
0
and
S
1
, with centers
C
0
and
C
1
and radii
r
0
and
r
1
, respectively (Figure 6.5). Let
d
=
C
1
−
C
0
be the distance between
C
0
and
C
1
.
Then, if
d
, one sphere is fully inside the other. A simple geometric argument
shows why this is so. Start with both spheres centered in the same location. Now
d
|
r
1
−
r
0
| ≥
. However, clearly this
is also the maximum distance by which the sphere centers can be separated (and
d
increased) before the inner sphere penetrates out through the surface of the outer
sphere, and the result follows.
In the first case, in which one sphere is inside the other, no new sphere has to
be calculated and the larger sphere can simply be returned. This avoids an expensive
square root operation. For the second case, in which the spheres are either partially
overlapping or are disjoint, the radius
r
of the new sphere is half the maximum
=
0, and the distance between the sphere surfaces is
|
r
1
−
r
0
|
