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 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. Google ScholarDigital Library
- 2.J. Arvo and D. Kirk. A survey of ray tracing acceleration techniques. In An Introduction to Ray Tracing, pages 201-262,1989. Google ScholarDigital Library
- 3.D. Baraff. Curved surfaces and coherence for non-penetrating rigid body simulation. ACM Computer Graphics, 24(4):19-28,1990. Google ScholarDigital Library
- 4.B. Barber, D. Dobkin, and H. Huhdanpaa. The quickhull algorithm for convex hull. Technical Report GCG53, The Geometry Center, MN, 1993.Google Scholar
- 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. Google ScholarDigital Library
- 6.S. Cameron. Collision detection by four-dimensional intersection testing. P~vceedings of International Conference on Robotics and Automation, pages 291- 302, 1990.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 8.J.F. Canny. Collision detection for moving polyhedra. IEEE Trans. PAMI, 8:200-209,1986. Google ScholarDigital Library
- 9.B. Chazelle and D. R Dobkin. Intersection of convex objects in two and three dimensions. J. ACM, 34:1-27,1987. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 11.R.O. Duda and RE. Hart. Pattern Classification and Scene Analysis. John Wiley and Sons, 1973.Google ScholarDigital Library
- 12.Tom Duff. Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry. ACM Computer Graphics, 26(2):131-139, 1992. Google ScholarDigital Library
- 13.J. Snyder et. al. Interval methods for multi-point collisions between time dependent curved surfaces. In P1vceedings ofACM Siggraph, pages 321-334, 1993. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 15.S. Gottschalk. Separating axis theorem. Technical Report TR96-024, Department of Computer Science, UNC Chapel Hill, 1996.Google Scholar
- 16.N. Greene. Detecting intersection of a rectangular solid and a convex polyhedron. In Graphics Gems IV, pages 74-82. Academic Press, 1994. Google ScholarDigital Library
- 17.J.K. Hahn. Realistic animation of rigid bodies. Computer Graphics, 22(4):pp. 299-308,1988. Google ScholarDigital Library
- 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.Google Scholar
- 19.B. V. Herzen, A. H. Barr, and H. R. Zatz. Geometric collisions for timedependent parametric surfaces. Computer Graphics, 24(4) :39-48,1990. Google ScholarDigital Library
- 20.R M. Hubbard. Interactive collision detection. In P1vceedings oflEEE Symposium on Resealvh Frontiers in Virtual Reality, October 1993.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 22.M.C. Lin and Dinesh Manocha. Fast interference detection between geometric models. The Visual Computer, 11(10):542-561,1995.Google ScholarCross Ref
- 23.M. Moore and J. Wilhelms. Collision detection and response for computer animation. Computer Graphics, 22(4):289-298,1988. Google ScholarDigital Library
- 24.B. Naylor, J. Amanatides, and W. Thibault. Merging bsp trees yield polyhedral modeling results. In P1vc. ofACM Siggraph, pages 115-124,1990. Google ScholarDigital Library
- 25.J. O'Rourke. Finding minimal enclosing boxes. Internat. J. Comput. Info~. Sci., 14:183-199,1985.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 27.F.R Preparata and M. I. Shamos. Computational Geometry. Springer-Verlag, New York, 1985. Google ScholarCross Ref
- 28.S. Quinlan. Efficient distance computation between non-convex objects. In P1vceedings of International Conference on Robotics and Automation, pages 3324-3329,1994.Google Scholar
- 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.Google ScholarCross Ref
- 30.S. Rubin and T. Whitted. A 3-dimensional representation for fast rendering of complex scenes. In P1vc. ofACM Siggraph, pages 110-116,1980. Google ScholarDigital Library
- 31.H. Samet. SpatiaI Data Structures: Quadtree, Octrees and Other Hieralvhical Methods. Addison Wesley, 1989.Google Scholar
- 32.T.W. Sederberg and S.R. Parry. Comparison of three curve intersection algorithms. Computer-AidedDesign, 18(1):58-63,1986. Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 35.H. Weghorst, G. Hooper, and D. Greenberg. Improved computationalmethods for ray tracing. ACM Transactions on Graphics, pages 52-69,1984. Google ScholarDigital Library
- 36.E. Welzl. Smallest enclosing disks (balls and ellipsoids). Technical Report B 91-09, Fachbereich Mathematik, Freie Universitat, Berlin, 1991.Google Scholar
Index Terms
- OBBTree: a hierarchical structure for rapid interference detection
Recommendations
OBBTree: A Hierarchical Structure for Rapid Interference Detection
Seminal Graphics Papers: Pushing the Boundaries, Volume 2We 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 ...
Efficient updates of bounding sphere hierarchies for geometrically deformable models
We present a new approach for efficient collision handling of meshless objects undergoing geometric deformation. The presented technique is based on bounding sphere hierarchies. We show that information of the geometric deformation model can be used to ...
Hierarchical structures for collision checking between virtual characters
Simulating a crowded scene like a busy shopping street requires tight packing of virtual characters. In such cases, collisions are likely to occur, and the choice in collision detection shape will influence how characters are allowed to intermingle. ...
Comments