4 1.FastComputationofTight‐FittingOrientedBoundingBoxes
keeps internal features of the model from affecting the resulting OBB orientation.
However, this makes the method superlinear.
The goal of this chapter is to present an alternative algorithm with a simple
implementation that runs in linear time and produces OBBs of high quality. It is
immediately applicable to point clouds, polygon meshes, or polygon soups, with-
out any need for an initial convex hull generation. This makes the algorithm fast
and generally applicable for many types of models used in computer graphics
applications.
1.2Algorithm
The algorithm is based on processing a small constant number of extremal verti-
ces selected from the input models. The selected points are then used to construct
a representative simple shape, which we refer to as the ditetrahedron, from which
a suitable orientation of the box can be derived efficiently. Hence, our heuristic is
called the ditetrahedron OBB algorithm, or DiTO for short. Since the chosen
number of selected extremal vertices affects the running time of the algorithm as
well as the resulting OBB quality, different instances of the algorithm are called
DiTO-k, where k is the number of selected vertices.
The ditetrahedron consists of two irregular tetrahedra connected along a
shared interior side called the base triangle. Thus, it is a polyhedron having six
faces, five vertices, and nine edges. In total, counting also the interior base trian-
gle, there are seven triangles. Note that this shape is not to be confused with the
triangular dipyramid (or bipyramid), which can be regarded as two pyramids with
equal heights and a shared base.
For most input meshes, it is expected that at least one of the seven triangles
of the ditetrahedron will be characteristic of the orientation of a tight-fitting
OBB. Let us consider two simple example meshes—a randomly rotated cube
with 8 vertices and 12 triangles and a randomly rotated star shape with 10 verti-
ces and 16 triangles. For these two shapes, the DiTO algorithm finds the mini-
mum volume OBBs. Ironically, the PCA algorithm computes an excessively
large OBB for the canonical cube example, with a volume approximately two to
four times larger than the minimum volume, depending on the orientation of the
cube mesh. Similarly, it also computes a loose-fitting OBB for the star shape,
with a volume approximately 1.1 to 2.2 times larger than the optimum, depend-
ing on the given orientation of the mesh. In Figure 1.1, these two models are
shown together with their axis-aligned bounding box (AABB), OBB computed
using PCA, and OBB computed using DiTO for a random orientation of the
models.