Interactive collision detection for complex and deformable models using programmable graphics hardware

ABSTRACT

In this paper we present an interactive collision detection algorithm for complex and deformable objects. For two target models, our approach rapidly calculates their region of interests (ROI), which is the overlapping of their axis aligned bounding boxes (AABBs), in CPU. The surfaces of both models inside the ROI are then voxelized using a novel GPU-based real-time voxelization method. The resultant volumes are represented by two 2D textures in video memory. The collision query is efficiently accomplished by comparing these 2D textures in GPU. The algorithm is robust to handle arbitrary shapes, no matter geometric models are convex or concave, closed or open, rigid or deformable. Our preliminary implementation achieves interactive frame rate for complex models with up to one million triangles on commodity desktop PCs.

REFERENCES

• 1: 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
• 2: S. Beckhaus, J. Wind, and T. Strothotte. Hardware-based voxelization for 3d spatial analysis. In Proceedings of CGIM 2002, pages 15--20, 2002.
• 3: Gino van den Bergen, Efficient collision detection of complex deformable models using AABB trees, Journal of Graphics Tools, v.2 n.4, p.1-13, April 1997
• 4: Gino Van den Bergen, A fast and robust GJK implementation for collision detection of convex objects, Journal of Graphics Tools, v.4 n.2, p.7-25, March 1999
• 5: Michael Boyles , Shiaofen Fang, Slicing-based volumetric collision detection, Journal of Graphics Tools, v.4 n.4, p.23-32, 1999
• 6: S. Cameron. Enhancing gjk: computing minimum and penetration distances between convex polyhedra. In Proceedings of IEEE International Conference of Robotics and Automation, pages 3112--3117, 1997.
• 7: K. Chunk and W. Wang. Quick collision detection of polytopes in virtual environments. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology, pages 125--131, 1996.
• 8: 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]
• 9: S. Ehmann and M. Lin. Accurate and fast proximity queries between polyhedra using convex surface decomposition. In Proceedings of Eurographics 2001, pages 500--510, 2001.
• 10: S. Fang and H. Chen. Hardware accelerated voxeliation. Computers and Graphics, 24(3):433--442, 2000.
• 11: Nikhil Gagvani , Deborah Silver, Shape-based volumetric collision detection, Proceedings of the 2000 IEEE symposium on Volume visualization, p.57-61, October 09-10, 2000, Salt Lake City, Utah, United States [doi>10.1145/353888.353899]
• 12: S. Gibson. Beyond volume rendering: visualization, haptic exploration, and physical modeling of voxel-based objects. In Proceedings of 6th Eurographics Workshop on Visualization in Scientific Computing, pages 10--24, 1995.
• 13: 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]
• 14: 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
• 15: Taosong He , Arie Kaufman, Collision detection for volumetric objects, Proceedings of the 8th conference on Visualization '97, p.27-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 16: B. Heidelberger, M. Teschner, and M. Gross. Real-time volumetric intersections of deforming objects. In Proceedings of Vision, Modeling, Visualization, pages 461--468, 2003.
• 17: 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]
• 18: K. Hoff, A. Zaferakis, M. Lin, and D. Manocha. Fast 3d geometric proximity queries between rigid and deformable models using graphics hardware acceleration. Technical Report TR02--004, 2002.
• 19: Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717]
• 20: 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]
• 21: P. Jimzenez, F. Thomas, and C. Torras. 3d collision detection: A survey. Computers and Graphics, 25(2):269--285, 2001.
• 22: Arie Kaufman , Daniel Cohen , Roni Yagel, Volume Graphics, Computer, v.26 n.7, p.51-64, July 1993 [doi>10.1109/MC.1993.274942]
• 23: Y. Kim, M. Otaduy, M. Lin, and D. Manocha. Fast penetration depth computation using rasterization hardware and hierarchical refinement. UNC-CH Technical Report TR02--014, 2002.
• 24: Y. Kitamura, A. Smith, H. Takemura, and F. Kishino. A real-time algorithm for accurate collision detection for deformable polyhedral objects. Presence, 7(1):36--52, 1998.
• 25: 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]
• 26: T. Larsson and T. Akenine-Moller. Efficient collision detection for models deformed by morphing. The Visual Computer, 9(2):164--174, 2003.
• 27: M. Lin and S. Gottschalk. Collision detection between geometric models: a survey. In Proceedings of IMA Conference on Mathematics of Surfaces, pages 37--56, 1998.
• 28: Jean-Christophe Lombardo , Marie-Paule Cani , Fabrice Neyret, Real-time Collision Detection for Virtual Surgery, Proceedings of the Computer Animation, p.82, May 26-28, 1999
• 29: William A. McNeely , Kevin D. Puterbaugh , James J. Troy, Six degree-of-freedom haptic rendering using voxel sampling, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.401-408, July 1999 [doi>10.1145/311535.311600]
• 30: Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
• 31: 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.
• 32: S. Redon, A. Kheddar, and S. Coquillart. Fast continuous collision detection between rigid bodies. In Proceedings of Eurographics, pages 278--288, 2002.
• 33: 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
• 34: M. Shinya and M. C. Forgue. Interference detection through rasterization. The Journal of Visualization and Computer Animation, 2(4):131--134, 1991.
• 35: A. Smith , Y. Kitamura , H. Takemura , F. Kishino, A simple and efficient method for accurate collision detection among deformable polyhedral objects in arbitrary motion, Proceedings of the Virtual Reality Annual International Symposium (VRAIS'95), p.136, March 11-15, 1995
• 36: T. Vassilev, B. Spanlang, and Y. Chrysanthou. Fast cloth animation on walking avatars. Computer Graphics Forum, 20(3):260--267, 2001.
• 37: Sidney W. Wang , Arie E. Kaufman, Volume-Sampled 3D Modeling, IEEE Computer Graphics and Applications, v.14 n.5, p.26-32, September 1994 [doi>10.1109/38.310721]
• 38: Dongliang Zhang , Matthew M. F. Yuen, Collision Detection for Clothed Human Animation, Proceedings of the 8th Pacific Conference on Computer Graphics and Applications, p.328, October 03-05, 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms

Keywords:
collision detection, deformation, graphics hardware, voxelization