Optimizing Cubature for Efficient Integration of Subspace Deformations

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 subspace forces at O(r^2) 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 multimodal (graphics, haptics, sound) applications. We show dramatically better efficiency than traditional Monte Carlo integration.

Source Code:

Download cubacode.tar. This is an implementation of the cubature optimization algorithm in C++ that can be extended to any specific force integration problem. Released under the GPL.

Publications:

Steven S. An, Theodore Kim and Doug L. James, Optimizing Cubature for Efficient Integration of Subspace Deformations, ACM Transactions on Graphics (SIGGRAPH ASIA Conference Proceedings), 27(5), December 2008, pp. 164:1-164:11.

PDF | Half-res Video (90MB) | Full-res Video (260MB) | KeyNote Slides

Examples Gallery:

Acknowledgments:

The authors wish to acknowledge funding and support from the National Science Foundation (CAREER- 0430528, EMT-CompBio-0621999), National Institutes of Health (NIBIB/NIH R01EB006615), the Alfred P. Sloan Foundation, Intel, Pixar, The Boeing Company, Autodesk, and NVIDIA. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.