We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If k is the combinatorial complexity of the output visibility map , the method runs in time O(n √k log n). The method is extended to work for other classes of objects as well, sometimes with even improved time bounds. For example, we obtain an algorithm that performs hidden surface removal for n (nonintersecting) balls in time O(n 3/2 log n + k).
No takes yet. Share an insight, caveat, or question.
Sharir et al. (1992) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: