Early Scan Line Termination

Early scan line termination (EST) is an optimization technique that reduces the number of local rays. As described above, each scan line intersected by the projection of the currently processed macro-cell is rasterized from the left to the right projection boundary. EST stops the rasterization process of a scan line as soon as one pixel remains blank because its local ray through the macro-cell did not intersect an iso-surface. It is easily understood that EST cannot be applied every time a local ray leaves a pixel blank, as this would sometimes lead to ray-surface intersections being missed and induce clearly visible errors. So, before rasterization, those parts of the macro-cell projection, in which EST can be safely applied, must be identified. Surface cells, within which ray-surface intersections might be missed due to EST, prohibit EST. They are detected and projected to the image plane in order to identify a critical region. EST can only be executed outside the critical region. Figure 4 shows two examples of iso-surfaces inside macro-cells. Curves and lines connecting those pixels, at which EST takes place, are labelled "EST" and drawn boldly in the figure. In the image on the left, all scan lines can be terminated early, because there is no critical region. In the example on the right hand side, the application of EST is confined by a critical region.

Figure 4: two macro-cells and the applicability of early scan line termination (EST) if scan lines are processed from left to right

To make the concept of early scan line termination more effective, the rasterization algorithm can be adapted according to the geometry of the iso-surfaces inside the macro-cell to allow also scan lines being processed from right to left, or treating pixel columns as scan lines and processing them from top to bottom or bottom to top. If, for example, scan lines are processed from bottom to top in the example on the right hand side in figure 4, all scan lines can be terminated early.

EST does a good job reducing the numbers of local rays per pixel. Figure 5 shows a snap shot from a virtual flight through a human trachea. Figure 6 depicts the numbers of local rays per pixel needed for rendering this image using cell-based first-hit ray casting both with and without EST. The brighter the color of a pixel, the more local rays were cast at that pixel. The wire-frame-like appearance of the image on the right is due to the fact that local rays, which initiate EST, leave the pixel blank. Thus, at pixels at which EST is performed at least one more local ray must be cast. In this example, EST reduces the average number of local rays per pixel from 2.803 to 1.143, which saves, for an image resolution of 512×512, about one second of rendering time for the frame.

Figure 5: a snap shot from a virtual flight through a trachea

Figure 6: numbers of local rays per pixel without (left) and with (right) the usage of early scan line termination

The decision, as to whether a surface cell can be considered unsafe and its projection should be included in the critical region, is based on calculating a representative normal vector for the iso-surface inside the surface cell and testing its direction in screen space. Since a representative surface normal might describe a part of an iso-surface too inaccurately, critical parts of the iso-surface might fail to be detected. Thus, EST can still lead to parts of iso-surfaces being missed. This results in holes in the iso-surface which can be detected after the regular computation of a frame, and filled. The exact criteria for surface cells being considered critical and the hole recovery algorithm are described in the master's thesis about cell-based first-hit ray casting [13].