Computational Design of High-level Interlocking Puzzles

This repo is an implementation of Computational Design of High-level Interlocking Puzzles [Chen et al. 2022]. Commercial licensing is available upon request. If you have any problems when using this code, you can contact me any time through 1998rlchen@gmail.com.

If you make use of this repo in your scientific work, please cite our paper. For your convenience, you can use the following bibtex snippet:

@article {Chen-2022-HighLevelPuzzle,
author   = {Rulin Chen and Ziqi Wang and Peng Song and Bernd Bickel},
title        = {Computational Design of High-level Interlocking Puzzles},
journal   = {ACM Transactions on Graphics (SIGGRAPH 2022)},
volume = {41},
number = {4},
pages   = {150:1 -- 150:15},
year      = {2022}}

Table of Contents

• About
• Getting Started
• GUI Interface
• Create a level-12 Cube Puzzle by Yourself !
• Authors
• Acknowledgments

About

This repo presents a computational approach to design high-level interlocking puzzles. We implemented our computational design tool in C++ and libigl [Jacobson et al. 2018] on a desktop computer with 3.6 GHz 8-Core Intel processor and 16 GB RAM.

Getting Started

Our code can be ran on MacOS and Unbuntu (Linux) system. First clone the repository, run CMake to generate Makefiles or CMake/Visual Studio project files, and the rest should just work automatically.

Compilation

• MacOS and Ubuntu(Linux):

$ cd [current folder path]
$ mkdir build
$ cd build
$ cmake ..
$ make -j 16

The integer following make -j is the number of threads supported by your CPU architecture. Replace it with your optimal value.

• Windows: currently unavailable.

GUI Interface

The control panel is shown below. There are 6 components in the control panel: Parameter Control, Status Bar, High Level Puzzle Constructor, Modify High Level Puzzle, Assembly State Viewer and Render Control.

• Parameter Control

  Piece Number Determine the number of pieces K.

  Level of Difficulty Determine the level of difficulty L. The program will keep running until constructing a puzzle with level of difficulty equal or higher than L.

  Seed Number With the same seed number, users can regenerate the same puzzle as before.

  Puzzle Tolerance This parameter is set for fabrication only, which can control the gap between pieces.

• High Level Puzzle Constructor

  Read Our program can read 2 types of input files: .puz and .vol file.

  Construct Construct the K piece level-L puzzle with given import volume.

  Save Puz Save puzzle generated by our program.

  Reset Reset all parameters.

• Modify High Level Puzzle

  Target Level (Modify) The target level after modifying current puzzle.

  Modifying Start modifying currrent puzzle.

• Assembly State Viewer

  Disassembly Step Determine the disassembly step.

  Prev Previous disassembly step.

  Next Next disassembly step.

• Render Control

  Control the object visualization state.

• Status Bar

  Puzzle State Indicate state (e.g. interlocking and deadlocking) of current puzzle.

  Level of Difficulty Level of difficult of current puzzle.

Create a level-12 Cube Puzzle by Yourself !

These instructions gives an example to you of how to use our code to generate high-level interlocking puzzle by yourself. To generate high-level interlocking puzzles efficiently, it is usually necessary to modify the puzzle pieces. For example, to generate a level-12 cube puzzle, we first constrct a level-6 cube puzzle and modify it to level-12 puzzle; see Section 4 in our paper for detailed explanation of construction and modifying algorithm.

Step 1: import a volume

Import a Cube_5x5x5_E1.vol volume file by clicking read button.

Step 2: create a level-6 cube puzzle

Set the Level of Difficulty as 6 and click the Construct button to create a piece-4 level-6 cube puzzle.

Step 3: modifying to reach a level-12 puzzle

Set the Target Level (Modify) as 12 and click the Modify button to start modifying.

Step 4: visualize disassembly steps

Click the Next to visualize how to disassemble the current puzzle.

Step 5: save puzzle for fabrication

Set the Puzzle Tolerance greater than 0 to create gaps between pieces. Here we suggest to set 0.005. Lastly, you can click Save Puz to save the .puz file and .obj files of each piece that can be used for fabrication.

Authors

• Rulin Chen
• Ziqi Wang
• Peng Song
• Bernd Bickel

Acknowledgements

We thank the reviewers for the valuable comments, David Gontier for sharing the source code of the baseline design approach, and Christian Hafner for proofreading the paper. This work was supported by the SUTD start-up Research Grant (Number: SRG ISTD 2019 148), and the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 715767 - MATERIALIZABLE).