“Medial Elastics: Efficient and Collision-ready Deformation via Medial Axis Transform” by Lan, Luo, Fratarcangeli, Xu, Wang, et al. …
Conference:
Type(s):
Title:
- Medial Elastics: Efficient and Collision-ready Deformation via Medial Axis Transform
Session/Category Title: Contact and Collisions
Presenter(s)/Author(s):
Abstract:
We propose a framework for the interactive simulation of nonlinear deformable objects. The primary feature of our system is the seamless integration of deformable simulation and collision culling, which are often independently handled in existing animation systems. The bridge connecting them is the medial axis transform (MAT), a high-fidelity volumetric approximation of complex 3D shapes. From the physics simulation perspective, MAT leads to an expressive and compact reduced nonlinear model. We employ a semireduced projective dynamics formulation, which well captures high-frequency local deformations of high-resolution models while retaining a low computation cost. Our key observation is that the most compelling (nonlinear) deformable effects are enabled by the local constraints projection, which should not be aggressively reduced, and only apply model reduction at the global stage. From the collision detection (CD)/collision culling (CC) perspective, MAT is geometrically versatile using linear-interpolated spheres (i.e., the so-called medial primitives (MPs)) to approximate the boundary of the input model. The intersection test between two MPs is formulated as a quadratically constrained quadratic program problem. We give an algorithm to solve this problem exactly, which returns the deepest penetration between a pair of intersecting MPs. When coupled with spatial hashing, collision (including self-collision) can be efficiently identified on the GPU within a few milliseconds even for massive simulations. We have tested our system on a variety of geometrically complex and high-resolution deformable objects, and our system produces convincing animations with all of the collisions/self-collisions well handled at an interactive rate.
References:
1. Nina Amenta and Marshall Bern. 1999. Surface reconstruction by Voronoi filtering. Discrete 8 Computational Geometry 22, 4 (1999), 481–504.
2. Steven S. An, Theodore Kim, and Doug L. James. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Transactions on Graphics 27 (2008), Article 165.
3. Baptiste Angles, Daniel Rebain, Miles Macklin, Brian Wyvill, Loic Barthe, J. P. Lewis, Javier von der Pahlen, et al. 2019. VIPER: Volume invariant position-based elastic rods. Proceedings of the ACM in Computer Graphics and Interactive Techniques 2, 2 (2019), Article 19, 26 pages. DOI:https://doi.org/10.1145/3340260
4. Andreas Antoniou and Wu-Sheng Lu. 2007. Practical Optimization: Algorithms and Engineering Applications. Springer.
5. Dominique Attali and Annick Montanvert. 1997. Computing and simplifying 2D and 3D continuous skeletons. Computer Vision and Image Understanding 67, 3 (1997), 261–273.
6. David Baraff. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Computer Graphics and Interactive Techniques. ACM, New York, NY, 23–34.
7. Jernej Barbič and Doug James. 2007. Time-critical distributed contact for 6-DOF haptic rendering of adaptively sampled reduced deformable models. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 171–180.
8. Jernej Barbič and Doug L. James. 2010. Subspace self-collision culling. ACM Transactions on Graphics 29, 4 (2010), 81.
9. Jernej Barbič and Yili Zhao. 2011. Real-time large-deformation substructuring. ACM Transactions on Graphics 30 (2011), Article 91.
10. Jernej Barbič and Doug L. James. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Transactions on Graphics 24 (2005), 982–990.
11. Adam W. Bargteil and Elaine Cohen. 2014. Animation of deformable bodies with quadratic Bézier finite elements. ACM Transactions on Graphics 33, 3 (2014), 27.
12. Gino van den Bergen. 1997. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2, 4 (1997), 1–13.
13. Harry Blum. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Forms. MIT Press, Cambridge, MA, 362–380.
14. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM Transactions on Graphics 33, 4 (2014), Article 154, 11 pages.
15. Christopher Brandt, Elmar Eisemann, and Klaus Hildebrandt. 2018. Hyper-reduced projective dynamics. ACM Transactions on Graphics 37, 4 (2018), Article 80, 13 pages.
16. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics 21, 3 (July 2002), 594–603.
17. Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popović. 2002. Interactive skeleton-driven dynamic deformations. ACM Transactions on Graphics 21 (2002), 586–593.
18. Xiao-Diao Chen, Jun-Hai Yong, Guo-Qin Zheng, Jean-Claude Paul, and Jia-Guang Sun. 2006. Computing minimum distance between two implicit algebraic surfaces. Computer-Aided Design 38, 10 (2006), 1053–1061.
19. Min Gyu Choi and Hyeong-Seok Ko. 2005. Modal warping: Real-time simulation of large rotational deformation and manipulation. IEEE Transactions on Visualization and Computer Graphics 11, 1 (2005), 91–101.
20. Andreas Fabri and Monique Teillaud. 2011. CGAL—The computational geometry algorithms library. In 10e colloque national en calcul des structures. 6.
21. Noura Faraj, Jean-Marc Thiery, and Tamy Boubekeur. 2013. Progressive medial axis filtration. In SIGGRAPH Asia 2013 Technical Briefs. ACM, New York, NY, 3.
22. François Faure, Benjamin Gilles, Guillaume Bousquet, and Dinesh K. Pai. 2011. Sparse meshless models of complex deformable solids. ACM Transactions on Graphics 30 (2011), Article 73.
23. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: A practical Gauss-Seidel method for stable soft body dynamics. ACM Transactions on Graphics 35, 6 (2016), Article 214, 9 pages.
24. Marco Fratarcangeli, Huamin Wang, and Yin Yang. 2018. Parallel iterative solvers for real-time elastic deformations. In SIGGRAPH Asia 2018 Courses. ACM, New York, NY, 14.
25. Ming Gao, Andre Pradhana Tampubolon, Chenfanfu Jiang, and Eftychios Sifakis. 2017. An adaptive generalized interpolation material point method for simulating elastoplastic materials. ACM Transactions on Graphics 36, 6 (2017), 223.
26. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K. Pai. 2011. Frame-based elastic models. ACM Transactions on Graphics 30, 2 (2011), 15.
27. Stefan Gottschalk, Ming C. Lin, and Dinesh Manocha. 1996. OBBTree: A hierarchical structure for rapid interference detection. In Computer Graphics and Interactive Techniques. ACM, New York, NY, 171–180.
28. Kris K. Hauser, Chen Shen, and James F. O’Brien. 2003. Interactive deformation using modal analysis with constraints. In Proceedings of Graphics Interface 2003, Vol. 3. 16–17.
29. Philip Martyn Hubbard. 1995. Collision detection for interactive graphics applications. IEEE Transactions on Visualization and Computer Graphics 1, 3 (1995), 218–230.
30. Alec Jacobson, Ilya Baran, Jovan Popovic, and Olga Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics 30, 4 (2011), Article 78.
31. Doug L. James and Dinesh K. Pai. 2004. BD-tree: Output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics 23, 3 (2004), 393–398.
32. Ladislav Kavan and Jiri Zara. 2005. Fast collision detection for skeletally deformable models. Computer Graphics Forum 24, 3 (2005), 363–372.
33. Theodore Kim and Doug L. James. 2009. Skipping steps in deformable simulation with online model reduction. ACM Transactions on Graphics 28 (2009), Article 123.
34. Martin Komaritzan and Mario Botsch. 2018. Projective skinning. Proceedings of the ACM on Computer Graphics and Interactive Techniques 1, 1 (2018), 12.
35. 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 (1998), 315–326.
36. Paul G. Kry, Doug L. James, and Dinesh K. Pai. 2002. EigenSkin: Real time large deformation character skinning in hardware. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’02). 153–159.
37. 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 Transactions on Graphics 35, 1 (2015), Article 8.
38. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast simulation of mass-spring systems. ACM Transactions on Graphics 32, 6 (2013), Article 214, 7 pages.
39. Ran Luo, Weiwei Xu, Huamin Wang, Kun Zhou, and Yin Yang. 2018. Physics-based quadratic deformation using elastic weighting. IEEE Transactions on Visualization and Computer Graphics 24, 12 (2018), 3188–3199.
40. Sebastian Martin, Peter Kaufmann, Mario Botsch, Eitan Grinspun, and Markus Gross. 2010. Unified simulation of elastic rods, shells, and solids. ACM Transactions on Graphics 29 (2010), Article 39.
41. Matthew Moore and Jane Wilhelms. 1988. Collision detection and response for computer animation. ACM SIGGRAPH Computer Graphics 22 (1988), 289–298.
42. Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless deformations based on shape matching. ACM Transactions on Graphics 24 (2005), 471–478.
43. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM ⊇ projective dynamics: Fast simulation of general constitutive models. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’16). 21–28.
44. Maxim Naumov. 2011. Parallel Solution of Sparse Triangular Linear Systems in the Preconditioned Iterative Methods on the GPU. Technical Report NVR-2001. NVIDIA, Westford, MA.
45. Matthieu Nesme, Paul G. Kry, Lenka Jeřábková, and François Faure. 2009. Preserving topology and elasticity for embedded deformable models. ACM Transactions on Graphics 28 (2009), Article 52.
46. Simon Pabst, Artur Koch, and Wolfgang Straßer. 2010. Fast and scalable CPU/GPU collision detection for rigid and deformable surfaces. Computer Graphics Forum 29 (2010), 1605–1612.
47. Alex Pentland and John Williams. 1989. Good vibrations: Modal dynamics for graphics and animation. ACM SIGGRAPH Computer Graphics 23 (1989), 207–214.
48. Ken Shoemake. 1985. Animating rotation with quaternion curves. ACM SIGGRAPH Computer Graphics 19 (1985), 245–254.
49. 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, New York, NY, 20.
50. Svetlana Stolpner, Paul Kry, and Kaleem Siddiqi. 2012. Medial spheres for shape approximation. IEEE Transactions on Pattern Analysis and Machine Intelligence 34, 6 (2012), 1234–1240.
51. Feng Sun, Yi-King Choi, Yizhou Yu, and Wenping Wang. 2016. Medial meshes: A compact and accurate representation of medial axis transform. IEEE Transactions on Visualization and Computer Graphics 22, 3 (March 2016), 1278–1290.
52. Min Tang, Zhongyuan Liu, Ruofeng Tong, and Dinesh Manocha. 2018. PSCC: Parallel self-collision culling with spatial hashing on GPUs. Proceedings of the ACM on Computer Graphics and Interactive Techniques 1, 1 (2018), 1–18.
53. Yun Teng, Miguel A. Otaduy, and Theodore Kim. 2014. Simulating articulated subspace self-contact. ACM Transactions on Graphics 33, 4 (2014), Article 106.
54. Matthias Teschner, Stefan Kimmerle, Bruno Heidelberger, Gabriel Zachmann, Laks Raghupathi, Arnulph Fuhrmann, M.-P. Cani, et al. 2005. Collision detection for deformable objects. Computer Graphics Forum 24 (2005), 61–81.
55. Jean-Marc Thiery, Émilie Guy, and Tamy Boubekeur. 2013. Sphere-meshes: Shape approximation using spherical quadric error metrics. ACM Transactions on Graphics 32, 6 (2013), Article 178.
56. Jean-Marc Thiery, Émilie Guy, Tamy Boubekeur, and Elmar Eisemann. 2016. Animated mesh approximation with sphere-meshes. ACM Transactions on Graphics 35, 3 (May 2016), Article 30, 13 pages. DOI:https://doi.org/10.1145/2898350
57. Anastasia Tkach, Mark Pauly, and Andrea Tagliasacchi. 2016. Sphere-meshes for real-time hand modeling and tracking. ACM Transactions on Graphics 35, 6 (Nov. 2016), Article 222, 11 pages.
58. Huamin Wang. 2015. A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Transactions on Graphics 34, 6 (2015), Article 246.
59. Huamin Wang and Yin Yang. 2016. Descent methods for elastic body simulation on the GPU. ACM Transactions on Graphics 35, 6 (2016), Article 212.
60. Xinlei Wang, Min Tang, Dinesh Manocha, and Ruofeng Tong. 2018. Efficient BVH-based collision detection scheme with ordering and restructuring. Computer Graphics Forum 37 (2018), 227–237.
61. Baorong Yang, Junfeng Yao, and Xiaohu Guo. 2018. DMAT: Deformable medial axis transform for animated mesh approximation. Computer Graphics Forum 37, 7 (2018), 1–11.
62. Yin Yang, Dingzeyu Li, Weiwei Xu, Yuan Tian, and Changxi Zheng. 2015. Expediting precomputation for reduced deformable simulation. ACM Transactions on Graphics 34, 6 (2015), Article 243.
63. Yin Yang, Weiwei Xu, Xiaohu Guo, Kun Zhou, and Baining Guo. 2013. Boundary-aware multidomain subspace deformation. IEEE Transactions on Visualization and Computer Graphics 19, 10 (2013), 1633–1645.
64. Gabriel Zachmann. 2002. Minimal hierarchical collision detection. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology. ACM, New York, NY, 121–128.
65. Gabriel Zachmann and Elmar Langetepe. 2003. Geometric Data Structures for Computer Graphics. Eurographics Association.
66. Changxi Zheng and Doug L. James. 2012. Energy-based self-collision culling for arbitrary mesh deformations. ACM Transactions on Graphics 31, 4 (2012), Article 98.
67. Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multigrid method for the simulation of high-resolution elastic solids. ACM Transactions on Graphics 29, 2 (2010), Article 16.
