An Exact Algorithm for Finding Minimum Oriented Bounding Boxes, Jukka Jylänki, 2015

An Exact Algorithm for Finding Minimum Oriented Bounding Boxes

Jukka Jyl

anki

∗

2015/06/01

Figure 1: Fast computation of the minimum volume OBB of a convex polyhedron. Left to right: Dragon: 2731149 vertices (2531 on the hull)

in 1.3 seconds; Lucy: 14026670 vertices (5262 on the hull) in 5.6 seconds; a bear: 3105537 vertices (6628 on the hull) in 7.3 seconds.

An optimized C++ implementation of the algorithm can be found here, or try it live on a web page here.

Abstract

A new method is presented for computing tight-ﬁtting enclosing

bounding boxes for point sets in three dimensions. The algorithm

is based on enumerating all box orientations that are uniquely de-

termined by combinations of edges in the convex hull of the in-

put point set. By using a graph search technique over the vertex

graph of the hull, the iteration can be done quickly in expected

O(n

3/2

(log n)

) time for input point sets that have a uniform dis-

tribution of directions on their convex hull. Under very speciﬁc

conditions, the algorithm runs in worst case O(n

log n) complex-

ity. Surprisingly, empirical evidence shows that this process always

yields the globally minimum bounding box by volume, which leads

to a conjecture that this method is in fact optimal.

CR Categories: F.2.2 [Analysis of Algorithms and Problem Com-

plexity]: Nonnumerical Algorithms and Problems—Geometrical

Problems and Computations; I.3.5 [Computer Graphics]: Compu-

tational Geometry and Object Modeling—Geometric Algorithms;

Object representations

Keywords: computational geometry, bounding box, OBB

1 Introduction

Given a three-dimensional set of points, a fundamental problem in

computational geometry is to ﬁnd the smallest possible oriented

bounding box (OBB) that contains all the points in the input data

set. This problem arises widely in applications in computer graph-

ics [Schneider and Eberly 2002], physical simulations [Ericson

2004] and spatial data structures [Gottschalk et al. 1996], as well as

other areas, such as computer-aided design [Chan 2003] and even

∗

e-mail:jujjyl@gmail.com

in medicine [Bartz et al. 2005]. Common uses in computer graphics

include approximating a complex shape with a simpler OBB for the

purposes of faster broad phase intersection testing, or for perform-

ing culling of renderable objects that need to be sent to the GPU.

OBBs have several desirable properties that make them useful for a

variety of scenarios. They are convex and consist of three pairs

of parallel planes, called slabs. In their local coordinate frame,

they are representable as axis-aligned bounding boxes (AABB) or if

scaled, as the unit cube. As such, intersection and distance tests be-

tween OBBs and other shapes can be implemented efﬁciently [Kay

and Kajiya 1986] [Schneider and Eberly 2002, pp. 394, 624, 639].

OBBs also provide generally tighter ﬁts than the simpler bound-

ing spheres or AABBs. However, unlike spheres and AABBs, for

which minimum volume enclosing shapes can be found in linear

time [Megiddo 1982] [Welzl 1991], the major shortcoming with

OBBs to date has been the difﬁculty of computing minimum vol-

ume OBB representations due to a lack of effective algorithms for

the task.

In this paper, new analysis and progress is presented to help solve

the minimum volume OBB problem. A new algorithm is intro-

duced, which has considerable practical merit:

1. Exact: The algorithm runs through a discrete process without

use of numerical optimization or iteration over the continuum.

As a result, the method is stable and predictable.

2. Simple: Unlike previously published results, the new method

is relatively easy to implement and it is possible to program

it in different variants to balance a tradeoff between desired

implementation complexity versus runtime complexity.

3. Fast: Both the time complexity and the constant time factors

in the algorithm are low, which make it a practically viable

solution.

4. Enumerative: The new algorithm is implementable as read-

only sequential traversal over sets of edges, so it is catego-

rizable as embarrassingly parallel and therefore suitable for

processing large data sets as well.

5. Optimal? Based on extensive numerical searches over both

synthetic and real world test cases, no example has yet sur-

faced where the new algorithm would not have found the op-

timal minimum volume box. However, at this point, no formal

proof of the optimality of this algorithm is known.

The next section of this paper will ﬁrst introduce the relevant earlier

research. In sections 3 and 4, the main problem will then be grad-

ually unwound in a bottom-up manner by presenting mathematical

analysis of each of the individual subproblems one at a time. These

results will all be brought together in the main algorithm ﬁnally in

section 5. Last, sections 6 and 7 conclude with experimental results

and practical remarks.

2 Related Work

In the past, only few papers have been published with theoretical

advances on the minimum volume OBB problem. In the 2D case,

it is known that the minimum area rectangle enclosing a convex

polygon must be ﬂush with one of the polygon edges [Freeman

and Shapira 1975]. The rotating calipers method [Toussaint

1983] is a linear time algorithm that builds on this characterization.

For the 3D case, the only currently known property is the following:

Theorem 2.1. A box of minimal volume circumscribing a convex

polyhedron must have at least two adjacent faces ﬂush with edges

of the polyhedron. [O’Rourke 1985] 

The term of being ﬂush with an edge here means that a face of

the box contains every point of that edge. Based on this prop-

erty, O’Rourke developed a O(n

) time algorithm which performs

a type of rotating calipers search for each pair of edges on the hull.

However, their method involves solving roots of a sixth degree

trigonometric polynomial numerically, and in addition the com-

plexity is so high that the method is often considered impracti-

cal. Unfortunately it also looks like this work has later become

misinterpreted in literature in several published books, which in

turn has led to misinformation in online sources [GameDev.Net ],

[StackOverﬂow ], [Troutman ]. To illustrate and clear up the con-

fusion, consider the following quotes:

• “O’Rourke (1985) shows that one box face must contain a

polyhedron face and another box face must contain a polyhe-

dron edge or three box faces must each contain a polyhedron

edge.”” [Schneider and Eberly 2002, p. 806]

• “[...] given a polyhedron either one face and one edge or

three edges of the polyhedron will be on different faces of its

bounding box.” [Ericson 2004, p.107]

• “The paper [O’R85] shows that the minimum-volume OBB

for a convex polyhedron must (1) have a face that is coincident

with a face of the polyhedron or (2) be supported by three mu-

tually perpendicular edges of the polyhedron.” [Eberly 2006,

p. 624] (see also [Geometric Tools LLC ])

The ﬁrst quote is possibly correct, however this does not follow

from theorem 2.1 or the treatise in [O’Rourke 1985]. In fact, if it

did, then it would directly prove the optimality of the new algorithm

presented in this paper. The second claim on the other hand is not

correct. Note the very subtle difference between the ﬁrst two quotes

that makes them different. It is possible that two adjacent faces of

a box are ﬂush with the same edge of a polyhedron, in the special

case that this polyhedron edge coincides with an edge of the box.

This counterexample will be called category D, and it will be pre-

sented in more detail later in section 5. See also ﬁgure 2. Finally,

the third statement is likewise a misinterpretation of O’Rourke, and

mathematically incorrect. The correct analysis will be presented in

section 3.5.

Given that the problem has resisted attempts of solving for several

decades, developers have sought to utilize a variety of numerical

and statistical optimization methods to ﬁnd suboptimal but good

enough approximations for practical use. A basic method is to use

principal component analysis (PCA) to estimate the direction of

largest spread in the point set and establish that as a cardinal di-

rection for the OBB. This process must be done using a continuous

set representation on the convex hull, or otherwise the approxima-

tion can be unboundedly bad [Dimitrov et al. 2009]. For obtaining

near-optimal results, there exists a (1 + )-approximation scheme

[Barequet and Har-Peled 2001], whereas for a completely oppo-

site line of approach one can embrace a carefully deﬁned heuristic

to trade optimality for speed [Larsson and K

allberg 2011]. There

have also been attempts at providing optimal results by using so-

phisticated numerical techniques, such as particle swarm optimiza-

tion [Borckmans and Absil 2010] and genetic search [Chang et al.

2011]. These have been proven to be effective, but they have an

element of randomness in them and may not ﬁnd the optimal box

in all cases.

The only brute force approach so far has been the exhaustive search

of all orientations over SO(3, R). This space is large, but there is a

commonly known trick to prune it that seems to be folklore. Given

a candidate orientation for the OBB, a better ﬁt can be searched in-

crementally by repeatedly projecting the model onto a plane corre-

sponding to one of the main axes of the current candidate OBB and

solving the resulting 2D problem in linear time using Toussaint’s ro-

tating calipers method. This reduces the brute force challenge from

SO(3, R) to a search of a good starting direction vector in the unit

(hemi)sphere, which, when iterated in this manner, would ”lock”

into the orientation of the optimal OBB. However the fundamental

problem is still that the search is conducted over a continuous space

and therefore it is not exhaustible by sampling a discrete set of ori-

