3D polyomino puzzle

Abstract

This paper presents a computer-aided geometric design approach to realize a new genre of 3D puzzle, namely the 3D Polyomino puzzle. We base our puzzle pieces on the family of 2D shapes known as polyominoes in recreational mathematics, and construct the 3D puzzle model by covering its geometry with polyominolike shapes. We first apply quad-based surface parametrization to the input solid, and tile the parametrized surface with polyominoes. Then, we construct a nonintersecting offset surface inside the input solid and shape the puzzle pieces to fit inside a thick shell volume. Finally, we develop a family of associated techniques for precisely constructing the geometry of individual puzzle pieces, including the ring-based ordering scheme, the motion space analysis technique, and the tab and blank construction method. The final completed puzzle model is guaranteed to be not only buildable, but also interlocking and maintainable.

References

1. Alexander, H. 1975. The computer plotter and the 17 ornamental design types. In SIGGRAPH 1975, 160--167.
2. Boier-Martin, I., Rushmeier, H., and Jin, J. 2004. Parameterization of triangle meshes over quadrilateral domains. In Proc. of Eurographics/ACM SIGGRAPH symp. on Geom. proc., 193--203.
3. Buss, S. R., and Fillmore, J. P. 2001. Spherical averages and applications to spherical splines and interpolation. ACM Tran. on Graphics 20, 2, 95--126.
4. Clarenz, U., Litke, N., and Rumpf, M. 2004. Axioms and variational problems in surface parameterization. Computer Aided Geometric Design 21, 8, 727--749.
5. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. ACM Tran. on Graphics (Proc. of SIGGRAPH) 25, 3, 1057--1066.
6. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In Proc. of ACM SIGGRAPH 95, 173--182.
7. Floater, M. S., and Hormann, K. 2004. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling, Springer, N. A. Dodgson, M. S. Floater, and M. A. Sabin, Eds., 259--284.
8. Gardner, M. 1957. Mathematical games: About the remarkable similarity between the icosian game and the towers of Hanoi. Scientific American 196, 150--156.
9. Golomb, S. W. 1954. Checkerboards and Polyominoes. The American Mathematical Monthly 61, 10 (Dec), 287--294.
10. Golomb, S. W. 1994. Polyominoes: Puzzles, Patterns, Problems, and Packings. Princeton University Press. Revised edition.
11. Kaplan, C. S., and Salesin, D. H. 2000. Escherization. In Proc. of ACM SIGGRAPH 2000, 499--510.
12. Kaplan, C. S. 2007. Semiregular patterns on surfaces. In SIGGRAPH '07: ACM SIGGRAPH 2007 Sketches, 78.
13. Massarwi, F., Gotsman, C., and Elber, G. 2007. Papercraft models using generalized cylinders. In 5th Pacific Conf. on Comp. Graphics and App., 148--157.
14. 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.
15. Mori, Y., and Igarashi, T. 2007. Plushie: an interactive design system for plush toys. ACM Tran. on Graphics (Proc. SIGGRAPH) 26, 3. Article 45.
16. Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Tran. on Graphics (Proc. SIGGRAPH) 26, 3. Article 78.
17. Peng, J., Kristjansson, D., and Zorin, D. 2004. Interactive modeling of topologically complex geometric detail. ACM Tran. on Graphics (Proc. of SIGGRAPH) 23, 3, 635--643.
18. Putter, G., 1998. Gerard's universal polyomino solver 1.4. http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html.
19. Ray, N., Li, W. C., Lévy, B., Sheffer, A., and Alliez, P. 2006. Periodic global parameterization. ACM Tran. on Graphics 25, 4, 1460--1485.
20. Shatz, I., Tal, A., and Leifman, G. 2006. Paper craft models from meshes. Visual Computer 22, 9, 825--834.
21. Tarini, M., Hormann, K., Cignoni, P., and Montani, C. 2004. Polycube-maps. ACM Tran. on Graphics (Proc. of SIGGRAPH) 23, 3, 853--860.
22. Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. of Eurographics symp. on geom. proc., 201--210.
23. 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.

Index Terms

• Applied computing

  • Arts and humanities

    • Architecture (buildings)

      • Computer-aided design

  • Computers in other domains

    • Personal computers and PC applications

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design