“Simulating articulated subspace self-contact” by Teng, Kim and Otaduy
Conference:
Type:
Session Title:
- Subspace & Spacetime
Title:
- Simulating articulated subspace self-contact
Moderator(s):
Presenter(s)/Author(s):
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).
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. 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