entations. Because of this, a brute force search over orientation

angles is not able to guarantee an optimal result.

In summary, all known methods so far use either approximation,

numerics or heuristics, which is unsatisfying. There is a clear need

to develop a fast and exact geometric algorithm to solve the prob-

lem, which will be the main motivation in the following sections.

3 Mathematical Aspects

In order to work through the details, some notation and concepts

need to be ﬁrst introduced. Recall that the internal points of the

input set do not play a role in the problem and one can restrict to

considering only the convex hull of the point set. In fact, for the

new algorithm, computing the convex hull is the required ﬁrst step,

since the algorithm is built to operate on the edges of a convex poly-

hedron. The convex hull can be computed in expected O(n log n)

time for example by using the quickhull algorithm [Barber et al.

1996].

For each direction vector n, one or more vertices of the polyhe-

dron can be identiﬁed as the most extreme points to the direction

of n. These are called supporting vertices, and will be denoted by

Supp(n). If for two vertices v

and v

there exists a direction n

such that v

∈ Supp(n) and v

∈ Supp(−n), then v

and v

are

said to be antipodal. Geometrically described, two vertices are an-

tipodal if it is possible to ﬁnd an orientation for an enclosing OBB

such that the two vertices of the hull lie on opposing faces of the

OBB.

In this paper, a new concept is introduced that is in some ways sim-

ilar to antipodality. If for two vertices v

and v

there exists two di-

rections n

and n

such that v

∈ Supp(n

) and v

∈ Supp(n

)

and n

· n

= 0, then v

and v

are said to be sidepodal. The geo-

metric meaning of this is that two vertices are said to be sidepodal

if it is possible to ﬁnd an orientation for an enclosing OBB where

the OBB touches both vertices v

and v

on two adjacent faces of

the OBB.

The concepts of support, antipodality and sidepodality are naturally

extended to also refer to edges (and faces) of the hull. For example,

one may refer to an edge e being sidepodal to a vertex v, if it is

possible to orient an OBB to be ﬂush with e and v on two adjacent

faces of the OBB.

If x is a vertex or an edge of the hull, then the set of all antipodal

vertices in the hull to x will be denoted by Anti

(x) and the set of

all antipodal edges in the hull to x will be denoted by Anti

(x).

Likewise, the sets Side

(x) and Side

(x) will refer to the sets of

all sidepodal vertices and respectively edges to x. Also, it will be

necessary to examine set intersections of these sidepodal sets, so as

a notational aid, Side

, e

) will be used as a shorthand to refer

to the set intersection Side

) ∩ Side

). It is immediately

clear that if edge e : v

→ v

is an antipodal or a sidepodal edge to

a feature x, then both vertices v

and v

of e immediately have the

same property. More precisely:

• If e ∈ Anti

(x), then {v

, v

} ⊆ Anti

(x),

• if e ∈ Side

(x), then {v

, v

} ⊆ Side

(x), and

• if e ∈ Side

, x

), then {v

, v

} ⊆ Side

, x

This may seem trivial, but it is worth explicitly noting since this

makes traversing sidepodal and antipodal edges effectively identi-

cal to traversing the sets of vertices. Note that for the sidepodality

relation, the opposite is not true, i.e. even if two neighboring ver-

tices are sidepodal to a feature x, it does not necessarily follow that

the edge connecting them would be sidepodal to x as well.

The notation N(v) will be used to refer to the set of vertex

neighbors of vertex v. Given an edge e, the angle measured from

inside of the hull between the two adjacent faces connected to e is

commonly called the dihedral angle of edge e. Because the hull

is convex, all dihedral angles are in the range of ]0, 180[ degrees.

Finally, the face normals of the two adjacent faces to e pointing

outwards of the hull will be denoted by f

(e) and f

(e). These

normal vectors deﬁne the following simple property that will be

useful later.

Lemma 3.1. If a face of an OBB is ﬂush with an edge e of the

convex hull, then the (unnormalized) normal vector n of that face

of the OBB is equal to n = f

(e) +



(e) −f

(e)



∗t for some

t ∈ [0, 1].

Proof. This formula for the normal follows directly from linear in-

terpolation. The value of t = 0 corresponds to the case when the

OBB is ﬂush with the face with normal f

(e), and the value of

t = 1 corresponds to the OBB being ﬂush with the face with the

normal f

(e). Since the dihedral angle of the edge is never 0, the

linear interpolation will not produce a degenerate zero vector.

While it would be possible to choose a parametrization based on

angle, or another that would preserve the magnitude of the normal

vector, either would greatly complicate later analysis, which is why

this presentation is preferred instead.

There exists an interesting geometric way to relate sidepodality of

a vertex and an edge to the support function.

Lemma 3.2. Given a vertex v and an edge e on a convex polyhe-

dron, the vertex v ∈ Side

(e) if and only if there exists a direction

vector n for which v ∈ Supp(n) and



n ·f

(e)



n ·f

(e)



≤ 0.

Proof. By lemma 3.1, the normal vector n

of the face of an OBB

that is ﬂush with an edge e has the parametrization n

= f

(e) +



(e)−f

(e)



∗t. The vertex v is sidepodal to edge e if and only

if there exists a direction n such that v ∈ Supp(n) and n ·n

= 0.

Substituting the formula of the normal gives the equation

n ·



(e) +



(e) −f

(e)



∗t



= 0, where t ∈ [0, 1] . (1)

The left-hand side is an expression linear to t, so its extremes are

at t = 0 and t = 1, and they correspond to values n · f

(e) and

n ·f

(e). Therefore according to Bolzano’s theorem, equation (1)

has a solution if and only if one of these values is nonnegative and

the other is nonpositive. In other words, either

1. n · f

(e) ≤ 0 and n ·f

(e) ≥ 0, or

2. n · f

(e) ≥ 0 and n ·f

(e) ≤ 0.

Then, in either case multiplying the two expressions together yields

the desired result.

Antipodality and sidepodality both form symmetric nontransitive

relations for vertices and edges of the hull. The new algorithm will

be based on computationally resolving these relations on the vertex

graph of the convex hull. Therefore the rest of this section will fo-

cus on the mathematical study of these properties which will enable

the development of suitable algorithms to enumerate these sets.

3.1 Antipodal Edge and Vertex

Given an edge e and a vertex v of a convex polyhedron, it is possible

to formulate a precise test whether e and v are antipodal partners to

each other. This involves ﬁnding a common normal vector n for

which e ∈ Supp(n) and v ∈ Supp(−n), or concluding that such

a vector does not exist. The ﬁrst condition is fulﬁlled if and only if

the direction n satisﬁes the parametrization of lemma 3.1, whereas

the second condition is met if and only if all vertex neighbors w of

vertex v are in the negative halfspace of the plane deﬁned by v and

−n. This gives the following set of conditions:

(

n = f

(e) +



(e) − f

(e)



∗ t , where t ∈ [0, 1] ,

(v − w) · n ≤ 0 ∀ w ∈ N(v) .

The set of equations deﬁned on the second line generates a set of

intervals, one for each neighbor in N (v), that the parameter t must

lie in for the solution to be valid. When codiﬁed, it turns into a test

of whether the range intervals have a non-degenerate overlap. This

procedure is shown in algorithm 1.

Algorithm 1: AreAntipodal(v,e)

let t

−

= 0

let t

= 1.0

for w ∈ N(v) do

let p = f

(e) · (w − v)

let q =



(e) − f

(e)



· (w − v)

if q > 0 then

= Min(t

, p/q)

else if q < 0 then

−

= Max(t

−

, p/q)

else if p < 0 then

return false

return t

−

≤ t

3.2 Antipodal Pair of Edges

Testing whether given two edges e

and e

of a convex polyhedron

are antipodal is also straightforward. Geometrically reasoning, it

is immediate that if an OBB is ﬂush with two edges e

and e

opposite faces of the box, then the normal vector n

of one of these

faces is perpendicular to both e

and e

, and therefore the direction

of n

is given by the cross product of the two edge vectors. That is,

= c ∗ e

× e

for some constant c. This direction is uniquely

deﬁned, and to see whether the conﬁguration is physically valid,

it remains only to test whether a box laid out in this orientation

intersects the inside of the polyhedron. A special case occurs when

is parallel to e

, in which case the cross product is degenerate

and the box is free to ”hinge” around in contact with the two edges.

Testing whether intersection occurs can be achieved by using the

parametrization for the normal vectors of the two edges from lemma

3.1, which yields the following group of equations:











= f

) +



) − f

)



∗ t , where t ∈ [0, 1] ,

= f

) +



) − f

)



∗ u , where u ∈ [0, 1] ,

= cn

, where c < 0 .

This leads to a matrix equation of form M x = f

), where

x =



t c cu



and M is represented as column vectors in

the form

M =



) − f

) f

) − f

)



(2)

