“OptCuts: joint optimization of surface cuts and parameterization”
Conference:
Type(s):
Title:
- OptCuts: joint optimization of surface cuts and parameterization
Session/Category Title: Mapping + transport
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Low-distortion mapping of three-dimensional surfaces to the plane is a critical problem in geometry processing. The intrinsic distortion introduced by these UV mappings is highly dependent on the choice of surface cuts that form seamlines which break mapping continuity. Parameterization applications typically require UV maps with an application-specific upper bound on distortion to avoid mapping artifacts; at the same time they seek to reduce cut lengths to minimize discontinuity artifacts. We propose OptCuts, an algorithm that jointly optimizes the parameterization and cutting of a three-dimensional mesh. OptCuts starts from an arbitrary initial embedding and a user-requested distortion bound. It requires no parameter setting and automatically seeks to minimize seam lengths subject to satisfying the distortion bound of the mapping computed using these seams. OptCuts alternates between topology and geometry update steps that consistently decrease distortion and seam length, producing a UV map with compact boundaries that strictly satisfies the distortion bound. OptCuts automatically produces high-quality, globally bijective UV maps without user intervention. While OptCuts can thus be a highly effective tool to create new mappings from scratch, we also show how it can be employed to improve pre-existing embeddings. Additionally, when semantic or other priors on seam placement are desired, OptCuts can be extended to respect these user preferences as constraints during optimization of the parameterization. We demonstrate the scalable performance of OptCuts on a wide range of challenging benchmark parameterization examples, as well as in comparisons with state-of-the-art UV methods and commercial tools.
References:
1. Shmuel Agmon. 1954. The relaxation method for linear inequalities. Canadian Journal of Mathematics 6, 3 (1954), 382–392.Google ScholarCross Ref
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, Roi Poranne, and Yaron Lipman. 2015. Seamless Surface Mappings. ACM Trans. Graph. 34, 4 (2015), 72:1–72:13. Google ScholarDigital Library
4. Larry Armijo. 1966. Minimization of functions having Lipschitz continuous first partial derivatives. Pacific Journal of mathematics 16, 1 (1966), 1–3.Google Scholar
5. Dimitri P. Bertsekas. 2016. Nonlinear Programming. Athena Scientific.Google Scholar
6. S Claici, M Bessmeltsev, S Schaefer, and J Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 37–47. Google ScholarDigital Library
7. Michael S. Floater. 2003. Mean Value Coordinates. Comput. Aided Geom. Des. 20, 1 (March 2003), 19–27. Google ScholarDigital Library
8. Xianfeng Gu, Steven J Gortler, and Hugues Hoppe. 2002. Geometry images. ACM Transactions on Graphics (TOG) 21, 3 (2002). Google ScholarDigital Library
9. Kai Hormann and Günther Greiner. 2000. MIPS: An efficient global parametrization method. Technical Report.Google Scholar
10. Kai Hormann, Bruno Lévy, and Alla Sheffer. 2007. Mesh Parameterization: Theory and Practice. In SIGGRAPH 2007 Course Notes. ACM Press, San Diego, CA. Google ScholarDigital Library
11. Alec Jacobson, Daniele Panozzo, and others. 2017. libigl: A simple C++ geometry processing library. (2017). http://libigl.github.io/libigl/.Google Scholar
12. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial complex augmentation framework for bijective maps. ACM Transactions on Graphics (TOG) 36, 6 (2017), 186. Google ScholarDigital Library
13. Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-Charts: Quasi-Developable Mesh Segmentation. In Computer Graphics Forum, Vol. 24.Google ScholarCross Ref
14. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete Conformal Mappings via Circle Patterns. ACM Trans. Graph. 25, 2 (2006), 412–438. Google ScholarDigital Library
15. 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
16. Songrun Liu, Zachary Ferguson, Alec Jacobson, and Yotam Gingold. 2017. Seamless: Seam erasure and seam-aware decoupling of shape from mesh resolution. ACM Transactions on Graphics (TOG) 36, 6 (2017), 216:1–216:15. Google ScholarDigital Library
17. Ashish Myles and Denis Zorin. 2013. Controlled-distortion Constrained Global Parametrization. ACM Trans. Graph. 32, 4 (2013), 105:1–105:14. Google ScholarDigital Library
18. Cosmin G. Petra, Olaf Schenk, and Mihai Anitescu. 2014a. Real-time stochastic optimization of complex energy systems on high-performance computers. IEEE Computing in Science & Engineering 16, 5 (2014), 32–42.Google ScholarCross Ref
19. Cosmin G. Petra, Olaf Schenk, Miles Lubin, and Klaus Gärtner. 2014b. An augmented incomplete factorization approach for computing the Schur complement in stochastic optimization. SIAM Journal on Scientific Computing 36, 2 (2014), C139–C162.Google ScholarCross Ref
20. Roi Poranne, Marco Tarini, Sandro Huber, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Autocuts: Simultaneous Distortion and Cut Optimization for UV Mapping. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH ASIA) 36, 6 (2017). Google ScholarDigital Library
21. M.J.D. Powell. 1973. On Search Directions for Minimization Algorithms. Mathematical Programming 4 (1973).Google Scholar
22. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Transactions on Graphics 36, 2 (April 2017), 16:1–16:16. Google ScholarDigital Library
23. Nicolas Ray, Wan Chiu Li, Bruno Lévy, Alla Sheffer, and Pierre Alliez. 2006. Periodic Global Parameterization. ACM Trans. Graph. 25, 4 (2006), 1460–1485. Google ScholarDigital Library
24. Nicolas Ray, Vincent Nivoliers, Sylvain Lefebvre, and Bruno Lévy. 2010. Invisible seams. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1489–1496. Google ScholarDigital Library
25. James Reinders. 2007. Intel threading building blocks: outfitting C++ for multi-core processor parallelism. ” O’Reilly Media, Inc.”. Google ScholarDigital Library
26. Pedro V Sander, John Snyder, Steven J Gortler, and Hugues Hoppe. 2001. Texture mapping progressive meshes. In Proceedings of the 28th annual conference on Computer graphics and interactive techniques. ACM, 409–416. Google ScholarDigital Library
27. Rohan Sawhney and Keenan Crane. 2017. Boundary First Flattening. ACM Trans. Graph. 37, 1, Article 5 (Dec. 2017). Google ScholarDigital Library
28. Alla Sheffer and John C Hart. 2002. Seamster: inconspicuous low-distortion texture seam layout. In Proceedings of the conference on Visualization’02. Google ScholarDigital Library
29. Alla Sheffer, Bruno Lévy, Maxim Mogilnitsky, and Alexander Bogomyakov. 2005. ABF++: fast and robust angle based flattening. ACM Transactions on Graphics (TOG) 24, 2 (2005), 311–330. Google ScholarDigital Library
30. Alla Sheffer, Emil Praun, and Kenneth Rose. 2007. Mesh Parameterization Methods and Their Applications. Foundations and Trends® in Computer Graphics and Vision 2, 2 (2007), 105–171. Google ScholarDigital Library
31. Jonathan Richard Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Applied computational geometry towards geometric engineering. Springer, 203–222. Google ScholarDigital Library
32. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Transactions on Graphics (proceedings of ACM SIGGRAPH issue) 36, 4 (2017), 38:1–38:11. Google ScholarDigital Library
33. Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Transactions on Graphics (TOG) 34, 4 (2015). Google ScholarDigital Library
34. John Snyder, Pedro V Sander, Zoe J Wood, Steven Gortler, and Hugues Hoppe. 2003. Multi-chart geometry images. (2003).Google Scholar
35. Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, and Dani Lischinski. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of IEEE Visualization. IEEE Computer Society, 355–362. Google ScholarDigital Library
36. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation. Google ScholarDigital Library
37. William Thomas Tutte. 1963. How to draw a graph. Proceedings of the London Mathematical Society 3, 1 (1963), 743–767.Google ScholarCross Ref
38. Bruno Vallet and Bruno Lévy. 2009. What you seam is what you get. Technical Report.Google Scholar
