OBBTree: a hierarchical structure for rapid interference detection

Stefan GottschalkMing C LinDinesh Manocha

article1996SIGGRAPH2,403 citations

Introduces oriented bounding box trees and a fast separating-axis overlap test to achieve real-time, exact collision detection between complex polygonal models undergoing rigid motion.

Listen

Simulating complex physical systems and performing tolerance analysis in computer-aided design require fast and exact collision detection. Traditional methods using bounding spheres or axis-aligned boxes struggle when unstructured, complex polygonal models come into close contact, resulting in severe performance bottlenecks due to the sheer volume of pairwise overlap checks required.

The article evaluates whether hierarchical representations based on oriented bounding boxes—rectangular boxes aligned arbitrarily in three-dimensional space—can deliver rapid, exact collision detection for large, unstructured polygonal models at interactive rates.

To address this question, the authors designed algorithms to compute tight-fitting bounding box hierarchies using statistical analysis of polygonal surfaces and introduced an overlap test based on a separating axis theorem. They implemented the system in a software package called RAPID and evaluated its performance through mathematical analysis and empirical simulations involving complex environments with up to hundreds of thousands of polygons.

The analysis demonstrates that the separating axis overlap test executes in roughly 5 to 7 microseconds (requiring under 200 operations in the worst case), which is one to two orders of magnitude faster than conventional linear programming and closest-feature tests. Furthermore, when approximating low-curvature geometry, the bounding boxes achieve quadratic convergence, requiring asymptotically fewer overlap tests than sphere trees or axis-aligned boxes in close-proximity scenarios. In interactive simulations involving dynamic models with hundreds of thousands of polygons, the system determined exact contacts in 4.2 to 6.9 milliseconds per step, outperforming previous methods that took a fraction of a second on smaller models.

These findings indicate that oriented bounding box hierarchies significantly reduce computational overhead in high-density contact scenarios without requiring pre-cleaned geometry or closed-form motion constraints. For engineering and virtual prototyping applications, this substantially cuts query times, lowers latency in interactive systems, and ensures robust contact resolution without manual geometry cleanup.

Organizations developing computer-aided design, robotics, or physics-based simulation tools should consider adopting oriented bounding box hierarchies, especially for close-proximity scenarios. Future work should focus on standardizing evaluation benchmarks, extending the technique to deformable objects and ray tracing, and investigating hardware or assembly-level implementations of the overlap test to maximize performance.

The reported performance advantages apply primarily to scenarios involving finely tessellated surfaces in close proximity; environments featuring highly irregular shapes or coarse geometries may not experience the same quadratic improvements. Memory requirements are approximately 412 bytes per triangle, representing an operational trade-off that should be accounted for when deploying on memory-constrained systems.

United States Army Research Office University of North Carolina at Chapel Hill contracts detection algorithm hierarchical structures Detection Interference Detection Two

OBB/OBBT.html Gottschalk et al (1996).pdf

Paper: Least-Squares Fitting of Two 3-D Point Sets, K. S. Arun et al. (1987). This foundational paper establishes the closed-form method for least-squares rigid-body alignment of 3D point sets that the OBBTree hierarchy relies on for computing relative motion and spatial transformations.
Paper: R-trees: a dynamic index structure for spatial searching, Antonin Guttman (1984). Understanding this introduction to dynamic spatial index structures provides the necessary background in hierarchical bounding volumes essential for grasping OBBTree collision queries.

Paper: A volumetric method for building complex models from range images, B. Curless et al. (1996). This work builds directly on rapid spatial data structures and surface representations to integrate multiple range images into seamless volumetric models.

Cover for OBBTree: a hierarchical structure for rapid interference detection

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 box 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 of hundreds of thousands of polygons at interactive rates.

Topics

contracts detection algorithm hierarchical structures

Keywords

Detection Interference Detection Two OBBs Hierarchical Models Box Bounding Overlap Algorithms

1 Introduction
2 Previous Work
3 Hierarchical Methods & Cost Equation
4 Building an OBBTree
5 Fast Overlap Test for OBBs
6 OBB’s vs. other Volumes
7 Implementation and Performance
7.1 Robustness and Accuracy
7.2 Performance
7.3 Comparison with Other Approaches
7.4 RAPID and benchmarks
8 Extensions and Future Work
9 Conclusion
10 Acknowledgements
References

