基于GPU快速光线跟踪算法的设计与实现

设计和实现了GPU上基于流的光线跟踪算法,采用一种基于线索二叉树的KD-Tree结构组织场景,避免了传统KD-Tree结构在遍历场景时在堆栈上的开销。算法在组织复杂场景上,优于利用传统KD-Tree和均匀剖分结构加速场景遍历的方法,在普通PC上实现了光线跟踪的快速渲染。     

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.     

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     

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.     

GemstoneFire: adaptive dispersive ray tracing of polyhedrons

Synthesizing realistic images of gemstones requires techniques beyond the scope of normal ray tracing. The fire of such highly refractive objects is what makes gemstones attractive, and also imposes very high computational overhead to perform time consuming dispersive ray tracing. Gemstones are usually cut in polyhdrons as for example, a brillant cut. After a detailed analysis of the nature of dispersive ray tracing of polyhedral objects, we propose here a new method of using three simple rays adaptively to model the ray spreading caused by dispersive refraction. It is shown that the proposed method reduces the computational complexity to an order close to that of normal ray tracing.     

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.     

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     

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 performance analysis exemplar: Parallel ray tracing

Among the many techniques in computer graphics, ray tracing is prized because it can render realistic images, albeit at great computational expense. Ray tracing's large computation requirements, coupled with its inherently parallel nature, make ray tracing algorithms attractive candidates for parallel implementation. In this paper we illustrate the utility and the importance of a suite of performance analysis tools when exploring the performance of several approaches to ray tracing on a distributed memory parallel system. These ray tracing algorithm variations introduce parallelism based on both ray and object partitions. Traditional timing analysis can quantify the performance effects of different algorithm choices (i.e. when an algorithm is best matched to a given problem), but it cannot identify the causes of these performance differences. We argue, by example, that a performance instrumentation system is needed that can trace the execution of distributed memory parallel programs by recording the occurrence of parallel program events. The resulting event traces can be used to compile summary stapistics that provide a global view of program performance. In addition, visualization tools permit the graphic display of event traces. Visual presentation of performance data is particularly useful, indeed, necessary for large-scale, parallel computations; assimilating the enormous volume of performance data mandates visual display.     

Interactive ray tracing of skinned animations

Recent high-performance ray tracing implementations have already achieved interactive performance on a single PC even for highly complex scenes. However, so far these approaches have been limited to mostly static scenes due to the high cost of updating the necessary spatial index structures after modifying scene geometry. In this paper, we present an approach that avoids these updates almost completely for the case of skinned models as typically used in computer games. We assume that the characters are built from meshes with an underlying skeleton structure, where the set of joint angles defines the character’s pose and determines the skinning parameters. Based on a sampling of the possible pose space we build a static fuzzy kd-tree for each skeleton segment in a fast preprocessing step. This fuzzy kd-tree is then organized into a top-level kd-tree. Together with the skeleton’s affine transformations this multi-level kd-tree allows fast and efficient scene traversal at runtime, while arbitrary combinations of animation sequences can be applied interactively to the joint angles. We achieve a real-time ray tracing performance of up to 15 frames per second at 1024×1024 resolution even on a single processor core.     

Faster ray tracing using adaptive grids

A new hybrid approach is presented which outperforms the regular grid technique in scenes with highly irregular object distributions by a factor of hundreds, and combined with an area interpolator, by a factor of thousands. Much has been said about scene independence of different acceleration techniques and the alleged superiority of one approach over another. Several theoretical and practical studies conducted in the past have led to the same conclusion: a space partitioning method that allows the fastest rendering of one scene often fails with another. Specialization may be the answer. This has always been pursued, consciously or not, in developing various ray-tracing systems. Despite our new algorithm's impressive efficiency, we don't interpret the new method as the fastest ray-tracing scene decomposition possible. This is because our recent groundwork experiments with a derivative method produced in some of the test scenes presented in this article produced timings that were better by approximately 50%