|
|
Sidebar: Volume Graphics Example - Discrete Ray Tracing
Ray tracing [2] is an image generation technique that simulates light behavior in a scene by following sight rays from the observer's eye as they interact with the scene and the light sources. Therefore, the basic computation performed by a ray tracer is the calculation of the intersection points between rays and objects. This computationally expensive operation accounts for the ray tracers' reputation as a costly method for image generation, which produces, however, superior image quality.
A major strategy for reducing the cost of ray tracing is to divide the world space into a set of rectangular subvolumes called cells [1]. A cell consists of a list of all objects (partially) residing in that region of the world. Rays are then traced as they travel from cell to cell. Only the lists of objects residing in the visited cells are candidates for ordered ray-object intersection calculation. The approach taken in this paper follows a regular space subdivision scheme, that is, all cells are equal-sized cubes. Alternatively, the octree approach divides the space into equal-sized octants. Each octant is independently and recursively subdivided into octants until some measure of uniformity or simplicity, of the scene enclosed by the octant, is satisfied.
When considering any subdivision approach, two issues have to be resolved: first, how to assign each cell its list of objects, that is, how to efficiently compute cell-object intersection; and second, how to step along the ray as it crosses cell boundaries, that is, how to efficiently compute ray-cell intersection. Although in some applications the octree presents a compact representation scheme, it does not perform as well in the case of sampled data and, due to its lack of uniformity, it does not perform the above two tasks as efficiently as the uniform subdivision approach.
Armed with a large memory, we can take the space subdivision approach to an extreme by subdividing into a high resolution uniform grid. This, in turn, can allow us to transform our internal scene representation from a 3D array of cells into a volume buffer of voxels. The major distinctions between a cell and a voxel lies in the assumptions made concerning voxels. First, it is assumed that the voxel grid resolution is adequate, that is, there is no large variation of surface attributes across the voxel extent. In addition, unlike a cell, which consists of a list of objects, the voxel represents the smallest space enumeration entity and therefore consists of information on a single object, much like its 2D counterpart, the pixel.
A ray tracing approach that employs a volume buffer is called 3D raster ray tracing (RRT) [4]. It operates in two phases: a preprocessing voxelization phase and a discrete ray tracing phase. In the voxelization phase the geometric model is digitized, using voxelization algorithms, which convert the continuous representation of the model into a discrete representation that is stored in the volume buffer (see Fundamentals of Voxelization ). For datasets that are already digitized, as in 3D medical imaging and 3D computational visualization, the discretization step is, of course, unnecessary. In the second phase a discrete variation of the conventional recursive ray tracer is employed. Unlike conventional ray tracing algorithms, in which analytical rays are intersected with the object list in order to find the closest intersection, in RRT 3D discrete rays (which are essentially voxelized lines) are traversed through the 3D raster in order to find the first surface voxel. Encountering a non-transparent voxel indicates a ray-surface hit. The view-independent attributes stored in the voxel (e.g., normal) are readily available for calculating spawning offspring rays and computing the illumination at that point. Figures 7 and 8 show the RRT rendering of both a geometric model ( Figure 8) and a sampled dataset intermixed with geometric objects and manipulated with block operations ( Figure 7).
In conventional ray tracing, computation time grows with the number of objects, and performance is greatly influenced by the type of objects comprising the scene; intersection calculation between a ray and a parametric surface is significantly more complex than intersecting the ray with a sphere or a polygon. In contrast, RRT completely eliminates the a computationally expensive ray-object intersection calculation, and instead relies solely on fast discrete ray traversal mechanism and a single simple type of object the voxel. Consequently, RRT performance is effectively independent of the number of objects in the scene or the objects' complexity or type. Therefore, for a given resolution, ray tracing time is nearly constant and can even decrease as the number of objects in the scene increases, as less stepping is necessary before an object is encountered.
Observing the nature of RRT, we note that it can precompute the view-independent attributes during the voxelization phase, is attractive for ray tracing 3D sampled datasets and computed datasets, and can support ray tracing of CSG models that are efficiently synthesized and constructed during the voxelization phase [3]. To recapitulate, RRT is a typical example of a volume graphics technique, demonstrating the attractive features intrinsic to the volumetric approach to 3D graphics.
References
1. Fujimoto, A., Tanaka, T. and Iwata, K., " ARTS: Accelerated Ray-Tracing System ", Computer Graphics & Applications, 6, 4 (April 1986), 16-26.
2. Glassner (ed.), A. S., in An Introduction to Ray Tracing, Academic Press, London, 1989.
3. Yagel, R., Kaufman, A. and Zhang, Q., " Realistic Volume Imaging", Visualization'91 Proceedings, San Diego, CA, October 1991.
4. Yagel, R., Cohen, D. and Kaufman, A., "Discrete Ray Tracing", IEEE Computer Graphics and Applications, September 1992, 19-28.