FastLSM: Fast Lattice Shape Matching
for Robust Real-Time Deformation

Alec Rivers         Doug James
Cornell University


  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 naive 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.
  Alec R. Rivers, Doug L. James: FastLSM: Fast Lattice Shape Matching for Robust Real-Time Deformation ACM Transactions on Graphics (SIGGRAPH 2007), to appear
  FastLSM: Fast Lattice Shape Matching for Robust Real-Time Deformation (5.4 MB)
  SIGGRAPH 2007 Presentation (Includes movies; 40 MB)
  2D demo: A fully tunable 2D demo. Source code included. (Requires Microsoft .NET framework) (426 KB)
  3D demo: A simple 3D demo, with few controls. No source code. (9 MB)
  FastLSM programming library (with source and testbed application): Source code and programming library for a simplified implementation of the FastLSM algorithm, including a testbed application. Slightly slower than the version used to make the demos. Not widely tested. (286 KB)


High-res video  (68 MB). Requires the DivX codec.



2007 Alec Rivers, Doug James