A simple output-sensitive algorithm for hidden surface removal
Micha Sharir, Mark H. Overmars · ACM Transactions on Graphics · 1992
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).