TIME AND SPACE BOUNDS FOR HIDDEN LINE AND HIDDEN SURFACE ALGORITHMS

Abstract

Asymptotic worst case time bounds for three hidden line algorithms are derived and analysed. The first algorithm is a brute force solution that needs at least quadratic time. The second exact hidden line algorithm is based on a classical divide and conquer strategy similar to Warnock's algorithm and the third one is completely new and uses a plane sweep. The last two algorithms need time between O(n log n) and O(n²log n) depending on properties of the class of 3D scenes used. A variant of the divide and conquer algorithm processes a suitable class of 3D scenes in linear time. These results clearly demonstrate, that the asymptotic time needed to eliminate hidden lines depends almost exclusively on properties of the scene and not so much on the cleverness of the algorithm.