TIME AND SPACE BOUNDS FOR HIDDEN LINE AND HIDDEN SURFACE ALGORITHMS

Thumbnail Image
Date
1981
Authors
Schmitt, Alfred
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
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.
Description

        
@inproceedings{
10.2312:eg.19811005
,
booktitle = {
Eurographics Conference Proceedings
},
editor = {
J. L. Encarnacao
},
title = {{
TIME AND SPACE BOUNDS FOR HIDDEN LINE AND HIDDEN SURFACE ALGORITHMS
}},
author = {
Schmitt, Alfred
},
year = {
1981
},
publisher = {
The Eurographics Association
},
ISSN = {
1017-4656
},
ISBN = {},
DOI = {
10.2312/eg.19811005
}
}
Citation
URI
https://doi.org/10.2312/eg.19811005
Collections
EG1981 Proceedings (Technical Papers)