X. L. Wang, M. Tang, D. Manocha, Ruo-Feng Tong
Bounding volume hierarchy (BVH) has been widely adopted as the acceleration structure in broad-phase collision detection. Previous state-of-the-art BVH-based collision detection approaches exploited the spatio-temporal coherence of simulations by maintaining a bounding volume test tree (BVTT) front. A major drawback of these algorithms is that large deformations in the scenes decrease culling efficiency and slow down collision queries. Moreover, for front-based methods, the inefficient caching on GPU caused by the arbitrary layout of BVH and BVTT front nodes becomes a critical performance issue. We present a fast and robust BVH-based collision detection scheme on GPU that addresses the above problems by ordering and restructuring BVHs and BVTT fronts. Our techniques are based on the use of histogram sort and an auxiliary structure BVTT front log, through which we analyze the dynamic status of BVTT front and BVH quality. Our approach efficiently handles inter- and intra-object collisions and performs especially well in simulations where there is considerable spatio-temporal coherence. The benchmark results demonstrate that our approach is significantly faster than the previous BVH-based method, and also outperforms other state-of-the-art spatial subdivision schemes in terms of speed.
Efficient BVH-based Collision Detection Scheme with Ordering and Restructuring
Dimitar Dinev, Tiantian Liu, Ladislav Kavan
We present a new time integration method featuring excellent stability and energy conservation properties, making it particularly suitable for real-time physics. The commonly used backward Euler method is stable but introduces artificial damping. Methods such as implicit midpoint do not suffer from artificial damping but are unstable in many common simulation scenarios. We propose an algorithm that blends between the implicit midpoint and forward/backward Euler integrators such that the resulting simulation is stable while introducing only minimal artificial damping. We achieve this by tracking the total energy of the simulated system, taking into account energy-changing events: damping and forcing. To facilitate real-time simulations, we propose a local/global solver, similar to Projective Dynamics, as an alternative to Newton’s method. Compared to the original Projective Dynamics, which is derived from backward Euler, our final method introduces much less numerical damping at the cost of minimal computing overhead. Stability guarantees of our method are derived from the stability of backward Euler, whose stability is a widely accepted empirical fact. However, to our knowledge, theoretical guarantees have so far only been proven for linear ODEs. We provide preliminary theoretical results proving the stability of backward Euler also for certain cases of nonlinear potential functions.
Stabilizing Integrators for Real-Time Physics
Kui Wu, Nghia Truong, Cem Yuksel, Rama Hoetzlein
We introduce efficient, large scale fluid simulation on GPU hardware using the fluid-implicit particle (FLIP) method over a sparse hierarchy of grids represented in NVIDIA GVDB Voxels. Our approach handles tens of millions of particles within a virtually unbounded simulation domain. We describe novel techniques for parallel sparse grid hierarchy construction and fast incremental updates on the GPU for moving particles. In addition, our FLIP technique introduces sparse, work efficient parallel data gathering from particle to voxel, and a matrix-free GPU-based conjugate gradient solver optimized for sparse grids. Our results show that our method can achieve up to an order of magnitude faster simulations on the GPU as compared to FLIP simulations running on the CPU.
Fast Fluid Simulations with Sparse Volumes on the GPU
Crispin Deul, Tassilo Kugelstadt, Marcel Weiler, Jan Bender
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 ten-thousand segments. In summary, our method allows the efficient simulation of stiff rods in the Position-Based Dynamics framework with a speedup of two orders of magnitude compared to the original XPBD approach.
Direct Position-Based Solver for Stiff Rods
Marcel Weiler, Dan Koschier, Magnus Brand, Jan Bender
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.
A Physically Consistent Implicit Viscosity Solver for SPH Fluids
Breannan Smith, Fernando de Goes, Theodore Kim
Non-linear hyperelastic energies play a key role in capturing the fleshy appearance of virtual characters. Real-world, volume-preserving biological tissues have Poisson’s ratios near 1/2, but numerical simulation within this regime is notoriously challenging. In order to robustly capture these visual characteristics, we present a novel version of Neo-Hookean elasticity. Our model maintains the fleshy appearance of the Neo-Hookean model, exhibits superior volume preservation, and is robust to extreme kinematic rotations and inversions. We obtain closed-form expressions for the eigenvalues and eigenvectors of all of the system’s components, which allows us to directly project the Hessian to semi-positive-definiteness, and also leads to insights into the numerical behavior of the material. These findings also inform the design of more sophisticated hyperelastic models, which we explore by applying our analysis to Fung and Arruda-Boyce elasticity. We provide extensive comparisons against existing material models.
Stable Neo-Hookean Flesh Simulation
Chuyuan Fu, Qi Guo, Theodore Gast, Chenfanfu Jiang, Joseph Teran
Recently the Affine Particle-In-Cell (APIC) Method was proposed by Jiang et al.[2015; 2017b] to improve the accuracy of the transfers in Particle-In-Cell (PIC) [Harlow 1964] techniques by augmenting each particle with a locally
affine, rather than locally constant description of the velocity. This reduced the dissipation of the original PIC without suffering from the noise present in the historic alternative, Fluid-Implicit-Particle (FLIP) [Brackbill and Ruppel 1986]. We present a generalization of APIC by augmenting each particle with a more general local function. By viewing the grid-to-particle transfer as a linear and angular momentum conserving projection of the particle-wise local grid velocities onto a reduced basis, we greatly improve the energy and vorticity conservation over the original APIC. Furthermore, we show that the cost of the generalized projection is negligible over APIC when using a particular class of local polynomial functions. Lastly, we note that our method retains the filtering property of APIC and PIC and thus has similar robustness to noise.
A Polynomial Particle-In-Cell Method
Tao Yang, Jian Chang, Ming C. Lin, Ralph R. Martin, Jian J. Zhang, and Shi-Min Hu
We introduce a unified particle framework which integrates the phase-field method with multi-material simulation to allow modeling of both liquids and solids, as well as phase transitions between them. A simple elastoplastic model is used to capture the behavior of various kinds of solids, including deformable bodies, granular materials, and cohesive soils. States of matter or phases, particularly liquids and solids, are modeled using the nonconservative Allen-Cahn equation. In contrast, materials—made of different substances—are advected by the conservative Cahn-Hilliard equation. The distributions of phases and materials are represented by a phase variable and a concentration variable, respectively, allowing us to represent commonly observed fluid-solid interactions. Our multi-phase, multi-material system is governed by a unified Helmholtz free energy density. This framework provides the first method in computer graphics capable of modeling a continuous interface between phases. It is versatile and can be readily used in many scenarios that are challenging to simulate. Examples are provided to demonstrate the capabilities and effectiveness of this approach.
A Unified Particle System Framework for Multi-Phase, Multi-Material Visual Simulations
Sadashige Ishida, Masafumi Yamamoto, Ryoichi Ando, Toshiya Hachisuka
Simulating the behavior of soap films and foams is a challenging task. A direct numerical simulation of films and foams via the Navier-Stokes equations is still computationally too expensive. We propose an alternative formulation inspired by geometric flow. Our model exploits the fact, according to Plateau’s laws, that the steady state of a film is a union of constant mean curvature surfaces and minimal surfaces. Such surfaces are also well known as the steady state solutions of certain curvature flows. We show a link between the Navier-Stokes equations and a recent variant of mean curvature flow, called hyperbolic mean curvature flow, under the assumption of constant air pressure per enclosed region. We thus introduce hyperbolic mean curvature flow to describe film dynamics. Instead of using hyperbolic mean curvature flow as is, we propose to replace curvature by the gradient of the surface area functional. This formulation enables us to robustly handle non-manifold configurations; such junctions connecting multiple films are intractable with the traditional formulation using curvature. We also add explicit volume preservation to hyperbolic mean curvature flow, which in fact corresponds to the pressure term of the Navier-Stokes equations. Our method is simple, fast, robust, and consistent with Plateau’s laws, which are all due to our reformulation of film dynamics as a geometric flow.
A Hyperbolic Geometric Flow for Evolving Films and Foams