From here, the valid values for t and u are solved easily by generic

3x3 matrix techniques, and they directly deﬁne one of the face nor-

mal directions for the OBB. This method is presented in algorithm

2, which tests whether two edges are antipodal, and if so, returns

the normal direction for the face of the OBB that is ﬂush with edge

Algorithm 2: AntipodalDir(e

, e

)

compute M according to equation (2)

let (t, c, cu)

= M

−1

)

if c < 0 and t ∈ [0, 1] and u ∈ [0, 1] then

let n = f

) +



) − f

)



∗ t

return n/||n||

else

return null

3.3 Sidepodal Pair of Edges

In a similar fashion, it can be analysed whether a pair of edges are

sidepodal partners to each other. If two edges e

and e

are sidepo-

dal, then the normal vectors deﬁned on the two edges by lemma 3.1

must be perpendicular, which gives the following set of equations:











= f

) +



) − f

)



∗ t , where t ∈ [0, 1] ,

= f

) +



) − f

)



∗ u , where u ∈ [0, 1] ,

· n

= 0 .

Solving this set of equations leads to a new equation of the form

a + bt + cu + dtu = 0, where t, u ∈ [0, 1] , (3)

where a, b, c and d are all scalar constants. Since the left-hand side

is a bilinear, closed and continuous expression of the parameters t

and u, it attains its minimum and maximum values at one of the four

extreme points of its domain, i.e. one of the four corners of the unit

square. This leads to a quick test that samples all these four corner

points of potential extrema and checks the signs of the result. If the

signs are different, then again due to Bolzano’s theorem, a solution

must exist to equation 3. A programmatic way to test this is shown

in algorithm 3.

Algorithm 3: AreSidepodal(e

, e

)

let a = f

) · f

)

let b =



) − f

)



· f

)

let c =



) − f

)



· f

)

let d =



) − f

)





) − f

)



let v

−

= Min(a, a + b, a + c, a + b + c + d)

let v

= Max(a, a + b, a + c, a + b + c + d)

return v

−

≤ 0 and v

≥ 0

3.4 Sidepodal Edge and Vertex

If a vertex v is located sidepodal to an edge, then lemma 3.2 says

that there must exist a normal n that satisﬁes the following condi-

tions.

(



n · f

(e)



n · f

(e)



≤ 0 ,

v ∈ Supp(n) .

The ﬁrst inequality holds if and only if one of the factors is non-

negative, and the other is nonpositive, and the second one holds if

and only if for each vertex neighbor w ∈ N(v) , n · (w − v) ≤ 0.

Therefore the normal vector n satisﬁes either











n · f

(e) ≤ 0 ,

n · f

(e) ≥ 0 ,

n · (w − v) ≤ 0 ∀ w ∈ N(v) ,

(4)











n · f

(e) ≥ 0 ,

n · f

(e) ≤ 0 ,

n · (w − v) ≤ 0 ∀ w ∈ N(v) .

(5)

The existence of a solution can be checked by proceeding with a

Gaussian elimination type of approach, performing elementary row

operations to reduce the inequalities to a pivoted form. However

when doing this, two rows may only be added together when they

have directions for their inequalities match, so the ﬁnal pivotized

form of conditions in (4) and (5) will both form a set of 3 to 6

inequalities. If neither of these sets of inequalities form a contra-

diction by forcing n to a zero vector, then the vertex v and edge e

are sidepodal.

There is also another way to determine if v ∈ Side

(e). This is

based on the geometric observation that if a vertex is sidepodal to

an edge, then starting from a box conﬁguration that is ﬂush with v

and e on adjacent faces, it is always possible to spin the box around

the normal of the box face that is ﬂush with e until the face of the

box that is ﬂush with v meets with a second vertex w ∈ N(v).

This property can be stated in the following form.

Proposition 3.3. Given a vertex v and an edge e of a convex poly-

hedron, v ∈ Side

(e) if and only if there exists a vertex w ∈ N (v)

such that (e

: v → w) ∈ Side

(e). 

Exploiting this property seemed to be more convenient in practice

rather than solving inequalities (4) and (5), however it is good to

know that both options exist.

3.5 Basis from Three Edges

Fixing an OBB to be ﬂush with only two edges on adjacent faces of

the OBB does not yet uniquely deﬁne its orientation, but still leaves

one degree of freedom. This can be seen clearly for example in the

earlier analysis by [O’Rourke 1985]. The question then arises, if

one is given three edges e

, e

and e

of a polyhedron, is it possible

to orient an OBB to be ﬂush with these edges, so that each of them

lies on separate, but mutually adjacent faces of the OBB, and if

so, what should the orientation (face normals n

, n

and n

) of the

OBB be? A hasty analysis might conclude that edges e

would be

in fact identical to normals n

, and that there would be no solution

if e

were not mutually perpendicular. However this

is not correct. Alternatively, one might think that the normals n

are computable from edges e

by some kind of sequence of cross

products, but this is not true either.

To provide the correct analysis, one proceeds with setting up a

group of equations like shown in previous sections. The three edges

are all mutually sidepodal, which yields the following:











= f

) +



) − f

)



∗ t , t ∈ [0, 1] ,

= f

) +



) − f

)



∗ u , u ∈ [0, 1] ,

= f

) +



) − f

)



∗ v , v ∈ [0, 1] ,

· n

= 0 ,

· n

= 0 ,

· n

= 0 .

(6)

Solving this is more complicated than before, but still doable. The

ﬁrst three conditions of equation set (6) may be renamed to the form











= a + bt , where t ∈ [0, 1] ,

= c + du , where u ∈ [0, 1] ,

= e + fv , where v ∈ [0, 1] ,

(7)

for obvious substitutions of vector constants a, b, c, d, e and f. Ex-

panding the three dot product conditions of equation set (6) with

variables from equations (7) then yields







a · c + b ·ct + u(a · d + b · dt) = 0 , (8)

c · e + c ·f v + u(d · e + d · fv) = 0 , (9)

a · e + a ·f v + t(b · e + b · fv) = 0 . (10)

Multiplying equation (8) by (d · e + d ·f v) and equation (9) by

−(a · d + b ·dt) and adding the resulting equations together gives

g + hv + t(i + jv) = 0 , (11)

where











g := (a ·c)(d · e) − (a · d)(c · e) ,

h := (a · c)(d · f) − (a · d)(c · f ) ,

i := (b · c)(d · e) − (b · d)(c · e) ,

j := (b · c)(d · f) − (b · d)(c · f) ,

(12)

and then multiplying equation (10) by −(i + jv) and equation (11)

by (b ·e + b ·fv) and adding the resulting equations together yields

+ lv + m = 0 , (13)

where











k := h(b · f) − j(a · f) ,

l := h(b · e) + g(b · f)

− i(a · f) − j(a · e) ,

m := g(b · e) − i(a · e) .

(14)

From here on, the two possible values for the parameter v can be

readily solved by applying a standard formula for roots of a second

degree polynomial to equation (13), and the values for t and u can

then be backtracked by using equations (9) and (10). If the second

degree polynomial in equation (13) has no real roots or if the pa-

rameters t, u or v are not in [0, 1] range, then an orientation does not

exist. As a special note, it is important to test that the ﬁnal solution

for t, u and v satisﬁes the original set of equations (6) again, since

equations (8) and (9) imply (11) only one way. That is, a solution

to equation (11) might not be a solution to equations (9) and (10).

Similarly, the equations (10) and (11) only imply (13) one way as

well.

In conclusion, this derivation provides an exact test for determin-

ing whether given three edges of the convex hull can accommodate

an OBB orientation where the three edges are all on mutually adja-

cent faces of the OBB, and if so, provides the possible coordinate

frames (n

, n

) for the orientation. Algorithm 4 shows a pro-

grammatic example. Note that this function will return a set of zero

to two solutions. The main algorithm will then loop over each of

these solutions in turn and process each one as a separate candidate

conﬁguration.

Algorithm 4: ComputeBasis(e

, e

)

compute a - m from equations (7), (12) and (14).

if polynomial kv

+ lv + m has no roots then

return {}

let v

, v

be the roots of kv

+ lv + m

let O = ∅

for v ∈ {v

, v

} do

let t = (g + hv)/(i + jv)

let u = (c · e + c · fv)/(d ·e + d · fv)

let n

= a + bt

let n

= c + du

let n

= e + fv

if t, u, v ∈ [0, 1] and n

⊥ n

and n

⊥ n

and n

⊥ n

then

O = O ∪



/||n

||, n

/||n

||, n

/||n

||)



return O

3.6 Basis from a Direction and an Edg e

The last subroutine that will be needed is the following. Let n

be a predetermined normal direction for one of the faces of the

OBB. Then, given an edge e, is it possible to complete the remain-

ing orientation of the OBB (compute n

and n

) such that edge e

is ﬂush with a face of the resulting OBB? The task is to identify

