research-article

Computational design of reconfigurables

Authors:

Eitan GrinspunAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 35, Issue 4

Article No.: 90, Pages 1 - 14

https://doi.org/10.1145/2897824.2925900

Published: 11 July 2016 Publication History

Abstract

A reconfigurable is an object or collection of objects whose transformation between various states defines its functionality or aesthetic appeal. For example, consider a mechanical assembly composed of interlocking pieces, a transforming folding bicycle, or a space-saving arrangement of apartment furniture. Unlike traditional computer-aided design of static objects, specialized tools are required to address problems unique to the computational design and revision of objects undergoing rigid transformations. Collisions and interpenetrations as objects transition from one configuration to another prevent the physical realization of a design. We present a software environment intended to support fluid interactive design of reconfigurables, featuring tools that identify, visualize, monitor and resolve infeasible configurations. We demonstrate the versatility of the environment on a number of examples spanning mechanical systems, urban dwelling, and interlocking puzzles, some of which we then realize via additive manufacturing.

Spatial-temporal information about collisions between objects is presented to the designer according to a cascading order of precedence. A designer may quickly determine when, and then where, and then how objects are colliding. This precedence guides the design and implementation of our four-dimensional spacetime bounding volume hierarchy for interactive-rate collision detection. On screen, the designer experiences a suite of interactive visualization and monitoring tools during editing: timeline notifications of new collisions, picture-in-picture windows for tracking collisions and suggestive hints for contact resolution. Contacts too tedious to remove manually can be eliminated automatically via our proposed constrained numerical optimization and swept-volume carving.

Supplementary Material

MP4 File (a90.mp4)

Download
303.85 MB

References

[1]

Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29, 4 (July), 82:1--82:10.

Digital Library

[2]

Bächer, M., Bickel, B., James, D. L., and Pfister, H. 2012. Fabricating articulated characters from skinned meshes. ACM Trans. Graph.

Digital Library

[3]

Bächer, M., Whiting, E., Bickel, B., and Sorkine-Hornung, O. 2014. Spin-it: Optimizing moment of inertia for spinnable objects. ACM Trans. Graph..

Digital Library

[4]

Bächer, M., Coros, S., and Thomaszewski, B. 2015. Linkedit: interactive linkage editing using symbolic kinematics. ACM Trans. Graph..

Digital Library

[5]

Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. ACM Trans. Graph. 22, 3, 862--870.

Digital Library

[6]

Bernstein, G. L., and Wojtan, C. 2013. Putting holes in holey geometry: Topology change for arbitrary surfaces. ACM Trans. Graph..

Digital Library

[7]

Bharaj, G., Levin, D. I. W., Tompkin, J., Fei, Y., Pfister, H., Matusik, W., and Zheng, C. 2015. Computational design of metallophone contact sounds. ACM Trans. Graph..

Digital Library

[8]

Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3 (July), 594--603.

Digital Library

[9]

Cameron, S. 1990. Collision detection by four-dimensional intersection testing. IEEE T. Robotics and Automation.

[10]

Campen, M., and Kobbelt, L. 2010. Polygonal boundary evaluation of minkowski sums and swept volumes. Comput. Graph. Forum.

[11]

Ceylan, D., Li, W., Mitra, N. J., Agrawala, M., and Pauly, M. 2013. Designing and fabricating mechanical automata from mocap sequences. ACM Trans. Graph..

Digital Library

[12]

Erleben, K. 2004. Stable, Robust, and Versatile Multibody Dynamics Animation. PhD thesis, Univ. of Copenhagen.

[13]

Everitt, C. 2001. Interactive order-independent transparency. Tech. rep., nVidia Corp.

[14]

Gal, R., Sorkine, O., Mitra, N. J., and Cohen-Or, D. 2009. iWIRES: An analyze-and-edit approach to shape manipulation. ACM Trans. Graph..

Digital Library

[15]

Garg, A., Sageman-Furnas, A. O., Deng, B., Yue, Y., Grinspun, E., Pauly, M., and Wardetzky, M. 2014. Wire mesh design. ACM Trans. Graph..

Digital Library

[16]

Guibas, L. J. 1998. Kinetic data structures--a state of the art report. Proc. WAFR.

Digital Library

[17]

Harmon, D., Panozzo, D., Sorkine, O., and Zorin, D. 2011. Interference-aware geometric modeling. ACM Trans. Graph..

Digital Library

[18]

Igarashi, Y., Igarashi, T., and Mitani, J. 2012. Beady: Interactive beadwork design and construction. ACM Trans. Graph..

Digital Library

[19]

Jacobson, A., Panozzo, D., et al., 2013. libigl: A simple C++ geometry processing library. http://igl.ethz.ch/projects/libigl/.

[20]

Joubert, N., Roberts, M., Truong, A., Berthouzoz, F., and Hanrahan, P. 2015. An interactive tool for designing quadrotor camera shots. ACM Trans. Graph..

Digital Library

[21]

Kavraki, L. E., Švestka, P., Latombe, J.-C., and Over-mars, M. H. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE TRA.

[22]

Klosowski, J. T., Held, M., Mitchell, J. S., Sowizral, H., and Zikan, K. 1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE TVCG.

Digital Library

[23]

Koo, B., Li, W., Yao, J., Agrawala, M., and Mitra, N. J. 2014. Creating works-like prototypes of mechanical objects. ACM Trans. Graph..

Digital Library

[24]

Li, H., Alhashim, I., Zhang, H., Shamir, A., and Cohen-Or, D. 2012. Stackabilization. ACM Trans. Graph..

Digital Library

[25]

Liu, S., Jacobson, A., and Gingold, Y. 2014. Skinning cubic Bézier splines and Catmull-Clark subdivision surfaces. ACM Trans. Graph..

Digital Library

[26]

Liu, T., Hertzmann, A., Li, W., and Funkhouser, T. 2015. Style compatibility for 3D furniture models. ACM Trans. Graph..

Digital Library

[27]

Merrell, P., Schkufza, E., Li, Z., Agrawala, M., and Koltun, V. 2011. Interactive furniture layout using interior design guidelines. ACM Trans. Graph..

Digital Library

[28]

Pavic, D., and Kobbelt, L. 2008. High-resolution volumetric computation of offset surfaces with feature preservation. Comput. Graph. Forum.

[29]

Peternell, M., Pottmann, H., Steiner, T., and Zhao, H. 2005. Swept volumes. Computer-Aided Design Appl..

[30]

Popović, J., Seitz, S. M., Erdmann, M., Popović, Z., and Witkin, A. 2000. Interactive manipulation of rigid body simulations. In Proc. SIGGRAPH.

Digital Library

[31]

Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press.

Digital Library

[32]

Schroeder, W. J., Lorensen, W. E., and Linthicum, S. 1994. Implicit modeling of swept surfaces and volumes. In Proc. of the Conference on Visualization.

Digital Library

[33]

Schüller, C., Panozzo, D., and Sorkine-Hornung, O. 2014. Appearance-mimicking surfaces. ACM Trans. Graph..

Digital Library

[34]

Schulz, A., Shamir, A., Levin, D. I. W., Sitthi-Amorn, P., and Matusik, W. 2014. Design and fabrication by example. ACM Trans. Graph..

Digital Library

[35]

Secord, A., Lu, J., Finkelstein, A., Singh, M., and Nealen, A. 2011. Perceptual models of viewpoint preference. ACM Trans. Graph..

Digital Library

[36]

Shao, M.-Z., and Badler, N. 1996. Spherical sampling by archimedes' theorem. Tech. rep., Univ. of Penn.

[37]

Shoemake, K. 1992. Uniform random rotations. In Graphics Gems III. Morgan Kaufmann.

Digital Library

[38]

Skouras, M., Thomaszewski, B., Bickel, B., and Gross, M. 2012. Computational design of rubber balloons. Comput. Graph. Forum.

Digital Library

[39]

Skouras, M., Thomaszewski, B., Coros, S., Bickel, B., and Gross, M. 2013. Computational design of actuated deformable characters. ACM Trans. Graph..

Digital Library

[40]

Snibbe, S. S. 1995. A direct manipulation interface for 3d computer animation. Comput. Graph. Forum.

Digital Library

[41]

Sun, T., and Zheng, C. 2015. Computational design of twisty joints and puzzles. ACM Trans. Graph..

Digital Library

[42]

Tang, M., Manocha, D., Yoon, S.-E., Du, P., Heo, J.-P., and Tong, R.-F. 2011. Volccd: Fast continuous collision culling between deforming volume meshes. ACM Trans. Graph. 30, 5 (Oct.), 111:1--111:15.

Digital Library

[43]

Teschner, M., Kimmerle, S., Zachmann, G., Heidelberger, B., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., and Strasser, W. 2004. Collision detection for deformable objects. In Proc. Eurographics (STAR).

[44]

Thomaszewski, B., Coros, S., Gauge, D., Megaro, V., Grinspun, E., and Gross, M. 2014. Computational design of linkage-based characters. ACM Trans. Graph..

Digital Library

[45]

Umetani, N., Kaufman, D. M., Igarashi, T., and Grinspun, E. 2011. Sensitive couture for interactive garment editing and modeling. ACM Trans. Graph..

Digital Library

[46]

Umetani, N., Igarashi, T., and Mitra, N. J. 2012. Guided exploration of physically valid shapes for furniture design. ACM Trans. Graph..

Digital Library

[47]

Umetani, N., Koyama, Y., Schmidt, R., and Igarashi, T. 2014. Pteromys: Interactive design and optimization of free-formed free-flight model airplanes. ACM Trans. Graph..

Digital Library

[48]

Volino, P., and Magnenat-Thalmann, N. 2006. Resolving surface collisions through intersection contour minimization. ACM Trans. Graph..

Digital Library

[49]

Wang, B., Faure, F., and Pai, D. K. 2012. Adaptive image-based intersection volume. ACM Trans. Graph. (Proc. SIGGRAPH) 31, 4.

Digital Library

[50]

Weld, J. D., and Leu, M. C. 1990. Geometric representation of swept volumes with application to polyhedral objects. Int. J. Rob. Res..

Digital Library

[51]

Witkin, A., and Kass, M. 1988. Spacetime constraints. Proc. SIGGRAPH.

Digital Library

[52]

Xin, S., Lai, C.-F., Fu, C.-W., Wong, T.-T., He, Y., and Cohen-Or, D. 2011. Making burr puzzles from 3d models. ACM Trans. Graph..

Digital Library

[53]

Yu, L.-F., Yeung, S. K., Tang, C.-K., Terzopoulos, D., Chan, T. F., and Osher, S. 2011. Make it home: automatic optimization of furniture arrangement. ACM Trans. Graph..

Digital Library

[54]

Zhou, Y., Sueda, S., Matusik, W., and Shamir, A. 2014. Boxelization: Folding 3d objects into boxes. ACM Trans. Graph..

Digital Library

Cited By

Fu QZhang FLi XFu H(2024)Magic Furniture: Design Paradigm of Multi-Function AssemblyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.325048830:7(4068-4079)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3250488
Yu MLiu TTan JLiu Y(2024)An Easy-to-Build Modular Robot Implementation of Chain-Based Physical Transformation for STEM EducationComputer-Aided Design and Computer Graphics10.1007/978-981-99-9666-7_12(170-185)Online publication date: 7-Feb-2024
https://doi.org/10.1007/978-981-99-9666-7_12
Cherchi GPellacini FAttene MLivesu M(2022)Interactive and Robust Mesh BooleansACM Transactions on Graphics10.1145/3550454.355546041:6(1-14)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555460
Show More Cited By

