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

research-article

Simulating articulated subspace self-contact

Authors:

Miguel A. Otaduy,

Theodore KimAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 33, Issue 4

Article No.: 106, Pages 1 - 9

https://doi.org/10.1145/2601097.2601181

Published: 27 July 2014 Publication History

Abstract

We present an efficient new subspace method for simulating the self-contact of articulated deformable bodies, such as characters. Self-contact is highly structured in this setting, as the limited space of possible articulations produces a predictable set of coherent collisions. Subspace methods can leverage this coherence, and have been used in the past to accelerate the collision detection stage of contact simulation. We show that these methods can be used to accelerate the entire contact computation, and allow self-contact to be resolved without looking at all of the contact points. Our analysis of the problem yields a broader insight into the types of non-linearities that subspace methods can efficiently approximate, and leads us to design a pose-space cubature scheme. Our algorithm accelerates self-contact by up to an order of magnitude over other subspace simulations, and accelerates the overall simulation by two orders of magnitude over full-rank simulations. We demonstrate the simulation of high resolution (100K -- 400K elements) meshes in self-contact at interactive rates (5.8 -- 50 FPS).

Supplementary Material

ZIP File (a106-teng.zip)

Supplemental material.

Download
29.94 MB

MP4 File (a106-sidebyside.mp4)

Download
12.25 MB

References

[1]

An, S. S., Kim, T., and James, D. L. 2008. Optimizing Cubature for Efficient Integration of Subspace Deformations. ACM Trans. on Graphics 27, 5 (Dec), 165.

Digital Library

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

Digital Library

[3]

Barbič, J., and James, D. L. 2008. Six-DoF haptic rendering of contact between geometrically complex reduced deformable models. IEEE Transactions on Haptics 1, 1 (jan.-june), 39--52.

Digital Library

[4]

Barbič, J., and James, D. L. 2010. Subspace self-collision culling. ACM Trans. Graph. 29, 4 (July), 81:1--81:9.

Digital Library

[5]

Barbič, J., and Zhao, Y. 2011. Real-time large-deformation substructuring. ACM Trans. on Graphics 30.

Digital Library

[6]

Chen, D., and Plemmons, R. 2007. Nonnegativity constraints in numerical analysis. In Symposium on the Birth of Numerical Analysis.

[7]

Clutterbuck, S., and Jacobs, J., 2010. A physically based approach to virtual character deformations. SIGGRAPH 2010 Talks.

[8]

Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In Proceedings of the Symposium on Interactive 3D Graphics and Games, 61--69.

Digital Library

[9]

de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. 2008. Computational Geometry: Algorithms and Applications, 3rd ed. Springer-Verlag.

Digital Library

[10]

Duff, I. S. 2004. MA57---a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30, 2 (June), 118--144.

Digital Library

[11]

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.

[12]

Harmon, D., and Zorin, D. 2013. Subspace integration with local deformations. ACM Transactions on Graphics 32 (July).

Digital Library

[13]

Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Trans. Graph..

Digital Library

[14]

Hirota, G., Fisher, S., State, A., Lee, C., and Fuchs, H. 2001. An implicit finite element method for elastic solids in contact. In Proceedings of the Fourteenth Conference on Computer Animation, 136--254.

[15]

Hogg, J., and Scott, J. 2010. An indenite sparse direct solver for multicore machines. Tech. Rep. TR-RAL-2010-011, Rutherford Appleton Laboratory, Chilton, Oxfordshire, UK.

[16]

Idelsohn, S., and Cardona, A. 1985. A reduction method for nonlinear structural dynamic analysis. Computer Methods in Applied Mechanics and Engineering 49, 253--279.

[17]

James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics 23, 3 (Aug.), 393--398.

Digital Library

[18]

Jones, M. T., Plassmann, P. E., and Mcs-p, P. 1995. An improved incomplete cholesky factorization. ACM Trans. Math. Software 21, 5--17.

Digital Library

[19]

Kavan, L., and Sorkine, O. 2012. Elasticity-inspired deformers for character articulation. ACM Trans. Graph. 31, 6 (Nov.), 196:1--196:8.

Digital Library

[20]