if this is possible, and if so, complete n

to an orthonormal basis

, n

) where, say, n

is perpendicular to e. Note that like in

the case of the three edges from the previous chapter, the correct

answer is not the cross product n

:= n

× e, since if e is parallel

to n

, the cross product will come out zero. Instead, lemma 3.1 can

be used again, which gives the following two conditions.

(

= f

(e) +



(e) − f

(e)



∗ u , where u ∈ [0, 1] ,

· n

= 0 .

Combining these two gives

· f

(e) + n



(e) − f

(e)



∗ u = 0 ,

from where the solution is

u =



· f

(e)





· (f

(e) − f

(e))



when the denominator is not zero, and when it is, any value of u

will satisfy the equation if and only if n

· f

(e) = 0 as well. The

Algorithm 5: CompleteBasis(n

, e)

let p = n

· f

(e)

let q = n



(e) − f

(e)



if q 6= 0 then

let u = p/q

let n

= f

(e) +



(e) − f

(e)



∗ u

= n

/||n

let n

= n

× n

return



, n

)



else if p = 0 then

let n

= f

(e)

let n

= n

× n

return



, n

)



else

return ∅

remaining face normal n

is then solvable via a cross product. This

process is shown in algorithm 5.

The equations and algorithms that were presented in this section

provide the tools for identifying antipodal and sidepodal compan-

ions for edges, and allows construction of candidate orientations

for an enclosing OBB once a set of candidate edges have been cho-

sen. The enumeration of these edges will follow a graph search

approach, but in order to make it feasible, these sets must ﬁrst be

analyzed in some spatial detail. The next section will focus on that

task, which will then enable building a search strategy for the algo-

rithm overall.

4 Analysis of Antipodal and Sidepodal Sets

For each convex polyhedron C, one can deﬁne the Gaussian

sphere representation of C, denoted by G(C). This representation

is a type of a dual representation of C, formed by a decomposition

of the unit sphere into disjoint regions, one for each vertex of C.

A point n in the Gaussian sphere belongs to the region of vertex v

of C if v ∈ Supp(n). This has the effect that vertices of C are

mapped to faces of G(C), and faces of C are mapped to single ver-

tices on G(C). An edge e on C is mapped to an arc on a great

circle of G(C) that is perpendicular in direction to e. Each face f

on G(C) is convex, because if v ∈ Supp(n

) and v ∈ Supp(n

then v ∈ Supp



+ (1 − t)n



as well for t ∈ [0, 1].

Using the Gaussian sphere representation, the following can be

said.

Theorem 4.1. Given an edge e of C, the set Anti

(e) forms a

single connected component in the vertex neighbor graph of C.

Proof. The viable normal directions n for an OBB ﬂush with an

edge e are explicitly parametrized by lemma 3.1, thus

Anti

(e) =

Supp



−f

(e)−



(e)−f

(e)



∗t



: t ∈ [0, 1]

On the Gaussian sphere G(C), this corresponds to a closed and con-

tinuous arc. Since this arc forms a single connected subset of points

on the Gaussian sphere, the set of vertices on C whose convex face

regions on G(C) the arc overlaps with is also connected.

Thinking about the set Anti

(e) being deﬁned by an arc on the

Gaussian sphere is also very useful for another reason. The length

of the arc is directly deﬁned by the dihedral angle of edge e, and

the closer the angle is to 180 degrees, the smaller the arc becomes,

meaning also that the smaller the set Anti

(e) corresponding to

edge e will be in general.

Likewise, the sets Side

(e) and Side

(e) have the same property.

Theorem 4.2. Given an edge e of C, the sets Side

(e) and

Side

(e) both form a single connected component in the vertex

neighbor graph of C.

Proof. By lemma 3.2, the set of antipodal vertices to edge e is de-

ﬁned in terms of the support function in the form

Side

(e) =

Supp(n) :



(e) · n



(e) · n



≤ 0

The set of normal vectors satisfying this inequality condition for n

forms a single closed and connected subset of G(C), so therefore

the set of vertices on C whose convex face regions on G(C) this

subset corresponds with is also connected. Adding the geometric

observation from proposition 3.3, it follows that the set Side

(e) is

also connected.

The reason that connectedness for these sets is important is that with

this property, if one ﬁrst obtains any element v

in, say, Anti

(e),

then the rest of the elements in that set can be enumerated quickly

in O



|Anti

(e)|



time by performing a graph search starting from

the neighborhood of v

, which will be much faster than having to

resort to a full O



|V |



search over all vertices of the convex polyhe-

dron. However, this property is only true if the number of neighbors

for each vertex of the polyhedron is bounded by a constant. This

condition will be implicitly assumed in all the analysis that follows,

but one should keep this technicality in mind.

Finally, a similar result exists for the structure of set intersections

of pairs of sidepodal vertex sets.

Theorem 4.3. Given two edges e

and e

of C, the set

Side

, e

) forms at most two separate connected components

in the vertex neighbor graph of C.

Proof. Expanding on the proof of lemma 3.2, the boundary of

Side

) is deﬁned by two equations f

) · n = 0 and

) · n = 0. These conditions map out two great circles on the

Gaussian sphere. Since the same holds for Side

), the boundary

of Side

, e

) is deﬁned by an intersection of two pairs of great

circles. Given that the intersection of two circles can have two dis-

tinct solutions, the boundary of Side

, e

) can be split into two

separate regions, both of which are themselves connected.

For the set Side

, e

) it is therefore necessary to ﬁnd, or ”boot-

strap” to two separate elements on the opposing sides of the Gaus-

sian sphere and perform a graph search from both starting points in

order to ensure that the whole set Side

, e

) gets enumerated in

full.

This bootstrapping process is fortunately simple. Each of the sets

Anti

(e), Side

(e) and Side

, e

) are deﬁned by one or two

support vector directions, so the task of bootstrapping is the same

as to ﬁnd an extreme vertex of the hull. That can be done in linear

time by iterating over the whole of V , but that is not very interest-

ing. A more advanced method is to utilize a Dobkin-Kirkpatrick

hierarchy to enable ﬁnding supporting vertices in O(log n) time

[Dobkin and Kirkpatrick 1990]. Therefore the total time complex-

ity to enumerate these sets is

• Anti

(e): O



log n + |Anti

(e)|



• Side

(e): O



log n + |Side

(e)|



• Side

, e

): O



log n + |Side

, e



Unfortunately it seems to be too difﬁcult to give strict limits for

the sizes of antipodal and sidepodal sets in the general case. In

the following sections, the sizes of these sets are analyzed in two

special cases that are the most interesting.

4.1 Analysis of Sphere(n)

Consider a set of n distinct points taken uniformly random on the

surface of the unit sphere and denote by Sphere(n) the convex hull

of that set. Clearly Sphere(n) consists of the n vertices itself. As

n grows, the shape of Sphere(n) grows to resemble the unit sphere.

This set has two particularly important properties. The ﬁrst is that

the dihedral angle of each edge e in Sphere(n) tends towards 180

degrees. This is another way of saying that the ”sharp” edges of

Sphere(n) all disappear. The second property is that the number of

vertices on each face of Sphere(n) is bounded by a constant. In fact,

each face is deﬁned by exactly three vertices with probability 1.

In this scenario, the areas of the convex regions in the Gaussian

sphere corresponding to each vertex in Sphere(n) tend to zero size.

Therefore any region R of the Gaussian sphere corresponds to a

number of vertices of Sphere(n) that is linearly proportional to

the surface area of R in Sphere(n). In particular, this means the

following.

Theorem 4.4. With probability 1, on the set Sphere(n), for each

edge e, the size of antipodal vertices |Anti

(e)| ∈ O(1).

Proof. As n grows, the dihedral angle of e tends to 180 degrees. In

other words, f

(e) tends towards f

(e) and hence the arc traced

by −n = −f

(e) −



(e) − f

(e)



∗ t degenerates towards a

single point, which has zero surface area.

A similar property exists for sidepodal edges.

Theorem 4.5. With probability 1, on the set Sphere(n), for each

edge e, the size of sidepodal vertices |Side

(e)| ∈ O(

√

n).

Proof. Since f

(e) tends towards f

(e), the two boundary circles

that deﬁne support directions for Side

(e) tend to a single overlap-

ping great circle on the Gaussian sphere. The length of circumfer-

ence of this great circle is 2πr, whereas the total surface area of the

sphere is 4πr

. Relating areas to vertices, n u 4πr

, so therefore

√

n u 2πr, or |Side

(e)| ∈ O(

√

n).

And ﬁnally,

Theorem 4.6. With probability 1, on the set Sphere(n), for

each pair of edges e

and e

, the size of sidepodal vertices

|Side

, e

)| ∈ O(1).

Proof. Continuing from proof of 4.5, the support directions for

Side

, e

) is the intersection formed by two great circles. When

6= e

