Optimizing cubature for efficient integration of subspace deformations

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(r²) 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.

REFERENCES

• 1: David Baraff , Andrew Witkin, Dynamic simulation of non-penetrating flexible bodies, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.303-308, July 1992
• 2: Jernej Barbič , Doug L. James, Real-Time subspace integration for St. Venant-Kirchhoff deformable models, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 3: Jernej Barbič , Doug James, Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 02-04, 2007, San Diego, California
• 4: Jernej Barbic , Doug L. James, Real-time reduced large-deformation models and distributed contact for computer graphics and haptics, Carnegie Mellon University, Pittsburgh, PA, 2007
• 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: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, A multiresolution framework for dynamic deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545268]
• 8: Min Gyu Choi , Hyeong-Seok Ko, Modal Warping: Real-Time Simulation of Large Rotational Deformation and Manipulation, IEEE Transactions on Visualization and Computer Graphics, v.11 n.1, p.91-101, January 2005 [doi>10.1109/TVCG.2005.13]
• 9: Stéphane Cotin , Hervé Delingette , Nicholas Ayache, Real-Time Elastic Deformations of Soft Tissues for Surgery Simulation, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.62-73, January 1999 [doi>10.1109/2945.764872]
• 10: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 11: Eitan Grinspun , Petr Krysl , Peter Schröder, CHARMS: a simple framework for adaptive simulation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 12: Radek Grzeszczuk , Demetri Terzopoulos , Geoffrey Hinton, NeuroAnimator: fast neural network emulation and control of physics-based models, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.9-20, July 1998 [doi>10.1145/280814.280816]
• 13: Michael T. Heath , Eric M. Munson, Scientific Computing: An Introductory Survey, McGraw-Hill Higher Education, 1996
• 14: Begnaud Francis Hildebrand, Introduction to numerical analysis: 2nd edition, Dover Publications, Inc., New York, NY, 1987
• 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: Doug L. James , Kayvon Fatahalian, Precomputing interactive dynamic deformable scenes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 17: Doug L. James , Dinesh K. Pai, ArtDefo: accurate real time deformable objects, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.65-72, July 1999 [doi>10.1145/311535.311542]
• 18: Doug L. James , Dinesh K. Pai, DyRT: dynamic response textures for real time deformation simulation with graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 19: Doug L. James , Christopher D. Twigg, Skinning mesh animations, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 20: Doug L. James , Jernej Barbič , Dinesh K. Pai, Precomputed acoustic transfer: output-sensitive, accurate sound generation for geometrically complex vibration sources, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 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: Paul G. Kry , Doug L. James , Dinesh K. Pai, EigenSkin: real time large deformation character skinning in hardware, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545286]
• 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: J. P. Lewis , Matt Cordner , Nickson Fong, Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.165-172, July 2000 [doi>10.1145/344779.344862]
• 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: Mark Meyer , John Anderson, Key Point Subspace Acceleration and soft caching, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 28: Nelles, O. 2000. Nonlinear System Identification: From Classical Approaches to Neural Networks and Fuzzy Models. Springer Verlag, December.
• 29: James F. O'Brien , Perry R. Cook , Georg Essl, Synthesizing sounds from physically based motion, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.529-536, August 2001 [doi>10.1145/383259.383321]
• 30: A. Pentland , J. Williams, Good vibrations: modal dynamics for graphics and animation, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.215-222, July 1989
• 31: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 32: Demetri Terzopoulos , Andrew Witkin, Physically Based Models with Rigid and Deformable Components, IEEE Computer Graphics and Applications, v.8 n.6, p.41-51, November 1988 [doi>10.1109/38.20317]
• 33: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 34: Vakakis, A. 2001. Normal modes and localization in nonlinear systems. Kluwer Academic Publishers.
• 35: Andrew Witkin , William Welch, Fast animation and control of nonrigid structures, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.243-252, September 1990, Dallas, TX, USA [doi>10.1145/97879.565650]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Keywords:
dimensional model reduction, dynamic deformations, nonlinear solid mechanics, quadrature, real-time simulation, reduced-order modeling, subspace dynamics, subspace integration