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 I56126 PISA ITALY
 Titolo Testata:
 Journal of algorithms
fascicolo: 1,
volume: 21,
anno: 1996,
pagine: 80  101
 SICI:
 01966774(1996)21:1<80:RHSRFP>2.0.ZU;2#
 Fonte:
 ISI
 Lingua:
 ENG
 Soggetto:
 ASPECT GRAPH; ALGORITHMS; OBJECTS; 3SPACE;
 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. 80101
Abstract
The repetitive hiddensurfaceremoval problem can be rephrased as theproblem of finding the most compact representation of all views of a polyhedral scene that allows efficient online retrieval of a single view. We assume that a polyhedral scene in 3space is given in advance and is preprocessed offline into a data structure. Afterward, the data structure is accessed repeatedly with viewpoints given online and the portions of the polyhedra visible from each viewpoint are produced online. 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 offline 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 online hiddensurfaceremoval queries in time O(k log n + min{n log n, kn(1+epsilon/)m(1/2)}) when the scene is composed of coriented 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 worstcase 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