Abstract This paper presents a realistic digital oil painting system, specifically targeted at the real‐time performance on highly resource‐constrained portable hardware such as tablets and iPads. To effectively use the limited computing power, we develop an efficient adaptation of the shallow water equations that models all the characteristic properties of oil paint. The pigments are stored in a multi‐layered structure to model the peculiar nature of pigment mixing in oil paint. The user experience ranges from thick shape‐retaining strokes to runny diluted paint that reacts naturally to the gravity set by tablet orientation. Finally, the paint is rendered in real time using a combination of carefully chosen efficient rendering techniques. The virtual lighting adapts to the tablet orientation, or alternatively, the front‐facing camera captures the lighting environment, which leads to a truly immersive user experience. Our proposed features are evaluated via a user study. In our experience, our system enables artists to quickly try out ideas and compositions anywhere when inspiration strikes, in a truly ubiquitous way. They do not need to carry expensive and messy oil paint supplies.

Rendering translucent materials with physically based Monte Carlo methods tends to be computationally expensive due to the long chains of volumetric scattering interactions. In the case of strongly forward scattering materials, the problem gets compounded since each scattering interaction becomes highly anisotropic and near-specular. Various well-known approaches try to avoid the resulting sampling problem through analytical approximations based on diffusion theory. Although these methods are computationally efficient, their assumption of diffusive, isotropic scattering can lead to considerable errors when rendering forward scattering materials, even in the optically dense limit. In this paper, we present an analytical subsurface scattering model, derived with the explicit assumption of strong forward scattering. Our model is not based on diffusion theory, but follows from a connection that we identified between the functional integral formulation of radiative transport and the partition function of a worm-like chain in polymer physics. Our resulting model does not need a separate Monte Carlo solution for unscattered or single-scattered contributions, nor does it require ad-hoc regularization procedures. It has a single singularity by design, corresponding to the initial unscattered propagation, which can be accounted for by the extensive analytical importance sampling scheme that we provide. Our model captures the full behaviour of forward scattering media, ranging from unscattered straight-line propagation to the fully diffusive limit. Moreover, we derive a novel forward scattering BRDF as limiting case of our subsurface scattering model, which can be used in a level of detail hierarchy. We show how our model can be integrated in existing Monte Carlo rendering algorithms, and make comparisons to previous approaches.

Computing direct illumination efficiently is still a problem of major significance in computer graphics. The evaluation involves an integral over the surface areas of the light sources in the scene. Because this integral typically features many discontinuities, introduced by the visibility term and complex material functions, Monte Carlo integration is one of the only general techniques that can be used to compute the integral. In this paper, we propose to evaluate the direct illumination using line samples instead of point samples. A direct consequence of line sampling is that the two-dimensional integral over the area of the light source is reduced to a one-dimensional integral. We exploit this dimensional reduction by relying on the property that commonly used sampling patterns, such as stratified sampling and low-discrepancy sequences, converge faster when the dimension of the integration domain is reduced. We show that, while line sampling is generally more computationally intensive than point sampling, the variance of a line sample is smaller than that of a point sample, resulting in a higher order of convergence.

Abstract Voxel‐based rendering has recently received significant attention due to its potential in the context of efficiently rendering massively large and highly detailed scenes. Unfortunately, few scenes are available in the form of sparse voxel octrees. In this paper, we present an out‐of‐core algorithm for constructing a sparse voxel octree from a triangle mesh. Our algorithm allows the input triangle mesh, the output sparse voxel octree and, most importantly, the intermediate high‐resolution 3D voxel grid, to be larger than available memory. We demonstrate that our out‐of‐core algorithm can construct sparse voxel octrees from triangle meshes using only a fraction of the memory required by an in‐core algorithm in roughly the same time, and that our out‐of‐core algorithm can also handle extremely large triangle meshes.

Abstract Evaluating the visibility between two points is a fundamental problem for ray‐tracing and path‐tracing algorithms. Ideally, visibility computations are organized such that a minimum number of geometric primitives need to be checked for each ray. Replacing complex geometric shapes by a simpler set of primitives is one strategy to control the amount of intersection calculations. However, approximating the original geometry introduces inaccuracies in e.g. shadow regions when shadow rays are intersected with the approximate geometry. This paper presents a theoretical framework for probabilistic visibility evaluation. When intersecting a shadow ray with the scene, we randomly select the original geometry, the approximated geometry, or one of several correction terms, to be tested. Not all shadow rays will therefore intersect the original geometry, but our method is able to produce unbiased images that converge to the correct solution. Although probabilistic visibility evaluation is an experimental idea, we show several example scenes that highlight the potential for future improvements.