, the great circles are distinct and the intersection has ex-

actly two solutions that are points. Like in the case of proof of

4.4, points have zero area, and hence Side

, e

) ∈ O(1) as

well.

Putting these three results together looks like the following.

Theorem 4.7. On the set Sphere(n), given an edge e or a pair of

edges e

, e

, the total time taken to enumerate

• Anti

(e) is O(log n) + O(1) = O(log n).

• Side

(e) is O(log n) + O(

√

n) = O(

√

n).

• Side

, e

) is O(log n) + O(1) = O(log n).

Proof. The total time to iterate over these sets is proportional to the

time taken to bootstrap to the ﬁrst vertex, plus the size of the set

itself.

This result concludes the analysis in positive light that in a suitably

uniform scenario, the sizes of antipodal and sidepodal sets are con-

siderably smaller and faster to enumerate than linear time. In the

next section, the same analysis is done without the assumption of

uniformity in place.

4.2 A Singularity in Cylinder(n)

If the requirement of uniform distribution from the case of

Sphere(n) is lifted, do the properties of theorem 4.7 still hold in

the general case? Unfortunately not always, and it is possible to

construct a scenario where the sizes of these sets are linear. Curi-

ously, the only currently found case occurs when the input data set

is a cylinder, which is deﬁned by

Cylinder(n) :=



cos

2πi

, ±1, sin

2πi



: i = 1, 2, . . . , n

This set represents a cylindrical shape with n points on both end

caps. An examination of this set shows that each edge e that is part

of the cylinder end caps of the convex hull of Cylinder(n) has a

linear number of vertices on average in each of the sets Anti

(e),

Side

(e) and Side

, e

). Therefore enumerating over these

sets is no faster than just enumerating over all vertices of the hull.

Examining the Gaussian sphere of this shape gives a clue to why

this happens. One problem stems from the fact that the end faces

of the cylinder lie on parallel planes, and have both n ∈ Ω(n)

vertices. For the Gaussian sphere, this means that there are two

vertices corresponding to those faces exactly at the opposite poles

of the Gaussian sphere, and they both have n ∈ Ω(n) incident

edges connecting them. The existence of such a ”singularity”

point that connects a linear number of vertices forces the size of

Anti

(e) to be linear for each edge on the cylinder end caps. If the

number of vertices on each face of the convex hull was bounded by

a constant, this would not happen. However, even if imposing such

a restriction, the sizes of the sets Side

(e) and Side

, e

) will

still remain linear, so this restriction does not completely capture

the worst case behavior. Therefore, at least in for Cylinder(n), the

following appears to be the case.

Proposition 4.8. In the worst case,

|Anti

(e)|, |Side

(e)| and |Side

, e

)| ∈ Ω(n) . 

It remains an open question whether it is possible to characterize

the conditions when this occurs in a more precise manner to under-

stand this behavior better. So far this worst case behavior has only

been observed on shapes that are very cylindrical, and even a small

deviation from this generally causes the issue to vanish.

5 The New Algorithm

With the help of the mathematical analysis in sections 3 and 4, it is

now possible to present the main algorithm. The overall strategy is

straightforward: instead of performing a brute force search over all

potential orientation directions in the sphere, the plan is to enumer-

ate all OBB orientations that are uniquely ﬁxed by combinations of

Figure 2: Examples of the four different edge contact categories A-D for a convex polyhedron and its enclosing OBB. The features in contact

with the OBB are highlighted in red. A: Three edges ﬂush with three mutually adjacent faces of the OBB. B: Three edges ﬂush with three

faces of the OBB, of which two are opposite. C: Three edges ﬂush with two adjacent faces. D: Two edges ﬂush with three faces, of which two

must be opposite.

Algorithm 6: FindMinOBB(V ,F ,E)

for e

∈ E do

for e

∈ Side

) do

Test category A

for e

∈ Side

, e

) do

B = ComputeBasis(e

, e

)

if B 6= ∅ then

O = ComputeOBB(V, B)

RecordOBB(O)

Test category B

for e

∈ Anti

) do

n = AntipodalDir(e

, e

)

B = CompleteBasis(n, e

)

if B 6= ∅ then

O = ComputeOBB(V, B)

RecordOBB(O)

Test category C

for f ∈ F do

let e

, e

be two edges in f.

let n = e

× e

for e

∈ Side

) do

B = CompleteBasis(n, e

)

if B 6= ∅ then

O = ComputeOBB(V, B)

RecordOBB(O)

edges of the convex hull. These conﬁgurations are divided into four

categories:

A The OBB is ﬂush with three (or more) edges of the hull on three

(or more) mutually adjacent faces of the OBB. Example case

with minimal contact of the hull and the OBB:

0 : (1, 0, 2), 2 : (4, 0, 4), 4 : (3, 2, 0)

1 : (1, 4, 3), 3 : (4, 2, 1)

The minimal volume OBB is ﬂush with edges 1 → 2, 1 → 4

and 2 → 3 on three mutually adjacent faces of the OBB and

touches vertex 0 on the face opposite to edge 1 → 2.

B The OBB is ﬂush with three (or more) edges of the hull on three

(or more) faces of the OBB, of which two are opposite to each

other. Example case with minimal contact of the hull and the

OBB:

0 : (0, 2, 0), 2 : (0, 4, 0)

1 : (0, 2, 2), 3 : (2, 0, 2)

The minimal volume OBB is ﬂush with edges 0 → 1, 0 → 2

and 2 → 3. The edges 0 → 1 and 2 → 3 lie on the opposite

faces of the OBB.

C The OBB is ﬂush with three (or more) edges of the hull on only

two adjacent faces of the OBB, or in other words, the OBB is

ﬂush with a face and an edge of the hull. Example case with

minimal contact of the hull and the OBB:

0 : (0, 0, 0), 2 : (5, 5, 0)

1 : (5, 2, 2), 3 : (10, 0, 0)

The minimal volume OBB is ﬂush with the face formed by

vertices 0 → 2 → 3, and the opposite face of the OBB is in

contact with the vertex 1. Note that the contact edge on an

adjacent face of the OBB may or may not be the same as one

of the edges of the face. In this case, the adjacent edge is edge

0 → 3, which is also one of the face edges.

D The OBB is ﬂush with only two edges of the hull on three differ-

ent faces of the OBB. This is a special case where an edge of

the hull coincides with an edge of the OBB. When this occurs,

there must exist two opposite faces on the OBB that contain

edges of the convex hull, or otherwise the box and the poly-

hedron could be projected to a 2D plane along the common

shared edge (reducing the shared edge to a point), and the re-

sulting 2D rectangle would not be ﬂush with any edge of the

2D polygon and therefore would not be optimal. Example

case with minimal contact of the hull and the OBB:

0 : (0, 4, 2), 2 : (2, 4, 2), 4 : (1, 4, 0)

1 : (0, 4, 4), 3 : (3, 0, 1)

In this example, the minimal volume OBB is ﬂush with only

two edges of the polyhedron, but these edges are in contact

with three different faces of the OBB. The vertex 0 is an in-

ternal vertex that is not in contact with the OBB.

Figure 2 shows a rendering to illustrate each of the example cases.

The main search will proceed by testing all valid conﬁgurations of

each of these categories. This is done in the following manner:

A + B For each edge e

∈ E, ﬁnd all edges e

∈ Side

) that

can be placed on an adjacent side of the OBB. Then, for

category A, complete the basis by searching for all edges

∈ Side

, e

) to be placed on a third face of the OBB

that is mutually adjacent to both earlier faces. Correspond-

ingly for category B, complete the basis by searching for all

edges e

∈ Anti

) to be placed on a third face of the OBB

that is opposite to the face that is in contact with edge e

C Loop over all faces f ∈ F . This ﬁxes one of the face normals

of the OBB. Then loop over all edges e

∈ Side

where e

is one of the edges of F . Complete the basis for

each using algorithm 5.

D This category gets implicitly handled during the search for

category B by allowing the assumption that e

= e

, so no

separate code for testing category D is needed. Effectively

this is recognizing that an edge may be sidepodal to itself.

The full code to perform this iteration is presented in algorithm

6. This code contains two new functions that have not been intro-

duced before. The ﬁrst function ComputeOBB takes a basis for

the orientation of an OBB and computes six extreme vertices of the

hull, one for each face of the OBB. With the help of the Dobkin-

Kirkpatrick structure, this takes at most O(log n) time. The second

one is the function RecordOBB. This is a constant time opera-

tion which tests the newly created OBB for volume against the best

previously found one, and records the smaller of the two.

Algorithm 6 contains two separate top level loops. The ﬁrst ex-

amines categories A, B and D, followed by a second one which

examines category C. In the ﬁrst loop structure, an outer loop over

each edge of the hull ﬁxes the ﬁrst edge. This is a O(n) operation.

The second loop iterates over all sidepodal edges of the ﬁrst edge.

