Hierarchical Vorticity Skeletons

Sebastian Eberhardt, Steffen Weissmann, Ulrich Pinkall, Nils Thuerey

We propose a novel method to extract hierarchies of vortex filaments from given three-dimensional flow velocity fields. We call these collections of filaments Hierarchical Vorticity Skeletons (HVS). They extract multi-scale information from the input velocity field, which is not possible with any previous filament extraction approach. Once computed, these HVSs provide a powerful mechanism for data compression and a very natural way for modifying flows. The data compression rates for all presented examples are above 99%. Employing our skeletons for flow modification has several advantages over traditional approaches. Most importantly, they reduce the complexity of three-dimensional fields to one-dimensional lines and, make complex fluid data more accessible for changing defining features of a flow. The strongly reduced HVS dataset still carries the main characteristics of the flow. Through the hierarchy we can capture the main features of different scales in the flow and by that provide a level of detail control. In contrast to previous work, we present a fully automated pipeline to robustly decompose dense velocities into filaments.

Hierarchical Vorticity Skeletons

Designing Cable-Driven Actuation Networks for Kinematic Chains and Trees

Vittorio Megaro, Espen Knoop, Andrew Spielberg, David I.W. Levin, Wojciech Matusik,Markus Gross, Bernhard Thomaszewski, Moritz Bächer

In this paper, we present an optimization-based approach for the design of cable-driven kinematic chains and trees. Our system takes as input a hierarchical assembly consisting of rigid links jointed together with hinges. The user also specifies a set of target poses or keyframes using inverse kinematics. Our approach places torsional springs at the joints and computes a cable network that allows us to reproduce the specified target poses. We start with a large set of cables that have randomly chosen routing points and we gradually remove the redundancy. Then we refine the routing points taking into account the path between poses or keyframes in order to further reduce the number of cables and minimize required control forces. We propose a reduced coordinate formulation that links control forces to joint angles and routing points, enabling the co-optimization of a cable network together with the required actuation forces. We demonstrate the efficacy of our technique by designing and fabricating a cable-driven, animated character, an animatronic hand, and a specialized gripper.

Designing Cable-Driven Actuation Networks for Kinematic Chains and Trees

Rigid Body Contact Problems using Proximal Operators

Kenny Erleben

Iterative methods are popular for solving contact force problems in rigid body dynamics. They are loved for their robustness and surrounded by mystery as to whether they converge or not. We provide a mathematical foundation for iterative (PROX) schemes based on proximal operators. This is a class of iterative Jacobi and blocked Gauss–Seidel variants that theoretically proven always converge and provides a flexible plug and play framework for exploring different friction laws. We provide a portfolio of experience for choosing r-Factor strategies for such schemes and we analyze the distribution of convergence behaviors. Our results indicate the Gauss-Seidel variant is superior in terms of delivering predictable convergence behaviour and hence should be preferred over Jacobi variants. Our results also suggest that Global r -Factor strategies are better for structured stacking scenarios and can achieve absolute convergence in more cases.

Rigid Body Contact Problems using Proximal Operators

Improving the GJK algorithm for faster and more reliable distance queries between convex objects

Mattia Montanari, Nik Petrinic, and Ettore Barbieri

This article presents a new version of the Gilbert-Johnson-Keerthi (GJK) algorithm that circumvents the shortcomings introduced by degenerate geometries. The original Johnson algorithm and Backup procedure are replaced by a distance subalgorithm that is faster and accurate to machine precision, thus guiding the GJK algorithm toward a shorter search path in less computing time. Numerical tests demonstrate that this effectively is a more robust procedure. In particular, when the objects are found in contact, the newly proposed subalgorithm runs from 15% to 30% times faster than the original one. The improved performance has a significant impact on various applications, such as real-time simulations and collision avoidance systems. Altogether, the main contributions made to the GJK algorithm are faster convergence rate and reduced computational time. These improvements may be easily added into existing implementations; furthermore, engineering applications that require solutions of distance queries to machine precision can now be tackled using the GJK algorithm.

Improving the GJK algorithm for faster and more reliable distance queries between convex objects

All’s Well That Ends Well: Guaranteed Resolution of Simultaneous Rigid Body Impact

Etienne Vouga, Breannan Smith, Danny M. Kaufman, Rasmus Tamstorf, Eitan Grinspun

Iterative algorithms are frequently used to resolve simultaneous impacts between rigid bodies in physical simulations. However, these algorithms lack formal guarantees of termination, which is sometimes viewed as potentially dangerous, so failsafes are used in practical codes to prevent infinite loops. We show such steps are unnecessary. In particular, we study the broad class of such algorithms that are conservative and satisfy a minimal set of physical correctness properties, and which encompasses recent methods like Generalized Reflections as well as pairwise schemes. We fully characterize finite termination of these algorithms. The only possible failure cases can be detected, and we describe a procedure for modifying the algorithms to provably ensure termination. We also describe modifications necessary to guarantee termination in the presence of numerical error due to the use of floating-point arithmetic. Finally, we discuss the challenges dissipation introduce for finite termination, and describe how dissipation models can be incorporated while retaining the termination guarantee.

All’s Well That Ends Well: Guaranteed Resolution of Simultaneous Rigid Body Impact

MaterialCloning: Acquiring Elasticity Parameters from Images for Medical Applications

