Realtime Two‐Way Coupling of Meshless Fluids and Nonlinear FEM

In this paper, we present a novel method to couple Smoothed Particle Hydrodynamics (SPH) and nonlinear FEM to animate the interaction of fluids and deformable solids in real time. To accurately model the coupling, we generate proxy particles over the boundary of deformable solids to facilitate the interaction with fluid particles, and develop an efficient method to distribute the coupling forces of proxy particles to FEM nodal points. Specifically, we employ the Total Lagrangian Explicit Dynamics (TLED) finite element algorithm for nonlinear FEM because of many of its attractive properties such as supporting massive parallelism, avoiding dynamic update of stiffness matrix computation, and efficient solver. Based on a predictor‐corrector scheme for both velocity and position, different normal and tangential conditions can be realized even for shell‐like thin solids. Our coupling method is entirely implemented on modern GPUs using CUDA. We demonstrate the advantage of our two‐way coupling method in computer animation via various virtual scenarios.     

Implicit Contact Handling for Deformable Objects

We present an algorithm for robust and efficient contact handling of deformable objects. By being aware of the internal dynamics of the colliding objects, our algorithm provides smooth rolling and sliding, stable stacking, robust impact handling, and seamless coupling of heterogeneous objects, all in a unified manner. We achieve dynamicsawareness through a constrained dynamics formulation with implicit complementarity constraints, and we present two major contributions that enable an efficient solution of the constrained dynamics problem: a time stepping algorithm that robustly ensures non-penetration and progressively refines the formulation of constrained dynamics, and a new solver for large mixed linear complementarity problems, based on iterative constraint anticipation. We show the application of our algorithm in challenging scenarios such as multi-layered cloth moving at high velocities, or colliding deformable solids simulated with large time steps.     

IISPH‐FLIP for incompressible fluids

We propose to use Implicit Incompressible Smoothed Particle Hydrodynamics (IISPH) for pressure projection and boundary handling in Fluid‐Implicit‐Particle (FLIP) solvers for the simulation of incompressible fluids. This novel combination addresses two issues of existing SPH and FLIP solvers, namely mass preservation in FLIP and efficiency and memory consumption in SPH. First, the SPH component enables the simulation of incompressible fluids with perfect mass preservation. Second, the FLIP component efficiently enriches the SPH component with detail that is comparable to a standard SPH simulation with the same number of particles, while improving the performance by a factor of 7 and significantly reducing the memory consumption. We demonstrate that the proposed IISPH‐FLIP solver can simulate incompressible fluids with a quantifiable, imperceptible density deviation below 0.1%. We show large‐scale scenarios with up to 160 million particles that have been processed on a single desktop PC using only 15GB of memory. One‐ and two‐way coupled solids are illustrated.     

Implicit Formulation for SPH‐based Viscous Fluids

We propose a stable and efficient particle‐based method for simulating highly viscous fluids that can generate coiling and buckling phenomena and handle variable viscosity. In contrast to previous methods that use explicit integration, our method uses an implicit formulation to improve the robustness of viscosity integration, therefore enabling use of larger time steps and higher viscosities. We use Smoothed Particle Hydrodynamics to solve the full form of viscosity, constructing a sparse linear system with a symmetric positive definite matrix, while exploiting the variational principle that automatically enforces the boundary condition on free surfaces. We also propose a new method for extracting coefficients of the matrix contributed by second‐ring neighbor particles to efficiently solve the linear system using a conjugate gradient solver. Several examples demonstrate the robustness and efficiency of our implicit formulation over previous methods and illustrate the versatility of our method.     

Stable and Fast Fluid–Solid Coupling for Incompressible SPH

The solid boundary handling has been a research focus in physically based fluid animation. In this paper, we propose a novel stable and fast particle method to couple predictive–corrective incompressible smoothed particle hydrodynamics and geometric lattice shape matching (LSM), which animates the visually realistic interaction of fluids and deformable solids allowing larger time steps or velocity differences. By combining the boundary particles sampled from solids with a momentum‐conserving velocity‐position correction scheme, our approach can alleviate the particle deficiency issues and prevent the penetration artefacts at the fluid–solid interfaces simultaneously. We further simulate the stable deformation and melting of solid objects coupled to smoothed particle hydrodynamics fluids based on a highly extended LSM model. In order to improve the time performance of each time step, we entirely implement the unified particle framework on GPUs using compute unified device architecture. The advantages of our two‐way fluid–solid coupling method in computer animation are demonstrated via several virtual scenarios.     