This takes O



log n + |Side



time.

The ﬁrst innermost loop searches through all conﬁgurations in cat-

egory A in O



log n + |Side

, e



time. To establish the

orientation of the OBB, algorithm 4 is invoked, which computes

a basis set (n

, n

) for the given three edges. The functions

ComputeOBB and RecordOBB then process the found basis.

The second innermost loop enumerates all conﬁgurations in cate-

gory B in O



log n + |Anti



time. If the iterated edges are

compatible, then one of the OBB face directions is ﬁrst computed

with algorithm 2, which is completed to a full basis by the method

5. This basis is then again tested.

Last, the second loop body iterates through each conﬁguration in

category C. Each face of the hull directly deﬁnes a face direction

for the OBB. The inner loop iterates over the sidepodal edges of e

in O



log n + |Side



time to ﬁnd the candidate orientations

for the second axis of the OBB. Like in the previous case, the full

basis is completed and tested.

The overall number of steps in the ﬁrst loop structure is |E|



log n+

|Side

∗



log n + |Side

∗

, e

∗

)| + |Anti

∗



log n,

whereas the second loop runs in |F |



log n + |Side

∗



log n

steps. On the Sphere(n) data set, based on theorem 4.7, the overall

algorithm runtime is therefore O



3/2

(log n)



. In the worst case,

like in the case of the Cylinder(n) data set suggested by proposition

4.8, the algorithm runs in O(n

log n) time.

5.1 Implementing the Graph Search

The main search algorithm in listing 6 contains for loops over sev-

eral different sets. Implementing these loops carefully is the key

to obtaining correct performance. While the for loops e

∈ E and

f ∈ F are trivial iterations of all stored edges and faces of the

hull, the other loops will require a two-phase operation that ﬁrst

bootstraps to a ﬁrst element of the set, and then traverses the vertex

graph of the hull to compute the remaining ones. This means that

the data structure storing the convex polyhedron will need to have

vertex adjacency information available. The actual iteration of each

set then works out to

For e

∈ Anti

1. Compute the ﬁrst antipodal vertex v

∈ Supp



− f

)



2. Since the set of antipodal vertices is connected due to theorem

4.1, ﬁnd all remaining antipodal vertices {v

}

⊆ Anti

)

by a ﬂood ﬁll that starts from v

and proceeds to each of its

neighbors that are tested for antipodality with respect to edge

using algorithm 1.

3. For each edge e

that exists in the subgraph induced by the an-

tipodal vertices {v

}

, test each for antipodality with respect

to edge e

using algorithm 2. This set of edges generates the

ﬁnal set Anti

For e

∈ Side

1. Compute the ﬁrst sidepodal vertex v

∈ Supp(e

2. Since the set of sidepodal vertices is connected due to theorem

4.2, ﬁnd all remaining sidepodal vertices {v

}

⊆ Side

)

by a ﬂood ﬁll that starts from v

and proceeds to each of its

neighbors that are tested for sidepodality with respect to e

using methods from section 3.4.

3. For each edge e

that exists in the subgraph induced by the

sidepodal vertices {v

}

, test each for sidepodality with re-

spect to edge e

by using algorithm 3. This set of edges gen-

erates the ﬁnal set Side

For e

∈ Side

, e

1. Let n = n

× n

, where n

and n

are chosen using lemma

3.1 with respect to edges e

and e

in such a way that the cross

product is not denegerate.

2. Compute ﬁrst representatives from both of the two disjoint

sets of connected components by searching v

∈ Supp(n)

and v

∈ Supp(−n).

3. Since the set of sidepodal vertices to a pair of edges is con-

nected inside the two disjoint sets, due to theorem 4.3, ﬁnd all

remaining sidepodal vertices {v

}

⊆ Side

, e

) by two

separate ﬂood ﬁlls that start from v

and v

respectively, and

proceed to each of their neighbors that are tested for sidepo-

dality with respect to e

and e

using methods from section

3.4.

4. For each edge e

that exists in the subgraph induced by the

sidepodal vertices {v

}

, use algorithm 5 to compute the set

of edges that are sidepodal to both e

and e

. This set of edges

generates the ﬁnal set Side

, e

This strategy ensures that the sets Side

(·) and Side

(·) are related

to each other in a numerically stable way.

5.2 Practical Considerations

Whenever implementing any piece of real-world code, there are al-

ways special considerations that are important to take into account

for the implementation to be successful and as efﬁcient as possible.

In this section, such practical matters are discussed.

The ﬁrst one is the fact that the algorithm relies on the precompu-

tation of the convex hull for the input point set. It is well known

that robustly computing an accurate convex hull for arbitrary input

can be hard due to ﬂoating point imprecision. A good treatise to

the stability issues with convex hull implementation that the reader

should be aware of has been presented at GDC [Gregorius 2014].

The OBB computation method itself has been found to be quite sta-

ble. It should however be noted that in places where the algorithms

presented in this paper compare ﬂoating point values for range or

equality, the code should in practice contain a very small epsilon

threshold for these comparisons. This is because otherwise the

graph search may terminate early when enumerating for example

Figure 3: Four models from the GAMMA Group real world data

set that exhibited worst case performance behavior. In clockwise

order starting from top left: arrow4.obj, taperoll.obj, candy05.obj

and kummer.obj. Each object has a strong cylindrical component

to their convex hulls.

the sets Side

∗

), and not ﬁnd an important conﬁguration for the

OBB.

To improve overall performance, a developer is advised to pay at-

tention to the symmetry of the problem to avoid redundant (but con-

stant factor) work. One such case occurs for example when enumer-

ating over all edge pairs e

and e

that are sidepodal to each other.

Since the order in which these are searched does not matter, one can

cut the work in half by assuming a canonical ordering that i ≤ j.

Note that depending on the context, equality can be important, or

otherwise category D from section 5 might be missed. Another such

place where symmetry may occur is if traversing over vertex pairs

to ﬁnd edges on the graph. In that case, the edges v

→ v

and

→ v

are the same, and should not be considered twice.

The version of the algorithm that was implemented for the

benchmarks in the next section does not actually use a Dobkin-

Kirkpatrick hierarchy to locate extreme vertices. To explain

why, consider the problem of ﬁnding k supporting vertices



Supp(n

), Supp(n

), . . . , Supp(n

)



corresponding to a se-

quence of k direction vectors (n

, n

, . . . , n

). In the implemen-

tation, one is able to organize these queries so that each search

direction is often only a very small perturbation away from the

previous search direction. Then the ﬁrst query for Supp(n

) will

amount to an uninformed search over V , but when searching for

Supp(n

), it is expected to be found in close vicinity to Supp(n

)

and can be located in only a few steps by performing a greedy hill

climbing search starting from the previously found vertex. There-

fore Supp(n

) through Supp(n

) can be found very quickly if

one caches the previous answer and always begins the next search

from that cached vertex. In this kind of implementation, there exists

a subroutine of depth-ﬁrst search code which quickly establishes a

good spatially coherent ordering for the edge graph, and all loops in

the algorithm are implemented to follow this spatial order. In prac-

tice this was seen to perform extremely well, to the point of almost

having the conﬁdence to assume amortized O(1) time extreme ver-

tex queries. However, there are technicalities involved and practical

benchmarks still showed a very slow logarithmic growth. A rigor-

ous exploitation of spatial coherency might have to consider a fast

constant factor approximation to what is called the Chinese Post-

man Problem [Filho and de Avila Ribeiro Junqueira 2010] in order

to establish a strict upper bound.

When benchmarking the implementation, it was found to be prac-

tical to precompute up front the ﬁrst representatives for the sets

0 0.2 0.4 0.6 0.8 1

·10

n: number of vertices on the sphere

seconds to compute OBB

Sphere(n)



3/2

(log n)



Figure 4: Time taken to compute minimum volume OBB for

Sphere(n).

Anti

(e) and Side

(e) for each edge e. Since this can be done

outside the hot inner loops in O(n log n) time and O(n) storage

space, it will speed up the implementation noticeably. In fact, pre-

computing full contents of the antipodal and sidepodal sets outside

the hot loops was measured to be a performance gain. That how-

ever is an implementation tradeoff since storing full sets will require

more than a linear amount of memory storage.

For the graph searches, the implementation will probably follow a

ﬂood ﬁll type of approach to detect whether a given vertex has been

visited before. An efﬁcient implementation of this should not use

a set or an associative container that would dynamically mutate to

track the visited vertices, but instead it is much faster to preallocate

a ﬂat array of static size n, where each index of the array stores

the information whether that vertex has been visited or not. This

scheme gives the ability to clear the structure for new searches in

constant time, by giving each search operation its own unique ID,

and storing at each index this ID if the given vertex has been visited.

Starting a new search then corresponds to simply incrementing the

ID counter by one, which effectively resets all vertices to unvisited

state. Also, when performing the actual search, one should not use

