Adaptive undersampling for efficient mobile ray tracing

Aiming to develop an efficient ray tracer for a mobile platform, we present an adaptive undersampling method that enhances the rendering speed by effectively replacing expensive ray-tracing operations with cheap interpolation whenever possible. Our method explores both object- and image-space information gathered during ray tracing to detect possibly problematic pixels. Rays are fired only for these pixels. We also present a postcorrection algorithm that minimizes annoying artifacts inevitably caused by undersampling. Our implementation on a mobile GPU demonstrates that this method can speed up the rendering computation significantly, while retaining almost the same visual quality of the rendering.     

Spacetime ray tracing for animation

Techniques for the efficient ray tracing of animated scenes are presented. They are based on two central concepts: spacetime ray tracing, and a hybrid adaptive space subdivision/boundary volume technique for generating efficient, nonoverlapping hierarchies of bounding volumes. In spacetime ray tracing, static objects are rendered in 4-D space-time using 4-D analogs to 3-D techniques. The bounding volume hierarchy combines elements of adaptive space subdivision and bounding volume techniques. The quality of hierarchy and its nonoverlapping character make it an improvement over previous algorithms, because both attributes reduce the number of ray/object intersections that must be computed. These savings are amplified in animation because of the much higher cost of computing ray/object intersections for motion-blurred animation. It is shown that it is possible to ray trace large animations more quickly with space-time ray tracing using this hierarchy than with straightforward frame-by-frame rendering     

Pixel-selected ray tracing

An acceleration method based on an idea that T. Whitted (Commun. ACM, vol.23, no.6 pp.343-349, June 1980) presented on ray tracing is discussed. He proposed making antialiased images by hierarchical adaptive oversampling. The present authors use hierarchical adaptive undersampling to reduce the number of pixels whose intensity must be calculated by ray tracing. To implement pixel-selected ray tracing (PSRT), homogeneous regions in images must first be found. Generally, adaptive undersampling can result in some image-quality defects, because small objects and parts of thin or wedge-shaped objects may disappear when they are located between the initially sampled pixels. PSRT has an improved algorithm that uses pixels with the correct object information from among the sampled pixels to find pixels with erroneous color and correct them. Moreover, PRST uses ray-object intersection trees for precise classification of the homogeneity of regions and for fast intensity calculation in homogeneous regions. Experimental results are presented. They show that PSRT is two to nine times faster than standard ray tracing     

Discrete ray tracing

Discrete ray tracing, or 3-D raster ray tracing (RRT), which, unlike existing ray tracing methods that use geometric representation for the 3-D scene employs a 3-D discrete raster of voxels for representing the 3-D scene in the same way a 2-D raster of pixels represents a 2-D image, is discussed. Each voxel is a small quantum unit of volume that has numeric values associated with it representing some measurable properties or attributes of the real object or phenomenon at that voxel. It is shown that RRT operates in two phases: preprocessing voxel and discrete ray tracing. In the voxel phase, the geometric model is digitized using 3-D scan-conversion algorithms that convert the continuous representation of the model into a discrete representation within the 3-D raster. In the second phase, RRT employs a discrete variation of the conventional recursive ray tracer in which 3-D discrete rays are traversed through the 3-D raster to find the first surface voxel. Encountering a nontransparent voxel indicates a ray-surface hit. Results obtained by running the RRT software one one 20-MIPS (25-GHz) processor of a Silicon Graphics 4D/240GTX are presented in terms of CPU time     

Interactive ray tracing for volume visualization

Presents a brute-force ray-tracing system for interactive volume visualization. The system runs on a conventional (distributed) shared-memory multiprocessor machine. For each pixel, we trace a ray through a volume to compute the color for that pixel. Although this method has a high intrinsic computational cost, its simplicity and scalability make it ideal for large data sets on current high-end parallel systems. To gain efficiency, several optimizations are used, including a volume bricking scheme and a shallow data hierarchy. These optimizations are used in three separate visualization algorithms: isosurfacing of rectilinear data, isosurfacing of unstructured data, and maximum-intensity projection on rectilinear data. The system runs interactively (i.e. at several frames per second) on an SGI Reality Monster. The graphics capabilities of the Reality Monster are used only for display of the final color image     

Exploiting coherence for multiprocessor ray tracing

The scalability and cost effectiveness of general-purpose distributed-memory multiprocessor systems makes them particularly suitable for ray-tracing applications. However, the limited memory available to each processor in such a system requires schemes to distribute the model database among the processors. The authors identify a form of coherence in the ray-tracing algorithm that can be exploited to develop optimum schemes for data distribution in a multiprocessor system. This in turn gives rise to high processor efficiency for systems with limited distributed memory     

Efficient data management for incoherent ray tracing

To obtain good performance on the GPU hardware, it is necessary to design algorithms to manage data, access memory under GPU memory hierarchy, and schedule more efficient threads. In this paper, we propose an efficient data management and task management designed for GPU based ray tracing. Due to the dynamic and uncertainty in ray tracing, we design data-management layer and task-management layer combined with fuzzy spatial analysis, use the two-level ray sorting and a ray bucket structure to reorganize ray data, then a warp's threads can be scheduled to access coherent geometry and nodes data, reduce memory bandwidth, and dispatch the data locally. We schedule tasks in data-driven execution according to coherent data, propose an adaptive ray compaction to eliminate inactive threads, maintain task efficiency of threads in a warp, and design two heuristics to decrease the compaction cost. On the basis of it, we also introduce a memory-optimized dynamic traversal management to reduce incoherent memory access, and avoid frequent sorting computation and compaction operations. Our experiments demonstrate all of these work combined can achieve good performance.     

Heuristics for ray tracing using space subdivision

Ray tracing requires testing of many rays to determine intersections with objects. A way of reducing the computation is to organize objects into hierarchical data structures. We examine two heuristics for space subdivisions using bintrees, one based on the intuition that surface area is a good estimate of intersection probability, one based on the fact that the optimal splitting plane lies between the spatial median and the object median planes of a volume. Traversal algorithms using cross links between nodes are presented as generalizations of ropes in octrees. Simulations of the surface area heuristic and the cross link scheme are presented. These results generalize to other hierarchical data structures.     

An efficient hierarchicaltraversal algorithm for ray tracing

Ray tracing has been shown to be an excellent technique for rendering realistic images. However, it is important to reduce the lengthy computation time resulting from the brute-force nature of the original ray-tracing algorithms. In this paper, two ideas are proposed to speep up the well-known hierarchical subdivision method. First, a new hierarchy traversal scheme is described to reduce the number of raybounding volume intersection tests for secondary rays. Then, a plane-sweep method is proposed to make fewer intersection checks for eye rays. Experiments and discussions are presented to prove the feasibility of our methods.     

Improved techniques for ray tracing parametric surfaces

Several techniques for acceleration of ray tracing parametric surfaces are presented. Some of these are entirely new to ray tracing, while others are improvements of previously known techniques. First a uniform spatial subdivision scheme is adapted to parametric surfaces. A new space- and time-efficient algorithm for finding raysurface intersections is introduced. It combines numerical and subdivision techniques, thus allowing utilization of ray coherence and greatly reducing the average ray-surface intersection time. Non-scanline sampling orders of the image plane are proposed that facilitate utilization of coherence. Finally, a method to handle reflected, refracted, and shadow rays in a more efficient manner is described. Results of timing tests indicating the efficiency of these techniques for various environments are presented.     

Coherent multiresolution isosurface ray tracing

We implement and evaluate a fast ray tracing method for rendering large structured volumes. Input data is losslessly compressed into an octree, enabling residency in CPU main memory. We cast packets of coherent rays through a min/max acceleration structure within the octree, employing a slice-based technique to amortize the higher cost of compressed data access. By employing a multiresolution level of detail (LOD) scheme in conjunction with packets, coherent ray tracing can efficiently render inherently incoherent scenes of complex data. We achieve higher performance with lesser footprint than previous isosurface ray tracers, and deliver large frame buffers, smooth gradient normals and shadows at relatively lesser cost. In this context, we weigh the strengths of coherent ray tracing against those of the conventional single-ray approach, and present a system that visualizes large volumes at full data resolution on commodity computers.     

Who invented ray tracing?

We provide some remarks on the very early developments of the visualization techniques conducted during the European Renaissance. It is shown that the basic principle of ray tracing was already presented by Albrecht Dürer (1471–1528) in 1525. This article is intended to be of common interest; it is not a scientific report.     

Fast Ray Tracing NURBS Surfaces

In this paper,a new algorithm wit extrapolation process for computing the ray/surface intersection is presented.Also,a ray is defined to be the intersection of two planes,which are non-orthogonal in general,in such a way that the number of multiplication operations is reduced.In the preprocessing step,NURBS surfaces are subdivded adaptively into rational Bezier patches.Parallelepipeds are used to enclose the respective patches as tightly as possible Therefore,for each ray that hits the enclosure(i.e.,parallelepiped)of a patch the intersection points with the parallelepiped‘s faces can be used to yield a good starting point for the following iteration.The improved Newton iteration with extrapolation process saves CPU time by reducing the number of iteration steps.The intersection scheme is facter than previous methods for which published performance data allow reliable comparison.The method may also be used to speed up tracing the intersection of two parametric surfaces and oter operations that need Newton iteration.     

Dispersive refraction in ray tracing

Dispersive refraction is the property that gives gemstones their fire, and that makes prisms produce a spectrum from white light. Modeling disperison in a ray tracing environment requires solution of some new problems, but allows production of more exciting images. The mechanism of dispersive refraction is discussed, and its implementation is described. Pictures of a prism and of several diamonds are included. Images generated by this technique are realistic, but are computationally expensive.This work was supported in part by the National Science Foundation (DCR-8341796 and MCS-8121750), the Defense Advanced Research Projects Agency (DAAK11-84-K-0017), and the Office of Naval Research (N00014-82-K-0351). All opinions, findings, conclusions or recommendations expressed in this document are those of the author and do not necessarily reflect the views of the sponsoring agencies     

A highly flexible multiprocessor solution for ray tracing

The ray tracing algorithm continues to attract much research and development to improve the quality of the images that are generated, and to reduce the time taken to produce them. By identifying the key requirements of a development system from the user's point of view, we describe a general-purpose multiprocessor solution for ray tracing which may be used to reduce execution time without restricting development of the ray tracing code. The solution is based upon a distributed memory multiprocessor system in which each processor addresses a small amount of memory relative to the size of the model database. Methods for exploiting the coherence of references to entries in the database are described which use a combination of dynamic and static caching techniques. This scheme allows databases of arbitrary size to be supported on multiprocessors with limited distributed memory.