Graphics Reference
In-Depth Information
and the centroid of the convex hull,
1
a
H
m
H
=
a
k
m
k
,
0
≤
k
<
n
is computed as the mean of the triangle centroids weighted by their area. The
i
and
j
subscripts indicate which coordinate component is taken (that is,
x
,
y
,or
z
). Code
for this calculation can be found in the publicly available collision detection package
RAPID. A slightly different formulation of this covariance matrix is given in [Eberly01],
and code is available on the companion CD-ROM for this topic.
The method just described treats the polyhedron as a hollow body, computing the
covariance matrix from the surface areas. A related method treating the polyhedron
as a solid body is described in [Mirtich96a]. Given an assumed uniform density poly-
hedron, Mirtich's polyhedral mass property algorithm integrates over the volume of
the polyhedron, computing its 3
3 inertia tensor (also known as the inertia or mass
matrix). The eigenvectors of this symmetric matrix are called the principal axes of
inertia, and the eigenvalues the principal moments of inertia. Just as with the covari-
ance matrices before, the Jacobi method can be used to extract these axes, which in
turn can then serve as the orientation matrix of an OBB. Detailed pseudocode for
computing the inertia matrix is given in Mirtich's article. A public domain implemen-
tation in C is also available for download on the Internet. Mirtich's article is revisited
in [Eberly03], in which a more computationally efficient approach is derived and for
which pseudocode is provided.
Note that neither covariance-aligned nor inertia-aligned oriented bounding boxes
are optimal. Consider an object
A
and its associated OBB
B
. Let
A
be expanded by
adding some geometry to it, but staying within the bounds of
B
. For both methods,
this would in general result in a different OBB
B
for the new object
A
. By construction,
B
and
B
both cover the two objects
A
and
A
. However, as the dimensions of the two
OBBs are in the general case different, one OBB must be suboptimal.
×
4.4.4
Optimizing PCA-based OBBs
As covariance-aligned OBBs are not optimal, it is reasonable to suspect they could
be improved through slight modification. For instance, perhaps the OBB could
be rotated about one of its axes to find the orientation for which its volume is
smallest. One improved approach to OBB fitting is to align the box along just
one principal component. The remaining two directions are determined from the
computed minimum-area bounding rectangle of the projection of all vertices onto
the perpendicular plane to the selected axis. Effectively, this method determines
the best rotation about the given axis for producing the smallest-volume OBB.
