Library

Sampling distributions with blue noise characteristics are widely used in computer graphics. Although Poisson-disk distributions are known to have excellent blue noise char- acteristics, they are generally regarded as too computationally expensive to generate in real time. We present a new method for sampling by dart-throwing in O(N log N) time and introduce a novel and efficient variation for generating Poisson-disk distributions in O(N) time and space

Poisson Disk sampling patterns are of interest to the graphics community because their blue-noise properties are desirable in sampling patterns for rendering, illumination, and other computations. Until now, such patterns could only be generated by slow methods with poor convergence, or could only be approximated by jittering individual samples or tiling sets of samples.
We present a simple and efficient randomized algorithm for generating true Poisson Disk sampling patterns in a square domain, given a minimum radius R between samples. The algorithm runs in O(N log N) time for a pattern of N points. The method is based on the Voronoi diagram. Source code is available online.

The photon map method is an extension of ray tracing that makes it able to efficiently compute caustics and soft indirect illumination on surfaces and in participating media. This paper describes a method to further speed up the computation of soft indirect illumination (diffuse-diffuse light transport such as color bleeding) on surfaces. The speedup is based on the observation that the many look-ups in the global photon map during final gathering can be simplified by precomputing local irradiance values at the photon positions. Our tests indicate that the calculation of soft indirect illumination during rendering, which is the most time-consuming part, can be sped up by a factor of 5-7 in typical scenes at the expense of 1) a precomputation that takes about 2%-5% of the time saved during rendering and 2) a 28% increase of memory use.

We present a BRDF model that combines several advantages of the various empirical models currently in use. In particular, it has intuitive parameters, is anisotropic, conserves energy, is reciprocal, has an appropriate non-Lambertian diffuse term, and is well-suited for use in Monte Carlo renderers.

Previous methods in environment map sampling seldom consider a sequence of dynamic environment maps. The generated sampling patterns of the sequence may not maintain the temporal illumination consistency and result in choppy animation. In this paper, we propose a novel approach, spherical Q²-tree, to address this consistency problem. The local adaptive nature of the proposed method suppresses the abrupt change in the generated sampling patterns over time, hence ensures a smooth and consistent illumination. By partitioning the spherical surface with simple curvilinear equations, we construct a quadrilateral-based quadtree over the sphere. This Q²-tree allows us to adaptively sample the environment based on an importance metric and generates low-discrepancy sampling patterns. No time-consuming relaxation is required. The sampling patterns of a dynamic sequence are rapidly generated by making use of the summed area table and exploiting the coherence of consecutive frames. From our experiments, the rendering quality of our sampling pattern for a static environment map is comparable to previous methods. However, our method produces smooth and consistent animation for a sequence of dynamic environment maps, even the number of samples is kept constant over time.

We present an algorithm for ray tracing displacement maps that requires no ad- ditional storage over the base model. Displacement maps are rarely used in ray tracing due to the cost associated with storing and intersecting the displaced geometry. This is unfortunate because displacement maps allow the addition of large amounts of geometric complexity into models. Our method works for models composed of triangles with normals at the vertices. In addition, we discuss a special purpose displacement that creates a smooth surface that interpolates the triangle vertices and normals of a mesh. The combination allows relatively coarse models to be displacement mapped and ray traced effectively.

This paper presents optimizations for faster view frustum culling (VFC) for axis aligned bounding box (AABB) and oriented bounding box (OBB) hierarchies. We exploit frame-to-frame coherency by caching and by comparing against previous distances and rotation angles. By using an octant test, we potentially halve the number of plane tests needed, and we also evaluate masking, which is a well-known technique. The optimizations can be used for arbitrary bounding volumes, but we only present results for AABBs and OBBs. In particular, we provide solutions which is 2-11 times faster than other VFC algorithms for AABBs and OBBs, depending on the circumstances.

This paper introduces an efficient two-pass rendering technique for translucent materials. We decouple the computation of irradiance at the surface from the evaluation of scattering inside the material. This is done by splitting the evaluation into two passes, where the first pass consists of computing the irradiance at selected points on the surface. The second pass uses a rapid hierarchical integration technique to evaluate a diffusion approximation based on the irradiance samples. This approach is substantially faster than previous methods for rendering translucent materials, and it has the advan- tage that it integrates seamlessly with both scanline rendering and global illumination methods. We show several images and animations from our implementation that demonstrate that the approach is both fast and robust, making it suitable for rendering translucent materials in production

