{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:02:51Z","timestamp":1784268171609,"version":"3.55.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T00:00:00Z","timestamp":1468195200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CMMI-11-29917, IIS-12-08153, IIS-14-09286, IIS-17257"],"award-info":[{"award-number":["CMMI-11-29917, IIS-12-08153, IIS-14-09286, IIS-17257"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,7,11]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1145\/2897824.2925900","type":"journal-article","created":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T12:04:33Z","timestamp":1468238673000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Computational design of reconfigurables"],"prefix":"10.1145","volume":"35","author":[{"given":"Akash","family":"Garg","sequence":"first","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alec","family":"Jacobson","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eitan","family":"Grinspun","sequence":"additional","affiliation":[{"name":"Columbia University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,7,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778819"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","unstructured":"B\u00e4cher M. Bickel B. James D. L. and Pfister H. 2012. Fabricating articulated characters from skinned meshes. ACM Trans. Graph. 10.1145\/2185520.2185543","DOI":"10.1145\/2185520.2185543"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601157"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","unstructured":"B\u00e4cher M. Coros S. and Thomaszewski B. 2015. Linkedit: interactive linkage editing using symbolic kinematics. ACM Trans. Graph.. 10.1145\/2766985","DOI":"10.1145\/2766985"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882357"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","unstructured":"Bernstein G. L. and Wojtan C. 2013. Putting holes in holey geometry: Topology change for arbitrary surfaces. ACM Trans. Graph.. 10.1145\/2461912.2462027","DOI":"10.1145\/2461912.2462027"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","unstructured":"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.. 10.1145\/2816795.2818108","DOI":"10.1145\/2816795.2818108"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566623"},{"key":"e_1_2_2_9_1","volume-title":"Collision detection by four-dimensional intersection testing","author":"Cameron S.","unstructured":"Cameron, S. 1990. Collision detection by four-dimensional intersection testing. IEEE T. Robotics and Automation."},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Campen M. and Kobbelt L. 2010. Polygonal boundary evaluation of minkowski sums and swept volumes. Comput. Graph. Forum.","DOI":"10.1111\/j.1467-8659.2010.01770.x"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","unstructured":"Ceylan D. Li W. Mitra N. J. Agrawala M. and Pauly M. 2013. Designing and fabricating mechanical automata from mocap sequences. ACM Trans. Graph.. 10.1145\/2508363.2508400","DOI":"10.1145\/2508363.2508400"},{"key":"e_1_2_2_12_1","unstructured":"Erleben K. 2004. Stable Robust and Versatile Multibody Dynamics Animation. PhD thesis Univ. of Copenhagen."},{"key":"e_1_2_2_13_1","unstructured":"Everitt C. 2001. Interactive order-independent transparency. Tech. rep. nVidia Corp."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","unstructured":"Gal R. Sorkine O. Mitra N. J. and Cohen-Or D. 2009. iWIRES: An analyze-and-edit approach to shape manipulation. ACM Trans. Graph.. 10.1145\/1531326.1531339","DOI":"10.1145\/1531326.1531339"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","unstructured":"Garg A. Sageman-Furnas A. O. Deng B. Yue Y. Grinspun E. Pauly M. and Wardetzky M. 2014. Wire mesh design. ACM Trans. Graph.. 10.1145\/2601097.2601106","DOI":"10.1145\/2601097.2601106"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/298960.299007"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","unstructured":"Harmon D. Panozzo D. Sorkine O. and Zorin D. 2011. Interference-aware geometric modeling. ACM Trans. Graph.. 10.1145\/2070781.2024171","DOI":"10.1145\/2070781.2024171"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185545"},{"key":"e_1_2_2_19_1","unstructured":"Jacobson A. Panozzo D. et al. 2013. libigl: A simple C++ geometry processing library. http:\/\/igl.ethz.ch\/projects\/libigl\/."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","unstructured":"Joubert N. Roberts M. Truong A. Berthouzoz F. and Hanrahan P. 2015. An interactive tool for designing quadrotor camera shots. ACM Trans. Graph.. 10.1145\/2816795.2818106","DOI":"10.1145\/2816795.2818106"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Kavraki L. E. \u0160vestka P. Latombe J.-C. and Over-mars M. H. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE TRA.","DOI":"10.1109\/70.508439"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","unstructured":"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. 10.1109\/2945.675649","DOI":"10.1109\/2945.675649"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","unstructured":"Koo B. Li W. Yao J. Agrawala M. and Mitra N. J. 2014. Creating works-like prototypes of mechanical objects. ACM Trans. Graph.. 10.1145\/2661229.2661289","DOI":"10.1145\/2661229.2661289"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","unstructured":"Li H. Alhashim I. Zhang H. Shamir A. and Cohen-Or D. 2012. Stackabilization. ACM Trans. Graph.. 10.1145\/2366145.2366177","DOI":"10.1145\/2366145.2366177"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","unstructured":"Liu S. Jacobson A. and Gingold Y. 2014. Skinning cubic B\u00e9zier splines and Catmull-Clark subdivision surfaces. ACM Trans. Graph.. 10.1145\/2661229.2661270","DOI":"10.1145\/2661229.2661270"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","unstructured":"Liu T. Hertzmann A. Li W. and Funkhouser T. 2015. Style compatibility for 3D furniture models. ACM Trans. Graph.. 10.1145\/2766898","DOI":"10.1145\/2766898"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","unstructured":"Merrell P. Schkufza E. Li Z. Agrawala M. and Koltun V. 2011. Interactive furniture layout using interior design guidelines. ACM Trans. Graph.. 10.1145\/2010324.1964982","DOI":"10.1145\/2010324.1964982"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Pavic D. and Kobbelt L. 2008. High-resolution volumetric computation of offset surfaces with feature preservation. Comput. Graph. Forum.","DOI":"10.1111\/j.1467-8659.2008.01113.x"},{"key":"e_1_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Peternell M. Pottmann H. Steiner T. and Zhao H. 2005. Swept volumes. Computer-Aided Design Appl..","DOI":"10.1080\/16864360.2005.10738324"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344880"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/148286"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/951087.951099"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","unstructured":"Sch\u00fcller C. Panozzo D. and Sorkine-Hornung O. 2014. Appearance-mimicking surfaces. ACM Trans. Graph.. 10.1145\/2661229.2661267","DOI":"10.1145\/2661229.2661267"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","unstructured":"Schulz A. Shamir A. Levin D. I. W. Sitthi-Amorn P. and Matusik W. 2014. Design and fabrication by example. ACM Trans. Graph.. 10.1145\/2601097.2601127","DOI":"10.1145\/2601097.2601127"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","unstructured":"Secord A. Lu J. Finkelstein A. Singh M. and Nealen A. 2011. Perceptual models of viewpoint preference. ACM Trans. Graph.. 10.1145\/2019627.2019628","DOI":"10.1145\/2019627.2019628"},{"key":"e_1_2_2_36_1","unstructured":"Shao M.-Z. and Badler N. 1996. Spherical sampling by archimedes' theorem. Tech. rep. Univ. of Penn."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","unstructured":"Shoemake K. 1992. Uniform random rotations. In Graphics Gems III. Morgan Kaufmann.","DOI":"10.5555\/130745.130769"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","unstructured":"Skouras M. Thomaszewski B. Bickel B. and Gross M. 2012. Computational design of rubber balloons. Comput. Graph. Forum. 10.1111\/j.1467-8659.2012.03064.x","DOI":"10.1111\/j.1467-8659.2012.03064.x"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","unstructured":"Skouras M. Thomaszewski B. Coros S. Bickel B. and Gross M. 2013. Computational design of actuated deformable characters. ACM Trans. Graph.. 10.1145\/2461912.2461979","DOI":"10.1145\/2461912.2461979"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","unstructured":"Snibbe S. S. 1995. A direct manipulation interface for 3d computer animation. Comput. Graph. Forum. 10.1111\/j.1467-8659.1995.cgf143_0271.x","DOI":"10.1111\/j.1467-8659.1995.cgf143_0271.x"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","unstructured":"Sun T. and Zheng C. 2015. Computational design of twisty joints and puzzles. ACM Trans. Graph.. 10.1145\/2766961","DOI":"10.1145\/2766961"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019627.2019630"},{"key":"e_1_2_2_43_1","volume-title":"Proc. Eurographics (STAR).","author":"Teschner M.","unstructured":"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)."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","unstructured":"Thomaszewski B. Coros S. Gauge D. Megaro V. Grinspun E. and Gross M. 2014. Computational design of linkage-based characters. ACM Trans. Graph.. 10.1145\/2601097.2601143","DOI":"10.1145\/2601097.2601143"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","unstructured":"Umetani N. Kaufman D. M. Igarashi T. and Grinspun E. 2011. Sensitive couture for interactive garment editing and modeling. ACM Trans. Graph.. 10.1145\/2010324.1964985","DOI":"10.1145\/2010324.1964985"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","unstructured":"Umetani N. Igarashi T. and Mitra N. J. 2012. Guided exploration of physically valid shapes for furniture design. ACM Trans. Graph.. 10.1145\/2185520.2185582","DOI":"10.1145\/2185520.2185582"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601129"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","unstructured":"Volino P. and Magnenat-Thalmann N. 2006. Resolving surface collisions through intersection contour minimization. ACM Trans. Graph.. 10.1145\/1141911.1142007","DOI":"10.1145\/1141911.1142007"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185593"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","unstructured":"Weld J. D. and Leu M. C. 1990. Geometric representation of swept volumes with application to polyhedral objects. Int. J. Rob. Res.. 10.1177\/027836499000900507","DOI":"10.1177\/027836499000900507"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/54852.378507"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","unstructured":"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.. 10.1145\/2010324.1964992","DOI":"10.1145\/2010324.1964992"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","unstructured":"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.. 10.1145\/2010324.1964981","DOI":"10.1145\/2010324.1964981"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601173"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897824.2925900","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897824.2925900","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897824.2925900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:59Z","timestamp":1763458079000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897824.2925900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,11]]},"references-count":54,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,11]]}},"alternative-id":["10.1145\/2897824.2925900"],"URL":"https:\/\/doi.org\/10.1145\/2897824.2925900","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,11]]},"assertion":[{"value":"2016-07-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}