“Computational design of twisty joints and puzzles”

  • ©Timothy Sun and Changxi Zheng

Conference:


Type:


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


ACM Digital Library Publication: