18 1.FastComputationofTight‐FittingOrientedBoundingBoxes
OBB axes. As it is now, we have only considered the triangles of this shape one
at a time. Furthermore, the construction of some simple shape other than the
ditetrahedron may be found to be more advantageous for determining the OBB
axes.
Finally, note that DiTO can be adapted to compute oriented bounding rectan-
gles in two dimensions. The conversion is straightforward. In this case, the large
base triangle simplifies to a base line segment, and the ditetrahedron simplifies to
a ditriangle (i.e., two triangles connected by the base line segment). There are
better algorithms available in two dimensions such as the rotating calipers meth-
od, which runs in

On time, but these methods require the convex hull of the
vertices to be present [Toussaint 1983].
References
[Barequet and Har-Peled 1999] Gill Barequet and Sariel Har-Peled. “Efficiently Approx-
imating the Minimum-Volume Bounding Box of a Point Set in Three Dimen-
sions.” SODA ’99: Proceedings of the Tenth Annual ACM-SIAM Symposium on
Discrete Algorithms, 1999, pp. 98–91.
[Dimitrov et al. 2009] Darko Dimitrov, Christian Knauer, Klaus Kriegel, and Günter
Rote. “Bounds on the Quality of the PCA Bounding Boxes.” Computational Ge-
ometry: Theory and Applications 42 (2009), pp. 772–789.
[Ericson 2005] Christer Ericson. Real-Time Collision Detection. San Francisco: Morgan
Kaufmann, 2005.
[Gottschalk et al. 1996] Stefan Gottschalk, Ming Lin, and Dinesh Manocha. “OBBTree:
A Hierarchical Structure for Rapid Interference Detection.” Proceedings of SIG-
GRAPH 1996, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings,
Annual Conference Series, ACM, pp. 171–180.
[Gottschalk 2000] Stefan Gottschalk. “Collision Queries using Oriented Bounding Box-
es.” PhD dissertation, University of North Carolina at Chapel Hill, 2000.
[Larsson et al. 2007] Thomas Larsson, Tomas Akenine-Möller, and Eric Lengyel. “On
Faster Sphere-Box Overlap Testing.” Journal of Graphics Tools 12:1 (2007), pp.
3–8.
[Larsson 2008] Thomas Larsson. “An Efficient Ellipsoid-OBB Intersection Test.” Jour-
nal of Graphics Tools 13:1 (2008), pp. 31–43.
[O’Rourke 1985] Joseph O’Rourke. “Finding Minimal Enclosing Boxes.” International
Journal of Computer and Information Sciences 14:3 (June 1985), pp. 183–199.
References 19
[Toussaint 1983] Godfried Toussaint. “Solving Geometric Problems with the Rotating
Calipers.” Proceedings of IEEE Mediterranean Electrotechnical Conference 1983,
pp. 1–4.
[Wald et al. 2007] Ingo Wald, Solomon Boulos, and Peter Shirley. “Ray Tracing De-
formable Scenes Using Dynamic Bounding Volume Hierarchies.” ACM Transac-
tions on Graphics 26:1 (2007).
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset