VISIBILITY ORDERING MESHED POLYHEDRA

A visibility ordering of a set of objects from some viewpoint is an ordering such that if object a obstructs object b, then b precedes a in the ordering. An algorithm is presented that generates a visibility ordering of an acyclic convex set of meshed convex polyhedra. This algorithm takes time linear in the size of the mesh. Modifications to this algorithm and/or preprocessing techniques are described that permit nonconvex cells, nonconvex meshes (meshes with cavities and/or voids), meshes with cycles, and sets of disconnected meshes to be ordered. Visibility ordering of polyhedra is applicable to scientific visualization, particularly direct volume rendering. It is shown how the ordering algorithms can be used for domain decomposition of finite element meshes for parallel processing, and how the data structures used by these algorithms can be used to solve the spatial point location problem. The effects of cyclically obstructing polyhedra are discussed and methods for their elimination are described, including the use of the Delaunay triangulation. Methods for converting nonconvex meshes into convex meshes are described.