{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T12:23:05Z","timestamp":1764937385287,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T00:00:00Z","timestamp":1646784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CCF-2017927, IIS-1954028, IIS-1838071, 1749570 and 1813166"],"award-info":[{"award-number":["CCF-2017927, IIS-1954028, IIS-1838071, 1749570 and 1813166"]}]},{"name":"Google faculty award and the NSF China","award":["62072284"],"award-info":[{"award-number":["62072284"]}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF2010168"],"award-info":[{"award-number":["W911NF2010168"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["FA9550-19-1-031"],"award-info":[{"award-number":["FA9550-19-1-031"]}],"id":[{"id":"10.13039\/100000181","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":[[2022,6,30]]},"abstract":"<jats:p>\n            Past work on optimizing fabrication plans given a carpentry design can provide Pareto-optimal plans trading off between material waste, fabrication time, precision, and other considerations. However, when developing fabrication plans, experts rarely restrict to a\n            <jats:italic>single design<\/jats:italic>\n            , instead considering\n            <jats:italic>families of design variations<\/jats:italic>\n            , sometimes adjusting designs to simplify fabrication. Jointly exploring the design and fabrication plan spaces for each design is intractable using current techniques. We present a new approach to jointly optimize design and fabrication plans for carpentered objects. To make this bi-level optimization tractable, we adapt recent work from program synthesis based on equality graphs (e-graphs), which encode sets of equivalent programs. Our insight is that subproblems within our bi-level problem share significant substructures. By representing both designs and fabrication plans in a new\n            <jats:italic>bag of parts<\/jats:italic>\n            (BOP) e-graph, we amortize the cost of optimizing design components shared among multiple candidates. Even using BOP e-graphs, the optimization space grows quickly in practice. Hence, we also show how a feedback-guided search strategy dubbed\n            <jats:italic>Iterative Contraction and Expansion on E-graphs<\/jats:italic>\n            (ICEE) can keep the size of the e-graph manageable and direct the search towards promising candidates. We illustrate the advantages of our pipeline through examples from the carpentry domain.\n          <\/jats:p>","DOI":"10.1145\/3508499","type":"journal-article","created":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T12:16:28Z","timestamp":1646828188000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Co-Optimization of Design and Fabrication Plans for Carpentry"],"prefix":"10.1145","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6389-1045","authenticated-orcid":false,"given":"Haisen","family":"Zhao","sequence":"first","affiliation":[{"name":"University of Washington and Shandong University and IST Austria, Seattle, WA"}]},{"given":"Max","family":"Willsey","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Amy","family":"Zhu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Chandrakana","family":"Nandi","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Zachary","family":"Tatlock","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Justin","family":"Solomon","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}]},{"given":"Adriana","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]}],"member":"320","published-online":{"date-parts":[[2022,3,9]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322981"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1527125.1527138"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13327"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2537852"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6940-7_15"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2013.2281535"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.996017"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01020-0_13"},{"key":"e_1_3_3_10_1","volume-title":"Bilevel Optimization: Theory, Algorithms and Applications","author":"Dempe Stephan","year":"2018","unstructured":"Stephan Dempe. 2018. Bilevel Optimization: Theory, Algorithms and Applications. TU Bergakademie Freiberg, Fakult\u00e4t f\u00fcr Mathematik und Informatik."},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392465"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0259-0"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323022"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766892"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925900"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417843"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2006.1688451"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2013.05.011"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/543552.512566"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2633519"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661289"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964980"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290605.3300386"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2016.01.084"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417772"},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322960"},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386012"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/909447"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737959"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386001"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12051"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/mcda.285"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2712906"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130803"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2032305.2032364"},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417765"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480881.1480915"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185582"},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407799"},{"issue":"6","key":"e_1_3_3_40_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3355089.3356489","article-title":"Design and structural optimization of topological interlocking assemblies","volume":"38","author":"Wang Ziqi","year":"2019","unstructured":"Ziqi Wang, Peng Song, Florin Isvoranu, and Mark Pauly. 2019. Design and structural optimization of topological interlocking assemblies. ACM Transactions on Graphics 38, 6 (2019), 1\u201313.","journal-title":"ACM Transactions on Graphics"},{"key":"e_1_3_3_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356556"},{"issue":"6","key":"e_1_3_3_43_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3414685.3417810","article-title":"DHFSlicer: Double height-field slicing for milling fixed-height materials","volume":"39","author":"Yang Jinfan","year":"2020","unstructured":"Jinfan Yang, Chrystiano Araujo, Nicholas Vining, Zachary Ferguson, Enrique Rosales, Daniele Panozzo, Sylvain Lefevbre, Paolo Cignoni, and Alla Sheffer. 2020. DHFSlicer: Double height-field slicing for milling fixed-height materials. ACM Transactions on Graphics 39, 6 (2020), 1\u201317.","journal-title":"ACM Transactions on Graphics"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12696"},{"key":"e_1_3_3_45_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-947X(2000)126:2(115)"},{"key":"e_1_3_3_46_1","doi-asserted-by":"crossref","unstructured":"Xiaoting Zhang Guoxin Fang M\u00e9lina Skouras Gwenda Gieseler Charlie Wang and Emily Whiting. 2019. Computational design of fabric formwork. ACM Transactions on Graphics 38 4 (2019) 1\u201313.","DOI":"10.1145\/3306346.3322988"},{"issue":"4","key":"e_1_3_3_47_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2897824.2925958","article-title":"Connected fermat spirals for layered fabrication","volume":"35","author":"Zhao Haisen","year":"2016","unstructured":"Haisen Zhao, Fanglin Gu, Qi-Xing Huang, Jorge Garcia, Yong Chen, Changhe Tu, Bedrich Benes, Hao Zhang, Daniel Cohen-Or, and Baoquan Chen. 2016. Connected fermat spirals for layered fabrication. ACM Transactions on Graphics 35, 4 (2016), 1\u201310.","journal-title":"ACM Transactions on Graphics"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508499","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3508499","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3508499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:40Z","timestamp":1750188640000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3508499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,9]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3508499"],"URL":"https:\/\/doi.org\/10.1145\/3508499","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2022,3,9]]},"assertion":[{"value":"2021-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}