An Overview

In the previous section, we saw how Q3Map2's BSP process broke the map down into convex volumes, placing portals between them, and indexed the entire process into the BSP-tree. The second part of a compile process is the VIS stage, where visibility between portals is determined and stored in a Potentially Visible Set table (or PVS-table). As mentioned, it is simple and fast to determine whether two convex volumes can see one another.

Q3Map2's VIS stage takes each portal at a time and checks direct line of sight between it and every other portal in the map. If two portals are determined that they can see each other without passing though stuructural brushes, all the leaf-nodes between them are marked as visible. If two portals are occluded from one another by a structural brush, then everything beyond the portal is hidden.

Once Q3Map2 has predetermined visibility of all the portals between convex volumes, the game engine at run-time looks at the leaf-node that the player is standing in, and compares it to the PVS-table to see all the leaf-nodes that the player can potentially look into. This forms a group of leaf-nodes that make up the player's current PVS, and everything beyond the PVS is culled.

Generating the PVS-Table

To illustrate how Q3Map2's VIS process works, we'll continue with our simplified 2-D example from the previous section. To recap, the BSP process took our map and broke it down into convex volumes, represented on the BSP-tree as leaf-nodes. The segments between the leaf-nodes are portals.

The BSP process stores all the portal information in a temporary .prt file. The VIS process reads the .prt file and uses it to calculate visibility between portals. You can prevent VIS from deleting this file with the -saveprt switch. This is useful later when we talk about hint brushes.

The PVS-table records whether or not each portal has line of sight with all the other portals in the map. Note that if one portal can see a second portal, then the same is true vice-versa. There is no need to index everything twice. Additionally, a portal never needs to index itself. The empty PVS-table is illustrated on the right next to our map.

Let's take a single portal (D) and check its visibility with all the other portals. If it can at least partially see another portal, it gets a check in the PVS-table. If the other portal is completely obscured by structural brushes, then it gets a cross. With each visibility trace, the VIS stage starts to populate the PVS-table.

The process continues with each portal in turn, checking it with the visibility of every other portal in the map until the PVS-table is completely filled out. This ends Q3Map2's VIS process, the PVS-table is saved to the .bsp map file and the .prt file is by default deleted.

The PVS-Table at Run-Time

Now that Q3Map2 has our map compiled with both BSP and VIS stages, we can take a look at what happens when we run the map and how the engine reads the PVS-table to determine visibility.

Suppose the player spawns in at leaf-node (7). This leaf-node is segmented by portals (B) and (C). To determine how far into the map the player can see from his current vantage point, the engine looks at the map's PVS-table under the columns and rows of portals (B) and (C). In addition to themselves, portal (D) is the only positive entry so all leaf-nodes on either side of portals (B, C, D) are now flagged as the player's current PVS and are drawn. All the other leaf-nodes in the map are not rendered, freeing up valuable resources. As long as the player stays in the current leaf-node, there is no way for him to see portal (A) or anything beyond it.

Now the player has moved into the hallway and is standing in leaf-node (8). As soon as he crosses the threshold between leaf-nodes (7) and (8), the engine reads the PVS-table again for the current volume and highlights the columns and rows of the two surrounding portals, resulting in a list of portals (A, B, C, D, F, G). The only portals that aren't on the list are portals (E) and (H), so the leaf-nodes beyond them are hidden.

The player has has now moved into the middle of the map, into leaf-node (14). What will be rendered? See if you can figure it out, first by looking only at the map layout, and then by only looking at the PVS-table. Do your results match up? What is the player's current PVS?

See the answer below:

The current convex volume is surrounded by 3 portals, (A, F, G), so those columns and rows on the PVS-table are highlighted. Portals (B, C, H) are the only portals not on the list, so the areas beyond those portals are not rendered.