A Hybrid Approach to Multiple Fluid Simulation using Volume Fractions

This paper presents a hybrid approach to multiple fluid simulation that can handle miscible and immiscible fluids, simultaneously. We combine distance functions and volume fractions to capture not only the discontinuous interface between immiscible fluids but also the smooth transition between miscible fluids. Our approach consists of four steps: velocity field computation, volume fraction advection, miscible fluid diffusion, and visualization. By providing a combining scheme between volume fractions and level set functions, we are able to take advantages of both representation schemes of fluids. From the system point of view, our work is the first approach to Eulerian grid‐based multiple fluid simulation including both miscible and immiscible fluids. From the technical point of view, our approach addresses the issues arising from variable density and viscosity together with material diffusion. We show that the effectiveness of our approach to handle multiple miscible and immiscible fluids through experiments.     

A PCA Decomposition for Real‐time BRDF Editing and Relighting with Global Illumination

We propose a novel rendering method which supports interactive BRDF editing as well as relighting on a 3D scene. For interactive BRDF editing, we linearize an analytic BRDF model with basis BRDFs obtained from a principal component analysis. For each basis BRDF, the radiance transfer is precomputed and stored in vector form. In rendering time, illumination of a point is computed by multiplying the radiance transfer vectors of the basis BRDFs by the incoming radiance from gather samples and then linearly combining the results weighted by user‐controlled parameters. To improve the level of accuracy, a set of sub‐area samples associated with a gather sample refines the glossy reflection of the geometric details without increasing the precomputation time. We demonstrate this program with a number of examples to verify the real‐time performance of relighting and BRDF editing on 3D scenes with complex lighting and geometry.     

Fast Particle‐based Visual Simulation of Ice Melting

The visual simulation of natural phenomena has been widely studied. Although several methods have been proposed to simulate melting, the flows of meltwater drops on the surfaces of objects are not taken into account. In this paper, we propose a particle‐based method for the simulation of the melting and freezing of ice objects and the interactions between ice and fluids. To simulate the flow of meltwater on ice and the formation of water droplets, a simple interfacial tension is proposed, which can be easily incorporated into common particle‐based simulation methods such as Smoothed Particle Hydrodynamics. The computations of heat transfer, the phase transition between ice and water, the interactions between ice and fluids, and the separation of ice due to melting are further accelerated by implementing our method using CUDA. We demonstrate our simulation and rendering method for depicting melting ice at interactive frame‐rates.     

Dynamic Multi‐View Exploration of Shape Spaces

Statistical shape modeling is a widely used technique for the representation and analysis of the shapes and shape variations present in a population. A statistical shape model models the distribution in a high dimensional shape space, where each shape is represented by a single point. We present a design study on the intuitive exploration and visualization of shape spaces and shape models. Our approach focuses on the dual‐space nature of these spaces. The high‐dimensional shape space represents the population, whereas object space represents the shape of the 3D object associated with a point in shape space. A 3D object view provides local details for a single shape. The high dimensional points in shape space are visualized using a 2D scatter plot projection, the axes of which can be manipulated interactively. This results in a dynamic scatter plot, with the further extension that each point is visualized as a small version of the object shape that it represents. We further enhance the population‐object duality with a new type of view aimed at shape comparison. This new “shape evolution view” visualizes shape variability along a single trajectory in shape space, and serves as a link between the two spaces described above. Our three‐view exploration concept strongly emphasizes linked interaction between all spaces. Moving the cursor over the scatter plot or evolution views, shapes are dynamically interpolated and shown in the object view. Conversely, camera manipulation in the object view affects the object visualizations in the other views. We present a GPU‐accelerated implementation, and show the effectiveness of the three‐view approach using a number of real‐world cases. In these, we demonstrate how this multi‐view approach can be used to visually explore important aspects of a statistical shape model, including specificity, compactness and reconstruction error.     

Nonrigid Matching of Undersampled Shapes via Medial Diffusion

We introduce medial diffusion for the matching of undersampled shapes undergoing a nonrigid deformation. We construct a diffusion process with respect to the medial axis of a shape, and use the quantity of heat diffusion as a measure which is both tolerant of missing data and approximately invariant to nonrigid deformations. A notable aspect of our approach is that we do not define the diffusion on the shape's medial axis, or similar medial representation. Instead, we construct the diffusion process directly on the shape. This permits the diffusion process to better capture surface features, such as varying spherical and cylindrical parts, as well as combine with other surface‐based diffusion processes. We show how to use medial diffusion to detect intrinsic symmetries, and for computing correspondences between pairs of shapes, wherein shapes contain substantial missing data.     

Fast and Robust Normal Estimation for Point Clouds with Sharp Features

