Fun in Geometry and Fabrication

3D Fabrication with Universal Building Blocks and Pyramidal Shells

Abstract: We introduce a computational solution for cost-efficient 3D fabrication using universal building blocks. Our key idea is to employ a set of universal blocks, which can be massively prefabricated at a low cost, to quickly assemble and constitute a significant internal core of the target object, so that only the residual volume need to be 3D printed online. We further improve the fabrication efficiency by decomposing the residual volume into a small number of printing-friendly pyramidal pieces. Computationally, we face a coupled de-composition problem: decomposing the input object into an internal core and residual, and decomposing the residual, to fulfill a combination of objectives for efficient 3D fabrication. To this end, we formulate an optimization that jointly minimizes the residual volume, the number of pyramidal residual pieces, and the amount of support waste when printing the residual pieces. To solve the optimization in a tractable manner, we start with a maximal internal core and iteratively refine it with local cuts to minimize the cost function. Moreover, to efficiently explore the large search space, we resort to cost estimates aided by pre-computation and avoid the need to explicitly construct pyramidal decompositions for each solution candidate. Results show that our method can iteratively reduce the estimated printing time and cost, as well as the support waste, and helps to save hours of fabrication time and much material consumption.

Authors/Presenter(s): Xuelin Chen, Shandong University, China
Honghua Li, Alibaba AI Labs, China
Chi-Wing Fu, The Chinese University of Hong Kong, Hong Kong
Hao (Richard) Zhang, Simon Fraser University, Canada
Daniel Cohen-Or, Tel Aviv University, Israel
Baoquan Chen, Peking University, Shandong University, China

Construction and Fabrication of Reversible Shape Transforms

Abstract: We study a new and elegant instance of geometric dissection of 2D shapes: reversible hinged dissection, which corresponds to a dual transform between two shapes where one of them can be dissected in its interior and then inverted inside-out, with hinges on the shape boundary, to reproduce the other shape, and vice versa. We call such a transform reversible inside-out transform or RIOT. Since it is rare for two shapes to possess even a rough RIOT, let alone an exact one, we develop both a RIOT construction algorithm and a quick filtering mechanism to pick, from a shape collection, potential shape pairs that are likely to possess the transform. Our construction algorithm is fully automatic. It computes an approximate RIOT between two given input 2D shapes, whose boundaries can undergo slight deformations, while the filtering scheme picks good inputs for the construction. Furthermore, we add properly designed hinges and connectors to the shape pieces and fabricate them using a 3D printer so that they can be played as an assembly puzzle. With many interesting and fun RIOT pairs constructed from shapes found online, we demonstrate that our method significantly expands the range of shapes to be considered for RIOT, a seemingly impossible shape transform, and offers a practical way to construct and physically realize these transforms.

Authors/Presenter(s): Shuhua Li, Dalian University of Technology, Simon Fraser University, China
Ali Mahdavi-Amiri, Simon Fraser University, Canada
Ruizhen Hu, Shenzhen University, China
Han Liu, Simon Fraser University, Canada
Changqing Zou, University of Maryland, College Park, United States of America
Oliver Van Kaick, Carleton University, Canada
Xiuping Liu, Dalian University of Technology, China
Hui Huang, Shenzhen University, China
Hao (Richard) Zhang, Simon Fraser University, Canada

DESIA: A General Framework for Designing Interlocking Assemblies

Abstract: Interlocking assemblies have a long history in the design of puzzles, furniture, architecture, and other complex geometric structures. The key defining property of interlocking assemblies is that all component parts are immobilized by their geometric arrangement, preventing the assembly from falling apart. Computer graphics research has recently contributed design tools that allow creating new interlocking assemblies. However, these tools focus on specific kinds of assemblies and explore only a limited space of interlocking configurations, which restricts their applicability for design. In this paper, we propose a new general framework for designing interlocking assemblies. The core idea is to represent part relationships with a family of base Directional Blocking Graphs and leverage efficient graph analysis tools to compute an interlocking arrangement of parts. This avoids the exponential complexity of brute-force search. Our algorithm iteratively constructs the geometry of assembly components, taking advantage of all existing blocking relations when constructing successive parts. As a result, our approach supports a wider range of assembly forms compared to previous methods and provides significantly more design flexibility. We show that our framework facilitates efficient design of complex interlocking assemblies, including new solutions that cannot be achieved by state of the art approaches.

Authors/Presenter(s): Ziqi Wang, EPFL, Switzerland
Peng Song, EPFL, Switzerland
Mark Pauly, EPFL, Switzerland

PhotoShape: Photorealistic Materials for Large-Scale Shape Collections

Abstract: Existing online 3D shape repositories contain thousands of 3D models but lack photorealistic appearance. We present an approach to automatically assign high-quality, realistic appearance models to large scale 3D shape collections. The key idea is to jointly leverage three types of online data – shape collections, material collections, and photo collections, using the photos as reference to guide assignment of materials to shapes. By generating a large number of synthetic renderings, we train a convolutional neural network to classify materials in real photos, and employ 3D-2D alignment techniques to transfer materials to different parts of each shape model. Our system produces photorealistic, relightable, 3D shapes (PhotoShapes).

Authors/Presenter(s): Keunhong Park, University of Washington, United States of America
Konstantinos Rematas, University of Washington, United States of America
Ali Farhadi, University of Washington, Allen Institute for Artificial Intelligence, United States of America
Steven M. Seitz, University of Washington, Google, United States of America

Axis-Aligned Height-Field Block Decomposition of 3D Shapes

Abstract: We propose a novel algorithm for decomposing general 3D geometries into a small set of overlap-free height-field blocks, volumes enclosed by a flat base and a height-field surface defined with respect to this base. This decomposition is useful for fabrication methodologies such as 3-axis CNC milling, where a single milling pass can only carve a single height-field surface defined with respect to the machine tray, but can also benefit other fabrication settings. Computing our desired decomposition requires solving a highly constrained discrete optimization problem, variants of which are known to be NP-hard. We effectively compute a high-quality decomposition by using a two-step process that leverages the unique characteristics of our setup. Specifically, we notice that if the height-field directions are constrained to the major axes we can always produce a valid decomposition starting from a suitable surface segmentation. Our method first produces a compact set of large, possibly overlapping, height-field blocks that jointly cover the model surface by recasting this discrete constrained optimization problem as an unconstrained optimization of a continuous function, which allows for an efficient solution. We then cast the computation of an overlap-free, final decomposition as an ordering problem on a graph, and solve it via a combination of cycle elimination and topological sorting. The combined algorithm produces a compact set of height-field blocks that jointly describe the input model within a user given tolerance. We demonstrate our method on a range of inputs, and showcase a number of real life models manufactured using our technique.

Authors/Presenter(s): Alessandro Muntoni, Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" (ISTI), New York University, Italy
Marco Livesu, Istituto di Matematica Applicata e Tecnologie Informatiche (IMATI), Consiglio Nazionale delle Ricerche (CNR), Italy
Riccardo Scateni, University of Cagliari, Italy
Alla Sheffer, University of British Columbia, Canada
Daniele Panozzo, New York University, United States of America