Knowls

Knowl 1 — Separating Axis Theorem for Oriented Bounding Boxes
theoretical result
Two disjoint convex polytopes in $\mathbb{R}^3$ can always be separated by a plane that is parallel to a face of either polytope, or parallel to an edge from each polytope. Consequently, two convex polytopes are disjoint if and only if there exists a separating axis orthogonal to a face of either polytope or orthogonal to an edge from each polytope.

For two oriented bounding boxes (OBBs), each box has $3$ mutually orthogonal face orientations and $3$ mutually orthogonal edge directions. Therefore, exactly $15$ candidate separating axes are necessary and sufficient to determine whether two OBBs overlap:
1. $3$ axes parallel to the face normals of the first box.
2. $3$ axes parallel to the face normals of the second box.
3. $9$ axes formed by the pairwise cross products of edge directions from both boxes ( $3 \times 3 = 9$ ).
If the intervals formed by projecting the two boxes onto any of these $15$ axes do not overlap, that axis is a separating axis and the boxes are disjoint. If the projected intervals overlap along all $15$ axes, the two OBBs intersect.
Knowl 2 — Fast OBB-OBB Overlap Detection Algorithm
algorithm
Given two oriented bounding boxes $A$ and $B$ , where $B$ is positioned relative to $A$ by a $3 \times 3$ rotation matrix $R = [R_{ij}]$ and a $3 \times 1$ translation vector $T = (T_1, T_2, T_3)^T$ , the overlap test evaluates whether a separating axis exists among $15$ candidate axes.

Let $a = (a_1, a_2, a_3)$ and $b = (b_1, b_2, b_3)$ be the half-dimensions (radii) of $A$ and $B$ , respectively, and let $A_1, A_2, A_3$ and $B_1, B_2, B_3$ denote their unit axis vectors. For any unit axis $L$ , the projected radius of $A$ is $r_A = \sum_{i=1}^3 |a_i (A_i \cdot L)|$ , the projected radius of $B$ is $r_B = \sum_{i=1}^3 |b_i (B_i \cdot L)|$ , and the projected distance between box centers is $|T \cdot L|$ . The intervals are disjoint if: $|T \cdot L| > r_A + r_B$

When $L$ is a box axis or edge cross-product, terms simplify using elements of $R$ and $T$ . The test evaluates up to $15$ simplified scalar inequalities and exits immediately upon finding a satisfied condition:
Input: Box A dimensions $a=(a_1,a_2,a_3)$ , Box B dimensions $b=(b_1,b_2,b_3)$ , rotation $R$ , translation $T$
Output: true if $A$ and $B$ overlap, false otherwise
// Precompute absolute values of rotation matrix elements
for $i = 1$ to 3 do
    for $j = 1$ to 3 do
         $Q_{ij} = |R_{ij}| + \epsilon$
    end