This paper presents a new method for estimating normals on unorganized point clouds that preserves sharp features. It is based on a robust version of the Randomized Hough Transform (RHT). We consider the filled Hough transform accumulator as an image of the discrete probability distribution of possible normals. The normals we estimate corresponds to the maximum of this distribution. We use a fixed‐size accumulator for speed, statistical exploration bounds for robustness, and randomized accumulators to prevent discretization effects. We also propose various sampling strategies to deal with anisotropy, as produced by laser scans due to differences of incidence. Our experiments show that our approach offers an ideal compromise between precision, speed, and robustness: it is at least as precise and noise‐resistant as state‐of‐the‐art methods that preserve sharp features, while being almost an order of magnitude faster. Besides, it can handle anisotropy with minor speed and precision losses.     

Estimation and Modeling of Actual Numerical Errors in Volume Rendering

In this paper we study the comprehensive effects on volume rendered images due to numerical errors caused by the use of finite precision for data representation and processing. To estimate actual error behavior we conduct a thorough study using a volume renderer implemented with arbitrary floating‐point precision. Based on the experimental data we then model the impact of floating‐point pipeline precision, sampling frequency and fixed‐point input data quantization on the fidelity of rendered images. We introduce three models, an average model, which does not adapt to different data nor varying transfer functions, as well as two adaptive models that take the intricacies of a new data set and transfer function into account by adapting themselves given a few different images rendered. We also test and validate our models based on new data that was not used during our model building.     

Hydraulic Erosion Using Smoothed Particle Hydrodynamics

This paper presents a new technique for modification of 3D terrains by hydraulic erosion. It efficiently couples fluid simulation using a Lagrangian approach, namely the Smoothed Particle Hydrodynamics (SPH) method, and a physically-based erosion model adopted from an Eulerian approach. The eroded sediment is associated with the SPH particles and is advected both implicitly, due to the particle motion, and explicitly, through an additional velocity field, which accounts for the sediment transfer between the particles. We propose a new donor-acceptor scheme for the explicit advection in SPH. Boundary particles associated to the terrain are used to mediate sediment exchange between the SPH particles and the terrain itself. Our results show that this particle-based method is efficient for the erosion of dense, large, and sparse fluid. Our implementation provides interactive results for scenes with up to 25,000 particles.     

Temporally Coherent Adaptive Sampling for Imperfect Shadow Maps

We propose a new adaptive algorithm for determining virtual point lights (VPL) in the scope of real‐time instant radiosity methods, which use a limited number of VPLs. The proposed method is based on Metropolis‐Hastings sampling and exhibits better temporal coherence of VPLs, which is particularly important for real‐time applications dealing with dynamic scenes. We evaluate the properties of the proposed method in the context of the algorithm based on imperfect shadow maps and compare it with the commonly used inverse transform method. The results indicate that the proposed technique can significantly reduce the temporal flickering artifacts even for scenes with complex materials and textures. Further, we propose a novel splatting scheme for imperfect shadow maps using hardware tessellation. This scheme significantly improves the rendering performance particularly for complex and deformable scenes. We thoroughly analyze the performance of the proposed techniques on test scenes with detailed materials, moving camera, and deforming geometry.     

As‐Killing‐As‐Possible Vector Fields for Planar Deformation

Cartoon animation, image warping, and several other tasks in two‐dimensional computer graphics reduce to the formulation of a reasonable model for planar deformation. A deformation is a map from a given shape to a new one, and its quality is determined by the type of distortion it introduces. In many applications, a desirable map is as isometric as possible. Finding such deformations, however, is a nonlinear problem, and most of the existing solutions approach it by minimizing a nonlinear energy. Such methods are not guaranteed to converge to a global optimum and often suffer from robustness issues. We propose a new approach based on approximate Killing vector fields (AKVFs), first introduced in shape processing. AKVFs generate near‐isometric deformations, which can be motivated as direction fields minimizing an “as‐rigid‐as‐possible” (ARAP) energy to first order. We first solve for an AKVF on the domain given user constraints via a linear optimization problem and then use this AKVF as the initial velocity field of the deformation. In this way, we transfer the inherent nonlinearity of the deformation problem to finding trajectories for each point of the domain having the given initial velocities. We show that a specific class of trajectories — the set of logarithmic spirals — is especially suited for this task both in practice and through its relationship to linear holomorphic vector fields. We demonstrate the effectiveness of our method for planar deformation by comparing it with existing state‐of‐the‐art deformation methods.     

Extraction Of Feature Lines On Surface Meshes Based On Discrete Morse Theory

