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.

Jiri Bittner - bittner@sgi.felk.cvut.cz