Figure 3: Potentially visible frustrum induced by the sequence of four portals. The extremal stabbing lines are marked as well.
The cell-to-cell visibility relation is based on the observation, that to see one cell from another an unobscured sightline between them must exist. The cell-to-cell visibility computation is performed as constrained depth first search on the adjacency graph. The existence of a sightline is established by involving the stabbing line algorithm for sequences of portals. This task is solved by transforming portal edges to Plücker coordinates (see e.g. [Tel92]), which suitably parameterize lines in 3D and involving six dimensional linear programming task. Furthermore the cell-to-frustrum visibility is determined. The computation of the potentially visible frustrum induced by the portal sequence is based on conservative approximation of the antipenumbra, when treating the first portal of the sequence as an areal light-source. The algorithm uses mapping to Plücker coordinates again and invokes the five dimensional convex polyhedra enumeration to produce a set of extremal stabbing lines. Some more computations are performed to conservatively approximate the potentially visible regions (see figure 3). We store the information about visibility relations using the extension of the Virtual Reality Modeling Language (VRML) file format, which is described in [Tre96].
Figure 3: Potentially visible frustrum induced by the sequence of four portals. The extremal stabbing lines are marked as well.