In this paper we present a new, efficient, output-sensitive method for computing the visibility map of a set of c-oriented polyhedra (polyhedra with their faces and edges having at most c different orientations, for some constant c) as seen from a given viewpoint. For non- intersecting 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. The method can even deal with intersecting polyhedra. In the latter case the algorithm runs in time O((n + k)log2n).