Kavan, L., Collins, S., Žára, J., and O'Sullivan, C. 2008. Geometric skinning with approximate dual quaternion blending. ACM Transactions on Graphics (TOG) 27, 4, 105.

Digital Library

[21]

Kim, T., and Delaney, J. 2013. Subspace fluid re-simulation. ACM Trans. Graph. 32 (July).

Digital Library

[22]

Kim, T., and James, D. L. 2011. Physics-based character skinning using multi-domain subspace deformations. In ACM SIGGRAPH/Eurographics Sym. on Computer Animation, 63--72.

Digital Library

[23]

Kim, J., and Pollard, N. S. 2011. Fast simulation of skeleton-driven deformable body characters. ACM Trans. Graph. 30, 5 (Oct.), 121:1--121:19.

Digital Library

[24]

Kry, P. G., James, D. L., and Pai, D. K. 2002. EigenSkin: Real Time Large Deformation Character Skinning in Hardware. In ACM SIGGRAPH Sym. on Computer Animation, 153--160.

Digital Library

[25]

Kurihara, T., and Miyata, N. 2004. Modeling deformable human hands from medical images. In ACM SIGGRAPH/Eurographics Sym. on Computer Animation, 357--366.

Digital Library

[26]

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 SIGGRAPH, 165--172.

Digital Library

[27]

Liu, L., Yin, K., Wang, B., and Guo, B. 2013. Simulation and control of skeleton-driven soft body characters. ACM Trans. Graph. 32, 6 (Nov.), 215:1--215:8.

Digital Library

[28]

McAdams, A., Zhu, Y., Selle, A., Empey, M., Tamstorf, R., Teran, J., and Sifakis, E. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Trans. Graph. 30, 4 (July), 37:1--37:12.

Digital Library

[29]

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.

[30]

O'Brien, J. F., Shen, C., and Gatchalian, C. M. 2002. Synthesizing sounds from rigid-body simulations. In ACM SIGGRAPH Sym. on Computer Animation, 175--181.

Digital Library

[31]

Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. In Computer Graphics (Proceedings of SIGGRAPH 89), 215--222.

Digital Library

[32]

Schvartzman, S. C., Gascón, J., and Otaduy, M. A. 2009. Bounded normal trees for reduced deformations of triangulated surfaces. In ACM SIGGRAPH/Eurographics Sym. on Computer Animation, 75--82.

Digital Library

[33]

Shabana, A. A. 1990. Theory of Vibration, Volume II: Discrete and Continuous Systems. Springer--Verlag, NY.

[34]

Sifakis, E., and Barbič, J. 2012. Fem simulation of 3d deformable solids: a practitioner's guide to theory, discretization and model reduction. In ACM SIGGRAPH Courses, 20:1--20:50.

Digital Library

[35]

Stanton, M., Sheng, Y., Wicke, M., Perazzi, F., Yuen, A., Narasimhan, S., and Treuille, A. 2013. Non-polynomial galerkin projection on deforming meshes. ACM Trans. Graph. 32 (July).

Digital Library

[36]

Tang, M., Manocha, D., Otaduy, M. A., and Tong, R. 2012. Continuous penalty forces. ACM Trans. Graph. 31, 4.

Digital Library

[37]

Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. In ACM SIGGRAPH Symp. on Computer Animation, 181--190.

Digital Library

[38]

Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Trans. Graph. 25, 3 (July), 826--834.

Digital Library

[39]

Vaillant, R., Barthe, L., Guennebaud, G., Cani, M.-P., Rohmer, D., Wyvill, B., Gourmel, O., and Paulin, M. 2013. Implicit skinning: Real-time skin deformation with contact modeling. ACM Trans. Graph. 32, 4 (July), 125:1--125:12.

Digital Library

[40]

von Tycowicz, C., Schulz, C., Seidel, H.-P., and Hildebrandt, K. 2013. An efficient construction of reduced deformable objects. ACM Trans. Graph. 32, 6 (Nov.), 213:1--213:10.

Digital Library

[41]

Wächter, A., and Vigerske, S., 2005. Interior point optimizer. https://projects.coin-or.org/Ipopt.

[42]

Wächter, A. 2002. An Interior Point Algorithm for Large-Scale Nonlinear Optimization with Applications in Process Engineering. PhD thesis, Carnegie Mellon University, Pittsburgh, PA.

