Physics-Based Animation

Multigrid finite-element solvers using the corotational formulation of finite elements provide an attractive means for the simulation of deformable bodies exhibiting linear elastic response. The separation of rigid body motions from the total element motions using purely geometric methods or polar decomposition of the deformation gradient, however, can introduce instabilities for large element rotations and deformations. Furthermore, the integration of the corotational formulation into dynamic multigrid elasticity simulations requires to continually rebuild consistent system matrices at different resolution levels. The computational load imposed by these updates prohibits the use of large numbers of finite elements at rates comparable to the small-strain finite element formulation. To overcome the first problem, we present a new method to extract the rigid body motion from total finite element displacements based on energy minimization. This results in a very stable corotational formulation that only slightly increases the computational overhead. We address the second problem by introducing a novel algorithm for computing sparse products of the form RKRT, as they have to be evaluated to update the multigrid hierarchy. By reformulating the problem into the simultaneous processing of a sequential data and control stream, cache miss penalties are significantly reduced. Even though the algorithm increases memory requirements, it accelerates the multigrid FE simulation by a factor of up to 4 compared to previous multigrid approaches. Due to the proposed improvements, finite element deformable body simulations using the corotational formulation can be performed at rates of 17 tps for up to 12k elements.

Corotated Finite Elements Made Fast and Stable

The Position Based Dynamics approach (PBD) recently introduced allows robust simulations of dynamic systems in real time. The simplicity of the method is due to the fact, that the solver processes the constraints one by one in a Gauss-Seidel type manner. In contrast to global Newton-Raphson solvers, the local solver can easily handle non-linear constraints as well as constraints based on inequalities. Unfortunately, this advantage comes at the price of much slower convergence.  In this paper we propose a multi-grid based process to speed up the convergence of PBD significantly while keeping the power of the method to process general non-linear constraints. Several examples show that the new approach is significantly faster than the original one. This makes real time simulation possible at a higher level of detail in interactive applications such as computer games.

Hierarchical Position Based Dynamics

We propose a novel boundary handling algorithm for particle-based fluids. Based on a predictor-corrector scheme for both velocity and position, one- and two-way coupling with rigid bodies can be realized. The proposed algorithm offers significant improvements over existing penalty-based approaches. Different slip conditions can be realized and non-penetration is enforced. Direct forcing is employed to meet the desired boundary conditions and to ensure valid states after each simulation step. We have performed various experiments in 2D and 3D. They illustrate one- and two-way coupling of rigid bodies and fluids, the effects of hydrostatic and dynamic forces on a rigid body as well as different slip conditions. Numerical experiments and performance measurements are provided.

Direct Forcing for Lagrangian Rigid-Fluid Coupling

“We present a novel technique for the animation of turbulent fluids by coupling a procedural turbulence model with a numerical fluid solver to introduce subgrid-scale flow detail. From the large-scale flow simulated by the solver, we model the production and behavior of turbulent energy using a physically motivated energy model. This energy distribution is used to synthesize an incompressible turbulent velocity field, whose features show plausible temporal behavior through a novel Lagrangian approach for advected noise. The synthesized turbulent flow has a dynamical effect on the large-scale flow, and produces visually plausible detailed features on both gaseous and free-surface liquid flows. Our method is an order of magnitude faster than full numerical simulation of equivalent resolution, and requires no manual direction.”

Fast Animation of Turbulence Using Energy Transport and Procedural Synthesis

Recent advances have brought real-time physically based simulation within reach, but simulations are still difficult to control in real time. We present interactive simulations of passive systems such as deformable solids or fluids that are not only fast, but also directable: they follow given input trajectories while simultaneously reacting to user input and other unexpected disturbances. We achieve such directability using a real-time controller that runs in tandem with a real-time physically based simulation. To avoid stiff and overcontrolled systems where the natural dynamics are overpowered, the injection of control forces has to be minimized. This search for gentle forces can be made tractable in real-time by linearizing the system dynamics around the input trajectory, and then using a time-varying linear quadratic regulator to build the controller. We show examples of controlled complex deformable solids and fluids, demonstrating that our approach generates a requested fixed outcome for reasonable user inputs, while simultaneously providing runtime motion variety.

Real-time Control of Physically Based Simulations using Gentle Forces

The list of SIGGRAPH Asia papers is up…

For physics, there’s basically 5 papers:

• Magnets in Motion
• Real-time Control of Physically Based Simulations using Gentle Forces
• Staggered Projections for Frictional Contact in Multibody Systems
• Optimizing Cubature for Efficient Integration of Subspace Deformations
• Fast Animation of Turbulence Using Energy Transport and Procedural Synthesis

We present a new discrete velocity-level formulation of frictional contact dynamics that reduces to a pair of coupled projections and introduce a simple fixed-point property of this coupled system. This allows us to construct a novel algorithm for accurate frictional contact resolution based on a simple staggered sequence of projections. The algorithm accelerates performance using warm starts to leverage the potentially high temporal coherence between contact states and provides users with direct control over frictional accuracy. Applying this algorithm to rigid and deformable systems, we obtain robust and accurate simulations of frictional contact behavior not previously possible, at rates suitable for interactive haptic simulations, as well as large-scale animations. By construction, the proposed algorithm guarantees exact, velocity-level contact constraint enforcement and obtains long-term stable and robust integration. Examples are given to illustrate the performance, plausibility and accuracy of the obtained solutions.

Staggered Projections for Frictional Contact in Multibody Systems

Precise contact modeling is essential when simulating rigid or deformable objects in interaction. Yet, most recent work in computer graphics has focused on the computation of the motion or deformation of objects, and little has been done to model the interaction between simulated objects. In this paper, we propose a novel and very efficient approach for precise computation of contact response between various types of objects commonly used in computer animation. Our approach represents the objects motion as a free motion and a corrective motion. The corrective motion uses an efficient contact model, based on an approximation of the behavior model, but still follows Signorini and Coulomb laws for contact and friction modeling. Our approach guarantees no interpenetration at the end of the time step, and only introduces a minimal error in the objects motion. We illustrate our approach using an approximate (warped) compliance in the case of non-linear deformable models. This speeds-up the contact response by several orders of magnitude, thus allowing the simulation of scenes with many complex interacting objects.

Efficient Contact Modeling using Compliance Warping

We propose a particle-based technique for simulating incompressible fluid that includes adaptive refinement of particle sampling. Each particle represents a mass of fluid in its local region. Particles are split into several particles for finer sampling in regions of complex flow. In regions of smooth flow, neighboring particles can be merged. Depth below the surface and Reynolds number are exploited as our criteria for determining whether splitting or merging should take place. For the fluid dynamics calculations, we use the hybrid FLIP method, which is computationally simple and efficient. Since the fluid is incompressible, each particle has a volume proportional to its mass. A kernel function, whose effective range is based on this volume, is used for transferring and updating the particle’s physical properties such as mass and velocity. Our adaptive particle-based simulation is demonstrated in several scenarios that show its effectiveness in capturing fine detail of the flow, where needed, while efficiently sampling regions where less detail is required.

Adaptive Particles for Incompressible Fluid Simulation

We present a remeshed vortex particle method for incompressible flow simulations on GPUs. The particles are convected in a Lagrangian frame and are periodically reinitialized on a regular grid. The grid is used in addition to solve for the velocity–vorticity Poisson equation and for the computation of the diffusion operators. In the present GPU implementation of particle methods, the remeshing and the solution of the Poisson equation rely on fast and efficient mesh-particle interpolations. We demonstrate that particle remeshing introduces minimal artificial dissipation, enables a faster computation of differential operators on particles over grid-free techniques and can be efficiently implemented on GPUs. The results demonstrate that, contrary to common practice in particle simulations, it is necessary to remesh the (vortex) particle locations in order to solve accurately the equations they discretize, without compromising the speed of the method. The present method leads to simulations of incompressible vortical flows on GPUs with unprecedented accuracy and efficiency.

Vortex Methods for Incompressible Flow Simulation on the GPU