Month: July 2012

Simulating Free Surface Flow with Very Large Timesteps

Michael Lentine, Matthew Cong, Saket Patkar, Ron Fedkiw

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.

Simulating Free Surface Flow with Very Large Timesteps

Mass-Conserving Eulerian Liquid Simulation

Nuttapong Chentanez, Matthias Mueller

We present a GPU friendly, Eulerian, free surface fluid simulation method that conserves mass locally and globally without the use of Lagrangian components. Local mass conservation prevents small scale details of the free surface from disappearing, a problem that plagues many previous approaches, while global mass conservation ensures that the total volume of the liquid does not decrease over time. Our method handles moving solid boundaries as well as cells that are partially filled with solids. Due to its stability, it allows the use of large time steps which makes it suitable for both off-line and real-time applications. We achieve this by using density based surface tracking with a novel, unconditionally stable, conservative advection scheme and a novel interface sharpening method. While our approach conserves mass, volume loss is still possible but only temporarily. With constant mass, local volume loss causes a local increase of the density used for surface tracking which we detect and correct over time. We also propose a density post-processing method to reveal sub-grid details of the liquid surface. We show the effectiveness of the proposed method in several practical examples all running either at interactive rates or in real-time.

Mass-Conserving Eulerian Liquid Simulation

Efficient Collision Detection for Brittle Fracture

Loiez Glondu, Sarah Schvartzman, Maud Marchal, Georges Dumon, Miguel Otaduy

In complex scenes with many objects, collision detection plays a key role in the simulation performance. This is particularly true for fracture simulation, where multiple new objects are dynamically created. In this paper, we present novel algorithms and data structures for collision detection in real-time brittle fracture simulations. We build on a combination of well-known efficient data structures, namely distance fields and sphere trees, making our algorithm easy to integrate on existing simulation engines. We propose novel methods to construct these data structures, such that they can be efficiently updated upon fracture events and integrated in a simple yet effective self-adapting contact selection algorithm. Altogether, we drastically reduce the cost of both collision detection and collision response. We have evaluated our global solution for collision detection on challenging scenarios, achieving high frame rates suited for hard real-time applications such as video games or haptics. Our solution opens promising perspectives for complex brittle fracture simulations involving many dynamically created objects.

Efficient Collision Detection for Brittle Fracture

Mass-Splitting for Jitter-Free Parallel Rigid Body Simulation

Richard Tonge, Feodor Benevolenski, Andrey Voroshilov

We present a parallel iterative rigid body solver that avoids common artifacts at low iteration counts. In large or real-time simulations, iteration is often terminated before convergence to maximize scene size. If the distribution of the resulting residual energy varies too much from frame to frame, then bodies close to rest can visibly jitter. Projected Gauss-Seidel (PGS) distributes the residual according to the order in which contacts are processed, and preserving the order in parallel implementations is very challenging. In contrast, Jacobi-based methods provide order independence, but have slower convergence. We accelerate projected Jacobi by dividing each body mass term in the effective mass by the number of contacts acting on the body, but use the full mass to apply impulses. We further accelerate the method by solving contacts in blocks, providing wallclock performance competitive with PGS while avoiding visible artifacts. We prove convergence to the solution of the underlying linear complementarity problem and present results for our GPU implementation,which can simulate a pile of 5000 objects with no visible jittering at over 60 FPS.

Mass-Splitting for Jitter-Free Parallel Rigid Body Simulation

Deformable Objects Alive!

Stelian Coros, Sebastian Martin, Bernhard Thomaszewski, Christian Schumacher, Robert Sumner, Markus Gross

We present a method for controlling the motions of active deformable characters. As an underlying principle, we require that all motions be driven by internal deformations. We achieve this by dynamically adapting rest shapes in order to induce deformations that, together with environment interactions, result in purposeful and physically-plausible motions. Rest shape adaptation is a powerful concept and we show that by restricting shapes to suitable subspaces, it is possible to explicitly control the motion styles of deformable characters. Our formulation is general and can be combined with arbitrary elastic models and locomotion controllers. We demonstrate the efficiency of our method by animating curve, shell, and solid-based characters whose motion repertoires range from simple hopping to complex walking behaviors.

Deformable Objects Alive!

Energetically Consistent Invertible Elasticity

Alexey Stomakhin, Russell Howes, Craig Schroeder, Joseph Teran

We provide a smooth extension of arbitrary isotropic hyperelastic energy density functions to inverted confi gurations. This extension is designed to improve robustness for elasticity simulations with extremely large deformations and is analogous to the extension given to the first Piola-Kircho ff stress in [ITF04]. We show that our energy-based approach is signi ficantly more robust to large deformations than the first Piola-Kircho ff . Furthermore, we show that the robustness and stability of a hyper-elastic model can be predicted from a characteristic contour, which we call its primary contour. The extension to inverted con figurations is de fined via extrapolation from a convex threshold surface that lies in the uninverted portion of the principal stretches space. The extended hyperelastic energy density yields continuous stress and unambiguous stress derivatives in all inverted con figurations, unlike in [TSIF05]. We show that our invertible energy-density-based approach outperforms the popular hyperelastic corotated model, and we also show how to use the primary contour methodology to improve the robustness of this model to large deformations.

Energetically Consistent Invertible Elasticity

Multiphase Flow of Immiscible Fluids on Unstructured Moving Meshes

Marek Misztal, Kenny Erleben, Adam Bargteil, J. Fursund, Brian Bunch Christensen, Andreas Bærentzen, Robert Bridson

In this paper, we present a method for animating multiphase flow of immiscible fluids using unstructured moving meshes. Our underlying discretization is an unstructured tetrahedral mesh, the deformable simplicial complex (DSC), that moves with the flow in a Lagrangian manner. Mesh optimization operations improve element quality and avoid element inversion. In the context of multiphase flow, we guarantee that every element is occupied by a single fluid and, consequently, the interface between fluids is represented by a set of faces in the simplicial complex. This approach ensures that the underlying discretization matches the physics and avoids the additional book-keeping required in grid-based methods where multiple fluids may occupy the same cell. Our Lagrangian approach naturally leads us to adopt a finite element approach to simulation, in contrast to the finite volume approaches adopted by a majority of fluid simulation techniques that use tetrahedral meshes. We characterize fluid simulation as an optimization problem allowing for full coupling of the pressure and velocity fields and the incorporation of a second-order surface energy. We introduce a preconditioner based on the diagonal Schur complement and solve our optimization on the GPU. We provide the results of parameter studies as well as a performance analysis of our method

Multiphase Flow of Immiscible Fluids on Unstructured Moving Meshes

Linear-Time Smoke Animation with Vortex Sheet Meshes

Tyson Brochu, Todd Keeler, Robert Bridson

We present the first quality physics-based smoke animation method which runs in time approximately linear in the size of the rendered two-dimensional visual detail. Our fundamental representation is a closed triangle mesh surface dividing space between clear air and a uniformly smoky region, on which we compute vortex sheet dynamics to accurately solve inviscid buoyant flow. We handle arbitrary moving no-stick solid boundaries and by default handle an infinite domain. The simulation itself runs in time linear to the number of triangles thanks to the use of a well-conditioned integral equation treatment together with a Fast Multipole Method for linear-time summations, providing excellent performance. Basic zero-albedo smoke rendering, with embedded solids, is easy to implement for interactive rates, and the mesh output can also serve as an extremely compact and detailed input to more sophisticated volume rendering.

Linear-Time Smoke Animation with Vortex Sheet Meshes