“Guaranteed globally injective 3D deformation processing” by Fang, Li, Jiang and Kaufman

We extend recent advances in the numerical time-integration of contacting elastodynamics [Li et al. 2020] to build a new framework, called Injective Deformation Processing (IDP), for the robust solution of a wide range of mesh deformation problems requiring injectivity. IDP solves challenging 3D (and 2D) geometry processing and animation tasks on meshes, via artificial time integration, with guarantees of both non-inversion and non-overlap. To our knowledge IDP is the first framework for 3D deformation processing that can efficiently guarantee globally injective deformation without geometric locking. We demonstrate its application on a diverse set of problems and show its significant improvement over state-of-the-art for globally injective 3D deformation.

1. Marc Alexa, Daniel Cohen-Or, and David Levin. 2000. As-rigid-as-possible shape interpolation. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques. 157–164.Google ScholarDigital Library
2. U.M. Ascher and L.R. Petzold. 1998. Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations. SIAM.Google Scholar
3. David Baraff, Andrew Witkin, and Michael Kass. 2003. Untangling cloth. ACM Trans. Graph. (TOG) 22, 3 (2003), 862–870.Google ScholarDigital Library
4. Ilya Baran and Jaakko Lehtinen. 2009. Notes on Inflating Curves. (2009).Google Scholar
5. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-up: Shaping discrete geometry with projections. In Computer Graphics Forum, Vol. 31. Wiley Online Library, 1657–1667.Google Scholar
6. 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), 1–11. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 594–603.Google ScholarDigital Library
7. Tyson Brochu and Robert Bridson. 2009. Robust topological operations for dynamic explicit surfaces. SIAM Journal on Scientific Computing 31, 4 (2009), 2472–2493.Google ScholarDigital Library
8. Thomas Buffet, Damien Rohmer, Loïc Barthe, Laurence Boissieux, and Marie-Paule Cani. 2019. Implicit untangling: a robust solution for modeling layered clothing. ACM Trans. Graph. (TOG) 38, 4 (2019), 1–12.Google ScholarDigital Library
9. Yanqing Chen, Timothy A Davis, William W Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse Cholesky factorization and update/downdate. ACM Trans. on Math. Software (TOMS) 35, 3 (2008).Google ScholarDigital Library
10. Xingyi Du, Noam Aigerman, Qingnan Zhou, Shahar Z. Kovalsky, Yajie Yan, Danny M. Kaufman, and Tao Ju. 2020. Lifting Simplices to Find Injectivity. ACM Trans. Graph. (2020).Google Scholar
11. Fionn Dunne and Nik Petrinic. 2005. Introduction to computational plasticity. Oxford University Press on Demand.Google Scholar
12. Y. Fang, M. Li, M. Gao, and C. Jiang. 2019. Silly rubber: an implicit material point method for simulating non-equilibrated viscoelastic and elastoplastic solids. ACM Trans. Graph. (TOG) 38, 4 (2019), 1–13.Google ScholarDigital Library
13. M. Gao, A. P. Tampubolon, C. Jiang, and E. Sifakis. 2017. An adaptive generalized interpolation material point method for simulating elastoplastic materials. ACM Trans. Graph. (TOG) 36, 6 (2017), 223.Google ScholarDigital Library
14. Eitan Grinspun, Anil N Hirani, Mathieu Desbrun, and Peter Schröder. 2003. Discrete shells. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation. Citeseer, 62–67.Google ScholarDigital Library
15. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3.Google Scholar
16. David Harmon, Daniele Panozzo, Olga Sorkine, and Denis Zorin. 2011. Interference-aware geometric modeling. ACM Trans. Graph. (TOG) 30, 6 (2011), 1–10.Google ScholarDigital Library
17. David Harmon, Etienne Vouga, Rasmus Tamstorf, and Eitan Grinspun. 2008. Robust treatment of simultaneous collisions. In ACM SIGGRAPH 2008 papers. 1–4.Google ScholarDigital Library
18. Takeo Igarashi, Tomer Moscovich, and John F Hughes. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. (TOG) 24, 3 (2005), 1134–1141.Google ScholarDigital Library
19. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial complex augmentation framework for bijective maps. ACM Trans. Graph. 36, 6 (2017).Google ScholarDigital Library
20. Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2015. Large-scale bounded distortion mappings. ACM Trans. Graph. (proceedings of ACM SIGGRAPH Asia) 34, 6 (2015).Google Scholar
21. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. (SIGGRAPH 2016) (2016).Google Scholar
22. 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. 39, 4 (2020).Google ScholarDigital Library
23. Minchen Li, Danny M Kaufman, and Chenfanfu Jiang. 2021. Codimensional Incremental Potential Contact. ACM Trans. Graph. (TOG) 40, 4 (2021).Google ScholarDigital Library
24. Minchen Li, Danny M Kaufman, Vladimir G Kim, Justin Solomon, and Alla Sheffer. 2018a. Optcuts: joint optimization of surface cuts and parameterization. ACM Trans. Graph. (TOG) 37, 6 (2018), 1–13.Google ScholarDigital Library
25. Minchen Li, Alla Sheffer, Eitan Grinspun, and Nicholas Vining. 2018b. FoldSketch: Enriching Garments with Physically Reproducible Folds. ACM Trans. Graph. (TOG). 37, 4 (2018). Google ScholarDigital Library
26. Marek Krzysztof Misztal and Jakob Andreas Bærentzen. 2012. Topology-Adaptive Interface Tracking Using the Deformable Simplicial Complex. ACM Trans. Graph. (2012).Google Scholar
27. Patrick Mullen, Alexander McKenzie, Yiying Tong, and Mathieu Desbrun. 2007. A variational approach to Eulerian geometry processing. ACM Trans. Graph. (TOG) 26, 3 (2007), 66–es.Google ScholarDigital Library
28. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air meshes for robust collision handling. ACM Trans. Graph. (TOG) 34, 4 (2015), 1–9.Google ScholarDigital Library
29. Raymond W Ogden. 1997. Non-linear elastic deformations. Courier Corporation.Google Scholar
30. Stéphane Pagano and Pierre Alart. 2008. Self-contact and fictitious domain using a difference convex approach. Int. J. for Numer. Meth. in Eng. 75 (07 2008).Google ScholarCross Ref
31. Leonardo Sacht, Etienne Vouga, and Alec Jacobson. 2015. Nested cages. ACM Trans. Graph. (TOG) 34, 6 (2015), 1–14.Google ScholarDigital Library
32. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally injective mappings. In Computer Graphics Forum, Vol. 32. Wiley Online Library, 125–135.Google Scholar
33. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Transactions on Mathematical Software (TOMS) 41, 2 (2015), 1–36.Google ScholarDigital Library
34. Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Trans. Graph. (TOG) 34, 4 (2015), 1–9.Google ScholarDigital Library
35. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, Vol. 4. 109–116.Google ScholarDigital Library
36. Jian-Ping Su, Chunyang Ye, Ligang Liu, and Xiao-Ming Fu. 2020. Efficient bijective parameterizations. ACM Trans. Graph. (TOG) 39, 4 (2020), 111–1.Google ScholarDigital Library
37. Pascal Volino and Nadia Magnenat-Thalmann. 2006. Resolving surface collisions through intersection contour minimization. ACM Trans. Graph. (TOG) 25, 3 (2006).Google ScholarDigital Library
38. Martin Wicke, Hermes Lanker, and Markus Gross. 2006. Untangling cloth with boundaries. In Proc. of Vision, Modeling, and Visualization. 349–356. Audrey Wong, David Eberle, and Theodore Kim. 2018. Clean cloth inputs: Removing character self-intersections with volume simulation. In ACM SIGGRAPH 2018 Talks.Google Scholar
39. Juntao Ye, Guanghui Ma, Liguo Jiang, Lan Chen, Jituo Li, Gang Xiong, Xiaopeng Zhang, and Min Tang. 2017. A unified cloth untangling framework through discrete collision detection. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 217–228.Google Scholar
40. Juntao Ye, Timo R Nyberg, and Gang Xiong. 2015. Fast discrete intersection detection for cloth penetration resolution. In 2015 IEEE International Conference on Multimedia Big Data. IEEE, 352–357.Google ScholarDigital Library
41. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasi-Newton for Distortion Optimization. ACM Trans. Graph. (SIGGRAPH 2018) (2018).Google Scholar