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

  • ©Alec Rivers and Doug L. James




    FastLSM: fast lattice shape matching for robust real-time deformation



    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

ACM Digital Library Publication:

Overview Page: