自從樂高®積木發售以來，已經成為廣為人知的積木玩具之一，並且也成為了廣受歡迎的創作媒介。而在電腦科學領域，也有許多自動生成2D與3D結構的研究，但大多數僅使用樂高的基本磚進行建構，外觀上仍保留了體素化的特徵。本研究透過加入不同尺寸的斜面磚塊，改良生成的樂高結構，使結果的外觀更加貼近使用者輸入的模型，並且讓外觀更加平滑。由於上述目標，在建構樂高結構的過程中，需要考量與模型的相似性。我們使用有向距離場、填充率與表面向量作為依據，以選擇適合的樂高磚塊。我們以貪婪策略建構表面區域，而內部構造則使用基本磚塊建構出穩定的內部構造。另外，我們也提出使用轉向磚塊的方式建構出更加接近的結果。最後，我們使用不同的模型及嘗試不同的建構策略來驗證我們的做法。

Since Lego® bricks was introduced in 1940s, it has become one of the most well-known brick systems. In computer science, there are many researches showing that we can automatically generate lego structures in both 2D and 3D aspects. However, former researches mainly focus on basic bricks, which only uses basic bricks for construction. The final results usually have a voxelized appearance. We propose a method to improve model similarity and smoothness by using a variety of slope bricks. To construct a lego model that looks like the input model, we need to consider the similarity between brick and partial surface of the model. We use signed distance field, fill rate, and surface normal to determine the best bricks for the partial surface. Because total possible lego brick combinations are growing exponentially, it’s very hard to test all possible combinations. We use a greedy strategy to generate our results. For inner area, we use the core blocks and basic bricks to generate the inner structure. Finally, we use a random start strategy and genetic algorithm to evaluate our performance. We also use variable models as our input to test our method.

