BSP Tips October 30, 2000 by Charles Bloom, cbloom@cbloom.com I'm going to write up a little bit about BSP's. I've been working with them lately, and there are some little gotchas that aren't discussed much which I'll go into. This is not a thorough BSP tutorial; look around the web for one of those. Also, I'm not going to talk at all about using BSP/CSG brushes to build geometry, I'll only talk about putting your polygons into a BSP once you've already got them from somewhere else. This is very usefull for collision and such. For example, testing all kinds of primitives for intersection with a BSP is very easy (eg. point-BSP, ray-BSP, swept-box-BSP, etc.). -------------------------------------------------------------- 1. A simple minimal BSP. First, I'll describe a very memory efficient little BSP. The cool thing here is that you don't actually need to store the polygons in the BSP at all. Thus your node is simply : BSPNode { short planeIndex; short frontChildNodeIndex,backChildNodeIndex; }; // 6 bytes ! Each node stores an index into a shared plane array. When you add a polygon to the BSP, you simply send it down the tree, cutting it at each existing plane in the tree and sending it down one or both sides. Whenever you hit a leaf, you make a new node. You generate only one plane in the shared plane array for each polygon you add, and all the nodes created for that polygon share that plane. I don't care at all about the order that you choose your polygons in. If you want to balance your tree, or minimize splits or whatever, you have to worry about that, but it's too much CPU work to worry about all that. If you like, an easy thing to do is sort your polygons by area, so that the largest ones go in first; this tends to do a nice cheap job of reducing splits. The polygons you add to the tree must have proper orientation. That is, they must have a front side which points at empty space, and a back side which points at solid space. As you are adding polygons, you make new planes that have front and back side children. Those children are implicitly "empty leaves" at that time. After you finish adding a closed model, you can ru through your BSP and mark all back side children of nodes as "solid". Any polygon which lands in a solid leaf in the future will simply be tossed out, eg. not create a new plane. An empty leaf is implicitly coded as a "NULL" child index. A solid leaf is encoded by storing (-1) or some such dummy-value as the child node index. I'm assuming that you're adding chunks of geometry to the BSP one by one. Each chunk must be independently closed (sealed, no leaks) and have a well-defined inside and outside. There are ways to reduce these restrictions, but they complicate matters and aren't worth doing. If you have a model that isn't closed, you can do something like CSG-style BSP to force it to be closed before adding it to the BSP I describe. If you add a polygon, and it goes down the tree and hits a plane which it lies along (the polygon is on that plane). You simply stop the descent and do nothing. The result is a very memory-efficient BSP. You need 16 bytes per polygon to represent the plane of that poly (a plane is 4 floats), and 6 bytes per node (you need O(N*log(N)) nodes typically, and O(N^2) worst-case, with N = number of polys). You can now do your simple primitive queries. To find out if a point is inside a model or not, you just "send the point down the BSP", and see if it hits a solid leaf or not. A little ascii art, now. Consider a 2d BSP for ease of drawing. Now the nodes correspond to lines in the plane. The triangle is made of 3 lines : /\ a/ \b / \ ------ c Three lines, a,b,c. I add them to the BSP in order, a-b-c. The resulting BSP is : root : { 0, E, 1 } node1: { 1, E, 2 } node2: { 2, E, E } These are nodes written as { plane index, front child index, back child index } and E means "empty/null leaf" After the triangle is added, you mark back-sides solid, so node 2 becomes node2: { 2, E, S } Get it? BTW here's a little trick to improve the balance of a quick and dirty BSP like this : add some axial-aligned planes in an oct-tree like heirarchy at the top of the BSP. This gaurantees good spatial coherence in your BSP (eg. if your octtree planes are separated by D units, then two polygons that are more than D apart will not split eachother), at the cost of some extra planes. It causes a few splits, but I've found it typically reduces the total number of splits and bsp nodes created. -------------------------------------------------------------- 2. The issue of epsilons Ok, so if you try to implement this, it might seem to work on some small test cases, but then you run it on a real-game model, and you hit giant asserts. You'll find that if you take a triangle and clip it down the tree, clipping segments by planes, you'll wind up with polygons that are no longer convex. This is very bad, it's an inconsistency - any polygon which lands in a leaf of a BSP after clipping should be convex. This problem is caused by floating inaccuracy. Let's investigate exactly how we clip polygons and what causes this problem. To clip a polygon to a plane, you walk through the list of vertices which make up the polygon (a convex polygon is just a list of vertices). You consider the edge from that vertex to the next vertex in the list, which defines a segment. If both ends of the segment are on the same side of the plane, you add the current vertex to a new polygon you are building for that side of the plane. If the segment crosses the plane, you make a new vertex where the segment intersects the plane. You add the segment (current->new) on one side of the plane, and (new->next) on the other side of the plane. So, this is all very easy. The hard part is just in finding this new vertex produced by intersection of the segment with the plane. How do we get this vertex? If the vertices of the segment are vCur and vNext, then we compute : dCur = signed distance from vCur to Plane; dNext = signed distance from vNext to Plane; // dCur and dNext must have opposite signs ! that's what it means // to be on different sides of the plane ! ratio = dCur / ( dCur - dNext ); vNew = vCur + ratio * (vNext - vCur); Well, this is all very nice. The problem is when dCur and dNext are very different (eg. one of them is very small, a vertex is nearly right-on the plane), then the value "ratio" is very inaccurate, which makes vNew very inaccurate. This means that vNew may not be close to the plane it's just been clipped to. This "drift" of clipped vertices is what causes polygons to because problems. So, how to do we fix it? We need to make all our planes thick. We must do this in a way that is totally internally consistent, that is, use the same thickness everywhere. If we clip a polygon against a plane, then take the resulting polygon on the front side, all of its vertices must be classified as "on" the plane, or in front of the plane. To gaurantee this, we need to expand the definition of "on" to include the vertices which are made by clipping. Thus, we define a global thickness value for our BSP planes. Any vertex within that distance is classified as "on". When you send a vertex down the BSP tree, any vertex which is "on" a plane must be sent to both sides. Without this "on" concept, a vertex will always land in just one BSP leaf. With this classification, a vertex may land in several leaves. This is not an inconsistency. Instead, this is because all the leaves are implicitly enlarged by the plane thickness amount, so that they overlap eachother slightly. To clip a polygon against the thick planes, we have to consider some new cases. First of all, a polygon could be totally "on" the plane if all its vertices are "on". If some of the vertices are on the plane, and some are in front, then the polygon is classified as being in front of the plane. The polygon is only clipped if it has vertices which classify as being in front of the plane and behind the plane. When clipping the polygon, a segment from "front" to "on" is added to the new front-side polygon. A segment from "on" to "on" is added to both the new front and back-side polygons. Only segments from "front" to "back" side vertices are clipped. This guarantees that whenever you do the clipping math, dCur and dNext (the distances from the vertices to the plane) have magnitude at least equal to the plane thickness. After creating the new vertex (vNew) you should assert that it is "on" the plane. This is the key consistency condition that we needed. If I clip a polygon against a plane, I get two new polygons, a front poly and a back poly. If I test them against the plane, I will always find that the front poly is classified as being on the front side of the plane. This will NOT work if you don't use thick planes !! Whenever you do any distance comparisons in your BSP work, you must always be aware of this plane thickness. If you ever don't use it, you'll end up with inconsistencies. -------------------------------------------------------------- 3. Floating precision (BSP's in large worlds) So, by using thick planes we've assured that dCur and dNext in our clipping equation are larger than the plane thickness. We could still have a problem though, if dCur = - thickness, and dNext was very large (for example). The largest dNext could be is equal to the size of your world. We need to make sure that when we take the world size, add the plane thickness, and then subtract the world size, we get back something reasonably close to the plane thickness, eg. not zero. Since 32-floats have 24-bit mantissas, we need to make sure that the world size and the plane thickness do not differ by more than a factor of 2^20 roughly. In most games where the human is the basic scale for the game, you would want a plane thickness around 1 cm, so that it's as large as possible without causing visual anomalies (you could use 1mm if you have a lot of fine details that the player can interact with). This means that your world must be confined to a cube of size 1km on a side. This is too small for many games. One option is just not to make a BSP from your whole world, but rather make one for each small model in that model's coordinate space. If you must make a BSP for the whole world, then you should split the BSP on a grid. That is, divide the world into chunks, and make each chunk have it's own local coordinate system. Add your models to the chunks they lie in (possibly more than one). This is a pain, but it's much better than dealing with floating precision problems. This is why that assert about "vNew" lying on the plane it was made from is so important - if you start using worlds that are too large for your plane thickness, you'll hit that assert and know you're in trouble. You must then either cut your world or increase your plane thickness. -------------------------------------------------------------- end