Abstract The efficient evaluation of visibility in a three‐dimensional scene is a longstanding problem in computer graphics. Visibility evaluations come in many different forms: figuring out what object is visible in a pixel; determining whether a point is visible to a light source; or evaluating the mutual visibility between 2 surface points. This paper provides a new, experimental view on visibility, based on a probabilistic evaluation of the visibility function. Instead of checking the visibility against all possible intervening geometry the visibility between 2 points is now evaluated by testing only a random subset of objects. The result is not a Boolean value that is either 0 or 1, but a numerical value that can even be negative. Because we use the visibility evaluation as part of the integrand in illumination computations, the probabilistic evaluation of visibility becomes part of the Monte Carlo procedure of estimating the illumination integral, and results in an unbiased computation of illumination values in the scene. Moreover, the number of intersections tests for any given ray is decreased, since only a random selection of geometric primitives is tested. Although probabilistic visibility is an experimental and new idea, we present a practical algorithm for direct illumination that uses the probabilistic nature of visibility evaluations.

Abstract Recent work in interactive global illumination addresses diffuse and moderately glossy indirect lighting effects, but high‐frequency effects such as multi‐bounce reflections on highly glossy surfaces are often ignored. Accurately simulating such effects is important to convey the realistic appearance of materials such as chrome and shiny metal. In this paper, we present an efficient method for visualizing multi‐bounce glossy reflections at interactive rates under environment lighting. Our main contribution is a pre‐computation–based method which efficiently gathers subsequent highly glossy reflection passes modelled with a non‐linear transfer function representation based on the von Mises–Fisher distribution. We show that our gathering method is superior to scattered sampling. To exploit the sparsity of the pre‐computed data, we apply perfect spatial hashing. As a result, we are able to visualize multi‐bounce glossy reflections at interactive rates at a low pre‐computation cost.

We have recently proposed a new procedural noise function, Gabor noise, which offers a combination of properties not found in the existing noise functions. In this paper, we present three significant improvements to Gabor noise: 1) an isotropic kernel for Gabor noise, which speeds up isotropic Gabor noise with a factor of roughly two, 2) an error analysis of Gabor noise, which relates the kernel truncation radius to the relative error of the noise, and 3) spatially varying Gabor noise, which enables spatial variation of all noise parameters. These improvements make Gabor noise an even more attractive alternative for the existing noise functions.

Abstract This paper proposes a method for efficiently rendering indirect highlights. Indirect highlights are caused by the primary light source reflecting off two or more glossy surfaces. Accurately simulating such highlights is important to convey the realistic appearance of materials such as chrome and shiny metal. Our method models the glossy BRDF at a surface point as a directional distribution, using a spherical von Mises‐Fisher (vMF) distribution. As our main contribution, we merge multiple vMFs into a combined multimodal distribution. This effectively creates a filtered radiance response function, allowing us to efficiently estimate indirect highlights. We demonstrate our method in a near‐interactive application for rendering scenes with highly glossy objects. Our results produce realistic reflections under both local and environment lighting.

Abstract Fluid animations in computer graphics show interactions with various kinds of objects. However, fluid flowing through a granular material such as sand is still not possible within current frameworks. In this paper, we present the simulation of fine granular materials interacting with fluids. We propose a unified Smoothed Particle Hydrodynamics framework for the simulation of both fluid and granular material. The granular volume is simulated as a continuous material sampled by particles. By incorporating previous work on porous flow in this simulation framework we are able to fully couple fluid and sand. Fluid can now percolate between sand grains and influence the physical properties of the sand volume. Our method demonstrates various new effects such as dry soil transforming into mud pools by rain or rigid sand structures being eroded by waves.

Noise is an essential tool for texturing and modeling. Designing interesting textures with noise calls for accurate spectral control, since noise is best described in terms of spectral content. Texturing requires that noise can be easily mapped to a surface, while high-quality rendering requires anisotropic filtering. A noise function that is procedural and fast to evaluate offers several additional advantages. Unfortunately, no existing noise combines all of these properties. In this paper we introduce a noise based on sparse convolution and the Gabor kernel that enables all of these properties. Our noise offers accurate spectral control with intuitive parameters such as orientation, principal frequency and bandwidth. Our noise supports two-dimensional and solid noise, but we also introduce setup-free surface noise. This is a method for mapping noise onto a surface, complementary to solid noise, that maintains the appearance of the noise pattern along the object and does not require a texture parameterization. Our approach requires only a few bytes of storage, does not use discretely sampled data, and is nonperiodic. It supports anisotropy and anisotropic filtering. We demonstrate our noise using an interactive tool for noise design.

