The cell-to-cell visibility preprocessing and query algorithms for 2D axial floor-plans (presented at SIGGRAPH '91) have been extended to cell-to-object visibility in 3D polyhedral environments, and an efficient implementation for 3D axial environments is demonstrated on a fully furnished architectural floor model with 250,000 polygons.
The building is subdivided along the major walls into cells, connected through transparent portals. During preprocessing, cell-to-cell visibility is established for all cell pairs connected by at least one sight line through the intervening portals. Even for a source cell containing a generalized observer, often only a small portion of other cells is visible. Only objects whose bounding boxes intersect these "visible volumes" become part of the cell-to-object visibility set of the source cell.
In the real-time walk-through simulation, cell-to-object visibility is further pruned with the view frustum from the observer's current position, and only the remaining objects, which still form an uncompromised superset of the truly visible polygons, are sent to the renderer. In our architectural floor model, this process removed on average about 95% of all polygons, and accelerated rendering speed by about a factor of seventeen.
Visibility Computations in Polyhedral Three-Dimensional Environments
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
The Engineering Library
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).