Hardware-Aware Analysis and Optimization of Stable Fluids

 We perform a detailed flop and bandwidth analysis of Jos Stam’s Stable Fluids algorithm on the CPU, GPU, and Cell. In all three cases, we find that the algorithm is bandwidth bound, with the cores sitting idle up to 96% of the time. Knowing this, we propose two modifications to accelerate the algorithm. First, a Mehrstellen discretization for the pressure solver which reduces the running time of the solver by a third. Second, a static caching scheme that eliminates roughly 99% of the random lookups in the advection stage. We observe a 2x speedup in the advection stage using this scheme. Both modifications apply equally well to all three architectures.

Hardware-Aware Analysis and Optimization of Stable Fluids

Fast Collision Detection for Deformable Models using Representative-Triangles

We present a new approach to accelerate collision detection for deformable models. Our formulation applies to all triangulated models and significantly reduces the number of elementary tests between features of the mesh, i.e., vertices, edges and faces. We introduce the notion of Representative-Triangles, standard geometric triangles augmented with mesh feature information and use this representation to achieve better collision query performance. The resulting approach can be combined with bounding volume hierarchies and works well for both inter-object and self-collision detection. We demonstrate the benefit of Representative-Triangles on continuous collision detection for cloth simulation and N-body collision scenarios. We observe up to a one-order of magnitude reduction in feature-pair tests and up to a 5X improvement in query time.

Fast Collision Detection for Deformable Models using Representative-Triangles

An Adaptive Contact Model for the Robust Simulation of Knots

In this paper, we present an adaptive model for dynamically deforming hyper-elastic rods. In contrast to existing approaches, adaptively introduced control points are not governed by geometric subdivision rules. Instead, their states are determined by employing a non-linear energy-minimization approach. Since valid control points are computed instantaneously, post-stabilization schemes are avoided and the stability of the dynamic simulation is improved.  Due to inherently complex contact configurations, the simulation of knot tying using rods is a challenging task. In order to address this problem, we combine our adaptive model with a robust and accurate collision handling method for elastic rods. By employing our scheme, complex knot configurations can be simulated in a physically plausible way.

An Adaptive Contact Model for the Robust Simulation of Knots

A Fast and Stable Penalty Method for Rigid Body Simulation

Two methods have been used extensively to model resting contact for rigid body simulation. The first approach, the penalty method, applies virtual springs to surfaces in contact to minimize interpenetration. This method, as typically implemented, results in oscillatory behavior and considerable penetration. The second approach, based on formulating resting contact as a linear complementarity problem, determines the resting contact forces analytically to prevent interpenetration. The analytical method exhibits expected-case polynomial complexity in the number of contact points, and may fail to find a solution in polynomial time when friction is modeled. We present a fast penalty method that minimizes oscillatory behavior and leads to little penetration during resting contact; our method compares favorably to the analytical method with regard to these two measures, while exhibiting much faster performance both asymptotically and empirically.

A Fast and Stable Penalty Method for Rigid Body Simulation

Two-Way Coupled SPH and Particle Level Set Fluid Simulation

Grid-based methods have difficulty resolving features on or below the scale of the underlying grid. Although adaptive methods (e.g. RLE, octrees) can alleviate this to some degree, separate techniques are still required for simulating small-scale phenomena such as spray and foam, especially since these more diffuse materials typically behave quite differently than their denser counterparts. In this paper, we propose a two-way coupled simulation framework that uses the particle level set method to efficiently model dense liquid volumes and a smoothed particle hydrodynamics (SPH) method to simulate diffuse regions such as sprays. Our novel SPH method allows us to simulate both dense and diffuse water volumes, fully incorporates the particles that are automatically generated by the particle level set method in under-resolved regions, and allows for two way mixing between dense SPH volumes and grid-based liquid representations.

Two-Way Coupled SPH and Particle Level Set Fluid Simulation

Level Set Driven Flows

In 2D, incompressible flows, the Stokes equations that represent the dynamics of very viscous flows and vorticity formulation of hydrodynamic equations both reduce to a scalar stream-function representation in terms of elliptic equations. By making use of this simplification and the properties of Fourier space representation of elliptic equations, we use a common spectral method to solve both of these equations. Based on this system of equations, we propose a level set based input description which provides a flexible environment for the user to model a wide range of flows and artistic effects in 2D. This input type allows the modeling of vortex sheet patterns and other complex flows with a very practical approach and chaotic, dynamic flows, even with viscous Stokes equations. A user interface is developed for the level set input which allows the user to draw the strokes or edit the level set data by applying transformation functions or perturbations. To sum up, this model can be used for the simulation of very viscous flows, vorticity dynamics, vortex sheet patterns, turbulent and chaotic flows as well as other artistic effects such as the traditional marbling patterns, with a simple, fast and stable system at high resolutions.

Level Set Driven Flows

Some Theses…

Frank Losasso’s PhD thesis on fluid simulation, which contains previously unpublished work on coupling together SPH and level set based fluid simulations:

Algorithms for Increasing the Efficiency and Fidelity of Fluid Simulation

Eftychios Sifakis’ PhD thesis on face, muscle, speech, and surgery simulation:

Algorithmic Aspects of the Simulation and Control of Computer Generated Human Anatomy Models

Geoffrey Irving’s PhD thesis on a variety of physics simulation topics:

Methods for the Physically-Based Simulation of Solids and Fluids

Update: While I’m doing the thesis thing, here’s a couple slightly older ones that are probably worth a look.

Adam Bargteil’s PhD thesis on liquid surface tracking.

Surface Tracking and Texturing

Bart Adams PhD thesis on point-based graphics:

Point-Based Modeling, Animation and Rendering of Dynamic Objects