00902869

j

00902869 de Berg, Mark Generalized hidden surface removal. Comput. Geom. 5, No.5, 249-276 (1996). 1996 Elsevier Science B.V. (North-Holland), Amsterdam EN hidden surface removal problem

doi:10.1016/0925-7721(95)00008-9

Summary: We study the following generalization of the classical hidden surface removal problem: given a set $S$ of objects, a view point and a point light source, compute which parts of the objects in $S$ are visible, subdivided into parts that are lit and parts that are not lit. We prove tight bounds on the maximum combinatorial complexity of such views and give efficient output-sensitive algorithms to compute the views for three cases: (i) $S$ consists of non-intersecting triangles, (ii) $S$ consists of horizontal axis-parallel rectangles, (iii) $S$ is the set of faces of a polyhedral terrain.