Graphics Reference
In-Depth Information
This approach was suggested in [Barequet96], in which three different methods were
investigated.
All-principal-components box
●
Max-principal-component box
●
Min-principal-component box
●
The all-principal-components box uses all three principal components to align
the OBB, and is equivalent to the method presented in the previous section. For
the max-principal-component box, the eigenvector corresponding to the largest
eigenvalue is selected as the length of the OBB. Then all points are projected onto
a plane perpendicular to that direction. The projection is followed by computing
the minimum-area bounding rectangle of the projected points, determining the
remaining two directions of the OBB. Finally, the min-principal-component box
selects the shortest principal component as the initial direction of the OBB, and
then proceeds as in the previous method. Based on empirical results, [Barequet96]
conclude that the min-principal-component method performs best. A compelling
reason max-principal-component does not do better is also given: as the max-
imum principal component is the direction with the maximum variance, it will
contribute the longest possible edge and is therefore likely to produce a larger
volume.
A local minimum volume can be reached by iterating this method on a given
starting OBB. The procedure would project all vertices onto the plane perpendicular
to one of the directions of the OBB, updating the OBB to align with the minimum-
area bounding rectangle of the projection. The iterations would be repeated until no
projection (along any direction of the OBB) gives an improvement, at which point
the local minimum has been found. This method serves as an excellent optimization
of boxes computed through other methods, such as Mirtich's, when performed as a
preprocessing step.
Remaining is the problem of computing the minimum-area bounding rectan-
gle of a set of points in the plane. The key insight here is a result from the field
of computational geometry. It states that a minimum-area bounding rectangle of
a convex polygon has (at least) one side collinear with an edge of the polygon
[Freeman75].
Therefore, the minimum rectangle can trivially be computed by a simple algorithm.
First, the convex hull of the point set is computed, resulting in a convex polygon.
Then, an edge at a time of the polygon is considered as one direction of the bound-
ing box. The perpendicular to this direction is obtained, and all polygon vertices are
projected onto these two axes and the rectangle area is computed. When all poly-
gon edges have been tested, the edge (and its perpendicular) giving the smallest
area determines the directions of the minimum-area bounding rectangle. For each
edge considered, the rectangle area is computed in
O
(
n
) time, for a total complexity
