Month: October 2019

Albert Peiret, Sheldon Andrews, József Kövecses, Paul G. Kry, Marek Teichmann

Substructuring permits parallelization of physics simulation on multi-core CPUs. We present a new substructuring approach for solving stiff multibody systems containing both bilateral and unilateral constraints. Our approach is based on non-overlapping domain decomposition with the Schur complement method, which we extend to systems involving contact formulated as a mixed bounds linear complementarity problem. At each time step, we alternate between solving the subsystem and interface constraint impulses, which leads to the identification of the active constraints. By using the active constraints to compute the effective mass of subsystems within the interface solve, we obtain an exact solution. We demonstrate that our simulations have preferable behavior compared to standard iterative solvers and substructuring techniques based on the exchange of forces at interface bodies. We observe considerable speedups for structured simulations where a user-defined partitioning can be applied, and moderate speedups for unstructured simulations, such as piles of bodies. In the latter case, we propose an automatic partitioning strategy based on the degree of bodies in the constraint graph. Because our method makes use of direct solvers, we are able to achieve interactive and real-time frame rates for a number of challenging scenarios involving large mass ratios, redundant constraints, and ill-conditioned systems.

Schur Complement-based Substructuring of Stiff Multibody Systems with Contact

Tassilo Kugelstadt, Andreas Longva, Nils Thuerey, Jan Bender

We propose a novel implicit density projection approach for hybrid Eulerian/Lagrangian methods like FLIP and APIC to enforce volume conservation of incompressible liquids. Our approach is able to robustly recover from highly degenerate configurations and incorporates volume-conserving boundary handling. A problem of the standard divergence-free pressure solver is that it only has a differential view on density changes. Numerical volume errors, which occur due to large time steps and the limited accuracy of pressure projections, are invisible to the solver and cannot be corrected. Moreover, these errors accumulate over time and can lead to drastic volume changes, especially in long-running simulations or interactive scenarios. Therefore, we introduce a novel method that enforces constant density throughout the fluid. The density itself is tracked via the particles of the hybrid Eulerian/Lagrangian simulation algorithm. To achieve constant density, we use the continuous mass conservation law to derive a pressure Poisson equation which also takes density deviations into account. It can be discretized with standard approaches and easily implemented into existing code by extending the regular pressure solver. Our method enables us to relax the strict time step and solver accuracy requirements of a regular solver, leading to significantly higher performance. Moreover, our approach is able to push fluid particles out of solid obstacles without losing volume and generates more uniform particle distributions, which makes frequent particle resampling unnecessary. We compare the proposed method to standard FLIP and APIC and to previous volume correction approaches in several simulations and demonstrate significant improvements in terms of incompressibility, visual realism and computational performance.

Implicit Density Projection for Volume Conserving Liquids

Jan Bender, Tassilo Kugelstadt, Marcel Weiler, Dan Koschier

In this paper, we present a novel method for the robust handling of static and dynamic rigid boundaries in Smoothed Particle Hydrodynamics (SPH) simulations. We build upon the ideas of the density maps approach which has been introduced recently by Koschier and Bender. They precompute the density contributions of solid boundaries and store them on a spatial grid which can be efficiently queried during runtime. This alleviates the problems of commonly used boundary particles, like bumpy surfaces and inaccurate pressure forces near boundaries. Our method is based on a similar concept but we precompute the volume contribution of the boundary geometry and store it on a grid. This maintains all benefits of density maps but offers a variety of advantages which are demonstrated in several experiments. Firstly, in contrast to the density maps method we can compute derivatives in the standard SPH manner by differentiating the kernel function. This results in smooth pressure forces, even for lower map resolutions, such that precomputation times and memory requirements are reduced by more than two orders of magnitude compared to density maps. Furthermore, this directly fits into the SPH concept so that volume maps can be seamlessly combined with existing SPH methods. Finally, the kernel function is not baked into the map such that the same volume map can be used with different kernels. This is especially useful when we want to incorporate common surface tension or viscosity methods that use different kernels than the fluid simulation.

Volume Maps: An Implicit Boundary Representation for SPH

Michael Tao, Christopher Batty, Eugene Fiume, David IW Levin

Although geometry arising “in the wild” most often comes in the form of a surface representation, a plethora of geometrical and physical applications require the construction of volumetric embeddings either of the geometry itself or the domain surrounding it. Cartesian cut-cell-based mesh generation provides an attractive solution in which volumetric elements are constructed from the intersection of the input surface geometry with a uniform or adaptive hexahedral grid. This choice, especially common in computational fluid dynamics, has the potential to efficiently generate accurate, surface-conforming cells; unfortunately, current solutions are often slow, fragile, or cannot handle many common topological situations. We therefore propose a novel, robust cut-cell construction technique for triangle surface meshes that explicitly computes the precise geometry of the intersection cells, even on meshes that are open or non-manifold. Its fundamental geometric primitive is the intersection of an arbitrary segment with an axis-aligned plane. Beginning from the set of intersection points between triangle mesh edges and grid planes, our bottom-up approach robustly determines cut-edges, cut-faces, and finally cut-cells, in a manner designed to guarantee topological correctness. We demonstrate its effectiveness and speed on a wide range of input meshes and grid resolutions, and make the code available as open source.

Mandoline: Robust Cut-Cell Generation for Arbitrary Triangle Meshes

Stefan Reinhardt, Tim Krake, Bernhard Eberhardt, Daniel Weiskopf

We present a novel technique to correct errors introduced by the discretization of a fluid body when animating it with smoothed particle hydrodynamics (SPH). Our approach is based on the Shepard correction, which reduces the interpolation errors from irregularly spaced data. With Shepard correction, the smoothing kernel function is normalized using the weighted sum of the kernel function values in the neighborhood. To compute the correction factor, densities of neighboring particles are needed, which themselves are computed with the uncorrected kernel. This results in an inconsistent formulation and an error-prone correction of the kernel. As a consequence, the density computation may be inaccurate, thus the pressure forces are erroneous and may  cause instabilities in the simulation process.We present a consistent formulation by using the corrected densities to compute the exact kernel correction factor and, thereby, increase the accuracy of the simulation. Employing our method, a smooth density  distribution is achieved, i.e., the noise in the density field is reduced by orders of magnitude. To show that our method is independent of the SPH variant, we evaluate our technique on weakly compressible SPH and on divergence-free SPH. Incorporating the corrected density into the correction process, the problem cannot be stated explicitly anymore. We propose an efficient and easy-to-implement algorithm to solve the implicit problem by applying the power method. Additionally, we demonstrate how our model can be applied to improve the density distribution on rigid bodies when using a well-known rigid-fluid coupling approach.

Consistent Shepard Interpolation for SPH-Based Fluid Animation