{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:31:10Z","timestamp":1780054270613,"version":"3.54.0"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2018,12,4]],"date-time":"2018-12-04T00:00:00Z","timestamp":1543881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-14-2-0242"],"award-info":[{"award-number":["FA8750-14-2-0242"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1138967, 1830901, 1644558"],"award-info":[{"award-number":["1138967, 1830901, 1644558"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>While computer-aided design is a major part of many modern manufacturing pipelines, the design files typically generated describe raw geometry. Lost in this representation is the procedure by which these designs were generated. In this paper, we present a method for reverse-engineering the process by which 3D models may have been generated, in the language of constructive solid geometry (CSG). Observing that CSG is a formal grammar, we formulate this inverse CSG problem as a program synthesis problem. Our solution is an algorithm that couples geometric processing with state-of-the-art program synthesis techniques. In this scheme, geometric processing is used to convert the mixed discrete and continuous domain of CSG trees to a pure discrete domain where modern program synthesizers excel. We demonstrate the efficiency and scalability of our algorithm on several different examples, including those with over 100 primitive parts. We show that our algorithm is able to find simple programs which are close to the ground truth, and demonstrate our method's applicability in mesh re-editing. Finally, we compare our method to prior state-of-the-art. We demonstrate that our algorithm dominates previous methods in terms of resulting CSG compactness and runtime, and can handle far more complex input meshes than any previous method.<\/jats:p>","DOI":"10.1145\/3272127.3275006","type":"journal-article","created":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T19:16:10Z","timestamp":1543432570000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":103,"title":["InverseCSG"],"prefix":"10.1145","volume":"37","author":[{"given":"Tao","family":"Du","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeevana Priya","family":"Inala","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yewen","family":"Pu","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Spielberg","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adriana","family":"Schulz","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniela","family":"Rus","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Armando","family":"Solar-Lezama","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wojciech","family":"Matusik","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,12,4]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa.","author":"Alur Rajeev","year":"2013","unstructured":"Rajeev Alur , Rastislav Bodik , Garvit Juniwal , Milo MK Martin , Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2013 . Syntax-guided synthesis. In Formal Methods in Computer-Aided Design (FMCAD), 2013. IEEE , 1--8. Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo MK Martin, Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2013. Syntax-guided synthesis. In Formal Methods in Computer-Aided Design (FMCAD), 2013. IEEE, 1--8."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0375-x"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185574"},{"key":"e_1_2_2_4_1","volume-title":"Three-dimensional binary space partitioning tree and constructive solid geometry tree construction from algebraic boundary representations","author":"Buchele Suzanne Fox","unstructured":"Suzanne Fox Buchele . 1999. Three-dimensional binary space partitioning tree and constructive solid geometry tree construction from algebraic boundary representations . The University of Texas at Austin. Suzanne Fox Buchele. 1999. Three-dimensional binary space partitioning tree and constructive solid geometry tree construction from algebraic boundary representations. The University of Texas at Austin."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2004.01.006"},{"key":"e_1_2_2_6_1","unstructured":"Suzanne F Buchele and Angela C Roles. 2001. Binary space partitioning tree and constructive solid geometry representations for objects bounded by curved surfaces.. In CCCG. Citeseer 49--52.  Suzanne F Buchele and Angela C Roles. 2001. Binary space partitioning tree and constructive solid geometry representations for objects bounded by curved surfaces.. In CCCG. Citeseer 49--52."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964930"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508378"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015817"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676726.2677006"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982402"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2910578"},{"key":"e_1_2_2_13_1","volume-title":"Handbook of computer aided geometric design","author":"Farin Gerald E","unstructured":"Gerald E Farin , Josef Hoschek , and Myung-Soo Kim . 2002. Handbook of computer aided geometric design . Elsevier . Gerald E Farin, Josef Hoschek, and Myung-Soo Kim. 2002. Handbook of computer aided geometric design. Elsevier."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2016.01.001"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601185"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766892"},{"key":"e_1_2_2_17_1","volume-title":"GrabCAD: Design Community","author":"CAD.","year":"2018","unstructured":"Grab CAD. 2018. GrabCAD: Design Community , CAD Library , 3D Printing Software. ( 2018 ). https:\/\/grabcad.com\/ GrabCAD. 2018. GrabCAD: Design Community, CAD Library, 3D Printing Software. (2018). https:\/\/grabcad.com\/"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925844.1926423"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2240236.2240260"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Sumit Gulwani Oleksandr Polozov Rishabh Singh etal 2017. Program synthesis. Foundations and Trends\u00ae in Programming Languages 4 1--2 (2017) 1--119.  Sumit Gulwani Oleksandr Polozov Rishabh Singh et al. 2017. Program synthesis. Foundations and Trends\u00ae in Programming Languages 4 1--2 (2017) 1--119.","DOI":"10.1561\/2500000010"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601218"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24855-2_110"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964973"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185551"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818648"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461933"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2480359.2429125"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818060"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964980"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2017.02.009"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964947"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12438"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925951"},{"key":"e_1_2_2_34_1","volume-title":"Retrieved","author":"SCAD.","year":"2018","unstructured":"Open SCAD. 2018 . The Programmers Solid 3D CAD Modeller. (2018) . Retrieved January 18, 2018 from http:\/\/www.openscad.org\/ OpenSCAD. 2018. The Programmers Solid 3D CAD Modeller. (2018). Retrieved January 18, 2018 from http:\/\/www.openscad.org\/"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925935"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342004041291"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.156011"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766895"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594302"},{"key":"e_1_2_2_40_1","volume-title":"Computer graphics forum","author":"Schnabel Ruwen","unstructured":"Ruwen Schnabel , Roland Wahl , and Reinhard Klein . 2007. Efficient RANSAC for point-cloud shape detection . In Computer graphics forum , Vol. 26 . Wiley Online Library , 214--226. Ruwen Schnabel, Roland Wahl, and Reinhard Klein. 2007. Efficient RANSAC for point-cloud shape detection. In Computer graphics forum, Vol. 26. Wiley Online Library, 214--226."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073688"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629573"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982416"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000468"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(91)90077-A"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/169728.169723"},{"key":"e_1_2_2_47_1","volume-title":"CSGNet: Neural Shape Parser for Constructive Solid Geometry. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).","author":"Sharma Gopal","year":"2018","unstructured":"Gopal Sharma , Rishabh Goyal , Difan Liu , Evangelos Kalogerakis , and Subhransu Maji . 2018 . CSGNet: Neural Shape Parser for Constructive Solid Geometry. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Gopal Sharma, Rishabh Goyal, Difan Liu, Evangelos Kalogerakis, and Subhransu Maji. 2018. CSGNet: Neural Shape Parser for Constructive Solid Geometry. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766994"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149199"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1168917.1168907"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944846.1944851"},{"key":"e_1_2_2_53_1","volume-title":"Thingiverse: Digital Designs for Physical Objects.","year":"2018","unstructured":"Thingiverse. 2018 . Thingiverse: Digital Designs for Physical Objects. (2018). https:\/\/www.thingiverse.com\/ Thingiverse. 2018. Thingiverse: Digital Designs for Physical Objects. (2018). https:\/\/www.thingiverse.com\/"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.160"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462174"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751556"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601162"},{"key":"e_1_2_2_59_1","volume-title":"Computer Graphics Forum","author":"Wu Q","unstructured":"Q Wu , K Xu , and J Wang . 2018. Constructing 3D CSG Models from 3D Raw Point Clouds . In Computer Graphics Forum , Vol. 37 . Wiley Online Library , 221--232. Q Wu, K Xu, and J Wang. 2018. Constructing 3D CSG Models from 3D Raw Point Clouds. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 221--232."},{"key":"e_1_2_2_60_1","volume-title":"Computer Graphics Forum","author":"Leif Kobbelt Jianhua Wu","unstructured":"Jianhua Wu Leif Kobbelt . 2005. Structure recovery via hybrid variational surface approximation . In Computer Graphics Forum , Vol. 24 . Wiley Online Library , 277--284. Jianhua Wu Leif Kobbelt. 2005. Structure recovery via hybrid variational surface approximation. In Computer Graphics Forum, Vol. 24. Wiley Online Library, 277--284."},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12434"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982425"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.04.005"},{"key":"e_1_2_2_64_1","volume-title":"Oscar Kin-Chung Au, and Chiew-Lan Tai","author":"Zheng Youyi","year":"2011","unstructured":"Youyi Zheng , Hongbo Fu , Daniel Cohen-Or , Oscar Kin-Chung Au, and Chiew-Lan Tai . 2011 . Component-wise Controllers for Structure-Preserving Shape Manipulation. In Computer Graphics Forum, Vol. 30 . Wiley Online Library , 563--572. Youyi Zheng, Hongbo Fu, Daniel Cohen-Or, Oscar Kin-Chung Au, and Chiew-Lan Tai. 2011. Component-wise Controllers for Structure-Preserving Shape Manipulation. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 563--572."},{"key":"e_1_2_2_65_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson . 2016 . Thingi10K : A Dataset of 10 ,000 3D -Printing Models. arXiv preprint arXiv:1605.04797 (2016). Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).","journal-title":"A Dataset of"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073613"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3272127.3275006","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3272127.3275006","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3272127.3275006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:03Z","timestamp":1750207443000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3272127.3275006"}},"subtitle":["automatic conversion of 3D models to CSG trees"],"short-title":[],"issued":{"date-parts":[[2018,12,4]]},"references-count":64,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3272127.3275006"],"URL":"https:\/\/doi.org\/10.1145\/3272127.3275006","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,4]]},"assertion":[{"value":"2018-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}