Frank Losasso Petterson, Ph.D.

Two-way Coupled SPH and Particle Level Set Fluid Simulation (PDF)

Abstract: 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.

Videos:

Algorithms for Increasing the Efficiency and Fidelity of Fluid Simulations (PDF)

Abstract: A dissertation submitted to the Department of Computer Science and the Committee on Graduate Studies of Stanford University in partial fulfillment of the requirements for the degree of Doctor of Philosophy.

Multiple Interacting Liquids (PDF)

Abstract: The particle level set method has proven successful for the simulation of two separate regions (such as water and air, or fuel and products). In this paper, we propose a novel approach to extend this method to the simulation of as many regions as desired. The various regions can be liquids (or gases) of any type with differing viscosities, densities, viscoelastic properties, etc. We also propose techniques for simulating interactions between materials, whether it be simple surface tension forces or more complex chemical reactions with one material converting to another or two materials combining to form a third. We use a separate particle level set method for each region, and propose a novel projection algorithm that decodes the resulting vector of level set values providing a .dictionary. that translates between them and the standard single-valued level set representation. An additional difficulty occurs since discretization stencils (for interpolation, tracing semi-Lagrangian rays, etc.) cross region boundaries naively combining non-smooth or even discontinuous data. This has recently been addressed via ghost values, e.g. for fire or bubbles. We instead propose a new paradigm that allows one to incorporate physical jump conditions in data "on the fly," which is significantly more efficient for multiple regions especially at triple points or near boundaries with solids.

Videos:

Efficient Simulation of Large Bodies of Water by Coupling Two and Three Dimensional Techniques (PDF)

Abstract: We present a new method for the efficient simulation of large bodies of water, especially effective when three-dimensional surface effects are important. Similar to a traditional two-dimensional height field approach, most of the water volume is represented by tall cells which are assumed to have linear pressure profiles. In order to avoid the limitations typically associated with a height field approach, we simulate the entire top surface of the water volume with a state of the art, fully three-dimensional Navier-Stokes free surface solver. Our philosophy is to use the best available method near the interface (in the three-dimensional region) and to coarsen the mesh away from the interface for efficiency. We coarsen with tall, thin cells (as opposed to octrees or AMR), because they maintain good resolution horizontally allowing for accurate representation of bottom topography.

Videos:

So Real It'll Make You Wet (PDF)

Abstract: For "Poseidon", we had to create multiple shots of photorealistic ocean water interacting with computer-generated objects. The challenge was to create water that was seen both on a huge scale and in close-up, and to go beyond any work previously seen. We solved the following novel problems: rendering a smooth high-resolution tesselation of a levelset and particle set with procedural displacement, surface texture and internal volumetrics; simulating and rendering multiple secondary particle sets driven by a physically based fluid simulation. (Image copyright Warner Bros.)

Melting and Burning Solids into Liquids and Gases (PDF)

Abstract: We propose a novel technique for melting and burning solid materials including the simulation of the resulting liquid and gas. The solid is simulated with traditional mesh-based techniques (triangles or tetrahedra) which enable robust handling of both deformable and rigid objects, collision and self-collision, rolling, friction, stacking, etc. The subsequently created liquid or gas is simulated with modern grid-based techniques including vorticity confinement and the particle level set method. The main advantage of our method is that state of the art techniques are used for both the solid and the fluid without compromising simulation quality when coupling them together or converting one into the other. For example, we avoid modeling solids as Eulerian grid-based fluids with high viscosity or viscoelasticity, which would preclude the handling of thin shells, self-collision, rolling, etc. Thus, our method allows one to achieve new effects while still using their favorite algorithms (and implementations) for simulating both solids and fluids, whereas other coupling algorithms require major algorithm and implementation overhauls and still fail to produce rich coupling effects (e.g. melting and burning solids).

Videos:

Coupling Water and Smoke to Thin Deformable and Rigid Shells (PDF)

Abstract: We present a novel method for solid/fluid coupling that can treat infinitesimally thin solids modeled by a lower dimensional triangulated surface. Since classical solid/fluid coupling algorithms rasterize the solid body onto the fluid grid, an entirely new approach is required to treat thin objects that do not contain an interior region. Robust ray casting is used to augment a number of interpolation, finite difference and rendering techniques so that fluid does not leak through the triangulated surface. Moreover, we propose a technique for properly enforcing incompressibility so that fluid does not incorrectly compress (and appear to lose mass) near the triangulated surface. This allows for the robust interaction of cloth and shells with thin sheets of water. The proposed method works for both rigid body shells and for deformable manifolds such as cloth, and we present a two way coupling technique that allows the fluid's pressure to affect the solid. Examples illustrate that our method performs well, especially in the difficult case of water and cloth where it produces visually rich interactions between the particle level set method for treating the water/air interface and our newly proposed method for treating the solid/fluid interface. We have implemented the method on both uniform and adaptive octree grids.

Videos:

Spatially Adaptive Techniques for Level Set Methods and Incompressible Flow (PDF)

Abstract: Since the seminal work of [92] on coupling the level set method of [69] to the equations for two-phase incompressible flow, there has been a great deal of interest in this area. That work demonstrated the most powerful aspects of the level set method, i.e. automatic handling of topological changes such as merging and pinching, as well as robust geometric information such as normals and curvature. Interestingly, this work also demonstrated the largest weakness of the level set method, i.e. mass or information loss characteristic of most Eulerian capturing techniques. In fact, [92] introduced a partial differential equation for battling this weakness, without which their work would not have been possible. In this paper, we discuss both historical and most recent works focused on improving the computational accuracy of the level set method focusing in part on applications related to incompressible flow due to both its popularity and stringent accuracy requirements. Thus, we discuss higher order accurate numerical methods such as Hamilton-Jacobi WENO [46], methods for maintaining a signed distance function, hybrid methods such as the particle level set method [27] and the coupled level set volume of fluid method [91], and adaptive gridding techniques such as the octree approach to free surface flows proposed in [56].

