TIME AND SPACE BOUNDS FOR HIDDEN LINE AND HIDDEN SURFACE ALGORITHMS

Simple item page
dc.contributor.authorSchmitt, Alfreden_US
dc.contributor.editorJ. L. Encarnacaoen_US
dc.date.accessioned2015-09-29T08:26:11Z
dc.date.available2015-09-29T08:26:11Z
dc.date.issued1981en_US
dc.description.abstractAsymptotic 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.en_US
dc.description.seriesinformationEurographics Conference Proceedingsen_US
dc.identifier.doi10.2312/eg.19811005en_US
dc.identifier.issn1017-4656en_US
dc.identifier.urihttps://doi.org/10.2312/eg.19811005en_US
dc.publisherThe Eurographics Associationen_US
dc.titleTIME AND SPACE BOUNDS FOR HIDDEN LINE AND HIDDEN SURFACE ALGORITHMSen_US
Files
Collections
EG1981 Proceedings (Technical Papers)