A Graph-based Method for Understanding Interlocking Assemblies
Event details
| Date | 31.08.2018 |
| Hour | 10:00 › 12:00 |
| Speaker | Ziqi Wang |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam (retake)
Exam president: Prof. Wenzel Jakob
Thesis advisor: Prof. Mark Pauly
Co-examiner: Prof. Pierre Dillenbourg
Abstract
Computing a feasible disassembly sequence of parts for a given 3D structure is a fundamental research topic in geometric reasoning. Its inverse problem, which is to create the geometry of a 3D assembly according to predefined constraints on the parts disassembly order, attracts more and more attention from computer graphics community. This report focuses on 3D interlocking assemblies where all component parts can be disassembled after removing a single key part. Though several computational methods for designing interlocking assemblies such as puzzle and furniture has recently been contributed, the interlocking mechanism has not yet been thoroughly investigated and the full search space of interlocking configurations has never been explored, restricting applicability for the design.
In this report, I propose a graph-based method for modeling the interlocking mechanism. The core idea is to represent part blocking relationships with a family of "Directional Blocking Graphs" (DBGs). By utilizing graph analysis tools in classic graph theory, my approach builds a connection between an interlocking assembly and the connectivity of its DBGs. Based on this connection, I propose an efficient algorithm to test interlocking with polynomial time complexity which enables the ability to explore interlocking configurations that are not possible by the state of the art. As a result, my method has potential to lead to a more efficient and flexible computational tool for designing interlocking assemblies of different forms.
Background papers
Recursive Interlocking Puzzles. ACM TransPeng Song, Chi-Wing Fu, and Daniel Cohen-Or. 2012. ACM Trans. on Graph. (SIGGRAPH Asia) 31, 6 (2012). Article No. 128.
Augmentation problems. Kapali P Eswaran and R Endre Tarjan. 1976. SIAM J. Comput. 5, 4 (1976), 653-665.
Geometric Reasoning About Mechanical Assembly, by Randall H. Wilson and Jean-Claude Latombe. 1994. Artificial Intelligence 71, 2 (1994), 371-396.
Exam president: Prof. Wenzel Jakob
Thesis advisor: Prof. Mark Pauly
Co-examiner: Prof. Pierre Dillenbourg
Abstract
Computing a feasible disassembly sequence of parts for a given 3D structure is a fundamental research topic in geometric reasoning. Its inverse problem, which is to create the geometry of a 3D assembly according to predefined constraints on the parts disassembly order, attracts more and more attention from computer graphics community. This report focuses on 3D interlocking assemblies where all component parts can be disassembled after removing a single key part. Though several computational methods for designing interlocking assemblies such as puzzle and furniture has recently been contributed, the interlocking mechanism has not yet been thoroughly investigated and the full search space of interlocking configurations has never been explored, restricting applicability for the design.
In this report, I propose a graph-based method for modeling the interlocking mechanism. The core idea is to represent part blocking relationships with a family of "Directional Blocking Graphs" (DBGs). By utilizing graph analysis tools in classic graph theory, my approach builds a connection between an interlocking assembly and the connectivity of its DBGs. Based on this connection, I propose an efficient algorithm to test interlocking with polynomial time complexity which enables the ability to explore interlocking configurations that are not possible by the state of the art. As a result, my method has potential to lead to a more efficient and flexible computational tool for designing interlocking assemblies of different forms.
Background papers
Recursive Interlocking Puzzles. ACM TransPeng Song, Chi-Wing Fu, and Daniel Cohen-Or. 2012. ACM Trans. on Graph. (SIGGRAPH Asia) 31, 6 (2012). Article No. 128.
Augmentation problems. Kapali P Eswaran and R Endre Tarjan. 1976. SIAM J. Comput. 5, 4 (1976), 653-665.
Geometric Reasoning About Mechanical Assembly, by Randall H. Wilson and Jean-Claude Latombe. 1994. Artificial Intelligence 71, 2 (1994), 371-396.
Practical information
- General public
- Free
Contact
- EDIC - [email protected]