“Progressive embedding” by Shen, Jiang, Zorin and Panozzo

  • ©Hanxiao Shen, Zhongshi Jiang, Denis Zorin, and Daniele Panozzo

Conference:


Type:


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


ACM Digital Library Publication:



Overview Page: