“Simplicial complex augmentation framework for bijective maps”
Conference:
Type(s):
Title:
- Simplicial complex augmentation framework for bijective maps
Session/Category Title: Volumes
Presenter(s)/Author(s):
Abstract:
Bijective maps are commonly used in many computer graphics and scientific computing applications, including texture, displacement, and bump mapping. However, their computation is numerically challenging due to the global nature of the problem, which makes standard smooth optimization techniques prohibitively expensive. We propose to use a scaffold structure to reduce this challenging and global problem to a local injectivity condition. This construction allows us to benefit from the recent advancements in locally injective maps optimization to efficiently compute large scale bijective maps (both in 2D and 3D), sidestepping the need to explicitly detect and avoid collisions. Our algorithm is guaranteed to robustly compute a globally bijective map, both in 2D and 3D. To demonstrate the practical applicability, we use it to compute globally bijective single patch parametrizations, to pack multiple charts into a single UV domain, to remove self-intersections from existing models, and to deform 3D objects while preventing self-intersections. Our approach is simple to implement, efficient (two orders of magnitude faster than competing methods), and robust, as we demonstrate in a stress test on a parametrization dataset with over a hundred meshes.
References:
1. 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.
2. Samantha Ainsley, Etienne Vouga, Eitan Grinspun, and Rasmus Tamstorf. 2012. Speculative Parallel Asynchronous Contact Mechanics. ACM Trans. Graph. 31, 6, Article 151 (2012), 8 pages.
3. 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.
4. David Bommes, Henrik Zimmer, and Leif Kobbelt. 2009. Mixed-integer Quadrangulation. ACM Trans. Graph. 28, 3, Article 77 (July 2009), 10 pages.
5. 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.
6. P. Degener, J. Meseth, and R. Klein. 2003. An Adaptable Surface Parameterization Method. In Proceedings of the 12th International Meshing Roundtable. 201–213.
7. Randall Dougherty, Vance Faber, and Michael Murphy. 2004. Unflippable Tetrahedral Complexes. Discrete & Computational Geometry 32, 3 (01 Sep 2004), 309–315.
8. Michael S. Floater. 1997. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design 14 (1997), 231–250.
9. 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.
10. 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.
11. 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.
12. Craig Gotsman and Vitaly Surazhsky. 2001. Guaranteed intersection-free polygon morphing. Computers & Graphics 25, 1 (2001), 67–75. Cross Ref
13. David Harmon. 2010. Robust, efficient, and accurate contact algorithms. Ph.D. Dissertation. Columbia University.
14. David Harmon, Daniele Panozzo, Olga Sorkine, and Denis Zorin. 2011. Interference-aware Geometric Modeling. ACM Trans. Graph. 30, 6, Article 137 (Dec. 2011), 10 pages.
15. David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun. 2009. Asynchronous Contact Mechanics. ACM Trans. Graph. 28, 3, Article 87 (July 2009), 12 pages.
16. K. Hormann and G. Greiner. 2000. MIPS: An Efficient Global Parametrization Method. In Curve and Surface Design: Saint-Malo 1999. 153–162.
17. 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.
18. Alec Jacobson, Daniele Panozzo, et al. 2014. libigl: A simple C++ geometry processing library. (2014). http://igl.ethz.ch/projects/libigl/.
19. P. Jimenez, F. Thomas, and C. Torras. 2001. 3D collision detection: a survey. Computers & Graphics 25, 2 (2001), 269 — 285. Cross Ref
20. Michael Kazhdan, Jake Solomon, and Mirela Ben-Chen. 2012. Can Mean-Curvature Flow Be Modified to Be Non-singular? Comput. Graph. Forum 31, 5 (Aug. 2012), 1745–1754.
21. Bryan Matthew Klingner. 2009. Tetrahedral mesh improvement. Ph.D. Dissertation. University of California at Berkeley.
22. 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.
23. 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.
24. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4 (2012), 108:1–108:13.
25. Yaron Lipman. 2013. Construction of Injective Mappings Of Meshes. CoRR abs/1310.0955 (2013). http://arxiv.org/abs/1310.0955
26. 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 (SGP ’08). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1495–1504.
27. Marek Krzysztof Misztal and Jakob Andreas Bærentzen. 2012. Topology-adaptive Interface Tracking Using the Deformable Simplicial Complex. ACM Trans. Graph. 31, 3, Article 24 (June 2012), 12 pages.
28. 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.
29. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (July 2014), 14 pages.
30. Kazim Pal, Christian Schüller, Daniele Panozzo, Olga Sorkine-Hornung, and Tim Weyrich. 2014. Content-Aware Surface Parameterization for Interactive Restoration of Historical Documents. Computer Graphics Forum (proceedings of EUROGRAPHICS issue) 33, 2 (2014).
31. Roi Poranne and Yaron Lipman. 2014. Provably Good Planar Mappings. ACM Trans. Graph. 33, 4 (2014), 76:1–76:11.
32. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Mappings. ACM Trans. Graph. 36, 2, Article 16 (2017), 16 pages.
33. Leonardo Sacht, Alec Jacobson, Daniele Panozzo, Christian Schüller, and Olga Sorkine-Hornung. 2013. Consistent Volumetric Discretizations Inside Self-Intersecting Surfaces. Computer Graphics Forum (proceedings of EUROGRAPHICS/ACM SIGGRAPH Symposium on Geometry Processing) 32, 5 (2013), 147–156.
34. Pedro V. Sander, John Snyder, Steven J. Gortler, and Hugues Hoppe. 2001. Texture Mapping Progressive Meshes. In ACM SIGGRAPH. 409–416.
35. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. In Symposium on Geometry Processing. 125–135.
36. Alla Sheffer, Emil Praun, and Kenneth Rose. 2006. Mesh Parameterization Methods and Their Applications. Found. Trends. Comput. Graph. Vis. 2, 2 (2006), 105–171.
37. Jonathan Shewchuk. 1996. Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. Applied computational geometry towards geometric engineering (1996), 203–222.
38. Hang Si. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Transactions on Mathematical Software (TOMS) 41, 2 (2015), 11.
39. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (July 2015), 9 pages.
40. Justin Solomon. 2015. Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics. A. K. Peters, Ltd., Natick, MA, USA. Cross Ref
41. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible Surface Modeling. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing (SGP ’07). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 109–116.
42. 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.
43. Vitaly Surazhsky and Craig Gotsman. 2001. Morphing stick figures using optimized compatible triangulations. In Computer Graphics and Applications, 2001. Proceedings. Ninth Pacific Conference on. IEEE, 40–49.
44. W. T. Tutte. 1963. How to drawa Graph. Proceedings of the London Mathematical Society 13, 3 (1963), 743–768. Cross Ref
45. Ofir Weber and Denis Zorin. 2014. Locally Injective Parametrization with Arbitrary Fixed Boundaries. ACM Trans. Graph. 33, 4, Article 75 (July 2014), 12 pages.
46. Eugene Zhang, Konstantin Mischaikow, and Greg Turk. 2005. Feature-based Surface Parameterization and Texture Mapping. ACM Trans. Graph. 24, 1 (Jan. 2005), 1–27.
47. Kun Zhou, John Synder, Baining Guo, and Heung-Yeung Shum. 2004. Iso-charts: Stretch-driven Mesh Parameterization Using Spectral Analysis. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP ’04). ACM, New York, NY, USA, 45–54.
