Dynamic output-sensitive hidden surface removal for c-oriented polyhedra

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    De Berg, M., Dynamic output-sensitive hidden surface removal for c-oriented polyhedra, Computational Geometry: Theory and Applications 2 (1992) 119–140. In this paper we present an output-sensitive algorithm to maintain the view of a set of c-oriented polyhedra under insertions into or deletions from the set. (A set of polyhedra is c-oriented if the number of different orientations of its edges is bounded by some constant c.) Cyclic overlap in the scene is allowed and the polyhedra may even intersect. The time needed for an update is O((k + 1)log3 n), where n is the total number of vertices of all polyhedra and k is the number of changes in the visibility map. The solution is based on new dynamic data structures for ray shooting and range searching problems for c-oriented objects.
    Original languageEnglish
    Pages (from-to)119-140
    Number of pages22
    JournalComputational Geometry
    Volume2
    Issue number3
    DOIs
    Publication statusPublished - 1992

    Fingerprint

    Dive into the research topics of 'Dynamic output-sensitive hidden surface removal for c-oriented polyhedra'. Together they form a unique fingerprint.

    Cite this