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.