Fast Polyhedral Cell Sorting for Interactive Rendering of Unstructured Grids

Direct volume rendering based on projective methods works by projecting, in visibility order, the polyhedral cells of a mesh onto the image plane, and incrementally composting the cell's color and opacity into the final image. Traditionally, there has been a big performance gap between approximate visibility sorting techniques and exact solutions. While approximate solutions provide reasonable results for "well-behaved" datasets, the artifacts they induce increase with the presence of non-convex boundaries, and "badly-shaped" cells.

Recently, Silva et al described XMPVO, a fast algorithm based on an extension of the MPVO algorithm. They showed it is possible to generalize Williams' MPVO algorithm, and remove the requirement that the mesh be convex and connected. It is shown to be several orders of magnitude faster than previous "exact" techniques.

In this paper we propose a new technique, BSP-XMPVO, which is based on XMPVO but almost two orders of magnitude faster. We get this speed-up by replacing XMPVO's view-dependent augmentation with a view-independent pre-processing phase, essentially composed of a BSP tree generation of the exterior faces of the boundary cells. With this new technique, approximate solutions are no longer required to achieve interactive speeds.