We present a novel way to efficiently compute Riemannian geodesic distance over a two- or three-dimensional domain. It is based on a previously presented method for computation of geodesic distances on surface meshes. Our method is adapted for rectangular grids, equipped with a variable anisotropic metric tensor. Processing and visualization of such tensor fields is common in certain applications, for instance structure tensor fields in image analysis and diffusion tensor fields in medical imaging. The included benchmark study shows that our method provides significantly better results in anisotropic regions in 2-D and 3-D and is faster than current stat-of-the-art solvers in 2-D grids. Additionally, our method is straightforward to code; the test implementation is less than 150 lines of C++ code. The paper is an extension of a previously presented conference paper and includes new sections on 3-D grids in particular.

This article presents a novel non-reflective boundary condition for the free surface incompressible Euler and Navier-Stokes equations. Boundaries of this type are very useful when, for example, simulating water flow around a ship moving over a wide ocean. Normally waves generated by the ship will reflect off of the boundaries of the simulation domain and as these reflected waves returns towards the ship they will cause undesired interference patterns.By employing a Perfectly Matched Layer (PML) approach we have derived a boundary condition that absorbs incoming waves and thus efficiently prevents these undesired wave reflections. To solve the resulting boundary equations we present a fast and stable algorithm based on the Stable Fluids approach. Through numerical experiments we then show that our boundaries are significantly more effective than simpler reflection preventing techniques. We also provide a thorough analysis of the parameters involved in our boundary formulation and show how they effect wave absorption efficiency.

We present a novel surface-tracking technique for free-surface fluid animations. Unlike the semi-implicit Particle Level Set method (PLS) our interface-tracking approach is purely implicit and hence avoids some of the well-known issues like surface noise and inflated memory footprints. Where PLS augments the interface with Lagrangian tracker-particles, we instead employ a higher resolution level set represented as a DT-Grid. The synchronization of our dual-resolution level sets is facilitated by a novel Spatially Adaptive Morphological (SAM) filter that attempts to preserve fine details while still avoiding spurious topology changes and boundary violations. We demonstrate that our approach can achieve comparative results to the PLS, but with a fraction of the memory footprint. We also show how our technique can be used to effectively enhance thin interface sheets at the cost of volume gain.

We have developed a novel approach to open-boundaries for fluid animations. More specifically we present a highly efficient energy absorbing boundary condition for the incompressible Navier-Stokes equations in the prescence of a free surface. Our work extends and adapts a Perfectly Matched Layer (PML) approach [Berenger 1994; Johnson 2007], recently developed for the Navier-Stokes equations, to free surfaces in the context fluid animations. We show how our PML boundary condition is able to effectively eliminate reflections generated by the presence of solid boundaries in the simulation domain, and that our method is far superior to simpler approaches for reducing wave reflection. Furthermore, we have adapted our theoretical PML model to work with the Stable-Fluids Eulerian Navier-Stokes solver commonly used in computer graphics. Finally, we show that the cost of deploying our method in terms of memory and additional computations is small, and for a given quality significantly less than other known methods.

We present techniques for warping and blending (or subtracting) geometric textures onto surfaces represented by high resolution level sets. The geometric texture itself can be represented either explicitly as a polygonal mesh or implicitly as a level set. Unlike previous approaches, we can produce topologically connected surfaces with smooth blending and low distortion. Specifically, we offer two different solutions to the problem of adding fine-scale geometric detail to surfaces. Both solutions assume a level set representation of the base surface which is easily achieved by means of a mesh-to-level-set scan conversion. To facilitate our mapping, we parameterize the embedding space of the base level set surface using fast particle advection. We can then warp explicit texture meshes onto this surface at nearly interactive speeds or blend level set representations of the texture to produce high-quality surfaces with smooth transitions.

This paper presents a technique for creating a smooth, closed surface from a set of 2D contours, which have been extracted from a 3D scan. The technique interprets the pixels that make up the contours as points in R3 and employs multi-level partition of unity (MPU) implicit models to create a surface that approximately fits to the 3D points. Since MPU implicit models additionally require surface normal information at each point, an algorithm that estimates normals from the contour data is also described. Contour data frequently contains noise from the scanning and delineation process. MPU implicit models provide a superior approach to the problem of contour-based surface reconstruction, especially in the presence of noise, because they are based on adaptive implicit functions that locally approximate the points within a controllable error bound. We demonstrate the effectiveness of our technique with a number of example datasets, providing images and error statistics generated from our results. © 2006 Elsevier Inc. All rights reserved.

One of the most common visualization tasks is the extraction of significant boundaries, often performed with iso- surfaces or level set segmentation. Isosurface extraction is simple and can be guided by geometric and topological analysis, yet frequently does not extract the desired boundary. Level set segmentation is better at boundary extrac- tion, but either leads to global segmentation without edges, [CV01], that scales unfavorably in 3D or requires an initial estimate of the boundary from which to locally solve segmentation with edges. We propose a hybrid system in which topological analysis is used for semi-automatic initialization of a level set segmentation, and geometric information bounded topologically is used to guide and accelerate an iterative segmentation algorithm that com- bines several state-of-the-art level set terms. We thus combine and improve both the flexible isosurface interface and level set segmentation without edges.

This article presents a generic framework for the representation and deformation of level set surfaces at extreme resolutions. The framework is composed of two modules that each utilize optimized and application specific algorithms: 1) A fast out-of-core data management scheme that allows for resolutions of the deforming geometry limited only by the available disk space as opposed to memory, and 2) compact and fast compression strategies that reduce both offline storage requirements and online memory footprints during simulation. Out-of-core and compression techniques have been applied to a wide range of computer graphics problems in recent years, but this article is the first to apply it in the context of level set and fluid simulations. Our framework is generic and flexible in the sense that the two modules can transparently be integrated, separately or in any combination, into existing level set and fluid simulation software based on recently proposed narrow band data structures like the DT-Grid of Nielsen and Museth [2006] and the H-RLE of Houston et al. [2006]. The framework can be applied to narrow band signed distances, fluid velocities, scalar fields, particle properties as well as standard graphics attributes like colors, texture coordinates, normals, displacements etc. In fact, our framework is applicable to a large body of computer graphics problems that involve sequential or random access to very large co-dimension one (level set) and zero (e.g. fluid) data sets. We demonstrate this with several applications, including fluid simulations interacting with large boundaries (? 15003), surface deformations (? 20483), the solution of partial differential equations on large surfaces (˜40963) and mesh-to-level set scan conversions of resolutions up to ? 350003 (7 billion voxels in the narrow band). Our out-of-core framework is shown to be several times faster than current state-of-the-art level set data structures relying on OS paging. In particular we show sustained throughput (grid points/sec) for gigabyte sized level sets as high as 65% of state-of-the-art throughput for in-core simulations. We also demonstrate that our compression techniques out-perform state-of-the-art compression algorithms for narrow bands. © 2007 ACM.