OBBTree
- 1 August 1996
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 171-180
- https://doi.org/10.1145/237170.237244
Abstract
We present a data structure and an algorithm for efficient and exact interference detection amongst com- plex models undergoing rigid motion. The algorithm is ap- plicable to all general polygonal models. It pre-computes a hierarchical representation of models using tight-fitting oriented bounding box trees (OBBTrees). At runtime, the algorithm traverses two such trees and tests for overlaps be- tween oriented bounding boxes based on a separating axis theorem, which takes less than 200 operations in practice. It has been implemented and we compare its performance with other hierarchical data structures. In particular, it can robustly and accurately detect all the contacts between large complex geometries composed of hundreds of thousands of polygons at interactive rates.Keywords
This publication has 24 references indexed in Scilit:
- Interval arithmetic recursive subdivision for implicit functions and constructive solid geometryACM SIGGRAPH Computer Graphics, 1992
- Curved surfaces and coherence for non-penetrating rigid body simulationACM SIGGRAPH Computer Graphics, 1990
- Geometric collisions for time-dependent parametric surfacesACM SIGGRAPH Computer Graphics, 1990
- Collision detection by four-dimensional intersection testingIEEE Transactions on Robotics and Automation, 1990
- Realistic animation of rigid bodiesACM SIGGRAPH Computer Graphics, 1988
- Collision Detection and Response for Computer AnimationACM SIGGRAPH Computer Graphics, 1988
- A fast procedure for computing the distance between complex objects in three-dimensional spaceIEEE Journal on Robotics and Automation, 1988
- Intersection of convex objects in two and three dimensionsJournal of the ACM, 1987
- Finding minimal enclosing boxesInternational Journal of Parallel Programming, 1985
- Improved Computational Methods for Ray TracingACM Transactions on Graphics, 1984