Abstract Poisson disk distributions have many applications in the field of computer graphics. Besides sampling, Poisson disk distributions are used in object distribution, non‐photorealistic rendering and procedural texturing. Over the years, a large number of methods for generating Poisson disk distributions have been proposed, making it difficult to choose the right method for a given application. In this paper, we present a detailed comparison of most techniques for generating Poisson disk distributions. The methods we study include dart throwing, relaxation dart throwing, Lloyd's relaxation, Shade's Poisson disk tiles, tiled blue noise samples, fast hierarchical importance sampling with blue noise properties, edge‐based Poisson disk tiles, template Poisson disk tiles, corner‐based Poisson disk tiles and recursive Wang tiles for real‐time blue noise. Analysing all of these methods within a single framework is one of the major contributions of this work .

Abstract The focus of research in acceleration structures for ray tracing recently shifted from render time to time to image, the sum of build time and render time, and also the memory footprint of acceleration structures now receives more attention. In this paper we revisit the grid acceleration structure in this setting. We present two efficient methods for representing and building a grid. The compact grid method consists of a static data structure for representing a grid with minimal memory requirements, more specifically exactly one index per grid cell and exactly one index per object reference, and an algorithm for building that data structure in linear time. The hashed grid method reduces memory requirements even further, by using perfect hashing based on row displacement compression. We show that these methods are more efficient in both time and space than traditional methods based on linked lists and dynamic arrays. We also present a more robust grid traversal algorithm. We show that, for applications where time to image or memory usage is important, such as interactive ray tracing and rendering large models, the grid acceleration structure is an attractive alternative.

Abstract In this paper we introduce the constrained tetrahedralization as a new acceleration structure for ray tracing. A constrained tetrahedralization of a scene is a tetrahedralization that respects the faces of the scene geometry. The closest intersection of a ray with a scene is found by traversing this tetrahedralization along the ray, one tetrahedron at a time. We show that constrained tetrahedralizations are a viable alternative to current acceleration structures, and that they have a number of unique properties that set them apart from other acceleration structures: constrained tetrahedralizations are not hierarchical yet adaptive; the complexity of traversing them is a function of local geometric complexity rather than global geometric complexity; constrained tetrahedralizations support deforming geometry without any effort; and they have the potential to unify several data structures currently used in global illumination.

This paper presents the simulation of a fluid flowing through a porous deformable material. We introduce the physical principles governing porous flow, expressed by the Law of Darcy, into the Smoothed Particle Hydrodynamics (SPH) framework for simulating fluids and deformable objects. Contrary to previous SPH approaches, we simulate porous flow at a macroscopic scale, making abstraction of individual pores or cavities inside the material. Thus, the number of computational elements is kept low, while at the same time realistic simulations can be achieved. Our algorithm models the changing behavior of the wet material as well as the full two-way coupling between the fluid and the porous material. This enables various new effects, such as the simulation of sponge-like elastic bodies and water-absorbing sticky cloth.

Abstract In this paper we present an elegant pixel‐based texture synthesis technique that is able to generate visually pleasing results from source textures of both stochastic and structured nature. Inspired by the observation that the most common artifacts that occur when synthesizing textures are high‐frequency discontinuities, our technique tries to avoid these artifacts by forcing at least one of the direct neighboring pixels in each causal neighborhood to match within a predetermined threshold. This does not only avoid deterioration of the visual quality, but also results in faster synthesis timings. We demonstrate our technique on a variety of stochastic and structured textures.

Visual observation is our principal source of information in determining the nature of objects, including shape, material or roughness. The physiological and cognitive processes that resolve visual input into an estimate of the material of an object are influenced by the illumination and the shape of the object. This affects our ability to select materials by observing them on a point-lit sphere, as is common in current 3D modeling applications. In this paper we present an exploratory psychophysical experiment to study various influences on material discrimination in a realistic setting. The resulting data set is analyzed using a wide range of statistical techniques. Analysis of variance is used to estimate the magnitude of the influence of geometry, and fitted psychometric functions produce significantly diverse material discrimination thresholds across different shapes and materials. Suggested improvements to traditional material pickers include direct visualization on the target object, environment illumination, and the use of discrimination thresholds as a step size for parameter adjustments.

