“Legolization: optimizing LEGO designs”
Conference:
Type(s):
Title:
- Legolization: optimizing LEGO designs
Session/Category Title: Specialized Design
Presenter(s)/Author(s):
Abstract:
Building LEGO sculptures requires accounting for the target object’s shape, colors, and stability. In particular, finding a good layout of LEGO bricks that prevents the sculpture from collapsing (due to its own weight) is usually challenging, and it becomes increasingly difficult as the target object becomes larger or more complex. We devise a force-based analysis for estimating physical stability of a given sculpture. Unlike previous techniques for Legolization, which typically use heuristic-based metrics for stability estimation, our force-based metric gives 1) an ordering in the strength so that we know which structure is more stable, and 2) a threshold for stability so that we know which one is stable enough. In addition, our stability analysis tells us the weak portion of the sculpture. Building atop our stability analysis, we present a layout refinement algorithm that iteratively improves the structure around the weak portion, allowing for automatic generation of a LEGO brick layout from a given 3D model, accounting for color information, required workload (in terms of the number of bricks) and physical stability. We demonstrate the success of our method with real LEGO sculptures built up from a wide variety of 3D models, and compare against previous methods.
References:
1. Baraff, D. 1994. Fast contact force computation for nonpenetrating rigid bodies. In Proc. ACM SIGGRAPH 1994, 23–34.
2. Chen, H., and Fang, S. 1998. Fast voxelization of three-dimensional synthetic objects. J. Graph. Tools 3, 4, 33–45.
3. Clague, K., Agullo, M., and Hassing, L. 2002. LEGO software power tools: with LDraw, MLCad, and LPub. Syngress.
4. Courtney, T., Bliss, S., and Herrera, A. 2003. Virtual LEGO: the official LDraw.org guide to LDraw tools for Windows. No Starch Press.
5. Erleben, K. 2007. Velocity-based shock propagation for multibody dynamics animation. ACM Trans. Graph. 26, 2, 12:1–12:20.
6. Garg, A., Sageman-Furnas, A. O., Deng, B., Yue, Y., Grinspun, E., Pauly, M., and Wardetzky, M. 2014. Wire mesh design. ACM Trans. Graph. (Proc. SIGGRAPH 2014) 33, 4, 66:1–66:12.
7. Gascón, J., Zurdo, J. S., and Otaduy, M. A. 2010. Constraint-based simulation of adhesive contact. In Proc. SCA 2010, 39–44.
8. Gower, R., Heydtmann, A., and Petersen, H. 1998. LEGO: automated model construction. In Proc. 32nd European Study Group with Industry, 81–94.
9. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Non-convex rigid bodies with stacking. ACM Trans. Graph. (Proc. SIGGRAPH 2003) 22, 3, 871–878.
10. Hildebrand, K., Bickel, B., and Alexa, M. 2012. crdbrd: shape fabrication by sliding planar slices. Comput. Graph. Forum (Proc. EUROGRAPHICS 2012) 31, 2–3, 583–592.
11. Hopcroft, J., and Tarjan, R. 1973. Efficient algorithms for graph manipulation. Communications of the ACM 16, 6, 372–378.
12. Jakob, W. 2010. Mitsuba renderer. http://www.mitsubarenderer.org.
13. Jessiman, J. 1995. LDraw, LEGO CAD software package. http://beta.ldraw.org/.
14. Kaufman, D. M., Edmunds, T., and Pai, D. K. 2005. Fast frictional dynamics for rigid bodies. ACM Trans. Graph. (Proc. SIGGRAPH 2005) 24, 3, 946–956.
15. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered projections for frictional contact in multibody systems. ACM Trans. Graph. (Proc. SIGGRAPH Asia 2008) 27, 5, 164:1–164:11.
16. Kilian, M., Flöry, S., Chen, Z., Mitra, N. J., Sheffer, A., and Pottmann, H. 2008. Curved folding. ACM Trans. Graph. (Proc. SIGGRAPH 2008) 27, 3, 75:1–75:9.
17. Kim, J.-W., Kang, K.-K., and Lee, J.-H. 2014. Survey on automated LEGO assembly construction. In Proc. WSCG 2014, 89–96.
18. Li, X.-Y., Shen, C.-H., Huang, S.-S., Ju, T., and Hu, S.-M. 2010. Popup: automatic paper architectures from 3D models. ACM Trans. Graph. (Proc. SIGGRAPH 2010) 29, 4, 111:1–111:9.
19. Li, X.-Y., Ju, T., Gu, Y., and Hu, S.-M. 2011. A geometric study of v-style pop-ups: theories and algorithms. ACM Trans. Graph. (Proc. SIGGRAPH 2011) 30, 4, 98:1–98:10.
20. Mitani, J., and Suzuki, H. 2004. Making papercraft toys from meshes using strip-based approximate unfolding. ACM Trans. Graph. (Proc. SIGGRAPH 2004) 23, 3, 259–263.
21. Mitra, N. J., and Pauly, M. 2009. Shadow art. ACM Trans. Graph. (Proc. SIGGRAPH Asia 2009) 28, 5, 156:1–156:7.
22. Mori, Y., and Igarashi, T. 2007. Plushie: an interactive design system for plush toys. ACM Trans. Graph. (Proc. SIGGRAPH 2007) 26, 3, 45:1–45:8.
23. Mueller, S., Mohr, T., Guenther, K., Frohnhofen, J., and Baudisch, P. 2014. faBrickation: fast 3D printing of functional objects by integrating construction kit building blocks. In Proc. SIGCHI 2014, 3827–3834.
24. Panozzo, D., Block, P., and Sorkine-Hornung, O. 2013. Designing unreinforced masonry models. ACM Trans. Graph. (Proc. SIGGRAPH 2013) 32, 4, 91:1–91:12.
25. Petrovic, P. 2001. Solving the LEGO brick layout problem using evolutionary algorithms. In Proc. NIK 2001.
26. Prévost, R., Whiting, E., Lefebvre, S., and Sorkine-Hornung, O. 2013. Make it stand: Balancing shapes for 3D fabrication. ACM Trans. Graph. (Proc. SIGGRAPH 2013) 32, 4, 81:1–81:10.
27. Schulz, A., Shamir, A., Levin, D. I. W., Sitthi-amorn, P., and Matusik, W. 2014. Design and fabrication by example. ACM Trans. Graph. (Proc. SIGGRAPH 2014) 33, 4, 62:1–62:11.
28. Schwartzburg, Y., Testuz, R., Tagliasacchi, A., and Pauly, M. 2014. High-contrast computational caustic design. ACM Trans. Graph. (Proc. SIGGRAPH 2014) 33, 4, 74:1–74:11.
29. Shigeo, T., Wu, H.-Y., Saw, S. H., Lin, C.-C., and Yen, H.-C. 2011. Optimized topological surgery for unfolding 3D meshes. Comput. Graph. Forum (Proc. Pacific Graphics 2011) 30, 7, 2077–2086.
30. Silva, L. F., Pamplona, V. F., and Comba, J. L. 2009. Legolizer: a real-time system for modeling and rendering LEGO representations of boundary models. In Proc. SIBGRAPI 2009, 17–23.
31. Skouras, M., Thomaszewski, B., Kaufmann, P., Garg, A., Bickel, B., Grinspun, E., and Gross, M. 2014. Designing inflatable structures. ACM Trans. Graph. (Proc. SIGGRAPH 2014) 33, 4, 63:1–63:10.
32. Smith, B., Kaufman, D. M., Vouga, E., Tamstorf, R., and Grinspun, E. 2012. Reflections on simultaneous impact. ACM Trans. Graph. (Proc. SIGGRAPH 2012) 31, 4, 106:1–106:12.
33. Song, P., Fu, C.-W., and Cohen-Or, D. 2012. Recursive interlocking puzzles. ACM Trans. Graph. (Proc. SIGGRAPH Asia 2012) 31, 6, 128:1–128:10.
34. Stava, O., Vanek, J., Benes, B., Carr, N., and Měch, R. 2012. Stress relief: Improving structural strength of 3D printable objects. ACM Trans. Graph. (Proc. SIGGRAPH 2012) 31, 4, 48:1–48:11.
35. Tachi, T. 2010. Origamizing polyhedral surfaces. IEEE TVCG 16, 2, 298–311.
36. Testuz, R., Schwartzburg, Y., and Pauly, M. 2013. Automatic generation of constructable brick sculptures. In Eurographics 2013 Short papers, 81–84.
37. The LEGO Group, and Google. 2012. Build with Chrome. http://www.buildwithchrome.com/static/map/.
38. The LEGO Group. 2010. Company profile: an introduction to The LEGO Group 2010.
39. The LEGO Group. 2012. LEGO digital designer. http://ldd.lego.com/.
40. Thomaszewski, B., Coros, S., Gauge, D., Megaro, V., Grinspun, E., and Gross, M. 2014. Computational design of linkage-based characters. ACM Trans. Graph. (Proc. SIGGRAPH 2014) 33, 4, 64:1–64:9.
41. Umetani, N., Igarashi, T., and Mitra, N. J. 2012. Guided exploration of physically valid shapes for furniture design. ACM Trans. Graph. (Proc. SIGGRAPH 2012) 31, 4, 86:1–86:11.
42. van Zijl, L., and Smal, E. 2008. Cellular automata with cell clustering. In Proc. Automata 2008, 425–440.
43. VidimčE, K., Wang, S.-P., Ragan-Kelley, J., and Matusik, W. 2013. OpenFab: A programmable pipeline for multi-material fabrication. ACM Trans. Graph. (Proc. SIGGRAPH 2013) 32, 4, 136:1–136:12.
44. Vouga, E., Höbinger, M., Wallner, J., and Pottmann, H. 2012. Design of self-supporting surfaces. ACM Trans. Graph. (Proc. SIGGRAPH 2012) 31, 4, 87:1–87:11.
45. Waßmann, M., and Weicker, K. 2012. Maximum flow networks for stability analysis of LEGO structures. In Proceedings of the 20th Annual European Conference on Algorithms, 813–824.
46. Weyrich, T., Deng, J., Barnes, C., Rusinkiewicz, S., and Finkelstein, A. 2007. Digital bas-relief from 3D scenes. ACM Trans. Graph. (Proc. SIGGRAPH 2007) 26, 3, 32:1–32:8.
47. Whiting, E., Ochsendorf, J., and Durand, F. 2009. Procedural modeling of structurally-sound masonry buildings. ACM Trans. Graph. (Proc. SIGGRAPH Asia 2009) 28, 5, 112:1–112:9.
48. Whiting, E., Shin, H., Wang, R., Ochsendorf, J., and Durand, F. 2012. Structural optimization of 3D masonry buildings. ACM Trans. Graph. (Proc. SIGGRAPH Asia 2012) 31, 6, 159:1–159:11.
49. Yue, Y., Iwasaki, K., Chen, B.-Y., Dobashi, Y., and Nishita, T. 2012. Pixel art with refracted light by rearrangeable sticks. Comput. Graph. Forum (Proc. EUROGRAPHICS 2012) 31, 2–3, 575–582.
50. Yue, Y., Iwasaki, K., Chen, B.-Y., Dobashi, Y., and Nishita, T. 2014. Poisson-based continuous surface generation for goal-based caustics. ACM Trans. Graph. (Presented at SIGGRAPH 2014) 33, 3, 31:1–31:7.
