Cell Removal

A cell $C$ does not contribute to MIP from any viewing direction (and therefore should not to be considered for rendering), if all rays passing through it collect a higher value by passing through other cells $D$ either before or after $C$ is processed. The first approach is to investigate direct neighbors $D_i$ of a cell $C$ only. $C$ does not contribute to any ray through it if $\forall i \vert (C_{max}\leq D_{i min})$. As we assume continuous rays to be traced through the volume, only face-connected neighbors of $C$ have to be considered (A ray entering $C$ through an edge or vertex at least ``touches'' some face-connected neighbors).

Applying such a unified relevance detection for cell elimination, which considers the whole domain of viewing directions, is very ineffective and leads to low cell removal rates. Significantly better results can be achieved if several distinct clusters of similar viewing directions are distinguished. For rendering, the set of cells corresponding to the cluster which contains the current viewing-direction is selected and used for MIP. To minimize the number of neighbors which have to be checked for elimination, a decomposition of all viewing directions into 24 clusters is performed first (in the same way as for the voxel-based MIP). Each cluster of viewing directions corresponds to a quarter-face of the directional cube as depicted in figure 4.12b. Considering just viewing directions out of one cluster, a cell's relevance to MIP depends on just three neighbors (figure 4.12c) instead of six as in the case of viewpoint-independent preprocessing (figure 4.12a).

Figure 4.12: a) relevance of cell $C$ depends on values of 6 face-connected neighbors $D_i$. b) decomposition of the viewing-domain into 24 (12) clusters of viewing directions. c) for any viewing direction within cluster 11 relevance of $C$ depends on the values of at most 3 direct neighbors

As the direction of ray traversal is not relevant for MIP and a MIP generated from a certain viewing direction produces exactly the same image as a MIP from the opposite direction, sets of possibly contributing cells have only to be calculated for 12 of the 24 clusters of viewing directions. Furthermore, as can be seen in figures 4.12b and c, three clusters of viewing directions around each corner of the directional cube result in the same set of direct neighbors on which a cell's relevance depends (for example clusters 1, 11 and 20). Unfortunately, the clusters differ in the way in which the estimations for rays entering through cell faces combine to the estimations for exiting faces. As the removal algorithm uses face estimations for determining non-contributing cells, the clusters can not be combined without sacrificing removal efficiency.

To achieve effective cell elimination, not only the influence of direct neighbors, but also the influence of more distant cells on rays has to be investigated. This can be done by applying a simple two-pass scheme for each cluster of viewing directions. For reasons of simplicity, the procedure will be explained in 2D. The extension to 3D is straight-forward.

Figure 4.13: a) Viewing domain decomposition in 2D. b) face-maximum propagation for cluster 1

For cell removal in 2D, the viewing domain is decomposited into 8 clusters, each one covering a range of viewing directions spanning 45 degrees (figure 4.13a). Rays within cluster 1 can enter cell $C$ only through edge $\overline{v_1v_4}$ or $\overline{v_4v_3}$. Considering just the values at the cell's vertices, cell $C$ has no influence on the maximum of rays through $\overline{v_1v_4}$, if $min(v_1,v_4)\geq max(v_2,v_3)$ - in this case, the maximum contribution of the cell to any ray entering through $\overline{v_1v_4}$ and leaving through $\overline{v_1v_2}$ or $\overline{v_2v_3}$ is located on the edge $\overline{v_1v_4}$. As this edge is shared with cell $D$ which is traversed by the rays earlier, $C$ does not contribute to the rays. Similarly, the cell has no influence on rays through $\overline{v_4v_3}$ if $min(v_3,v_4)\geq max(v_1,v_2)$ due to the contribution of cell $E$ - the condition for $\overline{v_4v_3}$ has to consider the influence of $v_1$, as a large data value at $v_1$ may influence the data gradient within the cell in a way that rays through $\overline{v_4v_3}$ obtain a larger value within the cell than at $\overline{v_4v_3}$ or $\overline{v_2v_3}$.

By preprocessing the volume in a spatially consecutive order, the influence of cells on ray maxima can be propagated with an advancing front approach. In the example in figure 4.13b, cells $D$ and $E$ are processed before cell $C$ is reached. For both of them, lower-bound estimations of the maximum for rays which leave the cells have been calculated (for this cluster, rays leave cells either through face $\overline{v_2v_3}$ or through face $\overline{v_1v_2}$). This means, that at the time $C$ is processed, lower-bound estimations $m_{1,4}$ for rays entering through $v_1v_4$ and $m_{3,4}$ for rays entering through $v_3v_4$ are available, which already include the influence of more distant (preceding) cells and the influence of the edges themselves ($min(v_1,v_4)$ and $min(v_3,v_4)$). Thus, the revised test for the irrelevance of cell $C$ is $m_{1,4}\geq max(v_2,v_3)$ and $m_{3,4}\geq max(v_1,v_2)$. If both conditions are true, $C$ is removed and never ever considered for MIP anymore. After classifying the cell, the lower-bound estimations for the maxima of rays leaving the cell have to be computed. As for the investigated cluster of viewing directions only rays which have entered the cell through $\overline{v_1v_4}$ can leave through $\overline{v_1v_2}$, the estimation for rays through $\overline{v_1v_2}$ is $m_{1,2}=max(min(v_1,v_2),m_{1,4})$. As rays entering through both, $\overline{v_1v_4}$ and $\overline{v_3v_4}$ can leave through $\overline{v_2v_3}$, the estimation for $v_2v_3=max(min(v_2,v_3),min(m_{1,4},m_{3,4}))$.

While the first sweep allows to identify and remove low-valued cells located behind higher-valued parts of the volume, a second sweep in the opposite direction is required to propagate the influence of high-valued cells to cells reached earlier by the rays of this cluster. The second sweep is identical with the first sweep with the exception of the inverted orientation of the rays and thus an inverted volume scan order. Cells which have been removed during the first sweep do not influence ray values during the second sweep. Considering also cells removed during the first sweep would result in mutual elimination of cells and would lead to holes in the volume.

The two-pass method presented above can be extended to 3D in a straight-forward way. For a decomposition of the viewing domain into 24 (12) clusters, rays may enter and leave cells through three faces for each cluster. Lower-bound estimations have to be propagated for faces instead of edges.

To even further increase the efficiency of removal and to compensate for noise which is usually present in MR data sets, the removal process can be modified to remove also cells which violate the exact criteria by a factor which does not exceed a user specified threshold (removal tolerance). After the preprocessing with a 1% tolerance, on average only about 30% of all cells remain as possibly contributing for a single view-set. For detailed results please refer to section 4.2.4 and table 4.5.

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