Merging visibility maps

Publisher Website
Google Scholar
Abstract
Let V be a set of objects in space for which we want to determine the portions visible from a particular point of view &ugr;. Assume V is subdivided in subsets V1,…, Vz and the visibility maps &Mgr;1, … &Mgr;z of these subsets from point ugr; are known. We show that the visibility map &Mgr; for V can be computed by merging &Mgr;1, … &Mgr;z in time &Ogr;((n + &kgr;)z log2 n) where n is the total size (number of edges, vertices and faces) of the visibility maps &Mgr;1,…, &Mgr;z and &kgr; is the size of &Mgr;. This result has important applications e.g. in animation where objects move with respect to a fixed environment. It also leads to efficient algorithms for special cases of the hidden-surface removal problem. For example, we obtain a method for hidden surface removal in a set of unit spheres, viewed from infinity, that runs in time &Ogr;((n + &kgr;) log2 n).

This publication has 0 references indexed in Scilit: