Real-Time Simulation of Large Bodies of Water with Small Scale Details

We present a hybrid water simulation method that combines grid based and particles based approaches. Our specialized shallow water solver can handle arbitrary underlying terrain slopes, arbitrary water depth and supports wet-dry regions tracking. To treat open water scenes we introduce a method for handling non-reflecting boundary conditions. Regions of liquid that cannot be represented by the height field including breaking waves, water falls and splashing due to rigid and soft bodies interaction are automatically turned into spray, splash and foam particles. The particles are treated as simple non-interacting point masses and they exchange mass and momentum with the height field fluid. We also present a method for procedurally adding small scale waves that are advected with the water flow. We demonstrate the effectiveness of our method in various test scene including a large flowing river along a valley with beaches, big rocks, steep cliffs and waterfalls. Both the grid and the particles simulations are implemented in CUDA. We achieve real-time performance on modern GPUs in all the examples.

Real-Time Simulation of Large Bodies of Water with Small Scale Details

SIGGRAPH 2010 papers

Kesen’s page of 2010 SIGGRAPH papers is up.

Here’s the list of SIGGRAPH 2010 physics-based animation papers to appear so far:

And a few TOG papers that I understand will be presented there too…

Dynamic Local Remeshing for Elastoplastic SimulationDynamic

SCA 2010 papers

The full list of accepted papers for SCA 2010 has been posted, and Ke-Sen’s collection is here.  Here’s the physics ones:

Efficient Yarn-Based Cloth Simulation With Adaptive Contact Linearization

Yarn-based cloth simulation can improve visual quality but at high computational costs due to the reliance on numerous persistent yarn-yarn contacts to generate material behavior. Finding so many contacts in densely interlinked geometry is a pathological case for traditional collision detection, and the sheer number of contact interactions makes contact processing the simulation bottleneck. In this paper, we propose a method for approximating penalty-based contact forces in yarn-yarn collisions by computing the exact contact response at one time step, then using a rotated linear force model to approximate forces in nearby deformed configurations. Because contacts internal to the cloth exhibit good temporal coherence, sufficient accuracy can be obtained with infrequent updates to the approximation, which are done adaptively in space and time. Furthermore, by tracking contact models we reduce the time to detect new contacts. The end result is a 7- to 9-fold speedup in contact processing and a 4- to 5-fold overall speedup, enabling simulation of character-scale garments.

Efficient Yarn-Based Cloth Simulation With Adaptive Contact Linearization

A Novel Algorithm for Incompressible Flow Using Only A Coarse Grid Projection

Large scale fluid simulation can be difficult using existing techniques due to the high computational cost of using large grids. We present a novel technique for simulating detailed fluids quickly. Our technique coarsens the Eulerian fluid grid during the pressure solve, allowing for a fast implicit update but still maintaining the resolution obtained with a large grid. This allows our simulations to run at a fraction of the cost of existing techniques while still providing the fine scale structure and details obtained with a full projection. Our algorithm scales well to very large grids and large numbers of processors, allowing for high fidelity simulations that would otherwise be intractable.

A Novel Algorithm for Incompressible Flow Using Only A Coarse Grid Projection

A Simple Geometric Model for Elastic Deformations

We advocate a simple geometric model for elasticity: distance between the differential of a deformation and the rotation group. It comes with rigorous differential geometric underpinnings, both smooth and discrete, and is computationally almost as simple and efficient as linear elasticity. Owing to its geometric non-linearity, though, it does not suffer from the usual linearization artifacts. A material model with standard elastic moduli (Lame parameters) falls out naturally, and a minimizer for static problems is easily augmented to construct a fully variational 2nd order time integrator. It has excellent conservation properties even for very coarse simulations, making it very robust. Our analysis was motivated by a number of heuristic, physics-like algorithms from geometry processing (editing, morphing, parameterization, and simulation). Starting with a continuous energy formulation and taking the underlying geometry into account, we simplify and accelerate these algorithms while avoiding common pitfalls. Through the connection with the Biot strain of mechanics, the intuition of previous work that these ideas are “like” elasticity is shown to be spot on.

A Simple Geometric Model for Elastic Deformations

