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

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.