A randomized marking scheme for continuous collision detection in simulation of deformable surfaces

ABSTRACT

Continuous collision detection techniques are applied extensively in the simulation of deformable surfaces, in particular for cloth simulation. Accurate contact information can be computed by using these techniques. Traditionally, for meshed surfaces, after collecting the triangle pairs that are potentially interacting, the feature pairs of these triangles are directly sent for the computation of collision information. Many feature pairs end up being processed repeatedly because a feature may be shared by more than one triangle. In this paper, we propose a randomized marking scheme to mark triangles and embed a feature filtering layer (FFL) in the pipeline of continuous collision detection. The purpose of the FFL is to extract potentially interacting feature pairs according to the marking of the triangles. By applying the FFL each interacting feature pair is processed exactly one time for the computation of collision information. On average, the number of potentially interacting feature pairs reduces significantly after filtering. We have integrated the FFL in a cloth simulation system. Interactive rates can be achieved for complex draping simulation.

REFERENCES

• 1: George Baciu , Wingo Sai-Keung Wong, Hardware-assisted self-collision for deformable surfaces, Proceedings of the ACM symposium on Virtual reality software and technology, November 11-13, 2002, Hong Kong, China [doi>10.1145/585740.585762]
• 2: George Baciu , Wingo Sai-Keung Wong, Image-Based Collision Detection for Deformable Cloth Models, IEEE Transactions on Visualization and Computer Graphics, v.10 n.6, p.649-663, November 2004 [doi>10.1109/TVCG.2004.44]
• 3: Bruce Guenther Baumgart, Geometric modeling for computer vision., 1974
• 4: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 5: J Canny, Collision detection vkr moving polyhedra, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.8 n.2, p.200-209, March 1986 [doi>10.1109/TPAMI.1986.4767773]
• 6: John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: Culley, R., and Kempf, K. 1986. A Collision Detection Algorithm Based on Velocity and Distance Bounds. In Proceedings of International Conference on Robotics and Automation, 1064--1068.
• 9: 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]
• 10: Liu, J., Ko, M., and Chang, R. 1996. Collision Avoidance in Cloth Animation. Visual Computer 12, 5, 234--243.
• 11: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
• 12: 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]
• 13: Provot, X. 1997. Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments. In Computer Animation and Simulation, 177--189.
• 14: Stephane Redon , Young J. Kim , Ming C. Lin , Dinesh Manocha , Jim Templeman, Interactive and Continuous Collision Detection for Avatars in Virtual Environments, Proceedings of the IEEE Virtual Reality 2004 (VR'04), p.117, March 27-31, 2004 [doi>10.1109/VR.2004.46]
• 15: Volino, P., and Magnenat-Thalmann, N. 1994. Efficient Self-Collision Detection on Smoothly Discretised Surface Animation using Geometrical Shape Regularity. Computer Graphics Forum 13, 3 (Sep.), 155--166.
• 16: Wingo Sai-Keung Wong , George Baciu, Dynamic Interaction between Deformable Surfaces and Nonsmooth Objects, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.329-340, May 2005 [doi>10.1109/TVCG.2005.44]
• 17: Wingo Sai-Keung Wong , George Baciu, GPU-based intrinsic collision detection for deformable surfaces: Collision Detection and Deformable Objects, Computer Animation and Virtual Worlds, v.16 n.3-4, p.153-161, July 2005 [doi>10.1002/cav.v16:3/4]
• 18: Wong, W. S.-K., and Baciu, G. 2005. Intrinsic Continuous Collision Detection for Deformable Meshes. Research Journal of Textile and Apparel 9, 1, 60--73.
• 19: Sai-Keung Wong , George Baciu , Andrew Horner, High performance virtual clothing dynamics, Hong Kong University of Science and Technology (People's Republic of China), 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Keywords:
continuous collision detection, deformable surfaces, interactive simulation, randomized marking scheme, set-covering problems