HIERARCHICAL ENUMERATION

The Hierarchical Enumeration ([6]) bases on the fact, that normally a high percentage of volume data is empty. Therefore as large as possible empty regions are grouped together and ignored during rendering. A region is empty if it contains only voxels with a opacity of 0. A binary volume pyramid is used for this, where a node contains a 0, if the represented section is empty, else 1. The pyramid is constructed by replacing 8 voxels by 1 voxel. This new voxel gets the value 1, if the value of one of the replaced voxels is not equal 0, which means the subvolume is not empty, otherwise 0. For the construction of the base level is the opacity from the original volume data used.

Construction of a binary volume pyramid
Construction of a binary volume pyramid

This algorithm is used for raycasting. For rendering you calculate the first intersection between the volume and the ray. Since the higher level of the binary pyramid normally contains many or only a 1 it is more efficient to start the traversal some levels below the top level. The traversal starts at the node in the starting level which is first intersected by the ray. The value of a node is checked, if the node contains a zero, the node is ignored and you move along the ray and check the next node on the same level, which is intersected. If the last checked cell and the new cell have different parents, we move up the pyramid to this parent and continue. If a checked node contains a 1, we move down and continue. Every time we find a node (cell) at the base level which is 1, this cell is used for rendering, which means the portion of the ray within this cell is used for resampling.
 

Raycasting with hierarchical enumeration
Raycasting with hierarchical enumeration
 
The Hierarchical Enumeration speeds up the rendering with a factor of 2 - 5, depending on the data, and has the advantage that the acceleration has no influence on the rendering quality.
 
Density of rays for hierarchical enumeration
 
Ray density for raycasting with and without hierarchical enumeration

This approach is also used for a hybrid raytracer ([5]), which renders both polygon and volume data without converting one data type into another.

 

 Main Page