Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This article presents the Voronoi-clip, or V-Clip, collision detection alogrithm for polyhedral objects specified by a boundary representation. V-Clip tracks the closest pair of features between convex polyhedra, using an approach reminiscent of the Lin-Canny closest features algorithm. V-Clip is an improvement over the latter in several respects. Coding complexity is reduced, and robustness is significantly improved; the implementation has no numerical tolerances and does not exhibit cycling problems. The algorithm also handles penetrating polyhedra, and can therefore be used to detect collisions between nonvconvex polyhedra described as hierarchies of convex pieces. The article presents the theoretical principles of V-Clip, and gives a pseudocode description of the algorithm. It also documents various test that compare V-Clip, Lin-Canny, and the Enhanced GJK algorithm, a simplex-based algorithm that is widely used for the same application. The results show V-Clip to be a strong contender in this field, comparing favorably with the other algorithms in most of the tests, in term of both performance and robustness.

REFERENCES

• 1: D. Ayala , P. Brunet , R. Juan , I. Navazo, Object representation by means of nonminimal division quadtrees and octrees, ACM Transactions on Graphics (TOG), v.4 n.1, p.41-59, Jan. 1985 [doi>10.1145/3973.3975]
• 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: David Baraff, Dynamic simulation of nonpenetrating rigid bodies, Cornell University, Ithaca, NY, 1992
• 4: CAMERON, S. 1997. Enhancing GJK: Computing minimum penetration distances between convex polyhedra. In Proceedings of the International Conference on Robotics and Automation. (Albuquerque, NM, April 20-25), 3112-3117.
• 5: CHUNG, K. 1996. An efficient collision detection algorithm for polytopes in virtual environments. Master's Thesis, University of Hong Kong, September.
• 6: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
• 7: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• 8: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics (2nd ed. in C): principles and practice, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 9: GILBERT, E. G., JOHNSON, D. W., AND KEERTHI, S.S. 1988. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE J. Robot. Autom. 4, 2 (April), 193-203.
• 10: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 11: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 12: Thomas C. Hudson , Ming C. Lin , Jonathan Cohen , Stefan Gottschalk , Dinesh Manocha, V-COLLIDE: accelerated collision detection for VRML, Proceedings of the second symposium on Virtual reality modeling language, p.117-ff., February 24-26, 1997, Monterey, California, United States [doi>10.1145/253437.253472]
• 13: Ming Chieh Lin , John F. Canny, Efficient collision detection for animation and robotics, 1993
• 14: LUENBERGER, D. G. 1984. Linear and Nonlinear Programming, second edition. Addison- Wesley, Reading, MA.
• 15: Brian Vincent Mirtich, Impulse-based dynamic simulation of rigid body systems, 1996
• 16: Bruce F. Naylor, Interactive solid geometry via partitioning trees, Proceedings of the conference on Graphics interface '92, p.11-18, September 1992, Vancouver, British Columbia, Canada
• 17: Rich Rabbitz, Fast collision detection of moving convex polyhedra, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 18: ROYDEN, H.L. 1988. Real Analysis, Third edition. Macmillan, New York, NY.

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.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations

General Terms:
Algorithms

Keywords:
collision detection, polyhedra