Graphics Reference
In-Depth Information
The minimum-area bounding rectangle of a convex polygon can also be computed
in
O
(
n
log
n
) time, using the method of
rotating calipers
[Toussaint83]. The rotating
calipers algorithm starts out bounding the polygon by four lines through extreme
points of the polygon such that the lines determine a rectangle. At least one line is
chosen to be coincident with an edge of the polygon. For each iteration of the algo-
rithm, the lines are simultaneously rotated clockwise about their supporting points
until a line coincides with an edge of the polygon. The lines now form a new bound-
ing rectangle around the polygon. The process is repeated until the lines have been
rotated by an angle of 90 degrees from their original orientation. The minimum-area
bounding rectangle corresponds to the smallest-area rectangle determined by the
lines over all iterations. The time complexity of the algorithm is bounded by the cost
of computing the convex hull. If the convex hull is already available, the rotating
calipers algorithm is
O
(
n
).
4.4.5
Brute-force OBB Fitting
The last approach to OBB fitting considered here is simply to compute the OBB in
a brute-force manner. One way to perform brute-force fitting is to parameterize
the orientation of the OBB in some manner. The space of orientations is sampled
at regular intervals over the parameterization and the best OBB over all sampled
rotations is kept. The OBB orientation is then refined by sampling the interval in
which the best OBB was found at a higher subinterval resolution. This hill-climbing
approach is repeated with smaller and smaller interval resolutions until there is little
or no change in orientation for the best OBB.
For each tested coordinate system, computing the candidate OBB requires the
transformation of all vertices into the coordinate system. Because this transformation
is expensive, the search should exit as soon as the candidate OBB becomes worse
than the currently best OBB. In that it is cheap to compute and has a relatively good
fit, a PCA-fitted OBB provides a good initial guess, increasing the chances of an early
out during point transformation [Miettinen02a]. To further increase the chance of an
early out, the (up to) six extreme points determining the previous OBB should be the
first vertices transformed. In [Miettinen02b] it is reported that over 90% of the tests
are early-exited using this optimization. Brute-force fitting of OBBs generally results
in much tighter OBBs than those obtained through PCA-based fitting.
The hill-climbing approach just described considers many sample points in the
space of orientation before updating the currently best OBB. The optimization-based
OBB-fitting method described in [Lahanas00] hill climbs the search space one sample
at a time, but employs a multisample technique to aid the optimizer escape from local
minima.
4.5
Sphere-swept Volumes
After spheres and boxes, it is natural to consider cylinders as bounding volumes.
Unfortunately, when the mathematics is worked out it turns out that the overlap test
