Hidden surface removal for axis-parallel polyhedra

M. Berg, de, M.H. Overmars

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


    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.
    Original languageEnglish
    Title of host publicationProceedings 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS, St. Louis MO, USA, October 22-24, 1990)
    PublisherInstitute of Electrical and Electronics Engineers
    Number of pages10
    ISBN (Print)0-8186-2082-X
    Publication statusPublished - 1990


    Dive into the research topics of 'Hidden surface removal for axis-parallel polyhedra'. Together they form a unique fingerprint.

    Cite this