Index Terms

Computational design of reconfigurables
1. Computing methodologies
  1. Computer graphics

Recommendations

Computational design of wind-up toys

Wind-up toys are mechanical assemblies that perform intriguing motions driven by a simple spring motor. Due to the limited motor force and small body size, wind-up toys often employ higher pair joints of less frictional contacts and connector parts of ...
Computational Assistance for User Interface Design: Smarter Generation and Evaluation of Design Ideas
CHI EA '23: Extended Abstracts of the 2023 CHI Conference on Human Factors in Computing Systems

This paper describes a lab demo by the User Interfaces group at Aalto University. The demo allows attendees to interactively experience recent research prototypes aiming to facilitate designers’ creative and problem-solving capabilities in user interface ...
A computational design tool for compliant mechanisms

We present a computational tool for designing compliant mechanisms. Our method takes as input a conventional, rigidly-articulated mechanism defining the topology of the compliant design. This input can be both planar or spatial, and we support a number ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 35, Issue 4

July 2016

1396 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2897824

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2016

Published in TOG Volume 35, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

computational design

Qualifiers

Research-article

Funding Sources

NSF

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
641
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)6

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Fu QZhang FLi XFu H(2024)Magic Furniture: Design Paradigm of Multi-Function AssemblyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.325048830:7(4068-4079)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1109/TVCG.2023.3250488
Yu MLiu TTan JLiu Y(2024)An Easy-to-Build Modular Robot Implementation of Chain-Based Physical Transformation for STEM EducationComputer-Aided Design and Computer Graphics10.1007/978-981-99-9666-7_12(170-185)Online publication date: 7-Feb-2024
https://doi.org/10.1007/978-981-99-9666-7_12
Cherchi GPellacini FAttene MLivesu M(2022)Interactive and Robust Mesh BooleansACM Transactions on Graphics10.1145/3550454.355546041:6(1-14)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555460
Zhao HWillsey MZhu ANandi CTatlock ZSolomon JSchulz A(2022)Co-Optimization of Design and Fabrication Plans for CarpentryACM Transactions on Graphics10.1145/350849941:3(1-13)Online publication date: 9-Mar-2022
https://dl.acm.org/doi/10.1145/3508499
Liu ZHu JXu HSong PZhang RBickel BFu C(2022)Worst‐Case Rigidity Analysis and Optimization for Assemblies with Mechanical JointsComputer Graphics Forum10.1111/cgf.1449041:2(507-519)Online publication date: 24-May-2022
https://doi.org/10.1111/cgf.14490
Sellán SAigerman NJacobson A(2021)Swept volumes via spacetime numerical continuationACM Transactions on Graphics10.1145/3450626.345978040:4(1-11)Online publication date: 19-Jul-2021
https://dl.acm.org/doi/10.1145/3450626.3459780
Wang ZSong PPauly M(2021)State of the Art on Computational Design of Assemblies with Rigid PartsComputer Graphics Forum10.1111/cgf.14266040:2(633-657)Online publication date: 4-Jun-2021
https://doi.org/10.1111/cgf.142660
Xiong GFu QFu HZhou BLuo GDeng Z(2021)Motion Planning for Convertible Indoor Scene Layout DesignIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2020.300568027:12(4413-4424)Online publication date: 1-Dec-2021
https://doi.org/10.1109/TVCG.2020.3005680
Cherchi GLivesu MScateni RAttene M(2020)Fast and robust mesh arrangements using floating-point arithmeticACM Transactions on Graphics10.1145/3414685.341781839:6(1-16)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417818
Li JCui MKim JChen XIqbal SMacLean KChevalier FMueller S(2020)RomeoProceedings of the 33rd Annual ACM Symposium on User Interface Software and Technology10.1145/3379337.3415826(897-911)Online publication date: 20-Oct-2020
https://dl.acm.org/doi/10.1145/3379337.3415826
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents