{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:21:27Z","timestamp":1764969687326,"version":"3.46.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["Grant Nos. 62036010","62472373"],"award-info":[{"award-number":["Grant Nos. 62036010","62472373"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>Approximate Convex Decomposition (ACD) aims to approximate complex 3D shapes with convex components, which is widely applied to create compact collision representations for real-time applications, including VR\/AR, interactive games, and robotic simulations. Efficiency and optimality are critical for ACD algorithms in approximating large-scale, complex 3D shapes, enabling high-quality decompositions with minimal components. Unfortunately, existing methods either employ sub-optimal greedy strategies or rely on computationally intensive multi-step searches. In this work, we propose RL-ACD, a data-driven, reinforcement learning-based approach for efficient and near-optimal convex shape decomposition. We formulate ACD as a Markov Decision Process (MDP), where cutting planes are iteratively applied based on the current stage's mesh fragments rather than the entire fine-grained mesh, leading to a novel, efficient geometric encoding. To train near-optimal policies for ACD, we propose a novel dual-state Bellman loss and analyze its convergence using a Q-learning algorithm. Comprehensive evaluations across diverse datasets validate the efficiency and accuracy of RL-ACD for convex decomposition tasks. Our method outperforms the multi-step tree search by 15\u00d7 in terms of computational speed, while reducing the number of resulting components by 16% compared to the current state-of-the-art greedy algorithms, significantly narrowing the sub-optimality gap and enhancing downstream task performance.<\/jats:p>","DOI":"10.1145\/3763270","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["RL-ACD: Reinforcement Learning-based Approximate Convex Decomposition"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5796-6144","authenticated-orcid":false,"given":"Yuzhe","family":"Luo","sequence":"first","affiliation":[{"name":"Sate Key Lab of CAD&amp;CG, Zhejiang University, Hangzhou, China"},{"name":"LIGHTSPEED, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9348-526X","authenticated-orcid":false,"given":"Zherong","family":"Pan","sequence":"additional","affiliation":[{"name":"LIGHTSPEED, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3326-7943","authenticated-orcid":false,"given":"Kui","family":"Wu","sequence":"additional","affiliation":[{"name":"LIGHTSPEED, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6036-6782","authenticated-orcid":false,"given":"Xingyi","family":"Du","sequence":"additional","affiliation":[{"name":"LIGHTSPEED, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-6104-4434","authenticated-orcid":false,"given":"Yun","family":"Zeng","sequence":"additional","affiliation":[{"name":"LIGHTSPEED, California, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7441-0086","authenticated-orcid":false,"given":"Xiangjun","family":"Tang","sequence":"additional","affiliation":[{"name":"Sate Key Lab of CAD&amp;CG, Zhejiang University, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2432-809X","authenticated-orcid":false,"given":"Yiqian","family":"Wu","sequence":"additional","affiliation":[{"name":"Sate Key Lab of CAD&amp;CG, Zhejiang University, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7339-2920","authenticated-orcid":false,"given":"Xiaogang","family":"Jin","sequence":"additional","affiliation":[{"name":"State Key Lab of CAD&amp;CG, Zhejiang University, Hangzhou, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0829-7075","authenticated-orcid":false,"given":"Xifeng","family":"Gao","sequence":"additional","affiliation":[{"name":"LIGHTSPEED, California, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ACM SIGGRAPH Conference Papers.","author":"Andrews James","year":"2024","unstructured":"James Andrews. 2024. Navigation-driven approximate convex decomposition. In ACM SIGGRAPH Conference Papers."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221025"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237218.237246"},{"key":"e_1_2_1_4_1","unstructured":"Angel X Chang Thomas Funkhouser Leonidas Guibas Pat Hanrahan Qixing Huang Zimo Li Silvio Savarese Manolis Savva Shuran Song Hao Su et al. 2015. ShapeNet: An information-rich 3d model repository. arXiv preprint arXiv:1512.03012 (2015)."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 45\u201354","author":"Chen Zhiqin","year":"2020","unstructured":"Zhiqin Chen, Andrea Tagliasacchi, and Hao Zhang. 2020. BSP-Net: Generating compact meshes via binary space partitioning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 45\u201354."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 31\u201344","author":"Deng Boyang","year":"2020","unstructured":"Boyang Deng, Kyle Genova, Soroosh Yazdani, Sofien Bouaziz, Geoffrey Hinton, and Andrea Tagliasacchi. 2020. CvxNet: Learnable convex decomposition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 31\u201344."},{"key":"e_1_2_1_7_1","first-page":"73312","article-title":"Swarm reinforcement learning for adaptive mesh refinement","volume":"36","author":"Freymuth Niklas","year":"2023","unstructured":"Niklas Freymuth, Philipp Dahlinger, Tobias W\u00fcrth, Simon Reisch, Luise K\u00e4rger, and Gerhard Neumann. 2023. Swarm reinforcement learning for adaptive mesh refinement. Advances in Neural Information Processing Systems 36 (2023), 73312\u201373347.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the IEEE International Conference on Machine Learning (ICML). 1352\u20131361","author":"Haarnoja Tuomas","year":"2017","unstructured":"Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. 2017. Reinforcement learning with deep energy-based policies. In Proceedings of the IEEE International Conference on Machine Learning (ICML). 1352\u20131361."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00024-2"},{"key":"e_1_2_1_10_1","volume-title":"Robust watertight manifold surface generation method for ShapeNet models. arXiv preprint arXiv:1802.01698","author":"Huang Jingwei","year":"2018","unstructured":"Jingwei Huang, Hao Su, and Leonidas Guibas. 2018. Robust watertight manifold surface generation method for ShapeNet models. arXiv preprint arXiv:1802.01698 (2018)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620370409"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00023-X"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC). 4046\u20134051","author":"Kockara Sinan","year":"2007","unstructured":"Sinan Kockara, Tansel Halic, Kamran Iqbal, Coskun Bayrak, and Richard Rowe. 2007. Collision detection: A survey. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC). 4046\u20134051."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997889"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the ACM Symposium on Solid and Physical Modeling. 121\u2013131","author":"Lien Jyh-Ming","year":"2007","unstructured":"Jyh-Ming Lien and Nancy M Amato. 2007. Approximate convex decomposition of polyhedra. In Proceedings of the ACM Symposium on Solid and Physical Modeling. 121\u2013131."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275035"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the IEEE International Conference on Image Processing (ICIP). 3501\u20133504","author":"Mamou Khaled","year":"2009","unstructured":"Khaled Mamou and Faouzi Ghorbel. 2009. A simple and efficient approach for 3D mesh approximate convex decomposition. In Proceedings of the IEEE International Conference on Image Processing (ICIP). 3501\u20133504."},{"key":"e_1_2_1_18_1","first-page":"141","article-title":"Volumetric hierarchical approximate convex decomposition","volume":"3","author":"Mamou Khaled","year":"2016","unstructured":"Khaled Mamou, E Lengyel, and A Peters. 2016. Volumetric hierarchical approximate convex decomposition. Game Engine Gems 3 (2016), 141\u2013158.","journal-title":"Game Engine Gems"},{"key":"e_1_2_1_19_1","first-page":"71","article-title":"Convolutional neural networks on surfaces via seamless toric covers","volume":"36","author":"Maron Haggai","year":"2017","unstructured":"Haggai Maron, Meirav Galun, Noam Aigerman, Miri Trope, Nadav Dym, Ersin Yumer, Vladimir G Kim, and Yaron Lipman. 2017. Convolutional neural networks on surfaces via seamless toric covers. ACM Transactions on Graphics (TOG) 36, 4 (2017), 71.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_1_20_1","volume-title":"Convergence of Q-learning: A simple proof","author":"Melo Francisco S","year":"2001","unstructured":"Francisco S Melo. 2001. Convergence of Q-learning: A simple proof. Institute of Systems and Robotics, Tech. Rep (2001), 1\u20134."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Volodymyr Mnih Koray Kavukcuoglu David Silver Andrei A Rusu Joel Veness Marc G Bellemare Alex Graves Martin Riedmiller Andreas K Fidjeland Georg Ostrovski et al. 2015. Human-level control through deep reinforcement learning. Nature 518 7540 (2015) 529\u2013533.","DOI":"10.1038\/nature14236"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1983.1056648"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201311"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)80172-0"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the IEEE International Conference on Computer Vision (ICCV). 303\u2013310","author":"Ren Zhou","year":"2011","unstructured":"Zhou Ren, Junsong Yuan, Chunyuan Li, and Wenyu Liu. 2011. Minimum near-convex decomposition for robust shape representation. In Proceedings of the IEEE International Conference on Computer Vision (ICCV). 303\u2013310."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632947"},{"volume-title":"Reinforcement learning: An introduction","author":"Sutton Richard S","key":"e_1_2_1_27_1","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press."},{"key":"e_1_2_1_28_1","first-page":"226","article-title":"Approximate convex decomposition and transfer for animated meshes","volume":"37","author":"Thul Daniel","year":"2018","unstructured":"Daniel Thul, Lubor Ladicky, Sohyeon Jeong, and Marc Pollefeys. 2018. Approximate convex decomposition and transfer for animated meshes. ACM Transactions on Graphics (TOG) 37, 6 (2018), 226.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2022.3207346"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366184"},{"key":"e_1_2_1_31_1","first-page":"42","article-title":"Approximate convex decomposition for 3d meshes with collision-aware concavity and tree search","volume":"41","author":"Wei Xinyue","year":"2022","unstructured":"Xinyue Wei, Minghua Liu, Zhan Ling, and Hao Su. 2022. Approximate convex decomposition for 3d meshes with collision-aware concavity and tree search. ACM Transactions on Graphics (TOG) 41, 4 (2022), 42.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_1_32_1","first-page":"82","article-title":"Learning a probabilistic latent space of object shapes via 3d generative-adversarial modeling","volume":"29","author":"Wu Jiajun","year":"2016","unstructured":"Jiajun Wu, Chengkai Zhang, Tianfan Xue, Bill Freeman, and Josh Tenenbaum. 2016. Learning a probabilistic latent space of object shapes via 3d generative-adversarial modeling. Advances in Neural Information Processing Systems (NIPS) 29 (2016), 82\u201390.","journal-title":"Advances in Neural Information Processing Systems (NIPS)"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618348"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 21769\u201321780","author":"Zhang Renrui","year":"2023","unstructured":"Renrui Zhang, Liuhui Wang, Yu Qiao, Peng Gao, and Hongsheng Li. 2023. Learning 3d representations from 2d pre-trained models via image-to-point masked autoencoders. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 21769\u201321780."},{"key":"e_1_2_1_35_1","first-page":"165","article-title":"Learning physically realizable skills for online packing of general 3D shapes","volume":"42","author":"Zhao Hang","year":"2023","unstructured":"Hang Zhao, Zherong Pan, Yang Yu, and Kai Xu. 2023. Learning physically realizable skills for online packing of general 3D shapes. ACM Transactions on Graphics (TOG) 42, 4 (2023), 165.","journal-title":"ACM Transactions on Graphics (TOG)"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763270","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:18:04Z","timestamp":1764969484000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763270"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3763270"],"URL":"https:\/\/doi.org\/10.1145\/3763270","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-04-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}