Related Work

For the virtual endoscopy application, visualization methods based on iso-surface rendering are more widely used than those based on volume rendering, since volume rendering techniques usually lack either speed or visual quality. An iso-surface is a surface of constant value (the so-called threshold) inside a three-dimensional data volume. There are two types of iso-surfacing techniques.

The first are surface fitting methods (SFM) which first convert volumetric data into a mesh of polygons using a surface extraction algorithm, e.g., the marching cubes technique [12]. The mesh representing the iso-surface is subsequently rendered using dedicated polygon rendering hardware. Due to hardware acceleration, rendering is fast, if the number of polygons is not too large. The most important disadvantage is limited flexibility. The iso-surface extraction procedure must be carried out every time the threshold (and therefore also the iso-surface) is changed. However, the provision of means of interactive threshold modification is important to allow the physicist to adjust the visual appearance to their needs, which prohibits the use of traditional SFM. During the past few years, some surface fitting techniques that execute a surface extraction procedure during each frame have been introduced. However, those methods either do not yet perform convincingly well or provide functionality that is limited in one way or the other. The fast technique proposed by Hietala et al. [7], for example, does not allow for interactive threshold modification.

The second type of iso-surfacing techniques is first-hit ray casting. Like in the traditional ray casting algorithm [9], each pixel is associated with a viewing ray. However, pixel colors are not accumulated by taking evenly spaced samples along the rays, but determined by intersecting the rays with the predefined iso-surfaces. Pure first-hit ray casting is in general too slow to be applicable in the virtual endoscopy scenario. Many ideas have been presented to accelerate first-hit ray casting in particular and ray casting in general. Important categories of techniques that optimize first-hit ray casting without altering image quality are:

acceleration of empty space traversal

Ray sampling intervals are chosen according to the probability of an iso-surface being intersected [3,6,16].

data set reduction

: interesting parts of the data set are identified prior to the rendering process. Rendering is then confined to those regions [11,15].

improvement of caching behavior

Thrashing is minimized by maximally utilizing cached data before they are replaced [8,14].

Cell-based first-hit ray casting, the new iso-surfacing algorithm that will be introduced in the next section, utilizes each of these three concepts to optimize rendering performance while keeping image quality at a high level.

Also, some acceleration techniques for first-hit ray casting, which trade image quality for speed, have been proposed:

simulation of perspective projection

Rays diverge in a perspective fashion, but are locally orthogonal and can be accelerated using templates [8,14].

usage of frame-to-frame coherency

The result image of a frame is used to predict the next frame. The prediction is then refined [18].

usage of pixel-space coherency

Only a subset of the pixel colors is determined using ray casting, the remaining ones are interpolated [10].

Another way to tackle the problem of interactive visualization for virtual endoscopy is image-based rendering. Wegenkittl et al. [17] introduced a method for the trans-bronchial biopsy application. Virtual cubes are centered on discrete points along a predefined path. In a preprocessing phase, an image is rendered to each of the six sides of each virtual cube, using direct volume rendering. During the interaction phase, it is possible to rotate the camera to any direction by accordingly projecting the six sides of the cube associated with the current view point to the screen. Aided by hardware acceleration, this technique achieves highly interactive frame rates. However, it trades flexibility for speed. Not only must the camera move on the predefined path, also the visual appearance of investigated structures cannot be adjusted at interaction time, since the selection of transfer functions and visualized objects must be done before the rather time-consuming preprocessing phase.