Output-sensitive hidden surface removal
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 598-603
- https://doi.org/10.1109/sfcs.1989.63541
Abstract
Several output-sensitive algorithms for hidden surface removal in a collection of n horizontal triangles, viewed from a point at z=- infinity , are derived. If k is the combinatorial complexity of the output visibility map, then the result is a simple (deterministic) algorithm that runs in time O(n square root k log n) and several improved and more sophisticated algorithms that use randomization. One of these algorithms runs in time O(n/sup 4/3/log /sup gamma /n+k/sup 3/5/n/sup 4/5+ delta /) for any delta >0, where gamma is some constant less than 3. The performance of the other algorithms is potentially even faster; it depends on other parameters of the structure of the given triangles, as well as on the output size. A variant of the simple algorithm performs hidden surface removal for n (nonintersecting) balls in time O(n/sup 3/2/log n+k).Keywords
This publication has 14 references indexed in Scilit:
- An efficient algorithm for hidden surface removalPublished by Association for Computing Machinery (ACM) ,1989
- An efficient output-sensitive hidden surface removal algorithm and its parallelizationPublished by Association for Computing Machinery (ACM) ,1988
- Hidden surface removal for rectanglesPublished by Association for Computing Machinery (ACM) ,1988
- Intersecting line segments, ray shooting, and other applications of geometric partitioning techniquesPublished by Springer Nature ,1988
- Reporting and Counting Intersections Between Two Sets of Line SegmentsPublished by Springer Nature ,1988
- New algorithms for special cases of the hidden line elimination problemComputer Vision, Graphics, and Image Processing, 1987
- Worst-case optimal hidden-surface removalACM Transactions on Graphics, 1987
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstaclesDiscrete & Computational Geometry, 1986
- A fast line-sweep algorithm for hidden line eliminationBIT Numerical Mathematics, 1985
- A Characterization of Ten Hidden-Surface AlgorithmsACM Computing Surveys, 1974