 |
|
As stated in the previous sections, it is important to ensure that data once replaced in the cache will not be requested again, thus avoiding thrashing. Law and Yagel have presented a thrashless distribution scheme for parallel raycasting [22,23,21]. Their scheme relies on an object space subdivision of the volume. While their method was essentially developed in the context of parallelization, avoiding multiple distribution of data, it is also useful for a single-processor approach.
The volume is subdivided into blocks, as described in Section 3.3.1. These blocks are then sorted in front-to-back order depending on the current viewing direction. The ordered blocks are placed in a set of block lists in such a way that no ray that intersects a block contained in a block list can intersect another block from the same block list. Each block holds a list of rays whose current resample position lies within the block. The rays are initially assigned to the block which they first intersect. The blocks are then traversed in front-to-back order by sequentially processing the block lists. The blocks within one block list can be processed in any order, e.g., in parallel. For each block, all rays contained in its list are processed. As soon as a ray leaves a block, it is removed from its ray list and added to the new block's ray list. When the ray list of a block is empty, processing is continued with the next block. Figure 3.10 illustrates this approach.
The generation of the block lists does not have to be performed for each frame. For parallel projection there are eight distinct cases where the order of blocks which have to be processed remains the same. Thus, the lists can be pre-computed for these eight cases. Figure 3.11 shows this for 2D where there are four cases.
 |