The 3D Visibility Complex: a unified data-structure for global visibility

of scenes of polygons and smooth objects In this paper we describe a unified data-structure, the 3D Visibility Complex which encodes the visibility information of a 3D scene of polygons and smooth convex objects. This datastructure is a partition of the maximal free segments and is based on the characterization of the topological changes of visibility along critical line sets. We show that the size k of the complex is Ω(n) and O(n 4) and we give an output sensitive algorithm to build it in time O((n 3 + k)logn). This theoretical work has already been used to define a practical data-structure, the Visibility Skeleton described in a companion paper.