“DESIA: a general framework for designing interlocking assemblies”
Conference:
Type(s):
Title:
- DESIA: a general framework for designing interlocking assemblies
Session/Category Title: Fun in geometry & fabrication
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Interlocking assemblies have a long history in the design of puzzles, furniture, architecture, and other complex geometric structures. The key defining property of interlocking assemblies is that all component parts are immobilized by their geometric arrangement, preventing the assembly from falling apart. Computer graphics research has recently contributed design tools that allow creating new interlocking assemblies. However, these tools focus on specific kinds of assemblies and explore only a limited space of interlocking configurations, which restricts their applicability for design.In this paper, we propose a new general framework for designing interlocking assemblies. The core idea is to represent part relationships with a family of base Directional Blocking Graphs and leverage efficient graph analysis tools to compute an interlocking arrangement of parts. This avoids the exponential complexity of brute-force search. Our algorithm iteratively constructs the geometry of assembly components, taking advantage of all existing blocking relations for constructing successive parts. As a result, our approach supports a wider range of assembly forms compared to previous methods and provides significantly more design flexibility. We show that our framework facilitates efficient design of complex interlocking assemblies, including new solutions that cannot be achieved by state of the art approaches.
References:
1. Maneesh Agrawala, Doantam Phan, Julie Heiser, John Haymaker, Jeff Klingner, Pat Hanrahan, and Barbara Tversky. 2003. Designing Effective Step-By-Step Assembly Instructions. ACM Trans. on Graph. (SIGGRAPH) 22, 3 (2003), 828–837. Google ScholarDigital Library
2. Marco Attene. 2015. Shapes In a Box: Disassembling 3D Objects for Effcient Packing and Fabrication. Computer Graphics Forum 34, 8 (2015), 64–76. Google ScholarDigital Library
3. Lujie Chen and Lawrence Sass. 2015. Fresh Press Modeler: A generative system for physically based low fidelity prototyping. Computers & Graphics 54 (2015), 157–165. Google ScholarDigital Library
4. Xuelin Chen, Hao Zhang, Jinjie Lin, Ruizhen Hu, Lin Lu, Qixing Huang, Bedrich Benes, Daniel Cohen-Or, and Baoquan Chen. 2015. Dapper: Decompose-and-pack for 3D Printing. ACM Trans. Graph. 34, 6 (2015), 213:1–213:12. Google ScholarDigital Library
5. Paolo Cignoni, Nico Pietroni, Luigi Malomo, and Roberto Scopigno. 2014. Field-aligned Mesh Joinery. ACM Trans. on Graph. 33, 1 (2014), 11:1–11:12. Google ScholarDigital Library
6. Fernando de Goes, Pierre Alliez, Houman Owhadi, and Mathieu Desbrun. 2013. On the Equilibrium of Simplicial Masonry Structures. ACM Trans. Graph. (SIGGRAPH) 32, 4 (2013). Article 93. Google ScholarDigital Library
7. Bansal Deepak. 2012. Sustainable Dry Interlocking Block Masonry Construction. In 15th International Brick and Block Masonry Conference.Google Scholar
8. Mario Deuss, Daniele Panozzo, Emily Whiting, Yang Liu, Philippe Block, Olga Sorkine-Hornung, and Mark Pauly. 2014. Assembling Self-Supporting Structures. ACM Trans. on Graph. (SIGGRAPH Asia) 33, 6 (2014). Article No. 214. Google ScholarDigital Library
9. Noah Duncan, Lap-Fai Yu, and Sai-Kit Yeung. 2016. Interchangeable Components for Hands-On Assembly Based Modelling. ACM Trans. on Graph. (SIGGRAPH Asia) 35, 6 (2016). Article No. 234. Google ScholarDigital Library
10. Ursula Frick, Tom Van Mele, and Philippe Block. 2015. Decomposing Three-Dimensional Shapes into Self-supporting, Discrete-Element Assemblies. In Modelling Behaviour. 187–201.Google Scholar
11. Chi-Wing Fu, Peng Song, Xiaoqi Yan, Lee Wei Yang, Pradeep Kumar Jayaraman, and Daniel Cohen-Or. 2015. Computational Interlocking Furniture Assembly. ACM Trans. on Graph. (SIGGRAPH) 34, 4 (2015). Article No. 91. Google ScholarDigital Library
12. Somayé Ghandi and Ellips Masehian. 2015. Review and taxonomies of assembly and disassembly path planning problems and approaches. Computer-Aided Design 67–68 (2015), 58–86. Google ScholarDigital Library
13. Jianwei Guo, Dong-Ming Yan, ErLi, Weiming Dong, Peter Wonka, and Xiaopeng Zhang. 2013. Illustrating the disassembly of 3D models. Computers & Graphics 37, 6 (2013), 574–581. Google ScholarDigital Library
14. Jingbin Hao, Liang Fang, and Robert E. Williams. 2011. An Efficient Curvature-based Partitioning of Large-scale STL Models. Rapid Prototyping Journal 17, 2 (2011), 116–127.Google ScholarCross Ref
15. Kristian Hildebrand, Bernd Bickel, and Marc Alexa. 2012. crdbrd: Shape Fabrication by Sliding Planar Slices. Comp. Graph. Forum 31, 2 (2012), 583–592. Google ScholarDigital Library
16. Ruizhen Hu, Honghua Li, Hao Zhang, and Daniel Cohen-Or. 2014. Approximate Pyramidal Shape Decomposition. ACM Trans. Graph. 33, 6 (2014), 213:1–213:12. Google ScholarDigital Library
17. Bongjin Koo, Jean Hergel, Sylvain Lefebvre, and Niloy J. Mitra. 2017. Towards Zero-Waste Furniture Design. IEEE Trans. Vis. & Comp. Graphics 23, 12 (2017), 2627–2640.Google ScholarCross Ref
18. Manfred Lau, Akira Ohgawara, Jun Mitani, and Takeo Igarashi. 2011. Converting 3D furniture models to fabricatable parts and connectors. ACM Trans. on Graph. (SIGGRAPH) 30, 4 (2011). Article No. 85. Google ScholarDigital Library
19. Wilmot Li, Maneesh Agrawala, Brian Curless, and David Salesin. 2008. Automated Generation of Interactive 3D Exploded View Diagrams. ACM Trans. on Graph. (SIGGRAPH) 27, 3 (2008). Article No. 101. Google ScholarDigital Library
20. Yang Liu, Pan Hao, John Snyder, Wenping Wang, and Baining Guo. 2013. Computing Self-Supporting Surfaces by Regular Triangulation. ACM Trans. Graph. (SIGGRAPH) 32, 4 (2013). Article 92. Google ScholarDigital Library
21. Linjie Luo, Ilya Baran, Szymon Rusinkiewicz, and Wojciech Matusik. 2012. Chopper: Partitioning Models into 3D-printable Parts. ACM Trans. Graph. 31, 6 (2012), 129:1–129:9. Google ScholarDigital Library
22. James McCrae, Nobuyuki Umetani, and Karan Singh. 2014. FlatFitFab: Interactive Modeling with Planar Sections. In ACM Symposium on User Interface Software and Technology. 13–22. Google ScholarDigital Library
23. Masaaki Miki, Takeo Igarashi, and Philippe Block. 2015. Parametric Self-supporting Surfaces via Direct Computation of Airy Stress Functions. ACM Trans. Graph. (SIGGRAPH) 34, 4 (2015). Article 89. Google ScholarDigital Library
24. Daniele Panozzo, Philippe Block, and Olga Sorkine-Hornung. 2013. Designing Unrein-forced Masonry Models. ACM Trans. on Graph. (SIGGRAPH) 32, 4 (2013). Article No. 91. Google ScholarDigital Library
25. Ronald Richter and Marc Alexa. 2015. Beam meshes. Computers & Graphics 53 (2015), 28–36. Google ScholarDigital Library
26. Matthias Rippmann, Tom Van Mele, Mariana Popescu, Edyta Augustynowicz, Tomás Méndez Echenagucia, Cristián Calvo Barentin, Ursula Frick, and Philippe Block. 2016. The Armadillo Vault: Computational design and digital fabrication of a freeform stone shell. In Advances in Architectural Geometry. 344–363.Google Scholar
27. Yuliy Schwartzburg and Mark Pauly. 2013. Fabrication-aware Design with Intersecting Planar Pieces. Comp. Graph. Forum 32, 2 (2013), 317–326.Google ScholarCross Ref
28. Tianjia Shao, Dongping Li, Yuliang Rong, Changxi Zheng, and Kun Zhou. 2016. Dynamic Furniture Modeling Through Assembly Instructions. ACM Trans. on Graph. (SIGGRAPH Asia) 35, 6 (2016). Article No. 172. Google ScholarDigital Library
29. Mélina Skouras, Stelian Coros, Eitan Grinspun, and Bernhard Thomaszewski. 2015. Interactive Surface Design with Interlocking Elements. ACM Trans. on Graph. (SIGGRAPH Asia) 34, 6 (2015). Article No. 224. Google ScholarDigital Library
30. A. S. Solodovnikov. 1979. Systems of Linear Inequalities. Mir Publishers.Google Scholar
31. Peng Song, Bailin Deng, Ziqi Wang, Zhichao Dong, Wei Li, Chi-Wing Fu, and Ligang Liu. 2016. CofiFab: Coarse-to-Fine Fabrication of Large 3D Objects. ACM Trans. on Graph. (SIGGRAPH) 35, 4 (2016). Article No. 45. Google ScholarDigital Library
32. Peng Song, Chi-Wing Fu, and Daniel Cohen-Or. 2012. Recursive Interlocking Puzzles. ACM Trans. on Graph. (SIGGRAPH Asia) 31, 6 (2012). Article No. 128. Google ScholarDigital Library
33. Peng Song, Chi-Wing Fu, Yueming Jin, Hongfei Xu, Ligang Liu, Pheng-Ann Heng, and Daniel Cohen-Or. 2017. Reconfigurable Interlocking Furniture. ACM Trans. on Graph. (SIGGRAPH Asia) 36, 6 (2017). Article No. 174. Google ScholarDigital Library
34. Peng Song, Zhongqi Fu, Ligang Liu, and Chi-Wing Fu. 2015. Printing 3D Objects with Interlocking Parts. Comp. Aided Geom. Des. 35–36 (2015), 137–148. Google ScholarDigital Library
35. Rob Stegmann. 2018. Rob’s Puzzle Page – Interlocking Puzzles. (2018). http://www.robspuzzlepage.com/interlocking.htm.Google Scholar
36. Alan Song-Ching Tai. 2012. Design For Assembly: A Computational Approach to Construct Interlocking Wooden Frames. Ph.D. Dissertation. Massachusetts Institute of Technology.Google Scholar
37. Chengcheng Tang, Xiang Sun, Alexandra Gomes, Johannes Wallner, and Helmut Pottmann. 2014. Form-finding with polyhedral meshes made simple. ACM Trans. Graph. (SIGGRAPH) 33, 4 (2014). Article 70. Google ScholarDigital Library
38. Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM J. Comput. 1, 2 (1972), 146–160.Google ScholarDigital Library
39. J. Vanek, J. A. Garcia Galicia, B. Benes, R. Měch, N. Carr, O. Stava, and G. S. Miller. 2014. PackMerger: A 3D Print Volume Optimizer. Computer Graphics Forum 33, 6 (2014), 322–332. Google ScholarDigital Library
40. E. Vouga, M. Höbinger, J. Wallner, and H. Pottmann. 2012. Design of self-supporting surfaces. ACM Trans. Graph. (SIGGRAPH) 31, 4 (2012), Article 87. Google ScholarDigital Library
41. Emily Whiting, John Ochsendorf, and Frédo Durand. 2009. Procedural Modeling of Structurally-Sound Masonry Buildings. ACM Trans. Graph. (SIGGRAPH Asia) 28, 5 (2009). Article 112. Google ScholarDigital Library
42. Randall H. Wilson. 1992. On Geometric Assembly Planning. Ph.D. Dissertation. Stanford University. Google ScholarDigital Library
43. Randall H. Wilson and Jean-Claude Latombe. 1994. Geometric Reasoning About Mechanical Assembly. Artificial Intelligence 71, 2 (1994), 371–396. Google ScholarDigital Library
44. Shi-Qing Xin, Chi-Fu Lai, Chi-Wing Fu, Tien-Tsin Wong, Ying He, and Daniel Cohen-Or. 2011. Making Burr Puzzles from 3D Models. ACM Trans. on Graph. (SIGGRAPH) 30, 4 (2011). Article No. 97. Google ScholarDigital Library
45. Jiaxian Yao, Danny M. Kaufman, Yotam Gingold, and Maneesh Agrawala. 2017b. Interactive Design and Stability Analysis of Decorative Joinery for Furniture. ACM Trans. on Graph. 36, 2 (2017). Article No. 20. Google ScholarDigital Library
46. Miaojun Yao, Zhili Chen, Weiwei Xu, and Huamin Wang. 2017a. Modeling, Evaluation and Optimization of Interlocking Shell Pieces. Comp. Graph. Forum 36, 7 (2017), 1–13.Google ScholarCross Ref
47. Yinan Zhang and Devin Balkcom. 2016. Interlocking Structure Assembly with Voxels. In IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems. 2173–2180.Google Scholar
48. Yinan Zhang, Emily Whiting, and Devin Balkcom. 2018. Assembling and Disassembling Planar Structures with Divisible and Atomic Components. IEEE Transactions on Automation Science and Engineering 15, 3 (2018), 945–954.Google ScholarCross Ref
