Computer Science – Computational Geometry
Scientific paper
1999-10-21
Computer Science
Computational Geometry
10 pages, many figures; To appear in Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000; See also
Scientific paper
We propose a hybrid image-space/object-space solution to the classical hidden surface removal problem: Given n disjoint triangles in Real^3 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(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.
No associations
LandOfFree
Finite-resolution hidden surface removal does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finite-resolution hidden surface removal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite-resolution hidden surface removal will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-427125