Monolithic Friction and Contact Handling for Rigid Bodies and Fluids Using SPH

We propose a novel monolithic pure SPH formulation to simulate fluids strongly coupled with rigid bodies. This includes fluid incompressibility, fluid–rigid interface handling and rigid–rigid contact handling with a viable implicit particle-based dry friction formulation. The resulting global system is solved using a new accelerated solver implementation that outperforms existing fluid and coupled rigid–fluid simulation approaches. We compare results of our simulation method to analytical solutions, show performance evaluations of our solver and present a variety of new and challenging simulation scenarios.     

Local Poisson SPH For Viscous Incompressible Fluids

Enforcing fluid incompressibility is one of the time‐consuming aspects in SPH. In this paper, we present a local Poisson SPH (LPSPH) method to solve incompressibility for particle based fluid simulation. Considering the pressure Poisson equation, we first convert it into an integral form, and then apply a discretization to convert the continuous integral equation to a discretized summation over all the particles in the local pressure integration domain determined by the local geometry. To control the approximation error, we further integrate our local pressure solver into the predictive‐corrective framework to avoid the computational cost of solving a pressure Poisson equation globally. Our method can effectively eliminate the large density deviations mainly caused by the solid boundary treatment and free surface topological change, and show advantage of a higher convergence rate over the predictive‐corrective incompressible SPH (PCISPH).     

Deformable Objects Collision Handling with Fast Convergence

We present a stable and efficient simulator for deformable objects with collisions and contacts. For stability, an optimization derived from the implicit time integrator is solved in each timestep under the inequality constraints coming from collisions. To achieve fast convergence, we extend the MPRGP based solver from handling box constraints only to handling general linear constraints and prove its convergence. This generalization introduces a cost of solving dense linear systems in each step, but these systems can be reduced into diagonal ones for efficiency without affecting the general stability via pruning redundant collisions. Our solver is an order of magnitude faster, especially for elastic objects under large deformation compared with iterative constraint anticipation method (ICA), a typical method for stability. The efficiency, robustness and stability are further verified by our results.     

SSD: Smooth Signed Distance Surface Reconstruction

We introduce a new variational formulation for the problem of reconstructing a watertight surface defined by an implicit equation, from a finite set of oriented points; a problem which has attracted a lot of attention for more than two decades. As in the Poisson Surface Reconstruction approach, discretizations of the continuous formulation reduce to the solution of sparse linear systems of equations. But rather than forcing the implicit function to approximate the indicator function of the volume bounded by the implicit surface, in our formulation the implicit function is forced to be a smooth approximation of the signed distance function to the surface. Since an indicator function is discontinuous, its gradient does not exist exactly where it needs to be compared with the normal vector data. The smooth signed distance has approximate unit slope in the neighborhood of the data points. As a result, the normal vector data can be incorporated directly into the energy function without implicit function smoothing. In addition, rather than first extending the oriented points to a vector field within the bounding volume, and then approximating the vector field by a gradient field in the least squares sense, here the vector field is constrained to be the gradient of the implicit function, and a single variational problem is solved directly in one step. The formulation allows for a number of different efficient discretizations, reduces to a finite least squares problem for all linearly parameterized families of functions, and does not require boundary conditions. The resulting algorithms are significantly simpler and easier to implement, and produce results of quality comparable with state‐of‐the‐art algorithms. An efficient implementation based on a primal‐graph octree‐based hybrid finite element‐finite difference discretization, and the Dual Marching Cubes isosurface extraction algorithm, is shown to produce high quality crack‐free adaptive manifold polygon meshes.     

Direct Position‐Based Solver for Stiff Rods

In this paper, we present a novel direct solver for the efficient simulation of stiff, inextensible elastic rods within the position‐based dynamics (PBD) framework. It is based on the XPBD algorithm, which extends PBD to simulate elastic objects with physically meaningful material parameters. XPBD approximates an implicit Euler integration and solves the system of non‐linear equations using a non‐linear Gauss–Seidel solver. However, this solver requires many iterations to converge for complex models and if convergence is not reached, the material becomes too soft. In contrast, we use Newton iterations in combination with our direct solver to solve the non‐linear equations which significantly improves convergence by solving all constraints of an acyclic structure (tree), simultaneously. Our solver only requires a few Newton iterations to achieve high stiffness and inextensibility. We model inextensible rods and trees using rigid segments connected by constraints. Bending and twisting constraints are derived from the well‐established Cosserat model. The high performance of our solver is demonstrated in highly realistic simulations of rods consisting of multiple 10 000 segments. In summary, our method allows the efficient simulation of stiff rods in the PBD framework with a speedup of two orders of magnitude compared to the original XPBD approach.     

Building a Large Database of Facial Movements for Deformation Model‐Based 3D Face Tracking

We introduce a new markerless 3D face tracking approach for 2D videos captured by a single consumer grade camera. Our approach takes detected 2D facial features as input and matches them with projections of 3D features of a deformable model to determine its pose and shape. To make the tracking and reconstruction more robust we add a smoothness prior for pose and deformation changes of the faces. Our major contribution lies in the formulation of the deformation prior which we derive from a large database of facial animations showing different (dynamic) facial expressions of a fairly large number of subjects. We split these animation sequences into snippets of fixed length which we use to predict the facial motion based on previous frames. In order to keep the deformation model compact and independent from the individual physiognomy, we represent it by deformation gradients (instead of vertex positions) and apply a principal component analysis in deformation gradient space to extract the major modes of facial deformation. Since the facial deformation is optimized during tracking, it is particularly easy to apply them to other physiognomies and thereby re‐target the facial expressions. We demonstrate the effectiveness of our technique on a number of examples.     

Creating and Preserving Vortical Details in SPH Fluid

We present a new method to create and preserve the turbulent details generated around moving objects in SPH fluid. In our approach, a high‐resolution overlapping grid is bounded to each object and translates with the object. The turbulence formation is modeled by resolving the local flow around objects using a hybrid SPH‐FLIP method. Then these vortical details are carried on SPH particles flowing through the local region and preserved in the global field in a synthetic way. Our method provides a physically plausible way to model the turbulent details around both rigid and deformable objects in SPH fluid, and can efficiently produce animations of complex gaseous phenomena with rich visual details.     

Efficient GPU Data Structures and Methods to Solve Sparse Linear Systems in Dynamics Applications

We present graphics processing unit (GPU) data structures and algorithms to efficiently solve sparse linear systems that are typically required in simulations of multi‐body systems and deformable bodies. Thereby, we introduce an efficient sparse matrix data structure that can handle arbitrary sparsity patterns and outperforms current state‐of‐the‐art implementations for sparse matrix vector multiplication. Moreover, an efficient method to construct global matrices on the GPU is presented where hundreds of thousands of individual element contributions are assembled in a few milliseconds. A finite‐element‐based method for the simulation of deformable solids as well as an impulse‐based method for rigid bodies are introduced in order to demonstrate the advantages of the novel data structures and algorithms. These applications share the characteristic that a major computational effort consists of building and solving systems of linear equations in every time step. Our solving method results in a speed‐up factor of up to 13 in comparison to other GPU methods.     

Latent‐space Dynamics for Reduced Deformable Simulation

We propose the first reduced model simulation framework for deformable solid dynamics using autoencoder neural networks. We provide a data‐driven approach to generating nonlinear reduced spaces for deformation dynamics. In contrast to previous methods using machine learning which accelerate simulation by approximating the time‐stepping function, we solve the true equations of motion in the latent‐space using a variational formulation of implicit integration. Our approach produces drastically smaller reduced spaces than conventional linear model reduction, improving performance and robustness. Furthermore, our method works well with existing force‐approximation cubature methods.     

Robust and Efficient Wave Simulations on Deforming Meshes

