Repetitive Hidden-Surface-Removal for Polyhedra

TitleRepetitive Hidden-Surface-Removal for Polyhedra
Publication TypeTechnical Report
Year of Publication1993
AuthorsPellegrini, M.
Other Numbers820

The repetitive hidden-surface-removal problem can be rephrased as the problem of finding the most compact representation of all views of a polyhedral scene that allows efficient on-line retrieval of a single view. In this paper we present a novel approach to this problem. We assume that a polyhedral scene in 3-space is given in advance and is preprocessed off-line into a data structure. Afterwards, the data structure is accessed repeatedly with view-points given on-line and the portions of the polyhedra visible from each view-point are produced on-line. This mode of operation is close to that of real interactive display systems. The main difficulty is to preprocess the scene without knowing the query view-points.Let n be the number total of edges, vertices and faces of the polyhedral objects and let k be the number of vertices and edges of the image. The main result of this paper is that, using an off-line data structure of size m with n^{1+?} ? m ? n^{2+?}, it is possible to answer on-line hidden-surface-removal queries in time O(k log n + min{n log n, kn^{1+?}/m^{1/2}}), when the scene is composed of c-oriented polyhedra. This data structure accommodates dynamic insertion and deletion of polyhedral objects. The polyhedra may intersect and may have cycles in the dominance relation. We also improve worst-case time/storage bounds for the repetitive hidden surface removal problem when the polyhedral scene is composed of unrestricted polyhedra.Preliminary version of this work is in the Proceedings of the 1993 Workshop on Algorithms and Data Structures.

Bibliographic Notes

ICSI Technical Report TR-93-032

Abbreviated Authors

M. Pellegrini

ICSI Publication Type

Technical Report