學術產出-Theses
Article View/Open
Publication Export
-
題名 具樂高®平滑化之立體模型風格化技術
3D LEGO® Generation Using Studs Not On Top Technique作者 張登凱
Chang, Teng-Kai貢獻者 紀明德
Chi, Ming-Te
張登凱
Chang, Teng-Kai關鍵詞 樂高
平滑化
風格化
LEGO
Stylization
Smooth-lize日期 2021 上傳時間 2-Sep-2021 16:51:41 (UTC+8) 摘要 自從樂高®積木發售以來，已經成為廣為人知的積木玩具之一，並且也成為了廣受歡迎的創作媒介。而在電腦科學領域，也有許多自動生成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 30cmhttps://www.coolshop.se/produkt/pokemon-mega-construx-jumbo-pikachu-30cm-fvk81/234P7E/[36] https://www.meshlab.net/ 描述 碩士
國立政治大學
資訊科學系
106753002資料來源 http://thesis.lib.nccu.edu.tw/record/#G0106753002 資料類型 thesis dc.contributor.advisor 紀明德 zh_TW dc.contributor.advisor Chi, Ming-Te en_US dc.contributor.author (Authors) 張登凱 zh_TW dc.contributor.author (Authors) Chang, Teng-Kai en_US dc.creator (作者) 張登凱 zh_TW dc.creator (作者) Chang, Teng-Kai en_US dc.date (日期) 2021 en_US dc.date.accessioned 2-Sep-2021 16:51:41 (UTC+8) - dc.date.available 2-Sep-2021 16:51:41 (UTC+8) - dc.date.issued (上傳時間) 2-Sep-2021 16:51:41 (UTC+8) - dc.identifier (Other Identifiers) G0106753002 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/136958 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 106753002 zh_TW dc.description.abstract (摘要) 自從樂高®積木發售以來，已經成為廣為人知的積木玩具之一，並且也成為了廣受歡迎的創作媒介。而在電腦科學領域，也有許多自動生成2D與3D結構的研究，但大多數僅使用樂高的基本磚進行建構，外觀上仍保留了體素化的特徵。本研究透過加入不同尺寸的斜面磚塊，改良生成的樂高結構，使結果的外觀更加貼近使用者輸入的模型，並且讓外觀更加平滑。由於上述目標，在建構樂高結構的過程中，需要考量與模型的相似性。我們使用有向距離場、填充率與表面向量作為依據，以選擇適合的樂高磚塊。我們以貪婪策略建構表面區域，而內部構造則使用基本磚塊建構出穩定的內部構造。另外，我們也提出使用轉向磚塊的方式建構出更加接近的結果。最後，我們使用不同的模型及嘗試不同的建構策略來驗證我們的做法。 zh_TW dc.description.abstract (摘要) 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. en_US dc.description.tableofcontents 第一章 緒論 1第二章 相關研究 42.1 樂高結構的表示方法 42.2 建構組合方式的演算法 62.3 風格化對應 7第三章 具平滑外觀的樂高建構 83.1 主要目標 83.2 主要挑戰 83.3 主要差異 93.4 使用磚組 9第四章 方法 124.1 系統架構 124.2 資料結構表示 144.3 模型前處理 154.3.1 表面區域 164.3.2 描述子 174.4 表面建構演算法 194.4.1 最佳磚選擇 204.4.2 斜磚選擇 204.5 鋸齒消除 244.6 隨機起始法 284.7 基因演算法 294.8 多方向堆積 304.9 結構穩定度 33第五章 結果與限制 345.1 策略比較 345.2 不同種類模型結果 395.3 系統環境 455.4 系統限制 45第六章 結論與未來展望 466.1 結論 466.2 未來展望 47參考文獻 48附錄A：其他立體模型結果 52附錄B：其他立體模型分數比較 54附錄C：平面模型分數比較 56 zh_TW dc.format.extent 6567409 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0106753002 en_US dc.subject (關鍵詞) 樂高 zh_TW dc.subject (關鍵詞) 平滑化 zh_TW dc.subject (關鍵詞) 風格化 zh_TW dc.subject (關鍵詞) LEGO en_US dc.subject (關鍵詞) Stylization en_US dc.subject (關鍵詞) Smooth-lize en_US dc.title (題名) 具樂高®平滑化之立體模型風格化技術 zh_TW dc.title (題名) 3D LEGO® Generation Using Studs Not On Top Technique en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [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 30cmhttps://www.coolshop.se/produkt/pokemon-mega-construx-jumbo-pikachu-30cm-fvk81/234P7E/[36] https://www.meshlab.net/ zh_TW dc.identifier.doi (DOI) 10.6814/NCCU202101407 en_US
