Game Engine Gems 2

 3

1

FastComputationofTight‐Fitting

OrientedBoundingBoxes

Thomas Larsson

Linus Källberg

Mälardalen University, Sweden

1.1Introduction

Bounding shapes, or containers, are frequently used to speed up algorithms in

games, computer graphics, and visualization [Ericson 2005]. In particular, the

oriented bounding box (OBB) is an excellent convex enclosing shape since it

provides good approximations of a wide range of geometric objects [Gottschalk

2000]. Furthermore, the OBB has reasonable transformation and storage costs,

and several efficient operations have been presented such as OBB-OBB

[Gottschalk et al. 1996], sphere-OBB [Larsson et al. 2007], ellipsoid-OBB [Lars-

son 2008], and ray-OBB [Ericson 2005] intersection tests. Therefore, OBBs can

potentially speed up operations such as collision detection, path planning, frus-

tum culling, occlusion culling, ray tracing, radiosity, photon mapping, and other

spatial queries.

To leverage the full power of OBBs, however, fast construction methods are

needed. Unfortunately, the exact minimum volume OBB computation algorithm

given by O’Rourke [1985] has





3

On

running time. Therefore, more practical

methods have been presented, for example techniques for computing a





1 ε



-

approximation of the minimum volume box [Barequet and Har-Peled 1999]. An-

other widely adopted technique is to compute OBBs by using principal compo-

nent analysis (PCA) [Gottschalk 2000]. The PCA algorithm runs in linear time,

but unfortunately may produce quite loose-fitting boxes [Dimitrov et al. 2009].

By initially computing the convex hull, better results are expected since this

4 1.FastComputationofTight‐FittingOrientedBoundingBoxes

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.2Algorithm

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.