A worst-case efficient algorithm for hidden-line elimination ^†

†This work was carried out under NATO Grant No. RG 155.81; the work of the first and second authors was additicinally supported by a grant from the Deutsche Forschungsgemeinschaft DFG, and the work of the third author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.

Abstract

Many practical algorithms for hidden-line and surface elimination in a 2-dimensional projection of a 3-dimensional scene have been proposed. However surprisingly little theoretical analysis of the algorithms has been carried out. Indeed no non-trivial lower bounds for the problem are known. We present a plane-sweep-based hidden-line-elimination algorithm for 2-dimensional projections of scenes consiting of arbitrary polyhedra. It requires, in the worst case0(n log n) space and 0((n + k) log² n) time, where n is the number of edges in the 3-dimensional scene, and k is the number of edge intersections in the specific projection.

Keywords:

• Hidden line elimination
• computational geometry
• worst case analysis
• computer graphics

C.R. Categories::

• F.2.2 [Geometrical problems and computation]
• 1.3.3 [Display algorithms]

†This work was carried out under NATO Grant No. RG 155.81; the work of the first and second authors was additicinally supported by a grant from the Deutsche Forschungsgemeinschaft DFG, and the work of the third author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.

†This work was carried out under NATO Grant No. RG 155.81; the work of the first and second authors was additicinally supported by a grant from the Deutsche Forschungsgemeinschaft DFG, and the work of the third author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.

Notes

†This work was carried out under NATO Grant No. RG 155.81; the work of the first and second authors was additicinally supported by a grant from the Deutsche Forschungsgemeinschaft DFG, and the work of the third author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.