“Compatible intrinsic triangulations” by Takayama

Finding distortion-minimizing homeomorphisms between surfaces of arbitrary genus is a fundamental task in computer graphics and geometry processing. We propose a simple method utilizing intrinsic triangulations, operating directly on the original surfaces without going through any intermediate domains such as a plane or a sphere. Given two models A and B as triangle meshes, our algorithm constructs a Compatible Intrinsic Triangulation (CIT), a pair of intrinsic triangulations over A and B with full correspondences in their vertices, edges and faces. Such a tessellation allows us to establish consistent images of edges and faces of A’s input mesh over B (and vice versa) by tracing piecewise-geodesic paths over A and B. Our algorithm for constructing CITs, primarily consisting of carefully designed edge flipping schemes, is empirical in nature without any guarantee of success, but turns out to be robust enough to be used within a similar second-order optimization framework as was used previously in the literature. The utility of our method is demonstrated through comparisons and evaluation on a standard benchmark dataset.

1. Noam Aigerman, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Spherical Orbifold Tutte Embeddings. ACM Trans. Graph. 36, 4, Article 90 (2017).Google ScholarDigital Library
2. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM Trans. Graph. 34, 6, Article 190 (2015).Google ScholarDigital Library
3. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. 35, 6, Article 217 (2016).Google ScholarDigital Library
4. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted Bijections for Low Distortion Surface Mappings. ACM Trans. Graph. 33, 4, Article 69 (2014).Google ScholarDigital Library
5. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless Surface Mappings. ACM Trans. Graph. 34, 4, Article 72 (2015).Google ScholarDigital Library
6. Marc Alexa. 2000. Merging polyhedral shapes with scattered features. The Visual Computer 16, 1 (2000), 26–37.Google ScholarDigital Library
7. 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 (SIGGRAPH ’00). 157–164.Google ScholarDigital Library
8. Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2005. Consistent Spherical Parameterization. In Computational Science – ICCS 2005. 265–272.Google Scholar
9. Alex Baden, Keenan Crane, and Misha Kazhdan. 2018. Möbius Registration. Comput. Graph. Forum 37, 5 (2018), 211–220.Google ScholarCross Ref
10. W. V. Baxter III, P. Barla, and K. Anjyo. 2009. Compatible Embedding for 2D Shape Animation. IEEE Trans. Vis. Comput. Graph. 15, 5 (2009), 867–879.Google ScholarDigital Library
11. Sofien Bouaziz, Andrea Tagliasacchi, and Mark Pauly. 2013. Sparse Iterative Closest Point. Comput. Graph. Forum 32, 5 (2013), 113–123.Google ScholarDigital Library
12. Xiaobai Chen, Aleksey Golovinskiy, and Thomas Funkhouser. 2009. A Benchmark for 3D Mesh Segmentation. ACM Trans. Graph. 28, 3 (2009).Google ScholarDigital Library
13. A. F. El Ouafdi, H. El Houari, and D. Ziou. 2021. Adaptive estimation of Hodge star operator on simplicial surfaces. The Visual Computer 37, 6 (2021), 1433–1445.Google ScholarDigital Library
14. D. Ezuz, B. Heeren, O. Azencot, M. Rumpf, and M. Ben-Chen. 2019a. Elastic Correspondence between Triangle Meshes. Comput. Graph. Forum 38, 2 (2019), 121–134.Google ScholarCross Ref
15. Danielle Ezuz, Justin Solomon, and Mirela Ben-Chen. 2019b. Reversible Harmonic Maps between Discrete Surfaces. ACM Trans. Graph. 38, 2, Article 15 (2019).Google ScholarDigital Library
16. Marco Fumero, Michael Möller, and Emanuele Rodolà. 2020. Nonlinear Spectral Geometry Processing via the TV Transform. ACM Trans. Graph. 39, 6, Article 199 (2020).Google ScholarDigital Library
17. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. https://eigen.tuxfamily.org/dox/unsupported/group__AutoDiff__Module.html.Google Scholar
18. Qi-Xing Huang, Bart Adams, Martin Wicke, and Leonidas J. Guibas. 2008. Non-Rigid Registration Under Isometric Deformations. Comput. Graph. Forum 27, 5 (2008), 1449–1457.Google ScholarCross Ref
19. Zhongshi Jiang, Teseo Schneider, Denis Zorin, and Daniele Panozzo. 2020. Bijective Projection in a Shell. ACM Trans. Graph. 39, 6, Article 247 (2020).Google ScholarDigital Library
20. T. Kanai, H. Suzuki, and F. Kimura. 1997. 3D geometric metamorphosis based on harmonic map. In Proceedings The Fifth Pacific Conference on Computer Graphics and Applications. 97–104.Google Scholar
21. Vladimir G. Kim, Yaron Lipman, and Thomas Funkhouser. 2011. Blended Intrinsic Maps. ACM Trans. Graph. 30, 4, Article 79 (2011).Google ScholarDigital Library
22. Vladislav Kraevoy and Alla Sheffer. 2004. Cross-Parameterization and Compatible Remeshing of 3D Models. ACM Trans. Graph. 23, 3 (2004), 861–869.Google ScholarDigital Library
23. Yaron Lipman and Thomas Funkhouser. 2009. MöBius Voting for Surface Correspondence. ACM Trans. Graph. 28, 3, Article 72 (2009).Google ScholarDigital Library
24. Nathan Litke, Marc Droske, Martin Rumpf, and Peter Schröder. 2005. An Image Processing Approach to Surface Matching. In Eurographics Symposium on Geometry Processing 2005.Google Scholar
25. Zhiguang Liu, Liuyang Zhou, Howard Leung, and Hubert P. H. Shum. 2018. High-quality compatible triangulations and their application in interactive animation. Computers & Graphics 76 (2018), 60–72.Google ScholarCross Ref
26. Manish Mandad, David Cohen-Steiner, Leif Kobbelt, Pierre Alliez, and Mathieu Desbrun. 2017. Variance-Minimizing Transport Plans for Inter-Surface Mapping. ACM Trans. Graph. 36, 4, Article 39 (2017).Google ScholarDigital Library
27. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional Maps: A Flexible Representation of Maps between Shapes. ACM Trans. Graph. 31, 4, Article 30 (2012).Google ScholarDigital Library
28. Daniele Panozzo, Ilya Baran, Olga Diamanti, and Olga Sorkine-Hornung. 2013. Weighted Averages on Surfaces. ACM Trans. Graph. 32, 4, Article 60 (2013).Google ScholarDigital Library
29. Emil Praun, Wim Sweldens, and Peter Schröder. 2001. Consistent Mesh Parameterizations. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). 179–184.Google ScholarDigital Library
30. Patrick Schmidt, Janis Born, Marcel Campen, and Leif Kobbelt. 2019. Distortion-Minimizing Injective Maps between Surfaces. ACM Trans. Graph. 38, 6, Article 156 (2019).Google ScholarDigital Library
31. Patrick Schmidt, Marcel Campen, Janis Born, and Leif Kobbelt. 2020. Inter-Surface Maps via Constant-Curvature Metrics. ACM Trans. Graph. 39, 4, Article 119 (2020).Google ScholarDigital Library
32. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-Surface Mapping. ACM Trans. Graph. 23, 3 (2004), 870–877.Google ScholarDigital Library
33. 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), 835–844.Google ScholarDigital Library
34. Nicholas Sharp and Keenan Crane. 2020a. A Laplacian for Nonmanifold Triangle Meshes. Comput. Graph. Forum 39, 5 (2020), 69–80.Google ScholarCross Ref
35. Nicholas Sharp and Keenan Crane. 2020b. You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges. ACM Trans. Graph. 39, 6, Article 249 (2020).Google ScholarDigital Library
36. Nicholas Sharp, Keenan Crane, et al. 2019a. geometry-central. https://www.geometry-central.net.Google Scholar
37. Nicholas Sharp, Yousuf Soliman, and Keenan Crane. 2019b. Navigating Intrinsic Triangulations. ACM Trans. Graph. 38, 4, Article 55 (2019).Google ScholarDigital Library
38. R. Shi, W. Zeng, Z. Su, J. Jiang, H. Damasio, Z. Lu, Y. Wang, S. Yau, and X. Gu. 2017. Hyperbolic Harmonic Mapping for Surface Registration. IEEE Trans. Pattern Anal. Mach. Intell. 39, 05 (2017), 965–980.Google ScholarDigital Library
39. Justin Solomon, Andy Nguyen, Adrian Butscher, Mirela Ben-Chen, and Leonidas Guibas. 2012. Soft Maps Between Surfaces. Comput. Graph. Forum 31, 5 (2012), 1617–1626.Google ScholarDigital Library
40. V. Surazhsky and C. Gotsman. 2004. High Quality Compatible Triangulations. Eng. with Comput. 20, 2 (2004), 147–156.Google ScholarDigital Library
41. Gary K.L. Tam, Zhi-Quan Cheng, Yu-Kun Lai, Frank C. Langbein, Yonghuai Liu, David Marshall, Ralph R. Martin, Xian-Fang Sun, and Paul L. Rosin. 2013. Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid. IEEE Trans. Vis. Comput. Graph. 19, 7 (2013), 1199–1217.Google ScholarDigital Library
42. J. Tao, J. Zhang, B. Deng, Z. Fang, Y. Peng, and Y. He. 2021. Parallel and Scalable Heat Methods for Geodesic Distance Computation. IEEE Trans. Pattern Anal. Mach. Intell. 43, 2 (2021), 579–594.Google ScholarDigital Library
43. Julien Tierny, Joel Daniels, Luis G. Nonato, Valerio Pascucci, and Claudio T. Silva. 2011. Inspired quadrangulation. Computer-Aided Design 43, 11 (2011), 1516–1526.Google ScholarDigital Library
44. Huai-Yu Wu, Chunhong Pan, Qing Yang, and Songde Ma. 2007. Consistent Correspondence between Arbitrary Manifold Surfaces. In International Conference on Computer Vision.Google ScholarCross Ref
45. Y. Yang, X. Fu, S. Chai, S. Xiao, and L. Liu. 2019. Volume-Enhanced Compatible Remeshing of 3D Models. IEEE Trans. Vis. Comput. Graph. 25, 10 (2019), 2999–3010.Google ScholarCross Ref
46. Yang Yang, Wen-Xiang Zhang, Yuan Liu, Ligang Liu, and Xiao-Ming Fu. 2020. Error-Bounded Compatible Remeshing. ACM Trans. Graph. 39, 4, Article 113 (2020).Google ScholarDigital Library
47. Lei Zhang, Ligang Liu, Zhongping Ji, and Guojin Wang. 2006. Manifold Parameterization. In Advances in Computer Graphics. 160–171.Google Scholar