[1] Grim Yun, Cheolseong Park, Heekyung Yang, and Kyungha Min. 2017. Legorization with multi-height bricks from silhouette-fitted voxelization. In Proceedings of CGI ’17, Yokohama, Japan, June 27-30, 2017, 6 pages.
[2] Kim, J.-W., Kang, K.-K. & Lee, J.-H. 2014. Survey on automated LEGO assembly construction. In Proc. WSCG 2014, 89-96.
[3] Kuo, M.-H., Lin, Y.-E., Chu, H.-K., Lee, R.-R., & Yang, Y.-L. (2015, October). Pixel2Brick: Constructing Brick Sculptures from Pixel Art. In Computer Graphics Forum (Vol. 34, No. 7, pp. 339-348).
[4] Luo, S.-J., Yue, Y., Huang, C.-K., Chung, Y.-H., Imai, S., Nishita, T., & Chen, B.-Y. (2015). Legolization: optimizing lego designs.In ACM Transactions on Graphics (TOG), 34(6), 222.
[5] Peysakhov M., Regli W. Using Assembly Representations to Enable Evolutionary Design of Lego Structures.In Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 17:155-68, 2003.
[6] Lambrecht, B. Voxelization of boundary representations using oriented LEGO plates. University of California, Berkeley, 2006.
[7] Zhang, M., Mitani, J., Kanamori, Y., & Fukui, Y. (2014). Blocklizer. ACM SIGGRAPH 2014 Posters on - SIGGRAPH 14. doi:10.1145/2614217.2614269
[8] Stephenson, B. (2016, June). A multi-phase search approach to the LEGO construction problem. In Ninth Annual Symposium on Combinatorial Search
[9] Zhang, M., Igarashi, Y., Kanamori, Y., & Mitani, J. (2015, August). Designing mini block artwork from colored mesh. In International Symposium on Smart Graphics (pp. 3-15). Springer, Cham.
[10] Sun, T., Zheng, C., Zhang, Y., & Yin, C. (2015). Computational design of twisty joints and puzzles. ACM Trans. Graph., 34(4), 101-1.
[11] Ono, S., Alexis, A., & Chang, Y. (2013). Automatic generation of LEGO from the polygonal data. In International workshop on advanced image technology (pp. 262-267).
[12] Testuz, Romain Pierre ; Schwartzburg, Yuliy ; Pauly, Mark(2013)
Automatic Generation of Constructable Brick Sculptures. In Eurographics 2013-Short Papers(pp. 81-84)
[13] Smal E. Automated Brick Sculpture Construction. MS. Thesis, The University of Stellenbosch, 2008.
[14] Edoardo Alberto Dominici, Nico Schertler, Jonathan Griffin, Shayan Hoshyari, Leonid Sigal, and Alla Sheffer. 2020. PolyFit: perception-aligned vectorization of raster clip-art via intermediate polygonal fitting. ACM Trans. Graph. 39, 4, Article 77 (July 2020), 16 pages.
[15] Gower, R. A. H., Heydtmann, A. E., & Petersen, H. G. (1998). LEGO: Automated Model Construction. In 32nd European Study Group with Industry - Final Report (pp. 81-94). Jens Gravesen and Poul Hjorth, Department of Mathematics, DTU.
[16] Kim, J., Chung, H., Cho, M., Park, J.Combinatorial (2020) 3D shape generation via sequential assembly arXiv, . https://arxiv.org/abs/2004.07414
[17] Takuya Kozaki, Hiroshi Tedenuma, Takashi Maekawa,(2016)Automatic generation of LEGO building instructions from multiple photographic images of real objects,Computer-Aided Design,Volume 70,Pages 13-22,
[18] Kollsker, Torkil & Malaguti, Enrico, (2021).Models and algorithms for optimising two-dimensional LEGO constructions European Journal of Operational Research, Elsevier, vol. 289(1), pages 270-284.
[19] Eilers, S. (2016) The LEGO counting problem American Mathematical Monthly, 123 (5), pp. 415-426.
[20] Lee, S., Kim, J., Kim, J.W., Moon, B.-R. (2015)Finding an optimal LEGO® brick layout of voxelized 3D object using a genetic algorithm GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference, pp. 1215-1222.
[21] Cohen-Or, D., Kaufman, A. (1995) Fundamentals of surface voxelization Graphical Models and Image Processing, 57 (6), pp. 453-461.
[22] Petrovic, P. (2001) Solving LEGO brick layout problem using evolutionary algorithms Proceedings to Norwegian Conference on Computer Science.
[23] Timcenko, O. (1998) LEGO: How to build with LEGO 32nd European Study Group with Industry - Final Report, pp. xix-xxi.
[24] Clague, K., Agullo, M., Hassing, L.(2002) LEGO Software Power Tools: With LDraw, MLCad, and LPub.
[25] Silva, L.F.M.S., Pamplona, V.F., Comba, J.L.D. (2009) Legolizer: A real-time system for modeling and rendering LEGO® representations of boundary models Proceedings of SIBGRAPI 2009 - 22nd Brazilian Symposium on Computer Graphics and Image Processing, art. no. 5395263, pp. 17-23
[26] Van Zijl, L., Smal, E. (2008) Cellular automata with cell clustering Proc. Automata 2008, pp. 425-440
[27] Michael Birsak, Florian Rist, Peter Wonka, Przemyslaw Musialski(2018): String Art: Towards Computational Fabrication of String Images. Comput. Graph. Forum 37(2): 263-274
[28] LEGO Pikachu Sculpture (LifeSize):
https://www.flickr.com/photos/alanboar/31397386242/
[29] LEGO Pikachu Pokemon:
https://www.flickr.com/photos/alanboar/28983446100/
[30] Birds – 21301 | ideas | Lego shop:
https://shop.lego.com/en-US/product/Birds-21301
[31] Hokusai - Great wave off Kanagawa – left:
https://www.flickr.com/photos/koffiemoc/32975781208
[32] Lego MOC Brickheadz - Legend of Zelda – Link:
https://picclick.it/Lego-MOC-Brickheadz-Legend-of-Zelda-163435635896.html
[33] Moulding colour palette 2016: https://brickset.com/colours/chart
[34] Gal, R., Sorkine, O., Popa, T., Sheffer, A., Cohen-Or, D. (2007): 3d collage: Expressive non- realistic modeling. In: NPAR 2007, pp. 7–14
[35] Pokemon - Mega Construx Jumbo Pikachu 30cm
https://www.coolshop.se/produkt/pokemon-mega-construx-jumbo-pikachu-30cm-fvk81/234P7E/
[36] https://www.meshlab.net/