“OBBTree: a hierarchical structure for rapid interference detection” by Gottschalk, Lin and Manocha

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.

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. P~vceedings of International Conference on Robotics and Automation, pages 291- 302, 1990.
7. S. Cameron. Approximation hierarchies and s-bounds. In P1vceedings. 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. R 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 P~vc. of ACM Interactive 3D Graphics Conference, pages 189-196,1995.
11. R.O. Duda and RE. 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 P1vceedings ofACM Siggraph, pages 321-334, 1993.
14. E.G. Gilbert, D. W. Johnson, and S. S. Keerthi. A fast procedure for computing the distance between objects in three-dimensional space. 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 timedependent parametric surfaces. Computer Graphics, 24(4) :39-48,1990.
20. R M. Hubbard. Interactive collision detection. In P1vceedings oflEEE Symposium on Resealvh Frontiers in Virtual Reality, October 1993.
21. M.C. Lin. Efficient Collision Detection for Animation and 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 P1vc. ofACM Siggraph, pages 115-124,1990.
25. J. O’Rourke. Finding minimal enclosing boxes. Internat. J. Comput. Info~. Sci., 14:183-199,1985.
26. M. Ponamgi, D. Manocha, and M. Lin. Incremental algorithms for collision detection between general solid models. In P1vc. of ACM/Siggraph Symposium on Solid Modeling, pages 293-304,1995.
27. F.R Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, New York, 1985.
28. S. Quinlan. Efficient distance computation between non-convex objects. In P1vceedings 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 P1vc. ofACM Siggraph, pages 110-116,1980.
31. H. Samet. SpatiaI Data Structures: Quadtree, Octrees and Other Hieralvhical Methods. Addison Wesley, 1989.
32. T.W. Sederberg and S.R. Parry. Comparison of three curve intersection algorithms. Computer-AidedDesign, 18(1):58-63,1986.
33. R. Seidel. Linear programming and convex hulls made easy. In P1vc. 6th Ann. ACM Conf. on Computational Geometry, pages 211-215, Berkeley, California, 1990.
34. W.Bouma and G.Vanecek. Collision detection and analysis in a physically based simulation. P1vceedings Eulvgraphics workshop on animation and simulation, pages 191-203,1991.
35. H. Weghorst, G. Hooper, and D. Greenberg. Improved computationalmethods 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.