Evaluation of the Maximum

Compared to the other stages of a MIP computation, the evaluation of maximum values within cells (trilinear interpolation) is by far the most expensive part. The reduction of the number and effort of evaluations which are required to generate an image is crucial for the performance. Performance can be improved on the one hand by using a less expensive (but usually also less accurate) evaluation method to approximate the maximum. On the other hand, more evaluations can be omitted if a good guess for the ray-maximum can be found early. The sorted cell-array allows to access and render most promising cells first. If the rendering is started with the projection of cells which have the highest cell maximum (and minimum), the probability of having to evaluate successive cells projected on the same pixels is significantly reduced. As can be seen in table 4.6, only about 2-4% of the cells of the original data set require the use of trilinear interpolation to evaluate their possible contribution to a MIP. The evaluation of the remaining cells is stopped either after checking $C_{max}$ or after performing the slightly more expensive maximum estimation described below.

Values of pixels which are covered by the current cell and which are lower than the cell maximum potentially have to be replaced by a higher value. An analytical solution for the maximum along the ray through the pixel is extremely expensive, and even a few trilinear interpolation steps along the ray are also quite costly. A cheap estimation of an upper bound for the ray maximum which is more restrictive than the cell maximum $C_{max}$ can greatly reduce the number of more costly and exact evaluations of the maximum. The following observations can be used to present such a heuristic:

• If the maximum is located on the entry or exit point of the ray: applying two bilinear interpolations on the entry and exit faces of the cell gives the exact value of the maximum, i.e., $max(entry, exit)$.
• If for this ray the maximum is located within the cell, there must be some positive deviation from a linear evolution between the entry and exit point of the ray. If a cheap approximative guess for this nonlinearity within the cell can be found, the upper-bound of the ray can be estimated as $min(C_{max}, max(entry, exit)+deviation)$.

A fast approximative estimation of this deviation is $deviation=Max(0, Max(v_i+v_j)/2-c)$ with $v_i$, $v_j$ being data values at the vertices located at the ends of the four space-diagonals of the cell and $c$ being the trilinearly interpolated value at the center of the cell (cheap evaluation, as a special case). Although this estimation is not a strict upper bound in all cases (just in about 99% of the cases), no visible impact on images of real-world data sets has been found. On average, this estimation for the ray-maximum within a cell is 30% lower compared with $C_{max}$ as an estimation. When using this estimation about 60% less (of significantly more expensive) trilinear evaluations have to be performed (table 4.6). As only 25-30% of the trilinear evaluations actually lead to a change of a pixel value, a more tight upper bound estimation could gain even more performance. If the estimated upper bound for the ray is above the value of the examined pixel, several steps of trilinear interpolation within the cell are performed utilizing information stored in the templates to obtain the ray maximum.

Projecting high-valued cells first and using an additional estimation of the ray/cell-maximum is very efficient, as the value of each non-background pixel of the image is set only 1.3 to 4 times as compared to 10-25 times for MIP using conventional ray-casting with optimizations.

For the following pseudo-code summary of the projection of the cell array, gray[] stores the mapping from data-values to gray levels as defined by the windowing function.

cells=get_cell_set(viewmatrix); // out of 12 preproc.
calculate_template(viewmatrix);
calculate_projection_arrays(viewmatrix);
for Cmax=highest to 0
  if(gray[Cmax]>0)
    for cell=cells.first_cell_with_Cmax 
           to cells.last_cell_with_Cmax
      project(cell);

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