1.3Evaluation 13
The DiTO algorithm also produces oriented boxes of relatively high quality.
For all meshes except Frog, the DiTO algorithm computes OBBs with smaller
surface areas than the PCA method does. For some of the models, the difference
is significant, and for the Teddy model, the PCA method computes boxes that are
actually looser fitting than the naive AABB method does. The DiTO algorithm,
however, is in general more sensitive than the PCA method to the orientation of
the input meshes as can be seen in the minimum and maximum area columns.
Among the included DiTO instances, there seems to be a small quality im-
provement for increasing k values for some of the models. DiTO-32 seems to
compute the best boxes in general. The quality difference of the computed boxes,
however, is quite small in most cases. Therefore, since DiTO-14 is approximately
twice as fast as DiTO-32, it is probably the preferable choice when speed is a
prioritized factor.
BoundingVolumeHierarchyQuality
We also tried the different OBB fitting algorithms for OBB hierarchy construc-
tion to evaluate them on different levels of geometric subdivision. On models
with smooth curvature, the geometry enclosed on the lower levels of the hierar-
chy tend to get an increasing flatness with each level, and we wanted to compare
the algorithms on this type of input. It turns out that our algorithm handles this
better than the other algorithms we tested. This is visualized using the Bunny
model in Figure 1.5.
For each one of the six test models, we applied the OBB fitting algorithms
during the hierarchy construction. These test runs have been done only once for
each model and OBB algorithm, with the model kept in its original local coordi-
nate system, due to the longer construction times for whole hierarchies. Table 1.4
shows the total surface areas of the resulting hierarchies.
Although the RAPID source package also includes a hierarchy builder, we
extracted the functions involved in fitting the OBBs and plugged them into our
own hierarchy builder since it uses a more elaborate strategy for partitioning
primitives that generally creates better hierarchy structures, albeit at a higher
computational cost. The table does not show execution times because the time for
hierarchy construction is influenced too much by factors other than the time to
fit the bounding volumes, such as the strategy used to find clusters in the geome-
try to build a good tree structure. However, the construction times were about the
same with all the algorithms. Note also that the BF algorithm is not included
since it gives unreasonably long construction times.
14 1.FastComputationofTight‐FittingOrientedBoundingBoxes
Figure 1.5. Levels 0, 6, 9, and 12 of OBB hierarchies built using AABBs (leftmost col-
umn), PCA (middle column), and DiTO-20 (rightmost column). As can be seen in the
magnified pictures in the bottom row, PCA and DiTO both produce OBBs properly
aligned with the curvature of the model, but the boxes produced by PCA have poor mutu-
al orientations with much overlap between neighboring boxes.
The algorithm used for building the tree structure is a top-down algorithm,
where the set of primitives is recursively partitioned into two subsets until there
is only one primitive left, which is then stored in a leaf node. Before partitioning
the primitives in each step, the selected OBB fitting procedure is called to create
an OBB to store in the node. This means that the procedure is called once for
every node of the tree. To partition the primitives under a node, we use a strategy
that tries to minimize the tree’s total surface area, similar to that used by Wald et
al. [2007] for building AABB hierarchies.
1.3Evaluation 15
Model AABB PCA DiTO-12 DiTO-14 DiTO-20 DiTO-26 DiTO-32
Pencil 9.64676 4.05974 3.03241 3.03952 3.03098 3.0111 3.00679
Teddy 90.6025 86.2482 71.9596 74.071 74.3019 73.1202 74.7392
Frog 56.1077 52.2178 42.7492 41.9447 41.6065 41.2272 42.0487
Chair 81.3232 92.9097 64.5399 66.9878 64.2992 65.5366 64.8454
Bunny 170.71 171.901 125.176 122.108 119.035 119.791 119.172
Hand 112.625 117.241 50.8327 49.8038 50.0446 48.8985 49.7918
Table 1.4. Total surface areas of OBB hierarchies built using the different OBB fitting
algorithms.
As Table 1.4 shows, the DiTO algorithms create better trees than the other
two algorithms do. An implication of the increasing flatness on the lower hierar-
chy levels is that the first base triangle more accurately captures the spatial ex-
tents of the geometry, and that the two additional tetrahedra get small heights. It
is therefore likely that the chosen OBB most often is found from the base triangle
and not from the triangles in the tetrahedra. The PCA fitter frequently produces
poor OBBs, and in three cases (Chair, Bunny, and Hand), produces even worse
OBBs than the AABB method does. It is also never better than any of the DiTO
versions.
Interesting to note is that there is a weak correspondence between the number
of extremal directions used in DiTO and the tree quality. This can be partly ex-
plained by the fact that the directions included in a smaller set are not always in-
cluded in a larger set, which, for example, is the case in DiTO-14 versus
DiTO-12. This means that for some models, fewer directions happen to give bet-
ter results than a larger number of directions. Another part of the explanation is
that the tested OBBs are only fitted to the set of extracted extremal points S,
which means that good-quality OBBs might be missed because worse OBBs get
better surface areas on the selected extremal points. All this suggests that execu-
tion time can be improved by using fewer extremal directions (see Table 1.3),
while not much OBB quality can be gained by using more.
Note that the AABB hierarchies sometimes have somewhat undeservedly
good figures because the models were kept in their local coordinate systems dur-
ing the construction. This gives the AABB an advantage in, for example, Pencil
and Chair, where much of the geometry is axis-aligned.
16 1.FastComputationofTight‐FittingOrientedBoundingBoxes
1.4OptimizationUsingSIMDInstructions
By using data-parallelism at the instruction level, the execution speed of the
DiTO algorithm can be improved substantially. As an initial case study, a new
version of DiTO-14 has been written that utilizes Intel’s Streaming SIMD
Extensions (SSE). For this version of the algorithm, the vertices are pre-stored as
groups of four vertices, which can be packed componentwise into three full SSE
registers, one for each coordinate component. For example, the first four vertices
0000
1111
2222
3333
,, ,
,, ,
,, ,
,, ,
x
yz
x
yz
x
yz
x
yz
p
p
p
p
are stored in the first vertex group as three arrays
00123
00123
00123
,,, ,
,,, ,
,,, .
x
xxx
yyyy
zzzz
X
Y
Z
Usually, this kind of data structure is referred to as structure of arrays (SoA).
There are two main passes in the algorithm, and they are the two loops over
all input vertices. These two passes can be implemented easily using SSE. First,
consider the last loop over all input vertices that determines the final dimensions
of the OBB by computing minimum and maximum projection values on the
given axes. This operation is ideal for an SSE implementation. By using the
mentioned SoA representation, four dot products are computed simultaneously.
Furthermore, the branches used in the scalar version to keep track of the most
extremal projection values are eliminated by using the far more efficient
minps
and
maxps SSE instructions.
Similarly, the first loop over all points of the model can also benefit a lot
from using SSE since extremal projections along different axes are also
computed. However, in this case the actual extremal points along the given
directions are wanted as outputs in addition to the maximum and minimum
projection values. Therefore, the solution is slightly more involved, but the loop
can still be converted to quite efficient SSE code using standard techniques for
branch elimination.
As shown in Table 1.5, our initial SIMD implementation of DiTO-14 is
significantly faster than the corresponding scalar version. Speed-ups greater than
1.5DiscussionandFutureWork 17
Model t
v
t
s
Pencil 0.09 0.035 2.6
Teddy 0.12 0.04 3.0
Frog 0.24 0.08 3.0
Chair 0.25 0.08 3.1
Bunny 0.98 0.21 4.7
Hand 10.0 1.99 5.0
Table 1.5. The execution time t for the scalar version of DiTO-14 versus
v
t
for the
vectorized SSE version. All timings are in ms, and the speed-up factors s are listed in the
last column.
four times are achieved for the most complex models, Bunny and Hand. To be as
efficient as possible for models with fewer input points, the remaining parts of
the algorithm have to be converted to SSE as well. This is particularly true when
building a bounding volume hierarchy, since most of the boxes in the hierarchy
only enclose small subsets of vertices.
1.5DiscussionandFutureWork
The assumption that the constructed ditetrahedron is a characterizing shape for a
tight-fitting OBB seems valid. According to our experiments, the proposed algo-
rithm is faster and gives better OBBs than do algorithms based on the PCA
method. Also, when building hierarchies of OBBs, our method gives more accu-
rate approximations of the geometry on the lower hierarchy levels, where the ge-
ometry tends to become flatter with each level. In addition, our method is more
general since it requires no knowledge of the polygon data.
We have not found any reliable data indicating which instance of the DiTO
algorithm is best. The tested variations produce quite similar results in terms of
surface area, although in some cases, there seems to be a small quality advantage
with increasing sampling directions. For construction of OBB trees, however, it
may be unnecessarily slow to use many sampling directions since n is less than k
for a large number of nodes at the lower hierarchy levels.
Although the presented heuristics work fine for fast OBB computation, it
would still be interesting to try to improve the algorithm further. Perhaps the con-
structed ditetrahedron can be utilized more intelligently when searching for good
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.