| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Image-Based Collision Detection for Deformable Cloth Models
November/December 2004 (vol. 10 no. 6)
pp. 649-663
Modeling the natural interaction of cloth and garments with objects in a 3D environment is currently one of the most computationally demanding tasks. These highly deformable materials are subject to a very large number of contact points in the proximity of other moving objects. Furthermore, cloth objects often fold, roll, and drape within themselves, generating a large number of self-collision areas. The interactive requirements of 3D games and physically driven virtual environments make the cloth collisions and self-collision 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 a large number of 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. An efficient backward voxel-based AABB hierarchy method is proposed to handle deformable surfaces which are highly compressed.
[1] 649 Using P-Buffers for Off-Screen Rendering in OpenGL http://developer.nvidia.com/docs/IO/1312/ ATTPixelBuffers.pdf, 2003.[2] G. Baciu and W.S.K. Wong, Hardware-Assisted Self-Collision for Deformable Surfaces Proc. ACM Symp. Virtual Reality Software and Technology, pp. 129-136, Nov. 2002.[3] G. Baciu and W.S.K. Wong, Image-Based Techniques in a Hybrid Collision Detector IEEE Trans. Visualization and Computer Graphics, vol. 9, no. 2, pp. 254-271, Apr.-June 2003.[4] G. Baciu, W.S.K. Wong, and H. Sun, RECODE: An Image-Based Collision Detection Algorithm J. Visualization and Computer Animation, vol. 10, no. 4, pp. 181-192, 1999.[5] G. Banel, Cloth Simulation: From the Movie Final Fantasy, The Spirits Within to the Game Proc. Game Developers Conf. (GDC2002), Mar. 2002.[6] D. Baraff and A. Witkin, Large Steps in Cloth Simulation Computer Graphics (Proc. SIGGRAPH '98), pp. 43-54, 1999.[7] P. Berman, B. Dasgupta, S. Muthukrishnan, and S. Ramaswami, Improved Approximation Algorithms for Rectangle Tiling and Packing Proc. Symp. Discrete Algorithms, pp. 427-436, 2001.[8] M. Botsch and L.P. Kobbelt, A Robust Procedure to Eliminate Degenerate Faces from Triangle Meshes Proc. Vision Modeling and Visualization Conf., pp. 283-290, 2001.[9] R. Bridson, R. Fedkiw, and J. Anderson, Robust Treatment of Collisions, Contact and Friction for Cloth Animation ACM Trans. Graphics, vol. 21, no. 3, pp. 594-603, 2002.[10] 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, vol. 37, pp. 513-531, 2001.[11] K. Chung and W. Wang, Quick Collision Detection of Polytopes in Virtual Environments Proc. ACM Symp. Virtual Reality Software and Technology, pp. 125-132, July 1996.[12] J. Cohen, M.C. Lin, D. Manocha, and M. Ponamgi, I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments Proc. ACM Interactive 3D Graphics Conf., pp. 189-196, 1995.[13] F. Cordier, P. Volino, and N. Magnenat-Thalmann, Integrating Deformations between Bodies and Clothes J. Visualization and Computer Animation, vol. 12, no. 1, pp. 45-53, Feb. 2001.[14] S. Fisher and M.C. Lin, Deformed Distance Fields for Simulation of Non-Penetrating Flexible Bodies Computer Animation and Simulation: Proc. Eurographics Workshop Computer Animation and Simulation, D. Thalmann, J.F. Canny, N. Magnenat-Thalmann, eds., pp. 99-112, 2001.[15] A. Garcia-Alonso, N. Serrano, and J. Flaquer, "Solving the Collision Detection Problem," IEEE Computer Graphics and Applications, vol. 13, no. 3, pp. 36-43, 1994.[16] E.G. Gilbert, D.W. Johnson, and S.S. Keerthi, A Fast Procedure for Computing the Distance between Objects in Three-Dimensional Space J. Robotics and Automation, vol. 4, no. 2, pp. 193-203, 1988.[17] S. Gottschalk, Separating Axis Theorem Technical Report TR96-024, Dept. of Computer Science, Univ. of North Carolina Chapel Hill, 1996.[18] S. Gottschalk, M.C. Lin, and D. Manocha, OBBTree: A Hierarchical Structure for Rapid Interference Detection Computer Graphics (Proc. SIGGRAPH '96), pp. 171-180, Aug. 1996.[19] M. Held, J.T. Klosowski, and J.S.B. Mitchell, Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs Proc. Canadian Conf. Computational Geometry, pp. 205-210, 1995.[20] B.V. Herzen, A.H. Barr, and H.R. Zats, Geometric Collision for Time-Dependent Parametric Surfaces Computer Graphics (SIGGRAPH '90), vol. 24, no. 4, pp. 39-48, 1990.[21] J. Hu and Y.F. Chan, Effect of Fabric Mechanical Properties on Drape Textile Research J., vol. 68, no. 1, pp. 57-64, 1998.[22] P.M. Hubbard, Collision Detection for Interactive Graphics Applications EEE Trans. Visualization and Computer Graphics, vol. 1, no. 3, pp. 218-228, Sept. 1995.[23] P.M. Hubbard, Approximating Polyhedra with Spheres for Time-Critical Collision Detection ACM Trans. Graphics, vol. 15, no. 3, pp. 179-210, 1996.[24] K.E. Hoff III, A. Zaferakis, M.C. Lin, and D. Manocha, Fast and Simple 2D Geometric Proximity Queries Using Graphics Hardware Proc. 2001 Symp. Interactive 3D Graphics, pp. 145-148, 2001.[25] S. Khanna, S. Muthukrishnan, and M. Paterson, On Approximating Rectangle Tiling and Packing Proc. Ninth Ann. ACM-SIAM Symp. Discrete Algorithms (SODA '98), pp. 384-393, 1998.[26] Y.J. Kim, M.A. Otaduy, M.C. Lin, and D. Manocha, Fast Penetration Depth Computation for Physically-Based Animation Computer Graphics (Proc. ACM SIGGRAPH 2002), pp. 23-31, 2002.[27] J.T. Klosowski, M. Held, J.S.B. Mitchell, H. Sowizral, and K. Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-dops IEEE Trans. Visualization and Computer Graphics, vol. 4, no. 1, pp. 21-36, Jan.-Mar. 1998.[28] L.P. Kobbelt and M. Botsch, An Interactive Approach to Point Cloud Triangulation Computer Graphics Forum, vol. 19, no. 3, pp. 479-487, 2000.[29] M.C. Lin and J.F. Canny, Efficient Collision Detection for Animation Proc. Third Eurographics Workshop Animation and Simulation, Sept. 1992.[30] M.C. Lin and S. Gottschalk, Collision Detection between Geometric Models: A Survey Proc. IMA Conf. Math. of Surfaces, 1999.[31] M.C. Lin and D. Manocha, Fast Interference Detection between Geometric Models The Visual Computer, vol. 11, no. 10, pp. 542-591, 1995.[32] J.D. Liu, M.T. Ko, and R.C. Chang, Collision Avoidance in Cloth Animation The Visual Computer, vol. 12, no. 5, pp. 234-243, 1996.[33] J.D. Liu, M.T. Ko, and R.C. Chang, A Simple Self-Collision Avoidance for Cloth Animation Computers and Graphics, vol. 22, no. 1, pp. 117-128, 1998.[34] S. Melax, BSP Collision Detection as Used in MDK2 and NeverWinter Nights Proc. Game Developers Conf. (GDC2001), Mar. 2001.[35] D. Metaxas and D. Terzopoulos, Dynamic Deformation of Solid Primitives with Constraints Computer Graphics (Proc. SIGGRAPH '92), vol. 26, no. 2, pp. 309-311, July 1992.[36] B. Mirtich, V-Clip: Fast and Robust Polyhedral Collision Detection ACM Trans. Computer Graphics, vol. 17, no. 3, pp. 177-208, July 1998.[37] T. Möler, A Fast Triangle-Triangle Intersection Test J. Graphics Tools, vol. 2, no. 2, pp. 25-30, 1997.[38] M. Moore and J.P. Wilhelms, Collision Detection and Response for Computer Animation Computer Graphics (Proc. SIGGRAPH '88), vol. 22, pp. 289-298, 1988.[39] M. Ponamgi, D. Manocha, and M.C. Lin, Incremental Algorithms for Collision Detection between General Solid Models Proc. ACM/SIGGRAPH Symp. Solid Modeling, pp. 293-304, 1995.[40] M.K. Ponamgi, D. Manocha, and M.C. Lin, Incremental Algorithms for Collision Detection between Polygonal Models IEEE Trans. Visualization and Computer Graphics, vol. 3, no. 1, pp. 51-64, Jan.-Mar. 1997.[41] X. Provot, Collision and Self-Collision Handling in Cloth Model Dedicated to Design Harments Proc. Computer Animation and Simulation '97, pp. 177-189, 1997.[42] T.W. Sederberg and R.J. Meyers, Loop Detection in Surface Patch Intersections Computer Aided Geometric Design, vol. 5, no. 2, pp. 161-171, 1988.[43] A. Smith, Y. Kitamu, H. Takemura, and F. Kishino, A Simple and Efficient Method for Accurate Collision Detection among Deformable Polyhedral Objects in Arbitrary Motion Proc. Virtual Reality Ann. Int'l Symp., pp. 136-145, 1995.[44] S. Suri, P.M. Hubbard, and J.F. Hughes, Collision Detection in Aspect and Scale Bounded Polyhedra Proc. Ninth ACM-SIAM Symp. Discrete Algorithms, pp. 127-136, Jan. 1998.[45] D. Terzopoulos and K. Fleischer, Modeling Inelastic Deformation: Viscoelasticity, Plasticity, Fracture Computer Graphics (Proc. SIGGRAPH '88), vol. 22, no. 4, pp. 269-278, 1988.[46] D. Terzopoulos, J. Platt, A. Barr, and K. Fleischer, Elastically Deformable Models Computer Graphics (Proc. SIGGRAPH '87), vol. 21, no. 4, pp. 205-214, July 1987.[47] D. Terzopoulos and A. Witkin, "Physically Based Models With Rigid and Deformable Components," IEEE Computer Graphics and Application, vol. 8, no. 6, pp. 41-51, 1988.[48] G. van den Bergen, Efficient Collision Detection of Complex Deformable Models Using AABB Trees J. Graphics Tools, vol. 2, no. 4, pp. 1-14, 1999.[49] T. Vassilev, B. Spanlang, and Y. Chrysanthou, Fast Cloth Animation on Walking Avatars Computer Graphics Forum, vol. 20, no. 3, pp. 260-267, Sept. 2001.[50] P. Volino, M. Courchesne, and N. Magnenat-Thalmann, Versatile and Efficient Techniques for Simulating Cloth and Other Deformable Objects Computer Graphics (SIGGRAPH Proc. 1995), pp. 137-144, Aug. 1995.[51] P. Volino and N. Magnenat-Thalmann, Efficient Self-Collision Detection on Smoothly Discretised Surface Animation Using Geometrical Shape Regularity Computer Graphics Forum, Eurographics Proc., vol. 13, no. 3, pp. 155-166, Sept. 1994.[52] P. Volino and N. Magnenat-Thalmann, Collision and Self-Collision Detection: Robust and Efficient Techniques for Highly Deformable Surfaces Proc. Eurographics Workshop Animation and Simulation, 1995.[53] P. Volino and N. Magnenat-Thalmann, Accurate Collision Response on Polygonal Meshes Proc. Computer Animation Conf., pp. 179-188, 2000.[54] P. Volino and N. Magnenat-Thalmann, Implementing Fast Cloth Simulation with Collision Response Computer Graphics Int'l, pp. 257-268, 2000.[55] P. Volino, N. Magnenat-Thalmann, J.H. Shen, and D. Thalmann, An Evolving System for Simulating Clothes on Virtual Actors IEEE Computer Graphics and Applications, vol. 16, no. 5, pp. 42-51, Sept. 1996.[56] Y. Yang and N. Magnenat-Thalmann, An Improved Algorithm for Collision Detection in Cloth Animation with Human Body Proc. First Pacific Conf. Computer Graphics and Applications, pp. 237-251, 1993.[57] M.J. Zyda, D.R. Pratt, D. Osborne, and J.G. Monahan, NPSNET: Real-Time Collision Detection and Response The J. Visualization and Computer Animation, vol. 4, no. 1, pp. 13-24, 1993.
Index Terms:
Collision detection, deformable surfaces, cloth simulation, animation.
Citation:
George Baciu, Wingo Sai-Keung Wong, "Image-Based Collision Detection for Deformable Cloth Models," IEEE Transactions on Visualization and Computer Graphics, vol. 10, no. 6, pp. 649-663, Nov./Dec. 2004, doi:10.1109/TVCG.2004.44
