next up previous
Next: Rasterization Up: paper Previous: Segmentation

Cell-Based First-Hit Ray Casting

Cell-based first-hit ray casting is a new fast first-hit ray casting algorithm, usable for virtual endoscopy, which renders a number of predefined iso-surfaces. This section gives a detailed description of the algorithm.

The algorithm is based on the organization of volume data as a min-max octree. Each node of the octree represents a cubic sub volume and stores the minimum and maximum data values of this sub volume. Leaf nodes of the octree represent so-called macro-cells which are cubic sub volumes consisting of n3 data cells ((n + 1)3 voxels). Usual values of n range between 3 and 10. By traversing the octree, macro-cells containing a part of one of the iso-surfaces can be found efficiently. Each of those macro-cells is trimmed to the smallest cuboid containing the macro cell's portions of the iso-surfaces and then projected to the screen plane. The projection is rasterized and a ray is cast through each covered pixel. This local ray is only tracked through the currently processed macro-cell. Through the application of a fast voxel traversal algorithm [1], cells, which are pierced by the ray and contain a part of an iso-surface, are detected. Within these surface cells, a ray-surface intersection test is performed. If an intersection is found, the gradient vector at the intersection point is calculated and a color is computed for the corresponding pixel, and, if the iso-surface is opaque, the pixel is marked such that no more local rays are cast at this pixel during the current frame.

It is easily understood that macro-cells must be processed in viewing order to avoid visibility artefacts. Therefore, during octree traversal, child nodes of the currently processed node must be sorted according to the viewing vector and accessed in the correct order.



Subsections
next up previous
Next: Rasterization Up: paper Previous: Segmentation
André Neubauer 2002-03-21