skip to main content
research-article

Optimizing cubature for efficient integration of subspace deformations

Published: 01 December 2008 Publication History

Abstract

We propose an efficient scheme for evaluating nonlinear subspace forces (and Jacobians) associated with subspace deformations. The core problem we address is efficient integration of the subspace force density over the 3D spatial domain. Similar to Gaussian quadrature schemes that efficiently integrate functions that lie in particular polynomial subspaces, we propose cubature schemes (multi-dimensional quadrature) optimized for efficient integration of force densities associated with particular subspace deformations, particular materials, and particular geometric domains. We support generic subspace deformation kinematics, and nonlinear hyperelastic materials. For an r-dimensional deformation subspace with O(r) cubature points, our method is able to evaluate sub-space forces at O(r2) cost. We also describe composite cubature rules for runtime error estimation. Results are provided for various subspace deformation models, several hyperelastic materials (St.Venant-Kirchhoff, Mooney-Rivlin, Arruda-Boyce), and multi-modal (graphics, haptics, sound) applications. We show dramatically better efficiency than traditional Monte Carlo integration.

Supplementary Material

JPG File (a165-an-mp4_hi.jpg)
MOV File (a165-an-mp4_hi.mov)

References

[1]
Baraff, D., and Witkin, A. 1992. Dynamic simulation of non-penetrating flexible bodies. In Computer Graphics (Proceedings of SIGGRAPH 92), 303--308.
[2]
Barbič, J., and James, D. L. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. on Graphics 24, 3 (Aug.), 982--990.
[3]
Barbič, J., and James, D. L. 2007. Time-critical distributed contact for 6-dof haptic rendering of adaptively sampled reduced deformable models. In Proceedings of ACM SIGGRAPH Symposium on Computer Animation (SCA 2007), San Diego, CA.
[4]
Barbič, J. 2007. Real-time Reduced Large-Deformation Models and Distributed Contact for Computer Graphics and Haptics. PhD thesis, Carnegie Mellon University.
[5]
Bathe, K.-J. 1996. Finite Element Procedures, second ed. Prentice Hall.
[6]
Bonet, J., and Wood, R. D. 2008. Nonlinear Continuum Mechanics for Finite Element Analysis, second ed. Cambridge University Press, New York.
[7]
Capell, S., Green, S., Curless, B., Duchamp, T., and Popović, Z. 2002. A Multiresolution Framework for Dynamic Deformations. In ACM SIGGRAPH Symposium on Computer Animation, 41--48.
[8]
Choi, M. G., and Ko, H.-S. 2005. Modal Warping: Real-Time Simulation of Large Rotational Deformation and Manipulation. IEEE Transactions on Visualization and Computer Graphics 11, 1 (Jan./Feb.), 91--101.
[9]
Cotin, S., Delingette, H., and Ayache, N. 1999. Real-time elastic deformations of soft tissues for surgery simulation. IEEE Transactions on Visualization and Computer Graphics 5, 1 (Jan./ Mar.), 62--73.
[10]
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.
[11]
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.
[12]
Grzeszczuk, R., Terzopoulos, D., and Hinton, G. 1998. NeuroAnimator: Fast Neural Network Emulation and Control of Physics-Based Models. In Proc. of SIGGRAPH 98, Computer Graphics Proceedings, Annual Conference Series, 9--20.
[13]
Heath, M. T. 2002. Scientific Computing: An Introductory Survey. McGraw-Hill Higher Education, New York.
[14]
Hildebrand, F. B. 1956. Introduction to Numerical Analysis. McGraw-Hill, New York.
[15]
Hoberock, J., and Jia, Y. 2008. Chapter 12: High-Quality Ambient Occlusion. In GPU Gems 3, H. Nguyen, Ed. Addison-Wesley, 257--274.
[16]
James, D. L., and Fatahalian, K. 2003. Precomputing interactive dynamic deformable scenes. ACM Transactions on Graphics 22, 3 (July), 879--887.
[17]
James, D. L., and Pai, D. K. 1999. ArtDefo: Accurate real time deformable objects. In Proceedings of SIGGRAPH 99, Computer Graphics Proceedings, Annual Conference Series, 65--72.
[18]
James, D. L., and Pai, D. K. 2002. DyRT: Dynamic response textures for real time deformation simulation with graphics hardware. ACM Transactions on Graphics 21, 3 (July), 582--585.
[19]
James, D. L., and Twigg, C. D. 2005. Skinning mesh animations. ACM Transactions on Graphics 24, 3 (Aug.), 399--407.
[20]
James, D. L., Barbič, J., and Pai, D. K. 2006. Precomputed Acoustic Transfer: Output-sensitive, accurate sound generation for geometrically complex vibration sources. ACM Transactions on Graphics 25, 3 (July), 987--995.
[21]
Kaufmann, P., Martin, S., Botsch, M., and Gross, M. 2008. Flexible Simulation of Deformable Models Using Discontinuous Galerkin FEM. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 105--115.
[22]
Kry, P. G., James, D. L., and Pai, D. K. 2002. EigenSkin: Real Time Large Deformation Character Skinning in Hardware. In ACM SIGGRAPH Symposium on Computer Animation, 153--160.
[23]
Krysl, P., Lall, S., and Marsden, J. E. 2001. Dimensional model reduction in non-linear finite element dynamics of solids and structures. International Journal for Numerical Methods in Engineering 51, 479--504.
[24]
Lawson, C. L., and Hanson, R. J. 1974. Solving Least Square Problems. Prentice Hall, Englewood Cliffs, NJ.
[25]
Lewis, J. P., Cordner, M., and Fong, N. 2000. Pose Space Deformations: A Unified Approach to Shape Interpolation and Skeleton-Driven Deformation. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series, 165--172.
[26]
Liu, Y., Kerdok, A. E., and Howe, R. D. 2004. A nonlinear finite element model of soft tissue indentation. In Proc. Intl. Symp. Medical Simulation (ISMS 2004), Lecture Notes in Computer Science, vol. 3078, Springer-Verlag, S. Cotin and D. Metaxas, Eds., 67--76.
[27]
Meyer, M., and Anderson, J. 2007. Key Point Subspace Acceleration and Soft Caching. ACM Transactions on Graphics 26, 3 (July), 74:1--74:8.
[28]
Nelles, O. 2000. Nonlinear System Identification: From Classical Approaches to Neural Networks and Fuzzy Models. Springer Verlag, December.
[29]
O'Brien, J. F., Cook, P. R., and Essl, G. 2001. Synthesizing sounds from physically based motion. In Proceedings of ACM SIGGRAPH 2001, Computer Graphics Proceedings, Annual Conference Series, 529--536.
[30]
Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. In Computer Graphics (Proceedings of SIGGRAPH 89), 215--222.
[31]
Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, New York, NY, USA. (Gaussian quadrature is discussed in section 4.5).
[32]
Terzopoulos, D., and Witkin, A. 1988. Physically Based Models with Rigid and Deformable Components. IEEE Computer Graphics & Applications 8, 6 (Nov.), 41--51.
[33]
Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically Deformable Models. In Computer Graphics (Proceedings of SIGGRAPH 87), 205--214.
[34]
Vakakis, A. 2001. Normal modes and localization in nonlinear systems. Kluwer Academic Publishers.
[35]
Witkin, A., and Welch, W. 1990. Fast Animation and Control of Nonrigid Structures. In Computer Graphics (Proceedings of SIGGRAPH 90), 243--252.