Simulating Water and Smoke With an Octree Data Structure (PDF)

Abstract: We present a method for simulating water and smoke on an unrestricted octree data structure exploiting mesh refinement techniques to capture the small scale visual detail. We propose a new technique for discretizing the Poisson equation on this octree grid. The resulting linear system is symmetric positive definite enabling the use of fast solution methods such as preconditioned conjugate gradients, whereas the standard approximation to the Poisson equation on an octree grid results in a non-symmetric linear system which is more computationally challenging to invert. The semi-Lagrangian characteristic tracing technique is used to advect the velocity, smoke density, and even the level set making implementation on an octree straightforward. In the case of smoke, we have multiple refinement criteria including object boundaries, optical depth, and vorticity concentration. In the case of water, we refine near the interface as determined by the zero isocontour of the level set function.

Videos:

Geometry clipmaps: Terrain rendering using nested regular grids (PDF)

Abstract: Rendering throughput has reached a level that enables a novel approach to level-of-detail (LOD) control in terrain rendering. We introduce the geometry clipmap, which caches the terrain in a set of nested regular grids centered about the viewer. The grids are stored as vertex buffers in fast video memory, and are incrementally refilled as the viewpoint moves. This simple framework provides visual continuity, uniform frame rate, complexity throttling, and graceful degradation. Moreover it allows two new exciting real-time functionalities: decompression and synthesis. Our main dataset is a 40GB height map of the United States. A compressed image pyramid reduces the size by a remarkable factor of 100, so that it fits entirely in memory. This compressed data also contributes normal maps for shading. As the viewer approaches the surface, we synthesize grid levels finer than the stored terrain using fractal noise displacement. Decompression, synthesis, and normal-map computations are incremental, thereby allowing interactive flight at 60 frames/sec.

Videos:

A Fast and Accurate Semi-Lagrangian Particle Level Set Method (PDF)

Abstract: In this paper, we present a fast semi-Lagrangian based particle level set method for the accurate capturing of interfaces. This method retains the robust topological properties of the level set method without the adverse effects of numerical dissipation. Both the level set method and the particle level set method typically use high order accurate numerical discretizations in time and space, e.g. TVD Runge-Kutta and HJ-WENO schemes. We demonstrate that these computationally expensive schemes are not required, rather fast, low order accurate numerical schemes suffice. That is, the addition of particles to the level set method not only removes the difficulties associated with numerical dissipation, but also alleviates the need for computationally expensive high order accurate schemes. We use a fast, first order accurate semi-Lagrangian advection scheme coupled with a first order accurate fast marching method to evolve the level set function. To accurately track the underlying flow characteristics, the particles are evolved with a second order accurate method. Since we avoid complex high order accurate numerical methods, extending the algorthim to arbitrary data strutures becomes more feasible, and we show preliminary results obtained with an octree-based adaptive mesh that captures the small scale features of the interface.

Videos:

Smooth Geometry Images (PDF)

Abstract: Previous parametric representations of smooth genus-zero surfaces require a collection of abutting patches (e.g. splines, NURBS, recursively subdivided polygons). We introduce a simple construction for these surfaces using a single uniform bi-cubic B-spline. Due to its tensor-product structure, the spline control points are conveniently stored as a geometry image with simple boundary symmetries. The bicubic surface is evaluated using subdivision, and the regular structure of the geometry image makes this computation ideally suited for graphics hardware. Specifically, we let the fragment shader pipeline perform subdivision by applying a sequence of masks (splitting, averaging, limit, and tangent) uniformly to the geometry image. We then extend this scheme to provide smooth level-of-detail transitions from a subsampled base octahedron all the way to a finely subdivided, smooth model. Finally, we show how the framework easily supports scalar displacement mapping.

Conveying Shape and Features with Image-Based Relighting (PDF)

Abstract: Hand-crafted illustrations are often more effective than photographs for conveying the shape and important features of an object, but they require expertise and time to produce. We describe an image compositing system and user interface that allow an artist to quickly and easily create technical illustrations from a set of photographs of an object taken from the same point of view under variable lighting conditions. Our system uses a novel compositing process in which images are combined using spatially-varying light mattes, enabling the final lighting in each area of the composite to be manipulated independently. We describe an interface that provides for the painting of local lighting effects (e.g. shadows, highlights, and tangential lighting to reveal texture) directly onto the composite. We survey some of the techniques used in illustration and lighting design to convey the shape and features of objects and describe how our system can be used to apply these techniques.

Dual Contouring of Hermite Data (PDF)

Abstract: This paper describes a new method for contouring a signed grid whose edges are tagged by Hermite data (i.e; exact intersection points and normals). This method avoids the need to explicitly identify and process "features" as required in previous Hermite contouring methods. We extend this contouring method to the case of multi-signed functions and demonstrate how to model textured contours using multi-signed functions. Using a new, numerically stable representation for quadratic error functions, we develop an octree-based method for simplifying these contours and their textured regions. We next extend our contouring method to these simplified octrees. This new method imposes no constraints on the octree (such as being a restricted octree) and requires no "crack patching". We conclude with a simple test for preserving the topology of both the contour and its textured regions during simplification.

Videos: