“Computational design of high-level interlocking puzzles” by Wang, Song and Bickel
Conference:
Type(s):
Title:
- Computational design of high-level interlocking puzzles
Presenter(s)/Author(s):
Abstract:
Interlocking puzzles are intriguing geometric games where the puzzle pieces are held together based on their geometric arrangement, preventing the puzzle from falling apart. High-level-of-difficulty, or simply high-level, interlocking puzzles are a subclass of interlocking puzzles that require multiple moves to take out the first subassembly from the puzzle. Solving a high-level interlocking puzzle is a challenging task since one has to explore many different configurations of the puzzle pieces until reaching a configuration where the first subassembly can be taken out. Designing a high-level interlocking puzzle with a user-specified level of difficulty is even harder since the puzzle pieces have to be interlocking in all the configurations before the first subassembly is taken out.In this paper, we present a computational approach to design high-level interlocking puzzles. The core idea is to represent all possible configurations of an interlocking puzzle as well as transitions among these configurations using a rooted, undirected graph called a disassembly graph and leverage this graph to find a disassembly plan that requires a minimal number of moves to take out the first subassembly from the puzzle. At the design stage, our algorithm iteratively constructs the geometry of each puzzle piece to expand the disassembly graph incrementally, aiming to achieve a user-specified level of difficulty. We show that our approach allows efficient generation of high-level interlocking puzzles of various shape complexities, including new solutions not attainable 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. Bernd Bickel, Paolo Cignoni, Luigi Malomo, and Nico Pietroni. 2018. State of the Art on Stylized Fabrication. Comp. Graph. Forum 37, 6 (2018), 325–342.Google ScholarCross Ref
3. A. Bourjault. 1984. Contribution a une approche méthodologique de l’assemblage automatisé: Elaboration automatique des séquences opératiores. Ph.D. Dissertation. L’Université de Franche-Comté.Google Scholar
4. Stewart T. Coffin. 2006. Geometric Puzzle Design. A. K. Peters.Google Scholar
5. Bill Cutler. 1988. Holey 6-Piece Burr! A Collection and Computer Analysis of Unusual Designs. http://billcutlerpuzzles.com/docs/H6PB/index.html.Google Scholar
6. Ruta Desai, James McCann, and Stelian Coros. 2018. Assembly-aware Design of Printable Electromechanical Devices. In Proc. ACM UIST. 457–472.Google ScholarDigital Library
7. 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), 214:1–214:10.Google ScholarDigital Library
8. Noah Duncan, Lap-Fai Yu, Sai-Kit Yeung, and Demetri Terzopoulos. 2017. Approximate Dissections. ACM Trans. on Graph. (SIGGRAPH Asia) 36, 6 (2017), 182:1–182:14.Google Scholar
9. Gershon Elber and Myung-Soo Kim. 2022. Synthesis of 3D Jigsaw Puzzles over Freeform 2-Manifolds. Comp. & Graph. (SMI) 102 (2022), 339–348.Google ScholarDigital Library
10. Thomas L. De Fazio and Daniel E. Whitney. 1987. Simplified Generation of All Mechanical Assembly Sequences. IEEE Journal on Robotics and Automation RA-3, 6 (1987), 640–658.Google ScholarCross Ref
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), 91:1–91:11.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 Scholar
13. David Gontier. 2020. Multi-level Interlocking Cubes. https://www.ceremade.dauphine.fr/~gontier/Puzzles/InterlockingPuzzles/interlocking.html.Google Scholar
14. Jianwei Guo, Dong-Ming Yan, Er Li, Weiming Dong, Peter Wonka, and Xiaopeng Zhang. 2013. Illustrating the Disassembly of 3D Models. Comp. & Graph. (SMI) 37, 6 (2013), 574–581.Google ScholarDigital Library
15. D. Halperin, J.-C. Latombe, and R. H. Wilson. 2000. A General Framework for Assembly Planning: The Motion Space Approach. Algorithmica 26, 3–4 (2000), 577–601.Google ScholarCross Ref
16. IBM Research. 1997. The burr puzzles site. https://www.cs.brandeis.edu/~storer/JimPuzzles/BURR/000BURR/READING/IbmPage.pdf.Google Scholar
17. Alec Jacobson, Daniele Panozzo, et al. 2018. libigl: A simple C++ geometry processing library. https://libigl.github.io/.Google Scholar
18. P. Jiménez. 2013. Survey on Assembly Sequencing: A Combinatorial and Geometrical Perspective. Journal of Intelligent Manufacturing 24, 2 (2013), 235–250.Google ScholarDigital Library
19. Gene T.C. Kao, Axel Kórner, Daniel Sonntag, Long Nguyen, Achim Menges, and Jan Knippers. 2017. Assembly-aware Design of Masonry Shell Structures: A Computational Approach. In Proceedings of the International Association for Shell and Spatial Structures Symposium.Google Scholar
20. Lydia Kavraki, Jean-Claude Latombe, and Randall H. Wilson. 1993. On the Complexity of Assembly Partitioning. Inform. Process. Lett. 48, 5 (1993), 229–235.Google ScholarDigital Library
21. Bernhard Kerbl, Denis Kalkofen, Markus Steinberger, and Dieter Schmalstieg. 2015. Interactive Disassembly Planning for Complex Objects. Comp. Graph. Forum (Eurographics) 34, 2 (2015), 287–297.Google ScholarDigital Library
22. Naoki Kita and Kazunori Miyata. 2020. Computational Design of Polyomino Puzzles. The Visual Computer (CGI) (2020), 1–11.Google Scholar
23. Naoki Kita and Takafumi Saito. 2020. Computational Design of Generalized Centrifugal Puzzles. Comp. & Graph. (SMI) 90 (2020), 21–28.Google ScholarDigital Library
24. Duc Thanh Le, Juan Cortés, and Thierry Siméon. 2009. A Path Planning Approach to (Dis)Assembly Sequencing. In Proc. Int. Conf. on Automation Science and Engineering. 286–291.Google ScholarCross Ref
25. Shuhua Li, Ali Mahdavi-amiri, Ruizhen Hu, Han Liu, Chanqing Zou, Oliver Van Kaick, Xiuping Liu, Hui Huang, and Hao Zhang. 2018. Construction and Fabrication of Reversible Shape Transforms. ACM Trans. on Graph. (SIGGRAPH Asia) 37, 6 (2018), 190:1–190:14.Google Scholar
26. Kui-Yip Lo, Chi-Wing Fu, and Hongwei Li. 2009. 3D Polyomino Puzzle. ACM Trans. on Graph. (SIGGRAPH Asia) 28, 5 (2009), 157:1–157:8.Google Scholar
27. Ellips Masehian and Somayé Ghandi. 2020. ASPPR: A New Assembly Sequence and Path Planner/Replanner for Monotone and Nonmonotone Assembly Planning. Computer-Aided Design 123 (2020), 102828:1–102828:22.Google Scholar
28. Ellips Masehian and Somayé Ghandi. 2021. Assembly Sequence and Path Planning for Monotone and Nonmonotone Assemblies with Rigid and Flexible Parts. Robotics and Computer-Integrated Manufacturing 72 (2021), 102180:1–102180:23.Google Scholar
29. Luiz S. Homem De Mello and Arthur C. Sanderson. 1990. AND/OR Graph Representation of Assembly Plans. IEEE Transactions on Robotics and Automation 6, 2 (1990), 188–199.Google ScholarCross Ref
30. Fakir S. Nooruddin and Greg Turk. 2003. Simplification and Repair of Polygonal Models Using Volumetric Techniques. IEEE Trans. Vis. & Comp. Graphics 9, 2 (2003), 191–205.Google ScholarDigital Library
31. Andreas Röver. 2013. Burr Tools. http://burrtools.sourceforge.net/.Google Scholar
32. 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), 45:1–45:11.Google ScholarDigital Library
33. Peng Song, Chi-Wing Fu, and Daniel Cohen-Or. 2012. Recursive Interlocking Puzzles. ACM Trans. on Graph. (SIGGRAPH Asia) 31, 6 (2012), 128:1–128:10.Google ScholarDigital Library
34. 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), 174:1–174:14.Google Scholar
35. Peng Song, Zhongqi Fu, Ligang Liu, and Chi-Wing Fu. 2015. Printing 3D Objects with Interlocking Parts. Comp. Aided Geom. Des. (GMP) 35–36 (2015), 137–148.Google Scholar
36. Olga Sorkine and Marc Alexa. 2007. As-Rigid-As-Possible Surface Modeling. In Proc. Eurographics Symposium on Geometry Processing. 109–116.Google Scholar
37. Timothy Sun and Changxi Zheng. 2015. Computational Design of Twisty Joints and Puzzles. ACM Trans. on Graph. (SIGGRAPH) 34, 4 (2015), 101:1–101:11.Google ScholarDigital Library
38. Keke Tang, Peng Song, Xiaofei Wang, Bailin Deng, Chi-Wing Fu, and Ligang Liu. 2019. Computational Design of Steady 3D Dissection Puzzles. Comp. Graph. Forum (Eurographics) 38, 2 (2019), 291–303.Google ScholarCross Ref
39. Jungfu Tsao and Jan Wolter. 1993. Assembly Planning with Intermediate States. In Proc. IEEE Int. Conf. on Robotics and Automation. 71–76.Google ScholarCross Ref
40. Ziqi Wang, Peng Song, Florin Isvoranu, and Mark Pauly. 2019. Design and Structural Optimization of Topological Interlocking Assemblies. ACM Trans. on Graph. (SIGGRAPH Asia) 38, 6 (2019), 193:1–193:13.Google Scholar
41. Ziqi Wang, Peng Song, and Mark Pauly. 2018. DESIA: A General Framework for Designing Interlocking Assemblies. ACM Trans. on Graph. (SIGGRAPH Asia) 37, 6 (2018), 191:1–191:14.Google Scholar
42. Ziqi Wang, Peng Song, and Mark Pauly. 2021. State of the Art on Computational Design of Assemblies with Rigid Parts. Comp. Graph. Forum (Eurographics) 40, 2 (2021), 633–657.Google ScholarCross Ref
43. Jan D. Wolter. 1991. A Combinatorial Analysis of Enumerative Data Structures for Assembly Planning. In Proc. IEEE Int. Conf. on Robotics and Automation. 611–618.Google ScholarCross Ref
44. Chenming Wu, Haisen Zhao, Chandrakana Nandi, Jeffrey I. Lipton, Zachary Tatlock, and Adriana Schulz. 2019. Carpentry Compiler. ACM Trans. on Graph. (SIGGRAPH Asia) 38, 6 (2019), 195:1–195:14.Google Scholar
45. 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), 97:1–97:8.Google ScholarDigital Library
46. Miaojun Yao, Zhili Chen, Weiwei Xu, and Huamin Wang. 2017. Modeling, Evaluation and Optimization of Interlocking Shell Pieces. Comp. Graph. Forum (Pacific Graphics) 36, 7 (2017), 1–13.Google ScholarCross Ref
47. Yinan Zhang and Devin Balkcom. 2016. Interlocking Structure Assembly with Voxels. In Proc. IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems. 2173–2180.Google ScholarDigital Library
48. Yinan Zhang, Yotto Koga, and Devin Balkcom. 2021. Interlocking Block Assembly With Robots. IEEE Transactions on Automation Science and Engineering 18, 3 (2021), 902–916.Google ScholarCross Ref
49. Yahan Zhou and Rui Wang. 2012. An Algorithm for Creating Geometric Dissection Puzzles. In Proc. Bridges Towson: Mathematics, Music, Art, Architecture, Culture. 49–56.Google Scholar