From: thinman@netcom.com (Technically Sweet) Subject: LECTURE: 7/20/93 Marco Pellegrini Talk at ICSI Date: Wed, 14 Jul 1993 20:06:13 GMT Organization: International Foundation for Internal Freedom The International Computer Science Institute is pleased to present a talk: Tuesday, July 20, 1993 2:00 p.m. MARCO PELLEGRINI Department of Computer Science King's College London, England marcop@icsi.berkeley.edu "Repetitive Hidden-Surface-Removal for Polyhedra" 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+epsilon} <= m <= 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 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 com- posed of unrestricted polyhedra. Preliminary version of this paper will appear in the Proceedings of the 1993 Workshop on Algorithms and Data Structures. This talk will be held in the Main Lecture Hall at ICSI. 1947 Center Street, Sixth Floor, Berkeley, CA 94704 (On Center between Milvia and Martin Luther King Jr. Way) ---------------------------------------------------------- Requests to be added to or deleted from the "talk" mailing list should be directed to talk-request@icsi.Berkeley.EDU. ---------------------------------------------------------- -- Lance Norskog thinman@netcom.com Data is not information is not knowledge is not wisdom.