Alec R. Rivers and
Doug L. James,
FastLSM: Fast Lattice Shape
Matching for Robust Real-Time Deformation,
ACM Transactions on Graphics (Proc. SIGGRAPH
2007), 26(3), July 2007, pp. 82:1-82:6.
ABSTRACT: 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.
Paper (PDF, 5.4MB)
Project page (with videos and downloadable demo)