We present an approach for extracting extremal feature lines of scalar indicators on surface meshes, based on discrete Morse Theory. By computing initial Morse‐Smale complexes of the scalar indicators of the mesh, we obtain a candidate set of extremal feature lines of the surface. A hierarchy of Morse‐Smale complexes is computed by prioritizing feature lines according to a novel criterion and applying a cancellation procedure that allows us to select the most significant lines. Given the scalar indicators on the vertices of the mesh, the presented feature line extraction scheme is interpolation free and needs no derivative estimates. The technique is insensitive to noise and depends only on one parameter: the feature significance. We use the technique to extract surface features yielding impressive, non photorealistic images.     

Stochastic Heat Kernel Estimation on Sampled Manifolds

The heat kernel is a fundamental geometric object associated to every Riemannian manifold, used across applications in computer vision, graphics, and machine learning. In this article, we propose a novel computational approach to estimating the heat kernel of a statistically sampled manifold (e.g. meshes or point clouds), using its representation as the transition density function of Brownian motion on the manifold. Our approach first constructs a set of local approximations to the manifold via moving least squares. We then simulate Brownian motion on the manifold by stochastic numerical integration of the associated Ito diffusion system. By accumulating a number of these trajectories, a kernel density estimation method can then be used to approximate the transition density function of the diffusion process, which is equivalent to the heat kernel. We analyse our algorithm on the 2‐sphere, as well as on shapes in 3D. Our approach is readily parallelizable and can handle manifold samples of large size as well as surfaces of high co‐dimension, since all the computations are local. We relate our method to the standard approaches in diffusion geometry and discuss directions for future work.     

Visualization of Particle‐based Data with Transparency and Ambient Occlusion

Particle‐based simulation techniques, like the discrete element method or molecular dynamics, are widely used in many research fields. In real‐time explorative visualization it is common to render the resulting data using opaque spherical glyphs with local lighting only. Due to massive overlaps, however, inner structures of the data are often occluded rendering visual analysis impossible. Furthermore, local lighting is not sufficient as several important features like complex shapes, holes, rifts or filaments cannot be perceived well. To address both problems we present a new technique that jointly supports transparency and ambient occlusion in a consistent illumination model. Our approach is based on the emission‐absorption model of volume rendering. We provide analytic solutions to the volume rendering integral for several density distributions within a spherical glyph. Compared to constant transparency our approach preserves the three‐dimensional impression of the glyphs much better. We approximate ambient illumination with a fast hierarchical voxel cone‐tracing approach, which builds on a new real‐time voxelization of the particle data. Our implementation achieves interactive frame rates for millions of static or dynamic particles without any preprocessing. We illustrate the merits of our method on real‐world data sets gaining several new insights.     

Enclosing Surfaces for Point Clusters Using 3D Discrete Voronoi Diagrams

Point clusters occur in both spatial and non-spatial data. In the former context they may represent segmented particle data, in the latter context they may represent clusters in scatterplots. In order to visualize such point clusters, enclosing surfaces lead to much better comprehension than pure point renderings.
We propose a flexible system for the generation of enclosing surfaces for 3D point clusters. We developed a GPU-based 3D discrete Voronoi diagram computation that supports all surface extractions. Our system provides three different types of enclosing surfaces. By generating a discrete distance field to the point cluster and extracting an isosurface from the field, an enclosing surface with any distance to the point cluster can be generated. As a second type of enclosing surfaces, a hull of the point cluster is extracted. The generation of the hull uses a projection of the discrete Voronoi diagram of the point cluster to an isosurface to generate a polygonal surface. Generated hulls of non-convex clusters are also non-convex. The third type of enclosing surfaces can be created by computing a distance field to the hull and extracting an isosurface from the distance field. This method exhibits reduced bumpiness and can extract surfaces arbitrarily close to the point cluster without losing connectedness.
We apply our methods to the visualization of multidimensional spatial and non-spatial data. Multidimensional clusters are extracted and projected into a 3D visual space, where the point clusters are visualized. The respective clusters can also be visualized in object space when dealing with multidimensional particle data.     

Wetting Effects in Hair Simulation

There is considerable recent progress in hair simulations, driven by the high demands in computer animated movies. However, capturing the complex interactions between hair and water is still relatively in its infancy. Such interactions are best modeled as those between water and an anisotropic permeable medium as water can flow into and out of the hair volume biased in hair fiber direction. Modeling the interaction is further challenged when the hair is allowed to move. In this paper, we introduce a simulation model that reproduces interactions between water and hair as a dynamic anisotropic permeable material. We utilize an Eulerian approach for capturing the microscopic porosity of hair and handle the wetting effects using a Cartesian bounding grid. A Lagrangian approach is used to simulate every single hair strand including interactions with each other, yielding fine‐detailed dynamic hair simulation. Our model and simulation generate many interesting effects of interactions between fine‐detailed dynamic hair and water, i.e., water absorption and diffusion, cohesion of wet hair strands, water flow within the hair volume, water dripping from the wet hair strands and morphological shape transformations of wet hair.     

Photon Beam Diffusion: A Hybrid Monte Carlo Method for Subsurface Scattering

