A voxel-based parallel collision detection algorithm

ABSTRACT

Two physical objects cannot occupy the same space at the same time. Simulated physical objects do not naturally obey this constraint. Instead, we must detect when two objects have collided---we must perform collision detection. This work presents a simple voxel-based collision detection algorithm, an efficient parallel implementation of the algorithm, and performance results.

REFERENCES

• 1: S. Bandi and D. Thalmann. An adaptive spatial subdivision of the object space for fast collision of animated rigid bodies. In Proceedings of Eurographics '95, pages 259--270, August 1995. http://ligwww.epfl.ch/~thalmann/
• 2: S. Brown, S. Attaway, S. Plimpton, and B. Hendrickson. Parallel strategies for crash and impact simulations. Computer Methods in Applied Mechanics and Engineering, 184:375--390, 2000
• 3: Robert K. Brunner , Laxmikant V. Kalé, Adapting to Load on Workstation Clusters, Proceedings of the The 7th Symposium on the Frontiers of Massively Parallel Computation, p.106, February 21-25, 1999
• 4: 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]
• 5: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 6: R. T. Farouki , C. Neff , M. A. O'Conner, Automatic parsing of degenerate quadric-surface intersections, ACM Transactions on Graphics (TOG), v.8 n.3, p.174-203, July 1989 [doi>10.1145/77055.77058]
• 7: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 8: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 9: E. Gilbert, D. Johnson, and S. Keerthi. A fast procedure for computing the distance between objects in three-dimensional space. IEEE Journal of Robotics and Automation, RA-4:193--203, 1988
• 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: Chris Hecker. Let's get to the (floating) point. Game Developer Magazine, Feb/Mar, 1996
• 12: P. Hubbard. Efficient Collision Detection for Animation and Robotics. PhD thesis, Brown University, 1994
• 13: P. Jiménez, F. Thomas, and C. Torras. 3d collision detection: A survey. Computers and Graphics, 25(2):269--285, 2001
• 14: L. Kale and S. Krishnan. Charm++: Parallel Programming with Message-Driven Objects. In Parallel Programming using C++, pages 175--213. 1996. http://charm.cs.uiuc.edu/
• 15: Laxmikant Kalé , Robert Skeel , Milind Bhandarkar , Robert Brunner , Attila Gursoy , Neal Krawetz , James Phillips , Artiomo Shinozaki , Krishnan Varadarajan , Klaus Schulten, NAMD2: greater scalability for parallel molecular dynamics, Journal of Computational Physics, v.151 n.1, p.283-312, May 1, 1999 [doi>10.1006/jcph.1999.6201]
• 16: Katsuaki Kawachi , Hiromasa Suzuki, Distance Computation between Non-Convex Polyhedra at Short Range Based on Discrete Voronoi Regions, Proceedings of the Geometric Modeling and Processing 2000, p.123, April 10-12, 2000
• 17: J. Klosowski, M. Held, J. Mitchell, H. Sowizral, and K. Zikan. Efficient collision detection using bounding volumes of k-dops. In Siggraph '96 Visual Proceedings, page 151, 1996
• 18: Shankar Krishnan , Amol Pattekar , Ming C. Lin , Dinesh Manocha, Spherical shell: a higher order bounding volume for fast proximity queries, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.177-190, August 1998, Houston, Texas, United States
• 19: O. Lawlor. A grid-based parallel collision detection algorithm. Master's thesis, University of Illinois at Urbana-Champaign, March 2001. http://charm.cs.uiuc.edu/papers/
• 20: Orion S. Lawlor , Laxmikant V. Kalé, Supporting dynamic parallel object arrays, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.21-28, June 2001, Palo Alto, California, United States [doi>10.1145/376656.376804]
• 21: Ming Chieh Lin , John F. Canny, Efficient collision detection for animation and robotics, 1993
• 22: M. Lin and J. Canny. Efficient algorithms for incremental distance computation. IEEE Conference on Robotics and Automation, pages 1008--1014, 1991
• 23: M. Lin and S. Gottschalk. Collision detection between geometric models: A survey. In Proceedings of IMA Conference on Mathematics of Surfaces, 1998. http://www.cs.unc.edu/~dm/collision.html
• 24: Subhash Suri , Philip M. Hubbard , John F. Hughes, Analyzing bounding boxes for object intersection, ACM Transactions on Graphics (TOG), v.18 n.3, p.257-277, July 1999 [doi>10.1145/336414.336423]
• 25: G. Turk. Interactive collision detection for molecular graphics. Master's thesis, University of North Carolina at Chapel Hill, 1989
• 26: Yunhong Zhou , Subhash Suri, Analysis of a bounding box heuristic for object intersection, Journal of the ACM (JACM), v.46 n.6, p.833-857, Nov. 1999 [doi>10.1145/331524.331528]
• 27: M. Zyda, W. Osborne, J. Monahan, and D. Pratt. Npsnet: Real-time collision detection and response. Journal of Visualization and Computer Animation, 4, number 1:13--24, 1993

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.m Miscellaneous

General Terms:
Algorithms

Keywords:
collision detection, contact, parallel geometry