Dynamic output-sensitive hidden surface removal for c-oriented polyhedra
Mark de Berg · 1991
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 ifthe number of different orientations of its edges is bounded by some constant c.) Cyclic overlap in the scene is aJlowed and the polyhedra may even intersect. The time needed for an update is 0 « k + 1) log3 n), where n is the total number of vertices of aJl 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. 1