“Medial IPC: accelerated incremental potential contact with medial elastics” by Lan, Yang, Kaufman, Yao, Li, et al. …

We propose a framework of efficient nonlinear deformable simulation with both fast continuous collision detection and robust collision resolution. We name this new framework Medial IPC as it integrates the merits from medial elastics, for an efficient and versatile reduced simulation, as well as incremental potential contact, for a robust collision and contact resolution. We leverage medial axis transform to construct a kinematic subspace. Instead of resorting to projective dynamics, we use classic hyperelastics to embrace real-world nonlinear materials. A novel reduced continuous collision detection algorithm is presented based on the medial mesh. Thanks to unique geometric properties of medial axis and medial primitives, we derive closed-form formulations for identifying between-primitive collision within the reduced medial space. In the meantime, the implicit barrier energy that generates necessary repulsion forces for collision resolution is also formulated with the medial coordinate. In other words, Medial IPC exploits a universal reduced coordinate for simulation, continuous self-/collision detection, and IPC-based collision resolution. Continuous collision detection also allows more aggressive time stepping. In addition, we carefully implement our system with a heterogeneous CPU-GPU deployment such that massively parallelizable computations are carried out on the GPU while few sequential computations are on the CPU. Such implementation also frees us from generating training poses for selecting Cubature points and pre-computing their weights. We have tested our method on complicated deformable models and collision-rich simulation scenarios. Due to the reduced nature of our system, the computation is faster than fullspace IPC or other fullspace methods using continuous collision detection by at least one order. The simulation remains high-quality as the medial subspace captures intriguing and local deformations with sufficient realism.