The goal of this paper is to enable the interactive simulation of phenomena such as animated fluid characters. While full 3D fluid solvers achieve this with control algorithms, these 3D simulations are usually too costly for real‐time environments. In order to achieve our goal, we reduce the problem from a three‐ to a two‐dimensional one, and make use of the shallow water equations to simulate surface waves that can be solved very efficiently. In addition to a low runtime cost, stability is likewise crucial for interactive applications. Hence, we make use of an implicit time integration scheme to obtain a robust solver. To ensure a low energy dissipation, we apply an Implicit Newmark time integration scheme. We propose a general formulation of the underlying equations that is tailored towards the use with an Implicit Newmark integrator. Furthermore, we gain efficiency by making use of a direct solver. Due to the generality of our formulation, the fluid simulation can be coupled interactively with arbitrary external forces, such as forces caused by inertia or collisions. We will discuss the properties of our algorithm, and demonstrate its robustness with simulations on strongly deforming meshes.     

A Physically Consistent Implicit Viscosity Solver for SPH Fluids

In this paper, we present a novel physically consistent implicit solver for the simulation of highly viscous fluids using the Smoothed Particle Hydrodynamics (SPH) formalism. Our method is the result of a theoretical and practical in‐depth analysis of the most recent implicit SPH solvers for viscous materials. Based on our findings, we developed a list of requirements that are vital to produce a realistic motion of a viscous fluid. These essential requirements include momentum conservation, a physically meaningful behavior under temporal and spatial refinement, the absence of ghost forces induced by spurious viscosities and the ability to reproduce complex physical effects that can be observed in nature. On the basis of several theoretical analyses, quantitative academic comparisons and complex visual experiments we show that none of the recent approaches is able to satisfy all requirements. In contrast, our proposed method meets all demands and therefore produces realistic animations in highly complex scenarios. We demonstrate that our solver outperforms former approaches in terms of physical accuracy and memory consumption while it is comparable in terms of computational performance. In addition to the implicit viscosity solver, we present a method to simulate melting objects. Therefore, we generalize the viscosity model to a spatially varying viscosity field and provide an SPH discretization of the heat equation.     

Smoothing of Partition of Unity Implicit Surfaces for Noise Robust Surface Reconstruction

We propose a novel method for smoothing partition of unity (PU) implicit surfaces consisting of sets of non-conforming linear functions with spherical supports. We derive new discrete differential operators and Laplacian smoothing using a spherical covering of PU as a grid-like data structure. These new differential operators are applied to the smoothing of PU implicit surfaces. First, Laplacian smoothing is performed for the vector field defined by the gradient of the PU implicit surface, which is then updated to reflect the smoothing of the gradient field. This process achieves a method for noise robust surface reconstruction from scattered points.     

An Optimization-based SPH Solver for Simulation of Hyperelastic Solids

This paper proposes a novel method for simulating hyperelastic solids with Smoothed Particle Hydrodynamics (SPH). The proposed method extends the coverage of the state-of-the-art elastic SPH solid method to include different types of hyperelastic materials, such as the Neo-Hookean and the St. Venant-Kirchoff models. To this end, we reformulate an implicit integration scheme for SPH elastic solids into an optimization problem and solve the problem using a general-purpose quasi-Newton method. Our experiments show that the Limited-memory BFGS (L-BFGS) algorithm can be employed to efficiently solve our optimization problem in the SPH framework and demonstrate its stable and efficient simulations for complex materials in the SPH framework. Thanks to the nature of our unified representation for both solids and fluids, the SPH formulation simplifies coupling between different materials and handling collisions.     

Smart Scribbles for Sketch Segmentation

We present ‘Smart Scribbles’—a new scribble‐based interface for user‐guided segmentation of digital sketchy drawings. In contrast to previous approaches based on simple selection strategies, Smart Scribbles exploits richer geometric and temporal information, resulting in a more intuitive segmentation interface. We introduce a novel energy minimization formulation in which both geometric and temporal information from digital input devices is used to define stroke‐to‐stroke and scribble‐to‐stroke relationships. Although the minimization of this energy is, in general, an NP‐hard problem, we use a simple heuristic that leads to a good approximation and permits an interactive system able to produce accurate labellings even for cluttered sketchy drawings. We demonstrate the power of our technique in several practical scenarios such as sketch editing, as‐rigid‐as‐possible deformation and registration, and on‐the‐fly labelling based on pre‐classified guidelines.