Shan Yang, Ming C. Lin

We present a practical approach for automatically estimating the material properties of soft bodies from two sets of images, taken before and after deformation. We reconstruct 3D geometry from the given sets of multiple-view images; we use a coupled simulation-optimization-identification framework to deform one soft body at its original, non-deformed state to match the deformed geometry of the same object in its deformed state. For shape correspondence, we use a distance-based error metric to compare the estimated deformation fields against the actual deformation field from the reconstructed geometry. The optimal set of material parameters is thereby determined by minimizing the error metric function. This method can simultaneously recover the elasticity parameters of multiple types of soft bodies using Finite Element Method-based simulation (of either linear or nonlinear materials undergoing large deformation) and particle-swarm optimization methods. We demonstrate this approach on real-time interaction with virtual organs in patient-specific surgical simulation, using parameters acquired from low-resolution medical images. We also highlight the results on physics-based animation of virtual objects using sketches from an artist’s conception.

MaterialCloning: Acquiring Elasticity Parameters from Images for Medical Applications

A Positive-Definite Cut-Cell Method for Strong Two-Way Coupling Between Fluids and Deformable Bodies

Omar Zarifi, Christopher Batty

We present a new approach to simulation of two-way coupling between inviscid free surface fluids and deformable bodies that exhibits several notable advantages over previous techniques. By fully incorporating the dynamics of the solid into pressure projection, we simultaneously handle fluid incompressibility and solid elasticity and damping. Thanks to this strong coupling, our method does not suer from instability, even in very taxing scenarios. Furthermore, use of a cut-cell discretization methodology allows us to accurately apply proper free-slip boundary conditions at the exact solid-fluid interface. Consequently, our method is capable of correctly simulating inviscid tangential flow, devoid of grid artefacts or artificial sticking. Lastly, we present an efficient algebraic transformation to convert the indenite coupled pressure projection system into a positive-definite form. We demonstrate the efficacy of our proposed method by simulating several interesting scenarios, including a light bath toy colliding with a collapsing column of water, liquid being dropped onto a deformable platform, and a partially liquid-filled deformable elastic sphere bouncing.

A Positive-Definite Cut-Cell Method for Strong Two-Way Coupling Between Fluids and Deformable Bodies

A Micropolar Material Model for Turbulent SPH Fluids

Jan Bender, Dan Koschier, Tassilo Kugelstadt, Marcel Weiler

In this paper we introduce a novel micropolar material model for the simulation of turbulent inviscid fluids. The governing equations are solved by using the concept of Smoothed Particle Hydrodynamics (SPH). As already investigated in previous works, SPH fluid simulations suffer from numerical diffusion which leads to a lower vorticity, a loss in turbulent details and finally in less realistic results. To solve this problem we propose a micropolar fluid model. The micropolar fluid model is a generalization of the classical Navier-Stokes equations, which are typically used in computer graphics to simulate fluids. In contrast to the classical Navier-Stokes model, micropolar fluids have a microstructure and therefore consider the rotational motion of fluid particles. In addition to the linear velocity field these fluids also have a field of microrotation which represents existing vortices and provides a source for new ones. However, classical micropolar materials are viscous and the translational and the rotational motion are coupled in a dissipative way. Since our goal is to simulate turbulent fluids, we introduce a novel modified micropolar material for inviscid fluids with a non-dissipative coupling. Our model can generate realistic turbulences, is linear and angular momentum conserving, can be easily integrated in existing SPH simulation methods and its computational overhead is negligible.

A Micropolar Material Model for Turbulent SPH Fluids

Evaporation and Condensation of SPH-based Fluids

Hendrik Hochstetter, Andreas Kolb

In this paper we present a method to simulate evaporation and condensation of liquids. Therefore, both the air and liquid phases have to be simulated. We use, as a carrier of vapor, a coarse grid for the air phase and mass-preservingly couple it to an SPH-based liquid and rigid body simulation. Since condensation only takes place on rigid surfaces, it is captured using textures that carry water to achieve high surface detail. The textures can exchange water with the air phase and are used to generate new particles due to condensation effects yielding a full two-way coupling of air phase and liquid. In order to allow gradual evaporation and condensation processes, liquid particles can take on variable sizes. Our proposed improved implicit surface definition is able to render dynamic contact angles for moving droplets yielding highly detailed fluid rendering.

Evaporation and Condensation of SPH-based Fluids

Fully Asynchronous SPH Simulation

Stefan Reinhardt, Markus Huber, Bernhard Eberhardt, Daniel Weiskopf

We present a novel method for fully asynchronous time integration of particle-based fluids using smoothed particle hydrodynamics (SPH). With our approach, we allow a dedicated time step for each particle. Therefore, we are able to increase the efficiency of simulations. Previous approaches of locally adaptive time steps have shown promising results in the form of increased time steps, however, they need to synchronize time steps in recurring intervals, which involves either interpolation operations or matching time steps. With our method, time steps are asynchronous through the whole simulation and no global time barriers are needed. In addition, we present an efficient method for parallelization of our novel asynchronous time integration. For both serial and parallel execution, we achieve speedups of up to 7.5 compared to fixed time steps and are able to outperform previous adaptive approaches considerably

Fully Asynchronous SPH Simulation