Analysis of an algorithm for fast ray tracing using uniform space subdivision

Ray tracing is becoming popular as the best method of rendering high quality images from three dimensional models. Unfortunately, the computational cost is high. Recently, a number of authors have reported on ways to speed up this process by means of space subdivision which is used to minimize the number of intersection calculations. We describe such an algorithm together with an analysis of the factors which affect its performance. The critical operation of skipping an empty space subdivision can be done very quickly, using only integer addition and comparison. A theoretical analysis of the algorithm is developed. It shows how the space and time requirements vary with the number of objects in the scene.     

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.     

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.     

Efficient parallel spatial subdivision algorithm for object-based parallel ray tracing

Parallel ray tracing of complex scenes on multicomputers requires the distribution of both computation and scene data to the processors. This is carried out during preprocessing and usually consumes too much time and memory. The paper presents an efficient parallel subdivision algorithm that decomposes a given scene into rectangular regions adaptively and maps the resultant regions to the node processors of a multicomputer. The proposed algorithm uses efficient data structures to identify the splitting planes quickly. Furthermore the mapping of the regions and the objects to the node processors is performed while parallel spatial subdivision proceeds. The proposed algorithm is implemented on an Intel iPSC/2 hypercube multicomputer and promising results have been obtained.     

Two algorithms for taking advantage of temporal coherence in ray tracing

The basic ray-tracing algorithm is adapted to make ray-tracing faster for the production of motion pictures. Two algorithms are presented. The image space temporal coherence algorithm takes advantage of the fact that motion picture images do not change very much from frame to frame. The reprojection algorithm uses information about the object space saved from the previous frame to accelerate the processing of the current frame. The reprojection algorithm is used when the viewpoint of the current frame is changed by a small amount from the viewpoint of the previous frame.     

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.     

Ray tracing: A quantitative analysis and a new practical algorithm

We present a new method to accelerate the process of finding nearest ray-object intersections in ray tracing. The algorithm consumes an amount of memory more or less linear in the number of objects. The basic ideas can be characterized with a modified BSP tree and plane traversal. Plane traversal is a fast linear time algorithm to find the closest intersection point in a list of bounding volumes hit by a ray. We use plane traversal at every node of the high outdegree BSP tree. Our implementation is competitive to fast ray-tracing programs. We present a benchmark suite that allows for an extensive comparison of ray-tracing algorithms.     

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.     

Shadows on bump-mapped surfaces in ray tracing

This paper presents a method of generating shadows on bump-mapped surfaces in ray tracing. The method yields images with realistic shadows influenced by bumpy surface geometry. In our method, intersections are calculated between eye/reflection/refraction rays and smooth original surfaces as usual, and the surfaces and shaded according to Blinn's bump mapping. For shadowing, however, we shift the intersection points based on the approximated bumpy surface shape, and the shadow rays are fired from the shifted intersection points. Since the method involves no explicit intersection calculation between rays and bumpy surfaces, it requires only a small amount of computation in addition to conventional ray tracting. It is easy to insert the method into existing ray tracers, and it can be applied to variants of ray tracing algorithms that use shadow rays.     

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.     

Parallel processing of an object space for image synthesis using ray tracing

This paper presents a novel parallel processing system for image synthesis using ray tracing. An object space is divided into parts (subspaces), each of which is allocated to a processor. The processor detects, simultaneously the intersections of the surfaces of each object and a fixed number of rays over the whole space, and calculates the local intensity on an object in each subspace. The global intensities of pixels on a screen are calculated by the other kind of processors simultaneously. We also present the optimal data structure, based on an adaptive division algorithm, for parallel processing of the object space.     

Data structures and the time complexity of ray tracing

The time complexity of ray tracing is a function of the data structures used for space division. Octree and hierarchical extents have been suggested as effective choices. In this paper, complexity parameters are suggested to characterize images and show that both octrees and hierarchies are appropriate choices if given most favorable images. Also, a unified technique is proposed and shown to be better than previous methods for all images. Octrees and hierarchies are particular cases of the new proposed algorithm.     

Tracing a ray through uniformly subdividedn-dimensional space

Finding the cells intersected by a ray in a uniformly subdivided space is a technique used in accelerated ray tracing and also other computer graphics applications. A related problem is that of finding the sequence of grid points in a 3D voxel space, which best approximates a given line. This paper examines earch of these problems, introduces a unifying approach and provides a generalisation of previous algorithms.Written while on sabbatical leave from Department of Computer Science, QMW University of London, Mile End Road, London E1 4NS, UK     

Nonlinear ray tracing: Visualizing strange worlds

Nonlinear ray tracing is investigated in this work. Sources of nonlinearity such as gravity centers, gravity lines, chaotic dynamical systems, and parametric curved rays are discussed. Curved rays are represented either iteratively or hierarchically. Algorithms for testing whether a curved ray and a 3D object intersect are presented. Sample images of a test implementation show the feasibility of the approach. Applications of nonlinear ray tracing are the visualization of relativistic effects, visualization of the geometric behavior of nonlinear dynamical systems, visualization of the movement of charged particles in a force field (e.g., electron movement), virtual reality, and arts.     

Investigation of starburst phenomenon using ray tracing for touch screen panels

We investigate the effect of the metal pattern shape (i.e., square, hexagonal, and random grids) on the starburst phenomenon of touch screen panels (TSPs) based on opaque metallic grids. It is demonstrated that a standalone random metal grid can suppress the starburst phenomenon to a great extent. By way of ray tracing simulation, we have found that specular reflection of light on the gentle slope of the patterned edges of metallic grids contributes to the generation of starburst patterns. It is also addressed that employing a light-absorbing material and increasing metal grid spacing can reduce the intensity of starburst patterns.     

Parallel ray tracing based upon a multilevel topological knowledge acquisition of the scene

Including the standard parallelization by grouping primary rays, this paper presents a new parallel ray-timing method based upon a topological knowledge acquisition of the scene. This topological knowledge focuses on relative positions between objects and processes and uses a new type of message. Indeed, instead of exchanging database pages or rays, processes exchange topological information. This information is used by each process to decrease its own list of objects to test against rays The acquisition of information about relative positions between objects and processes is obtained by a careful ordering of he pixel calculation. The processes are dispatched on a computer network including a parallel computer The organization of the processes on this network is a multilevel one leading to different levels of topological message exchanges This method is characterized by topological messages describing the scene, dynamic optimization of the database, easy parallelization on any network (no deadlock, fault tolerance, easily expandable and simple routing), and gives interesting results with true or simulated parallelism.     

Efficient,complete radiosity ray tracing using a shadow-coherence method

Most two-pass rendering methods calculate a radiosity shading for each patch or element in a scene in the first pass. This shading contains two components: one for the light received directly from the main light sources and one representing the intensity of the light received indirectly by means of diffuse and specular interreflection between patches. However, it is very difficult to achieve accurate representation of the distribution of this radiosity shading over the patch, particularly where clearly visible shadow boundaries exist. A better approach is to store only the indirect reflection component in the form of radiosity shading, and to calculate the direct reflection component during the second pass by casting shadow rays. This approach normally requires that many shadow rays must be cast. However, the number of rays for shadow testing can be kept low by selecting only those light sources that substantially contribute to the shading of a patch and applying an adaptive image refinement technique in combination with a shadow coherence method.