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