Finite-resolution hidden surface removal

Research output: Contribution to conferencePaper


We propose a hybrid image-space/object-space solution to the classical hidden surface removal problem: Given n disjoint triangles in R3 and p sample points (`pixels') in the xy-plane, determine the first triangle directly behind each pixel. Our algorithm constructs the sampled visibility map of the triangles with respect to the pixels, which is the subset of the trapezoids in a trapezoidal decomposition of the analytic visibility map that contain at least one pixel. The sampled visibility map adapts to local changes in image complexity, and its complexity is bounded both by the number of pixels and by the complexity of the analytic visibility map. Our algorithm runs in time O(n1+ε+n2/3+εt2/3+p), where t is the output size. This is nearly optimal in the worst case and compares favorably with the best output-sensitive algorithms for both ray casting and analytic hidden surface removal. In the special case where the pixels form a regular grid, a sweepline variant of our algorithm runs in time O(n1+ε+n2/3+εt2/3+t log p), which is usually sublinear in the number of pixels.

Original languageEnglish (US)
Number of pages9
StatePublished - Jan 1 2000
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000


Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA


ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Erickson, J. (2000). Finite-resolution hidden surface removal. 901-909. Paper presented at 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, .