end
// 3 Face axes of Box A ( $L = A_1, A_2, A_3$ )
if $|T_1| > a_1 + b_1 Q_{11} + b_2 Q_{12} + b_3 Q_{13}$ then return false
if $|T_2| > a_2 + b_1 Q_{21} + b_2 Q_{22} + b_3 Q_{23}$ then return false
if $|T_3| > a_3 + b_1 Q_{31} + b_2 Q_{32} + b_3 Q_{33}$ then return false
// 3 Face axes of Box B ( $L = B_1, B_2, B_3$ )
if $|T_1 R_{11} + T_2 R_{21} + T_3 R_{31}| > b_1 + a_1 Q_{11} + a_2 Q_{21} + a_3 Q_{31}$ then return false
if $|T_1 R_{12} + T_2 R_{22} + T_3 R_{32}| > b_2 + a_1 Q_{12} + a_2 Q_{22} + a_3 Q_{32}$ then return false
if $|T_1 R_{13} + T_2 R_{23} + T_3 R_{33}| > b_3 + a_1 Q_{13} + a_2 Q_{23} + a_3 Q_{33}$ then return false
// 9 Cross-product axes ( $L = A_i \times B_j$ )
if $|T_3 R_{21} - T_2 R_{31}| > a_2 Q_{31} + a_3 Q_{21} + b_2 Q_{13} + b_3 Q_{12}$ then return false // $A_1 \times B_1$
if $|T_3 R_{22} - T_2 R_{32}| > a_2 Q_{32} + a_3 Q_{22} + b_1 Q_{13} + b_3 Q_{11}$ then return false // $A_1 \times B_2$
if $|T_3 R_{23} - T_2 R_{33}| > a_2 Q_{33} + a_3 Q_{23} + b_1 Q_{12} + b_2 Q_{11}$ then return false // $A_1 \times B_3$
if $|T_1 R_{31} - T_3 R_{11}| > a_1 Q_{31} + a_3 Q_{11} + b_2 Q_{23} + b_3 Q_{22}$ then return false // $A_2 \times B_1$
if $|T_1 R_{32} - T_3 R_{12}| > a_1 Q_{32} + a_3 Q_{12} + b_1 Q_{23} + b_3 Q_{21}$ then return false // $A_2 \times B_2$
if $|T_1 R_{33} - T_3 R_{13}| > a_1 Q_{33} + a_3 Q_{13} + b_1 Q_{22} + b_2 Q_{21}$ then return false // $A_2 \times B_3$
if $|T_2 R_{11} - T_1 R_{21}| > a_1 Q_{21} + a_2 Q_{11} + b_2 Q_{33} + b_3 Q_{32}$ then return false // $A_3 \times B_1$
if $|T_2 R_{12} - T_1 R_{22}| > a_1 Q_{22} + a_2 Q_{12} + b_1 Q_{33} + b_3 Q_{31}$ then return false // $A_3 \times B_2$
if $|T_2 R_{13} - T_1 R_{23}| > a_1 Q_{23} + a_2 Q_{13} + b_1 Q_{32} + b_2 Q_{31}$ then return false // $A_3 \times B_3$
return true
The full test requires at most $15$ comparisons, $60$ additions/subtractions, $81$ multiplications, and $24$ absolute values (under $200$ operations in the worst case, and approximately $100$ operations on average due to early exit).
Knowl 3 — Tight-Fitting OBB Generation via Continuous Surface Covariance Integration
algorithm
To fit an oriented bounding box around a group of polygons without distortion from interior vertices or non-uniform vertex sampling, the orientation axes are computed from the continuous surface integral of the convex hull of the polygon vertices.

Let the convex hull be tessellated into $n$ triangles. For the $i$ -th triangle with vertices $p^i, q^i, r^i \in \mathbb{R}^3$ , its area is $m^i = \frac{1}{2}\|(q^i - p^i) \times (r^i - p^i)\|$ . Any point on the triangle is parameterized by $x^i = p^i + s(q^i - p^i) + t(r^i - p^i)$ for $s, t \in [0, 1]$ and $s+t \le 1$ .

The mean centroid $\mu \in \mathbb{R}^3$ of the convex hull surface is computed in closed form as: $\mu = \frac{1}{n} \sum_{i=1}^n \left( \frac{1}{m^i} \int_0^1 \int_0^{1-t} x^i \, ds \, dt \right) = \frac{1}{6n} \sum_{i=1}^n \frac{1}{m^i} (p^i + q^i + r^i)$

Let $\bar{p}^i = p^i - \mu$ , $\bar{q}^i = q^i - \mu$ , and $\bar{r}^i = r^i - \mu$ . The entries $C_{jk}$ ( $1 \le j, k \le 3$ ) of the $3 \times 3$ covariance matrix $C$ are given by: $C_{jk} = \frac{1}{24n} \sum_{i=1}^n m^i \left[ (\bar{p}_j^i + \bar{q}_j^i + \bar{r}_j^i)(\bar{p}_k^i + \bar{q}_k^i + \bar{r}_k^i) + \bar{p}_j^i \bar{p}_k^i + \bar{q}_j^i \bar{q}_k^i + \bar{r}_j^i \bar{r}_k^i \right]$

