“3D polyomino puzzle”
Conference:
Type(s):
Title:
- 3D polyomino puzzle
Session/Category Title: 3D is fun
Presenter(s)/Author(s):
Moderator(s):
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
4. Clarenz, U., Litke, N., and Rumpf, M. 2004. Axioms and variational problems in surface parameterization. Computer Aided Geometric Design 21, 8, 727–749. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
8. Gardner, M. 1957. Mathematical games: About the remarkable similarity between the icosian game and the towers of Hanoi. Scientific American 196, 150–156.Google ScholarCross Ref
9. Golomb, S. W. 1954. Checkerboards and Polyominoes. The American Mathematical Monthly 61, 10 (Dec), 287–294.Google ScholarCross Ref
10. Golomb, S. W. 1994. Polyominoes: Puzzles, Patterns, Problems, and Packings. Princeton University Press. Revised edition.Google Scholar
11. Kaplan, C. S., and Salesin, D. H. 2000. Escherization. In Proc. of ACM SIGGRAPH 2000, 499–510. Google ScholarDigital Library
12. Kaplan, C. S. 2007. Semiregular patterns on surfaces. In SIGGRAPH ’07: ACM SIGGRAPH 2007 Sketches, 78. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
16. Ostromoukhov, V. 2007. Sampling with polyominoes. ACM Tran. on Graphics (Proc. SIGGRAPH) 26, 3. Article 78. Google ScholarDigital Library
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. Google ScholarDigital Library
18. Putter, G., 1998. Gerard’s universal polyomino solver 1.4. http://www.xs4all.nl/~gp/PolyominoSolver/Polyomino.html.Google Scholar
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. Google ScholarDigital Library
20. Shatz, I., Tal, A., and Leifman, G. 2006. Paper craft models from meshes. Visual Computer 22, 9, 825–834. Google ScholarDigital Library
21. Tarini, M., Hormann, K., Cignoni, P., and Montani, C. 2004. Polycube-maps. ACM Tran. on Graphics (Proc. of SIGGRAPH) 23, 3, 853–860. Google ScholarDigital Library
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. Google ScholarDigital Library
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. Google ScholarDigital Library
