“Atlas refinement with bounded packing efficiency” by Liu, Fu, Ye, Chai and Liu

  • ©Hao-Yu Liu, Xiao-Ming Fu, Chunyang Ye, Shuangming Chai, and Ligang Liu




    Atlas refinement with bounded packing efficiency

Session/Category Title:   Shape Science



    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.


    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

ACM Digital Library Publication:

Overview Page: