Abstract:
We propose a hybrid image-space/object-space solution to the classical hidden surface
removal problem: Given a set of n triangles in R^{3} and a set of
p sample points (``pixels'') in the xy-plane, determine which triangle is
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(n^{1+e}
+ n^{2/3+e}t^{2/3}
+ p),
where t is the output size and e is any positive constant. 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(n^{1+e}
+ n^{2/3+e}t^{2/3}
+ t log p),
which is usually sublinear in the number of pixels.