“Real-time locally injective volumetric deformation”
Abstract:
We present a highly efficient method for interactive volumetric meshless shape deformation. Our method operates within a low dimensional sub-space of shape-aware C∞ harmonic maps, and is the first method that is guaranteed to produce a smooth locally injective deformation in 3D. Unlike mesh-based methods in which local injectivity is enforced on tetrahedral elements, our method enforces injectivity on a sparse set of domain samples. The main difficulty is then to certify the map as locally injective throughout the entire domain. This is done by utilizing the Lipschitz continuity property of the harmonic basis functions. We show a surprising relation between the Lipschitz constant of the smallest singular value of the map Jacobian and the norm of the Hessian. We further carefully derive a Lipschitz constant for the Hessian, and develop a sufficient condition for the injectivity certification. This is done by utilizing the special structure of the harmonic basis functions combined with a novel regularization term that pushes the Lipschitz constants further down. As a result, the injectivity analysis can be performed on a relatively sparse set of samples. Combined with a parallel GPU-based implementation, our method can produce superior deformations with unique quality guarantees at real-time rates which were possible only in 2D so far.
References:
1. Adams Bart, Ovsjanikov Maks, Wand Michael, Seidel Hans-Peter, and Guibas Leonidas J. 2008. Meshless Modeling of Deformable Shapes and Their Motion. In Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Dublin, Ireland) (SCA 2008). Eurographics Association, Goslar, DEU, 77–86.Google Scholar
2. Aharon Ido, Chen Renjie, Zorin Denis, and Weber Ofir. 2019. Bounded Distortion Tetrahedral Metric Interpolation. ACM Transactions on Graphics 38, 6 (2019), Article 182, 17 pages.Google Scholar
3. Aigerman Noam and Lipman Yaron. 2013. Injective and bounded distortion mappings in 3D. ACM Transactions on Graphics 32, 4 (2013), 106.Google Scholar
4. Ben-Chen Mirela, Weber Ofir, and Gotsman Craig. 2009. Variational harmonic maps for space deformation. ACM Transactions on Graphics 28, 3 (2009), Article 34, 11 pages.Google Scholar
5. Chao Isaac, Pinkall Ulrich, Sanan Patrick, and Schröder Peter. 2010. A simple geometric model for elastic deformations. ACM Transactions on Graphics 29, 4 (2010), Article 38, 6 pages.Google Scholar
6. Chen Renjie and Weber Ofir. 2015. Bounded distortion harmonic mappings in the plane. ACM Transactions on Graphics 34, 4 (2015), Article 73, 12 pages.Google Scholar
7. Chen Renjie and Weber Ofir. 2017. GPU-Accelerated Locally Injective Shape Deformation. ACM Transactions on Graphics 36, 6 (2017), Article 214, 13 pages.Google Scholar
8. Chen Renjie, Weber Ofir, Keren Daniel, and Ben-Chen Mirela. 2013. Planar shape interpolation with bounded distortion. ACM Transactions on Graphics 32, 4 (2013), Article 108, 11 pages.Google Scholar
9. Chien Edward, Chen Renjie, and Weber Ofir. 2016a. Bounded Distortion Harmonic Shape Interpolation. ACM Transactions on Graphics 35, 4 (2016), Article 105, 15 pages.Google Scholar
10. Chien Edward, Levi Zohar, and Weber Ofir. 2016b. Bounded Distortion Parametrization in the Space of Metrics. ACM Transactions on Graphics 35, 6 (2016), Article 215, 16 pages.Google Scholar
11. Floater Michael S., Kós Géza, and Reimers Martin. 2005. Mean value coordinates in 3D. Computer Aided Geometric Design 22, 7 (2005), 623–631.Google ScholarCross Ref
12. Fu Xiao-Ming, Liu Yang, and Guo Baining. 2015. Computing Locally Injective Mappings by Advanced MIPS. ACM Transactions on Graphics 34, 4, Article 71 (2015), 12 pages.Google Scholar
13. Golub Gene H. and Van Loan Charles F. 1996. Matrix Computations (3rd Ed.). Johns Hopkins University Press, USA.Google Scholar
14. Hefetz Fedida Eden, Chien Edward, and Weber Ofir. 2017. Fast Planar Harmonic Deformations with Alternating Tangential Projections. Computer Graphics Forum 36, 5 (2017), 175–188. Proceedings of Symposium on Geometry Processing 2017.Google ScholarDigital Library
15. Huang Jin, Shi Xiaohan, Liu Xinguo, Zhou Kun, Wei Li-Yi, Teng Shang-Hua, Bao Hujun, Guo Baining, and Shum Heung-Yeung. 2006. Subspace Gradient Domain Mesh Deformation. ACM Transactions on Graphics 25, 3 (2006), 1126–1134.Google ScholarDigital Library
16. Igarashi Takeo, Moscovich Tomer, and Hughes John F. 2005. As-rigid-as-possible shape manipulation. ACM Transactions on Graphics 24, 3 (2005), 1134–1141.Google ScholarDigital Library
17. Jacobson Alec, Baran Ilya, Popović Jovan, and Sorkine Olga. 2011. Bounded biharmonic weights for real-time deformation. ACM Transactions on Graphics 30, 4 (2011), Article 78, 8 pages.Google Scholar
18. Joshi Pushkar, Meyer Mark, DeRose Tony, and Green Brian. 2007. Harmonic coordinates for character articulation. ACM Transactions on Graphics 26, 3 (2007), 71.Google ScholarDigital Library
19. Ju Tao, Schaefer Scott, and Warren Joe. 2005. Mean value coordinates for closed triangular meshes. ACM Transactions on Graphics 24, 3 (2005), 561–566.Google ScholarDigital Library
20. Kovalsky Shahar Z., Aigerman Noam, Basri Ronen, and Lipman Yaron. 2014. Controlling Singular Values with Semidefinite Programming. ACM Transactions on Graphics 33, 4, Article 68 (2014), 13 pages.Google Scholar
21. Kovalsky Shahar Z., Aigerman Noam, Basri Ronen, and Lipman Yaron. 2015. Large-scale bounded distortion mappings. ACM Transactions on Graphics 34, 6 (2015), Article 191.Google Scholar
22. Kovalsky Shahar Z., Galun Meirav, and Lipman Yaron. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Transactions on Graphics 35, 4 (2016), Article 134.Google Scholar
23. Laugesen Richard Snyder. 1996. Injectivity can fail for higher-dimensional harmonic extensions. Complex Variables, Theory and Application: An International Journal 28, 4 (1996), 357–369.Google ScholarCross Ref
24. Levi Z. and Gotsman C. 2015. Smooth Rotation Enhanced As-Rigid-As-Possible Mesh Animation. IEEE Transactions on Visualization and Computer Graphics 21, 2 (2015), 264–277.Google ScholarDigital Library
25. Levi Zohar and Weber Ofir. 2016. On the convexity and feasibility of the bounded distortion harmonic mapping problem. ACM Transactions on Graphics 35, 4 (2016), Article 106, 15 pages.Google Scholar
26. Li Xian-Ying, Ju Tao, and Hu Shi-Min. 2013. Cubic mean value coordinates. ACM Transactions on Graphics 32, 4 (2013), Article 126, 10 pages.Google Scholar
27. Lipman Yaron. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics 31, 4 (2012), 108.Google Scholar
28. Lipman Yaron, Levin David, and Cohen-Or Daniel. 2008. Green Coordinates. ACM Transactions on Graphics 27, 3 (2008), 10 pages.Google Scholar
29. Lipman Yaron, Sorkine Olga, Levin David, and Cohen-Or Daniel. 2005. Linear rotation-invariant coordinates for meshes. ACM Transactions on Graphics 24, 3 (2005), 479–487.Google ScholarDigital Library
30. Nocedal Jorge and Wright Stephen. 2006. Numerical Optimization. Springer Science & Business Media, New York.Google Scholar
31. Poranne Roi and Lipman Yaron. 2014. Provably good planar mappings. ACM Transactions on Graphics 33, 4 (2014), 76.Google Scholar
32. Pugh Charles C. 2015. Real Mathematical Analysis (2nd Ed.). Springer, Cham, USA.Google Scholar
33. Rabinovich Michael, Poranne Roi, Panozzo Daniele, and Sorkine-Hornung Olga. 2017. Scalable Locally Injective Mappings. ACM Transactions on Graphics 36, 2, Article 16 (2017), 16 pages.Google Scholar
34. Sacht Leonardo, Vouga Etienne, and Jacobson Alec. 2015. Nested Cages. ACM Transactions on Graphics 34, 6, Article 170 (2015), 14 pages.Google Scholar
35. Schüller Christian, Kavan Ladislav, Panozzo Daniele, and Sorkine-Hornung Olga. 2013. Locally injective mappings. Computer Graphics Forum 32, 5 (2013), 125–135.Google ScholarDigital Library
36. Sederberg Thomas W. and Parry Scott R. 1986. Free-Form Deformation of Solid Geometric Models. In Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH 1986). Association for Computing Machinery, New York, NY, USA, 151–160.Google Scholar
37. Si Hang. 2015. TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator. ACM Trans. Math. Softw. 41, 2, Article 11 (2015), 36 pages.Google Scholar
38. Smith Breannan, Goes Fernando De, and Kim Theodore. 2019. Analytic Eigensystems for Isotropic Distortion Energies. ACM Transactions on Graphics 38, 1, Article 3 (2019), 15 pages.Google Scholar
39. Smith Jason and Schaefer Scott. 2015. Bijective Parameterization with Free Boundaries. ACM Transactions on Graphics 34, 4 (2015), Article 70, 9 pages.Google Scholar
40. Sorkine Olga and Alexa Marc. 2007. As-rigid-as-possible Surface Modeling. In Proceedings of the Symposium on Geometry Processing. Eurographics, Switzerland, 109–116.Google Scholar
41. Stomakhin Alexey, Howes Russell, Schroeder Craig, and Teran Joseph M. 2012. Energetically Consistent Invertible Elasticity. In Eurographics Conference on Computer Animation (Lausanne, Switzerland) (EUROSCA’12). Eurographics Association, Goslar, DEU, 25–32.Google Scholar
42. Sumner Robert W and Popović Jovan. 2004. Deformation transfer for triangle meshes. ACM Transactions on Graphics 23, 3 (2004), 399–405.Google ScholarDigital Library
43. Thiery Jean-Marc, Tierny Julien, and Boubekeur Tamy. 2014. Jacobians and Hessians of mean value coordinates for closed triangular meshes. The Visual Computer 30, 9 (2014), 981–995.Google ScholarDigital Library
44. Weber Ofir, Ben-Chen Mirela, and Gotsman Craig. 2009. Complex Barycentric Coordinates with Applications to Planar Shape Deformation. Computer Graphics Forum 28, 2 (2009), 587–597.Google ScholarCross Ref
45. Weber Ofir and Gotsman Craig. 2010. Controllable conformal maps for shape deformation and interpolation. ACM Transactions on Graphics 29, 4 (2010), Article 78, 11 pages.Google Scholar
46. Weber Ofir, Myles Ashish, and Zorin Denis. 2012a. Computing Extremal Quasiconformal Maps. Computer Graphics Forum 31, 5 (2012), 1679–1689.Google ScholarDigital Library
47. Weber Ofir, Poranne Roi, and Gotsman Craig. 2012b. Biharmonic Coordinates. Computer Graphics Forum 31, 8 (2012), 2409–2422.Google ScholarDigital Library