The algorithm computes the three mutually orthogonal eigenvectors of the symmetric matrix $C$ , normalizes them to unit length, and adopts them as the coordinate axes of the bounding box. The extremal vertices of the bounded geometry are projected onto these basis vectors to determine the box extents and origin.
Knowl 4 — Top-Down Recursive OBBTree Construction
algorithm
An OBBTree is constructed top-down by recursively partitioning a collection of input polygons:
Input: Set of polygons $P$
Output: Root node of OBBTree hierarchy enclosing $P$
Function BuildOBBTree(P):
    node = AllocateNode()
    Compute tight-fitting OBB for $P$ using surface covariance integration
    Store box center, orientation basis, and dimensions in node

    if $|P| \le 1$ or $P$ is indivisible then
        node.isLeaf = true
        node.triangles = $P$
        return node
    end

    // Subdivision: Split along the longest box axis
    axis = longest axis of node's OBB
    splitPoint = mean centroid $\mu$ of polygon vertices
    partition plane = plane orthogonal to axis passing through splitPoint

    Partition $P$ into $P_1$ and $P_2$ based on which side of the plane polygon centers lie

    // If longest axis cannot partition $P$ , try second longest, then shortest
    if $P_1 = \emptyset$ or $P_2 = \emptyset$ then
        Try partitioning along second longest axis
    end
    if $P_1 = \emptyset$ or $P_2 = \emptyset$ then
        Try partitioning along shortest axis
    end
    if $P_1 = \emptyset$ or $P_2 = \emptyset$ then
        node.isLeaf = true
        node.triangles = $P$
        return node
    end

    node.leftChild = BuildOBBTree( $P_1$ )
    node.rightChild = BuildOBBTree( $P_2$ )
    return node
Choosing the split coordinate as the median center point produces a balanced tree of depth $O(\log n)$ for $n$ polygons. The total tree construction complexity is $O(n \log^2 n)$ when building convex hulls at each recursive level, and $O(n \log n)$ if fitting is performed directly on triangle vertices without convex hulls.
Knowl 5 — Asymptotic Tightness and Bounding Volume Complexity for Low-Curvature Surfaces
theoretical result
Let a bounding volume $B$ enclose a surface patch $G$ . The tightness $\epsilon$ of $B$ with respect to $G$ is its Hausdorff distance $\epsilon = \max_{b \in B} \min_{g \in G} \text{dist}(b, g)$ , the diameter $d$ is $d = \max_{g, h \in G} \text{dist}(g, h)$ , and the aspect ratio is $\rho = \epsilon / d$ .

For surfaces with low constant curvature $r$ (e.g., a spherical surface of large radius):
1. Axis-Aligned Bounding Boxes (AABBs) and Spheres: The aspect ratio $\rho$ remains approximately invariant between parent and child nodes as dimensions are halved ( $ho \approx \text{const}$ ). Thus, tightness depends linearly on diameter: $\epsilon = O(d)$ . Covering a surface of area $A$ with $N$ equal-sized volumes requires $d = O(\sqrt{A/N})$ , yielding $\epsilon = O(\sqrt{A/N})$ .
2. Oriented Bounding Boxes (OBBs): Because an OBB aligns with the local principal surface frame, $\epsilon = r - r\cos\theta = d^2 / (8r)$ (using $d = 2r\sin\theta$ and small-angle approximation $\cos\theta \approx 1 - \theta^2/2$ ). Thus, tightness depends quadratically on diameter: $\epsilon = O(d^2)$ . Covering area $A$ with $N$ OBBs yields $\epsilon = O(A/N)$ .
To bound a surface patch to a prescribed tightness $\epsilon$ , OBBTrees require $O(m)$ bounding volumes, whereas AABBTrees and sphere trees require $O(m^2)$ bounding volumes. Consequently, for surfaces in parallel close proximity, OBBTrees require asymptotically fewer bounding volume overlap tests as clearance $\epsilon \to 0$ .
Knowl 6 — Hierarchical Interference Detection Cost Formulation
equation
The total computational cost $T$ of detecting interference between two models using bounding volume hierarchies is formulated as: $T = N_v C_v + N_p C_p$ where:
- $T$ : Total interference detection computation time.
- $N_v$ : Number of bounding volume pair overlap tests performed during tree traversal.
- $C_v$ : Computational cost of testing a single pair of bounding volumes for overlap.
- $N_p$ : Number of primitive (e.g., triangle) pairs tested for intersection at the leaf level.
- $C_p$ : Computational cost of testing a single pair of geometric primitives for intersection.
While OBBs have a higher per-test overlap cost $C_v$ compared to spheres or AABBs, their tighter geometric fit dramatically reduces $N_v$ and $N_p$ when models are in close proximity.
Knowl 7 — OBB Overlap Simplification for Degenerate and Infinite Extents
model/method
The 15-axis separating axis test can be optimized for degenerate and infinite bounding volumes:
1. Degenerate OBBs (Zero Extent): When a bounding box encloses a single triangle or segment, one or more dimensions are zero. For each extent $a_i = 0$ or $b_j = 0$ , $9$ multiplications and $10$ additions are eliminated from the overlap test. The total operations across all $15$ axes scale as follows:
  - Standard Box–Box: $15$ comparisons, $60$ additions/subtractions, $81$ multiplications, $24$ absolute values.
  - Box–Rectangle (one zero extent): $15$ comparisons, $50$ additions/subtractions, $72$ multiplications, $24$ absolute values.
  - Rectangle–Rectangle (two zero extents): $15$ comparisons, $40$ additions/subtractions, $63$ multiplications, $24$ absolute values.
