
13.2 Boxes 619
If U
i
are unit-length eigenvectors, the extents e
i
along those axes are computed from
the extreme values of the projections of the points onto those axes:
a
i
= min
0≤j<n
4
U
i
.
(V
j
− C)
5
, b
i
= max
0≤j<n
4
U
i
.
(V
j
− C)
5
, e
i
= max{|a
i
|, |b
i
|}
This box does not necessarily have the smallest volume of all boxes with the same axis
directions. For a tighter fit, adjust the center of the box and choose the extents, as
shown,tobe
C
= C +
1
2
2
i=0
(a
i
+ b
i
)U
i
, e
i
= (b
i
− a
i
)/2
The pseudocode is
Box3 box; // center, axis[3], extent[3]
// Compute mean of points.
Vector3 sum = P[0];
for(i=1;i<n;i++)
{
sum += P[i];
}
box.center = sum/n;
// Compute covariances of points.
Matrix3