recursive function calls, because unless optimized into tail calls,

these may have unbounded depth and stack space in most runtime

environments is ﬁxed.

5.3 Dealing with the Singularity

Since the performance gap between best and worst cases is so large,

it is natural to ask if the worst case performance can be improved.

Unfortunately this is yet unknown, but there are a number of things

that can be done to mitigate the issue in practice. In this section

three such strategies are presented.

The algorithms presented in section 3 deal with computing scalars

to obtain normal vectors for OBB faces from the parametrization

given in lemma 3.1. In the difﬁcult case of the cylinder, it can be

observed that the solutions for this parametrization often come out

at the extreme ends when t = 0 or t = 1, since several edges of the

cylinder have a dihedral angle of exactly 90 degrees. This corre-

sponds to the special case when one of the OBB faces is ﬂush with

a face of the polyhedron, and because these conﬁgurations will all

be searched in the loop for category C, there is no reason to handle

them at all in categories A and B . Therefore the implementation is

ﬁle vertices faces edges t

exact

merge

extrude

approx

extrude

exact

approx

exact

arrow4.obj 1024 2044 3066 84.7 29.6 16.4 0.54 1.0005x 1.006x

taperoll.obj 839 1674 2511 67.5 54.3 8.63 2.05 1.005x 1.011x

candy05.obj 20044 40084 60126 84.7 83.9 29.8 0.1 1.00007x 1.001x

kummer.obj 624 1244 1866 66.9 11.8 3.45 0.7 1.007x 1.012x

Figure 5: Results of applying preprocessing methods on the four worst case models from the data set obtained from GAMMA Group mesh

database. The columns t

show the number of seconds taken to compute the minimum volume OBB in different cases. The column t

exact

corresponds to the case of the original unprocessed model. Last two columns denote ratios of the found OBBs to the volume of the optimal

box, when approximation methods were used.

free to restrict valid values of t to the range [ε, 1 − ε] for a small

constant ε > 0 in order to cut down redundant work.

Another observation is that the convex hull algorithm that is em-

ployed might by convention generate hulls that consist of triangular

faces only. This can create neighboring triangles that are aligned

in a plane. The edges joining such adjacent planar triangles have

a dihedral angle of 180 degrees each, so they are degenerate and

do not have any actual effect and an implementation should remove

these edges in a preprocess step. This can be done either by merg-

ing all neighboring planar triangles to form convex polygons, or

by ignoring all internal edges on the faces during the search. This

scheme will be later called the merge strategy. In the case of the

cylinder, the overhead from redundant internal edges can be consid-

erable since there are a linear number of them, and if not removed,

each of these internal edges will in turn have a linear number of

sidepodal partners.

The abovementioned optimizations are unfortunately only improve-

ments by a constant factor. In order to completely remove the

problem in practice, two speciﬁc approximation methods were em-

ployed with the goal of preprocessing the convex hull in a subtle

manner that should have only minimal effect on the resulting OBB,

but would considerably cut down the work in practice. Assuming

that the basis of the OBB obtained as a result from this approxima-

tion does not change much, then the same basis can be used on the

original unprocessed convex hull to compute the exact tight-ﬁtting

OBB.

The ﬁrst method builds on the idea that because the end caps of the

cylinder are so problematic due to the large number of vertices in

them, these faces should be removed. This can be done by extrud-

ing a new vertex outward to the direction of the face normal from

the centroid of each face polygon that has too many vertices. This

breaks each polygonal face up into a number of triangles, which

each have their unique face normal direction. If the new vertex is

located very close to the plane of the polygon, the orientation of

the resulting OBB will be very close to the original. This method

will be called the extrude strategy. For convex hull algorithms that

produce only triangular data, this strategy will ﬁrst require running

the merge step to ﬁnd the faces with large number of vertices.

The second method operates by constructing a simpliﬁed approxi-

mation of the convex hull by repeatedly merging two adjacent faces

of the hull that are almost coplanar, until an error threshold is met

or the number of faces is reduced down to a number that is small

enough to process. When two faces are merged in this manner, the

new face does not even need to enclose all the points of the original

hull, since the approximation will only be used to establish an orien-

tation for the OBB and the tight ﬁt can be computed on the original

hull after the basis has been chosen. The process can be done for

disjoint pairs of faces, after which the convex hull is recomputed

again to ensure proper convexity. For the case of the cylinder, this

method was found to be very efﬁcient, since it successfully removes

large numbers of edges on the side of the cylinder, where the ﬁnest

detail typically is. This will be called the approx strategy. Running

merge or extrude steps before this strategy was not seen beneﬁcial,

so the results for this strategy consist of only running the approx

step alone.

The next section reports results from practical tests, where the last

conducted test shows comparisons of adding the three optimizations

merge, extrude and approx that were introduced in this section.

6 Experimental Results

The new algorithm proposed in section 5 was implemented us-

ing the open source MathGeoLib software package [Jyl

anki 2011–

2015]. The code was then tested on two different data sets. The ﬁrst

one was the synthetic case of Sphere(n) from section 4.1 for values

n ∈ {50, 100, 150, . . . , 10000}. The second data set consisted of

2088 different 3D models obtained from the GAMMA Group on-

line 3D mesh research database [GAMMA Group 2008]. From this

database, all ﬁles in the .obj ﬁle format were chosen from ﬁve dif-

ferent categories:

• 55 models from the dataset 2001.

• 381 models from the dataset ANIMALS.

• 530 models from the dataset ARCHITEC.

• 437 models from the dataset GEOMETRY.

• 685 models from the dataset MECHANICAL.

In the ﬁrst test, an OBB was generated for each input object in

both of the two data sets using the exact version of new algorithm

that does not include approximations from the previous section, and

the result was compared for optimality against the smallest vol-

ume OBB found via a brute force search. The brute force search

consisted of subdividing the unit hemisphere to a search grid of

256 ∗ 256 starting search directions, and using the rotating calipers

method to improve the volume of the box until reaching a local

minimum for each start orientation. This test conﬁrmed that in each

case, the new algorithm found the same or a better bounding OBB

than the brute force method did, up to the precision determinable

by ﬂoating point computation.

The second test consisted of benchmarking the performance of the

exact version of the new algorithm on the same two data sets.

The performance tests were run on a MacBook Pro laptop with a

2.7GHz Intel Core i7 processor and 16GB of RAM running Win-

dows 8.1. The test program was built by using the Microsoft Visual

Studio 2013 Update 4 compiler, with 64-bit compilation and Math-

GeoLib AVX SIMD performance optimizations enabled. Execu-

tion was single-threaded in all benchmarks. The numbers reported

in each case do not include the time taken to run the quickhull algo-

rithm. The resulting runtime performance for the case of Sphere(n)

is shown in ﬁgure 4, where the actual data is graphed in blue. A

regression curve of the expected performance of n

3/2

(log n)

pro-

vided by earlier analysis was ﬁt to this data in the range n ≤ 5000

and is shown for reference in black. Extrapolating this curve for

0 500 1,000 1,500 2,000 2,500 3,000 3,500 4,000 4,500

seconds

2001

animals

architec

geometry

mechanical



3/2

(log n)



Figure 6: A scatter plot showing the time taken to compute the minimum volume OBB for ﬁve different data sets from the GAMMA Group 3D

mesh database. Each model is located on the x-axis based on the number of vertices on its convex hull. The y-coordinate speciﬁes the number

of seconds taken to compute the OBB for that model. The black curve shows the regression function from the previous Sphere(n) case. The

four models shown in ﬁgure 3 were complete outliers that did not ﬁt in this plot.

values of 5000 ≤ n ≤ 10000 shows a pleasing match with the

recorded data.

Figure 6 shows the performance of the exact version of the algo-

rithm on the real world data sets from the GAMMA Group. In

the scatter plot, the x-coordinate of each point gives the number of

points on the convex hull of that object, whereas the vertical axis

shows the time taken to compute the OBB, in seconds. The re-

sults from this benchmark show that fortunately the performance

for most real world objects is very similar to the case of Sphere(n).

Of the 2088 models that were tested, 2084 exhibited performance

close to the best case behavior. The remaining four models were

outliers that took more than a minute to process. Taking a closer

look revealed that each of these four had convex hulls that have a

strong cylindrical shape. Figure 3 shows a rendering of each.

The last test consisted of measuring the effects of including the

merge, extrude and approx mitigation strategies on these four dif-

ﬁcult test models from the GAMMA Group database that suffered

from degenerate behavior. The results are presented in ﬁgure 5 and

they look promising. For all models, merging planar triangles was

an improvement. Since it does not change the optimality of the

result or slow down the computation of the OBB, it would be a

mistake to ignore the merge preprocessing step. The extrude ap-

proximation method was also effective and it was able to speed up

the computation considerably in each case. Even while this method

is not theoretically optimal, it is something to consider in practice,

