Publication Details
Title: Repetitive Hidden-Surface-Removal for Polyhedra
Author: M. Pellegrini
Group: ICSI Technical Reports
Date: July 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-032.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-032
Bibliographic Reference:
M. Pellegrini. Repetitive Hidden-Surface-Removal for Polyhedra. ICSI Technical Report TR-93-032, July 1993
Author: M. Pellegrini
Group: ICSI Technical Reports
Date: July 1993
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1993/tr-93-032.pdf
Overview:
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 Information:
ICSI Technical Report TR-93-032
Bibliographic Reference:
M. Pellegrini. Repetitive Hidden-Surface-Removal for Polyhedra. ICSI Technical Report TR-93-032, July 1993