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. Baraff, D., and Witkin, A. 1998. Large steps in cloth Simulation. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM Press, 43--54.]]
2. Benzi, M., and Tuma, M. 1999. A comparative study of sparse approximate inverse preconditioners. Applied Numerical Mathematics: Transactions of IMACS 30, 2--3, 305--340.]]
3. Benzi, M., Cullum, J. K., and Tuma, M. 2000. Robust approximate inverse preconditioning for the conjugate gradient method. SIAM Journal on Scientific Computing 22, 4, 1318--1332.]]
4. Bridson, R., and Tang, W.-P. 2001. Multiresolution approximate inverse preconditioners. SIAM Journal on Scientific Computing 23, 2, 463--479.]]
5. Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, 28--36.]]
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. Capell, S., Green, S., Curless, B., Duchamp, T., and Popovic, Z. 2002. Interactive skeleton-driven dynamic deformations. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM Press, 586--593.]]
8. Capell, S., Green, S., Curless, B., Duchamp, T., and Popovic, Z. 2002. A multiresolution framework for dynamic deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, ACM Press, 41--47.]]
9. Chadwick, J. E., Haumann, D. R., and Parent, R. E. 1989. Layered construction for deformable animated characters. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques, ACM Press, 243--252.]]
10. Choi, K.-J., and Ko, H.-S. 2002. Stable but responsive cloth. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM Press, 604--611.]]
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. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space & time adaptive sampling. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM Press, 3136.]]
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. Grinspun, E., Krysl, P., and Schröder, P. 2002. Charms: a simple framework for adaptive simulation. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM Press, 281--290.]]
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. James, D. L., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM Trans. Graph. 22, 3, 879--887.]]
19. James, D. L., and Pai, D. K. 1999. Artdefo: accurate real time deformable objects. In Proceedings of the 26th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 65--72.]]
20. James, D. L., and Pai, D. K. 2002. Dyrt: dynamic response textures for real time deformation simulation with graphics hardware. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques, ACM Press, 582--585.]]
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. James, D. L., and Pai, D. K. 2003. Multiresolution green's function methods for interactive simulation of large-scale elastostatic objects. ACM Trans. Graph. 22, 1, 47--82.]]
23. Müller, M., and Gross, M. 2004. Interactive virtual materials. In GI '04: Proceedings of the 2004 conference on Graphics interface, Canadian Human-Computer Communications Society, 239--246.]]
24. Müller, M., Dorsey, J., Mcmillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, ACM Press, 49--54.]]
25. Pai, D. K., Van Den Doel, K., James, D. L., Lang, J., Lloyd, J. E., Richmond, J. L., and Yau, S. H. 2001. Scanning physical interaction behavior of 3d objects. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques, ACM Press, 87--96.]]
26. Pentland, A., and Williams, J. 1989. Good vibrations: model dynamics for graphics and animation. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques, ACM Press, 215--222.]]
27. Quarteroni, A., and Valli, A. 1999. Domain Decomposition Methods for Partial Differential Equations. Oxford Science Publications, Clarendon Press, Oxford.]]
28. Sloan, P.-P., Hall, J., Hart, J., and Snyder, J. 2003. Clustered principal components for precomputed radiance transfer. ACM Trans. Graph. 22, 3, 382--391.]]
29. Stam, J. 1997. Stochastic dynamics: Simulating the effects of turbulence on flexible structures. Comput Graphics Forum 16, 3 (Sept.), 159--164.]]
30. Terzopoulos, D., and Witkin, A. 1988. Physically based models with rigid and deformable components. IEEE Comput. Graph. Appl. 8, 6, 41--51.]]
31. Tu, X., and Terzopoulos, D. 1994. Artificial fishes: physics, locomotion, perception, behavior. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques, ACM Press, 43--50.]]
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

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Shape modeling

• Mathematics of computing

  • Continuous mathematics

    • Topology

      • Geometric topology