“Simulating articulated subspace self-contact” by Teng, Kim and Otaduy

  • ©Yun Teng, Theodore Kim, and Miguel A. Otaduy



Session Title:

    Subspace & Spacetime


    Simulating articulated subspace self-contact




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


    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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
    4. Barbič, J., and James, D. L. 2010. Subspace self-collision culling. ACM Trans. Graph. 29, 4 (July), 81:1–81:9. Google ScholarDigital Library
    5. Barbič, J., and Zhao, Y. 2011. Real-time large-deformation substructuring. ACM Trans. on Graphics 30. Google ScholarDigital Library
    6. Chen, D., and Plemmons, R. 2007. Nonnegativity constraints in numerical analysis. In Symposium on the Birth of Numerical Analysis.Google Scholar
    7. Clutterbuck, S., and Jacobs, J., 2010. A physically based approach to virtual character deformations. SIGGRAPH 2010 Talks.Google Scholar
    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. Google ScholarDigital Library
    9. de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. 2008. Computational Geometry: Algorithms and Applications, 3rd ed. Springer-Verlag. Google ScholarDigital 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. Google ScholarDigital 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.Google Scholar
    12. Harmon, D., and Zorin, D. 2013. Subspace integration with local deformations. ACM Transactions on Graphics 32 (July). Google ScholarDigital Library
    13. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Trans. Graph.. Google ScholarDigital 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.Google Scholar
    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.Google Scholar
    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.Google ScholarCross Ref
    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. Google ScholarDigital 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. Google ScholarDigital Library
    19. Kavan, L., and Sorkine, O. 2012. Elasticity-inspired deformers for character articulation. ACM Trans. Graph. 31, 6 (Nov.), 196:1–196:8. Google ScholarDigital 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. Google ScholarDigital Library
    21. Kim, T., and Delaney, J. 2013. Subspace fluid re-simulation. ACM Trans. Graph. 32 (July). Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital 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.Google Scholar
    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. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
    33. Shabana, A. A. 1990. Theory of Vibration, Volume II: Discrete and Continuous Systems. Springer–Verlag, NY.Google Scholar
    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. Google ScholarDigital 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). Google ScholarDigital Library
    36. Tang, M., Manocha, D., Otaduy, M. A., and Tong, R. 2012. Continuous penalty forces. ACM Trans. Graph. 31, 4. Google ScholarDigital 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. Google ScholarDigital Library
    38. Treuille, A., Lewis, A., and Popović, Z. 2006. Model reduction for real-time fluids. ACM Trans. Graph. 25, 3 (July), 826–834. Google ScholarDigital 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. Google ScholarDigital 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. Google ScholarDigital Library
    41. Wächter, A., and Vigerske, S., 2005. Interior point optimizer. https://projects.coin-or.org/Ipopt.Google Scholar
    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.Google Scholar
    43. Wicke, M., Stanton, M., and Treuille, A. 2009. Modular bases for fluid dynamics. ACM Trans. Graph. 28, 3 (Aug.), 39. Google ScholarDigital 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.Google ScholarCross Ref
    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. Google ScholarDigital Library

ACM Digital Library Publication: