Cell Storage

In the following, the vertex coordinates $(x,y,z)=(min(x_i),min(y_i),min(z_i))$, with $(x_i,y_i,z_i)$ being the eight vertices of a cell, will be used as reference coordinates of a cell.

Cells which have been identified during preprocessing as relevant cells are extracted from the volume and stored into a similar RenderList structure as described in section 4.1.2. Cells are sorted according to descending cell-maximum ($C_{max}$) values within the cell array. For every cell its reference coordinates are stored into the corresponding 32 bit entry in the array. $C_{max}$ is stored as the key attribute at RenderListEntrys.

Using this alternative storage scheme, it is trivial to start MIP with high-valued cells. Speed-up factors of 10-20 compared to other optimized high-quality MIP approaches [5,51,67] are gained by just this part of the approach, in combination with the usual optimizations like evaluating only cells with $C_{max}>$current ray maximum, and noise skipping (see table 4.3, row 3 for detailed results).

Although sorting all cells by $C_{min}$ would most effectively reduce the number of interpolations required, sorting them by $C_{max}$ has several advantages. The encoding of $C_{max}$ in the RenderListEntry allows to access it in an efficient way for testing a cell's relevance during projection. Within a group of cells with the same $C_{max}$ sub-sorting is done according to descending $C_{min}$. Due to the small range of different values, sorting by $C_{max}$ and $C_{min}$ can be done using fast histogram-based sorting (complexity $O(N)$). During projection, cells with high $C_{max}$ and $C_{min}$ are processed first.

The chosen cell order is also well-suited for efficiently skipping cells which have been mapped to black due to windowing. If cells are sorted by $C_{max}$ and rendering is started with highest values of $C_{max}$, rendering can be stopped after reaching the first cell with $C_{max}$ mapped to black. For realistic window definitions (as used by medical doctors) this can significantly speed up the rendering (up to several times faster).

In addition to the fast computation of MIP due to re-sorting, another big advantage is gained: progressive refinement is achieved automatically, as cells which are most relevant to MIP are projected first. Projection can be stopped any time - the result will always be optimal for the given time-constraints. Also, computation of cheap previews is simple. Since interaction is crucial for using MIP, this advantage is also very important for practical use.

In the following a rough comparison between the traditional way of volume storage and the RenderList-based representation of cells is given: Storing the position instead of data values doubles the amount of memory required. As roughly 30% of all cells remain after the preprocessing step (cell removal), the amount of memory required is about 0.6 * original volume size (per cluster of viewing directions). For 12 clusters this results in an approximately sevenfold increase in memory size compared with the original data set. Considering data sets from medical applications and regular hardware resources, the storage requirements are high, but acceptable. If, nevertheless, the memory resources are a limiting factor, the data set can also be transformed into a single cell array without prior view-dependent preprocessing. This, of course, slightly increases rendering time (see table 4.7), but still gains results significantly faster than conventional approaches of comparable image quality, while requiring just twice as much memory as the original data set.

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