Clustering method for fast deformation with constraints

ABSTRACT

We present a fast deformation method for flexible objects. The deformation of the object is physically modeled using a linear elasticity model with a displacement based finite elements method, yielding a linear system at each time step of simulation. We solve this linear system using a precomputed force-displacement matrix, which describes the object response in terms of displacement accelerations to the forces acting on each vertex. We exploit the spatial coherence to effectively compress the force-displacement matrix to make this method practical and efficient by applying the clustered principal component analysis method. And we developed a method to efficiently handle the additional constraints for interactive user manipulation. At last large deformations are addressed based upon the compressed force-displacement matrix by combining a domain decomposition method and tracking the rotational motions. The experimental results demonstrate fast performances on complex large scale objects under interactive user manipulations.

REFERENCES

• 1: 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]
• 2: Michele Benzi , Miroslav Tůma, A comparative study of sparse approximate inverse preconditioners, Applied Numerical Mathematics, v.30 n.2-3, p.305-340, June 1999
• 3: Michele Benzi , Jane K. Cullum , Miroslav Tuma, Robust Approximate Inverse Preconditioning for the Conjugate Gradient Method, SIAM Journal on Scientific Computing, v.22 n.4, p.1318-1332, 2000 [doi>10.1137/S1064827599356900]
• 4: Robert Bridson , Wei-Pai Tang, Multiresolution Approximate Inverse Preconditioners, SIAM Journal on Scientific Computing, v.23 n.2, p.463-479, 2001 [doi>10.1137/S1064827500373784]
• 5: R. Bridson , S. Marino , R. Fedkiw, Simulation of clothing with folds and wrinkles, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 6: Bro-Nielsen, M., and Cotin, S. 1996. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum 15, 3, 57--66.
• 7: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, Interactive skeleton-driven dynamic deformations, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 8: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, A multiresolution framework for dynamic deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545268]
• 9: J. E. Chadwick , D. R. Haumann , R. E. Parent, Layered construction for deformable animated characters, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.243-252, July 1989
• 10: Kwang-Jin Choi , Hyeong-Seok Ko, Stable but responsive cloth, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 11: Cook, R. D., Malkus, D. S., and Plesha, M. E. 1989. Concepts and Applications of Finite Element Analysis, 3rd edition ed. John Wiley & Sons.
• 12: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 13: Gibson, S. F. F., and Mirtich, B. 1997. A survey of deformable modeling in computer graphics. Tech. Rep. TR-97--19, Mitsubish Electric Research Lab., Cambridge, November.
• 14: Eitan Grinspun , Petr Krysl , Peter Schröder, CHARMS: a simple framework for adaptive simulation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 15: Hauser, K., Shen, C., and O'Brien, J. F. 2003. Interactive deformations using modal analysis with constraints. In Proceedings of Graphics Interface 2003, 247--256.
• 16: Hauth, M., and Etzmuss, O. 2001. A high performance solver for the animation of deformable objects using advanced numerical methods. In Proceedings of Eurograhics, 137--151.
• 17: J. Lang, D. K. P., and Seidel, H.-P. 2003. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. proceedings of Graphics Interface (June).
• 18: Doug L. James , Kayvon Fatahalian, Precomputing interactive dynamic deformable scenes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 19: Doug L. James , Dinesh K. Pai, ArtDefo: accurate real time deformable objects, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.65-72, July 1999 [doi>10.1145/311535.311542]
• 20: Doug L. James , Dinesh K. Pai, DyRT: dynamic response textures for real time deformation simulation with graphics hardware, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 21: James, D. L., and Pai, D. K. 2002. Real time simulation of multizone elastokinematic models. In Proceedings of the IEEE International Conference on Robotics and Automation, 927--932.
• 22: Doug L. James , Dinesh K. Pai, Multiresolution green's function methods for interactive simulation of large-scale elastostatic objects, ACM Transactions on Graphics (TOG), v.22 n.1, p.47-82, January 2003 [doi>10.1145/588272.588278]
• 23: Matthias Müller , Markus Gross, Interactive virtual materials, Proceedings of the 2004 conference on Graphics interface, p.239-246, May 17-19, 2004, London, Ontario, Canada
• 24: Matthias Müller , Julie Dorsey , Leonard McMillan , Robert Jagnow , Barbara Cutler, Stable real-time deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545269]
• 25: Dinesh K. Pai , Kees van den Doel , Doug L. James , Jochen Lang , John E. Lloyd , Joshua L. Richmond , Som H. Yau, Scanning physical interaction behavior of 3D objects, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.87-96, August 2001 [doi>10.1145/383259.383268]
• 26: A. Pentland , J. Williams, Good vibrations: model dynamics for graphics and animation, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.215-222, July 1989
• 27: Quarteroni, A., and Valli, A. 1999. Domain Decomposition Methods for Partial Differential Equations. Oxford Science Publications, Clarendon Press, Oxford.
• 28: Peter-Pike Sloan , Jesse Hall , John Hart , John Snyder, Clustered principal components for precomputed radiance transfer, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 29: Stam, J. 1997. Stochastic dynamics: Simulating the effects of turbulence on flexible structures. Comput Graphics Forum 16, 3 (Sept.), 159--164.
• 30: 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]
• 31: Xiaoyuan Tu , Demetri Terzopoulos, Artificial fishes: physics, locomotion, perception, behavior, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.43-50, July 1994 [doi>10.1145/192161.192170]
• 32: Wu, X., Downes, M. S., Goktekin, T., and Tendick, F. 2001. Adaptive nonlinear finite elements for deformable body simulation using dynamic progressive meshes. Comput Graphics Forum 20, 3 (Sept.), 349--358.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

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

Keywords:
clustered principal component analysis, deformation, domain decomposition method, finite element method