Abstract
In this paper 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.
Original language | English |
---|---|
Pages (from-to) | 249-276 |
Number of pages | 28 |
Journal | Computational Geometry |
Volume | 5 |
Issue number | 5 |
DOIs | |
Publication status | Published - 1996 |