Neighborhood-based Elimination

Figure 4.2: Detection of voxels $V$ which do not contribute to any MIP. For simplicity the different cases are shown in 2D. a) $V$ irrelevant for rays through $W_{i}$ as $d(W_{i})\geq d(V)$ b) $V$ irrelevant for rays through $W_{i}$. c) $V$ irrelevant for rays through $W_{i}$ as ray maxima are determined by voxels $U_{m}$. d) $V$ irrelevant for rays through $W_{i}$, as ray maxima are determined by $U_{n}$.

A simple approach for the identification of ``hidden'' voxels is to examine direct neighbors $W_{i}$ of a voxel $V$. If $V$ does not influence the maximum of any ray passing through $V$ and any of it's neighbors $W_{i}$, it can be removed. Obviously, this is the case if all rays through $V$ pass through a neighbor $W_i$ with $d(W_{i})\geq d(V)$ either before of after passing through $V$.This condition can be tested by examining the values of all 26 direct neighbors $W$ of $V$:

• If for all $i$: $d(W_{i})\geq d(V)$, all rays through $W_{i}$ and $V$ will have at least the value $d(W_{i})$ and are not influenced by $V$ (see figure 4.2a).
• If for some $i$: $d(W_{i})<d(V)$, but all rays through $W_{i}$ and $V$ pass through another neighbor $W_j$ of $V$ with $d(W_j)\geq d(V)$, the ray-values will at least be $d(W_j)$. Thus $V$ has also no influence on rays through $W_{i}$ (see figure 4.2b).

Voxel elimination which is based on these two tests can be performed rapidly (see table 4.1) and just requires access to direct neighbors of each voxel. If the above tests fail for a group of rays through $W_i$, $V$, and $W_j$, with $d(W_i)<d(V)$ and $d(W_j)<d(V)$, the influence of a larger neighborhood of $V$ on the value of these rays can be checked. Each ray passes through a sequence of voxels $U_k$ with $U_l=V$, $U_{l-1}=W_i$ and $U_{l+1}=W_j$ as the volume is traversed. If each of those rays passes through some voxel $U_m$ with $m<l-1$ and $d(U_m)>d(V)$, $V$ has no influence on the values of the rays through $W_i$ and $W_j$ (figure 4.2c). Similarly, if all rays through $W_i$ and $W_j$ pass through voxels $U_n$ with $n>l+1$ and $d(U_n)>d(V)$, $V$ has no influence on the values of those rays (figure 4.2d).

Figure 4.3: Tracking the influence of distant parts of the volume on rays through $W_i$, $V$ and $W_j$. As all of them pass either through $U_1$, $U_2$ or $U_3$ and $d(U_2)>d(V)$, $V$ does not influence rays through $U_2$, $W_j$, $V$ and $W_i$. As $d(U_1)<d(V)$ and $d(U_3)<d(V)$, further tracking of rays passing through $U_1$ or $U_3$ is required.

The check of the influence of more distant volume areas can be realized by recursively propagating bundles of rays starting at direct neighbors of $V$ (see table 4.1). If a voxel $U$ is hit by a bundle of rays and $d(U)\geq d(V)$ the tracking of the bundle is terminated, as $V$ has no influence on the rays. If $d(U)<d(V)$ the bundle is split and tracked in a subset of the neighbors of $U$ (figure 4.3).

To improve efficiency and avoid unnecessary recursive checks, values of voxels scheduled for removal are replaced by the minimum of their obscuring values (which is always larger or equal to their original value). To compensate for noise in the data and to increase the number of rejected voxels a user specified tolerance value $\varepsilon$ can be included in the comparison process, which artificially lowers the value of each checked voxel $V$ by $\varepsilon$. For voxel reduction rates using different elimination efforts and tolerance values $\varepsilon$ please refer to table 4.1. Although recursive elimination requires significantly more time, it may be the method of choice if data is prepared on a high-end machine for viewing with low-end hardware over a network.

Table 4.1: Volume reduction: Fast optimization (``Fast'') considers direct neighbors, full optimization (``Full'') performs recursion up to a distance of 10 voxels. Direction dependent optimization produces 24 view-dependent sets of voxels. The results show the percentage of voxels removed and the time required for preprocessing on a PII/450 PC.

data	size	Fast	Full	Fast	Full	direction
set		$\varepsilon=$0%	$\varepsilon=$0%	$\varepsilon=$1%	$\varepsilon=$1%	dependent
angio	256$^2\times$64	25%	47%	29%	53%	73%
		5s	270s	5s	270s	72s
mr01	256$^2\times$74	33%	46%	45%	55%	72%
		6s	208s	6s	208s	76s
mr03	256$^2\times$124	29%	58%	29%	58%	70%
		10s	562s	10s	562s	120s

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