“Progressive embedding” by Shen, Jiang, Zorin and Panozzo
Conference:
Type(s):
Title:
- Progressive embedding
Session/Category Title: Shape Science
Presenter(s)/Author(s):
Abstract:
Tutte embedding is one of the most common building blocks in geometry processing algorithms due to its simplicity and provable guarantees. Although provably correct in infinite precision arithmetic, it fails in challenging cases when implemented using floating point arithmetic, largely due to the induced exponential area changes.We propose Progressive Embedding, with similar theoretical guarantees to Tutte embedding, but more resilient to the rounding error of floating point arithmetic. Inspired by progressive meshes, we collapse edges on an invalid embedding to a valid, simplified mesh, then insert points back while maintaining validity. We demonstrate the robustness of our method by computing embeddings for a large collection of disk topology meshes.By combining our robust embedding with a variant of the matchmaker algorithm, we propose a general algorithm for the problem of mapping multiply connected domains with arbitrary hard constraints to the plane, with applications in texture mapping and remeshing.
References:
1. Noam Aigerman, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Spherical Orbifold Tutte Embeddings. ACM Trans. Graph. 36, 4, Article 90 (July 2017), 13 pages. Google ScholarDigital Library
2. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte Embeddings. ACM Trans. Graph. 34, 6, Article 190 (Oct. 2015), 12 pages. Google ScholarDigital Library
3. Noam Aigerman and Yaron Lipman. 2016. Hyperbolic Orbifold Tutte Embeddings. ACM Trans. Graph. 35, 6, Article 217 (Nov. 2016), 14 pages. Google ScholarDigital Library
4. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted Bijections for Low Distortion Surface Mappings. ACM Trans. Graph. 33, 4 (2014), 69:1–69:12. Google ScholarDigital Library
5. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2015. Seamless Surface Mappings. ACM Trans. Graph. 34, 4, Article 72 (July 2015), 13 pages. Google ScholarDigital Library
6. David Bommes, Marcel Campen, Hans-Christian Ebke, Pierre Alliez, and Leif Kobbelt. 2013. Integer-grid Maps for Reliable Quad Meshing. ACM Trans. Graph. 32, 4, Article 98 (July 2013), 12 pages. Google ScholarDigital Library
7. D. Bommes, B. Lévy, N. Pietroni, E. Puppo, C. Silv a, M. Tarini, and D. Zorin. 2012. State of the Art in Quad Meshing. In Eurographics STARS.Google Scholar
8. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer Quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages. Google ScholarDigital Library
9. Hervé Brönnimann, Andreas Fabri, Geert-Jan Giezeman, Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Stefan Schirra. 2018. 2D and 3D Linear Geometry Kernel. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https://doc.cgal.org/4.13/Manual/packages.html#PkgKernel23SummaryGoogle Scholar
10. Marcel Campen, Cláudio T. Silva, and Denis Zorin. 2016. Bijective Maps from Simplicial Foliations. ACM Trans. Graph. 35, 4, Article 74 (July 2016), 15 pages. Google ScholarDigital Library
11. Erin W. Chambers, David Eppstein, Michael T. Goodrich, and Maarten Löffler. 2011. Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area. In Proceedings of the 18th International Conference on Graph Drawing (GD’10). Springer-Verlag, Berlin, Heidelberg, 129–140. http://dl.acm.org/citation.cfm?id=1964371.1964384 Google ScholarDigital Library
12. S. Claici, M. Bessmeltsev, S. Schaefer, and J. Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. Comput. Graph. Forum 36, 5 (Aug. 2017), 37–47. Google ScholarDigital Library
13. P. Degener, J. Meseth, and R. Klein. 2003. An Adaptable Surface Parameterization Method. In Proceedings of the 12th International Meshing Roundtable. 201–213.Google Scholar
14. Tamal K Dey, Herbert Edelsbrunner, Sumanta Guha, and Dmitry V Nekhayev. 1999. Topology preserving edge contraction. Publ. Inst. Math.(Beograd)(NS) 66, 80 (1999), 23–45.Google Scholar
15. István Fáry. 1948. On straight line representation of planar graphs. Acta Univ. Szeged. Sect. Sci. Math. 11 (1948), 229–233.Google Scholar
16. Michael S. Floater. 1997. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 14 (1997), 231–250. Google ScholarDigital Library
17. Michael S. Floater and Kai Hormann. 2005. Surface Parameterization: a Tutorial and Survey. In In Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization. Springer Verlag, 157–186.Google Scholar
18. Laurent Fousse, Guillaume Hanrot, Vincent Lefèvre, Patrick Pélissier, and Paul Zimmermann. 2007. MPFR: A Multiple-precision Binary Floating-point Library with Correct Rounding. ACM Trans. Math. Softw. 33, 2, Article 13 (June 2007). Google ScholarDigital Library
19. Xiao-Ming Fu and Yang Liu. 2016. Computing Inversion-free Mappings by Simplex Assembly. ACM Trans. Graph. 35, 6, Article 216 (Nov. 2016), 12 pages. Google ScholarDigital Library
20. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing Locally Injective Mappings by Advanced MIPS. ACM Trans. Graph. 34, 4, Article 71 (July 2015), 12 pages. Google ScholarDigital Library
21. Craig Gotsman and Vitaly Surazhsky. 2001. Guaranteed intersection-free polygon morphing. Computers & Graphics 25, 1 (2001), 67–75.Google ScholarCross Ref
22. Torbjörn Granlund. 2018. GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.). http://gmplib.org/.Google Scholar
23. Gaël Guennebaud, Benoît Jacob, et al. 2010. Eigen v3. http://eigen.tuxfamily.org.Google Scholar
24. Dan Halperin and Eli Packer. 2002. Iterated snap rounding. Computational Geometry 23, 2 (2002), 209 — 225. Google ScholarDigital Library
25. Hugues Hoppe. 1996. Progressive Meshes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’96). ACM, New York, NY, USA, 99–108. Google ScholarDigital Library
26. K. Hormann and G. Greiner. 2000. MIPS: An Efficient Global Parametrization Method. In Curve and Surface Design: Saint-Malo 1999. 153–162.Google Scholar
27. Kai Hormann, Bruno Lévy, and Alla Sheffer. 2007. Mesh Parameterization: Theory and Practice. In ACM SIGGRAPH 2007 Courses (SIGGRAPH ’07). ACM, New York, NY, USA. Google ScholarDigital Library
28. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (July 2018), 14 pages. Google ScholarDigital Library
29. John FP Hudson and Julius L Shaneson. 1969. Piecewise linear topology. Vol. 11. WA Benjamin New York.Google Scholar
30. Alec Jacobson, Daniele Panozzo, et al. 2016. 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 Trans. Graph. 36, 6, Article 186 (Nov. 2017), 9 pages. Google ScholarDigital Library
32. Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2015. Large-scale Bounded Distortion Mappings. ACM Trans. Graph. 34, 6, Article 191 (Oct. 2015), 10 pages. Google ScholarDigital Library
33. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. 35, 4, Article 134 (July 2016), 11 pages. Google ScholarDigital Library
34. Vladislav Kraevoy and Alla Sheffer. 2004. Cross-parameterization and Compatible Remeshing of 3D Models. ACM Trans. Graph. 23, 3 (Aug. 2004), 861–869. Google ScholarDigital Library
35. Vladislav Kraevoy, Alla Sheffer, and Craig Gotsman. 2003. Matchmaker: Constructing Constrained Texture Maps. ACM Trans. Graph. 22, 3 (July 2003), 326–333. Google ScholarDigital Library
36. Ludek Kucera. 1991. The greedy coloring is a bad probabilistic algorithm. Journal of Algorithms 12, 4 (1991), 674 — 684. Google ScholarDigital Library
37. Ulf Labsik, Kai Hormann, and Guenther Greiner. 2000. Using Most Isometric Parametrizations for Remeshing Polygonal Surfaces. In Proceedings of the Geometric Modeling and Processing 2000 (GMP 2000). IEEE Computer Society, Washington, DC, USA. Google ScholarDigital Library
38. T. Y. Lee, S. W. Yen, and I. C. Yeh. 2008. Texture Mapping with Hard Constraints Using Warping Scheme. IEEE Transactions on Visualization and Computer Graphics 14, 2 (March 2008), 382–395. Google ScholarDigital Library
39. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. ACM Trans. Graph. 21, 3 (July 2002), 362–371. Google ScholarDigital Library
40. Minchen Li, Danny M Kaufman, Vladimir G Kim, Justin Solomon, and Alla Sheffer. 2018. OptCuts: joint optimization of surface cuts and parameterization. In SIGGRAPH Asia 2018 Technical Papers. ACM, 247. Google ScholarDigital Library
41. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4 (2012), 108:1–108:13. Google ScholarDigital Library
42. Yaron Lipman. 2014. Bijective mappings of meshes with boundary and the degree in mesh processing. SIAM Journal on Imaging Sciences 7, 2 (2014), 1263–1283.Google ScholarDigital Library
43. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive Parameterizations. ACM Trans. Graph. 37, 4, Article 41 (July 2018), 12 pages. Google ScholarDigital Library
44. Aleksandar Mijatović. 2003. Simplifying triangulations of S3. Pacific journal of mathematics 208, 2 (2003), 291–324.Google Scholar
45. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air Meshes for Robust Collision Handling. ACM Trans. Graph. 34, 4, Article 133 (July 2015), 9 pages. Google ScholarDigital Library
46. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (July 2014), 14 pages. Google ScholarDigital Library
47. Eli Packer. 2018. 2D Snap Rounding. In CGAL User and Reference Manual (4.13 ed.). CGAL Editorial Board. https://doc.cgal.org/4.13/Manual/packages.html#PkgSnapRounding2SummaryGoogle Scholar
48. Yue Peng, Bailin Deng, Juyong Zhang, Fanyu Geng, Wenjie Qin, and Ligang Liu. 2018. Anderson Acceleration for Geometry Optimization and Physics Simulation. ACM Trans. Graph. 37, 4, Article 42 (July 2018), 14 pages. Google ScholarDigital Library
49. Roi Poranne and Yaron Lipman. 2014. Provably Good Planar Mappings. ACM Trans. Graph. 33, 4, Article 76 (July 2014), 11 pages. Google ScholarDigital Library
50. Roi Poranne, Marco Tarini, Sandro Huber, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Autocuts: Simultaneous Distortion and Cut Optimization for UV Mapping. ACM Trans. Graph. 36, 6, Article 215 (Nov. 2017), 11 pages. Google ScholarDigital Library
51. 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). ACM, New York, NY, USA, 179–184. Google ScholarDigital Library
52. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2, Article 16 (April 2017), 16 pages. Google ScholarDigital Library
53. Pedro V. Sander, John Snyder, Steven J. Gortler, and Hugues Hoppe. 2001. Texture Mapping Progressive Meshes. In ACM SIGGRAPH. 409–416. Google ScholarDigital Library
54. Walter Schnyder. 1990. Embedding Planar Graphs on the Grid. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’90). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 138–148. http://dl.acm.org/citation.cfm?id=320176.320191 Google ScholarDigital Library
55. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-surface Mapping. ACM Trans. Graph. 23, 3 (Aug. 2004), 870–877. Google ScholarDigital Library
56. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. In Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing (SGP ’13). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 125–135. Google ScholarDigital Library
57. Aviv Segall, Orestis Vantzos, and Mirela Ben-Chen. 2016. Hele-Shaw flow simulation with interactive control using complex barycentric coordinates. In Proceedings of the ACM SIGGRAPH/Eurographics symposium on computer animation. Eurographics Association, 85–95. Google ScholarDigital Library
58. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh Parameterization Methods and Their Applications. Found. Trends. Comput. Graph. Vis. 2, 2 (2006), 105–171. Google ScholarDigital Library
59. Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In Applied Computational Geometry: Towards Geometric Engineering, Ming C. Lin and Dinesh Manocha (Eds.). Lecture Notes in Computer Science, Vol. 1148. Springer-Verlag, 203–222. From the First ACM Workshop on Applied Computational Geometry. Google ScholarDigital Library
60. Peter W Shor and Christopher J Van Wyk. 1992. Detecting and decomposing self-overlapping curves. Computational Geometry 2, 1 (1992), 31–50. Google ScholarDigital Library
61. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans. Graph. 36, 4, Article 38 (July 2017), 11 pages. Google ScholarDigital Library
62. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (July 2015), 9 pages. Google ScholarDigital Library
63. Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, and Dani Lischinski. 2002. Bounded-distortion Piecewise Mesh Parameterization. In Proceedings of the Conference on Visualization. 355–362. Google ScholarDigital Library
64. W.T Tutte. 1963. How to draw a graph. Proc. London Math. Soc., 3 (1963), 743–768.Google ScholarCross Ref
65. Ofir Weber and Denis Zorin. 2014. Locally Injective Parametrization with Arbitrary Fixed Boundaries. ACM Trans. Graph. 33, 4, Article 75 (July 2014), 12 pages. Google ScholarDigital Library
66. Eugene Zhang, Konstantin Mischaikow, and Greg Turk. 2005. Feature-based Surface Parameterization and Texture Mapping. ACM Trans. Graph. 24, 1 (Jan. 2005), 1–27. Google ScholarDigital Library
67. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).Google Scholar
68. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasinewton for Distortion Optimization. ACM Trans. Graph. 37, 4, Article 40 (July 2018), 14 pages. Google ScholarDigital Library
