Figure 1: An example of the spatial subdivision in three dimensions. Different cells are shown in different colors.
Given a model of virtual environment, we attempt to subdivide it into smaller discrete parts called cells. Each cell is a convex polyhedral volume. When the spatial subdivision is completed, the portal enumeration is performed to find transparent polygonal regions upon the cell boundaries which connect adjacent cells. Obviously, the observer can see from one cell to another through portals on their shared boundary and to the more distant cells through portal sequences. In densely occluded environments, such as architectural models, cell boundaries often follow walls and partitions, so cells roughly correspond to rooms of the environment. The portals likewise correspond to doors and windows through which neighboring rooms are connected. Entities of the spatial subdivision, these are cells, boundaries and portals, together with their topological connections are represented by the adjacency graph. For each cell in the adjacency graph we determine a set of potentially visible regions. A hierarchical data structure - the visibility tree is used to store the visibility information. The root node of the tree corresponds to the source cell, which is actually the cell the tree is built for. The tree structure stores the cell-to-cell visibility relation, defining the order in which the cells are visited along sightline from the root cell (see figure 4). The visibility tree can be further extended to hold information about the cell-to-frustrum visibility, which estimates the potentially visible regions induced by the portal sequences. Using the static visibility relations several dynamic queries can be formulated, to find a tight superset of objects visible to the observer, knowing observer's location and viewing direction.
Figure 1: An example of the spatial subdivision in three dimensions. Different cells are shown in different colors.