“FastLSM: fast lattice shape matching for robust real-time deformation” by Rivers and James

We introduce a simple technique that enables robust approximation of volumetric, large-deformation dynamics for real-time or large-scale offline simulations. We propose Lattice Shape Matching, an extension of deformable shape matching to regular lattices with embedded geometry; lattice vertices are smoothed by convolution of rigid shape matching operators on local lattice regions, with the effective mechanical stiffness specified by the amount of smoothing via region width. Since the naïve method can be very slow for stiff models – per-vertex costs scale cubically with region width – we provide a fast summation algorithm, Fast Lattice Shape Matching (FastLSM), that exploits the inherent summation redundancy of shape matching and can provide large-region matching at constant per-vertex cost. With this approach, large lattices can be simulated in linear time. We present several examples and benchmarks of an efficient CPU implementation, including many dozens of soft bodies simulated at real-time rates on a typical desktop machine.

1. Barbič, J., and James, D. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. on Graphics 24, 3 (Aug.), 982–990. Google ScholarDigital Library
2. Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. Interactive Skeleton-Driven Dynamic Deformations. ACM Trans. on Graphics 21, 3 (July), 586–593. Google ScholarDigital Library
3. Coquillart, S. 1990. Extended Free-Form Deformation: A Sculpturing Tool for 3D Geometric Modeling. In Computer Graphics (Proc. of SIGGRAPH 90), vol. 24, 187–196. Google ScholarDigital Library
4. Crow, F. C. 1984. Summed-area Tables for Texture Mapping. In Computer Graphics (Proc. of SIGGRAPH 84), vol. 18, 207–212. Google ScholarDigital Library
5. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic Real-Time Deformations Using Space & Time Adaptive Sampling. In Proc. of ACM SIGGRAPH 2001, 31–36. Google ScholarDigital Library
6. Faloutsos, P., van de Panne, M., and Terzopoulos, D. 1997. Dynamic Free-Form Deformations for Animation Synthesis. IEEE Trans. on Visualization and Computer Graphics 3, 3 (July – September), 201–214. Google ScholarDigital Library
7. Gibson, S. F., and Mirtich, B. 1997. A Survey of Deformable Models in Computer Graphics. Tech. Rep. TR-97-19, Mitsubishi Electric Research Laboratories, Cambridge, MA, November.Google Scholar
8. Golub, G., and Van Loan, C. 1996. Matrix Computations, third ed. The Johns Hopkins University Press, Baltimore. Google ScholarDigital Library
9. Grinspun, E., Krysl, P., and Schröder, P. 2002. CHARMS: A Simple Framework for Adaptive Simulation. ACM Trans. on Graphics 21, 3 (July), 281–290. Google ScholarDigital Library
10. Hensley, J., Scheuermann, T., Coombe, G., Singh, M., and Lastra, A. 2005. Fast Summed-Area Table Generation and its Applications. Computer Graphics Forum 24, 3, 547–556.Google ScholarCross Ref
11. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In 2004 ACM SIGGRAPH / Eurographics Symposium on Computer Animation, 131–140. Google ScholarDigital Library
12. James, D. L., Barbič, J., and Twigg, C. D. 2004. Squashing Cubes: Automating Deformable Model Construction for Graphics. In Proc. of the SIGGRAPH 2004 Conference on Sketches & Applications, ACM Press. Google ScholarDigital Library
13. Kopp, J., 2006. Efficient numerical diagonalization of Hermitian 3×3 matrices. arXiv:physics/0610206v1 {physics.comp-ph}.Google Scholar
14. MacCracken, R., and Joy, K. I. 1996. Free-Form Deformations with Lattices of Arbitrary Topology. In Proc. of SIGGRAPH 96, Computer Graphics Proc., 181–188. Google ScholarDigital Library
15. Molino, N., Bao, Z., and Fedkiw, R. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Trans. on Graphics 23, 3 (Aug.), 385–392. Google ScholarDigital Library
16. Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable Real-Time Deformations. In ACM SIGGRAPH Symposium on Computer Animation, 49–54. Google ScholarDigital Library
17. Müller, M., Teschner, M., and Gross, M. 2004. Physically based simulation of objects represented by surface meshes. In Proc. of Computer Graphics International (CGI), 26–33. Google ScholarCross Ref
18. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless Deformations Based on Shape Matching. ACM Trans. on Graphics 24, 3 (Aug.), 471–478. Google ScholarDigital Library
19. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2006. Position Based Dynamics. In Proc. of Virtual Reality Interactions and Physical Simulations (VRIPhys), 71–80.Google Scholar
20. Nealen, A., Muller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Eurographics: State of the Art Report.Google Scholar
21. Sederberg, T. W., and Parry, S. R. 1986. Free-Form Deformation of Solid Geometric Models. In Computer Graphics (Proc. SIGGRAPH 86), vol. 20, 151–160. Google ScholarDigital Library
22. Sifakis, E., Neverov, I., and Fedkiw, R. 2005. Automatic determination of facial muscle activations from sparse motion capture marker data. ACM Trans. on Graphics 24, 3, 417–425. Google ScholarDigital Library
23. Terzopoulos, D., and Fleischer, K. 1988. Deformable models. The Visual Computer 4, 6 (Dec.), 306–331.Google ScholarCross Ref
24. Weiss, B. 2006. Fast Median and Bilateral Filtering. ACM Trans. on Graphics 25, 3 (July), 519–526. Google ScholarDigital Library
25. Westermann, R., and Rezk-Salama, C. 2001. Real-Time Volume Deformations. Comp. Graph. Forum 20, 3, 443–451.Google ScholarCross Ref
26. Wicke, M., Hatt, P., Pauly, M., Mueller, M., and Gross, M. 2006. Versatile virtual materials using implicit connectivity. In Eurographics Symposium on Point-Based Graphics, Boston, USA, 29–30 July, 73–82. Google ScholarCross Ref