I-COLLIDE: an interactive and exact collision detection system for large-scale environments

ABSTRACT

we present an exact and interactive collision detection system, I-COLLIDE, for large-scale environments. Such environments are characterized by the number of objects undergoing rigid motion and the complexity of the models. The algorithm does not assume the objects' motions can be expressed as a closed form function of time. The collision detection system is general and can be easily interfaced with a variety of applications. The algorithm uses a two-level approach based on pruning multiple-object pairs using bounding boxes and performing exact collision detection between selected pairs of polyhedral models. We demonstrate the performance of the system in walkthrough and simulation environments consisting of a large number of moving objects. In particular, the system takes less than 1/20 of a second to determine all the collisions and contacts in an environment consisting of more than 1000 moving polytopes, each consisting of more than 50 faces on an HP-9000/750.

REFERENCES

• 1: Alejandro Garcia-Alonso , Nicolás Serrano , Juan Flaquer, Solving the Collision Detection Problem, IEEE Computer Graphics and Applications, v.14 n.3, p.36-43, May 1994 [doi>10.1109/38.279041]
• 2: David Baraff, Curved surfaces and coherence for non-penetrating rigid body simulation, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.19-28, Aug. 1990
• 3: D. Bara.ff. Dynamic simulation o} non-penetrating rigid body simulation. PhD thesis, Cornell Universilzy, 1992.
• 4: S. Cameron. Collision detection by four-dimensional intersection testing. Proceedings of International Conference on Robotics and Automation, pages pp. 291-302, 1990.
• 5: Stephen Cameron, Approximation hierarchies and S-bounds, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.129-137, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112537]
• 6: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav K. Ponamgi, Interactive and Exact Collision Detection for Multi-Body Environments, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1994
• 7: P. Dworkin and D. Zeltzer. A new model for efficient dynamics simulation. Proceedings Eurographics workshop on animation and simulation, pages 175- 184, 1993.
• 8: H. Edelsbrunner. A new approach to rectangle intersections, Part I. Internat. J. Comput. Math., 13:209- '2 lC,, 1983.
• 9: John M. Snyder , Adam R. Woodbury , Kurt Fleischer , Bena Currin , Alan H. Barr, Interval methods for multi-point collisions between time-dependent curved surfaces, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.321-334, September 1993 [doi>10.1145/166117.166158]
• 10: E. G. Gilbert, D. W. Johnson, and S. S. Keertffi. A fast procedure for computing the distance between objects in three-dimensional space. IEEE J. Robotics and Automation, vol RA-4:pp. 193-203, 1988.
• 11: James K. Hahn, Realistic animation of rigid bodies, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.299-308, Aug. 1988
• 12: J.E. Hopcroft, J.T. Schwartz, and M. Sharir. Efficient detection of intersections among spheres. The International Journal of Robotics Research, 2(4):77- 80, 19~3.
• 13: H.Six and D.Wood. Cotmting and reporting imersections of D-ranges. IEEE Transactions on Computers, pages 46-55, 1982.
• 14: P. M. Hubbard. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality, October 1993.
• 15: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 16: M. Lin and J. Canny. Efficient collision detection for animation. In Proceedings of the Third Eurograohics Workshop on Animation and Simulation, Cambridge, England, 1991.
• 17: M.C. {,in. Efficient Collision Detection for Animation and Robotics. PhD thesis, Department of Electrical F, ngineering and Computer Science, Univers:ity of Cafifornia, Berkeley, December 1993.
• 18: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
• 19: M.Shamos and D.Hoey. Geometric intersection problems. Proe. 17th An. IEEE Syrup. Found. on Cornput. Science, pages 208-215, 1976.
• 20: Alex Pentland, Computational complexity versus virtual worlds, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.185-192, Mar. 1990
• 21: Madhav K. Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental Algorithms for Collision Detection Between General Solid Models, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1994
• 22: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 23: William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987
• 24: David Zeltzer, Autonomy, interaction, and presence, Presence: Teleoperators and Virtual Environments, v.1 n.1, p.127-132, Winter 1992

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality

General Terms:
Algorithms, Performance