OBBTree: A Hierarchical Structure for Rapid Interference Detection
University of North Carolina at Chapel Hill
Abstract
We present a data structure and an algorithm for efficient and exact interference detection amongst complex models undergoing rigid motion. The algorithm is applicable to all general polygonal models. It pre-computes a hierarchical representation of models using tight-fitting oriented bounding b ox trees (OBBTrees). At runtime, the algorithm traverses two such trees and tests for overlaps between 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…
Citation impact
- FWCI
- 38.48
- Percentile
- 100%
- References
- 30
Authors
3Topics & keywords
- Bounding overwatch
- Bounding volume
- Computer science
- Interference (communication)
- Representation (politics)
- Algorithm
- Data structure
- Hierarchical database model