Visible surface calculation for complex unstructured polygonal scenes (Q1059281)

The visible surface problem is to determine those subpolygons of a 3-D scene of arbitrary simple planar polygons which are visible from a given viewpoint. The algorithm which is presented here, and which is designed for complex scenes solves this problem by an implicit partitioning w.r.t. a raster of cells. The estimation of complexity leads to propositions on the favorable choice of the grid, and to the characterization of classes of scenes which are relevant for practical applications, and for which the algorithm shows a linear time and space behavior.