Recursive interlocking puzzles: rendering and 3D printing
In this paper, we detail the development process involved in generating computational 3D models and 3D printing them. This process involves merging, shrinking, and rendering mesh models, flowing through the system as either a triangle mesh model or a voxelized grid, depending on the type of functionality invoked. We also observe how merging and shrinking mesh models is necessary for 3D printed models to interconnect without locking together due to the compactness of the printing material.
Recursive interlocking puzzles: generating 3D interlocking puzzle pieces from 3D arrays
This paper focuses on a technique for generating 3D (three-dimensional) interlocking puzzles. The technique is adapted from a research paper published in 2012 entitled ‘Recursively Interlocking Puzzles’ which contains a 3D puzzle piece generating algorithm written by Peng Song, Chi-Wing Fu and Daniel Cohen-Or. Together, they solved the mystery of the governing mechanics behind recursively interlocking puzzles. Their algorithm follows a top-down constructive approach which offers a much-needed speedup over pre-existing exhaustive search approaches. Such 3D puzzles have a large number of (potential) applications. For example, they can be used to create games and furniture which can be assembled and/or disassembled. This paper focuses specifically on the application of 3D interlocking puzzles to the fast-growing field of 3D printing.
Conclusions and Results
Rendering and 3D printing:
Algorithm design. Each of the algoritms highlighted above are well designed and perform as intended. Algorithm 1 is designed to
iteratively merge new cubes to an accumulating mesh composed of
previously-rendered cubes. The algorithm takes into account that a
new cube will have to merge with at least one other cube in the
accumulating mesh and, therefore, adjoining triangles have to be
rremoved and duplicate vertices must be removed. Algorithm 2 is
designed to iteratively translate each of the vertices of the
accumulating mesh. The algorithm covers the whole process from
identifying surrounding triangles, to normalizing, snapping, and
finally translating the vertex.
Implementation. The implementation of each algorithm is
relatively straightforward. The difficulty lies in checking for
accuracy in each of the intermediary phases of the implementation
of each functionality. The primary method of testing is tracing,
which involves standard output error printing of the relevant
information required for verifying the accuracy of a particular
process. This method is coupled with a paper-written set of tests
used to visually confirm the tracing outputs.
Generating 3D interlocking puzzle pieces from 3D arrays
Interlocking puzzles are a largely unexplored topic with many
possible applications. This paper describes the coding process
undertaken to derive 3D interlocking puzzles using 3D arrays as
the primary data structure. It helps bridge the gap between a
high-level and lower-level algorithm which is easier to understand
from a programming perspective. The Song et al. technique of
generating recursively interlocking puzzles is fairly complex
and requires a lot of explanation. One cannot understand it by
simply reading their paper once or twice. Although we failed to
generate a set of valid key and secondary puzzle pieces, we are
well aware of the errors we made in understanding and implementing
their technique. The lack of time was the main drawback.
The primary objective of 3D printing valid puzzle pieces can still
be accomplished by hard-coding puzzle pieces in 3D arrays. The IO
class would assist us in using these 3D arrays to generate files which
are served as input to the renderer for post-processing. Going
forward, we aim to improve the accuracy of the implementation
described in section 5 of this paper. Once this implementation yields
valid sets of key and secondary puzzle pieces, one may focus on the
efficiency aspect. The efficiency aspect requires that one should
accomplish speedup over the original algorithm. We hope this paper
inspires more insight into the topic of recursively interlocking 3D
puzzles. May we continue to “do the other things, not because they
are easy, but because they are hard”. May we continue to recursively
unlock a future of possibilities.
Figure 1: A visualization of a key piece generated by our implementation on the renderer supplied. This key piece was generated from a 3D array of 1s and 0s, later represented in a file format recognized by the renderer.
