article · ACM Transactions on Graphics · 1992

A simple output-sensitive algorithm for hidden surface removal

Cited by 46Open access

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(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).

Cite this paper

APA 7

Sharir, M., & Overmars, M. H. (1992). A simple output-sensitive algorithm for hidden surface removal. ACM Transactions on Graphics, 11(1), 1–11. https://doi.org/10.1145/102377.112141

MLA 9

Sharir, Micha, and Mark H. Overmars. “A simple output-sensitive algorithm for hidden surface removal.” ACM Transactions on Graphics, vol. 11, no. 1, 1992, pp. 1–11, https://doi.org/10.1145/102377.112141.

Chicago

Sharir, Micha, and Mark H. Overmars. 1992. “A simple output-sensitive algorithm for hidden surface removal.” ACM Transactions on Graphics 11 (1): 1–11. https://doi.org/10.1145/102377.112141.

Harvard

Sharir, M. and Overmars, M.H. (1992) ‘A simple output-sensitive algorithm for hidden surface removal’, ACM Transactions on Graphics, 11(1), pp. 1–11. Available at: https://doi.org/10.1145/102377.112141.

BibTeX

@article{sharir1992simple,
  title = {{A simple output-sensitive algorithm for hidden surface removal}},
  author = {Sharir, Micha and Overmars, Mark H.},
  journal = {ACM Transactions on Graphics},
  volume = {11},
  number = {1},
  pages = {1--11},
  year = {1992},
  doi = {10.1145/102377.112141}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.