Shadow Sweep Elimination

Figure 4.4: Removal of hidden voxels in 2D: a) viewpoint-independent preprocessing: relevance of voxel $V$ depends on rays passing through eight neighbors. b) 4 view-sets: relevance of $V$ depends on three neighbors. c) 8 view-sets: dependency minimized (two neighbors).

Although the above approach is able to remove approximately half of a data set, many voxels have to remain in the volume even if they only contribute to a MIP for a narrow range of viewing directions. If enough memory is available for redundant storage of the data, more efficient preprocessing can be performed by subdividing all possible viewing directions into disjoint view-sets in a way which minimizes dependencies among voxels (figure 4.4). The highest efficiency of removal in 3D can be achieved if 24 such view-sets are used. For each view-set a set of potentially visible voxels is computed using a two-pass procedure:

Figure 4.5: View-point dependent voxel removal (2D). a) Shadowed voxel sweep. b) Leading voxel sweep.

• Shadowed voxel sweep: Mark all voxels $V$ in shadow of (local) maxima as non-contributing. This is the case when $d(V)$ is lower than the smallest ray maximum of rays through $V$ collected before reaching $V$. This can be easily performed by sweeping through the volume and processing voxels in the order in which they are hit by an advancing front of rays. During this process a front is propagated which contains the smallest maximum values for rays entering each voxel directly ahead of the front. Considering the example in figure 4.5a, all viewing-rays of the given view-set through voxel $V$ have first to pass either through $V_1$ or $V_2$. The lowest possible values of rays at $V_1$ and $V_2$ respectively are $min_1=d(V_1)$ and $min_2=d(V_2)$, as both $V_1$ and $V_2$ are on the border of the volume. Thus the lowest possible value of a ray arriving at $V$ is $arr_V=min(min_1,min_2)$. As $d(V)>arr_V$, $V$ may influence some of the arriving rays, and can not be removed. The value of the rays after passing $V$ equals $max(arr_V, d(V))$ and influences the values of rays arriving at the successive voxels $V_3$ and $V_4$.
• Leading voxel sweep: During the second pass all low-valued voxels in front of voxels containing unremoved (local) maxima are removed. The removal is performed in the same way as step 1 with the difference that the scan is performed opposite to the direction of the viewing rays (figure 4.5b). Note, that voxels removed during the shadowing sweep have no influence on ray maxima during the second sweep.

Direction dependent preprocessing allows to remove about three quarters of all voxels for each view-set (see table 4.1). During rendering, voxels of the view-set which contains the current viewing direction are selected and rendered.

mailto:mroz@cg.tuwien.ac.at.