Introduction
BSP trees provide a quick method of sorting a collection
of 3d polygons in a scene. The BSP (binary space partition) tree is pre-calculated
in advance. This can then be used to sort the polygons in real time.
Theory
The diagrams shown will be 2D top down views, although
3D terms such as plane, etc will be used.
Making
a BSP Tree
First I shall discuss the method of making a BSP tree.
Below is a diagram showing a simple room to which the BSP tree algorithm
can be applied.
The white capitals mark the vertices of the polygons. The yellow lower
case letters mark the polygons. Note that the polygons are split, eg polygon
'a' is split into a1, a2, & a3. More on this later. Note that the point
at which the polygons are split is the point at which the polygon intersects
with a red line. The blue lines denote the surface normal of each polygon.
Note that a point is 'infront' of a polygon if it is on the side on which
the normal points, for example Vertex 'D' is infront of polygon 'h'. If
the point is on the other side, it is 'behind' the polygon. The red lines
extending from each polygon denote the plane on which the polygon lies.
When splitting a polygon (call it polygon 2), or determining whether it
is infront of or behind polygon 1, you determine which side of polygon
1's plane polygon 2 is on. The planes are also used to split the polygons.
When polygons are listed, they will be listed with their constituent parts
in brackets. For example, the polygon a will be listed as a(a1,a2,a3),
because a is split into a1, a2, & a3. However this will not be done
if the polygon has only one constituent part, ie polygon 'f' which has
only one part. These constituent parts (a1, b3, etc) are calculated during
the BSP tree creation process, - they are known to the algorithm only as
either 'a' of 'b', etc. However, for the purposes of this document, their
constituent parts will be listed.
We start off with the list of polygons :
a(a1,a2,a3),
b(b1,b2,b3,b4), c(c1,c2), d(d1,d2,d3), e, f, g, h
We then choose a polygon with which to partition the room. The choice is fairly arbitary, although a polygon which has other polygons 'infront' and 'behind' it should be chosen. For the purposes of this example we will choose polygon f. We then divide the scene into polygons which are 'infront' of polygon f, and polygons which are behind it. Polygons which are partly infront and partly behind are split, ie polygon b(b1,b2,b3,b4), which is split into b1, b2(b2,b3,b4). So, polygon b is split into b1, b2(b2,b3,b4), and d is split into d1, d2(d2,d3) The polygons which are infront of f are : a(a1,a2,a3), b1, d1, e, g. The polygons behind are : b2(b2,b3,b4), c(c1,c2), d2(d2,d3), h, i. To turn this into a tree we put f at the node (where the tree splits), the polygons infront of f go on the right subtree, and the polygons behind go on the left subtree. We end up with the tree :
Step 1
f
/ \
/ \
/
\
/
\
/
\
/
\
b2(b2,b3,b4),
a(a1,a2,a3),
c(c1,c2),
b1, d1, e, g
d2(d2,d3),
h, i
The algorithm is now repeated for one of the subtrees, - a partitioning polygon is chosen, however, ONLY the polygons on the subtree you are working on are split : if polygon e in the right subtree was chosen, only polygons in the right subtree are split and partitioned, (partitioned as is in split, sent to front/right or back/left) polygons in the left subtree are ignored. Note that in the following stages all subtrees will be split, - if you take it one step at a time it would take forever! This is how our tree progresses :
Step 2
f
/ \
/ \
/
\
/
\
/
\
/
\
h
e
/ \
/ \
/ \
/ \
/ \
/ \
b3, d3 b2(b2,b4),
a2, d1 a1(a1,a3), g,
c(c1,c2),
b1
d2, i
In the case of both the 'a2, d1' and the 'b3, d3' subtrees, they will need to be split further despite the fact that there are only two polygons meaning that the partitioning polygon will not be able to have polygons on both sides. Although, in some cases when only two polygons are left, one could be split, although this should be avoided, - the more splitting that is done, the more polygons there are that need to be drawn. The way to avoid splitting is to (if possible) choose the partitioning polygon that does not split the other.
Step 3
f
/ \
/ \
/
\
/
\
/
\
/
\
h
e
/ \
/ \
/ \
/ \
/ \
/ \
b3 i
a2 g
/ / \
/ / \
/ / \
/ / \
d3 /
\
d1 /
\
c2, b4 b2, c1, d2
a3, b1 a1
Note that the b3 and a2 subtrees have no polygons infront of them, so b3 and a2 do not have further right subtrees. Also, there is only one polygon on the left subtrees of b3 and a2, so the tree stops here and does not diverge / extend any further.
Step 4
f
/ \
/ \
/
\
/
\
/
\
/
\
h
e
/ \
/ \
/ \
/ \
/ \
/ \
b3 i
a2 g
/ / \
/ / \
/ / \
/ / \
d3 /
\
d1 /
\
c2 b2
a3 a1
/ /
/
b4 c1
b1
\
d2
To save time (and page space) two steps were taken, in the last tree, there
was a 'b2,c1,d2' subtree which has been split into its components to COMPLETE
THE TREE. (YIPEE!)
As you may have noticed, in step 3, the 'b2,c1,d2' subtree could not be
split so as to have polygons both infront of and behind the partitioning
polygon. In cases like this, any
partitioning
polygon can be chosen.
When turning this into code, a recursive function would be written. A data
structure
similar
to this would be used :-
struct
BspNode {
TPolygon* list;
//the list of polygons for thie node
TPlane partition;
//the plane of the partitioning poly. The plane is all that is
//needed to paritition a list, the polygon data is not.
BspNode *left, *right; //pointers to left
and right subtrees
};
The recursive function could take input in the form of a pointer to a BSP
node structure
like above.
It would partition the list and send the front and back lists to the subtrees
pointed
to by the BspNode* pointers. The function would the call itself this passing
the pointer to the left subtree. (if the tree extends no further down that
path, it would not do this - this is where it stops recursing) The left
subtree would get processed. It would call again,
this time
passing the right subtree to be processed. the function would then terminate.
Thats pretty much it.
Traversing a BSP Tree
Traversing the BSP tree is REALLY easy. We shall take it that you want
to draw the polygons in the order of back to front. (use it as a painters
algorithm) You need the location of the
camera
to do this.
At each node of the tree (well each node that has one or more subtrees
that is) you have a
partitioning
polygon. Once again, in code, the function would be recursive. You process
one node at a time. To process a node, you take the plane of the partitioning
polygon. You need to
determine
which side of the plane the camera is on, - infront or behind.
The plane
equation is :
Ax + By + Cz = D
Where the vector [a,b,c] is the surface normal. To determine which side
you put the x, y, & z coordinates of the camera into the plane equation.
(alternatively you take the dot product of the camera location vector and
the plane surface noamal) You compare the result of the left side of the
equation (or the result of the dot product) and compare it with D. If the
result >= D, the camera is in front of the plane, else it is behind. You
now know which side of the partitioning polygon the camera is on. You want
to draw the polygons on the other side first. So, if the camera is infront
of the partitioning polygon, you want to draw the polygons behind, so you
call the recursive function passing it a pointer to the left (behind) subtree.
If the camera is behind the polygon, you want the right (front) subtree.
Once the recursive function call returns, you draw the partitioning polygon,
and then head down the other side of the tree. Thats it, the simplistic
recursive function will do the rest.
If anyone has any questions, ideas for optimiztions, etc, don't hesitate to mail me at :
mrmeanie@easynet.co.uk