Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
REPETITIVE HIDDEN SURFACE REMOVAL FOR POLYHEDRA
Autore:
PELLEGRINI M;
Indirizzi:
CNR,IST MATEMAT COMPUTAZ,VIA SANTA MARIA 46 I-56126 PISA ITALY
Titolo Testata:
Journal of algorithms
fascicolo: 1, volume: 21, anno: 1996,
pagine: 80 - 101
SICI:
0196-6774(1996)21:1<80:RHSRFP>2.0.ZU;2-#
Fonte:
ISI
Lingua:
ENG
Soggetto:
ASPECT GRAPH; ALGORITHMS; OBJECTS; 3-SPACE;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
CompuMath Citation Index
Science Citation Index Expanded
Science Citation Index Expanded
Citazioni:
36
Recensione:
Indirizzi per estratti:
Citazione:
M. Pellegrini, "REPETITIVE HIDDEN SURFACE REMOVAL FOR POLYHEDRA", Journal of algorithms, 21(1), 1996, pp. 80-101

Abstract

The repetitive hidden-surface-removal problem can be rephrased as theproblem of finding the most compact representation of all views of a polyhedral scene that allows efficient on-line retrieval of a single view. We assume that a polyhedral scene in 3-space is given in advance and is preprocessed off-line into a data structure. Afterward, the data structure is accessed repeatedly with viewpoints given on-line and the portions of the polyhedra visible from each viewpoint 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 withoutknowing the query viewpoints. In this paper, we present a novel approach to this problem. Let n be the total number 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+epsilon) less than or equalto m less than or equal to n(2+epsilon), it is possible to answer on-line hidden-surface-removal queries in time O(k log n + min{n log n, kn(1+epsilon/)m(1/2)}) when the scene is composed of c-oriented polyhedra. This data structure allows 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 and storage boundsfor the repetitive hidden surface removal problem when the polyhedralscene is composed of unrestricted polyhedra. (C) 1996 Academic Press,Inc.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 04/07/20 alle ore 14:02:50