Cited By

View all
  • (2024)DBSF-Net: Infrared Image Colorization Based on the Generative Adversarial Model with Dual-Branch Feature Extraction and Spatial-Frequency-Domain DiscriminationRemote Sensing10.3390/rs1620376616:20(3766)Online publication date: 10-Oct-2024
  • (2024)Near-realtime Facial Animation by Deep 3D Simulation Super-ResolutionACM Transactions on Graphics10.1145/367068743:5(1-20)Online publication date: 9-Aug-2024
  • (2024)Highly Efficient Modeling of Solder Balls and Their Visco-plastic Behavior Applying the Energy Conserving Sampling and Weighting Method2024 IEEE 10th Electronics System-Integration Technology Conference (ESTC)10.1109/ESTC60143.2024.10712055(1-8)Online publication date: 11-Sep-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics
ACM Transactions on Graphics  Volume 27, Issue 5
December 2008
552 pages
ISSN:0730-0301
EISSN:1557-7368
DOI:10.1145/1409060
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2008
Published in TOG Volume 27, Issue 5

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. dimensional model reduction
  2. dynamic deformations
  3. nonlinear solid mechanics
  4. quadrature
  5. real-time simulation
  6. reduced-order modeling
  7. subspace dynamics
  8. subspace integration

Qualifiers

  • Research-article

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)65
  • Downloads (Last 6 weeks)11
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)DBSF-Net: Infrared Image Colorization Based on the Generative Adversarial Model with Dual-Branch Feature Extraction and Spatial-Frequency-Domain DiscriminationRemote Sensing10.3390/rs1620376616:20(3766)Online publication date: 10-Oct-2024
  • (2024)Near-realtime Facial Animation by Deep 3D Simulation Super-ResolutionACM Transactions on Graphics10.1145/367068743:5(1-20)Online publication date: 9-Aug-2024
  • (2024)Highly Efficient Modeling of Solder Balls and Their Visco-plastic Behavior Applying the Energy Conserving Sampling and Weighting Method2024 IEEE 10th Electronics System-Integration Technology Conference (ESTC)10.1109/ESTC60143.2024.10712055(1-8)Online publication date: 11-Sep-2024
  • (2024)Subspace graph networks for real-time granular flow simulation with applications to machine-terrain interactionsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108765135:COnline publication date: 1-Sep-2024
  • (2024)A hyperreduced reduced basis element method for reduced-order modeling of component-based nonlinear systemsComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2024.117254431(117254)Online publication date: Nov-2024
  • (2024)Hyperreduced-order modeling of thermally coupled flowsApplied Mathematical Modelling10.1016/j.apm.2023.08.028125(59-81)Online publication date: Jan-2024
  • (2024)Model reduction techniques for parametrized nonlinear partial differential equationsError Control, Adaptive Discretizations, and Applications, Part 110.1016/bs.aams.2024.03.005(135-190)Online publication date: 2024
  • (2023)Scalable Projection-Based Reduced-Order Models for Large Multiscale Fluid SystemsAIAA Journal10.2514/1.J06286961:10(4499-4523)Online publication date: Oct-2023
  • (2023)Modal-graph 3D shape servoing of deformable objects with raw point cloudsInternational Journal of Robotics Research10.1177/0278364923119890042:14(1213-1244)Online publication date: 1-Dec-2023
  • (2023)Progressive Shell Qasistatics for Unstructured MeshesACM Transactions on Graphics10.1145/361838842:6(1-17)Online publication date: 5-Dec-2023
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media