Accelerated Ray-Tracing of Volumetric Data

In ray tracing complex scenes most of the processor time is spent on the ray-object intersection tests [Whi80]. Numerous acceleration techniques were therefore proposed with the aim to minimize the number of the tests by excluding from the consideration beforehand all the objects for which such test fails. One category of such techniques employs uniform subdivision of the scene space in voxels [FTI86], each with a list of relevant objects assigned. The voxels pierced by the ray are then inspected in the direction of the ray progress until the first intersection is found.

Ray tracing is a popular rendering technique also in volume visualization due to its algorithmic simplicity and versatility: within the same framework one can implement different rendering methods (direct surface and volume rendering, MIP) both in software and hardware [Pfi00,MDH$^+$01]. Object representation by the distance fields is similar to the aforementioned uniform subdivision, with two basic differences: instead of a list of objects, a single volume primitive is assigned to each grid location and the number of voxels is typically several orders of magnitude higher ($512^3$ and often even more). In such a case, even traversal of the empty background voxels surrounding the objects can be time consuming.

One possibility how to minimize the time spent for the traversal of the voxels pierced by the ray in large grids is to identify the empty background voxels by segmentation and to gather them in macro-regions, which can be then safely skipped. Devillers [Dev89] proposed to build overlapping cuboid regions and to assign each background voxel to one of them. Other authors used octrees to build hierarchical nonoverlapping macro regions [Lev90,SW91].

Distances for the ray traversal speed-up were for the first time used by Zuiderveld et al [ZKV92]. After the data segmentation, a distance to the object surface is assigned to each background voxel by a distance transform [Bor86]. This information is then utilized during the ray traversal by adapting the sampling step accordingly. The authors used this RADC (Ray Acceleration by Distance Coding) scheme for their implementation of the direct volume rendering by compositing. A similar proximity clouds technique was used by Cohen and Sheffer [CS94] to render surfaces from voxelized data. They observed an uncertainty in the sense that some important non-background voxels were skipped either. Therefore, in order to eliminate this drawback, they proposed to decrease the distances by 1 and to switch the ray traversal algorithm to a 6-connected line generator in the object vicinity.

Both the RADC and proximity clouds techniques can work with different discrete approximations of the Euclidean distance. This in not the case of the Chessboard Distance (CD) voxel traversal technique [Šrá94b], which issues exclusively from the chessboard distance. The CD transform defines a cubic macro-region around each voxel with its sides aligned with the voxel faces. The simple cubic geometry enables further optimizations and even an extension of the technique to rectilinear grids with variable voxel dimensions [ŠK00].