Abstract The representation of geometric models by trimmed NURBS surfaces has become a standard in the CAD industry. In CAD applications, the rendering of surfaces is usually solved by tessellation followed up by z‐buffer rendering. Ray tracing of NURBS surfaces has not been widely used in industry due to its computational complexity that hinders achieving real‐time performance in practice. We propose novel methods achieving faster point location search needed by trimming in the context of ray tracing trimmed NURBS surfaces. The proposed 2D data structure based on kd‐trees allows for faster ray tracing while it requires less memory for its representation and less preprocessing time than previously published methods. Further, we show the current state of the art for ray tracing trimmed NURBS surfaces on a GPU. With careful design and implementation, the number of rays cast on a GPU may reach real‐time performance in the order of tens to hundreds of million rays per second for moderately to large complex scenes containing hundreds of thousands of NURBS surfaces and trimming curves.

Abstract We present an improved way of acquiring spatially varying surface reflectance represented by a bidirectional texture function (BTF). Planar BTF samples are measured as images at several inclination angles which puts constraints on the minimum depth of field of cameras used in the measurement instrument. For standard perspective imaging, we show that the size of a sample measured and the achievable spatial resolution are strongly interdependent and limited by diffraction at the lens' aperture. We provide a formula for this relationship. We overcome the issue of the required depth of field by using Scheimpflug imaging further enhanced by an anamorphic attachment. The proposed optics doubles the spatial resolution of images compared to standard perspective imaging optics. We built an instrument prototype with the proposed optics that is portable and allows for measurement on site. We show rendered images using the visual appearance measured by the instrument prototype.

Surface reflectance of real-world materials is now widely represented by the bidirectional reflectance distribution function (BRDF) and also by spatially varying representations such as SVBRDF and the bidirectional texture function (BTF). The raw surface reflectance measurements are typically compressed or fitted by analytical models, that always introduce a certain loss of accuracy. For its evaluation we need a distance function between a reference surface reflectance and its approximate version. Although some of the past techniques tried to reflect the perceptual sensitivity of human vision, they have neither optimized illumination and viewing conditions nor surface shape. In this paper, we suggest a new image-based methodology for comparing different anisotropic BRDFs. We use optimization techniques to generate a novel surface which has extensive coverage of incoming and outgoing light directions, while preserving its features and frequencies that are important for material appearance judgments. A single rendered image of such a surface along with simultaneously optimized lighting and viewing directions leads to the computation of a meaningful BRDF difference, by means of standard image difference predictors. A psychophysical experiments revealed that our surface provides richer information on material properties than the standard surfaces often used in computer graphics, e.g., sphere or blob.

Abstract We reexamine in this paper the variance for the Multiple Importance Sampling (MIS) estimator for multi‐sample and one‐sample model. As a result of our analysis we can obtain the optimal estimator for the multi‐sample model for the case where the weights do not depend on the count of samples. We extend the analysis to include the cost of sampling. With these results in hand we find a better estimator than balance heuristic with equal count of samples. Further, we show that the variance for the one‐sample model is larger or equal than for the multi‐sample model, and that there are only two cases where the variance is the same. Finally, we study on four examples the difference of variances for equal count as used by Veach, our new estimator, and a recently introduced heuristic.

Abstract We present a performance comparison of bounding volume hierarchies and kd‐trees for ray tracing on many‐core architectures (GPUs). The comparison is focused on rendering times and traversal characteristics on the GPU using data structures that were optimized for very high performance of tracing rays. To achieve low rendering times, we extensively examine the constants used in termination criteria for the two data structures. We show that for a contemporary GPU architecture (NVIDIA Kepler) bounding volume hierarchies have higher ray tracing performance than kd‐trees for simple and moderately complex scenes. On the other hand, kd‐trees have higher performance for complex scenes, in particular for those with high depth complexity. Finally, we analyse the causes of the performance discrepancies using the profiling characteristics of the ray tracing kernels.

We present the first parallel on-demand spatial hierarchy construction algorithm targeting ray tracing on many-core processors such as GPUs. The method performs simultaneous ray traversal and spatial hierarchy construction focused on the parts of the data structure being traversed. The method is based on a versatile framework built around a task pool and runs entirely on the GPU. We show that the on-demand construction can improve rendering times compared to full hierarchy construction. We evaluate our method on both object (BVH) and space (kd-tree) subdivision data structures and compare them mutually. The on-demand method is particularly beneficial for rendering large scenes with high occlusion. We also present SAH kd-tree builder that outperforms previous state-of-the-art builders running on the GPU.

Abstract We present a novel interaction device tracked in 6 degrees of freedom by two commodity cameras. The inexpensive Light Chisel is statically illuminated with two LEDs, and uses no additional sensor (e.g. inertial or magnetic) or means of communication or synchronization. Its form factor is well suited for a screwdriver or chisel grip, allowing the Light Chisel to be rolled between the fingers. The position and orientation of the tool is tracked absolutely, making the Light Chisel suited for complex interaction, e.g. geometric modeling in augmented reality. The Light Chisel is physically small, limiting the physical and optical collisions with the real world. The orientation of the tool is tracked in a wide range of angles: pitch and yaw±90°, roll±180°. We evaluated our system against the OptiTrack optical tracking system. Our system achieved mean differences from OptiTrack reference of2.07 mmin position,1.06°in yaw and pitch, and5.26°in roll using a pair of VGA cameras. We demonstrate usefulness of our Light Chisel in four applications: character animation, modeling by swirls, volumetric modeling, and docking of CAD models.

Abstract We compare five existing dynamic memory allocators optimized for GPUs and show their strengths and weaknesses. In the measurements, we use three generic evaluation tests proposed in the past and we add one with a real workload, where dynamic memory allocation is used in building the k ‐d tree data structure. Following the performance analysis we propose a new dynamic memory allocator and its variants that address the limitations of the existing dynamic memory allocators. The new dynamic memory allocator uses few resources and is targeted towards large and variably sized memory allocations on massively parallel hardware architectures.

In this paper we introduce unique publicly available dense an isotropic BRDF data measurements. We use this dense data as a reference for performance evaluation of the proposed BRDF sparse angular sampling and interpolation approach. The method is based on sampling of BRDF subspaces at fixed elevations by means of several adaptively-represented, uniformly distributed, perpendicular slices. Although this proposed method requires only a sparse sampling of material, the interpolation provides a very accurate reconstruction, visually and computationally comparable to densely measured reference. Due to the simple slices measurement and method's robustness it allows for a highly accurate acquisition of BRDFs. This in comparison with standard uniform angular sampling, is considerably faster yet uses far less samples.

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

Abstract We present an algorithm for fast optimization of bounding volume hierarchies (BVH) for efficient ray tracing. We perform selective updates of the hierarchy driven by the cost model derived from the surface area heuristic. In each step, the algorithm updates a fraction of the hierarchy nodes to minimize the overall hierarchy cost. The updates are realized by simple operations on the tree nodes: removal, search and insertion. Our method can quickly reduce the cost of the hierarchy constructed by the traditional techniques, such as the surface area heuristic. We evaluate the properties of the proposed method on fourteen test scenes of different complexity including individual objects and architectural scenes. The results show that our method can improve a BVH initially constructed with the surface area heuristic by up to 27% and a BVH constructed with the spatial median split by up to 88%.

Abstract We present a novel method for massively parallel hierarchical scene processing on the GPU, which is based on sequential decomposition of the given hierarchical algorithm into small functional blocks. The computation is fully managed by the GPU using a specialized task pool which facilitates synchronization and communication of processing units. We present two applications of the proposed approach: construction of the bounding volume hierarchies and collision detection based on divide‐and‐conquer ray tracing. The results indicate that using our approach we achieve high utilization of the GPU even for complex hierarchical problems which pose a challenge for massive parallelization. The results indicate that using our approach we achieve high utilization of the GPU even for complex hierarchical problems which pose a challenge for massive parallelization.

Abstract In this paper we review the traversal algorithms for kd‐trees for ray tracing. Ordinary traversal algorithms such as sequential, recursive, and those with neighbour‐links have different limitations, which led to several new developments within the last decade. We describe algorithms exploiting ray coherence and algorithms designed with specific hardware architecture limitations such as memory latency and consumption in mind. We also discuss the robustness of traversal algorithms as one issue that has been neglected in previous research.

Abstract The Bidirectional Texture Function (BTF) is becoming widely used for accurate representation of real‐world material appearance. In this paper a novel BTF compression model is proposed. The model resamples input BTF data into a parametrization, allowing decomposition of individual view and illumination dependent texels into a set of multi‐dimensional conditional probability density functions. These functions are compressed in turn using a novel multi‐level vector quantization algorithm. The result of this algorithm is a set of index and scale code‐books for individual dimensions. BTF reconstruction from the model is then based on fast chained indexing into the nested stored code‐books. In the proposed model, luminance and chromaticity are treated separately to achieve further compression. The proposed model achieves low distortion and compression ratios 1:233–1:2040, depending on BTF sample variability. These results compare well with several other BTF compression methods with predefined compression ratios, usually smaller than 1:200. We carried out a psychophysical experiment comparing our method with LPCA method. BTF synthesis from the model was implemented on a standard GPU, yielded interactive framerates. The proposed method allows the fast importance sampling required by eye‐path tracing algorithms in image synthesis.

In this paper we propose a global visibility algorithm which computes from-region visibility for all view cells simultaneously in a progressive manner. We cast rays to sample visibility interactions and use the information carried by a ray for all view cells it intersects. The main contribution of the paper is a set of adaptive sampling strategies based on ray mutations that exploit the spatial coherence of visibility. Our method achieves more than an order of magnitude speedup compared to per-view cell sampling. This provides a practical solution to visibility preprocessing and also enables a new type of interactive visibility analysis application, where it is possible to quickly inspect and modify a coarse global visibility solution that is constantly refined.

Abstract We present a novel framework for efficiently computing the indirect illumination in diffuse and moderately glossy scenes using density estimation techniques. Many existing global illumination approaches either quickly compute an overly approximate solution or perform an orders of magnitude slower computation to obtain high‐quality results for the indirect illumination. The proposed method improves photon density estimation and leads to significantly better visual quality in particular for complex geometry, while only slightly increasing the computation time. We perform direct splatting of photon rays, which allows us to use simpler search data structures. Since our density estimation is carried out in ray space rather than on surfaces, as in the commonly used photon mapping algorithm, the results are more robust against geometrically incurred sources of bias. This holds also in combination with final gathering where photon mapping often overestimates the illumination near concave geometric features. In addition, we show that our photon splatting technique can be extended to handle moderately glossy surfaces and can be combined with traditional irradiance caching for sparse sampling and filtering in image space.

We present an interactive system for fully dynamic scene lighting using captured high dynamic range (HDR) video environment maps. The key component of our system is an algorithm for efficient decomposition of HDR video environment map captured over hemisphere into a set of representative directional light sources, which can be used for the direct lighting computation with shadows using graphics hardware. The resulting lights exhibit good temporal coherence and their number can be adaptively changed to keep a constant framerate while good spatial distribution (stratification) properties are maintained. We can handle a large number of light sources with shadows using a novel technique which reduces the cost of BRDF-based shading and visibility computations. We demonstrate the use of our system in a mixed reality application in which real and synthetic objects are illuminated by consistent lighting at interactive framerates.

We present a new algorithm for computing indirect illumination based on density estimation similarly to photon mapping. We accelerate the search for final gathering by reorganizing the computation in the reverse order. We use two trees that organize spatially not only the position of photons but also the position of final gather rays. The achieved speedup is algorithmic, the performance improvement takes advantage of logarithmic complexity of searching in trees. The algorithm requires almost no user settings unlike many known acceleration techniques for photon mapping. The image quality is the same as for traditional photon mapping with final gathering, since the algorithm does not approximate or interpolate. Optionally, the algorithm can be combined with other techniques such as density control and importance sampling. The algorithm creates a coherent access pattern to the main memory. This further improves on performance and also allows us to use efficient external data structures to alleviate the increased memory requirements.

No abstract available.

Abstract We present a series of simple improvements that make use of temporal and spatial coherence in the scope of hierarchical visibility algorithms. Thehierarchy updatingavoids visibility tests of certain interior nodes of the hierarchy. Thevisibility propagationalgorithm reuses information about visibility of neighbouring spatial regions. Finally, theconservative hierarchy updatingavoids visibility tests of the hierarchy nodes that are expected to remain visible. We evaluate the presented methods in the context of hierarchical visibility culling usingocclusion trees. Copyright © 2002 John Wiley & Sons, Ltd.

We describe two new techniques of ray shooting acceleration that exploit the traversal coherence of a spatial hierarchy. The first technique determines a sequence of adjacent leaf‐cells of the hierarchy that is pierced by all rays contained within a certain convex shaft. This sequence is used to accelerate ray shooting for all remaining rays within the shaft. The second technique establishes a cut of the hierarchy that contains nodes where the hierarchy traversal can no longer be predetermined for all rays contained within a given shaft. This cut is used to initiate the traversal for all remaining rays contained in the shaft. The description of the methods is followed by results evaluated by their practical implementation.

In the scope of rendering complex models with high depth complexity, it is of great importance to design output-sensitive algorithms, i.e., algorithms with the time complexity proportional to the number of visible graphic primitives in the resulting image. In this paper an algorithm allowing efficient culling of the invisible portion of the rendered model is presented. Our approach uses a spatial hierarchy to represent the topology of the model. For a current viewpoint a set of polygonal occluders is determined that are used to build the occlusion tree. In the occlusion tree occlusion volumes of the selected occluders are merged. Visibility from the viewpoint is determined by processing the spatial hierarchy and classifying the visibility of its regions. In this process the occlusion tree is used to determine the viewpoint-to-region visibility efficiently. The algorithm is well-suited for complex models where large occluders are present.