3
1
FastComputationofTight‐Fitting
OrientedBoundingBoxes
Thomas Larsson
Linus Källberg
Mälardalen University, Sweden
1.1Introduction
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.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.
1.2Algorithm 5
Figure 1.1. Computed boxes for a simple cube mesh (12 triangles) and star mesh (16
triangles). The first column shows the AABB, the second column shows the OBB com-
puted by PCA, and the last column shows the OBB computed by DiTO. The meshes were
randomly rotated before the computation.
The OBB is represented here by three orthonormal vectors u, v, and w defin-
ing the orientation of the box’s axes, the half-extents
u
h
,
v
h
, and
w
h
defining the
size of the box, and a midpoint
m defining the center of the box. In the following,
we explain how the algorithm works, and we present our experimental evalua-
tion.
SelectingtheExtremalPoints
Call the set containing the n vertices of the input model P. The algorithm starts
off by selecting a subset S with k representative extremal points from the vertices
P, where k is an even number. This is done by finding the vertices with minimum
and maximum projection values along
2
s
k
predefined directions or normal
vectors. The points in S are stored systematically so that any extremal point pair
,
j
j
ab
along a direction
j
n
can be retrieved, where
j
a
and
j
b
are the points with
minimum and maximum projection values, respectively. Note that all the points
in S are guaranteed to be located on the convex hull of the input mesh. Hopefully,
this makes them important for the later determination of the OBB axes. Ideally,
the used normal vectors should be uniformly distributed in direction space. How-
ever, to be able to optimize the projection calculations that are calculated by sim-
6 1.FastComputationofTight‐FittingOrientedBoundingBoxes
ple dot products, normals with many 0s and 1s may be preferable, given that they
sample the direction space in a reasonable manner.
Clearly, the DiTO-k algorithm relies on the choice of an appropriate normal
set
s
N
, and simply by choosing a different normal set a new instance of DiTO-k
is created. In the experiments described later, five normal sets are used, yielding
five algorithm instances. The normal sets are listed in Table 1.1. The normals in
6
N
, used in DiTO-12, are obtained from the vertices of a regular icosahedron
with the mirror vertices removed. Similarly, the normals in
10
N
, used in DiTO-20,
are taken from the vertices of a regular dodecahedron. The normal set
16 6 10
NNN
is used in DiTO-32. The normals in
7
N
and
13
N
, used in DiTO-14
and DiTO-26, are not uniformly distributed, but they are still usually regarded as
good choices for computing k-DOPs [Ericson 2005]. Therefore, they are also ex-
pected to work well in this case.
6
N
10
N
7
N
13
N
0,1, a
0, ,1aa
1, 0, 0
1, 0, 0
0,1, a
0, , 1aa
0,1, 0
0,1, 0
1, , 0a
,1 ,0aa
0,0,1
0,0,1
1, , 0a
,1 ,0aa
1, 1,1
1, 1,1
,0,1a
1,0,aa
1,1, 1
1,1, 1
,0, 1a
1,0,aa
1, 1,1
1, 1,1
1, 1,1
1, 1, 1
1, 1, 1
1,1, 1
1,1, 0
1, 1,1
1, 1, 0
1, 1, 1
1, 0,1
1, 0, 1
0,1,1
0,1, 1
Table 1.1. Efficient normal sets
6
N
,
10
N
,
7
N
, and
13
N
used for DiTO-12, DiTO-20, Di-
TO-14, and DiTO-26, respectively, with the value
5 1 2 0.61803399a
. The
normals in
6
N
and
10
N
are uniformly distributed.
1.2Algorithm 7
FindingtheAxesoftheOBB
To determine the orientation of the OBB, candidate axes are generated, and the
best axes found are kept. To measure the quality of an orientation, an OBB cov-
ering the subset S is computed. In this way, the quality of an orientation is deter-
mined in
Ok time, where
kn
for complex models. For very simple models,
however, when
n
k
, the candidate OBBs are of course computed using the en-
tire point set P. To measure the quality, the surface areas of the boxes are used,
rather than their volumes. This effectively avoids the case of comparing boxes
with zero volumes covering completely flat geometry. Furthermore, it makes
sense to reduce the surface area as much as possible for applications such as ray
casting. Of course, if preferred, a quality criterion based on the volume can be
used in the algorithm instead.
The best axes found are initialized to the standard axis-aligned base, and the
best surface area is initialized to the surface area of the AABB covering P. Then
the algorithm proceeds by calculating what we call the large base triangle. The
first edge of this triangle is given by the point pair with the furthest distance
among the s point pairs in S, that is, the point pair that satisfies
m
ax
jj
ab
.
Call these points
0
p
and
1
p
. Then a third point
2
p
is selected from S that lies fur-
thest away from the infinite line through
0
p
and
1
p
. An example of a constructed
large base triangle is shown on the left in Figure 1.2.
The base triangle is then used to generate three different candidate orienta-
tions, one for each edge of the triangle. Let n be the normal of the triangle, and
010
e
pp be the first edge. The axes are then chosen as
000
1
201
,
,
.
u
ee
u
nn
u
uu
The axes are chosen similarly for the other two edges of the triangle. For each
computed set of axes, an approximation of the size of the resulting OBB is com-
puted by projecting the points in S on the axes, and the best axes found are kept.
In Figure 1.3, an example of the three considered OBBs for the base triangle is
shown.
Next, the algorithm proceeds by constructing the ditetrahedron, which con-
sists of two connected tetrahedra sharing the large base triangle. For this, two
additional points
0
q
and
1
q
are computed by searching S for the points furthest
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.