“Making burr puzzles from 3D models” by Xin, Lai, Fu, Wong, He, et al. …

A 3D burr puzzle is a 3D model that consists of interlocking pieces with a single-key property. That is, when the puzzle is assembled, all the pieces are notched except one single key component which remains mobile. The intriguing property of the assembled burr puzzle is that it is stable, perfectly interlocked, without glue or screws, etc. Moreover, a burr puzzle consisting of a small number of pieces is still rather difficult to solve since the assembly must follow certain orders while the combinatorial complexity of the puzzle’s piece arrangements is extremely high.In this paper, we generalize the 6-piece orthogonal burr puzzle (a knot) to design and model burr puzzles from 3D models. Given a 3D input model, we first interactively embed a network of knots into the 3D shape. Our method automatically optimizes and arranges the orientation of each knot, and modifies pieces of adjacent knots with an appropriate connection type. Then, following the geometry of the embedded pieces, the entire 3D model is partitioned by splitting the solid while respecting the assembly motion of embedded pieces. The main technical challenge is to enforce the single-key property and ensure the assembly/disassembly remains feasible, as the puzzle pieces in a network of knots are highly interlocked. Lastly, we also present an automated approach to generate the visualizations of the puzzle assembly process.

1. Agrawala, M., Phan, D., Heiser, J., Haymaker, J., Klingner, J., Hanrahan, P., and Tversky, B. 2003. Designing effective step-by-step assembly instructions. ACM Trans. Graph. 22 (July), 828–837. Google ScholarDigital Library
2. Cho, T. S., Avidan, S., and Freeman, W. T. 2010. A probabilistic image jigsaw puzzle solver. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2010, 183–190.Google Scholar
3. Coffin, S. T. 2007. Geometric Puzzle Design. A. K. Peters.Google Scholar
4. Cutler, W. H. 1978. The six-piece burr. Journal of Recreational Mathematics 10, 4, 241–250.Google Scholar
5. Cutler, W. H., 1994. A computer analysis of all 6-piece burrs. Self published.Google Scholar
6. Cutler, W. H., 2000. Bill Cutler Puzzles, Inc. puzzle works. http://home.comcast.net/~billcutler/index.html.Google Scholar
7. Freeman, H., and Garder, L. 1964. Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE Transactions on Electronic Computers EC-13, 2, 118–127.Google ScholarCross Ref
8. Goldberg, D., Malon, C., and Bern, M. 2002. A global approach to automatic solution of jigsaw puzzles. In Proceedings of the Eighteenth Annual Symposium on Computational Geometry, ACM, New York, NY, USA, 82–87. Google Scholar
9. IBM Research, 1997. The burr puzzles site. http://www.research.ibm.com/BurrPuzzles/.Google Scholar
10. Kilian, M., Flöery, S., Chen, Z., Mitra, N. J., Sheffer, A., and Pottmann, H. 2008. Curved folding. ACM Tran. on Graphics (Proc. of SIGGRAPH) 27, 3. Google ScholarDigital Library
11. Kong, W., and Kimia, B. B. 2001. On solving 2D and 3D puzzles using curve matching. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2001.Google Scholar
12. Li, W., Agrawala, M., Curless, B., and Salesin, D. 2008. Automated generation of interactive 3D exploded view diagrams. ACM Trans. Graph. 27 (August), 101:1–101:7. Google ScholarDigital Library
13. Li, X.-Y., Shen, C.-H., Huang, S.-S., Ju, T., and Hu, S.-M. 2010. Popup: Automatic paper architectures from 3D models. ACM Tran. on Graphics (Proc. of SIGGRAPH) 29, 3. Article 111. Google ScholarDigital Library
14. Lo, K.-Y., Fu, C.-W., and Li, H. 2009. 3D Polyomino puzzle. ACM Tran. on Graphics (Proc. of SIGGRAPH Asia) 28, 5. Article 157. Google ScholarDigital Library
15. Mitani, J., and Suzuki, H. 2004. Making papercraft toys from meshes using strip-based approximate unfolding. ACM Tran. on Graphics (Proc. of SIGGRAPH) 23, 3, 259–263. Google ScholarDigital Library
16. Mitra, N. J., and Pauly, M. 2009. Shadow art. ACM Tran. on Graphics (Proc. of SIGGRAPH Asia) 28, 5. Article 156. Google Scholar
17. Mitra, N. J., Yang, Y.-L., Yan, D.-M., Li, W., and Agrawala, M. 2010. Illustrating how mechanical assemblies work. ACM Tran. on Graphics (Proc. of SIGGRAPH) 29, 3. Article 58. Google ScholarDigital Library
18. Mori, Y., and Igarashi, T. 2007. Plushie: an interactive design system for plush toys. ACM Tran. on Graphics (Proc. SIGGRAPH) 26, 3. Article 45. Google ScholarDigital Library
19. Weyrich, T., Deng, J., Barnes, C., Rusinkiewicz, S., and Finkelstein, A. 2007. Digital bas-relief from 3D scenes. ACM Tran. on Graphics (Proc. of SIGGRAPH) 26, 3. Article 32. Google ScholarDigital Library
20. Wolfson, H., Schonberg, E., Kalvin, A., and Lamdan, Y. 1988. Solving jigsaw puzzles by computer. Annals of Operations Research 12, 51–64. Google ScholarDigital Library