In this article we revisit the concept of Wang tiles and introduce corner tiles, square tiles with colored corners. During past years, Wang tiles have become a valuable tool in computer graphics. Important applications of Wang tiles include texture synthesis, tile-based texture mapping, and generating Poisson disk distributions. Through their colored edges, Wang tiles enforce continuity with their direct neighbors. However, Wang tiles do not directly constrain their diagonal neighbors. This leads to continuity problems near tile corners, a problem commonly known as the corner problem. Corner tiles, on the other hand, do impose restrictions on their diagonal neighbors, and thus are not subject to the corner problem. In this article we show that previous applications of Wang tiles can also be done using corner tiles, but that corner tiles have distinct advantages for each of these applications. Compared to Wang tiles, corner tiles are easier to tile, textures synthesized with corner tiles contain more samples from the original texture, corner tiles reduce the required texture memory by a factor of two for tile-based texture mapping, and Poisson disk distributions generated with corner tiles have better spectral properties. Corner tiles result in cleaner, simpler, and more efficient applications.

Many translucent materials exhibit heterogeneous subsurface scattering, which arises from complex internal structures. The acquisition and representation of these scattering functions is a complex problem that has been only partially addressed in previous techniques. Unlike homogeneous materials, the spatial component of heterogeneous subsurface scattering can vary arbitrarily over surface locations. Storing the spatial component without compression leads to impractically large datasets. In this paper, we address the problem of acquiring and compactly representing the spatial component of heterogeneous subsurface scattering functions. We propose a material model based on matrix factorization that can be mapped onto arbitrary geometry, and, due to its compact form, can be incorporated into most visualization systems with little overhead. We present results of several real-world datasets that are acquired using a projector and a digital camera.

In order to overcome several limitations of structured light 3D acquisition methods, the colors, intensities, and shapes of the projected patterns are adapted to the scene. Based on a crude estimate of the scene geometry and reflectance characteristics, the local intensity ranges in the projected patterns are adapted, in order to avoid over- and under-exposure in the image. This avoids the infamous specularity problems and generally increases accuracy. The estimated geometry also helps to limit the effect of aliasing caused by the sampling of foreshortened patterns. Furthermore, the approach also accounts for the adverse effects that small motions during scanning would normally have. Moreover, the approach yields a confidence measure at every pixel of the range image. Last but not least, the scanner consists of consumer products only, and therefore is cheap.

In this paper we present a method for geometry synthesis by example, inspired by techniques from texture synthesis. Given an example of input geometry, we synthesize new output geometry that is perceived similar to the input geometry, but at the same time differs in its local appearance. We assume the input geometry satisfies the constraints of a Markov Random Field model, and represent the input geometry by a hierarchical distance field. This allows us to perform fast matching between a target distance field that is partially synthesized, and the input distance field. Once the target distance field is completed, we copy the original corresponding geometry elements to the synthesized result. We show that automatically generating geometry by example can be achieved within reasonable computing times, and is able to produce convincing results.

We present efficient data structures and caching schemes to accelerate ray-surface intersections for deforming point-sampled surfaces.By exploiting spatial and temporal coherence of the deformation during the animation, we are able to improve rendering performance by a factor of two to three compared to existing techniques.Starting from a tight bounding sphere hierarchy for the undeformed object, we use a lazy updating scheme to adapt the hierarchy to the deformed surface in each animation step.In addition, we achieve a significant speedup for ray-surface intersections by caching per-ray intersection points.We also present a technique for rendering sharp edges and corners in point-sampled models by introducing a novel surface clipping algorithm.

In this article, we present a procedural object distribution function, a new texture basis function that distributes procedurally generated objects over a procedurally generated texture. The objects are distributed uniformly over the texture, and are guaranteed not to overlap. The scale, size, and orientation of the objects can be easily manipulated. The texture basis function is efficient to evaluate, and is suited for real-time applications. The new texturing primitive we present extends the range of textures that can be generated procedurally.The procedural object distribution function we propose is based on Poisson disk tiles and a direct stochastic tiling algorithm for Wang tiles. Poisson disk tiles are square tiles filled with a precomputed set of Poisson disk distributed points, inspired by Wang tiles. A single set of Poisson disk tiles enables the real-time generation of an infinite amount of Poisson disk distributions of arbitrary size. With the direct stochastic tiling algorithm, these Poisson disk distributions can be evaluated locally, at any position in the Euclidean plane.Poisson disk tiles and the direct stochastic tiling algorithm have many other applications in computer graphics. We briefly explore applications in object distribution, primitive distribution for illustration, and environment map sampling.