2. Infinite Extents (Fat Rays and Half-Planes): If an extent is infinite (e.g., $a_2 = \infty$ ), an inequality containing $a_2 |R_{32}|$ cannot be satisfied unless $R_{32} = 0$ . The test simplifies to checking $R_{32} = 0$ via a short-circuit boolean condition and omitting the infinite term from the radius summation.

Knowl 8 — Comparative Overlap Test Execution Times across Algorithms

data/table

Average time required to test overlap between two arbitrarily oriented bounding boxes on an HP 735/125 workstation demonstrates that the separating axis test is approximately one order of magnitude faster than closest features computation and 25 to 45 times faster than linear programming.

Unlike closest features computation or linear programming, the separating axis algorithm involves only fixed sequences of linear comparisons with early exit, requiring no division, square root, or iterative state maintenance.

Knowl 9 — Collision Detection Performance on Complex Synthetic Environments

data/table

Performance results for collision detection using OBBTrees (implemented in the RAPID library) on an SGI Reality Engine (90 MHz R8000 CPU, 512 MB RAM) across two complex dynamic benchmark environments:

Metric	Pipes Scenario	Wrinkled Torus Scenario
Environment Size	143,690 polygons	98,000 polygons
Object Size	143,690 polygons	20,000 polygons
Number of Steps	4,008	1,298
Total Number of Contacts	23,905	2,266
Total Box-Box Tests	1,704,187	1,055,559
Total Triangle-Triangle Tests	71,589	7,069
Total Time	16.9 s	8.9 s
Average Detection Time per Step	4.2 ms	6.9 ms
Average Time per Box Test	7.9 $\mu$ s	7.3 $\mu$ s
Average Contacts per Step	6.0	1.7

In both benchmarks, RAPID successfully detects all contact points between models composed of hundreds of thousands of polygons at interactive rates (4.2 ms to 6.9 ms per query).

Knowl 10 — Memory Layout and Storage Overhead of OBBTree Hierarchies
model/method
An OBBTree representing $n$ triangles consists of $n$ leaf boxes and $n - 1$ internal node boxes, averaging approximately $2$ bounding boxes per triangle.
- Box Node Memory: Each box data structure stores a $3 \times 3$ rotation matrix, a $3 \times 1$ translation vector (defining relative placement to its parent), pointers to its parent and two child nodes, three box dimensions (half-lengths), and a pointer/list to enclosed triangles, totaling $168$ bytes per box.
- Triangle Storage: A triangle primitive requires $9$ double-precision floating point coordinates (64-bit IEEE) plus a integer identifier, totaling $76$ bytes.
- Overall Memory Footprint: The hierarchical structure consumes approximately $412$ bytes per triangle in the model (excluding runtime dynamic allocator overhead).
Representing orientations with quaternions instead of full rotation matrices saves storage space but incurs an additional $13$ arithmetic operations per OBB overlap test.
Knowl 11 — Performance Limitations and Geometric Boundary Cases of OBBTrees
limitation
The asymptotic performance advantage of OBBTrees over AABBTrees and sphere trees is subject to several practical and geometric limitations:
1. High-Curvature Geometry: For surfaces exhibiting high curvature everywhere (such as 3D fractals), OBBs cannot achieve quadratic convergence ( $\epsilon = O(d^2)$ ), and their performance advantage degrades.
2. Coarse Tessellation: When models have coarse polygonal tessellations, the tree depth is constrained. In close-proximity queries, traversals must reach the leaves regardless of bounding volume orientation, requiring similar numbers of tests as simpler bounding volumes.
3. Non-Parallel Proximity: When objects touch at single localized points without extended parallel surfaces in close proximity, the reduction in bounding volume overlap tests $N_v$ may not compensate for the higher per-test cost $C_v$ .
4. Rank-Deficient Input: Computing the convex hull for OBB orientation via Qhull fails if the point set does not span three full dimensions (e.g., planar or collinear polygon clusters). In such degenerate cases, convex hull computation must be bypassed or projected to lower dimensions.

