“Box cutter: atlas refinement for efficient packing via void elimination” by Limper, Vining and Sheffer

  • ©Max Limper, Nicholas Vining, and Alla Sheffer



Entry Number: 153


    Box cutter: atlas refinement for efficient packing via void elimination

Session/Category Title: An Atlas for the World and Other Surfaces




    Packed atlases, consisting of 2D parameterized charts, are ubiquitously used to store surface signals such as texture or normals. Tight packing is similarly used to arrange and cut-out 2D panels for fabrication from sheet materials. Packing efficiency, or the ratio between the areas of the packed atlas and its bounding box, significantly impacts downstream applications.We propose Box Cutter, a new method for optimizing packing efficiency suitable for both settings. Our algorithm improves packing efficiency without changing distortion by strategically cutting and repacking the atlas charts or panels. It preserves the local mapping between the 3D surface and the atlas charts and retains global mapping continuity across the newly formed cuts. We balance packing efficiency improvement against increase in chart boundary length and enable users to directly control the acceptable amount of boundary elongation. While the problem we address is NP-hard, we provide an effective practical solution by iteratively detecting large rectangular empty spaces, or void boxes, in the current atlas packing and eliminating them by first refining the atlas using strategically placed axis-aligned cuts and then repacking the refined charts. We repeat this process until no further improvement is possible, or until the desired balance between packing improvement and boundary elongation is achieved. Packed chart atlases are only useful for the applications we address if their charts are overlap-free; yet many popular parameterization methods, used as-is, produce atlases with global overlaps. Our pre-processing step eliminates all input overlaps while explicitly minimizing the boundary length of the resulting overlap-free charts. We demonstrate our combined strategy on a large range of input atlases produced by diverse parameterization methods, as well as on multiple sets of 2D fabrication panels. Our framework dramatically improves the output packing efficiency on all inputs; for instance with boundary length increase capped at 50% we improve packing efficiency by 68% on average.


    1. Mirela Ben-Chen, Craig Gotsman, and Guy Bunin. 2008. Conformal Flattening by Curvature Prescription and Metric Scaling. Computer Graphics Forum 27, 2 (2008), 449–458.Google ScholarCross Ref
    2. 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. Google ScholarDigital Library
    3. Mario Botsch, Leif Kobbelt, Mark Pauly, Pierre Alliez, and Bruno LÃl’vy. 2010. Polygon Mesh Processing. AK Peters. 250 pages.Google Scholar
    4. Alon Bright, Edward Chien, and Ofir Weber. 2017. Harmonic Global Parametrization with Rational Holonomy. ACM Trans. Graph. 36, 4, Article 89 (July 2017), 15 pages. Google ScholarDigital Library
    5. Nathan A. Carr and John C. Hart. 2002. Meshed Atlases for Real-time Procedural Solid Texturing. ACM Trans. Graph. 21, 2 (April 2002), 106–131. Google ScholarDigital Library
    6. Xuelin Chen, Hao Zhang, Jinjie Lin, Ruizhen Hu, Lin Lu, Qixing Huang, Bedrich Benes, Daniel Cohen-Or, and Baoquan Chen. 2015. Dapper: Decompose-and-pack for 3D Printing. ACM Trans. Graph. 34, 6, Article 213 (Oct. 2015), 12 pages. Google ScholarDigital Library
    7. David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2004. Variational Shape Approximation. In ACM SIGGRAPH 2004 Papers (SIGGRAPH ’04). ACM, New York, NY, USA, 905–914. Google ScholarDigital Library
    8. Daniel Sanchez-Crespo Dalmau. 2003. Core Techniques and Algorithms in Game Programming. New Riders Games. Google ScholarDigital Library
    9. Michael S. Floater. 1997. Parametrization and Smooth Approximation of Surface Triangulations. Comput. Aided Geom. Des. 14, 3 (April 1997), 231–250. Google ScholarDigital Library
    10. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA. Google ScholarDigital Library
    11. Francisco González and Gustavo Patow. 2009. Continuity Mapping for Multi-chart Textures. ACM Trans. Graph. 28, 5 (2009), 109:1–109:8. Google ScholarDigital Library
    12. Xianfeng Gu, Steven J. Gortler, and Hugues Hoppe. 2002. Geometry Images. In Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’02). ACM, New York, NY, USA, 355–361. Google ScholarDigital Library
    13. Ziyad S. Hakura and Anoop Gupta. 1997. The Design and Analysis of a Cache Architecture for Texture Mapping. In Proceedings of the 24th Annual International Symposium on Computer Architecture (ISCA ’97). ACM, New York, NY, USA, 108–120. Google ScholarDigital Library
    14. K. Hormann, B. Lévy, and A. Sheffer. 2007. Mesh Parameterization: Theory and Practice. In SIGGRAPH 2007 Course Notes. ACM Press, San Diego, CA, vi+115. Google ScholarDigital Library
    15. Zhongshi Jiang, Scott Schaefer, and Daniele Panozzo. 2017. Simplicial Complex Augmentation Framework for Bijective Maps. ACM Trans. Graph. 36, 6 (2017), 186:1–186:9. Google ScholarDigital Library
    16. M. Jin, Y. Wang, S. T. Yau, and X. Gu. 2004. Optimal global conformal surface parameterization. In IEEE Visualization 2004. 267–274. Google ScholarDigital Library
    17. Dan Julius, Vladislav Kraevoy, and Alla Sheffer. 2005. D-Charts: Quasi-Developable Mesh Segmentation. Computer Graphics Forum 24, 3 (2005), 581–590.Google ScholarCross Ref
    18. B. W. Kernighan and S. Lin. 1970. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal 49, 2 (Feb 1970), 291–307.Google ScholarCross Ref
    19. Margret Keuper, Evgeny Levinkov, Nicolas Bonneel, Guillaume Lavoue, Thomas Brox, and Bjorn Andres. 2015. Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts. In The IEEE International Conference on Computer Vision (ICCV). Google ScholarDigital Library
    20. Liliya Kharevych, Boris Springborn, and Peter Schröder. 2006. Discrete Conformal Mappings via Circle Patterns. ACM Trans. Graph. 25, 2 (April 2006), 412–438. Google ScholarDigital Library
    21. B. Koo, J. Hergel, S. Lefebvre, and N. J. Mitra. 2017. Towards Zero-Waste Furniture Design. IEEE Transactions on Visualization and Computer Graphics 23, 12 (Dec 2017), 2627–2640.Google ScholarCross Ref
    22. Zohar Levi and Denis Zorin. 2014. Strict Minimizers for Geometric Optimization. ACM Trans. Graph. 33, 6, Article 185 (Nov. 2014), 14 pages. Google ScholarDigital Library
    23. Bruno Lévy, Sylvain Petitjean, Nicolas Ray, and Jérome Maillot. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. In Proceedings of the 29th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’02). ACM, New York, NY, USA, 362–371. Google ScholarDigital Library
    24. Yaron Lipman. 2012. Bounded Distortion Mapping Spaces for Triangular Meshes. ACM Trans. Graph. 31, 4, Article 108 (July 2012), 13 pages. Google ScholarDigital Library
    25. Songrun Liu, Zachary Ferguson, Alec Jacobson, and Yotam Gingold. 2017. Seamless: Seam erasure and seam-aware decoupling of shape from mesh resolution. ACM Trans. Graph. 36, 6 (2017), 216:1–216:15. Google ScholarDigital Library
    26. Victor J. Milenkovic. 1999. Rotational polygon containment and minimum enclosure using only robust 2D constructions. Computational Geometry 13, 1 (1999), 3 — 19. Google ScholarDigital Library
    27. Jacob Munkberg, Jon Hasselgren, Petrik Clarberg, Magnus Andersson, and Tomas Akenine-Möller. 2016. Texture Space Caching and Reconstruction for Ray Tracing. ACM Trans. Graph. 35, 6, Article 249 (Nov. 2016), 13 pages. Google ScholarDigital Library
    28. Ashish Myles, Nico Pietroni, and Denis Zorin. 2014. Robust Field-aligned Global Parametrization. ACM Trans. Graph. 33, 4, Article 135 (July 2014), 14 pages. Google ScholarDigital Library
    29. Ashish Myles and Denis Zorin. 2012. Global parametrization by incremental flattening. ACM Trans. Graph. 31, 4, Article 109 (July 2012), 11 pages. Google ScholarDigital Library
    30. Tobias Nöll and Didier Stricker. 2011. Efficient Packing of Arbitrarily Shaped Charts for Automatic Texture Atlas Generation. In Proceedings of the Twenty-second Eurographics Conference on Rendering (EGSR ’11). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1309–1317. Google ScholarDigital Library
    31. Roi Poranne, Marco Tarini, Sandro Huber, Daniele Panozzo, and Olga Sorkine-Hornung. 2017. Autocuts: Simultaneous Distortion and Cut Optimization for UV Mapping.Google ScholarDigital Library
    32. Budirijanto Purnomo, Jonathan D. Cohen, and Subodh Kumar. 2004. Seamless Texture Atlases. In Proc. Symp. Geometry Processing. 65–74. Google ScholarDigital Library
    33. Nicolas Ray, Vincent Nivoliers, Sylvain Lefebvre, and Bruno Lévy. 2010. Invisible Seams. In Proc. Eurographics Conference on Rendering. 1489–1496. Google ScholarDigital Library
    34. Pedro V. Sander, Steven J. Gortler, John Snyder, and Hugues Hoppe. 2002. Signal-specialized Parametrization. In Proc. Eurographics Workshop on Rendering. 87–98. Google ScholarDigital Library
    35. 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 (SIGGRAPH ’01). ACM, New York, NY, USA, 409–416. Google ScholarDigital Library
    36. 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 (SGP ’03). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 146–155. Google ScholarDigital Library
    37. Alla Sheffer and John C. Hart. 2002. Seamster: Inconspicuous Low-distortion Texture Seam Layout. In Proceedings of the Conference on Visualization ’02 (VIS ’02). IEEE Computer Society, Washington, DC, USA, 291–298. Google ScholarDigital Library
    38. Alla Sheffer, Bruno Lévy, Maxim Mogilnitsky, and Alexander Bogomyakov. 2005. ABF++: Fast and Robust Angle Based Flattening. ACM Transactions on Graphics (Apr 2005). Google ScholarDigital Library
    39. 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
    40. Jason Smith and Scott Schaefer. 2015. Bijective Parameterization with Free Boundaries. ACM Trans. Graph. 34, 4, Article 70 (July 2015), 9 pages. Google ScholarDigital Library
    41. Olga Sorkine, Daniel Cohen-Or, Rony Goldenthal, and Dani Lischinski. 2002. Bounded-distortion Piecewise Mesh Parameterization. In Proceedings of the Conference on Visualization ’02 (VIS ’02). IEEE Computer Society, Washington, DC, USA, 355–362. Google ScholarDigital Library
    42. 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. Google ScholarDigital Library
    43. Yahan Zhou, Shinjiro Sueda, Wojciech Matusik, and Ariel Shamir. 2014. Boxelization: Folding 3D Objects into Boxes. ACM Trans. Graph. 33, 4, Article 71 (July 2014), 8 pages. Google ScholarDigital Library

ACM Digital Library Publication: