“Atlas refinement with bounded packing efficiency” by Liu, Fu, Ye, Chai and Liu
Conference:
Type(s):
Title:
- Atlas refinement with bounded packing efficiency
Session/Category Title: Shape Science
Presenter(s)/Author(s):
Abstract:
We present a novel algorithm to refine an input atlas with bounded packing efficiency. Central to this method is the use of the axis-aligned structure that converts the general polygon packing problem to a rectangle packing problem, which is easier to achieve high packing efficiency. Given a parameterized mesh with no flipped triangles, we propose a new angle-driven deformation strategy to transform it into a set of axis-aligned charts, which can be decomposed into rectangles by the motorcycle graph algorithm. Since motorcycle graphs are not unique, we select the one balancing the trade-off between the packing efficiency and chart boundary length, while maintaining bounded packing efficiency. The axis-aligned chart often contains greater distortion than the input, so we try to reduce the distortion while bounding the packing efficiency and retaining bijection. We demonstrate the efficacy of our method on a data set containing over five thousand complex models. For all models, our method is able to produce packed atlases with bounded packing efficiency; for example, when the packing efficiency bound is set to 80%, we elongate the boundary length by an average of 78.7% and increase the distortion by an average of 0.0533%. Compared to state-of-the-art methods, our method is much faster and achieves greater packing efficiency.
References:
1. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal flattening by curvature prescription and metric scaling. In Comput. Graph. Forum, Vol. 27. 449–458.Google ScholarCross Ref
2. Marcel Campen. 2017. Partitioning surfaces into quadrilateral patches: a survey. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 567–588. Google ScholarDigital Library
3. Nathan A. Carr and John C. Hart. 2002. Meshed Atlases for Real-time Procedural Solid Texturing. ACM Trans. Graph. 21, 2 (2002), 106–131. Google ScholarDigital Library
4. Nathan A. Carr, Jared Hoberock, Keenan Crane, and John C. Hart. 2006. Rectangular multi-chart geometry images. In Proceedings of the fourth Eurographics symposium on Geometry processing. Google ScholarDigital Library
5. Shuangming Chai, Xiao-Ming Fu, Xin Hu, Yang Yang, and Ligang Liu. 2018. Sphere-based Cut Construction for Planar Parameterizations. Computer & Graphics (SMI 2018) 74 (2018), 66–75.Google Scholar
6. Chin-Chen Chang and Chen-Yu Lin. 2010. Texture tiling on 3D models using automatic PolyCube-maps and wang tiles. Journal of Information Science and Engineering 26, 1 (2010), 291–305.Google Scholar
7. S Claici, M Bessmeltsev, S Schaefer, and J Solomon. 2017. Isometry-Aware Preconditioning for Mesh Parameterization. Comput. Graph. Forum (SGP) 36, 5 (2017), 37–47. Google ScholarDigital Library
8. David Eppstein, Michael T. Goodrich, Ethan Kim, and Rasmus Tamstorf. 2008. Motorcycle Graphs: Canonical Quad Mesh Partitioning. Comput. Graph. Forum (SGP) 27, 5 (2008), 1477–1486. Google ScholarDigital Library
9. Xianzhong Fang, Weiwei Xu, Hujun Bao, and Jin Huang. 2016. All-hex meshing using closed-form induced Polycube. ACM Trans. Graph. (SIGGRAPH) 35, 4 (2016), 124:1–124:9. Google ScholarDigital Library
10. Michael S. Floater. 2003. One-to-one piecewise linear mappings over triangulations. Math. Comput. 72 (2003), 685–696. Google ScholarDigital Library
11. Michael S. Floater and Kai Hormann. 2005. Surface parameterization: a tutorial and survey. In In Advances in Multiresolution for Geometric Modelling. Springer, 157–186.Google Scholar
12. Xiao-Ming Fu, Chong-Yang Bai, and Yang Liu. 2016. Efficient Volumetric PolyCube-Map Construction. Computer Graphics Forum (Pacific Graphics) 35, 7 (2016). Google ScholarDigital Library
13. Xiao-Ming Fu and Yang Liu. 2016. Computing inversion-free mappings by simplex assembly. ACM Trans. Graph. (SIGGRAPH ASIA) 35, 6 (2016), 216:1–216:12. Google ScholarDigital Library
14. Xiao-Ming Fu, Yang Liu, and Baining Guo. 2015. Computing locally injective mappings by advanced MIPS. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 71:1–71:12. Google ScholarDigital Library
15. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. Google ScholarDigital Library
16. Björn Golla, Hans-Peter Seidel, and Renjie Chen. 2018. Piecewise linear mapping optimization based on the complex view. 37, 7 (2018), 233–243.Google Scholar
17. James Gregson, Alla Sheffer, and Eugene Zhang. 2011. All-Hex mesh generation via volumetric PolyCube deformation. Comput. Graph. Forum (SGP) 30 (2011), 1407–1416.Google ScholarCross Ref
18. Xianfeng Gu, Steven J. Gortler, and Hugues Hoppe. 2002. Geometry Images. ACM Trans. Graph. (SIGGRAPH) 21, 3 (2002), 355–361. Google ScholarDigital Library
19. Ziyad S. Hakura and Anoop Gupta. 1997. The Design and Analysis of a Cache Architecture for Texture Mapping. SIGARCH Comput. Archit. News 25, 2 (1997), 108–120. Google ScholarDigital Library
20. K. Hormann and G. Greiner. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153–162.Google Scholar
21. Kai Hormann, Bruno Lévy, and Alla Sheffer. 2007. Mesh Parameterization: Theory and Practice. In ACM SIGGRAPH 2007 Courses (SIGGRAPH ’07). Google ScholarDigital Library
22. Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun. 2014. l1-based construction of PolyCube maps from complex shapes. ACM Trans. Graph. 33, 3 (2014), 25:1–25:11. Google ScholarDigital Library
23. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. (SIGGRAPH ASIA) 36, 6 (2017), 186:1–186:9. Google ScholarDigital Library
24. Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-Charts: Quasi-Developable Mesh Segmentation. In Comput. Graph. Forum, Vol. 24. 581–590.Google ScholarCross Ref
25. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete conformal mappings viacircle patterns. ACM Trans. Graph. 25, 2 (2006), 412–438. Google ScholarDigital Library
26. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated Quadratic Proxy for Geometric Optimization. ACM Trans. Graph. (SIGGRAPH) 35, 4 (2016), 134:1–134:11. Google ScholarDigital Library
27. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least squares con-formal maps for automatic texture atlas generation. ACM Trans. Graph. (SIGGRAPH) 21, 3 (2002), 362–371. Google ScholarDigital Library
28. Minchen Li, Danny M. Kaufman, Vladimir G. Kim, Justin Solomon, and Alla Sheffer. 2018. OptCuts: Joint Optimization of Surface Cuts and Parameterization. ACM Trans. Graph. (SIGGRAPH ASIA) 37, 6 (2018). Google ScholarDigital Library
29. Max Limper, Nicholas Vining, and Alla Sheffer. 2018. Box Cutter: Atlas Refinement for Efficient Packing via Void Elimination. ACM Trans. Graph. (SIGGRAPH) 37, 4 (2018), 153:1–153:13. Google ScholarDigital Library
30. Celong Liu, Wuyi Yu, Zhonggui Chen, and Xin Li. 2017. Distributed poly-square mapping for large-scale semi-structured quad mesh generation. Computer Aided Design 90 (2017), 5 — 17.Google ScholarCross Ref
31. Ligang Liu, Chunyang Ye, Ruiqi Ni, and Xiao-Ming Fu. 2018. Progressive Parameterizations. ACM Trans. Graph. (SIGGRAPH) 37, 4 (2018), 41:1–41:12. Google ScholarDigital Library
32. Marco Livesu, Nicholas Vining, Alla Sheffer, James Gregson, and Riccardo Scateni. 2013. Polycut: monotone graph-cuts for PolyCube base-complex construction. ACM Trans. Graph. (SIGGRAPH ASIA) 32, 6 (2013), 171:1–171:12. Google ScholarDigital Library
33. Victor J. Milenkovic. 1999. Rotational Polygon Containment and Minimum Enclosure Using Only Robust 2D Constructions. Comput. Geom. Theory Appl. 13, 1 (1999), 3–19. Google ScholarDigital Library
34. Ashish Myles and Denis Zorin. 2012. Global Parametrization by Incremental Flattening. ACM Trans. Graph. (SIGGRAPH) 31, 4 (2012), 109:1–109:11. Google ScholarDigital Library
35. Tobias Nöll and D Strieker. 2011. Efficient packing of arbitrary shaped charts for automatic texture atlas generation. Comput. Graph. Forum 30, 4 (2011), 1309–1317. Google ScholarDigital Library
36. 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. (SIGGRAPH ASIA) 36, 6 (2017), 215:1–215:11. Google ScholarDigital Library
37. Fabián Prada, Misha Kazhdan, Ming Chuang, and Hugues Hoppe. 2018. Gradient-domain Processing Within a Texture Atlas. ACM Trans. Graph. (SIGGRAPH) 37, 4 (2018), 154:1–154:14. Google ScholarDigital Library
38. Budirijanto Purnomo, Jonathan D. Cohen, and Subodh Kumar. 2004. Seamless Texture Atlases. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 65–74. Google ScholarDigital Library
39. Michael Rabinovich, Roi Poranne, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Scalable Locally Injective Maps. ACM Trans. Graph. 36, 2 (2017). Google ScholarDigital Library
40. Pedro V. Sander, Steven J. Gortler, John Snyder, and Hugues Hoppe. 2002. Signal-specialized Parametrization. In Proceedings of the 13th Eurographics Workshop on Rendering. 87–98. Google ScholarDigital Library
41. Pedro V. Sander, John Snyder, Steven J. Gortler, and Hugues Hoppe. 2001. Texture mapping progressive meshes. In SIGGRAPH. 409–416. Google ScholarDigital Library
42. P. V. Sander, Z. J. Wood, S. J. Gortler, J. Snyder, and H. Hoppe. 2003. Multi-chart Geometry Images. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 146–155. Google ScholarDigital Library
43. Christian Schüller, Ladislav Kavan, Daniele Panozzo, and Olga Sorkine-Hornung. 2013. Locally Injective Mappings. Comput. Graph. Forum (SGP) 32, 5 (2013), 125–135. Google ScholarDigital Library
44. Alla Sheffer. 2002. Spanning tree seams for reducing parameterization distortion of triangulated surfaces. In Shape Modeling International. 61–66. Google ScholarDigital Library
45. Alla Sheffer and John C Hart. 2002. Seamster: inconspicuous low-distortion texture seam layout. In Proceedings of the conference on Visualization’02. 291–298. Google ScholarDigital Library
46. 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
47. Anna Shtengel, Roi Poranne, Olga Sorkine-Hornung, Shahar Z. Kovalsky, and Yaron Lipman. 2017. Geometric Optimization via Composite Majorization. ACM Trans. Graph. (SIGGRAPH) 36, 4 (2017), 38:1–38:11. Google ScholarDigital Library
48. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015), 70:1–70:9. Google ScholarDigital Library
49. Yousuf Soliman, Dejan Slepčev, and Keenan Crane. 2018. Optimal Cone Singularities for Conformal Flattening. ACM Trans. Graph. (SIGGRAPH) 37, 4 (2018), 105:1–105:17. Google ScholarDigital Library
50. Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, and Dani Lischinski. 2002. Bounded-distortion piecewise mesh parameterization. In Proceedings of the Conference on Visualization ’02. 355–362. Google ScholarDigital Library
51. Boris Springborn, Peter Schröder, and Ulrich Pinkall. 2008. Conformal equivalence of triangle meshes. ACM Trans. Graph. (SIGGRAPH) 27, 3 (2008), 77:1–77:11. Google ScholarDigital Library
52. Marco Tarini, Kai Hormann, Paolo Cignoni, and Claudio Montani. 2004. PolyCube-Maps. ACM Trans. Graph. (SIGGRAPH) 23, 3 (2004), 853–860. Google ScholarDigital Library
53. TeamHypersomnia. 2016–2018. rectpack2D. https://github.com/TeamHypersomnia/rectpack2D.Google Scholar
54. W. T. Tutte. 1963. How to draw a graph. In Proceedings of the London Mathematical Society, Vol. 13. 747–767.Google Scholar
55. Jiazhil Xia, Ismael Garcia, Ying He, Shi-Qing Xin, and Gustavo Patow. 2011. Editable polycube map for GPU-based subdivision surfaces. In Symp. on Interactive 3D Graphics and Games. 151–158. Google ScholarDigital Library
56. Shiwei Xiao, Hongmei Kang, Xiao-Ming Fu, and Falai Chen. 2018. Computing IGA-suitable Planar Parameterizations by PolySquare-enhanced Domain Partition. Comput. Aided Geom. Des. 62 (2018), 29–43.Google ScholarCross Ref
57. Chih-Yuan Yao and Tong-Yee Lee. 2008. Adaptive geometry image. IEEE. T. Vis. Comput. Gr. 14, 4 (2008), 948–960. Google ScholarDigital Library
58. Wuyi Yu, Kang Zhang, Shenghua Wan, and Xin Li. 2014. Optimizing Polycube domain construction for hexahedral remeshing. Computer Aided Design 46 (2014), 58–68. Google ScholarDigital Library
59. Eugene Zhang, Konstantin Mischaikow, and Greg Turk. 2005. Feature-based surface parameterization and texture mapping. ACM Transactions on Graphics (TOG) 24, 1 (2005),1–27. Google ScholarDigital Library
60. 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. 45–54. Google ScholarDigital Library
61. Yufeng Zhu, Robert Bridson, and Danny M. Kaufman. 2018. Blended Cured Quasi-newton for Distortion Optimization. ACM Trans. Graph. (SIGGRAPH) 37, 4 (2018), 40:1–40:14. Google ScholarDigital Library