{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T16:56:23Z","timestamp":1777568183205,"version":"3.51.4"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T00:00:00Z","timestamp":1701734400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2023,12,5]]},"abstract":"<jats:p>2D irregular shape packing is a necessary step to arrange UV patches of a 3D model within a texture atlas for memory-efficient appearance rendering in computer graphics. Being a joint, combinatorial decision-making problem involving all patch positions and orientations, this problem has well-known NP-hard complexity. Prior solutions either assume a heuristic packing order or modify the upstream mesh cut and UV mapping to simplify the problem, which either limits the packing ratio or incurs robustness or generality issues. Instead, we introduce a learning-assisted 2D irregular shape packing method that achieves a high packing quality with minimal requirements from the input. Our method iteratively selects and groups subsets of UV patches into near-rectangular super patches, essentially reducing the problem to bin-packing, based on which a joint optimization is employed to further improve the packing ratio. In order to efficiently deal with large problem instances with hundreds of patches, we train deep neural policies to predict nearly rectangular patch subsets and determine their relative poses, leading to linear time scaling with the number of patches. We demonstrate the effectiveness of our method on three datasets for UV packing, where our method achieves a higher packing ratio over several widely used baselines with competitive computational speed.<\/jats:p>","DOI":"10.1145\/3618348","type":"journal-article","created":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T10:20:48Z","timestamp":1701771648000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Learning Based 2D Irregular Shape Packing"],"prefix":"10.1145","volume":"42","author":[{"given":"Zeshi","family":"Yang","sequence":"first","affiliation":[{"name":"LightSpeed Studios, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zherong","family":"Pan","sequence":"additional","affiliation":[{"name":"LightSpeed Studios, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manyi","family":"Li","sequence":"additional","affiliation":[{"name":"Shandong University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kui","family":"Wu","sequence":"additional","affiliation":[{"name":"LightSpeed Studios, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xifeng","family":"Gao","sequence":"additional","affiliation":[{"name":"LightSpeed Studios, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,5]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the 1st international computational geometry software workshop","volume":"63","author":"Akkiraju Nataraj","year":"1995","unstructured":"Nataraj Akkiraju, Herbert Edelsbrunner, Michael Facello, Ping Fu, EP Mucke, and Carlos Varela. 1995. Alpha shapes: definition and software. In Proceedings of the 1st international computational geometry software workshop, Vol. 63."},{"key":"e_1_2_2_2_1","volume-title":"Computer Graphics Forum","author":"Attene Marco","unstructured":"Marco Attene. 2015. Shapes in a box: Disassembling 3D objects for efficient packing and fabrication. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 64--76."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0168"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.063"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.02.026"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0293"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120899"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.202"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2007.06.063"},{"key":"e_1_2_2_10_1","unstructured":"Dawson-Haggerty et al. 2019. trimesh. https:\/\/trimsh.org\/"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653771.1653865"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.3390\/math11020327"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2004.09.008"},{"key":"e_1_2_2_14_1","volume-title":"International Conference on Machine Learning. PMLR, 3700--3710","author":"Goyal Ankit","year":"2020","unstructured":"Ankit Goyal and Jia Deng. 2020. Packit: A virtual environment for geometric planning. In International Conference on Machine Learning. PMLR, 3700--3710."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.3389\/fmech.2022.966691"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1024022"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417764"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.61.132"},{"key":"e_1_2_2_19_1","volume-title":"Learning to solve 3-D bin packing problem via deep reinforcement learning and constraint programming","author":"Jiang Yuan","year":"2021","unstructured":"Yuan Jiang, Zhiguang Cao, and Jie Zhang. 2021. Learning to solve 3-D bin packing problem via deep reinforcement learning and constraint programming. IEEE transactions on cybernetics (2021)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130895"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.3389\/fmech.2020.576642"},{"key":"e_1_2_2_22_1","volume-title":"Least squares conformal maps for automatic texture atlas generation. ACM transactions on graphics (TOG) 21, 3","author":"L\u00e9vy Bruno","year":"2002","unstructured":"Bruno L\u00e9vy, Sylvain Petitjean, Nicolas Ray, and J\u00e9rome Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM transactions on graphics (TOG) 21, 3 (2002), 362--371."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201328"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323001"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1631\/jzus.2006.A0570"},{"key":"e_1_2_2_26_1","volume-title":"Computer Graphics Forum","author":"N\u00f6ll Tobias","unstructured":"Tobias N\u00f6ll and D Strieker. 2011. Efficient packing of arbitrary shaped charts for automatic texture atlas generation. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1309--1317."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2007.10.012"},{"key":"e_1_2_2_28_1","unstructured":"Adam Paszke Sam Gross Soumith Chintala Gregory Chanan Edward Yang Zachary DeVito Zeming Lin Alban Desmaison Luca Antiga and Adam Lerer. 2017. Automatic differentiation in pytorch. (2017)."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130845"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983621"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.engappai.2008.10.025"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383307"},{"key":"e_1_2_2_33_1","unstructured":"Pedro V Sander Zo\u00eb J Wood Steven Gortler John Snyder and Hugues Hoppe. 2003. Multi-chart geometry images. (2003)."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201389"},{"key":"e_1_2_2_35_1","volume-title":"Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347","author":"Schulman John","year":"2017","unstructured":"John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.2002.1183795"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003710050082"},{"key":"e_1_2_2_39_1","volume-title":"Reinforcement learning: An introduction","author":"Sutton Richard S","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10295"},{"key":"e_1_2_2_41_1","unstructured":"Petar Velickovic Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Lio Yoshua Bengio et al. 2017. Graph attention networks. stat 1050 20 (2017) 10--48550."},{"key":"e_1_2_2_42_1","volume-title":"Highly-Performant Package for Graph Neural Networks. arXiv preprint arXiv:1909.01315","author":"Wang Minjie","year":"2019","unstructured":"Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. 2019. Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks. arXiv preprint arXiv:1909.01315 (2019)."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2022.102149"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2023.3235742"},{"key":"e_1_2_2_45_1","volume-title":"Retrieved","author":"Young Jonathan","year":"2023","unstructured":"Jonathan Young. 2023. Xatlas. Retrieved May, 2023 from https:\/\/github.com\/jpcy\/xatlas"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2020.101854"},{"key":"e_1_2_2_47_1","volume-title":"International Conference on Learning Representations. 0--0.","author":"Zhao Hang","year":"2021","unstructured":"Hang Zhao, Yang Yu, and Kai Xu. 2021. Learning efficient online 3d bin packing on packing configuration trees. In International Conference on Learning Representations. 0--0."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11432-021-3348-6"},{"key":"e_1_2_2_49_1","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10k: A dataset of 10 000 3d-printing models."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618348","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T10:52:39Z","timestamp":1755773559000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,5]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,5]]}},"alternative-id":["10.1145\/3618348"],"URL":"https:\/\/doi.org\/10.1145\/3618348","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,5]]},"assertion":[{"value":"2023-12-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}