Coverage note — None was omitted; all key theoretical contributions, algorithms, performance models, empirical data tables, data structures, and limitations from the paper are represented.

References

1.A.Garica-Alonso, N.Serrano, and J.Flaquer. Solving the collision detection problem. IEEE Computer Graphics and Applications, 13(3):36–43, 1994.
2.J. Arvo and D. Kirk. A survey of ray tracing acceleration techniques. In An Introduction to Ray Tracing, pages 201–262, 1989.
3.D. Baraff. Curved surfaces and coherence for non-penetrating rigid body simulation. ACM Computer Graphics, 24(4):19–28, 1990.
4.B. Barber, D. Dobkin, and H. Huhdanpaa. The quickhull algorithm for convex hull. Technical Report GCG53, The Geometry Center, MN, 1993.
5.N. Beckmann, H. Kriegel, R. Schneider, and B. Seeger. The r*-tree: An efficient and robust access method for points and rectangles. Proc. SIGMOD Conf. on Management of Data, pages 322–331, 1990.
6.S. Cameron. Collision detection by four-dimensional intersection testing. Proceedings of InternationalConference on Robotics and Automation, pages 291–302, 1990.
7.S. Cameron. Approximation hierarchies and s-bounds. In Proceedings. Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 129–137, Austin, TX, 1991.
8.J. F. Canny. Collision detection for moving polyhedra. IEEE Trans. PAMI, 8:200–209, 1986.
9.B. Chazelle and D. P. Dobkin. Intersection of convex objects in two and three dimensions. J. ACM, 34:1–27, 1987.
10.J. Cohen, M. Lin, D. Manocha, and M. Ponamgi. I-collide: An interactive and exact collision detection system for large-scale environments. In Proc. of ACM Interactive 3D Graphics Conference, pages 189–196, 1995.
11.R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. John Wiley and Sons, 1973.
12.Tom Duff. Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry. ACM Computer Graphics, 26(2):131–139, 1992.
13.J. Snyder et. al. Interval methods for multi-point collisions between time dependent curved surfaces. In Proceedings of ACM Siggraph, pages 321–334, 1993.
14.E. G. Gilbert, D. W. Johnson, and S. S. Keerthi. A fast procedurefor computing the distance between objects in three-dimensionalspace. IEEE J. Robotics and Automation, vol RA-4:193–203, 1988.
15.S. Gottschalk. Separating axis theorem. Technical Report TR96-024, Department of Computer Science, UNC Chapel Hill, 1996.
16.N. Greene. Detecting intersection of a rectangular solid and a convex polyhedron. In Graphics Gems IV, pages 74–82. Academic Press, 1994.
17.J. K. Hahn. Realistic animation of rigid bodies. Computer Graphics, 22(4):pp. 299–308, 1988.
18.M. Held, J.T. Klosowski, and J.S.B. Mitchell. Evaluation of collision detection methods for virtual reality fly-throughs. In Canadian Conference on Computational Geometry, 1995.
19.B. V. Herzen, A. H. Barr, and H. R. Zatz. Geometric collisions for time-dependent parametric surfaces. Computer Graphics, 24(4):39–48, 1990.
20.P. M. Hubbard. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality, October 1993.
21.M.C. Lin.Efficient Collision Detection for Animationand Robotics. PhD thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley, December 1993.
22.M.C. Lin and Dinesh Manocha. Fast interference detection between geometric models. The Visual Computer, 11(10):542–561, 1995.
23.M. Moore and J. Wilhelms. Collision detection and response for computer animation. Computer Graphics, 22(4):289–298, 1988.
24.B. Naylor, J. Amanatides, and W. Thibault. Merging bsp trees yield polyhedral modeling results. In Proc. of ACM Siggraph, pages 115–124, 1990.
25.J. O'Rourke. Finding minimal enclosing boxes. Internat. J. Comput. Inform. Sci., 14:183–199, 1985.
26.M. Ponamgi, D. Manocha, and M. Lin. Incremental algorithms for collision detection between general solid models. In Proc. of ACM/SiggraphSymposium on Solid Modeling, pages 293–304, 1995.
27.F.P. Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, New York, 1985.
28.S. Quinlan. Efficient distance computation between non-convex objects. In Proceedings of International Conference on Robotics and Automation, pages 3324–3329, 1994.
29.A. Rappoport. The extended convex differences tree (ecdt) representation for n-dimensional polyhedra. International Journal of Computational Geometry and Applications, 1(3):227–41, 1991.
30.S. Rubin and T. Whitted. A 3-dimensional representation for fast rendering of complex scenes. In Proc. of ACM Siggraph, pages 110–116, 1980.
31.H. Samet. Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods. Addison Wesley, 1989.
32.T.W. Sederberg and S.R. Parry. Comparison of three curve intersection algorithms. Computer-Aided Design, 18(1):58–63, 1986.
33.R. Seidel. Linear programmingand convexhulls made easy. In Proc. 6th Ann. ACM Conf. on ComputationalGeometry, pages 211–215,Berkeley, California, 1990.
34.W.Bouma and G.Vanecek.Collision detection and analysis in a physically based simulation. ProceedingsEurographicsworkshop on animationand simulation, pages 191–203, 1991.
35.H. Weghorst, G. Hooper, and D. Greenberg. Improvedcomputational methods for ray tracing. ACM Transactions on Graphics, pages 52–69, 1984.
36.E. Welzl. Smallest enclosing disks (balls and ellipsoids). Technical Report B 91-09, Fachbereich Mathematik, Freie Universitat, Berlin, 1991.

