Results

Table 4.3: Comparison of ray-casting based MIP (trilinear interpolation, columns 4 and 5 with optimizations) with the proposed approach (RenderList of cells and optimizations).

levels of proposed	preprocessing	memory	speed-up compared to
approach	time	factor	brute	+ $C_{max}$	+ignore
			force	$>max$	noise
RenderList	6s	2.0	1.3-1.4
+ $C_{max}>max$	6s	2.0	6.1-7.4	3.9-5.3	3.1-4
+ ignore noise	6s	2.0	20-40	14-25	11-20
+ cell elimination	93.6s	3.6-12	28-43	18-27	14-22

Table 4.4: Comparison of interpolation efficiency: brute-force (row 1) interpolates at every step along ray (col. 1), within every cell (col. 2). Each pixel changes 24 times (col. 3). Row 2: interpolation only if $C_{max}>max$. Row 3: also ignore low-valued cells. Row 4 shows the results for the proposed approach.

method	interpolations	cells	pixels set
brute-force	100%	100%	24
+ $C_{max}>max$	26%	29%	24
+ ignore noise	7.7%	7.8%	13
cell array	1.3%	2.5%	1.65

The MIP algorithm presented in this paper has been implemented as a Java applet. The applet and further high-resolution results are available at ( http://www.cg.tuwien.ac.at/research/vis/vismed/CMIP/). A C implementation is expected to exhibit a 30-40% better performance.

Table 4.3 depicts the speed-up achieved by the RenderList-based method compared to brute-force ray casting with trilinear interpolation (integer arithmetic) and to optimized ray-casting (no interpolation in cells with $C_{max}\leq max$, skip background noise which is windowed to black). The second row (sorted cells, evaluation only if $C_{max}>max$) clearly shows the advantage of projecting high-valued cells first (factor 3-7). Even more performance is gained by the ability to skip low-valued cells without any overhead (row 3). This results in a speed-up factor of 11-40. Finally, by eliminating cells during the preprocessing step, factors of up to 43 compared to brute-force rendering and up to 22 compared to optimized ray-casting can be achieved.

Rendering times as compared in table 4.3 may depend on the optimization of the implementation. To obtain a less implementation-dependent measure for the efficiency of the approach, the number of interpolations performed, cell-, and image-access statistics of the algorithm are compared to ray casting in table 4.4. Compared to even optimized ray casting, the cell-array requires five times less interpolations. Also, updates of ray-maxima and thus of pixel values occur significantly less frequently during the rendering process. Due to the difference in the number of interpolations performed, it can be concluded, that a speed-up factor of approximately five is related to the avoidance of cell evaluations. The remaining portion of the speed-up is based on efficient volume traversal (strictly linear access to the cell array) and cell skipping.

Table 4.5 shows cell removal statistics for the preprocessing of the hand data set depicted in figures 4.15 and 4.16 and the kidney data set of figure 4.17a. As the second sweep eliminates just few additional cells, it can be optionally omitted to shorten the preprocessing. Increasing the tolerance for preprocessing mainly affects low-gradient areas which usually do not contain vessel data (figure 4.16).

Table 4.6 presents statistical information on the number of cells involved in the image creation, the number of upper-bound estimations for ray-cell intersections and the percentage of intersections which require a more accurate trilinear interpolation to evaluate the maximum within a cell. Rows 1 and 2 represent the hand data set for two different image sizes, Row 3 shows data for the kidney data set.

Finally, table 4.7 presents rendering times for MIP using the cell array approach. The rendering times have been measured on a PIII/750 PC.

Figure 4.15: Quality comparison of MIP which was produced using a) ray casting with trilinear interpolation, b) ray casting with nearest neighbor interpolation, c) shear/warp projection with nearest-neighbor interpolation, d) RenderList and trilinear interpolation. The difference images depict amplified differences with respect to ray casting with trilinear interpolation.

		d) sorted cells
		c) n. neighbor shear/warp
		b) n. neighbor ray casting
	difference	a) trilinear interpolation

Figure 4.16: Results for RenderList-based MIP with different tolerance values for preprocessing (hand data set). As the tolerance is increased, deviations appear mainly within areas containing low-valued noise.

difference
tolerance 0%	tolerance 1%	tolerance 2%

Table 4.5: Cell elimination results

data set	size	toler.	sweep 1	sweep 2	total
hand	$256^2\times 100$	1%	81%	3%	84%
hand	$256^2\times 100$	2%	93%	2%	95%
kidney	$256^2\times 69$	1%	56%	5.5%	61%

Table 4.6: Efficiency of maximum-value evaluation: Column ``cells accessed'' gives the percentage of cells involved in the evaluation process. ``approximations'' is the total number of approximation operations, ``evaluations'' is the percentage of approximated ray intersections which required more exact evaluation. ``pixel set'' is the number of writes to a non-background pixel.

data	image size	cells accessed	approximations	evaluations	pixel set
hand	$465^2$	2.5%	1518k	26%	1.65
hand	$512^2$	4.1%	2439k	27%	1.5
kidney	$465^2$	3.2%	1077k	29%	1.46

Table 4.7: Rendering times for different data sets and image sizes. All data sets have been preprocessed with a 1% tolerance threshold. The timings depend on the used window definition. Some of the resulting images can be seen in figures 4.15d and 4.17a, b. User hardware: PIII/750PC.

data set	size	img size	without preprocessing	with preprocessing
hand	$256^2\times 100$	256$^2$	295ms	215ms
		512$^2$	615ms	450ms
kidney	$256^2\times 69$	256$^2$	180ms	150ms
		512$^2$	350ms	315ms
head	$256^2\times 124$	256$^2$	180ms	170ms
		512$^2$	380ms	365ms

Figure 4.17: a) kidney data set b) head data set

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