Collision queries using oriented bounding boxes

Bounding volume hierarchies (BVHs) have been used widely in collision detection algorithms. The most commonly used bounding volume types are axis-aligned bounding boxes (AABBs) and spheres, which have simple representations, compact storage, and are easy to implement. This dissertation explores the use of oriented bounding boxes (OBBs), which may be aligned with the underlying geometry to fit more tightly. We believe that OBBs historically have been used less often because previously known methods for testing OBBs for overlap were relatively expensive, good methods for automatic construction of trees of OBBs were not known, and the benefits of using OBBs were not well understood. In this dissertation we present methods for building good trees of OBBs and demonstrate their use in efficient collision detection. In particular, we present a new OBB overlap test which is more efficient than previously known methods. We also examine some of the trade-offs of using OBBs by analyzing benchmark results comparing the performances of OBBs, AABBs and spheres, and we show that OBBs can significantly outperform the latter two bounding volumes for important classes of inputs. We also present two new tools, the bounding volume test tree (BVTT) and the contact pair matrix (CPM), for analyzing collision queries. Finally, we describe the design and implementation of a software system that permits the fair comparison of algorithmic variations on BVH-based collision detection.