“Computational design of twisty joints and puzzles”
Conference:
Type(s):
Title:
- Computational design of twisty joints and puzzles
Session/Category Title: Fabrication & Function
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We present the first computational method that allows ordinary users to create complex twisty joints and puzzles inspired by the Rubik’s Cube mechanism. Given a user-supplied 3D model and a small subset of rotation axes, our method automatically adjusts those rotation axes and adds others to construct a “non-blocking” twisty joint in the shape of the 3D model. Our method outputs the shapes of pieces which can be directly 3D printed and assembled into an interlocking puzzle. We develop a group-theoretic approach to representing a wide class of twisty puzzles by establishing a connection between non-blocking twisty joints and the finite subgroups of the rotation group SO(3). The theoretical foundation enables us to build an efficient system for automatically completing the set of rotation axes and fast collision detection between pieces. We also generalize the Rubik’s Cube mechanism to a large family of twisty puzzles.
References:
1. Bächer, M., Bickel, B., James, D. L., and Pfister, H. 2012. Fabricating articulated characters from skinned meshes. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 4. Google ScholarDigital Library
2. Calì, J., Calian, D. A., Amati, C., Kleinberger, R., Steed, A., Kautz, J., and Weyrich, T. 2012. 3d-printing of non-assembly, articulated models. ACM Transactions on Graphics (TOG) 31, 6, 130. Google ScholarDigital Library
3. Ceylan, D., Li, W., Mitra, N. J., Agrawala, M., and Pauly, M. 2013. Designing and fabricating mechanical automata from mocap sequences. ACM Trans. Graph. 32, 6 (Nov.), 186:1–186:11. Google ScholarDigital Library
4. Chen, D., Sitthi-Amorn, P., Lan, J. T., and Matusik, W. 2013. Computing and fabricating multiplanar models. Computer Graphics Forum 32, 2, 305–315.Google ScholarCross Ref
5. Coros, S., Thomaszewski, B., Noris, G., Sueda, S., Forberg, M., Sumner, R. W., Matusik, W., and Bickel, B. 2013. Computational design of mechanical characters. ACM Trans. Graph. 32, 4 (July), 83:1–83:12. Google ScholarDigital Library
6. Ding, X., Lv, S., and Yang, Y. 2011. Configuration transformation theory from a chain-type reconfigurable modular mechanism-rubik’s snake. In 13th World Congress in Mechanism and Machine Science.Google Scholar
7. Golub, G. H., and Van Loan, C. F. 2012. Matrix computations, vol. 3. JHU Press.Google Scholar
8. Gower, J. C., and Dijksterhuis, G. B. 2004. Procrustes problems, vol. 3. Oxford University Press Oxford.Google Scholar
9. Igarashi, Y., Igarashi, T., and Mitani, J. 2012. Beady: interactive beadwork design and construction. ACM Transactions on Graphics (TOG) 31, 4, 49. Google ScholarDigital Library
10. Khoudary, S., 2000. Mechanism for independently moving segments of a three-dimensional object and applications thereof, May 11. WO Patent App. PCT/GB1999/003,643.Google Scholar
11. Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 4598, 671–680.Google Scholar
12. Lo, K.-Y., Fu, C.-W., and Li, H. 2009. 3d polyomino puzzle. ACM Trans. Graph. 28, 5 (Dec.), 157:1–157:8. Google ScholarDigital Library
13. Meyer, M., Desbrun, M., Schröder, P., and Barr, A. H. 2003. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and mathematics III. Springer.Google Scholar
14. Mori, Y., and Igarashi, T. 2007. Plushie: an interactive design system for plush toys. ACM Transactions on Graphics (TOG) 26, 3, 45. Google ScholarDigital Library
15. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3 (July), 471–478. Google ScholarDigital Library
16. Rivers, A. R., and James, D. L. 2007. Fastlsm: Fast lattice shape matching for robust real-time deformation. ACM Trans. Graph. 26, 3 (July). Google ScholarDigital Library
17. Rokicki, T., Kociemba, H., Davidson, M., and Dethridge, J., 2010. God’s number is 20. http://cube20.org/.Google Scholar
18. Scherphuis, J., 2003. Sphere. http://www.jaapsch.net/puzzles/sphere.htm.Google Scholar
19. Scherphuis, J., 2015. Mini cube, the 2X2X2 rubik’s cube. http://www.jaapsch.net/puzzles/cube2.htm.Google Scholar
20. Shewchuk, J. R. 1996. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In Applied computational geometry towards geometric engineering. Springer, 203–222. Google ScholarDigital Library
21. Skouras, M., Thomaszewski, B., Kaufmann, P., Garg, A., Bickel, B., Grinspun, E., and Gross, M. 2014. Designing inflatable structures. ACM Transactions on Graphics (TOG) 33, 4, 63. Google ScholarDigital Library
22. Song, P., Fu, C.-W., and Cohen-Or, D. 2012. Recursive interlocking puzzles. ACM Trans. Graph. 31, 6 (Nov.), 128:1–128:10. Google ScholarDigital Library
23. Sorkine, O., Cohen-Or, D., Lipman, Y., Alexa, M., Rössl, C., and Seidel, H.-P. 2004. Laplacian surface editing. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, ACM, New York, NY, USA, SGP ’04, 175–184. Google ScholarDigital Library
24. Thistlethwaite, M. B., 1981. The 45–52 move strategy. http://www.jaapsch.net/puzzles/thistle.htm.Google Scholar
25. Thomaszewski, B., Coros, S., Gauge, D., Megaro, V., Grinspun, E., and Gross, M. 2014. Computational design of linkage-based characters. ACM Trans. Graph. 33, 4 (July), 64:1–64:9. Google ScholarDigital Library
26. Thurston, W. P., and Levy, S. 1997. Three-dimensional geometry and topology, vol. 1. Princeton University Press.Google Scholar
27. Umetani, N., Kaufman, D. M., Igarashi, T., and Grinspun, E. 2011. Sensitive couture for interactive garment modeling and editing. In ACM SIGGRAPH 2011 Papers, ACM, New York, NY, USA, SIGGRAPH ’11, 90:1–90:12. Google ScholarDigital Library
28. Umetani, N., Igarashi, T., and Mitra, N. J. 2012. Guided exploration of physically valid shapes for furniture design. ACM Trans. Graph. 31, 4 (July), 86:1–86:11. Google ScholarDigital Library
29. Verdes, P., 2004. Cubic logic toy, Feb. 12. WO Patent App. WO/2004/103497.Google Scholar
30. Wahba, G. 1965. A least squares estimate of satellite attitude. SIAM review 7, 3, 409–409.Google Scholar
31. Xin, S., Lai, C.-F., Fu, C.-W., Wong, T.-T., He, Y., and Cohen-Or, D. 2011. Making burr puzzles from 3d models. In ACM Transactions on Graphics (TOG), vol. 30, ACM, 97. Google ScholarDigital Library
32. Zhou, Y., Sueda, S., Matusik, W., and Shamir, A. 2014. Boxelization: Folding 3d objects into boxes. ACM Trans. Graph. 33, 4 (July), 71:1–71:8. Google ScholarDigital Library