since the resulting OBB volumes were only 0.5% larger than the

optimal in worst case. Finally, the results of the approx method

shows that it is a promising way to speed up the search to a few

seconds at most, while only introducing about one percent increase

in the resulting volume.

7 Conclusion and Future Work

A new algorithm has been introduced for ﬁnding tight-ﬁtting

enclosing bounding boxes for three-dimensional point data. The

method operates by quickly iterating over all possible OBB

orientations that are uniquely determined by combinations of

edges of the convex hull of the input. This was made possible

with the help of new mathematical insight on the problem. The

algorithm is able to accurately ﬁnd the optimal minimum volume

enclosing OBB in all conducted tests. Unfortunately the optimality

of this method depends on an unproven assumption, but given the

infallible practical evidence, it is appropriate to posit the following.

Conjecture 7.1. A box of minimal volume circumscribing a convex

polyhedron has at least three distinct edge-face contacts (of which

at least two occur on adjacent faces of the OBB).

In this statement, an edge-face contact means that a speciﬁc face f

of the OBB is ﬂush with a speciﬁc edge e of the polyhedron. Being

distinct means that in any pair of the contacts, either the edges or

the faces in question are different. This statement captures all of the

categories A - D enumerated in section 5 (ﬁgure 2), so if proven,

it would assert the optimality of the new algorithm. The second

part in parentheses is repeated from theorem 2.1. If conjecture 7.1

holds, the presented method will be the ﬁrst algorithm in its own

class in comparison to all previously published results: an exact

and deterministic geometric enumeration method for solving the

minimum volume OBB problem.

The algorithm has been implemented in practice and the real world

results validate the theoretical aspects. On the tested real world

models that are not cylinder-like, the algorithm runs in the pre-

dicted O(n

3/2

(log n)

) time, which is a large improvement over

the previously published best O(n

) time complexity. For mod-

els that have only a few hundred points on their convex hulls, the

algorithm can ﬁnd optimal OBBs at interactive rates. In the worst

case, which is currently only known to happen on cylindrical shapes

and shapes that can have vertices with Ω(n) number of neighbors,

the algorithm exhibits degenerate behavior that causes it to run in

O(n

log n) time. However this performance cliff can be mitigated

in practice by performing a preprocessing step on the input. It is an

open question if this worst case behavior can be strictly improved.

On the other end, I believe that Ω(n

3/2

) is a lower bound that can-

not be circumvented by any algorithm that is based on enumerating

edge conﬁgurations of the hull.

In some applications it is more useful to ﬁnd an enclosing OBB that

minimizes the surface area of the box rather than the volume. The

presented algorithm can be trivially adapted to optimize the sur-

face area instead of the volume, but it is unclear however whether

this will result in optimal minimum surface area OBBs. Due to the

already lengthy treatise presented in this paper, this kind of exami-

nation was left out for later.

Solving conjecture 7.1 will probably need to examine the volume of

an OBB as a function of a given basis. O’Rourke suspected that this

function might have local minima in conﬁgurations where the OBB

is ﬂush with exactly two edges and four vertices of the polyhedron,

but noted that he had not found evidence of this in practice. If such

a conﬁguration exists that is a global minimum, it will disprove the

optimality of the new algorithm presented here. Despite attempts

at producing such a conﬁguration via computer search, I have not

been able to ﬁnd a counterexample. In fact, such a conﬁguration

does not seem to exist even as a local minimum. Therefore it raises

a question whether conjecture 7.1 could even be strengthened to

apply to all local minima of the volume function.

Acknowledgements

I would like to thank Kalle Lepp

a and Ilari Vallivaara for each of

the many pleasing and insightful conversations on the topic.

References

BARBER, C. B., DOBKIN, D. P., AND HUHDANPAA, H. 1996.

The quickhull algorithm for convex hulls. ACM TRANSAC-

TIONS ON MATHEMATICAL SOFTWARE 22, 4, 469–483.

BAREQUET, G., AND HAR-PELED, S. 2001. Efﬁciently approxi-

mating the minimum-volume bounding box of a point set in three

dimensions. J. Algorithms 38, 1 (Jan.), 91–109.

BARTZ, D., KLOSOWSKI, J. T., STANEKER, D., INTERAKTIVE

SYSTEME, G., AND T

UBINGEN, U., 2005. Visual computing

for medicine.

BORCKMANS, P. B., AND ABSIL, P.-A. 2010. Oriented bounding

box computation using particle swarm optimization. In ESANN.

CHAN, C. 2003. Minimum Bounding Boxes and Volume Decom-

position of CAD Models. University of Hong Kong.

CHANG, C.-T., GORISSEN, B., AND MELCHIOR, S. 2011.

Fast oriented bounding box optimization on the rotation group

SO(3,R). ACM Trans. Graph. 30, 5 (Oct.), 122:1–122:16.

DIMITROV, D., KNAUER, C., KRIEGEL, K., AND ROTE, G. 2009.

Bounds on the quality of the pca bounding boxes. Comput.

Geom. Theory Appl. 42, 8 (Oct.), 772–789.

DOBKIN, D. P., AND KIRKPATRICK, D. G. 1990. Determining

the separation of preprocessed polyhedra: A uniﬁed approach.

In Proceedings of the Seventeenth International Colloquium on

Automata, Languages and Programming, Springer-Verlag New

York, Inc., New York, NY, USA, 400–413.

EBERLY, D. H. 2006. 3D Game Engine Design, Second Edition: A

Practical Approach to Real-Time Computer Graphics (The Mor-

gan Kaufmann Series in Interactive 3D Technology). Morgan

Kaufmann Publishers Inc., San Francisco, CA, USA.

ERICSON, C. 2004. Real-Time Collision Detection (The Morgan

Kaufmann Series in Interactive 3-D Technology) (The Morgan

Kaufmann Series in Interactive 3D Technology). Morgan Kauf-

mann Publishers Inc., San Francisco, CA, USA.

FILHO, M. G., AND DE AVILA RIBEIRO JUNQUEIRA, R. 2010.

Chinese postman problem (cpp): solution methods and compu-

tational time. Int. J. of Logistics Systems and Management.

FREEMAN, H., AND SHAPIRA, R. 1975. Determining the

minimum-area encasing rectangle for an arbitrary closed curve.

Commun. ACM 18, 7 (July), 409–413.

GAMEDEV.NET. How to create oriented bounding box.

GAMMA GROUP, 2008. 3d meshes research database of

the group g

eration automatique de maillages et m

ethodes

d’adaptation, inria, france. [software, website]. Avail-

able at https://www-roc.inria.fr/gamma/gamma/

download/download.php.

GEOMETRIC TOOLS LLC. Mathematics: Computational geome-

try.

GOTTSCHALK, S., LIN, M. C., AND MANOCHA, D. 1996.

Obbtree: A hierarchical structure for rapid interference detec-

tion. In Proceedings of the 23rd Annual Conference on Com-

puter Graphics and Interactive Techniques, ACM, New York,

NY, USA, SIGGRAPH ’96, 171–180.

GREGORIUS, D., 2014. The 3d quickhull algo-

rithm. Game Developers Conference. Available at

http://www.gdcvault.com/play/1020141/

Physics-for-Game-Programmers.

JYL

ANKI, J., 2011–2015. MathGeoLib: A C++ library for

3D mathematics and geometry manipulation. Available at

http://clb.confined.space/MathGeoLib/ and https://

github.com/juj/MathGeoLib/.

KAY, T. L., AND KAJIYA, J. T. 1986. Ray tracing complex

scenes. In Proceedings of the 13th Annual Conference on Com-

puter Graphics and Interactive Techniques, ACM, New York,

NY, USA, SIGGRAPH ’86, 269–278.

LARSSON, T., AND K

ALLBERG, L. 2011. Fast computation of

tight-ﬁtting oriented bounding boxes. In Game Engine Gems 2,

E. Lengyel, Ed. A K Peters, 3–19.

MEGIDDO, N. 1982. Linear-time algorithms for linear program-

ming in r3 and related problems. In Foundations of Computer

Science, 1982. SFCS ’08. 23rd Annual Symposium on, 329–338.

O’ROURKE, J. 1985. Finding minimal enclosing boxes. Interna-

tional Journal of Computer & Information Sciences 14, 3, 183–

199.

SCHNEIDER, P. J., AND EBERLY, D. 2002. Geometric Tools for

Computer Graphics. Elsevier Science Inc., New York, NY, USA.

STACKOVERFLOW. Creating oobb from points.

TOUSSAINT, G. 1983. Solving geometric problems with the rotat-

ing calipers. In Proc. IEEE MELECON ’83, 10—02.

TROUTMAN, N. Calculating minimum volume bounding box.

WELZL, E. 1991. Smallest enclosing disks (balls and ellipsoids). In

Results and New Trends in Computer Science, Springer-Verlag,

359–370.