We present photon beam diffusion, an efficient numerical method for accurately rendering translucent materials. Our approach interprets incident light as a continuous beam of photons inside the material. Numerically integrating diffusion from such extended sources has long been assumed computationally prohibitive, leading to the ubiquitous single‐depth dipole approximation and the recent analytic sum‐of‐Gaussians approach employed by Quantized Diffusion. In this paper, we show that numerical integration of the extended beam is not only feasible, but provides increased speed, flexibility, numerical stability, and ease of implementation, while retaining the benefits of previous approaches. We leverage the improved diffusion model, but propose an efficient and numerically stable Monte Carlo integration scheme that gives equivalent results using only 3–5 samples instead of 20–60 Gaussians as in previous work. Our method can account for finite and multi‐layer materials, and additionally supports directional incident effects at surfaces. We also propose a novel diffuse exact single‐scattering term which can be integrated in tandem with the multi‐scattering approximation. Our numerical approach furthermore allows us to easily correct inaccuracies of the diffusion model and even combine it with more general Monte Carlo rendering algorithms. We provide practical details necessary for efficient implementation, and demonstrate the versatility of our technique by incorporating it on top of several rendering algorithms in both research and production rendering systems.     

Visual Analysis and Semantic Exploration of Urban LIDAR Change Detection

Many previous approaches to detecting urban change from LIDAR point clouds interpolate the points into rasters, perform pixel‐based image processing to detect changes, and produce 2D images as output. We present a method of LIDAR change detection that maintains accuracy by only using the raw, irregularly spaced LIDAR points, and extracts relevant changes as individual 3D models. We then utilize these models, alongside existing GIS data, within an interactive application that allows the chronological exploration of the changes to an urban environment. A three‐tiered level‐of‐detail system maintains a scale‐appropriate, legible visual representation across the entire range of view scales, from individual changes such as buildings and trees, to groups of changes such as new residential developments, deforestation, and construction sites, and finally to larger regions such as neighborhoods and districts of a city that are emerging or undergoing revitalization. Tools are provided to assist the visual analysis by urban planners and historians through semantic categorization and filtering of the changes presented.     

An Operator Approach to Tangent Vector Field Processing

In this paper, we introduce a novel coordinate‐free method for manipulating and analyzing vector fields on discrete surfaces. Unlike the commonly used representations of a vector field as an assignment of vectors to the faces of the mesh, or as real values on edges, we argue that vector fields can also be naturally viewed as operators whose domain and range are functions defined on the mesh. Although this point of view is common in differential geometry it has so far not been adopted in geometry processing applications. We recall the theoretical properties of vector fields represented as operators, and show that composition of vector fields with other functional operators is natural in this setup. This leads to the characterization of vector field properties through commutativity with other operators such as the Laplace‐Beltrami and symmetry operators, as well as to a straight‐forward definition of differential properties such as the Lie derivative. Finally, we demonstrate a range of applications, such as Killing vector field design, symmetric vector field estimation and joint design on multiple surfaces.     

Approximate Bias Compensation for Rendering Scenes with Heterogeneous Participating Media

In this paper we present a novel method for high‐quality rendering of scenes with participating media. Our technique is based on instant radiosity, which is used to approximate indirect illumination between surfaces by gathering light from a set of virtual point lights (VPLs). It has been shown that this principle can be applied to participating media as well, so that the combined single scattering contribution of VPLs within the medium yields full multiple scattering. As in the surface case, VPL methods for participating media are prone to singularities, which appear as bright “splotches” in the image. These artifacts are usually countered by clamping the VPLs' contribution, but this leads to energy loss within the short‐distance light transport. Bias compensation recovers the missing energy, but previous approaches are prohibitively costly. We investigate VPL‐based methods for rendering scenes with participating media, and propose a novel and efficient approximate bias compensation technique. We evaluate our technique using various test scenes, showing it to be visually indistinguishable from ground truth.     

A Biophysically‐Based Model of the Optical Properties of Skin Aging

This paper presents a time‐varying, multi‐layered biophysically‐based model of the optical properties of human skin, suitable for simulating appearance changes due to aging. We have identified the key aspects that cause such changes, both in terms of the structure of skin and its chromophore concentrations, and rely on the extensive medical and optical tissue literature for accurate data. Our model can be expressed in terms of biophysical parameters, optical parameters commonly used in graphics and rendering (such as spectral absorption and scattering coefficients), or more intuitively with higher‐level parameters such as age, gender, skin care or skin type. It can be used with any rendering algorithm that uses diffusion profiles, and it allows to automatically simulate different types of skin at different stages of aging, avoiding the need for artistic input or costly capture processes. While the presented skin model is inspired on tissue optics studies, we also provided a simplified version valid for non‐diagnostic applications.