Foldabilizing Furniture

摘要

We introduce the foldabilization problem for space-saving furniturerndesign. Namely, given a 3D object representing a piece of furniture,rnour goal is to apply a minimum amount of modification to the objectrnso that it can be folded to save space — the object is thus foldabilized.rnWe focus on one instance of the problem where folding isrnwith respect to a prescribed folding direction and allowed objectrnmodifications include hinge insertion and part shrinking.rnWe develop an automatic algorithm for foldabilization by formulatingrnand solving a nested optimization problem operating at tworngranularity levels of the input shape. Specifically, the input shape isrnfirst partitioned into a set of integral folding units. For each unit, wernconstruct a graph which encodes conflict relations, e.g., collisions,rnbetween foldings implied by various patch foldabilizations withinrnthe unit. Finding a minimum-cost foldabilization with a conflictfreernfolding is an instance of the maximum-weight independent setrnproblem. In the outer loop of the optimization, we process the foldingrnunits in an optimized ordering where the units are sorted basedrnon estimated foldabilization costs. We show numerous foldabilizationrnresults computed at interactive speed and 3D-print physicalrnprototypes of these results to demonstrate manufacturability.