Voxel Storage

Figure 4.6: Optimized voxel storage for MIP: relevant voxels are sorted according to data value. Their position in space is stored in an array (as the only individual attribute). The voxels are grouped into RenderListEntrys which hold voxels with identical data values. The data value is stored only once at each RenderListEntry

Voxels which have been classified as relevant during the preprocessing step are extracted from the volume, by storing just their positions into an array. Within the array, voxels are sorted according to data value. After sorting, voxels with the same data value occupy subsequent positions in the array, and can be easily grouped into RenderListEntrys. The data value has to be stored just once for every group (see figure 4.6) at the RenderListEntry. The required sorting of all voxels according to their data value can be performed in linear time, as the limited range of possible data values allows to use histogram-based sorting. The coordinates of each voxel within the volume can be packed into a 32 bit integer, allowing the encoding of volumes of up to $2048\times2048\times1024$ voxels. A straight-forward conversion of a 16 bit/value volume to a 32 bit position representation would mean to double the memory cost. Omitting the voxels which have been marked by the preprocessing step as irrelevant leads to a factor of 0.8 to 1.5 in storage size compared to the original data for direction independent data. For direction-dependent data, approximately one quarter of the original data has to be stored for all 24 view-sets. The overall memory cost for direction dependent preprocessing is thus 12 times higher than the cost of the original volume.

By sorting voxels by value several important advantages for MIP are gained:

• The voxels can be splatted in the order of ascending data values as the array is traversed. Therefore comparing the value of the actual voxel with the screen content is not necessary at all. The value of the actual voxel is always larger or equal to the content of the screen, thus it's projection can be written into the image. Omitting the comparison during projection results in about 10% better performance.
• A general advantage of the voxel list approach is that the array is traversed in the same way independent of the viewing direction. Optimal cache coherency is always achieved. The same code accessing data in a linear way is up to eight times faster than in the case of extremely misaligned access.
• As blood vessels are represented by high data values, lower data values usually contain less important information. If an interactive display of the full data set is not possible on the given hardware, lower intensity values can be simply skipped (see figure 4.7) to achieve interactivity during user interactions. The algorithm can be adjusted to display MIP at an arbitrary frame rate. The number of voxels which can be displayed at a specific frame rate can be easily derived automatically from a performance measurement of the number of voxels which can be rendered per second.
• Instead of directly mapping data values to a linear ramp of gray values for viewing ( $d_{min}\Rightarrow g_{min}$, $d_{max}\Rightarrow g_{max}$), medical data sets are usually viewed using a ``window'' to improve contrast and to focus on certain details. The window is defined by a center value $c$ and a width $w$ which maps all data values below $c-w/2$ to black, all data values above $c+w/2$ to white, and the data in between to a gray ramp. As realistic window functions as used by doctors map significant portions of the data to black, the corresponding parts of the sorted voxel array can be skipped during rendering at almost zero cost. This results in an additional speed-up of up to 500% compared to rendering without windowing under real-world conditions.

Figure 4.7: a) MIP of a head data set (MR), 2.6M voxels. b) Interactive preview of the same data at 10 fps on a P233MMX with approximately 25% of the volume data displayed. Only slight differences are noticeable

(a)	(b)

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