The spatial subdivision of the MVE is constructed incrementally based
on the binary space partitioning. The *root cell* corresponds to
the convex hull of the model. This cell is divided selecting the
largest *occluder* along which a splitting plane is introduced,
until no more candidates exist. The selection of the largest
occluder in the current cell should prevent its descendants from
``seeing'' each other. In the current heuristics only polygons larger
than some threshold are treated as occluders, assuming that all the other
polygons form *detail-objects*. This choice makes the final
cells of the subdivided model roughly correspond to actual rooms of
the virtual environment. Thus, the spatial subdivision uses data
structure known as BSP tree to store the intermediate results. The
cell *boundaries* are created explicitly at each step of the
spatial subdivision algorithm. When the spatial subdivision
terminates the *portal* enumeration is invoked. The portals are
computed as a convex hull of the set difference of the cell
boundaries and the union of occluders coaffine to each particular
boundary.

In order to preserve information about the spatial subdivision, the
cell *adjacency graph* is created (see 2). Informally,
the adjacency graph is a multi-graph structure, where nodes correspond
to cells (leaves of the BSP tree) and where two cells are connected
with an edge, if they share a portal on their common boundary. Thus
edges of the adjacency graph correspond to the portals between cells
of the spatial subdivision.

**Figure 2:** An example of the cell adjacency graph.

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