PuzLock

Interlocking puzzles are three-dimensional (3D) structures where the assembly of its individual pieces lock together to form a final stable shape. Apart from their novelty, these structures have many useful applications, as they do away with the need for screws, adhesives, and hooks, potentially simplifying many manufacturing processes. However, finding a valid interlocking decomposition, given some solid volume as an input shape, is a complex task. Historically, they were hand-designed through much effort, while the advent of technology has seen several time-consuming and exhaustive computational methods proposed. Consequently, Song et al . (2012) developed a unique approach to the problem which was significantly more efficient. It focused on a specific subset of the field called recursive interlocking, wherein there is exactly one order of assembly, and the structure remains interlocking at each sequential step. Our project focuses on implementing and proposing improvements to this algorithm.  

Our implementation takes the desired dimensions, number of pieces and a 3D .STL file as input. However, this file is first pre-processed, producing a voxelized representation. The voxelized model is then parsed through the puzzle generator, which uses an intricate system of blockages and anchors to first generate a ‘key’ piece, then the remaining pieces, consecutively.

Thorough testing, via both 3D printing and aggregated runs, confirmed the functionality and demonstrated that processing times varied with a complexity of approximately O(nlogn), with regard to both the number of pieces and the specified dimensions. Shape complexity affects processing times in a similar fashion. 

While our implementation produces valid results in reasonable time, we identified several portions where both multi-threading and GPU-optimization could be applied in order to improve performance. In future work, we also aim to use novel approaches to remove the voxelization requirement and produce true-to-surface models.