Octree-based Volumetric Visualization

This paper deals with the problem of displaying 3-dimensional
objects represented using linear octree, and offers a new and
efficient solution.
Octree is the most common data
structure used to model 3-dimensional geological features in
Geographic Information System.
Linear octree is a compact representation of octree.
Combining polygon scan-conversion with front to back traversal of
polygons in three-dimensional space result in significant improvement
of display algorithms, because it avoids re-computation of color value
of any pixel on screen.
Our algorithm provides an $O(N\log~N)$
solution to rearrange voxels of the linear octree in order of
increasing distance from the viewer.
Using this order, the voxels in
the octree are traversed in front-to-back manner and the visible faces
of the voxels are scan-converted.
Since all the voxels of the octree are of similar shape and equal
size, area coherence is used by the scan conversion routine to avoid
expensive floating point computations. This improves the overall
performance of the algorithm. Our algorithm has been implemented on a
X Window platform and gives reasonable result on a 386 class machine.