1. Samantha Ainsley, Etienne Vouga, Eitan Grinspun, and Rasmus Tamstorf. 2012. Speculative parallel asynchronous contact mechanics. ACM Trans. Graph. (TOG) 31, 6 (2012), 1–8.Google ScholarDigital Library
2. Nina Amenta and Marshall Bern. 1999. Surface reconstruction by Voronoi filtering. Discrete & Computational Geometry 22, 4 (1999), 481–504.Google ScholarCross Ref
3. Steven S An, Theodore Kim, and Doug L James. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Trans. Graph. (TOG) 27, 5 (2008), 1–10.Google ScholarDigital Library
4. IK Argyros, MA Hernández-Verón, and MJ Rubio. 2019. On the Convergence of SecantLike Methods. In Current Trends in Mathematical Analysis and Its Interdisciplinary Applications. Springer, 141–183.Google Scholar
5. David Baraff. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proceedings of the 21st annual conference on Computer graphics and interactive technique. ACM, 23–34.Google ScholarDigital Library
6. Jernej Barbič and Doug L James. 2010. Subspace self-collision culling. ACM Trans. Graph. (TOG) 29, 4 (2010), 81.Google ScholarDigital Library
7. Jernej Barbič and Jovan Popović. 2008. Real-time control of physically based simulations using gentle forces. ACM Trans. Graph. (TOG) 27, 5 (2008), 1–10.Google ScholarDigital Library
8. Jernej Barbič and Doug L James. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. Graph. (TOG) 24, 3 (2005), 982–990.Google ScholarDigital Library
9. Adam W Bargteil and Elaine Cohen. 2014. Animation of deformable bodies with quadratic bézier finite elements. ACM Trans. Graph. (TOG) 33, 3 (2014), 27.Google ScholarDigital Library
10. Gino van den Bergen. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of graphics tools 2, 4 (1997), 1–13.Google ScholarDigital Library
11. Harry Blum. 1967. A transformation for extracting new descriptors of shape. Models for Perception of Speech and Visual Forms, 1967 (1967), 362–380.Google Scholar
12. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: fusing constraint projections for fast simulation. ACM Trans. Graph. (TOG) 33, 4 (2014), 154:1–154:11.Google ScholarDigital Library
13. Christopher Brandt, Elmar Eisemann, and Klaus Hildebrandt. 2018. Hyper-reduced projective dynamics. ACM Trans. Graph. (TOG) 37, 4 (2018), 1–13.Google ScholarDigital Library
14. Tyson Brochu, Essex Edwards, and Robert Bridson. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. on Graph. (TOG) 31, 4 (2012), 1–7.Google ScholarDigital Library
15. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popović. 2002. Interactive skeleton-driven dynamic deformations. ACM Trans. Graph. (TOG) 21, 3 (2002), 586–593.Google ScholarDigital Library
16. Min Gyu Choi and Hyeong-Seok Ko. 2005. Modal warping: Real-time simulation of large rotational deformation and manipulation. IEEE Trans. on Visualization and Computer Graphics 11, 1 (2005), 91–101.Google ScholarDigital Library
17. Dirk Den Hertog. 2012. Interior point approach to linear, quadratic and convex programming: algorithms and complexity. Vol. 277. Springer Science & Business Media.Google Scholar
18. JC Ehiwario and SO Aghamie. 2014. Comparative study of bisection, Newton-Raphson and secant methods of root-finding problems. IOSR J. of Engineering 4, 4 (2014), 1–7.Google Scholar
19. Kenny Erleben. 2018. Methodology for assessing mesh-based contact point methods. ACM Trans. Graph. (TOG) 37, 3 (2018), 1–30.Google ScholarDigital Library
20. François Faure, Benjamin Gilles, Guillaume Bousquet, and Dinesh K Pai. 2011. Sparse meshless models of complex deformable solids. ACM Trans. Graph. (TOG) 30, 4 (2011), 73.Google ScholarDigital Library
21. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: A practical gauss-seidel method for stable soft body dynamics. ACM Trans. Graph. (TOG) 35, 6 (2016), 1–9.Google ScholarDigital Library
22. Moritz Geilinger, David Hahn, Jonas Zehnder, Moritz Bächer, Bernhard Thomaszewski, and Stelian Coros. 2020. ADD: analytically differentiable dynamics for multi-body systems with frictional contact. ACM Trans. Graph. (TOG) 39, 6 (2020), 1–15.Google ScholarDigital Library
23. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K Pai. 2011. Frame-based elastic models. ACM Trans. Graph. (TOG) 30, 2 (2011), 15.Google ScholarDigital Library
24. Stefan Gottschalk, Ming C Lin, and Dinesh Manocha. 1996. OBBTree: A hierarchical structure for rapid interference detection. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques. ACM, 171–180.Google ScholarDigital Library
25. Gaël Guennebaud, Benoit Jacob, et al. 2010. Eigen. URl: http://eigen.tuxfamily.org (2010).Google Scholar
26. David Harmon, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun. 2008. Robust treatment of simultaneous collisions. ACM Trans. Graph. (TOG) 27, 3 (2008), 1–4.Google ScholarDigital Library
27. Kris K Hauser, Chen Shen, and James F O’Brien. 2003. Interactive deformation using modal analysis with constraints.. In Graphics Interface, Vol. 3. 16–17.Google Scholar
28. Florian Hecht, Yeon Jin Lee, Jonathan R Shewchuk, and James F O’Brien. 2012. Updated sparse cholesky factors for corotational elastodynamics. ACM Trans. Graph. (TOG) 31, 5 (2012), 123.Google ScholarDigital Library
29. Don Herbison-Evans. 1995. Solving quartics and cubics for graphics. In Graphics Gems V. Elsevier, 3–15.Google Scholar
30. Philip Martyn Hubbard. 1995. Collision detection for interactive graphics applications. IEEE Trans. on Visualization and Computer Graphics 1, 3 (1995), 218–230.Google ScholarDigital Library
31. Geoffrey Irving, Joseph Teran, and Ronald Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation. 131–140.Google ScholarDigital Library
32. Alec Jacobson, Ilya Baran, Jovan Popovic, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. (TOG) 30, 4 (2011), 78–1.Google ScholarDigital Library
33. Doug L James, Jernej Barbič, and Christopher D Twigg. 2004. Squashing cubes: Automating deformable model construction for graphics. In ACM SIGGRAPH 2004 Sketches. 38.Google ScholarDigital Library
34. Doug L James and Dinesh K Pai. 2004. BD-tree: output-sensitive collision detection for reduced deformable models. ACM Trans. Graph. (TOG) 23, 3 (2004), 393–398.Google ScholarDigital Library
35. Theodore Kim and David Eberle. 2020. Dynamic deformables: implementation and production practicalities. In ACM SIGGRAPH 2020 Courses. 1–182.Google ScholarDigital Library
36. Theodore Kim and Doug L James. 2009. Skipping steps in deformable simulation with online model reduction. ACM Trans. Graph. (TOG) 28, 5 (2009), 123.Google ScholarDigital Library
37. Shankar Krishnan, M Gopi, M Lin, Dinesh Manocha, and A Pattekar. 1998. Rapid and accurate contact determination between spline models using ShellTrees. Computer Graphics Forum 17, 3 (1998), 315–326.Google ScholarCross Ref
38. Lei Lan, Ran Luo, Marco Fratarcangeli, Weiwei Xu, Huamin Wang, Xiaohu Guo, Junfeng Yao, and Yin Yang. 2020. Medial elastics: efficient and collision-ready deformation via medial axis transform. ACM Trans. Graph. (TOG) 39, 3 (2020), 1–17.Google ScholarDigital Library
39. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M Kaufman. 2020. Incremental potential contact: intersection-and inversion-free, large-deformation dynamics. ACM Trans. Graph. (TOG) 39, 4 (2020).Google ScholarDigital Library
40. Pan Li, Bin Wang, Feng Sun, Xiaohu Guo, Caiming Zhang, and Wenping Wang. 2015. Q-Mat: Computing medial axis transform by quadratic error minimization. ACM Trans. Graph. (TOG) 35, 1 (2015), 8.Google ScholarDigital Library
41. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast simulation of mass-spring systems. ACM Trans. Graph. (TOG) 32, 6 (2013), 214:1–214:7.Google ScholarDigital Library
42. Ran Luo, Weiwei Xu, Huamin Wang, Kun Zhou, and Yin Yang. 2018. Physics-based quadratic deformation using elastic weighting. IEEE Trans. on Visualization and Computer Graphics 24, 12 (2018), 3188–3199.Google ScholarCross Ref
43. Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Tae-Yong Kim. 2020. Primal/dual descent methods for dynamics. Computer Graphics Forum 39, 8 (2020), 89–100.Google ScholarDigital Library
44. Miles Macklin, Kenny Erleben, Matthias Müller, Nuttapong Chentanez, Stefan Jeschke, and Viktor Makoviychuk. 2019. Non-smooth newton methods for deformable multi-body dynamics. ACM Trans. Graph. (TOG) 38, 5 (2019), 1–20.Google ScholarDigital Library
45. Sebastian Martin, Peter Kaufmann, Mario Botsch, Eitan Grinspun, and Markus Gross. 2010. Unified simulation of elastic rods, shells, and solids. ACM Trans. Graph. (TOG) 29, 4 (2010), 39.Google ScholarDigital Library
46. Aleka McAdams, Andrew Selle, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Computing the singular value decomposition of 3×3 matrices with minimal branching and elementary floating point operations. Technical Report. University of Wisconsin-Madison Department of Computer Sciences.Google Scholar
47. Matthew Moore and Jane Wilhelms. 1988. Collision detection and response for computer animation. In Proceedings of the 15th annual conference on Computer graphics and interactive techniques, Vol. 22. ACM, 289–298.Google ScholarDigital Library
48. Jean Jacques Moreau. 2011. On unilateral constraints, friction and plasticity. In New variational techniques in mathematical physics. Springer, 171–322.Google Scholar
49. Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. (TOG) 24, 3 (2005), 471–478.Google ScholarDigital Library
50. CUDA Nvidia. 2008. Cublas library. NVIDIA Corporation, Santa Clara, California 15, 27 (2008), 31.Google Scholar
51. IFD Oliveira and RHC Takahashi. 2020. An enhancement of the bisection method average performance preserving minmax optimality. ACM Transactions on Mathematical Software (TOMS) 47, 1 (2020), 1–24.Google ScholarDigital Library
52. Miguel A Otaduy, Rasmus Tamstorf, Denis Steinemann, and Markus Gross. 2009. Implicit contact handling for deformable objects. Computer Graphics Forum 28, 2 (2009), 559–568.Google ScholarCross Ref
53. Alex Pentland and John Williams. 1989. Good vibrations: Modal dynamics for graphics and animation. In Proceedings of the 16th annual conference on Computer graphics and interactive techniques, Vol. 23. ACM.Google ScholarDigital Library
54. Eftychios Sifakis and Jernej Barbic. 2012. FEM simulation of 3D deformable solids: a practitioner’s guide to theory, discretization and model reduction. In ACM SIGGRAPH 2012 Courses. ACM, 20.Google ScholarDigital Library
55. Breannan Smith, Fernando De Goes, and Theodore Kim. 2018. Stable neo-hookean flesh simulation. ACM Trans. Graph. (TOG) 37, 2 (2018), 1–15.Google ScholarDigital Library
56. Feng Sun, Yi-King Choi, Yizhou Yu, and Wenping Wang. 2016. Medial meshes: a compact and accurate representation of medial axis transform. IEEE Trans. on Visualization and Computer Graphics 22, 3 (2016), 1278–1290.Google ScholarDigital Library
57. Rasmus Tamstorf, Toby Jones, and Stephen F McCormick. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Trans. Graph. (TOG) 34, 6 (2015), 245.Google ScholarDigital Library
58. Huamin Wang and Yin Yang. 2016. Descent methods for elastic body simulation on the GPU. ACM Trans. Graph. (TOG) 35, 6 (2016), 212.Google ScholarDigital Library
59. Hongyi Xu, Funshing Sin, Yufeng Zhu, and Jernej Barbič. 2015. Nonlinear material design using principal stretches. ACM Trans. Graph. (TOG) 34, 4 (2015), 1–11.Google ScholarDigital Library
60. Yin Yang, Dingzeyu Li, Weiwei Xu, Yuan Tian, and Changxi Zheng. 2015. Expediting precomputation for reduced deformable simulation. ACM Trans. Graph. (TOG) 34, 6 (2015).Google ScholarDigital Library
61. Gabriel Zachmann. 2002. Minimal hierarchical collision detection. In ACM symposium on Virtual reality software and technology. ACM, 121–128.Google ScholarDigital Library
62. Gabriel Zachmann and Elmar Langetepe. 2003. Geometric data structures for computer graphics. Eurographics Assoc.Google Scholar
63. Changxi Zheng and Doug L James. 2012. Energy-based self-collision culling for arbitrary mesh deformations. ACM Trans. Graph. (TOG) 31, 4 (2012), 98.Google ScholarDigital Library
64. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Trans. Graph. (TOG) 29, 2 (2010), 16.Google ScholarDigital Library
65. Olgierd Cecil Zienkiewicz, Robert Leroy Taylor, Olgierd Cecil Zienkiewicz, and Robert Lee Taylor. 1977. The finite element method. Vol. 36. McGraw-hill London.Google Scholar