“Scalable Locally Injective Mappings” by Rabinovich, Poranne, Panozzo and Sorkine-Hornung
Conference:
Type(s):
Title:
- Scalable Locally Injective Mappings
Session/Category Title: Mappings and Deformations
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present a scalable approach for the optimization of flip-preventing energies in the general context of simplicial mappings and specifically for mesh parameterization. Our iterative minimization is based on the observation that many distortion energies can be optimized indirectly by minimizing a family of simpler proxy energies. Minimization of these proxies is a natural extension of the local/global minimization of the ARAP energy. Our algorithm is simple to implement and scales to datasets with millions of faces. We demonstrate our approach for the computation of maps that minimize a conformal or isometric distortion energy, both in two and three dimensions. In addition to mesh parameterization, we show that our algorithm can be applied to mesh deformation and mesh quality improvement.
References:
1. Noam Aigerman and Yaron Lipman. 2013. Injective and bounded distortion mappings in 3D. ACM Transactions on Graphics 32, 4, Article No. 106. DOI:http://dx.doi.org/10.1145/2461912.2461931 Google ScholarDigital Library
2. Noam Aigerman and Yaron Lipman. 2015. Orbifold Tutte embeddings. ACM Transactions on Graphics 34, 6, Article No. 190. DOI:http://dx.doi.org/10.1145/2816795.2818099 Google ScholarDigital Library
3. Noam Aigerman, Roi Poranne, and Yaron Lipman. 2014. Lifted bijections for low distortion surface mappings. ACM Transactions on Graphics 33, 4, Article No. 69. DOI:http://dx.doi.org/10.1145/2601097.2601158 Google ScholarDigital Library
4. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum 27, 2, 449–458. DOI:http://dx.doi.org/10.1111/j.1467-8659.2008.01142.x Google ScholarCross Ref
5. 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, Article No. 98. DOI:http://dx.doi.org/10.1145/2461912.2462014 Google ScholarDigital Library
6. David Bommes, Bruno Lévy, Nico Pietroni, Enrico Puppo, Claudio Silva, Marco Tarini, and Denis Zorin. 2012. State of the art in quad meshing. In Eurographics STARs. Eurographics.Google Scholar
7. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer quadrangulation. ACM Transactions on Graphics 28, 3, Article No. 77. DOI:http://dx.doi.org/10.1145/1531326.1531383 Google ScholarDigital Library
8. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-up: Shaping discrete geometry with projections. Computer Graphics Forum 31, 5, 1657–1667. Google ScholarDigital Library
9. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM Transactions on Graphics 33, 4, Article No. 154. DOI:http://dx.doi.org/10.1145/2601097.2601116 Google ScholarDigital Library
10. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM Transactions on Graphics 29, 4, Article No. 38. DOI:http://dx.doi.org/10.1145/1778765.1778775 Google ScholarDigital Library
11. Renjie Chen and Ofir Weber. 2015. Bounded distortion harmonic mappings in the plane. ACM Transactions on Graphics 34, 4, Article No. 73. DOI:http://dx.doi.org/10.1145/2766989 Google ScholarDigital Library
12. O. Civit-Flores and A. Susin. 2014. Robust treatment of degenerate elements in interactive corotational FEM simulations. Computer Graphics Forum 33, 6, 298–309. Google ScholarDigital Library
13. M. Desbrun, M. Meyer, and P. Alliez. 2002. Intrinsic parameterizations of surface meshes. Computer Graphics Forum 21, 3, 209–218. Google ScholarCross Ref
14. Olga Diamanti, Amir Vaxman, Daniele Panozzo, and Olga Sorkine-Hornung. 2015. Integrable polyvector fields. ACM Transactions on Graphics 34, 4, 38:1–38:12.Google ScholarDigital Library
15. Michael S. Floater. 2003. One-to-one piecewise linear mappings over triangulations. Mathematics of Computation 72, 242, 685–696. Google ScholarDigital Library
16. Michael S. Floater and Kai Hormann. 2005. Surface parameterization: A tutorial and survey. In Advances in Multiresolution for Geometric Modelling. Mathematics and Visualization Series. Springer, 157–186. DOI:http://dx.doi.org/10.1007/3-540-26808-1_9 Google ScholarCross Ref
17. Xiao-Ming Fu and Yang Liu. 2016. Computing inversion-free mappings by simplex assembly. ACM Transactions on Graphics 35, 6, Article No. 216. Google ScholarDigital Library
18. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Transactions on Graphics 34, 4, Article No. 71. DOI:http://dx.doi.org/10.1145/2766938 Google ScholarDigital Library
19. Mike Giles. 2008. An Extended Collection of Matrix Derivative Results for Forward and Reverse Mode Automatic Differentiation. Technical Report. Oxford University Computing Laboratory. http://eprints.maths.ox.ac.uk/1079/Google Scholar
20. K. Hormann and G. Greiner. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design. Vanderbilt University Press, Nashville, TN, 153–162.Google Scholar
21. G. Irving, J. Teran, and R. Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the Eurographics Symposium on Computer Animation. 131–140. DOI:http://dx.doi.org/10.1145/1028523.1028541 Google ScholarDigital Library
22. Alec Jacobson, Ilya Baran, Ladislav Kavan, Jovan Popović, and Olga Sorkine. 2012. Fast automatic skinning transformations. ACM Transactions on Graphics 31, 4, 77:1–77:10.Google ScholarDigital Library
23. Alec Jacobson, Daniele Panozzo, Christian Schuller, Olga Diamanti, Qingnan Zhou, Sebastian Koch, Amir Vaxman, et al. 2016. libigl: A Simple C++ Geometry Processing Library. Retrieved February 5, 2017, from http://libigl.github.io/libigl/.Google Scholar
24. Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2014. Controlling singular values with semidefinite programming. ACM Transactions on Graphics 33, 4, Article No. 68. Google ScholarDigital Library
25. Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman. 2015. Large-scale bounded distortion mappings. ACM Transactions on Graphics 34, 6, Article No. 191. DOI:http://dx.doi.org/10.1145/2816795.2818098 Google ScholarDigital Library
26. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated quadratic proxy for geometric optimization. ACM Transactions on Graphics 35, 4, 134. DOI:http://dx.doi.org/10.1145/2897824.2925920 Google ScholarDigital Library
27. A. Kuzmin, M. Luisier, and O. Schenk. 2013. Fast methods for computing selected elements of the Green’s function in massively parallel nanoelectronic device simulations. In Proceedings of the Euro-Par Conference. 533–544. DOI:http://dx.doi.org/10.1007/978-3-642-40047-6_54 Google ScholarDigital Library
28. U. Labsik, K. Hormann, and G. Greiner. 2000. Using most isometric parametrizations for remeshing polygonal surfaces. In Proceedings of the Geometric Modeling and Processing Conference. 220–228.Google Scholar
29. Zohar Levi and Denis Zorin. 2014. Strict minimizers for geometric optimization. ACM Transactions on Graphics 33, 6, Article No. 185. DOI:http://dx.doi.org/10.1145/2661229.2661258 Google ScholarDigital Library
30. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Transactions on Graphics 21, 3, 362–371. Google ScholarDigital Library
31. Yaron Lipman. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Transactions on Graphics 31, 4, Article No. 108. DOI:http://dx.doi.org/10.1145/2185520.2185604 Google ScholarDigital Library
32. Ligang Liu, Lei Zhang, Yin Xu, Craig Gotsman, and Steven J. Gortler. 2008. A local/global approach to mesh parameterization. In Proceedings of the Symposium on Geometry Processing. 1495–1504. http://dl.acm.org/citation.cfm?id=1731309.1731336Google ScholarDigital Library
33. Tiantian Liu, Ming Gao, Lifeng Zhu, Eftychios Sifakis, and Ladislav Kavan. 2016. Fast and robust inversion-free shape manipulation. Computer Graphics Forum 35, 2, 1–11. Google ScholarDigital Library
34. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based elastic materials. ACM Transactions on Graphics 30, 4, 72:1–72:8.Google ScholarDigital Library
35. Tobias Martin, Pushkar Joshi, Miklós Bergou, and Nathan Carr. 2013. Efficient non-linear optimization via multi-scale gradient filtering. Computer Graphics Forum 32, 6, 89–100. DOI:http://dx.doi.org/10.1111/cgf.12019 Google ScholarDigital Library
36. Janick Martinez Esturo, Christian Rössl, and Holger Theisel. 2014. Smoothed quadratic energies on meshes. ACM Transactions on Graphics 34, 1, Article No. 2. Google ScholarDigital Library
37. Patrick Mullen, Yiying Tong, Pierre Alliez, and Mathieu Desbrun. 2008. Spectral conformal parameterization. In Proceedings of the Symposium on Geometry Processing. 1487–1494. http://dl.acm.org/citation.cfm?id=1731309.1731335Google ScholarCross Ref
38. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust field-aligned global parametrization. ACM Transactions on Graphics 33, 4, Article No. 135. DOI:http://dx.doi.org/10.1145/2601097.2601154 Google ScholarDigital Library
39. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Transactions on Graphics 31, 4, 109:1–109:11.Google ScholarDigital Library
40. Jorge Nocedal and Steve J. Wright. 2006. Numerical Optimization. Springer, Berlin, Germany. http://opac.inria.fr/record=b1120179 NEOS guide http://www-fp.mcs.anl.gov/otc/Guide/.Google Scholar
41. Fred Pighin and John P. Lewis. 2007. Practical least-squares for computer graphics. In Proceedings of the ACM SIGGRAPH 2007 Courses (SIGGRAPH’07). 1–57. Google ScholarDigital Library
42. Roi Poranne, Elena Ovreiu, and Craig Gotsman. 2013. Interactive planarization and optimization of 3D meshes. Computer Graphics Forum 32, 1, 152–163. Google ScholarCross Ref
43. Michael Rabinovich. 2016. Scalable Locally Injective Mappings. Retrieved February 5, 2017, from https://github.com/MichaelRabinovich/Scalable-Locally-Injective-Mappings.Google Scholar
44. Patrick David Sanan. 2014. Geometric Elasticity for Graphics, Simulation, and Computation. Ph.D. Dissertation. California Institute of Technology.Google Scholar
45. Olaf Schenk, Matthias Bollhöfer, and Rudolf A. Römer. 2008. On large-scale diagonalization techniques for the Anderson model of localization. SIAM Review 50, 1, 91–112. DOI:http://dx.doi.org/10.1137/070707002 Google ScholarDigital Library
46. Olaf Schenk, Andreas Wachter, and Michael Hagemann. 2007. Matching-based preprocessing algorithms to the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Computational Optimization and Applications 36, 2-3, 321–341. DOI:http://dx.doi.org/10.1007/s10589-006-9003-y Google ScholarDigital Library
47. John Schreiner, Arul Asirvatham, Emil Praun, and Hugues Hoppe. 2004. Inter-surface mapping. ACM Transactions on Graphics 23, 3, 8. DOI:http://dx.doi.org/10.1145/1015706.1015812 Google ScholarDigital Library
48. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally injective mappings. Computer Graphics Forum 32, 5, 125–135. Google ScholarDigital Library
49. A. Sheffer and E. de Sturler. 2001. Parameterization of faceted surfaces for meshing using angle-based flattening. Engineering with Computers 17, 3, 326–337. DOI:http://dx.doi.org/10.1007/PL00013391 Google ScholarCross Ref
50. Alla Sheffer, Bruno Lévy, Maxim Mogilnitsky, and Alexander Bogomyakov. 2005. ABF++: Fast and robust angle based flattening. ACM Transactions on Graphics 24, 2, 311–330. Google ScholarDigital Library
51. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh parameterization methods and their applications. Foundations and Trends in Computer Graphics and Vision 2, 2, 105–171. DOI:http://dx.doi.org/10.1561/0600000011 Google ScholarDigital Library
52. Jason Smith and Scott Schaefer. 2015. Bijective parameterization with free boundaries. ACM Transactions on Graphics 34, 4, Article No. 70. DOI:http://dx.doi.org/10.1145/2766947 Google ScholarDigital Library
53. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Proceedings of the Symposium on Geometry Processing. 109–116. http://dl.acm.org/citation.cfm?id=1281991.1282006Google Scholar
54. 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 (SCA’05). ACM, New York, NY, 181–190. DOI:http://dx.doi.org/10.1145/1073368.1073394 Google ScholarDigital Library
55. W. T. Tutte. 1963. How to draw a graph. Proceedings of the London Mathematical Society 13, 743–767. http://www.ams.org/mathscinet-getitem?mr=28:1610 Google ScholarCross Ref
56. Ofir Weber, Ashish Myles, and Denis Zorin. 2012. Computing extremal quasiconformal maps. Computer Graphics Forum 31, 5, 11. DOI:http://dx.doi.org/10.1111/j.1467-8659.2012.03173.x Google ScholarDigital Library
57. Shin Yoshizawa, Alexander Belyaev, and Hans-Peter Seidel. 2004. A fast and simple stretch-minimizing mesh parameterization. In Proceedings of Shape Modeling International 2004 (SMI’04). IEEE, Los Alamitos, CA, 200–208. DOI:http://dx.doi.org/10.1109/SMI.2004.2Google ScholarDigital Library
58. Rhaleb Zayer, Bruno Lévy, and Hans-Peter Seidel. 2007. Linear angle based parameterization. In Proceedings of the 5th Eurographics Symposium on Geometry Processing (SGP’07). 135–141. http://dl.acm.org/citation.cfm?id=1281991.1282010Google Scholar
