@article{13188, abstract = {The Kirchhoff rod model describes the bending and twisting of slender elastic rods in three dimensions, and has been widely studied to enable the prediction of how a rod will deform, given its geometry and boundary conditions. In this work, we study a number of inverse problems with the goal of computing the geometry of a straight rod that will automatically deform to match a curved target shape after attaching its endpoints to a support structure. Our solution lets us finely control the static equilibrium state of a rod by varying the cross-sectional profiles along its length. We also show that the set of physically realizable equilibrium states admits a concise geometric description in terms of linear line complexes, which leads to very efficient computational design algorithms. Implemented in an interactive software tool, they allow us to convert three-dimensional hand-drawn spline curves to elastic rods, and give feedback about the feasibility and practicality of a design in real time. We demonstrate the efficacy of our method by designing and manufacturing several physical prototypes with applications to interior design and soft robotics.}, author = {Hafner, Christian and Bickel, Bernd}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, keywords = {Computer Graphics, Computational Design, Computational Geometry, Shape Modeling}, number = {5}, publisher = {Association for Computing Machinery}, title = {{The design space of Kirchhoff rods}}, doi = {10.1145/3606033}, volume = {42}, year = {2023}, } @article{13265, abstract = {In this study, we propose a computational framework for optimizing the continuity of the toolpath in fabricating surface models on an extrusion-based 3D printer. Toolpath continuity is a critical issue that influences both the quality and the efficiency of extrusion-based fabrication. Transfer moves lead to rough and bumpy surfaces, where this phenomenon worsens for materials with large viscosity, like clay. The effects of continuity on the surface models are even more severe in terms of the quality of the surface and the stability of the model. We introduce a criterion called the one–path patch (OPP) to represent a patch on the surface of the shell that can be traversed along one path by considering the constraints on fabrication. We study the properties of the OPPs and their merging operations to propose a bottom-up OPP merging procedure to decompose the given shell surface into a minimal number of OPPs, and to generate the “as-continuous-as-possible” (ACAP) toolpath. Furthermore, we augment the path planning algorithm with a curved-layer printing scheme that reduces staircase defects and improves the continuity of the toolpath by connecting multiple segments. We evaluated the ACAP algorithm on ceramic and thermoplastic materials, and the results showed that it improves the fabrication of surface models in terms of both efficiency and surface quality.}, author = {Zhong, Fanchao and Xu, Yonglai and Zhao, Haisen and Lu, Lin}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {3}, publisher = {Association for Computing Machinery}, title = {{As-Continuous-As-Possible extrusion-based fabrication of surface models}}, doi = {10.1145/3575859}, volume = {42}, year = {2023}, } @article{14240, abstract = {This paper introduces a novel method for simulating large bodies of water as a height field. At the start of each time step, we partition the waves into a bulk flow (which approximately satisfies the assumptions of the shallow water equations) and surface waves (which approximately satisfy the assumptions of Airy wave theory). We then solve the two wave regimes separately using appropriate state-of-the-art techniques, and re-combine the resulting wave velocities at the end of each step. This strategy leads to the first heightfield wave model capable of simulating complex interactions between both deep and shallow water effects, like the waves from a boat wake sloshing up onto a beach, or a dam break producing wave interference patterns and eddies. We also analyze the numerical dispersion created by our method and derive an exact correction factor for waves at a constant water depth, giving us a numerically perfect re-creation of theoretical water wave dispersion patterns.}, author = {Jeschke, Stefan and Wojtan, Christopher J}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Generalizing shallow water simulations with dispersive surface waves}}, doi = {10.1145/3592098}, volume = {42}, year = {2023}, } @article{12984, abstract = {Tattoos are a highly popular medium, with both artistic and medical applications. Although the mechanical process of tattoo application has evolved historically, the results are reliant on the artisanal skill of the artist. This can be especially challenging for some skin tones, or in cases where artists lack experience. We provide the first systematic overview of tattooing as a computational fabrication technique. We built an automated tattooing rig and a recipe for the creation of silicone sheets mimicking realistic skin tones, which allowed us to create an accurate model predicting tattoo appearance. This enables several exciting applications including tattoo previewing, color retargeting, novel ink spectra optimization, color-accurate prosthetics, and more.}, author = {Piovarci, Michael and Chapiro, Alexandre and Bickel, Bernd}, issn = {1557-7368}, journal = {Transactions on Graphics}, keywords = {appearance, modeling, reproduction, tattoo, skin color, gamut mapping, ink-optimization, prosthetic}, location = {Los Angeles, CA, United States}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Skin-Screen: A computational fabrication framework for color tattoos}}, doi = {10.1145/3592432}, volume = {42}, year = {2023}, } @article{13049, abstract = {We propose a computational design approach for covering a surface with individually addressable RGB LEDs, effectively forming a low-resolution surface screen. To achieve a low-cost and scalable approach, we propose creating designs from flat PCB panels bent in-place along the surface of a 3D printed core. Working with standard rigid PCBs enables the use of established PCB manufacturing services, allowing the fabrication of designs with several hundred LEDs. Our approach optimizes the PCB geometry for folding, and then jointly optimizes the LED packing, circuit and routing, solving a challenging layout problem under strict manufacturing requirements. Unlike paper, PCBs cannot bend beyond a certain point without breaking. Therefore, we introduce parametric cut patterns acting as hinges, designed to allow bending while remaining compact. To tackle the joint optimization of placement, circuit and routing, we propose a specialized algorithm that splits the global problem into one sub-problem per triangle, which is then individually solved. Our technique generates PCB blueprints in a completely automated way. After being fabricated by a PCB manufacturing service, the boards are bent and glued by the user onto the 3D printed support. We demonstrate our technique on a range of physical models and virtual examples, creating intricate surface light patterns from hundreds of LEDs.}, author = {Freire, Marco and Bhargava, Manas and Schreck, Camille and Hugron, Pierre-Alexandre and Bickel, Bernd and Lefebvre, Sylvain}, issn = {1557-7368}, journal = {Transactions on Graphics}, keywords = {PCB design and layout, Mesh geometry models}, location = {Los Angeles, CA, United States}, number = {4}, publisher = {Association for Computing Machinery}, title = {{PCBend: Light up your 3D shapes with foldable circuit boards}}, doi = {10.1145/3592411}, volume = {42}, year = {2023}, } @article{11442, abstract = {Enabling additive manufacturing to employ a wide range of novel, functional materials can be a major boost to this technology. However, making such materials printable requires painstaking trial-and-error by an expert operator, as they typically tend to exhibit peculiar rheological or hysteresis properties. Even in the case of successfully finding the process parameters, there is no guarantee of print-to-print consistency due to material differences between batches. These challenges make closed-loop feedback an attractive option where the process parameters are adjusted on-the-fly. There are several challenges for designing an efficient controller: the deposition parameters are complex and highly coupled, artifacts occur after long time horizons, simulating the deposition is computationally costly, and learning on hardware is intractable. In this work, we demonstrate the feasibility of learning a closed-loop control policy for additive manufacturing using reinforcement learning. We show that approximate, but efficient, numerical simulation is sufficient as long as it allows learning the behavioral patterns of deposition that translate to real-world experiences. In combination with reinforcement learning, our model can be used to discover control policies that outperform baseline controllers. Furthermore, the recovered policies have a minimal sim-to-real gap. We showcase this by applying our control policy in-vivo on a single-layer, direct ink writing printer. }, author = {Piovarci, Michael and Foshey, Michael and Xu, Jie and Erps, Timothy and Babaei, Vahid and Didyk, Piotr and Rusinkiewicz, Szymon and Matusik, Wojciech and Bickel, Bernd}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Closed-loop control of direct ink writing via reinforcement learning}}, doi = {10.1145/3528223.3530144}, volume = {41}, year = {2022}, } @article{11735, abstract = {Interlocking puzzles are intriguing geometric games where the puzzle pieces are held together based on their geometric arrangement, preventing the puzzle from falling apart. High-level-of-difficulty, or simply high-level, interlocking puzzles are a subclass of interlocking puzzles that require multiple moves to take out the first subassembly from the puzzle. Solving a high-level interlocking puzzle is a challenging task since one has to explore many different configurations of the puzzle pieces until reaching a configuration where the first subassembly can be taken out. Designing a high-level interlocking puzzle with a user-specified level of difficulty is even harder since the puzzle pieces have to be interlocking in all the configurations before the first subassembly is taken out. In this paper, we present a computational approach to design high-level interlocking puzzles. The core idea is to represent all possible configurations of an interlocking puzzle as well as transitions among these configurations using a rooted, undirected graph called a disassembly graph and leverage this graph to find a disassembly plan that requires a minimal number of moves to take out the first subassembly from the puzzle. At the design stage, our algorithm iteratively constructs the geometry of each puzzle piece to expand the disassembly graph incrementally, aiming to achieve a user-specified level of difficulty. We show that our approach allows efficient generation of high-level interlocking puzzles of various shape complexities, including new solutions not attainable by state-of-the-art approaches.}, author = {Chen, Rulin and Wang, Ziqi and Song, Peng and Bickel, Bernd}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Computational design of high-level interlocking puzzles}}, doi = {10.1145/3528223.3530071}, volume = {41}, year = {2022}, } @article{11736, abstract = {This paper introduces a methodology for inverse-modeling of yarn-level mechanics of cloth, based on the mechanical response of fabrics in the real world. We compiled a database from physical tests of several different knitted fabrics used in the textile industry. These data span different types of complex knit patterns, yarn compositions, and fabric finishes, and the results demonstrate diverse physical properties like stiffness, nonlinearity, and anisotropy. We then develop a system for approximating these mechanical responses with yarn-level cloth simulation. To do so, we introduce an efficient pipeline for converting between fabric-level data and yarn-level simulation, including a novel swatch-level approximation for speeding up computation, and some small-but-necessary extensions to yarn-level models used in computer graphics. The dataset used for this paper can be found at http://mslab.es/projects/YarnLevelFabrics.}, author = {Sperl, Georg and Sánchez-Banderas, Rosa M. and Li, Manwen and Wojtan, Christopher J and Otaduy, Miguel A.}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {4}, publisher = {Association for Computing Machinery}, title = {{Estimation of yarn-level simulation models for production fabrics}}, doi = {10.1145/3528223.3530167}, volume = {41}, year = {2022}, } @article{12431, abstract = {This paper presents a new representation of curve dynamics, with applications to vortex filaments in fluid dynamics. Instead of representing these filaments with explicit curve geometry and Lagrangian equations of motion, we represent curves implicitly with a new co-dimensional 2 level set description. Our implicit representation admits several redundant mathematical degrees of freedom in both the configuration and the dynamics of the curves, which can be tailored specifically to improve numerical robustness, in contrast to naive approaches for implicit curve dynamics that suffer from overwhelming numerical stability problems. Furthermore, we note how these hidden degrees of freedom perfectly map to a Clebsch representation in fluid dynamics. Motivated by these observations, we introduce untwisted level set functions and non-swirling dynamics which successfully regularize sources of numerical instability, particularly in the twisting modes around curve filaments. A consequence is a novel simulation method which produces stable dynamics for large numbers of interacting vortex filaments and effortlessly handles topological changes and re-connection events.}, author = {Ishida, Sadashige and Wojtan, Christopher J and Chern, Albert}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {Association for Computing Machinery}, title = {{Hidden degrees of freedom in implicit vortex filaments}}, doi = {10.1145/3550454.3555459}, volume = {41}, year = {2022}, } @article{9376, abstract = {This paper presents a method for designing planar multistable compliant structures. Given a sequence of desired stable states and the corresponding poses of the structure, we identify the topology and geometric realization of a mechanism—consisting of bars and joints—that is able to physically reproduce the desired multistable behavior. In order to solve this problem efficiently, we build on insights from minimally rigid graph theory to identify simple but effective topologies for the mechanism. We then optimize its geometric parameters, such as joint positions and bar lengths, to obtain correct transitions between the given poses. Simultaneously, we ensure adequate stability of each pose based on an effective approximate error metric related to the elastic energy Hessian of the bars in the mechanism. As demonstrated by our results, we obtain functional multistable mechanisms of manageable complexity that can be fabricated using 3D printing. Further, we evaluated the effectiveness of our method on a large number of examples in the simulation and fabricated several physical prototypes.}, author = {Zhang, Ran and Auzinger, Thomas and Bickel, Bernd}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, keywords = {multistability, mechanism, computational design, rigidity}, number = {5}, publisher = {Association for Computing Machinery}, title = {{Computational design of planar multistable compliant structures}}, doi = {10.1145/3453477}, volume = {40}, year = {2021}, } @article{9817, abstract = {Elastic bending of initially flat slender elements allows the realization and economic fabrication of intriguing curved shapes. In this work, we derive an intuitive but rigorous geometric characterization of the design space of plane elastic rods with variable stiffness. It enables designers to determine which shapes are physically viable with active bending by visual inspection alone. Building on these insights, we propose a method for efficiently designing the geometry of a flat elastic rod that realizes a target equilibrium curve, which only requires solving a linear program. We implement this method in an interactive computational design tool that gives feedback about the feasibility of a design, and computes the geometry of the structural elements necessary to realize it within an instant. The tool also offers an iterative optimization routine that improves the fabricability of a model while modifying it as little as possible. In addition, we use our geometric characterization to derive an algorithm for analyzing and recovering the stability of elastic curves that would otherwise snap out of their unstable equilibrium shapes by buckling. We show the efficacy of our approach by designing and manufacturing several physical models that are assembled from flat elements.}, author = {Hafner, Christian and Bickel, Bernd}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, keywords = {Computing methodologies, shape modeling, modeling and simulation, theory of computation, computational geometry, mathematics of computing, mathematical optimization}, location = {Virtual}, number = {4}, publisher = {Association for Computing Machinery}, title = {{The design space of plane elastic curves}}, doi = {10.1145/3450626.3459800}, volume = {40}, year = {2021}, } @article{8562, abstract = {Cold bent glass is a promising and cost-efficient method for realizing doubly curved glass facades. They are produced by attaching planar glass sheets to curved frames and require keeping the occurring stress within safe limits. However, it is very challenging to navigate the design space of cold bent glass panels due to the fragility of the material, which impedes the form-finding for practically feasible and aesthetically pleasing cold bent glass facades. We propose an interactive, data-driven approach for designing cold bent glass facades that can be seamlessly integrated into a typical architectural design pipeline. Our method allows non-expert users to interactively edit a parametric surface while providing real-time feedback on the deformed shape and maximum stress of cold bent glass panels. Designs are automatically refined to minimize several fairness criteria while maximal stresses are kept within glass limits. We achieve interactive frame rates by using a differentiable Mixture Density Network trained from more than a million simulations. Given a curved boundary, our regression model is capable of handling multistable configurations and accurately predicting the equilibrium shape of the panel and its corresponding maximal stress. We show predictions are highly accurate and validate our results with a physical realization of a cold bent glass surface.}, author = {Gavriil, Konstantinos and Guseinov, Ruslan and Perez Rodriguez, Jesus and Pellis, Davide and Henderson, Paul M and Rist, Florian and Pottmann, Helmut and Bickel, Bernd}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {Association for Computing Machinery}, title = {{Computational design of cold bent glass façades}}, doi = {10.1145/3414685.3417843}, volume = {39}, year = {2020}, } @article{7418, abstract = {Multiple importance sampling (MIS) has become an indispensable tool in Monte Carlo rendering, widely accepted as a near-optimal solution for combining different sampling techniques. But an MIS combination, using the common balance or power heuristics, often results in an overly defensive estimator, leading to high variance. We show that by generalizing the MIS framework, variance can be substantially reduced. Specifically, we optimize one of the combined sampling techniques so as to decrease the overall variance of the resulting MIS estimator. We apply the approach to the computation of direct illumination due to an HDR environment map and to the computation of global illumination using a path guiding algorithm. The implementation can be as simple as subtracting a constant value from the tabulated sampling density done entirely in a preprocessing step. This produces a consistent noise reduction in all our tests with no negative influence on run time, no artifacts or bias, and no failure cases.}, author = {Karlík, Ondřej and Šik, Martin and Vévoda, Petr and Skrivan, Tomas and Křivánek, Jaroslav}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {6}, publisher = {ACM}, title = {{MIS compensation: Optimizing sampling techniques in multiple importance sampling}}, doi = {10.1145/3355089.3356565}, volume = {38}, year = {2019}, } @article{4063, abstract = {This paper describes a general-purpose programming technique, called Simulation of Simplicity, that can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task of providing a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than those that do not use it. We believe that this technique will become a standard tool in writing geometric software.}, author = {Edelsbrunner, Herbert and Mücke, Ernst}, issn = {1557-7368}, journal = {ACM Transactions on Graphics}, number = {1}, pages = {66 -- 104}, publisher = {ACM}, title = {{Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms}}, doi = {10.1145/77635.77639}, volume = {9}, year = {1990}, }