ZSWEEP: An Efficient and Exact Projection Algorithm for Unstructured Volume Rendering

We present a simple new algorithm that performs fast and memory-efficient cell projection for (exact) rendering of unstructured datasets. The main idea of the "ZSweep" algorithm is very simple; it is based on sweeping the data with a plane parallel to the viewing plane, in order of increasing z, projecting the faces of cells that are incident to vertices as they are encountered by the sweep plane. The efficiency arises from the fact that the algorithm exploits the implicit (approximate) global ordering that the z-ordering of the vertices induces on the cells that are incident on them. The algorithm projects cells by projecting each of their faces, with special care taken to avoid double projection of internal faces and to assure correctness in the projection order. The contribution for each pixel is computed in stages, during the sweep, using a short list of ordered face intersections, which is known to be correct and complete at the instant that each stage of the computation is completed. The ZSweep algorithm is simple enough to be readily adaptable to general (non-tetrahedral) cell formats. It is memory efficient, since its auxiliary data structures have only to store partial information taken from a small number of "slices" of the dataset. We also introduce a simple technique of data sparsification, which may be of interest in its own right. Our implementation is hardware-independent and handles datasets containing tetrahedral and/or hexahedral cells. We give experimental evidence that our method is competitive, up to 5 times faster than the best previously-known exact algorithms that use comparable amounts of memory, while using much less memory than ray-casting.