ISSN:
1436-5057
Keywords:
51N20
;
68-04
;
68C05
;
68C25
;
Visible surface algorithms
;
computational geometry
;
computer graphics
;
computational complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Das Visible-Surface-Problem besteht darin, die Teilpolygone einer 3-D-Szene aus beliebigen einfachen planaren Polygonen zu bestimmen, die von einem gegebenen Augenpunkt aus sichtbar sind. Der Algorithmus der hier vorgestellt wird, und der für umfangreiche Szenen ausgelegt ist, löst dieses Problem durch implizites Zerlegen bezüglich eines Zellrasters. Die Komplexitätsabschätzung führt zu Aussagen über die günstige Wahl des Gitters und zu der Charakterisierung von Szenenklassen, welche bei praktischen Anwendungen auftreten, und für die der Algorithmus ein lineares Zeit- und Speicherplatzverhalten zeigt.
Notes:
Abstract The visible surface problem is to determine those subpolygons of a 3-D scence of arbitrary simple planar polygons which are visible from a given viewpoint. The algorithm which is presented here, and which is designed for complex scenes solves this problem by an implicit partitioning w.r.t. a raster of cells. The estimation of complexity leads to propositions on the favorable choice of the grid, and to the characterization of classes of scenes, which are relevant for practical applications, and for which the algorithm shows a linear time and space behavior.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02240191
Permalink