Visibility Computations in Polyhedral Three-Dimensional Environments

Seth J. Teller and Carlo H. Séquin

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-92-680
April 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-680.pdf

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.


BibTeX citation:

@techreport{Teller:CSD-92-680,
    Author = {Teller, Seth J. and Séquin, Carlo H.},
    Title = {Visibility Computations in Polyhedral Three-Dimensional Environments},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1992},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6128.html},
    Number = {UCB/CSD-92-680},
    Abstract = {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. <p>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. <p>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.}
}

EndNote citation:

%0 Report
%A Teller, Seth J.
%A Séquin, Carlo H.
%T Visibility Computations in Polyhedral Three-Dimensional Environments
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-680
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6128.html
%F Teller:CSD-92-680