{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T16:42:13Z","timestamp":1777567333239,"version":"3.51.4"},"reference-count":50,"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"}],"funder":[{"name":"the Research Grants Council of the Hong Kong Special Administrative Region","award":["CUHK 14201921"],"award-info":[{"award-number":["CUHK 14201921"]}]}],"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>\n            This paper presents computational methods to aid the creation of LEGO\n            <jats:sup>\u00ae1<\/jats:sup>\n            sketch models from simple input images. Beyond conventional LEGO\n            <jats:sup>\u00ae<\/jats:sup>\n            mosaics, we aim to improve the expressiveness of LEGO\n            <jats:sup>\u00ae<\/jats:sup>\n            models by utilizing LEGO\n            <jats:sup>\u00ae<\/jats:sup>\n            tiles with sloping and rounding edges, together with rectangular bricks, to reproduce smooth curves and sharp features in the input. This is a challenging task, as we have limited brick shapes to use and limited space to place bricks. Also, the search space is immense and combinatorial in nature. We approach the task by decoupling the LEGO\n            <jats:sup>\u00ae<\/jats:sup>\n            construction into two steps: first approximate the shape with a LEGO\n            <jats:sup>\u00ae<\/jats:sup>\n            -buildable contour then filling the contour polygon with LEGO\n            <jats:sup>\u00ae<\/jats:sup>\n            bricks. Further, we formulate this contour approximation into a graph optimization with our objective and constraints and effectively solve for the contour polygon that best approximates the input shape. Further, we extend our optimization model to handle multi-color and multi-layer regions, and formulate a grid alignment process and various perceptual constraints to refine the results. We employ our method to create a large variety of LEGO\n            <jats:sup>\u00ae<\/jats:sup>\n            models and compare it with humans and baseline methods to manifest its compelling quality and speed.\n          <\/jats:p>","DOI":"10.1145\/3618306","type":"journal-article","created":{"date-parts":[[2023,12,5]],"date-time":"2023-12-05T10:20:48Z","timestamp":1701771648000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Computational Design of LEGO\n            <sup>\u00ae<\/sup>\n            Sketch Art"],"prefix":"10.1145","volume":"42","author":[{"given":"Mingjun","family":"Zhou","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}]},{"given":"Jiahao","family":"Ge","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}]},{"given":"Hao","family":"Xu","sequence":"additional","affiliation":[{"name":"Qianzhi Technology Inc., China"}]},{"given":"Chi-Wing","family":"Fu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2023,12,5]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2023. BrickLink - Studio. https:\/\/www.bricklink.com\/v2\/build\/studio.page"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(03)00002-3"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767747"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2014.2336542"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.993558"},{"key":"e_1_2_2_6_1","article-title":"The OpenCV Library","volume":"25","author":"Bradski Gary","year":"2000","unstructured":"Gary Bradski. 2000. The OpenCV Library. Dr. Dobb's Journal: Software Tools for the Professional Programmer 25, 11 (2000).","journal-title":"Dr. Dobb's Journal: Software Tools for the Professional Programmer"},{"key":"e_1_2_2_7_1","article-title":"Fabricable Tile Decors","volume":"36","author":"Chen Weikai","year":"2017","unstructured":"Weikai Chen, Yuexin Ma, Sylvain Lefebvre, Shiqing Xin, Jon\u00e0s Mart\u00ednez, and wenping wang. 2017. Fabricable Tile Decors. ACM Transactions on Graphics (SIGGRAPH Asia) 36, 6 (2017), 175:1--175:15.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_8_1","article-title":"3D Fabrication with Universal Building Blocks and Pyramidal Shells","volume":"37","author":"Chen Xuelin","year":"2018","unstructured":"Xuelin Chen, Honghua Li, Chi-Wing Fu, Hao Zhang, Daniel Cohen-Or, and Baoquan Chen. 2018. 3D Fabrication with Universal Building Blocks and Pyramidal Shells. ACM Transactions on Graphics (SIGGRAPH Asia) 37, 6 (2018), 189:1--189:15.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/83.481671"},{"key":"e_1_2_2_10_1","article-title":"Assembling Self-Supporting Structures","volume":"33","author":"Deuss Mario","year":"2014","unstructured":"Mario Deuss, Daniele Panozzo, Emily Whiting, Yang Liu, Philippe Block, Olga Sorkine-Hornung, and Mark Pauly. 2014. Assembling Self-Supporting Structures. ACM Transactions on Graphics (SIGGRAPH Asia) 33, 6 (2014), 214:1--214:10.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778782"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778781"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS47612.2022.9981423"},{"key":"e_1_2_2_14_1","article-title":"Computational Design of Cold Bent Glass Facades","volume":"39","author":"Gavriil Konstantinos","year":"2020","unstructured":"Konstantinos Gavriil, Ruslan Guseinov, Jes\u00fas P\u00e9rez, Davide Pellis, Paul Henderson, Florian Rist, Helmut Pottmann, and Bernd Bickel. 2020. Computational Design of Cold Bent Glass Facades. ACM Transactions on Graphics (SIGGRAPH Asia) 39, 6 (2020), 208:1--208:16.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_15_1","volume-title":"Mike W. Taves, Joshua Arnott, Brendan C. Ward, et al.","author":"Gillies Sean","year":"2023","unstructured":"Sean Gillies, Casper van der Wel, Joris Van den Bossche, Mike W. Taves, Joshua Arnott, Brendan C. Ward, et al. 2023. Shapely. https:\/\/github.com\/shapely\/shapely"},{"key":"e_1_2_2_16_1","volume-title":"Petersen","author":"Gower Rebecca A. H.","year":"1998","unstructured":"Rebecca A. H. Gower, Agnes E. Heydtmann, and Henrik G. Petersen. 1998. LEGO: Automated Model Construction. 32nd European Study Group with Industry - Final Report (1998), 81--94."},{"key":"e_1_2_2_17_1","unstructured":"Branko Gr\u00fcnbaum and G. C. (Geoffrey Colin) Shephard. 1987. Tilings and Patterns. W.H.Freeman and Company."},{"key":"e_1_2_2_18_1","unstructured":"Gurobi Optimization LLC. 2023. Gurobi Optimizer Reference Manual. https:\/\/www.gurobi.com"},{"key":"e_1_2_2_19_1","volume-title":"Mark Wiebe, Pearu Peterson, Pierre G\u00e9rard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant.","author":"Harris Charles R.","year":"2020","unstructured":"Charles R. Harris, K. Jarrod Millman, St\u00e9fan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fern\u00e1ndez del R\u00edo, Mark Wiebe, Pearu Peterson, Pierre G\u00e9rard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020. Array programming with NumPy. Nature 585, 7825 (2020), 357--362."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383327"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-015-1072-4"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3378541"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459839"},{"key":"e_1_2_2_24_1","volume-title":"Salesin","author":"Kaplan Craig S.","year":"2000","unstructured":"Craig S. Kaplan and David H. Salesin. 2000. Escherization. In Proceedings of SIGGRAPH. 499--510."},{"key":"e_1_2_2_25_1","volume-title":"Proc. WSCG. 89--96","author":"Kim Jae Woo","year":"2014","unstructured":"Jae Woo Kim, Kyung Kyu Kang, and Ji Hyoung Lee. 2014. Survey on Automated LEGO Assembly Construction. In Proc. WSCG. 89--96."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/24725854.2020.1755067"},{"key":"e_1_2_2_27_1","unstructured":"Torkil Kollsker. 2020. Mathematical Models and Algorithms for Optimisation of the LEGO Construction Problem. Ph.D. Dissertation. Technical University of Denmark."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.07.004"},{"key":"e_1_2_2_29_1","volume-title":"Stidsen","author":"Kollsker Torkil","year":"2021","unstructured":"Torkil Kollsker and Thomas J. R. Stidsen. 2021. Optimisation and Static Equilibrium of Three-Dimensional LEGO Constructions. Operations Research Forum 2, 21 (2021)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12772"},{"key":"e_1_2_2_31_1","article-title":"Pyramid of Arclength Descriptor for Generating Collage of Shapes","volume":"35","author":"Kwan Kin Chung","year":"2016","unstructured":"Kin Chung Kwan, Lok Tsun Sinn, Chu Han, Tien-Tsin Wong, and Chi-Wing Fu. 2016. Pyramid of Arclength Descriptor for Generating Collage of Shapes. ACM Transactions on Graphics (SIGGRAPH Asia) 35, 6 (2016), 229:1--229:12.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2739480.2754667"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14490"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459843"},{"key":"e_1_2_2_35_1","article-title":"Legolization: Optimizing LEGO Designs","volume":"34","author":"Luo Sheng-Jie","year":"2015","unstructured":"Sheng-Jie Luo, Yonghao Yue, Chun-Kai Huang, Yu-Huan Chung, Sei Imai, Tomoyuki Nishita, and Bing-Yu Chen. 2015. Legolization: Optimizing LEGO Designs. ACM Transactions on Graphics (SIGGRAPH Asia) 34, 6 (2015), 222:1--222:12.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_36_1","volume-title":"https:\/\/brick.me\/ [Online","author":"Brick Brick","year":"2023","unstructured":"Brick me. 2022. Brick.me. https:\/\/brick.me\/ [Online; accessed 18-May-2023]."},{"key":"e_1_2_2_37_1","article-title":"Escherization with Large Deformations Based on As-Rigid-As-Possible Shape Modeling","volume":"41","author":"Nagata Yuichi","year":"2021","unstructured":"Yuichi Nagata and Shinji Imahori. 2021. Escherization with Large Deformations Based on As-Rigid-As-Possible Shape Modeling. ACM Transactions on Graphics (SIGGRAPH) 41, 2 (2021), 11:1--11:16.","journal-title":"ACM Transactions on Graphics (SIGGRAPH)"},{"key":"e_1_2_2_38_1","article-title":"Checkerboard Patterns with Black Rectangles","volume":"38","author":"Peng Chi-Han","year":"2019","unstructured":"Chi-Han Peng, Caigui Jiang, Peter Wonka, and Helmut Pottmann. 2019. Checkerboard Patterns with Black Rectangles. ACM Transactions on Graphics (SIGGRAPH Asia) 38, 6 (2019), 171:1--171:13.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1977.4309681"},{"key":"e_1_2_2_40_1","volume-title":"Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence. 1089","author":"Peysakhov Maxim","unstructured":"Maxim Peysakhov, Vlada Galinskaya, and William C. Regli. 2000. Representation and Evolution of Lego-Based Assemblies. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence. 1089."},{"key":"e_1_2_2_41_1","unstructured":"Eugene Smal. 2008. Automated Brick Sculpture Construction. Thesis. Stellenbosch : Stellenbosch University."},{"key":"e_1_2_2_42_1","volume-title":"Animosaics. In Proceedings of the 2005 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA '05)","author":"Smith Kaleigh","year":"2005","unstructured":"Kaleigh Smith, Yunjun Liu, and Allison Klein. 2005. Animosaics. In Proceedings of the 2005 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA '05). 201--208."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-012-0521-z"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","unstructured":"Ruocheng Wang Yunzhi Zhang Jiayuan Mao Chin-Yi Cheng and Jiajun Wu. 2022. Translating a Visual LEGO Manual to a Machine-Executable Plan. In Computer Vision - ECCV 2022 (Lecture Notes in Computer Science). 677--694.","DOI":"10.1007\/978-3-031-19836-6_38"},{"key":"e_1_2_2_45_1","volume-title":"Mosaic Art. https:\/\/brickmosaicdesigner.com\/ [Online","year":"2023","unstructured":"Xplicator. 2020. Mosaic Art. https:\/\/brickmosaicdesigner.com\/ [Online; accessed 18-May-2023]."},{"key":"e_1_2_2_46_1","first-page":"196","article-title":"Computational LEGO Technic Design","volume":"38","author":"Xu Hao","year":"2019","unstructured":"Hao Xu, Ka-Hei Hui, Chi-Wing Fu, and Hao Zhang. 2019. Computational LEGO Technic Design. ACM Transactions on Graphics (SIGGRAPH Asia) 38, 6 (2019), 196.","journal-title":"ACM Transactions on Graphics (SIGGRAPH Asia)"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392380"},{"key":"e_1_2_2_48_1","first-page":"1","article-title":"Structure-Based ASCII Art","volume":"52","author":"Xu Xuemiao","year":"2010","unstructured":"Xuemiao Xu, Linling Zhang, and Tien-Tsin Wong. 2010. Structure-Based ASCII Art. In Proceedings of SIGGRAPH. 52:1--52:10.","journal-title":"Proceedings of SIGGRAPH."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3095140.3095180"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13603"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T10:48:14Z","timestamp":1755773294000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,5]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,5]]}},"alternative-id":["10.1145\/3618306"],"URL":"https:\/\/doi.org\/10.1145\/3618306","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"}}]}}