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 data-structure 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 Omega (n) and O(n4) and we give an output sensitive algorithm to build it in time O((n3+k) log n).
This theoretical work has already been used to define a practical data-structure, the Visibility Skeleton described in a companion paper.