Graphics Reference
In-Depth Information
For long and thin objects, an OBB axis should be aligned with the direction of the
objects. For a flat object, an OBB axis should be aligned with the normal of the flat
object. These directions correspond to the principal directions of the objects, and the
principal component analysis used in Section 4.3.3 can be used here.
Computing bounding boxes based on covariance of model vertices generally works
satisfactorily for models whose vertices are uniformly distributed over the model
space. Unfortunately, the influence of internal points often bias the covariance and
can make the OBB take on any orientation regardless of the extremal points. For
this reason, all methods for computing bounding volumes based on weighting vertex
positions should ideally be avoided. It is sufficient to note that the defining features
(center, dimensions, and orientation) of a minimum bounding volume are all inde-
pendent of clustering of object vertices. This can easily be seen by considering adding
(or taking away) extra vertices off-center, inside or on the boundary, of a bounding
volume. These actions do not affect the defining features of the volume and therefore
should not affect its calculation. However, adding extra points in this manner changes
the covariance matrix of the points, and consequently any OBB features directly com-
puted from the matrix. The situation can be improved by considering just extremal
points, using only those points on the convex hull of the model. This eliminates the
internal points, which can no longer misalign the OBB. However, even though all
remaining points are extremal the resulting OBB can still be arbitrarily bad due to
point distribution. A clustering of points will still bias an axis toward the cluster. In
other words, using vertices alone simply cannot produce reliable covariance matrices.
A suggested solution is to use a continuous formulation of covariance, computing
the covariance across the entire face of the primitives [Gottschalk00]. The convex hull
should still be used for the calculation. If not, small outlying geometry would extend
the bounding box, but not contribute enough significance to align the box properly.
In addition, interior geometry would still bias the covariance. If the convex hull is
already available, this algorithm is O ( n ). If the convex hull must be computed, it is
O ( n log n ).
Given n triangles p k , q k , r k ,0
k
<
n , in the convex hull, the covariance matrix
is given by
12 9 m k , i m k , j
r k , i r k , j
1
a H
a k
C ij
=
+
p k , i p k , j
+
q k , i q k , j
+
m H , i m H , j ,
0
k
<
n
q k
p k
r k
p k /2 is the area and m k
p k
r k 3isthe
where a k
=
×
=
+
q k
+
centroid of triangle k .
The total area of the convex hull is given by
a H =
a k ,
0
k
<
n
Search WWH ::




Custom Search