8 1.FastComputationofTight‐FittingOrientedBoundingBoxes
Figure 1.2. Illustration of how the large base triangle spanning extremal points (left) is
extended to tetrahedra in two directions by finding the most distant extremal points below
and above the triangle surface (right).
above and below the plane of the base triangle. An example of a ditetrahedron
constructed in this way is shown on the right in Figure 1.2. This effectively gen-
erates six new triangles, three top triangles located above the plane of the base
triangle and three bottom triangles located below the base triangle. For each one
of these triangles, candidate OBBs are generated in the same way as already de-
scribed above for the large base triangle, and the best axes found are kept.
After this, all that remains is to define the final OBB appropriately. A final
pass through all n vertices in P determines the true size of the OBB, that is, the
smallest projection values
u
s
,
v
s
, and
w
s
, as well as the largest projection values
u
l
,
Figure 1.3. The three different candidate orientations generated from the normal and
edges of the large base triangle. In each case, the box is generated from the edge drawn
with a solid line.
1.2Algorithm 9
v
l
, and
w
l
of P along the determined axes u, v, and w. The final OBB parameters
besides the best axes found are then given by
,
2
,
2
,
2
.
222
uu
u
vv
v
ww
w
uu vv ww
ls
h
ls
h
ls
h
ls ls ls
m
uv w
The parameters
u
h
,
v
h
, and
w
h
are the half-extents, and m is the midpoint of the
box. Note that m needs to be computed in the standard base, rather than as the
midpoint in its own base.
A final check is also made to make sure that the OBB is still smaller than the
initially computed AABB; otherwise, the OBB is aligned with the AABB in-
stead. This may happen in some cases, since the final iteration over all n points in
P usually grows the OBB slightly compared to the best-found candidate OBB,
whose size only depends on the subset S.
This completes our basic presentation of the DiTO algorithm. Example
source code in C/C++ for the DiTO-14 algorithm is available, which shows how
to efficiently implement the algorithm and how the low-level functions work.
HandlingDetrimentalCases
There are at least three cases of detrimental input that the algorithm needs to de-
tect and handle appropriately. The first case is when the computation of the first
long edge in the base triangle results in a degenerate edge; that is, the two points
are located at the same spot. In this case, the OBB is aligned with the already
computed AABB, and the algorithm is aborted.
The second case arises when the computation of the third point in the base
triangle results in a degenerate triangle; that is, the point is collinear with the
endpoints of the first long edge. In this case, one of the OBB axes is aligned with
the already-found first long edge in the base triangle, and the other two axes are
chosen arbitrarily to form an orthogonal base. The dimensions of the OBB are
then computed, and the algorithm is terminated.
The third detrimental case is when the construction of a tetrahedron (either
the upper or the lower) fails because the computed fourth point lies in the plane
10 1.FastComputationofTight‐FittingOrientedBoundingBoxes
of the already-found base triangle. When this happens, the arising triangles of the
degenerate tetrahedron are simply ignored by the algorithm; that is, they are not
used in the search for better OBB axes.
1.3Evaluation
To evaluate the DiTO algorithm, we compared it to three other methods referred
to here as AABB, PCA, and brute force (BF). The AABB method simply com-
putes an axis-aligned bounding box, which is then used as an OBB. While this
method is expected to be extremely fast, it also produces OBBs of poor quality in
general.
The PCA method was first used to compute OBBs by Gottschalk et al.
[1996]. It works by first creating a representation of the input model’s shape in
the form of a covariance matrix. High-quality OBB axes are then assumed to be
given by the eigenvectors of this matrix. As an implementation of the PCA meth-
od, we used code from Gottschalk et al.’s RAPID source package. This code
works on the triangles of the model and so has linear complexity in the input size.
The naive BF method systematically tests
9
0909
0
different orientations
by incrementing Euler angles one degree at a time using a triple-nested loop. This
method is of course extremely slow, but in general it is expected to create OBBs
of high quality which is useful for comparison to the other algorithms. To avoid
having the performance of BF break down completely, only 26 extremal points
are used in the iterations. This subset is selected initially in the same way as in
the DiTO algorithm.
All the algorithms were implemented in C/C++. The source code was com-
piled using Microsoft Visual Studio 2008 Professional Edition and run single-
threaded using a laptop with an Intel Core2 Duo T9600 2.80 GHz processor and
4 GB RAM. The input data sets were triangle meshes with varying shapes and
varying geometric complexity. The vertex and triangle counts of these meshes
are summarized in Table 1.2. Screenshots of the triangle meshes are shown in
Figure 1.4.
To gather statistics about the quality of the computed boxes, each algorithm
computes an OBB for 100 randomly generated rotations of the input meshes. We
then report the average surface area
avg
A
, the minimum and maximum surface
areas
min
A
and
max
A
, as well as the average execution time
avg
t
in milliseconds. The
results are given in Table 1.3.
The BF algorithm is very slow, but it computes high-quality OBBs on aver-
age. The running times lie around one second for each mesh since the triple-
nested loop acts like a huge hidden constant factor. The quality of the boxes var-
1.3Evaluation
Tab
l
tion
o
ies
s
ing
f
pute
co
mp
T
fast
e
The
nee
d
vert
i
the
n
size
larg
e
Fi
g
l
e 1.2. The nu
m
o
f the algorith
m
s
lightly due t
o
f
rom
t
he incr
e
d by the o
t
p
aring them
t
T
he DiTO a
l
e
r than the P
C
big perform
a
d
s
t
o iterate
o
i
ces. For con
n
n
umber of v
e
of the verte
x
e
as the corre
s
g
ure 1.4. Visu
a
Model
Pencil
Teddy
Frog
Chair
Bunny
Hand
m
ber of vertic
e
m
s.
o
the testing
o
e
mental step
p
t
her algorit
h
t
o the sizes o
f
l
gorithm is v
e
C
A algorith
m
a
nce differe
n
o
ver the poly
g
n
ected triang
l
e
rtices, and e
a
x
data that t
h
s
ponding dat
a
a
lizations of th
e
Vertices
1234
1598
4010
7260
32,875
327,323
e
s and triangle
o
f somewhat
p
ing of the E
u
h
ms, howev
e
f
the boxes c
o
e
ry competit
i
m
, although b
o
ce is mainly
g
on data inst
e
l
e meshes, th
e
a
ch triangle
h
h
e PCA met
h
a
for the DiT
O
e
triangle mes
h
Trian
g
2448
3192
7964
14,372
65,536
654,66
6
s for the poly
g
unevenly di
s
u
ler angles.
T
e
r, can be
m
o
mputed by t
h
i
ve. For exa
m
o
th methods
a
due to the
fa
e
ad of iterati
n
e number of
t
h
as three ver
t
h
od processe
s
O
algorithm.
h
es used for e
v
g
les
6
g
on meshes us
e
s
tributed orie
n
T
he quality o
f
m
easured q
u
h
e BF metho
d
m
ple, it runs
a
re fast linea
r
fa
ct tha
t
the
P
n
g over the l
i
triangles is r
o
t
ices. Theref
o
s
is roughly
v
aluation of th
e
e
d for evalua-
n
tations aris-
f
boxes com-
u
ite well by
d
.
significantly
r
algorithms.
P
CA method
i
st of unique
o
ughly twice
o
re, the total
six times as
e
algorithms.
11
12 1.FastComputationofTight‐FittingOrientedBoundingBoxes
Pencil Chair
Method
av
g
A
min
A
ma
x
A
av
g
t
Method
av
g
A
min
A
ma
x
A
av
g
t
AABB 1.4155 0.2725 2.1331 0.02 AABB 7.1318 4.6044 8.6380 0.07
PCA 0.2359 0.2286 0.2414 0.51 PCA 4.7149 4.7139 4.7179 1.87
BF 0.2302 0.2031 0.2696 1009 BF 3.6931 3.6106 4.6579 1047
DiTO-12 0.2316 0.1995 0.2692 0.11 DiTO-12 3.8261 3.6119 4.1786 0.35
DiTO-14 0.2344 0.1995 0.2707 0.09 DiTO-14 3.8094 3.6129 4.2141 0.25
DiTO-20 0.2306 0.1995 0.2708 0.14 DiTO-20 3.8213 3.6164 3.9648 0.37
DiTO-26 0.2331 0.1995 0.2707 0.15 DiTO-26 3.8782 3.6232 4.0355 0.35
DiTO-32 0.2229 0.1995 0.2744 0.20 DiTO-32 3.8741 3.6227 3.9294 0.49
Teddy Bunny
Method
av
g
A
min
A
ma
x
A
av
g
t
Method
av
g
A
min
A
ma
x
A
av
g
t
AABB 3.9655 3.5438 4.3102 0.02 AABB 5.7259 4.7230 6.4833 0.19
PCA 4.0546 4.0546 4.0546 0.60 PCA 5.2541 5.2540 5.2541 8.76
BF 3.3893 3.3250 3.5945 1043 BF 4.6934 4.5324 4.9091 1041
DiTO-12 3.7711 3.5438 4.0198 0.14 DiTO-12 4.9403 4.5635 5.7922 1.13
DiTO-14 3.7203 3.5438 3.9577 0.12 DiTO-14 4.9172 4.5810 5.6695 0.98
DiTO-20 3.7040 3.5438 3.8554 0.19 DiTO-20 4.8510 4.5837 5.5334 1.55
DiTO-26 3.7193 3.5438 3.8807 0.16 DiTO-26 4.7590 4.5810 5.3967 1.42
DiTO-32 3.7099 3.5438 3.8330 0.22 DiTO-32 4.7277 4.6552 5.1037 2.04
Frog Hand
Method
av
g
A
min
A
ma
x
A
av
g
t
Method
av
g
A
min
A
ma
x
A
av
g
t
AABB 4.6888 3.0713 5.7148 0.07 AABB 2.8848 2.4002 3.2693 1.98
PCA 2.6782 2.6782 2.6782 1.14 PCA 2.5066 2.5062 2.5069 86.6
BF 2.7642 2.6582 3.5491 1037 BF 2.3071 2.2684 2.4531 1067
DiTO-12 2.7882 2.6652 3.0052 0.28 DiTO-12 2.3722 2.2946 2.5499 11.8
DiTO-14 2.7754 2.6563 2.9933 0.24 DiTO-14 2.3741 2.2914 2.5476 10.0
DiTO-20 2.7542 2.6602 2.9635 0.40 DiTO-20 2.3494 2.2805 2.4978 15.5
DiTO-26 2.7929 2.6579 3.0009 0.36 DiTO-26 2.3499 2.2825 2.5483 14.5
DiTO-32 2.7685 2.6538 2.9823 0.44 DiTO-32 2.3372 2.2963 2.4281 20.6
Table 1.3. The average, minimum, and maximum area as well as the average execution time in ms
over 100 random orientations of the input meshes.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.