[43]

Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Trans. Graph. 28, 3 (Aug.), 39.

Digital Library

[44]

Yang, Y., Xu, W., Guo, X., Zhou, K., and Guo, B. 2013. Boundary-aware multi-domain subspace deformation. IEEE Transactions on Visualization and Computer Graphics.

[45]

Zhu, Y., Sifakis, E., Teran, J., and Brandt, A. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. 29, 2 (Mar.), 16:1--16:18.

Digital Library

Cited By

Razon AChen YHan YGagniere STupek MTeran J(2023)A Linear and Angular Momentum Conserving Hybrid Particle/Grid Iteration for Volumetric Elastic ContactProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36069246:3(1-25)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.1145/3606924
Benchekroun OZhang JChaudhuri SGrinspun EZhou YJacobson A(2023)Fast Complementary Dynamics via Skinning EigenmodesACM Transactions on Graphics10.1145/359240442:4(1-21)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592404
Chen HDiaz EYuksel C(2023)Shortest Path to Boundary for Self-Intersecting MeshesACM Transactions on Graphics10.1145/359213642:4(1-15)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592136
Show More Cited By

Index Terms

Simulating articulated subspace self-contact
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

Subspace condensation: full space adaptivity for subspace deformations

Subspace deformable body simulations can be very fast, but can behave unrealistically when behaviors outside the prescribed subspace such as novel external collisions, are encountered. We address this limitation by presenting a fast, flexible new method ...
Subspace fluid re-simulation

We present a new subspace integration method that is capable of efficiently adding and subtracting dynamics from an existing high-resolution fluid simulation. We show how to analyze the results of an existing high-resolution simulation, discover an ...
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 ...

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 33, Issue 4

July 2014

1366 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2601097

Issue’s Table of Contents

Copyright © 2014 ACM.

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 the author(s) 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: 27 July 2014

Published in TOG Volume 33, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
452
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Razon AChen YHan YGagniere STupek MTeran J(2023)A Linear and Angular Momentum Conserving Hybrid Particle/Grid Iteration for Volumetric Elastic ContactProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36069246:3(1-25)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.1145/3606924
Benchekroun OZhang JChaudhuri SGrinspun EZhou YJacobson A(2023)Fast Complementary Dynamics via Skinning EigenmodesACM Transactions on Graphics10.1145/359240442:4(1-21)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592404
Chen HDiaz EYuksel C(2023)Shortest Path to Boundary for Self-Intersecting MeshesACM Transactions on Graphics10.1145/359213642:4(1-15)Online publication date: 26-Jul-2023
https://dl.acm.org/doi/10.1145/3592136
Bertiche HMadadi MEscalera S(2022)Neural Cloth SimulationACM Transactions on Graphics10.1145/3550454.355549141:6(1-14)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555491
Hachette OCanezin FVaillant RMellado NBarthe L(2022)Automatic shape adjustment at joints for the implicit skinningComputers and Graphics10.1016/j.cag.2021.10.018102:C(300-308)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1016/j.cag.2021.10.018
Tan QZhou YWang TCeylan DSun XManocha D(2022)A Repulsive Force Unit for Garment Collision Handling in Neural NetworksComputer Vision – ECCV 202210.1007/978-3-031-20062-5_26(451-467)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-20062-5_26
Brunel CBénard PGuennebaud G(2021)A time-independent deformer for elastic contactsACM Transactions on Graphics10.1145/3450626.345987940:4(1-14)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459879
Romero CCasas DPérez JOtaduy M(2021)Learning contact corrections for handle-based subspace dynamicsACM Transactions on Graphics10.1145/3450626.345987540:4(1-12)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459875
Wang QTao YBrandt ECutting CSifakis E(2021)Optimized Processing of Localized Collisions in Projective DynamicsComputer Graphics Forum10.1111/cgf.1438540:6(382-393)Online publication date: 21-Jul-2021
https://doi.org/10.1111/cgf.14385
Tapia JRomero CPérez JOtaduy M(2021)Parametric Skeletons with Reduced Soft‐Tissue DeformationsComputer Graphics Forum10.1111/cgf.1419940:6(34-46)Online publication date: 2-Feb-2021
https://doi.org/10.1111/cgf.14199
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