Fast and reliable collision detection using graphics processors

ABSTRACT

We present a fast and reliable collision detection algorithm using graphics processors. We use visibility computations to prune non-overlapping pairs of triangles. We overcome the accuracy problems due to limited viewport resolution using Minkowski sums of primitives and a pixel-size sphere.

REFERENCES

• 1: George Baciu , Wingo S. K. Wong, Image-Based Techniques in a Hybrid Collision Detector, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.254-271, April 2003 [doi>10.1109/TVCG.2003.1196011]
• 2: Naga K. Govindaraju , Ming C. Lin , Dinesh Manocha, Fast and reliable collision culling using graphics hardware, Proceedings of the ACM symposium on Virtual reality software and technology, November 10-12, 2004, Hong Kong [doi>10.1145/1077534.1077538]
• 3: Naga K. Govindaraju , Stephane Redon , Ming C. Lin , Dinesh Manocha, CULLIDE: interactive collision detection between complex models in large environments using graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 4: M. Lin and S. Gottschalk. Collision detection between geometric models: A survey. Proc. of IMA Conference on Mathematics of Surfaces, 1998.
• 5: M. Lin and D. Manocha. Collision and proximity queries. In Handbook of Discrete and Computational Geometry, 2003.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

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

General Terms:
Algorithms, Performance, Reliability

Keywords:
Minkowski sums, collision detection, deformable models, graphics hardware