Interpenetration Free Simulation of Thin Shell Rigid Bodies


English, E., Lentine, M., and Fedkiw, R.
IEEE TVCG 19, 991-1004 (2013).

We propose a new algorithm for rigid body simulation that guarantees each body is in an interpenetration free state, both increasing the accuracy and robustness of the simulation as well as alleviating the need for ad hoc methods to separate bodies for subsequent simulation and rendering. We cleanly separate collision and contact resolution such that objects move and collide in the first step, with resting contact handled in the second step. The first step of our algorithm guarantees that each time step produces geometry that does not intersect or overlap by using an approximation to the continuous collision detection (and response) problem and thus is amenable to thin shells and degenerately flat objects moving at high speeds. In addition we introduce a novel failsafe which allows us to resolve all interpenetration without iterating to convergence. Since the first step guarantees a non-interfering state for the geometry, in the second step we propose a contact model for handling thin shells in proximity considering only the instantaneous locations at the ends of the time step.

Fast and Scalable Methods for the Simulation of Incompressible Flow


Lentine, M.
Stanford University Department of Computer Science Thesis (2012).

This dissertation presents efficient and scalable algorithms for the simulation of incompressible fluids. Physical simulation of fluids is one of the most interesting and challenging problems because of the amount of small scale details that realistic fluids exhibit. Although a large number of high fidelity simulations can be obtained with existing techniques, the resolution that these techniques can obtain is limited by the amount of computational power available. The simulation of incompressible flow has two main aspects: advection and projection. This thesis addresses performance and scalability issues related to both aspects and demonstrates a number of algorithms that work to massively reduce the computational cost of simulations.

Simulating Free Surface Flow with Very Large Time Steps

[pdf]  [video]

Lentine, M., Cong, M., Patkar, S., and Fedkiw, R.
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA) (2012).

We provide a novel simulation method for incompressible free surface flows that allows for large time steps on the order of 10-40 times bigger than the typical explicit time step restriction would allow. Although semi-Lagrangian advection allows for this from the standpoint of stability, large time steps typically produce significant visual errors. This was addressed in previous work for smoke simulation using a mass and momentum conserving version of semi-Lagrangian advection, and while its extension to water for momentum conservation for small time steps was addressed, pronounced issues remain when taking large time steps. The main difference between smoke and water is that smoke has a globally defined velocity field whereas water needs to move in a manner uninfluenced by the surrounding air flow, and this poses real issues in determining an appropriate extrapolated velocity field. We alleviate problems with the extrapolated velocity field by not using it when it is incorrect, which we determine via conservative advection of a color function which adds forwardly advected semi-Lagrangian rays to maintain conservation when mass is lost. We note that one might also use a more traditional volume-of-fluid method which is more explicitly focused on the geometry of the interface but can be less visually appealing -- it is also unclear how to extend volume-of-fluid methods to have larger time steps. Finally, we prefer the visual smoothness of a particle level set method coupled to a traditional backward tracing semi-Lagrangian advection where possible, only using our forward traced color function solution in areas of the flow where the particle level set method fails due to the extremely large time steps.

Mass and Momentum Conservation for Fluid Simulation

[pdf]  [video]

Lentine, M., Aanjaneya, M., and Fedkiw, R.
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA) (2011).

Momentum conservation has long been used as a design principle for solid simulation (e.g. collisions between rigid bodies, mass-spring elastic and damping forces, etc.), yet it has not been widely used for fluid simulation. In fact, semi-Lagrangian advection does not conserve momentum, but is still regularly used as a bread and butter method for fluid simulation. In this paper, we propose a modification to the semi-Lagrangian method in order to make it fully conserve momentum. While methods of this type have been proposed earlier in the computational physics literature, they are not necessarily appropriate for coarse grids, large time steps or inviscid flows, all of which are common in graphics applications. In addition, we show that the commonly used vorticity confinement turbulence model can be modified to exactly conserve momentum as well. We provide a number of examples that illustrate the benefits of this new approach, both in conserving fluid momentum and passively advected scalars such as smoke density. In particular, we show that our new method is amenable to efficient smoke simulation with one time step per frame, whereas the traditional non-conservative semi-Lagrangian method experiences serious artifacts when run with these large time steps, especially when object interaction is considered.