We present a new meshless animation framework for elastic and plastic materials that fracture. Central to our method is a highly dynamic surface and volume sampling method that supports arbitrary crack initiation, propagation, and termination, while avoiding many of the stability problems of traditional mesh-based techniques. We explicitly model advancing crack fronts and associated fracture surfaces embedded in the simulation volume. When cutting through the material, crack fronts directly affect the coupling between simulation nodes, requiring a dynamic adaptation of the nodal shape functions. We show how local visibility tests and dynamic caching lead to an efficient implementation of these effects based on point collocation. Complex fracture patterns of interacting and branching cracks are handled using a small set of topological operations for splitting, merging, and terminating crack fronts. This allows continuous propagation of cracks with highly detailed fracture surfaces, independent of the spatial resolution of the simulation nodes, and provides effective mechanisms for controlling fracture paths. We demonstrate our method for a wide range of materials, from stiff elastic to highly plastic objects that exhibit brittle and/or ductile fracture.

Abstract Image‐based techniques have become very popular over the past couple of years. Ranging from modeling to rendering and lighting, the use of images as direct input for graphics algorithms has become as important as processing polygons or other forms of data. This talk will focus on some of the challenges posed by Image‐based relighting. Starting from a set of photographs of an object under various illumination conditions, Image‐based relighting computes novel renderings of the objects. Also, the inverse problem stated as ``What is the required lighting configuration to reach a desired illumination on the object?'' will be discussed, as well as some thoughts on how results from computer vision can be used to accelerate the process.

This paper presents a new multispectral compact laboratory gonioreflectometer that can adequately sample bidirectional reflectance functions. It will be used for obtaining BRDF data of vegetation elements that can be applied in light transport simulations within virtual forests. In this way, future investigation and interpretation of radiation of forest canopies will be made possible.

Abstract We propose a new technique for efficiently rendering bidirectional texture functions (BTFs). A 6D BTF describesthe appearance of a material as a texture that depends on the lighting and viewing directions. As such, a BTFaccommodates self‐shadowing, interreflection, and masking effects of a complex material without needing anexplicit representation of the small scale geometry. Our method represents the BTF as a set of spatially varyingapparent BRDFs, that each encode the reflectance field of a single pixel in the BTF. Each apparent BRDF isdecomposed into a product of three or more two‐dimensional positive factors using a novel factorization technique,which we call chained matrix factorization (CMF). The proposed factorization technique is fully automatic andsuitable for both BRDFs and apparent BRDFs (which typically exhibit off‐specular peaks and non‐reciprocity).The main benefit of CMF is that it delivers factors well suited for the limited dynamic range of conventionaltexture maps. After factorization, an efficient representation of the BTF is obtained by clustering the factors intoa compact set of 2D textures. With this compact representation, BTFs can be rendered on recent consumer levelhardware with arbitrary viewing and lighting directions at interactive rates. Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three‐DimensionalGraphics and Realism

In this paper we present an algorithm to perform interactive boolean operations on free-form solids bounded by surfels. We introduce a fast inside-outside test to check whether surfels lie within the bounds of another surfel-bounded solid. This enables us to add, subtract and intersect complex solids at interactive rates. Our algorithm is fast both in displaying and constructing the new geometry resulting from the boolean operation.We present a resampling operator to solve problems resulting from sharp edges in the resulting solid. The operator resamples the surfels intersecting with the surface of the other solid. This enables us to represent the sharp edges with great detail.We believe our algorithm to be an ideal tool for interactive editing of free-form solids.

We present an image-based technique to relight real objects illuminated by a 4D incident light field, representing the illumination of an environment. By exploiting the richness in angular and spatial variation of the light field, objects can be relit with a high degree of realism.We record photographs of an object, illuminated from various positions and directions, using a projector mounted on a gantry as a moving light source. The resulting basis images are used to create a subset of the full reflectance field of the object. Using this reflectance field, we can create an image of the object, relit with any incident light field and observed from a flxed camera position.To maintain acceptable recording times and reduce the amount of data, we propose an efficient data acquisition method.Since the object can be relit with a 4D incident light field, illumination effects encoded in the light field, such as shafts of shadow or spot light effects, can be realized.

In this paper we present a technique for computing the direct lighting in a three-dimensional scene containing area light sources.Our method correctly handles partial visibility between luminaires and receivers, and is able to efficiently generate accurate soft shadows in scenes modeled with general bidirectional reflectance distribution functions.In most current algorithms, the form factor between a light source and receiver is computed using a stochastic ray casting approach which evaluates partial visibility.Such an approach often leads to noisy artifacts or aliasing problems.Generating significantly more rays is often the only solution to improving image quality.Our approach first stores visibility information in the image plane, using lazy evaluation of the visibility function.In a second phase, illumination values for each pixel are generated, using analytic or stochastic integration.Soft shadows and other shading effects are generated with high accuracy in less time than with existing shading algorithms.Coherence in specific blockerlight source relationships across the image plane is exploited to amortize the cost of analytic form factor calculations.By storing information in the image plane, our method is currently designed for generating a single image, and is thus view-dependent.