“Distortion-minimizing injective maps between surfaces” by Schmidt, Born, Campen and Kobbelt
Conference:
Type(s):
Title:
- Distortion-minimizing injective maps between surfaces
Session/Category Title: Geometry Brekkie
Presenter(s)/Author(s):
Moderator(s):
Abstract:
The problem of discrete surface parametrization, i.e. mapping a mesh to a planar domain, has been investigated extensively. We address the more general problem of mapping between surfaces. In particular, we provide a formulation that yields a map between two disk-topology meshes, which is continuous and injective by construction and which locally minimizes intrinsic distortion. A common approach is to express such a map as the composition of two maps via a simple intermediate domain such as the plane, and to independently optimize the individual maps. However, even if both individual maps are of minimal distortion, there is potentially high distortion in the composed map. In contrast to many previous works, we minimize distortion in an end-to-end manner, directly optimizing the quality of the composed map. This setting poses additional challenges due to the discrete nature of both the source and the target domain. We propose a formulation that, despite the combinatorial aspects of the problem, allows for a purely continuous optimization. Further, our approach addresses the non-smooth nature of discrete distortion measures in this context which hinders straightforward application of off-the-shelf optimization techniques. We demonstrate that, despite the challenges inherent to the more involved setting, discrete surface-to-surface maps can be optimized effectively.
References:
1. Noam Aigerman, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Spherical Orbifold Tutte Embeddings. ACM Transactions on Graphics 36, 4 (2017).Google ScholarDigital Library
2. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM Transactions on Graphics 34, 6 (2015).Google ScholarDigital Library
3. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Transactions on Graphics 35, 6 (2016).Google ScholarDigital Library
4. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted Bijections for Low Distortion Surface Mappings. ACM Transactions on Graphics 33, 4 (2014).Google ScholarDigital Library
5. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless Surface Mappings. ACM Transactions on Graphics 34, 4 (2015).Google ScholarDigital Library
6. Marc Alexa. 2000. Merging Polyhedral Shapes with Scattered Features. The Visual Computer 16, 1 (2000).Google Scholar
7. Marc Alexa. 2002. Recent Advances in Mesh Morphing. In Computer Graphics Forum, Vol. 21.Google ScholarCross Ref
8. Brett Allen, Brian Curless, and Zoran Popović. 2003. The Space of Human Body Shapes: Reconstruction and Parameterization from Range Scans. In ACM Transactions on Graphics, Vol. 22.Google ScholarDigital Library
9. Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2005. Consistent Spherical Parameterization. In International Conference on Computational Science. Springer.Google Scholar
10. Omri Azencot, Etienne Corman, Mirela Ben-Chen, and Maks Ovsjanikov. 2017. Consistent Functional Cross Field Design for Mesh Quadrangulation. ACM Transactions on Graphics 36, 4 (2017).Google ScholarDigital Library
11. Alex Baden, Keenan Crane, and Misha Kazhdan. 2018. Möbius Registration. Computer Graphics Forum (2018).Google Scholar
12. Henning Biermann, Ioana Martin, Fausto Bernardini, and Denis Zorin. 2002. Cut-and-Paste Editing of Multiresolution Surfaces. ACM Transactions on Graphics 21, 3 (2002).Google ScholarDigital Library
13. Volker Blanz and Thomas Vetter. 1999. A Morphable Model for the Synthesis of 3D Faces. In Proceedings of SIGGRAPH ’99. ACM Press / Addison-Wesley.Google ScholarDigital Library
14. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013. Integer-Grid Maps for Reliable Quad Meshing. ACM Transactions on Graphics 32, 4 (2013).Google ScholarDigital Library
15. Mario Botsch, Stefan Steinberg, Stefan Bischoff, and Leif Kobbelt. 2002. OpenMesh: A Generic and Efficient Polygon Mesh Data Structure. OpenSG Symposium (2002).Google Scholar
16. Sofien Bouaziz, Andrea Tagliasacchi, and Mark Pauly. 2013. Sparse Iterative Closest Point. In Symposium on Geometry Processing. Eurographics Association.Google Scholar
17. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York.Google ScholarDigital Library
18. Marcel Campen, David Bommes, and Leif Kobbelt. 2012. Dual Loops Meshing: Quality Quad Layouts on Manifolds. ACM Transactions on Graphics 31, 4 (2012).Google ScholarDigital Library
19. Marcel Campen and Leif Kobbelt. 2014. Quad Layout Embedding via Aligned Parameterization. Computer Graphics Forum 33, 8 (2014).Google Scholar
20. Renjie Chen and Ofir Weber. 2017. GPU-Accelerated Locally Injective Shape Deformation. ACM Transactions on Graphics 36, 6 (2017).Google ScholarDigital Library
21. Sebastian Claici, Mikhail Bessmeltsev, Scott Schaefer, and Justin Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. In Computer Graphics Forum, Vol. 36.Google ScholarDigital Library
22. Hans-Christian Ebke, Patrick Schmidt, Marcel Campen, and Leif Kobbelt. 2016. Interactively Controlled Quad Remeshing of High Resolution 3D Models. ACM Transactions on Graphics 35, 6 (2016).Google ScholarDigital Library
23. Danielle Ezuz, Behrend Heeren, Omri Azencot, Martin Rumpf, and Mirela Ben-Chen. 2019a. Elastic Correspondence between Triangle Meshes. Computer Graphics Forum 38, 2 (2019).Google Scholar
24. Danielle Ezuz, Justin Solomon, and Mirela Ben-Chen. 2019b. Reversible Harmonic Maps between Discrete Surfaces. ACM Transactions on Graphics 38, 2 (2019).Google ScholarDigital Library
25. Björn Golla, Hans-Peter Seidel, and Renjie Chen. 2018. Piecewise Linear Mapping Optimization Based on the Complex View. In Computer Graphics Forum, Vol. 37.Google ScholarCross Ref
26. Aleksey Golovinskiy and Thomas Funkhouser. 2009. Consistent Segmentation of 3D Models. Computers & Graphics 33, 3 (2009).Google Scholar
27. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
28. Igor Guskov, Kiril Vidimce, Wim Sweldens, and Peter Schröder. 2000. Normal Meshes. In Proceedings of SIGGRAPH ’00.Google Scholar
29. Qi-Xing Huang, Bart Adams, Martin Wicke, and Leonidas J. Guibas. 2008. Non-Rigid Registration Under Isometric Deformations. In Symposium on Geometry Processing.Google Scholar
30. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A Simple C++ Geometry Processing Library. http://libigl.github.io/libigl/.Google Scholar
31. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Transactions on Graphics 36, 6 (2017).Google ScholarDigital Library
32. Takashi Kanai, Hiromasa Suzuki, and Fumihiko Kimura. 1997. 3D Geometric Metamorphosis Based on Harmonic Map. In Proceedings of Pacific Graphics ’97. IEEE.Google ScholarCross Ref
33. Andrei Khodakovsky, Nathan Litke, and Peter Schröder. 2003. Globally Smooth Parameterizations with Low Distortion. ACM Transactions on Graphics 22, 3 (2003).Google ScholarDigital Library
34. Vladimir G. Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended Intrinsic Maps. ACM Transactions on Graphics 30, 4.Google ScholarDigital Library
35. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Transactions on Graphics 35, 4 (2016).Google ScholarDigital Library
36. Vladislav Kraevoy and Alla Sheffer. 2004. Cross-Parameterization and Compatible Remeshing of 3D Models. ACM Transactions on Graphics 23, 3 (2004).Google ScholarDigital Library
37. Vladislav Kraevoy and Alla Sheffer. 2005. Template-Based Mesh Completion. In Symposium on Geometry Processing, Vol. 385.Google Scholar
38. Vladislav Kraevoy, Alla Sheffer, and Craig Gotsman. 2003. Matchmaker: Constructing Constrained Texture Maps. ACM Transactions on Graphics 22, 3 (2003).Google ScholarDigital Library
39. Aaron W. F. Lee, David Dobkin, Wim Sweldens, and Peter Schröder. 1999. Multiresolution Mesh Morphing. In Proceedings of SIGGRAPH ’99.Google ScholarDigital Library
40. Bruno Lévy. 2001. Constrained Texture Mapping for Polygonal Meshes. In Proceedings of SIGGRAPH ’01. ACM.Google ScholarDigital Library
41. Hao Li, Robert W Sumner, and Mark Pauly. 2008b. Global Correspondence Optimization for Non-Rigid Registration of Depth Scans. In Computer Graphics Forum, Vol. 27. Wiley Online Library.Google Scholar
42. Xin Li, Yunfan Bao, Xiaohu Guo, Miao Jin, Xianfeng Gu, and Hong Qin. 2008a. Globally Optimal Surface Mapping for Surfaces with Arbitrary Topology. IEEE Transactions on Visualization and Computer Graphics 14, 4 (2008).Google Scholar
43. Yaron Lipman. 2014. Bijective Mappings of Meshes with Boundary and the Degree in Mesh Processing. SIAM Journal on Imaging Sciences 7, 2 (2014).Google ScholarCross Ref
44. Yaron Lipman and Thomas Funkhouser. 2009. Möbius Voting for Surface Correspondence. ACM Transactions on Graphics 28, 3 (2009).Google ScholarDigital Library
45. Nathan Litke, Marc Droske, Martin Rumpf, and Peter Schröder. 2005. An Image Processing Approach to Surface Matching. In Symposium on Geometry Processing, Vol. 255.Google Scholar
46. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive Parameterizations. ACM Transactions on Graphics 37, 4 (2018).Google ScholarDigital Library
47. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A Local / Global Approach to Mesh Parameterization. In Symposium on Geometry Processing.Google Scholar
48. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. PolyCut: Monotone Graph-Cuts for PolyCube Base-Complex Construction. ACM Transactions on Graphics 32, 6 (2013).Google ScholarDigital Library
49. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-minimizing Transport Plans for Inter-Surface Mapping. ACM Transactions on Graphics 36, 4 (2017).Google ScholarDigital Library
50. Min Meng and Ying He. 2016. Consistent Quadrangulation for Shape Collections via Feature Line Co-extraction. Computer-Aided Design 70, C (2016).Google Scholar
51. Jan Möbius and Leif Kobbelt. 2010. OpenFlipper: An Open Source Geometry Processing and Rendering Framework. In International Conference on Curves and Surfaces.Google Scholar
52. Brent C. Munsell, Pahal Dalal, and Song Wang. 2008. Evaluating Shape Correspondence for Statistical Shape Analysis: A Benchmark Study. IEEE Transactions on Pattern Analysis and Machine Intelligence 30, 11 (2008).Google ScholarDigital Library
53. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization (2nd ed. ed.). Springer, New York.Google Scholar
54. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional Maps: A Flexible Representation of Maps Between Shapes. ACM Transactions on Graphics 31, 4 (2012).Google ScholarDigital Library
55. Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Sorkine-Hornung. 2013. Weighted Averages on Surfaces. ACM Transactions on Graphics 32, 4 (2013).Google ScholarDigital Library
56. Nico Pietroni, Marco Tarini, and Paolo Cignoni. 2010. Almost Isometric Mesh Parameterization through Abstract Domains. IEEE Transactions on Visualization and Computer Graphics 16, 4 (2010).Google ScholarDigital Library
57. Roi Poranne and Yaron Lipman. 2016. Simple Approximations of Planar Deformation Operators. Technical Report.Google Scholar
58. Emil Praun, Wim Sweldens, and Peter Schröder. 2001. Consistent Mesh Parameterizations. In Proceedings of SIGGRAPH ’01.Google ScholarDigital Library
59. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Transactions on Graphics 36, 4 (2017).Google ScholarDigital Library
60. Emanuele Rodolà, Michael Möller, and Daniel Cremers. 2015. Point-wise Map Recovery and Refinement from Functional Correspondence.Google Scholar
61. Pedro V. Sander, John Snyder, Steven J. Gortler, and Hugues Hoppe. 2001. Texture Mapping Progressive Meshes. In Proceedings of SIGGRAPH ’01. ACM.Google ScholarDigital Library
62. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-Surface Mapping. ACM Transactions on Graphics 23, 3 (2004).Google ScholarDigital Library
63. Andrei Sharf, Marina Blumenkrants, Ariel Shamir, and Daniel Cohen-Or. 2006. Snap-Paste: An Interactive Technique for Easy Mesh Composition. The Visual Computer 22, 9 (2006).Google Scholar
64. Jonathan Richard Shewchuk. 1996. Robust Adaptive Floating-Point Geometric Predicates. In Proceedings of the Twelfth Annual Symposium on Computational Geometry. Association for Computing Machinery.Google ScholarDigital Library
65. Rui Shi, Wei Zeng, Zhengyu Su, Jian Jiang, Hanna Damasio, Zhonglin Lu, Yalin Wang, Shing-Tung Yau, and Xianfeng Gu. 2017. Hyperbolic Harmonic Mapping for Surface Registration. IEEE Transactions on Pattern Analysis and Machine Intelligence 39, 5 (2017).Google ScholarDigital Library
66. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Transactions on Graphics 36, 4 (2017).Google ScholarDigital Library
67. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Transactions on Graphics 34, 4 (2015).Google ScholarDigital Library
68. Justin Solomon, Andy Nguyen, Adrian Butscher, Mirela Ben-Chen, and Leonidas Guibas. 2012. Soft Maps Between Surfaces. In Computer Graphics Forum, Vol. 31.Google ScholarDigital Library
69. Robert W. Sumner and Jovan Popović. 2004. Deformation Transfer for Triangle Meshes. ACM Transactions on Graphics 23, 3 (2004).Google ScholarDigital Library
70. Gary K. Tam, Zhi-Quan Cheng, Yu-Kun Lai, Frank Langbein, Yonghuai Liu, A. David Marshall, Ralph Martin, Xianfang Sun, and Paul Rosin. 2013. Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid. IEEE Transactions on Visualization and Computer Graphics 19, 7 (2013).Google ScholarDigital Library
71. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. Polycube-Maps. In ACM Transactions on Graphics, Vol. 23.Google ScholarDigital Library
72. Marco Tarini, Enrico Puppo, Daniele Panozzo, Nico Pietroni, and Paolo Cignoni. 2011. Simple Quad Domains for Field Aligned Mesh Parametrization. ACM Transactions on Graphics 30, 6 (2011).Google ScholarDigital Library
73. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust Quasistatic Finite Elements and Flesh Simulation. In SCA ’05.Google Scholar
74. Julien Tierny, Joel Daniels, Luis G. Nonato, Valerio Pascucci, and Claudio T. Silva. 2011. Inspired Quadrangulation. Computer-Aided Design 43, 11 (2011).Google Scholar
75. Oliver Van Kaick, Hao Zhang, Ghassan Hamarneh, and Daniel Cohen-Or. 2011. A Survey on Shape Correspondence. In Computer Graphics Forum, Vol. 30.Google Scholar
76. Christoph Von-Tycowicz, Christian Schulz, Hans-Peter Seidel, and Klaus Hildebrandt. 2015. Real-Time Nonlinear Shape Interpolation. ACM Transactions on Graphics 34, 3 (2015).Google ScholarDigital Library
77. Andrea Walther and Andreas Griewank. 2012. Getting Started with ADOL-C. In Combinatorial Scientific Computing, Uwe Naumann and Olaf Schenk (Eds.). CRC Press, Taylor & Francis Group.Google Scholar
78. Ofir Weber and Denis Zorin. 2014. Locally Injective Parametrization with Arbitrary Fixed Boundaries. ACM Transactions on Graphics 33, 4 (2014).Google ScholarDigital Library
79. Huai-Yu Wu, Chunhong Pan, Qing Yang, and Songde Ma. 2007. Consistent Correspondence Between Arbitrary Manifold Surfaces. In ICCV 2007. IEEE.Google Scholar
80. Yang Yang, Xiao-Ming Fu, Shuangming Chai, Shiwei Xiao, and Ligang Liu. 2018. Volume-Enhanced Compatible Remeshing of 3D Models. IEEE Transactions on Visualization and Computer Graphics (2018).Google Scholar
81. Lei Zhang, Ligang Liu, Zhongping Ji, and Guojin Wang. 2006. Manifold Parameterization. In Advances in Computer Graphics. Springer.Google Scholar
82. Jiaran Zhou, Marcel Campen, Denis Zorin, Changhe Tu, and Claudio T. Silva. 2018. Quadrangulation of Non-Rigid Objects Using Deformation Metrics. Computer-Aided Geometric Design 62 (2018).Google Scholar
