Visibility-ordering meshed polyhedra
- 1 April 1992
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 11 (2) , 103-126
- https://doi.org/10.1145/130826.130899
Abstract
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.Keywords
This publication has 26 references indexed in Scilit:
- Incremental topological flipping works for regular triangulationsPublished by Association for Computing Machinery (ACM) ,1992
- Tetrahedrizing point sets in three dimensionsJournal of Symbolic Computation, 1990
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithmsACM Transactions on Graphics, 1990
- The implementation of an algorithm to find the convex hull of a set of three-dimensional pointsACM Transactions on Graphics, 1990
- Triangulating a non-convex polytypePublished by Association for Computing Machinery (ACM) ,1989
- Volume renderingACM SIGGRAPH Computer Graphics, 1988
- Three dimensional mesh generation by triangulation of arbitrary point setsPublished by American Institute of Aeronautics and Astronautics (AIAA) ,1987
- How to search in historyInformation and Control, 1985
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal AlgorithmSIAM Journal on Computing, 1984
- The A -buffer, an antialiased hidden surface methodACM SIGGRAPH Computer Graphics, 1984