“Meshless deformations based on shape matching” by Müller-Fischer, Heidelberger, Teschner and Gross

We present a new approach for simulating deformable objects. The underlying model is geometrically motivated. It handles pointbased objects and does not need connectivity information. The approach does not require any pre-processing, is simple to compute, and provides unconditionally stable dynamic simulations.The main idea of our deformable model is to replace energies by geometric constraints and forces by distances of current positions to goal positions. These goal positions are determined via a generalized shape matching of an undeformed rest state with the current deformed state of the point cloud. Since points are always drawn towards well-defined locations, the overshooting problem of explicit integration schemes is eliminated. The versatility of the approach in terms of object representations that can be handled, the efficiency in terms of memory and computational complexity, and the unconditional stability of the dynamic simulation make the approach particularly interesting for games.

1. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Computer Graphics Proceedings. Annual Conference Series, ACM SIGGRAPH 2000, 157–164. Google ScholarDigital Library
2. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH 1998, 43–54. Google ScholarDigital Library
3. Barzel, R., Hughes, J. F., and Wood, D. N. 1996. Plausible motion simulation for computer graphics animation. Proceedings of the Eurographics Workshop on Computer Animation and Simulation, 183–197. Google ScholarDigital Library
4. Barzel, R. 1997. Faking dynamics of ropes and springs. IEEE Computer Graphics and Applications 17, 31–39. Google ScholarDigital Library
5. Besl, P., and McKay, N. 1992. A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 14, 2, 239–256. Google ScholarDigital Library
6. Capell, S., Green, S., Curless, B., Duchamp, T., and Popovic, Z. 2002. Interactive skeleton-driven dynamic deformations. In Proceedings of SIGGRAPH 2002, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 586–593. Google ScholarDigital Library
7. Debunne, G., Desbrun, M., Cani, M. P., and Barr, A. H. 2001. Dynamic real-time deformations using space & time adaptive sampling. In Computer Graphics Proceedings, Annual Conference Series. ACM SIGGRAPH 2001, 31–36. Google ScholarDigital Library
8. Desbrun, M., and Cani, M.-P. 1995. Animating soft substances with implicit surfaces. In Computer Graphics Proceedings. ACM SIGGRAPH, 287–290. Google ScholarDigital Library
9. Desbrun, M., and Cani, M.-P. 1996. Smoothed particles: A new paradigm for animating highly deformable bodies. In 6th Eurographics Workshop on Computer Animation and Simulation ’96, 61–76. Google ScholarDigital Library
10. Desbrun, M., Schroder, P. and Barr. A. H. 1999. Interactive animation of structured deformable objects. In Graphics Interface. 1–8. Google ScholarDigital Library
11. Eberly, D. H. 2003. Game Physics. Morgan Kaufmann. Google ScholarDigital Library
12. Faugeras, O. D., and Hebert, M. 1983. A 3-d recognition and positioning algorithm using geometric matching between primitive surfaces. In Int. Joint Conference on Artificial Intelligence, 996–1002.Google Scholar
13. Grinspun, E., Krysl, P., and Schroder, P. 2002. Charms: A simple framework for adaptive simulation. In Proceedings of SIGGRAPH 2002, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 281–290. Google ScholarDigital Library
14. Hauser, K. K., Shen, C., and O’Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Graphics Interface, A K Peters, CIPS, Canadian Human-Computer Communication Society, 247-256.Google Scholar
15. Heidelberger, B., Teschner, M., Keiser, R., Müller, M., and Gross, M. 2004. Consistent penetration depth estimation for deformable collision response. In Proceedings of Vision, Modeling, Visualization VMV’04, Stanford, USA, 339–346.Google Scholar
16. Horn, B. K. P. 1987. Closed-form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America A 4, 4, 629-642.Google ScholarCross Ref
17. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. Eurographics (Sept.), 131–140. Google ScholarDigital Library
18. James, D., and Pai, D. K. 1999. Artdefo, accurate real time deformable objects. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH 99, 65–72. Google ScholarDigital Library
19. James, D. L., and Pai, D. K. 2002. Dyrt: Dynamic response textures for real time deformation simulation with graphics hardware. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, 582–585. Google ScholarDigital Library
20. James, D. L., and Pai, D. K. 2004. Bd-tree: output-sensitive collision detection for reduced deformable models. ACM Trans. Graph. 23, 3, 393–398. Google ScholarDigital Library
21. Kanatani, K. 1994. Analysis of 3-d rotation fitting. IEEE Trans. Pattern Anal. Mach. Intell. 16, 5, 543–549. Google ScholarDigital Library
22. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Shape matching and anisotropy. ACM Trans. Graph. 23, 3, 623–629. Google ScholarDigital Library
23. Kent, J. R., Carlson, W. E., and Parent, R. E. 1992. Shape transformation for polyhedral objects. Computer Graphics 26, 47–54. Google ScholarDigital Library
24. Lorusso, A., Eggert, D. W., and Fisher, R. B. 1995. A comparison of four algorithms for estimating 3-d rigid transformations. In BMVC ’95: Proceedings of the 1995 British conference on Machine vision (Vol. 1), BMVA Press, 237–246. Google ScholarDigital Library
25. Metaxas, D., and Terzopoulos, D. 1992. Dynamic deformation of solid primitives with constraints. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH 1992, 309–312. Google ScholarDigital Library
26. Müller, M., and Gross, M. 2004. Interactive virtual materials. Proceedings of Graphics Interface (GI 2004), 239–246. Google ScholarDigital Library
27. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. Proceedings of 2002 ACM SIGGRAPH Symposium on Computer Animation, 49–54. Google ScholarDigital Library
28. Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., and Alexa, M. 2004. Point based animation of elastic, plastic and melting objects. Proceedings of 2004 ACM SIGGRAPH Symposium on Computer Animation, 141–151. Google ScholarDigital Library
29. O’Brien, J. F., Bargteil, A. W., and Hodgins, J. K. 2002, Graphical modeling and animation of ductile fracture. In Proceedings of SIGGRAPH 2002, ACM Press / ACM SIGGRAPH, Computer Graphics Proceedings, Annual Conference Series, ACM, 291–294. Google ScholarDigital Library
30. Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, 215–222. Google ScholarDigital Library
31. Shen, C., Hauser, K., Gatchalian, C., and O’Brien, J. 2002. Modal analysis for real-time viscoelastic deformation. ACM SIGGRAPH 2002 Conference Abstracts and Applications (july). Google ScholarDigital Library
32. Shoemake, K., and Duff, T. 1992. Matrix animation and polar decomposition. In Graphics Interface, 258–264. Google ScholarDigital Library
33. Teran, J., Blemker, S., Hing, V. N. T., and Fedkiw, R. 2003. Finite volume methods for the simulation of skeletal muscle. Proceedings of 2003 ACM SIGGRAPH Symposium on Computer Animation, 68–74. Google ScholarDigital Library
34. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH 87, 205–214. Google ScholarDigital Library
35. Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision, Modeling, Visualization VMV’03, 47–54.Google Scholar
36. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Computer Graphics Forum 24, 1 (March), 61–81.Google ScholarCross Ref
37. Tonnesen, D. 1998. Dynamically Coupled Particle Systems for Geometric Modeling, Reconstruction, and Animation. PhD thesis, University of Toronto. Google ScholarDigital Library
38. Umeyama, S. 1991. Least squares estimation of transformation parameters between two point patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence 13, 4 (Apr.), 376–80. Google ScholarDigital Library