An exact interactive time visibility ordering algorithm for polyhedral cell complexes

Abstract

A visibility ordering of a set of objects, from a given viewpoint, is a total order on the objects such that if object a obstructs object b, then b precedes a in the ordering. Such order-ings are extremely useful for rendering volumetric data. We present an algorithm that generates a visibility ordering of the cells of an unstructured mesh, provided that the cells are convex polyhedra and nomntersecting, and that the visibility ordering graph does not contain cycles. The overall mesh may be nonconvex and it may have disconnected components. Our technique employs the sweep paradigm to determine an ordering between pairs of exterior (mesh boundary) cells which can obstruct one another. It then builds on Williams' MPVO algorithm [33] which exploits the ordering implied by adjacencies within the mesh. The partial ordering of the exterior cells found by sweeping is used to augment the DAG created in Phase II of the MPVO algorithm. Our method thus removes the assumption of the MPVO algorithm that the mesh be convex and connected, and thereby allows us to extend MPVO algorithm, without using the heuristics that were originally suggested by Williams (and are sometimes problematic). The resulting XMPVO algorithm has been analyzed, and a variation of it has been implemented for unstructured tetrahedral meshes; we provide experimental evidence that it performs very well in practice.