Hardware-assisted self-collision for deformable surfaces

ABSTRACT

The natural behavior of garments and textile materials in the presence of changing object states is potentially the most computationally demanding task in a dynamic 3D virtual environment. Cloth materials are highly deformable inducing a very large number of contact points or regions with other objects. In a natural environment, cloth objects often interact with themselves generating a large number of self-collisions areas. The interactive requirements of 3D games and physically driven virtual environments make the cloth collisions and self-collisions computations more challenging. By exploiting mathematically well-defined smoothness conditions over smaller patches of deformable surfaces and resorting to image-based collision detection tests, we developed an efficient collision detection method that achieves interactive rates while tracking self-interactions in highly deformable surfaces consisting of more that 50,000 elements. The method makes use of a novel technique for dynamically generating a hierarchy of cloth bounding boxes in order to perform object-level culling and image-based intersection tests using conventional graphics hardware support.

REFERENCES

• 1: G. Baciu, S. K. Wong, and H. Sun. RECODE: An Image-Based Collision Detection Algorithm. Journal of Visualization and Computer Animation, 10(4):181--192, 1999.
• 2: G. Banel Cloth Simulation: From the Movie Final Fantasy, The Spirits Within to the Game. In Proceedings of the Game Developers Conferece (GDC2002), March 2002.
• 3: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 4: S. F. Chen, J. L. Hu, and J. G. Teng. A finite-volume method for contact drape simulation of woven fabrics and garments. Finite Elements in Analysis and Design, 37:513--531, 2001.
• 5: Kevin Chung and Wenping Wang. Quick Collision Detection of Polytopes in Virtual Environments. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology, pages 125--132. ACM, July 1996.
• 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: F. Cordier, P. Volino, and N. Magnenat-Thalmann. Integrating deformations between bodies and clothes. Journal of Visualization and Computer Animation, 12(1):45--53, Feb. 2001.
• 8: Susan Fisher , Ming C. Lin, Deformed distance fields for simulation of non-penetrating flexible bodies, Proceedings of the Eurographic workshop on Computer animation and simulation, p.99-111, September 02-03, 2001, Manchester, UK
• 9: Alejandro Garcia-Alonso , Nicolás Serrano , Juan Flaquer, Solving the Collision Detection Problem, IEEE Computer Graphics and Applications, v.14 n.3, p.36-43, May 1994 [doi>10.1109/38.279041]
• 10: E. G. Gilbert, D. W. Johnson, and S. S. Keerthi. A fast procedure for computing the distance between objects in three-dimensional space. Journal of Robotics and Automation, 4(2):193--203, 1988.
• 11: S. Gottschalk. Separating axis theorem. Technical Report TR96-024, Department of Computer Science, UNC Chapel Hill, 1996.
• 12: 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]
• 13: M. Held, J. T. Klosowski, and J. S. B. Mitchell. Evaluation of collision detection methods for virtual reality fly-throughs. In Canadian Conferenceon Computational Geometry, 1995.
• 14: Brian Von Herzen , Alan H. Barr , Harold R. Zatz, Geometric collisions for time-dependent parametric surfaces, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.39-48, Aug. 1990
• 15: J. Hu and Y.-F. Chan. Effect of Fabric Mechanical Properties on Drape. Textile Research Journal, 68(1):57--64, 1998.
• 16: 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]
• 17: Philip M. Hubbard, Approximating polyhedra with spheres for time-critical collision detection, ACM Transactions on Graphics (TOG), v.15 n.3, p.179-210, July 1996 [doi>10.1145/231731.231732]
• 18: 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]
• 19: 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]
• 20: 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]
• 21: M. C. Lin and J. F. Canny. Efficient Collision Detection for Animation. In Third Eurographics Workshop on Animation and Simulation, Cambridge, September 1992.
• 22: M. C. Lin and S. Gottschalk. Collision detection between geometric models: a survey. In Proceedings of IMA Conference on Mathematics of Surfaces, 1999.
• 23: M. C. Lin and D. Manocha. Fast interference detection between geometric models. The Visual Computer, 11(10):542--591, 1995.
• 24: S. Melax. BSP Collision Detection As Used In MDK2 and NeverWinter Nights. In Proceedings of the Game Developers Conferece (GDC2001), March 2001.
• 25: Dimitri Metaxas , Demetri Terzopoulos, Dynamic deformation of solid primitives with constraints, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.309-312, July 1992
• 26: 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]
• 27: Tomas Möller, A fast triangle-triangle intersection test, Journal of Graphics Tools, v.2 n.2, p.25-30, 1997
• 28: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
• 29: 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]
• 30: Madhav Ponamgi , Dinesh Manocha , Ming C. Lin, Incremental algorithms for collision detection between solid models, Proceedings of the third ACM symposium on Solid modeling and applications, p.293-304, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218076]
• 31: Xavier Provot. Collision and self collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation '97, pages 177--189, 1997.
• 32: 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
• 33: Subhash Suri , Philip M. Hubbard , John F. Hughes, Collision detection in aspect and scale bounded polyhedra, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.127-136, January 25-27, 1998, San Francisco, California, United States
• 34: Demetri Terzopoulos , Kurt Fleischer, Modeling inelastic deformation: viscolelasticity, plasticity, fracture, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.269-278, Aug. 1988
• 35: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.205-214, July 1987
• 36: Demetri Terzopoulos , Andrew Witkin, Physically Based Models with Rigid and Deformable Components, IEEE Computer Graphics and Applications, v.8 n.6, p.41-51, November 1988 [doi>10.1109/38.20317]
• 37: T. Vassilev, Spanlang B., and Chrysanthou Y. Fast Cloth Animation on Walking Avatars. Computer Graphics Forum, 20(3):260--267, Sep. 2001.
• 38: P. Volino and N. Magnenat-Thalmann. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Computer Graphics Forum, 13(3):155--166, 1994.
• 39: Pascal Volino , Nadia Magnenat Thalmann, Accurate Collision Response on Polygonal Meshes, Proceedings of the Computer Animation, p.154, May 03-05, 2000
• 40: Pascal Volino , Nadia Magnenat Thalmann, Implementing Fast Cloth Simulation with Collision Response, Proceedings of the International Conference on Computer Graphics, p.257, June 19-24, 2000
• 41: Pascal Volino , Martin Courchesne , Nadia Magnenat Thalmann, Versatile and efficient techniques for simulating cloth and other deformable objects, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.137-144, September 1995 [doi>10.1145/218380.218432]
• 42: Pascal Volino and N. Magnenant-Thalmann. Collision and Self-Collision Detection: Robust and Efficient Techniques for Highly Deformable Surfaces. In Eurographics Workshop on Animation and Simulation. Springer-Verlag, 1995.
• 43: Pascal Volino , Nadia Magnenat Thalmann , Shen Jianhua , Daniel Thalmann, An Evolving System for Simulating Clothes on Virtual Actors, IEEE Computer Graphics and Applications, v.16 n.5, p.42-51, September 1996 [doi>10.1109/38.536274]
• 44: Y. Yang and N. Thalmann. An improved algorithm for collision detection in cloth animation with human body. In First Pacific Conference on Computer Graphics and Applications, pages 237--251, 1993.
• 45: M. J. Zyda, D. R. Pratt, D. Osborne, and J. G. Monahan. NPSNET: Real-time collision detection and response. The Journal of Visualization and Computer Animation, 4:13--24, 1993.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation; Virtual reality

General Terms:
Algorithms, Experimentation, Performance

Keywords:
cloth simulation, collision detection, deformable surfaces, graphics hardware