An efficient, output-sensitive method for computing the visibility map of a set of axis-parallel polyhedra (i.e. polyhedra with their faces and edges parallel to the coordinate axes) as seen from a given viewpoint is introduced. For nonintersecting polyhedra with n edges in total, the algorithm runs in time O((n+k)log n), where k is the complexity of the visibility map. The method can handle cyclic overlap of the polyhedra and perspective views without any problem. For c-oriented polyhedra (with faces and edges in c orientations, for some constant c) the method can be extended to run in the same time bound. The method can be extended even further to deal with intersecting polyhedra with only a slight increase in the time bound.
|Title of host publication||Proceedings 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS, St. Louis MO, USA, October 22-24, 1990)|
|Publisher||Institute of Electrical and Electronics Engineers|
|Number of pages||10|
|Publication status||Published - 1990|