Citation

MLA

Gottschalk, S., et al. “OBBTree”. Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 1996, pp. 171–80, https://doi.org/10.1145/237170.237244.

APA

Gottschalk, S., Lin, M. C., & Manocha, D. (1996). OBBTree. Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 171–180. https://doi.org/10.1145/237170.237244

Chicago

Gottschalk, S., M. C. Lin, and D. Manocha. 1996. “OBBTree”. Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, 171–80. https://doi.org/10.1145/237170.237244.

Harvard

Gottschalk, S., Lin, M.C. and Manocha, D. (1996) “OBBTree”, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, pp. 171–180. Available at: https://doi.org/10.1145/237170.237244.

Vancouver

1. Gottschalk S, Lin MC, Manocha D (1996) OBBTree. In: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, pp 171–180

BibTeX

@inproceedings{Gottschalk_1996, series={SIGGRAPH96}, title={OBBTree: a hierarchical structure for rapid interference detection}, url={http://dx.doi.org/10.1145/237170.237244}, DOI={10.1145/237170.237244}, booktitle={Proceedings of the 23rd annual conference on Computer graphics and interactive techniques}, publisher={ACM}, author={Gottschalk, S. and Lin, M. C. and Manocha, D.}, year={1996}, month=Aug, pages={171–180}, collection={SIGGRAPH96} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Separating Axis Algorithm	Closest Features	Linear Programming
5–7 $\mu$ s	45–105 $\mu$ s	180–230 $\mu$ s

OBBTree: a hierarchical structure for rapid interference detection

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Separating Axis Theorem for Oriented Bounding Boxes

Knowl 2 — Fast OBB-OBB Overlap Detection Algorithm

Knowl 3 — Tight-Fitting OBB Generation via Continuous Surface Covariance Integration

Knowl 4 — Top-Down Recursive OBBTree Construction

Knowl 5 — Asymptotic Tightness and Bounding Volume Complexity for Low-Curvature Surfaces

Knowl 6 — Hierarchical Interference Detection Cost Formulation

Knowl 7 — OBB Overlap Simplification for Degenerate and Infinite Extents