We introduce structured importance sampling, a new technique for efficiently rendering scenes illuminated by distant natural illumination given in an environment map. Our method handles occlusion, high-frequency lighting, and it is significantly faster than alternative methods based on Monte Carlo sampling. We achieve this speedup as a result of several ideas. First, we present a new metric for stratifying and sampling an environment map taking into account both the illumination intensity as well as the expected variance due to occlusion within the scene. We then present a novel hierarchical stratification algorithm that uses our metric to automatically stratify the environment map into regular strata. This approach enables a number of rendering optimizations, such as pre-integrating the illumination within each stratum to eliminate noise at the cost of adding bias, and sorting the strata to reduce the number of sample rays. We have render ed several scenes illuminated by natural lighting, and our results indicate that structured importance sampling is better than the best previous Monte Carlo techniques, requiring one to two orders of magnitude fewer samples for the same image quality.

Ray tracing is one of the most elegant techniques in computer graphics. Many phenomena that are difficult or impossible with other techniques are simple with ray tracing, including shadows, reflections, and refracted light. Ray directions, however, have been determined precisely, and this has limited the capabilities of ray tracing. By distributing the directions of the rays according to the analytic function they sample, ray tracing can incorporate fuzzy phenomena. This provides correct and easy solutions to some previously unsolved or partially solved problems, including motion blur, depth of field, penumbras, translucency, and fuzzy reflections. Motion blur and depth of field calculations can be integrated with the visible surface calculations, avoiding the problems found in previous methods.

Ray tracing, ray casting, and other forms of point sampling are important techniques in computer graphics, but their usefulness has been undermined by aliasing artifacts. In this paper it is shown that these artifacts are not an inherent part of point sampling, but a consequence of using regularly spaced samples. If the samples occur at appropriate nonuniformly spaced locations, frequencies above the Nyquist limit do not alias, but instead appear as noise of the correct average intensity. This noise is much less objectionable to our visual system than aliasing. In ray tracing, the rays can be stochastically distributed to perform a Monte Carlo evaluation of integrals in the rendering equation. This is called distributed ray tracing and can be used to simulate motion blur, depth of field, penumbrae, gloss, and translucency.

The quality of computer generated images of three-dimensional scenes depends on the shading technique used to paint the objects on the cathode-ray tube screen. The shading algorithm itself depends in part on the method for modeling the object, which also determines the hidden surface algorithm. The various methods of object modeling, shading, and hidden surface removal are thus strongly interconnected. Several shading techniques corresponding to different methods of object modeling and the related hidden surface algorithms are presented here. Human visual perception and the fundamental laws of optics are considered in the development of a shading rule that provides better quality and increased realism in generated images.

In the production of computer generated pictures of three dimensional objects, one stage of the calculation is the determination of the intensity of a given object once its visibility has been established. This is typically done by modelling the surface as a perfect diffuser, sometimes with a specular component added for the simulation of hilights. This paper presents a more accurate function for the generation of hilights which is based on some experimental measurements of how light reflects from real surfaces. It differs from previous models in that the intensity of the hilight changes with the direction of the light source. Also the position and shape of the hilights is somewhat different from that generated by simpler models. Finally, the hilight function generates different results when simulating metallic vs. nonmetallic surfaces. Many of the effects so generated are somewhat subtle and are apparent only during movie sequences. Some representative still frames from such movies are included.

The bidirectional reflectance distribution function (BRDF) formalism is commonly used in computer graphics to represent surface reflection properties. Although many BRDF models have been proposed, most do not possess at least some of the desirable practical properties. In this paper we present a simple and flexible model which satisfies many of these requirements. We show that the proposed model provides a good approximation for many real world materials, obeys basic physical restrictions, allows straightforward hardware implementation and provides for efficient sampling in a Monte-Carlo rendering system. A simple procedure to fit the model to BRDF measurement data is presented which suggests a simplified way of measuring surface reflection.

We introduce a tiled 3D MIP map representation of global illumination data. The representation is an adaptive, sparse octree with a "brick" at each octree node; each brick consists of 8^3 voxels with sparse irradiance values. The representation is designed to enable efficient caching. Combined with photon tracing and recent advances in distribution ray tracing of very complex scenes, the result is a method for efficient and flexible computation of global illumination in very complex scenes. The method can handle scenes with many more textures, geometry, and photons than could fit in memory. We show an example of a CG movie scene that has been retrofitted with global illumination shading using our method.