A parallel multigrid Poisson solver for fluids simulation on large grids

We present a highly efficient numerical solver for the Poisson equation on irregular voxelized domains supporting an arbitrary mix of Neumann and Dirichlet boundary conditions. Our approach employs a multigrid cycle as a preconditioner for the conjugate gradient method, which enables the use of a lightweight, purely geometric multigrid scheme while drastically improving convergence and robustness on irregular domains. Our method is designed for parallel execution on shared-memory platforms and poses modest requirements in terms of bandwidth and memory footprint. Our solver will accommodate as many as 768X1152 voxels with a memory footprint less than 16GB, while a full smoke simulation at this resolution fits in 32GB of RAM. Our preconditioned conjugate gradient solver typically reduces the residual by one order of magnitude every 2 iterations, while each PCG iteration requires approximately 6.1 sec on a 16-core SMP at 768^3 resolution. We demonstrate the efficacy of our method on animations of smoke flow past solid objects and free surface water animations using Poisson pressure projection at unprecedented resolutions.

A parallel multigrid Poisson solver for fluids simulation on large grids

Discrete Viscous Threads

We present a continuum-based discrete model for thin threads of viscous fluid by drawing upon the Rayleigh analogy to elastic rods, demonstrating canonical coiling, folding, and breakup in dynamic simulations. Our derivation emphasizes space-time symmetry, which sheds light on the role of time-parallel transport in eliminating — without approximation — all but an O(n) band of entries of the physical system’s energy Hessian. The result is a fast, unified, implicit treatment of viscous threads and elastic rods that closely reproduces a variety of fascinating physical phenomena, including hysteretic transitions between coiling regimes, competition between surface tension and gravity, and the first numerical fluid-mechanical sewing machine. The novel implicit treatment also yields an order of magnitude speedup in our elastic rod dynamics.

Discrete Viscous Threads

Enhancing Fluid Animation with Adaptive, Controllable, and Intermittent Turbulence

This paper proposes a new scheme for enhancing fluid animation with controllable turbulence. An existing fluid simulation from ordinary fluid solvers is fluctuated by turbulent variation modeled as a random process of forcing. The variation is precomputed as a sequence of solenoidal noise vector fields directly in the spectral domain, which is fast and easy to implement. The spectral generation enables flexible vortex scale and spectrum control following a user prescribed energy spectrum, e.g. Kolmogorov’s cascade theory, so that the fields provide fluctuations in subgrid scales and/or in preferred large octaves. The vector fields are employed as turbulence forces to agitate the existing flow, where they act as a stimulus of turbulence inside the framework of the Navier-Stokes equations, leading to natural integration and temporal consistency. The scheme also facilitates adaptive turbulent enhancement steered by various physical or user-defined properties, such as strain rate, vorticity, distance to objects and scalar density, in critical local regions. Furthermore, an important feature of turbulent fluid, intermittency, is created by applying turbulence control during randomly selected temporal periods.

Enhancing Fluid Animation with Adaptive, Controllable, and Intermittent Turbulence

FASTCD: Fracturing-Aware Stable Collision Detection

We present a collision detection (CD) method for complex and large-scale fracturing models that have geometric and topological changes. We first propose a novel dual-cone culling method to improve the performance of CD, especially self-collision detection among fracturing models. Our dual-cone culling method has a small computational overhead and a conservative algorithm. Combined with bounding volume hierarchies (BVHs), our dual-cone culling method becomes approximate. However, we found that our method does not miss any collisions in the tested benchmarks. We also propose a novel, selective restructuring method that improves the overall performance of CD and reduces performance degradations at fracturing events. Our restructuring method is based on a culling efficiency metric that measures the expected number of overlap tests of a BVH. To further reduce the performance degradations at fracturing events, we also propose a novel, fast BVH construction method that builds multiple levels of the hierarchy in one iteration using a grid and hashing. We test our method with four different large-scale deforming benchmarks. Compared to the state-of-the-art methods, our method shows a more stable performance for CD by improving the performance by a factor of up to two orders of magnitude at frames when deforming models change their mesh topologies.

FASTCD: Fracturing-Aware Stable Collision Detection