An Unconditionally Stable Fully Conservative Semi-Lagrangian Method


Lentine, M., Gretarsson, J., and Fedkiw, R.
Journal of Computational Physics 230, 2857-2879 (2011).

Semi-Lagrangian methods have been around for some time, dating back at least to [3]. Researchers have worked to increase their accuracy, and these schemes have gained newfound interest with the recent widespread use of adaptive grids where the CFL-based time step restriction of the smallest cell can be overwhelming. Since these schemes are based on characteristic tracing and interpolation, they do not readily lend themselves to a fully conservative implementation. However, we propose a novel technique that applies a conservative limiter to the typical semi-Lagrangian interpolation step in order to guarantee that the amount of the conservative quantity does not increase during this advection. In addition, we propose a new second step that forward advects any of the conserved quantity that was not accounted for in the typical semi-Lagrangian advection. We show that this new scheme can be used to conserve both mass and momentum for incompressible flows. For incompressible flows, we further explore properly conserving kinetic energy during the advection step, but note that the divergence free projection results in a velocity field which is inconsistent with conservation of kinetic energy (even for inviscid flows where it should be conserved). For compressible flows, we rely on a recently proposed splitting technique that eliminates the acoustic CFL time step restriction via an incompressible-style pressure solve. Then our new method can be applied to conservatively advect mass, momentum and total energy in order to exactly conserve these quantities, and remove the remaining time step restriction based on fluid velocity that the original scheme still had.

Creature Control in a Fluid Environment

[pdf]  [video]

Lentine, M., Gretarsson, J., Schroeder, C., Robinson-Mosher, A., and Fedkiw, R.
IEEE TVCG 17, 682-693 (2011).

In this paper, we propose a method designed to allow creatures to actively respond to a fluid environment. We explore various objective functions in order to determine ways to direct the behavior of our creatures. Our proposed method works in conjunction with generalized body forces as well as both one-way and two-way coupled fluid forces. As one might imagine, interesting behaviors can be derived from minimizing and maximizing both drag and lift as well as minimizing the effort that a creature’s internal actuators exert. A major application for our work is the automatic specification of secondary motions, for example, certain joints can be animated while others are automatically solved for in order to satisfy the objective function.

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

[pdf]  [video]

Lentine, M., Zheng, W., and Fedkiw, R.
SIGGRAPH 2010, ACM TOG 29, 4 (2010).

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.

Avatar: Bending Rigid Bodies


Criswell, B., Lentine, M., and Sauers, S.
SIGGRAPH 2010 Talks.

Simulating bending and denting of rigid materials has become an increasingly important aspect for modeling the realistic destruction of objects. Historically, modeling these phenomena has been a tedious and time consuming process for the artists at Industrial Light & Magic. Typically the artists would manually shape the rigid bodies after the simulation to produce this realistic look. However, for the movie Avatar, we have developed a new system that seamlessly transitions between rigid and deformable simulations allowing the artists to achieve realistic destruction without the need to apply any post corrective shapes.

A Mass-Spring Model for Hair Simulation

[pdf]  [video]

Selle, A., Lentine, M., and Fedkiw, R.
SIGGRAPH 2008, ACM TOG 27, 3 (2008).

Our goal is to simulate the full hair geometry, consisting of approximately one hundred thousand hairs on a typical human head. This will require scalable methods that can simulate every hair as opposed to only a few guide hairs. Novel to this approach is that the individual hair/hair interactions can be modeled with physical parameters (friction, static attraction, etc.) at the scale of a single hair as opposed to clumped or continuum interactions. In this vein, we first propose a new altitude spring model for preventing collapse in the simulation of volumetric tetrahedra, and we show that it is also applicable both to bending in cloth and torsion in hair. We demonstrate that this new torsion model for hair behaves in a fashion similar to more sophisticated models with significantly reduced computational cost. For added efficiency, we introduce a semi-implicit discretization of standard springs that makes them truly linear in multiple spatial dimensions and thus unconditionally stable without requiring Newton-Raphson iteration. We also simulate complex hair/hair interactions including sticking and clumping behavior, collisions with objects (e.g. head and shoulders) and selfcollisions. Notably, in line with our goal to simulate the full head of hair, we do not generate any new hairs at render time.