Extracting Connectivity
Information From A BSP Tree

By Nathan Whitaker

Introduction

Finding leaf - leaf connectivity information from a bsp tree may seem unimportant for most applications but, for games especially it is an important issue. Consider the bsp tree for a Quake level - instead of storing one polygon at each node, convex clumps of polygons were stored at each leaf and only split plane information was stored at the nodes. The average Quake bsp tree contained about 10000 polygons which you can imagine would be extremely slow to process. Quake did many things do speed this up but, perhaps the most important was the use of a ‘Potentially Visibile Set’ ( pvs from now on ). A pvs contains a bit for every leaf ( convex clump of polygons ) in the bsp tree - if that leaf is potentially visible from the current leaf the bit was set. Each leaf of the bsp tree stored a pvs reflecting other leafs so instead of processing 10000 polygons only the leaves potentially visible from the leaf the player was in were processed.

The backbone of creating the pvs is finding which leafs are connected via portals. If we assume the bsp tree we are testing is a closed corridor style environment ( like Quake, Doom ) then we know that passage into another leaf only exists between a portal ( open leaf ).

 

Finding the portals

Stage one

After we have created a Quake style bsp tree ( split planes at the nodes, convex clumps of polygons at the leaves ) we can start to find the portals with a large amount of recursion. For every split plane in the bsp tree we create a huge square polygon along that plane with dimensions matching the bounding sphere of the data set. The next stage is to slice up this huge polygon into many smaller polygons. The slicing process is recursive and involves slicing each polygon by all the other splitting planes that make the bsp tree. We now give each polygon a unique id and also store which split plane it lies on.

Stage two

After stage one we will have lots of polygons all of varying dimensions but, all will lie on one of the split planes. Now we run each polygon in turn through the bsp tree until it eventually pops out at a leaf. If the polygon is in front of a plane we push it down the front list, if its behind we push it down the back list and if it is on the plane ( easy to check if you store the data in stage one ) we push it down the front and the back list.

Pushing down the front and the back at the same time is the only tricky part to this stage as you still have to process the polygon down both sides. it is worth mentioning that if you end up having to split any polygons then you have made a mistake in stage one - remember every polygon is pre split against every plane in the bsp tree.

When any polygon finally reaches a leaf store its id ( and any other id’s that reach the same leaf ).

Stage three

After stage two we have id numbers of polygon’s ( potential portals ) stored in each leaf. We now check each polygon to see which leaf(s) it exists in . If we find it exists in only one leaf we can disregard it - it can’t be a portal ( two sides make a portal ) but, if we find it exists in two leaves we clip the potential portal against all the polygons in both leaves planes. Any part of the potential portal that lies behind any of the leaf polygons planes gets thrown away. If the polygon we are about to test against lies on the same plane as the potential polygon we leave it.

After this stage if any potential polygon remains ( survived all the slicing ) it is in fact a portal between the two leaves it existed in. The final shape its in is also the shape of the portal between the two connecting leaves ( back bone of a pvs ).