In this research paper, the author describes an algorithm for visibility-ordering the cells of any acyclic convex set of meshed convex polyhedra. Organized in 12 sections, the paper presents the theory and implementation of the meshed polyhedra visibility ordering (MPVO) algorithm. A summary of the paper and a discussion of some algorithms that are not suitable for visibility-ordering large meshes or that have a high complexity are given in the introduction. Section 2 presents an overview of the MPVO algorithm. Preliminary definitions are given in Section 3. Section 4 presents a formal description of the MPVO algorithm, while implementation details are discussed in Section 5. The complexity analysis is given in Section 6. Williams shows that this algorithm orders the cells of a mesh in linear time using linear storage.
The rest of the paper illustrates some applications of this algorithm. An important part of the paper is dedicated to preprocessing techniques and to modifications to the MPVO algorithm that permit nonconvex cells, nonconvex meshes, meshes with cycles, and the set of disconnected meshes to be ordered. For instance, sections 8 and 9, using Delaunay triangulation, describe the effects of cyclically obstructing polyhedra and present methods for elimination of these effects and for converting nonconvex meshes into convex meshes.
The algorithms presented in this work can be used in scientific visualization (direct volume rendering and volume visualization) and for domain decomposition of finite element meshes for parallel processing (covered in Section 10). Section 11 shows how the spatial point location problem can be solved using the data structures for the MPVO algorithm. The low complexity of this algorithm recommends it for use in three-dimensional graphics and realism. The paper is long, but the author presents this subject clearly. In order to understand this algorithm, some background in computational geometry and topological sort methods is needed.
A bibliography of 43 references is presented; all of them are cited in the text.
