Fast and reliable collision culling using graphics hardware

ABSTRACT

We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. To overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE [8] and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including non-manifold geometry, deformable models, and breaking objects.

REFERENCES

• 1: Tomas Akenine-Möller , Jacob Ström, Graphics for the masses: a hardware rasterization architecture for mobile phones, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 2: 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]
• 3: G. Baciu , W. Wong , H. Sun, RECODE: An Image-based Collision Detection Algorithm, Proceedings of the 6th Pacific Conference on Computer Graphics and Applications, p.125, October 26-29, 1998
• 4: G. Barequet, B. Chazelle, L. Guibas, J. Mitchell, and A. Tal. Boxtree: A hierarchical representation of surfaces in 3D. In Proc. of Eurographics'96, 1996.
• 5: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 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: 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]
• 8: 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
• 9: Alexander Gress and Gabriel Zachmann. Object-space interference detection on programmable graphics hardware. In SIAM Conf. on Geometric Design and Computing, Seattle, Washington, November13-17 2003.
• 10: B. Heidelberger, M. Teschner, and M. Gross. Real-time volumetic intersections of deforming objects. Proc. of Vision, Modeling and Visualization, 2003.
• 11: Martin Held , James T. Klosowski , Joseph S. B. Mitchell, Real-time collision detection for motion simulation within complex environments, ACM SIGGRAPH 96 Visual Proceedings: The art and interdisciplinary programs of SIGGRAPH '96, p.151, August 04-09, 1996, New Orleans, Louisiana, United States [doi>10.1145/253607.253888]
• 12: Kenneth E. Hoff, III , Andrew Zaferakis , Ming Lin , Dinesh Manocha, Fast and simple 2D geometric proximity queries using graphics hardware, Proceedings of the 2001 symposium on Interactive 3D graphics, p.145-148, March 2001 [doi>10.1145/364338.364383]
• 13: P. M. Hubbard. Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality, October 1993.
• 14: P. Jimenez, F. Thomas, and C. Torras. 3d collision detection: A survey. Computers and Graphics, 25(2):269--285, 2001.
• 15: B. Kelleher. Pixelvision architecture. Technical Report 1998--013, Digital Systems Research Center, 1998.
• 16: Young J. Kim , Miguel A. Otaduy , Ming C. Lin , Dinesh Manocha, Fast penetration depth computation for physically-based animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545266]
• 17: James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998 [doi>10.1109/2945.675649]
• 18: D. Knott and D. Pai. Cinder: Collision and interference detection in real-time using graphics hardware. Proc. of Graphics Interface, pages 73--80, 2003.
• 19: M. Lin and S. Gottschalk. Collision detection between geometric models: A survey. Proc. of IMA Conference on Mathematics of Surfaces, 1998.
• 20: Joel McCormack , Robert McNamara, Tiled polygon traversal using half-plane edge functions, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.15-21, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.346882]
• 21: Tomas Möller, A fast triangle-triangle intersection test, Journal of Graphics Tools, v.2 n.2, p.25-30, 1997
• 22: S. Morein. ATI Radeon HyperZ technology. In ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, Hot3D Proceedings, 2000.
• 23: K. Myszkowski, O. G. Okunev, and T. L. Kunii. Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, 11(9):497--512, 1995.
• 24: M. Lin N. Govindaraju and D. Manocha. Quick-cullide: Fast inter- and intra-object collision culling using graphics hardware. Technical report, University of North Carolina at Chapel Hill, July 2004.
• 25: Madhav K. Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental Algorithms for Collision Detection Between Polygonal Models, IEEE Transactions on Visualization and Computer Graphics, v.3 n.1, p.51-64, January 1997 [doi>10.1109/2945.582346]
• 26: S. Quinlan. Efficient distance computation between non-convex objects. In Proceedings of International Conference on Robotics and Automation, pages 3324--3329, 1994.
• 27: Ramesh Raskar , Michael Cohen, Image precision silhouette edges, Proceedings of the 1999 symposium on Interactive 3D graphics, p.135-140, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300539]
• 28: Jarek Rossignac , Abe Megahed , Bengt-Olaf Schneider, Interactive inspection of solids: cross-sections and interferences, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.353-360, July 1992
• 29: M. Shinya and M. C. Forgue. Interference detection through rasterization. The Journal of Visualization and Computer Animation, 2(4):131--134, 1991.
• 30: Freesolid: Software library for interference detection. http://www.win.tue.nl/ gino/solid/.
• 31: T. Vassilev, B. Spanlang, and Y. Chrysanthou. Fast cloth animation on walking avatars. Computer Graphics Forum (Proc. of Eurographics'01), 20(3):260--267, 2001.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
      I.3.7 Three-Dimensional Graphics and Realism

General Terms:
Algorithms, Performance, Reliability

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