Figure 2: An example of the cell adjacency graph.
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.