A Simple Output-Sensitive Algorithm for Hidden Surface Removal
Micha Sharir, Mark H. Overmars
In ACM Transactions on Graphics, 11(1), January 1992.
Abstract: 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(nk 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(n3/2log n+k) .
@article{Sharir:1992:ASO,
author = {Micha Sharir and Mark H. Overmars},
title = {A Simple Output-Sensitive Algorithm for Hidden Surface Removal},
journal = {ACM Transactions on Graphics},
volume = {11},
number = {1},
pages = {1--11},
month = jan,
year = {1992},
}
Return to the search page.
graphbib: Powered by "bibsql" and "SQLite3."