Hidden surface removal for \(c\)-oriented polyhedra (Q1194308)

An output-sensitive hidden surface removal algorithm that can deal with cyclic overlap among the objects is given. The method works for any set of polyhedra whose faces have a constant number of different orientations. Let \(n\) be the total number of edges of the polyhedra and \(k\) the complexity of the visibility map. The time complexity of \(O((n+k)\log n)\) improves earlier results on that line. The basic method also works for intersecting polyhedra and for polyhedra, where the number of different orientations of the edges is not bounded. Further results are given and open questions are discussed.