The 3D Visibility Complex:
a unified data-structure for global visibility of scenes of polygons and smooth objects

Frédo Durand, George Drettakis and Claude Puech



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.


gzipped postscript(380 Kb) - PDF