Here is where I'll write about Possible Visible Set and how it is calculated. Then I'll go into the optimizations, RLE the PVS list and lastly appologize for not yet understanding how non-occluders are implemented.

Possible Visible Set (PVS) is the set of all areas visible from this area. In BSP terms, it's the set of all interior leaf nodes visible from any other interior leaf node. If you know this list then you can stop trying to draw certain portions of the tree because you know that portion will be drawn over or clipped and thus turn into a huge waste of time. And since BSP models almost never change shape, you can save even more time by precalculating the list. The whole idea is just to save as much as possible when rendering, even if it involves a certain ammount of work ahead of time.

Now, most of you are probably thinking about the problem of how to calculate the list. You might consider casting "rays" outward from each node and seeing if the ray passes uncut into every other node. This has a few big flaws: how can you be sure something small and really far away doesn't fall between rays? Ok, you could test against every vertex in every other node. How do you find a spot in your starting node from which you can see into all the other possible nodes? There are just too many cases to consider. What we need is a way to cover the entire area visible between any two nodes.

Solution: Portals! Consider a set of portals generated from a simple BSP.


If you were standing in section 1 you could see into everything except leaf nodes 7 and 8. The same is also true in reverse. Now let's consider the portals and how they play their part.

Penumbra is the shadow cast by something when a light is shone on it. Antipenumbra is the exact opposite, something like shining a light through a piece of paper with an oddly shaped hole cut in it. the antipenumbra of any one portal through any other portal tells us which of all the other portals is visible when looking in that direction.


Since all portals are sandwiched between two nodes, if a generator portal is within the antipenumbra of a source and target portal then the nodes touching the source, generator and target can all "see" each other. But what's the fastest way to figure out which portals lie in the antipenumbras of other source/target combinations? What if a node has more than one portal? What about the possibility of one portal seeing into another and another and then another? EEEP!

Once again, recursion comes to our aide. The pseudocode would go a little like this.

for( every node 'gSourceNode' ) {
  gSourceNode.PVSMarkVisible( gSourceNode ).
  for( all portals touching gSourceNode 'sourcePortal' ) {
    for( all nodes touching sourcePortal 'targetNode' ) {
      if( targetNode == gSourceNode ) continue;
	  gSourceNode.PVSMarkVisible( targetNode );
      // Since targetNode is convex (a rule of BSPs)
      // all target portals must be visible from
	  // sourceNode.
      for( all portals touching targetNode
         'targetPortal' ) {
        // Eliminate trivial cases.
        if( targetPortal == sourcePortal ) continue;
        if( targetPortal and sourcePortal are
            coplanar ) continue;
        RecursePVS( targetNode,
          targetPortal,
          sourcePortal );
      }
    }
  }
}


Recurse( targetNode, targetPortal, sourcePortal ) {
  generatorNode = targetPortal.GetNode()  that is not
                  targetNode.
  gSourceNode.PVSMarkVisible( generatorNode );
  for( all portals touching generatorNode 
      'generatorPortal' ) {
    // Eliminate trivial cases.
    if( generatorPortal == targetPortal ) continue;
    if( generatorPortal on the gSourceNode side
        of sourcePortal ) continue;
    if( generatorPortal on the targetPortal side
        of targetPortal ) continue;
    // This is the tricky part.
    newGenPortals += AntiPenumbraClip( generatorPortal,
        targetPortal, sourcePortal );
    newSrcPortals += AntiPenumbraClip( sourcePortal,
        targetPortal, generatorPortal );
    // If anything is still visible, we have to recurse.
    // This is what makes it memory expensive.
    if( !newGenPortals || !newSrcPortals ) continue;
    for( all newSrcPortals 'nsp' ) {
      for( all newGenPortals 'ngp' ) {
        Recurse( ngp, generatorNode, nsp );
      }
    }
    delete all nsp and ngp.
  }
}