More Web Proxy on the site http://driver.im/

article

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

Authors:

Alec R. Rivers,

Doug L. JamesAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 26, Issue 3

Pages 82 - es

https://doi.org/10.1145/1276377.1276480

Published: 29 July 2007 Publication History

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 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.

Supplementary Material

JPG File (pps082.jpg)

Download
17.54 KB

MP4 File (pps082.mp4)

Download
52.66 MB

References

[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.

Digital 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.

Digital 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.

Digital Library

[4]

Crow, F. C. 1984. Summed-area Tables for Texture Mapping. In Computer Graphics (Proc. of SIGGRAPH 84), vol. 18, 207--212.

Digital 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.

Digital 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.

Digital 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.

[8]

Golub, G., and Van Loan, C. 1996. Matrix Computations, third ed. The Johns Hopkins University Press, Baltimore.

Digital 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.

Digital 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.

[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.

Digital 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.

Digital Library

[13]

Kopp, J., 2006. Efficient numerical diagonalization of Hermitian 3x3 matrices. arXiv:physics/0610206v1 {physics.comp-ph}.

[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.

Digital 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.

Digital 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.

Digital 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.

[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.

Digital 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.

[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.

[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.

Digital 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.

Digital Library

[23]

Terzopoulos, D., and Fleischer, K. 1988. Deformable models. The Visual Computer 4, 6 (Dec.), 306--331.

[24]

Weiss, B. 2006. Fast Median and Bilateral Filtering. ACM Trans. on Graphics 25, 3 (July), 519--526.

Digital Library

[25]

Westermann, R., and Rezk-Salama, C. 2001. Real-Time Volume Deformations. Comp. Graph. Forum 20, 3, 443--451.

[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.

Cited By

Li PXu BZhang XFang DZhang J(2024)Design and development of a personalized virtual reality-based training system for vascular intervention surgeryComputer Methods and Programs in Biomedicine10.1016/j.cmpb.2024.108142249:COnline publication date: 9-Jul-2024
https://dl.acm.org/doi/10.1016/j.cmpb.2024.108142
Bouaziz SMartin SLiu TKavan LPauly M(2023)Projective Dynamics: Fusing Constraint Projections for Fast SimulationSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596794(787-797)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596794
Weiss T(2023)Fast Position-based Multi-Agent Group DynamicsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35855076:1(1-15)Online publication date: 16-May-2023
https://dl.acm.org/doi/10.1145/3585507
Show More Cited By

Index Terms

FastLSM: fast lattice shape matching for robust real-time deformation
1. Computing methodologies
  1. Computer graphics
    1. Animation
      1. Physical simulation
    2. Shape modeling
2. Mathematics of computing
  1. Continuous mathematics
    1. Topology
      1. Geometric topology

Recommendations

FastLSM: fast lattice shape matching for robust real-time deformation
SIGGRAPH '07: ACM SIGGRAPH 2007 papers

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 ...
Deformation and fracturing using adaptive shape matching with stiffness adjustment
CASA' 2009 Special Issue

This paper presents a fast method that computes deformations with fracturing of an object using a hierarchical lattice. Our method allows numerically stable computation based on so-called shape matching. During the simulation, the deformed shape of the ...
Spectral Analysis on Medial Axis of 2D Shapes

Shape analysis finds many important applications in shape understanding, matching and retrieval. Among the various shape analysis methods, spectral shape analysis aims to study the spectrum of the Laplace-Beltrami operator of some well-designed shape-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 26, Issue 3

July 2007

976 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1276377

Issue’s Table of Contents

Copyright © 2007 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Published in TOG Volume 26, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

131
Total Citations
View Citations
1,888
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)4

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li PXu BZhang XFang DZhang J(2024)Design and development of a personalized virtual reality-based training system for vascular intervention surgeryComputer Methods and Programs in Biomedicine10.1016/j.cmpb.2024.108142249:COnline publication date: 9-Jul-2024
https://dl.acm.org/doi/10.1016/j.cmpb.2024.108142
Bouaziz SMartin SLiu TKavan LPauly M(2023)Projective Dynamics: Fusing Constraint Projections for Fast SimulationSeminal Graphics Papers: Pushing the Boundaries, Volume 210.1145/3596711.3596794(787-797)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1145/3596711.3596794
Weiss T(2023)Fast Position-based Multi-Agent Group DynamicsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35855076:1(1-15)Online publication date: 16-May-2023
https://dl.acm.org/doi/10.1145/3585507
Tong QWei WZhang YXiao JWang D(2023)Survey on Hand-Based Haptic Interaction for Virtual RealityIEEE Transactions on Haptics10.1109/TOH.2023.326619916:2(154-170)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TOH.2023.3266199
dell’Erba RD’Avanzo PRapisarda A(2023)A comparison between the finite element method and a kinematic model derived from robot swarms for first and second gradient continuaContinuum Mechanics and Thermodynamics10.1007/s00161-023-01217-935:4(1769-1786)Online publication date: 10-Apr-2023
https://doi.org/10.1007/s00161-023-01217-9
KILIÇ ÖNEN SASLANDAĞ A(2022)Sac ve Levhalar İçin Serbest Deformasyon MakinasıFree Deformation Machine For SheetsOsmaniye Korkut Ata Üniversitesi Fen Bilimleri Enstitüsü Dergisi10.47495/okufbed.10345315:Özel Sayı(227-233)Online publication date: 23-Feb-2022
https://doi.org/10.47495/okufbed.1034531
Xing JRuan LWang BZhu BChen B(2022)Position-Based Surface Tension FlowACM Transactions on Graphics10.1145/3550454.355547641:6(1-12)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555476
Fujita KMorimoto YTomotari M(2021)blobby: Generation of Fluid Style Effects in Hand-drawn Animationblobby: 手描きアニメーションにおける流体調表現の生成The Journal of the Society for Art and Science10.3756/artsci.20.4020:1(40-44)Online publication date: 30-Mar-2021
https://doi.org/10.3756/artsci.20.40
Kumar ARank S(2021)BEAPS: Integrating Volumetric Dynamics in Virtual Agent PrototypingAdvances in Visual Computing10.1007/978-3-030-90439-5_34(427-438)Online publication date: 4-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-90439-5_34
QIN XWU TLIU Y(2020)A surface deformation method based on stiffness controlJournal of Advanced Mechanical Design, Systems, and Manufacturing10.1299/jamdsm.2020jamdsm001014:1(JAMDSM0010-JAMDSM0010)Online publication date: 2020
https://doi.org/10.1299/jamdsm.2020jamdsm0010
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents