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     

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     

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.     

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.     

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     

Object-oriented program tracing and visualization

Conventional program analysis and presentation techniques are insufficient when dealing with object oriented concepts, but tool developers have nevertheless found a way to obtain and visualize OO traces. The approach presented combines static information with actual execution information to produce views that summarize the relevant computation. In developing this approach, the authors focused on reducing the search space for extracting dynamic program information and on creating visualizations that may improve a programmer's understanding of object behaviour in real world OO systems. They applied the research prototype, Program Explorer, to a real project outside IBM. Although Program Explorer was originally designed for C++, a version for IBM's System Object Model (SOM) has demonstrated that the concepts are applicable to OO languages in general     

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%     

Efficient shadow computations in ray tracing

Two techniques to speed up shadow computations in ray tracing are examined. The first, atomic adaptive sampling, is intended for any light type, such as directional, spot, point, linear, and area lights, in antialiasing, while the second, plane-vertex checking, specifically accelerates shadow computation of linear and area lights. The basic ideas can be extended to other ray types and, for the plane-vertex check, to radiosity applications as well. Existing surveys explain the fundamentals and provide references to intersection culler and shadow algorithms     

Adaptive cell division for ray tracing

In ray tracing the two most commonly used data structures are the octree and uniform cell division. The octree structure allows efficient adaptive subdivision of space, while taking care of the spatial coherence of the objects in it; however, the tree structure locating the next node in the path of a ray is complex and time consuming. The cell structure, on the other hand, can be stored in a three-dimensional array, and each cell can be efficiently accessed by specifying three indices. However, such a uniform cell division does not take care of object coherence. The proposed data structure combines the positive features of the above data structures while minimising their disadvantages. The entire object space is implicitly assumed to be a three-dimensional grid of cells. Initially, the entire object space is a single voxel which later undergoes “adaptive cell division.” But, unlike in the octree structure, where each voxel is divided exactly at the middle of each dimension, in adaptive cell division, each voxel is divided at the nearest cell boundary. The result is that each voxel contains an integral number of cells along each axis. Corresponding to the implicit cell division we maintain a three-dimensional array, with each array element containing the voxel number which is used to index into the voxel array. The voxel array is used to store information about the structure of each voxel, in particular, the objects in each voxel. While a ray moves from one voxel to another we always keep track of the cell through which the ray is currently passing. Since only arrays are involved in accessing the next voxel in the path of the ray, the operation is very efficient.     

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     

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.     

光线跟踪方法在体绘制中的应用与发展

针对光线跟踪方法存在求交计算量大、实时交互性差等缺点.从体光线跟踪算法、基于图形硬件加速的光线跟踪体绘制方法,并行光线跟踪体绘制技术这3个方面,对国内外光线跟踪方法在体绘制中的应用技术进行了分类描述与综述,重点介绍了体光照模型、光线跟踪混合绘制、基于可编程硬件加速、并行绘制算法及体系结构,并结合应用阐述了各自特点及其相互联系,最后对光线跟踪方法在体绘制的应用提出了研究建议.     

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.