An efficient algorithm for hidden surface removal, II

摘要

We give an efficient, randomized hidden surface removal algorithm for scenes containing intersecting faces. Randomization is assumed only in the algorithm and not in the input. The algorithm is quasi-output sensitive in the following sense. Project all boundary edges as well as the edges formed by the intersections of scene faces onto the view plane. This gives rise to several junctions in the view plane, visible as well as invisible. Let us define the degree deg(q) of a junction q as the number of scene faces that give rise to q. Define l(q), the obstruction level of q, to be the number of faces in the scene that obscure q with respect to the view point. Thus l(q)=0 iff q is visible. Then the expected time spent by the algorithm on a junction q is inversely proportional to (1 + l(q))deg(q)−1. Thus the work done on a junction decreases very fast as its obstruction level w.r.t. the view point increases.