BSP Trees
----------------------------------------------------------------------------
Introduction
BSP trees are becoming one of the most popular spatial subdivision
algorithms, due to their flexibility, and their ability to draw a scene with
perfect order. However, though they are becoming popular, they are complex
and difficult to code at first, and the theory can be hard to understand for
some people. In this page, rather than going over and over the same things
that have been said a thousand times before, I'll instead give a brief
overview of the theory, and concentrate on more details regarding the
implementation. More information concerning one specific part of BSP trees
can be found in the BSP FAQ, though it does have to be said that there are
some unfinished parts in it. This is no criticism on the author, just a
neutral observation. (And perhaps a hint that people should help finish the
FAQ!).
----------------------------------------------------------------------------
Theory
Note: this section is only intended as a refresher. If you don't know BSP
trees, then there may be better definitions for you to learn from. This is
to set the scene, and introduce the contents of this file.
A BSP tree carves up space into sets of successive half-spaces. A half space
is the portion of space that is either in front of a hyperplane, or behind
it. A hyperplane is a plane, with the same dimensions as the space it is in.
For example a 2D hyperplane is a line. A 3D hyperplane is plane. However, a
2D hyperplane (line) cannot be used to partition 3D space into two
half-spaces. Likewise a 3D plane cannot partition 4D space into two
halfspaces. Halfspaces are infinite, and every polygon must lie entirely in
only one halfspace.
A BSP tree is built by making a binary tree, where each node has a plane,
which may or may not be from the source model, and the branches point to the
sub-nodes that either lie entirely behind that plane, or, entirely in front
of that node. Similary, the sub-nodes of that node have their own planes,
which contain sub-nodes and so on. The planes stored in the nodes gives us a
space partitioning scheme, as they can be used to identify polygons or
objects that lie in regions of space enclosed by a set of planes. These
planes are later used for sorting the scene. A node may or may not have
polygons stored with it; this is the key distinction between node-based and
leaf-based BSP (more on that later).
At each node, there is some form of cheap, simple bounding volume, such as a
bounding sphere or a bounding box. This box/sphere encloses both the current
node, and all its children. This volume is used to aid rendering and
culling, as this gives a tree a hierarchial nature, so that subtrees can be
discarded if their bounding volume fails to fulfill some criteria.
----------------------------------------------------------------------------
Code and data structures
The data structure for a BSP tree is fairly simple. Below is a pseudo-code
description, derived from the BSP tree structure I use in my own BSP engine.
Structure BSPNode
BSPNode pointer frontnode, backnode;
Vector centre, transformed_centre;
List polygon_list;
Plane plane;
Vector boxmin, boxmax;
Vector transformed_boxmin, transformed_boxmax;
End Structure
Structure BSPTree
BSPNode Pointer root
List vertex_list
End Structure
These two structures enable us to represent the BSP tree in memory. Included
in the structure is enough information to make the tree practical. Note that
you should aim to try and make this structure as small as possible, as there
may be a great many of them loaded into memory.
Code structures for the BSP tree largely reflect their recursive nature.
Recursive functions are very common when dealing with BSP trees, whether
they explicity recur on the CPU stack, or, instead use a stack of BSP trees
to handle the recursion, so avoiding possible stack overflow. Each method
has its advantages and distadvantages, and you should experiment with both.
However, for the purposes of this file, I'll stick to explicit recursion, as
it makes the code easier to follow.
Loading and saving a BSP tree can be done in the natural recursive manner
for this data structure. All it takes is to simply dump the node structure,
along with a flag, to the file, and traverse the tree in the same order.
In your flags field, you would have something like:
00000000000000xx - Has front sub-tree
|--- Has back sub-tree
This flag field contains all the information you need. Then, you choose
which order to save nodes in, either [front node, back node], or [back node,
front node]. Choose an order and stick to it. Then when you load save, its
simple. If a node has a front sub-node, set the bit to 1. Same for the back
node. Then, when writing/reading, simply traverse the front or back node if
it exists, then traverse the other if it exists. Eg:
If (node has front sub-node)
Set bit in flags variable
If (node has back sub-node)
Set bit in flags variable
Read/Write flags field
Read/Write node data
If node has front sub-node
Recur with front-node
If node has back sub-node
Recur with back-node
Its that simple. Makes stuff a lot more elegant. Although this might seem
hard at first, it soon comes to you. This is partly the reason I don't like
or use the Jaluit compiler, because its output format is so weird... this
way is so much simpler.
----------------------------------------------------------------------------
Building the tree
Building the tree is the most expensive process, and it can quickly become
very time- and memory-consuming, as the size of the polygon database
increases. Building the most optimal tree is a desirable goal, but is very
expensive for large databases. Also, for different purposes, there may be
different optimal trees. However, there are two general "best" cases;
Split-optimized, and Balance-optimized.
To construct a Split-optimized tree, you simply have to select the plane
that will cause the least amount of polygons to be split. This is done by
classifying what side of the plane a polygon lies. If all of its vertices
are in front, its in front, no split. If all are behind, its behind, no
split. If all are on the plane, then its just added to the list, no split.
However, if some are in front, and some are behind, then theres a split.
However, if some are on the plane, and some are [in front / behind], then
there is no split. That last point once caused me a lot of problems, and not
many people spot it when writing a compiler. Consider:
/-----\
| |
============== <--- plane
| |
\-----/
That case needs a split. However:
===------======
| |
\----/
Does not need to be split. Its behind the plane, though it may not seem
so at first.
The reason this distinction is so important is that often we have such
surfaces butted against each other, and a naive compiler will attempt to
split, possibly causing both a degeneration in the polygon, and un-needed
increase in polygon count.
Balanced trees must have roughly the same number of polygons either side of
the plane. This is quite simple to calculate. Count the number of polygons
in front of the plane. Count the number behind. Don't count the number on
the plane, or those split, as they don't really need to be considered. To
find the difference, just do abs(numback - numfront). If this is less than
say some value, eg 5, then take the tree. Else carry on searching. You may
wish to look for a balance of zero, which would give you a perfectly
balanced tree.
You can also combine the two criteria together. I do this by calculating a
"score". The score is derived from the number of splits, the balance, and
the number of the plane. I use the formula:
Score = numsplit*ksplit + balance*kbalance + onplane*konplane
Where
Numsplit = number of polygons split
Balance = abs(front - back), the balancing value
Onplane = Number of coplanar polygons
ksplit, kbalance, konplane = Weighting of those threee criteria.
A smaller score will yield a better tree.
Classification Routine
You'll need a routine to classify the polygon against the plane. Though this
seems easy enough at first, the case I pointed out above can often
complicate things. The best routine I have found is something like:
Function ClassifyPolygon(Polygon, Plane)
Integer front, back, on
front = back = on = 0
For i=0 to Polygon.Numvert
Switch(ClassifyVertex(Polygon.vertex[i], Plane))
Case InFront:
front++
Case Behind
back++
Case OnPlane
on++
front++
back++
End Switch
End For
If on == Polygon.Numvert Then
Return OnPlane
Else If front == Polygon.Numvert Then
Return InFront
Else If back == Polygon.Numvert Then
Return Behind
Else
Return Split
End IF
End Function
I've found that this routine works well for me. Now, this routine will have
to be coded very well, because its going to be called over and over again.
Bounding Boxes
For BSP trees, I find personally that bounding boxes work as the best
bounding volume, because the further you go down the tree, generally, the
flatter the box tends to become, because you come closer and closer to a
single plane (for node based BSP. So, a box will have the least wasted
space. However, a sphere will be easier to code, and slightly cheaper to
test. However, you have to trade off the cheaper test against the fact that
the wasted space may cause a sphere to be inside the volume, with no
polygons inside after all.
Constructing the bounding box for a node and all its children is very
simple. Firstly, construct the bounding box for the nodes polygons. Thats
done by examining each vertex, and updating the minimum/maximum co-ordinate
values accordingly. The two values, minimum and maximum, give you a bounding
box for that node alone. Now, traverse either/both/neither of the subtrees,
depending on whether they exist or not. Now, find the maximum bounding box
out of all (1-3) boxes. Hey presto, thats your box.
Splits
I don't intend to go into the precise details of splitting polygons, as
there is pseudo-code in the FAQ, and real code in my compiler. However,
there are some things you should be aware of:
* Numerical problems. Floating point can have some accuracy problems. So,
to compensate, choose some value epsilon to be 1/2 the thickness of the
plane. Then, instead of:
If dist < 0.0
Behind
Else If dist > 0.0
InFront
Else
OnPlane
End If
Write:
If dist < -epsilon
Behind
Else If dist > epsilon
InFront
Else
OnPlane
End If
* Cracks. This is caused by one polygon being split, and a polygon that
shares an edge being split, is not split. This can introduce T-vertices
into the model, which in turn will cause shading anomalies. Some ways
around this are:
1. Use a subpixel accurate rasteriser. However this will only remove
the crack, it won't correct the shade/texture problems.
2. Insert the new vertex into both polygons that share the edge. This
is the better solution, as it will correct the shading problems
too. However, you'll have more complex geometry to deal with. If
you triangulate your tree, you will then add an extra triangle per
vertex inserted; not nice.
Personally I've just used option 1. However, I do have the texturing +
shading problems I mentioned. I've got as far as creating the edge
list, but not finished coding number 2 yet. Just a matter or getting
other things done first, before I worry about that
----------------------------------------------------------------------------
Rendering The Tree
This is the most important bit, and, the biggest advantage that using BSP
trees over things like octrees. Though octrees can be used for a display
algorithm, if I remember rightly, it only works for parallel projection. BSP
trees however provide a fast, simple method of drawing, with zero sorting
errors, and high speed.
The basic idea is that if the viewer is in one half-space, we traverse the
trees and render polygons in one order, and, if the viewer is in the other
half-space, then traverse in the opposite order. Pseudo code for a
front->back traversal is:
Dot = Viewer*Plane
If Dot > 0.0 Then
If Front Node exists Then
Traverse Front Node
End If
Draw Polygons
If Back Node exists Then
Traverse Back Node
End I
Else
If Back Node exists Then
Traverse Back Node
End I
Draw Polygons
If Front Node exists Then
Traverse Front Node
End If
End If
This gives us a basic frame to work with. Firstly, we can get rid of the
polygon drawing part of the Else clause in the If statement. This operation
performs back face culling. We can now cull large numbers of polygons in one
go, as the average scene will consist of large numbers of planar polygons,
such as floors, ceilings, walls etc. This is also very beneficial for
triangle renders, as it slashes the triangle count, because a triangle-based
modeller (like 3ds) will generally use more triangles for the same surface
than a polygon (n-gon) based modeller would.
Now, before we go any further, an important note: You need to transform the
plane equations into camera space before finding the dot product. This is
one important detail the various BSP sources on the 'Net failed to tell me,
resulting in lots of strange sorting errors. Now, there are two ways of
going about this:
1. Transform the plane equation itself. Given a point on the plane P, the
plane equation N, then we have: N*P = 0. Given a transformation matrix
M however, N*(M*P) != 0. So we have to compensate for that problem, so
transforming the plane equation by the inverse matrix, M^-1. So, (M^-1
* N)*(P * M) = 0. However this is a bit awkward, as we have to invert
the matrix etc...
2. Instead, just transform the plane normal, and a point on the plane.
Then, use these two points to find the distance part of the plane
equation, 'D'. If the plane equation is Ax + By + Cz + D = 0 then the
normal is given by (A, B, C). Rearranging for D gives us D = -Ax - By -
Cz, which is the negative dot product of the normal against the point.
Given the transformed normal, and the new D, you now have the plane
equation you need. This is the method I use.
Now lets get back to optimizing this code. Now, we know that if a node is
not in the frustum, theres no point traversing it, because we won't see its
polygons, nor its childrens polygons. So, extend the traversal If statement
to something like:
If (Front Node Exists) And (NodeInFrustum(Front Node) Then
Traverse Front Node
End If
Repeat that for all the If statements, and now you're not traversing parts
of the tree you don't need to. Now, another thing: don't do one big block
traversal of your vertices. We have a spatial subdivison scheme, and so we
can postpone transforming the vertices 'till we know that the vertex is in
the frustum. Using the frame counter idea I describe in the Speed-up page,
this can easily be done. Simply make a function that transforms all the
vertices belonging to all the nodes in the polygon, if they haven't already
been transformed. This is called just before the polygons are drawn. So we
have:
TransformNodeVertices
DrawNodePolygons
Where TransformNodeVertices looks something like:
For every polygon in node
For every vertex in polygon
If vertex not already transformed Then
TransformVertex
If Vertex Inside Frustum Then
ProjectVertex
End If
End If
End For
End For
This alone should get you a decent frame rate. However, advanced things such
as visibility pre-processing are not covered here; thats because I haven't
got round to writing myself a good visibility generator yet, because I'm
still researching the problem. However, once I do, I might write a page on
that ... (If anyone knows anything...)
----------------------------------------------------------------------------
Leafy BSP
Leafy BSP is different to ordinary, node-based BSP. In nodey BSP, we store
the polygons in the nodes of the tree. However in leafy BSP, we store the
polygons in the leaves. A leaf is defined as a node with no children. The
idea is that the polygons we then store in the leaves are no longer always
planar (though they could be), but form a convex hull. The polygons in this
hull can then be painted in any order, with backface culling applied. This
also gives us the advantage that we can choose any old plane we like, rather
than planes from the model -- though we can still use those if we want.
Traversal is done as usual, with the planes in the tree simply being used to
"guide" ourself to the leaves. It sounds a nice scheme, giving us the
following advantages:
1. Smaller tree? Presumably larger numbers of polygons would be bunched
together, and possibly in a more spatially coherent manner, as you
would choose things like tabletops and boxes, rather than big, flat,
planar surfaces such as floors and ceilings.
2. Following on from the latter point in #1, possibly better spatial
coherence? However, not having planar polygons means that the backface
culling will have to be done seperately. Though you can still cull
entire sets of polygons in one go, because you can store a list of
planes, with the associated polygons. You'd have something like:
Procedure RenderTriangle
If triangles plane not processed Then
If plane backfacing Then
Mark all planar polygons backfacing
Return
Else
Mark all planar polygons front facing
End If
Else
If triangle marked backfacing
Return
End If
End If
Usual stuff to draw the triangle ...
End Procedure
In fact thinking about it, that code could be used in *any* renderer,
whether its BSP based or not. Damn ... why didn't I think of that
sooner? Anyway, better spatial coherence will lead to better culling,
etc ...
If you're interested in the source code to a BSP tree compiler to play with,
then the source to a slightly older version of my compiler than the one I'm
using (A man has to keep some tricks to himself) is available here. I may
put up the source to my new Solid BSP Tree compiler sometime, but its still
under development, so not for a while yet.
----------------------------------------------------------------------------
Solid BSP Trees
Before I go any further, I would like to thank Sean Barrett for answering a
number of questions I had regarding Solid BSP Trees. Without those answers I
wouldn't have got them working so quickly.
Solid BSP Trees are a slightly different version of regular BSP trees, with
the property that they encode space into Solid/Non-solid partitions. This
property has a number of useful applications, most notably in ray tracing /
casting problems, such as visibility, or collision detection. They can also
be used to form a leaf based BSP representation. Understandably they are
desirable in any engine.
Crucial Differences
There are a number of areas where Solid BSP trees differ from conventional
BSP trees. Most notably, is the fact that they store convex lumps of
polygons in the leaves, rather than the nodes of the tree. This is the
property that most people know of. As mentioned before, they can also encode
space into Solid / Non-solid blocks. And, the rendering algorithm differs
slightly.
Construction
Constructing a Solid BSP tree is similar to that of a normal BSP tree, but
with a major difference: You can't use the "coincident" BSP case. So, if a
polygon lies along the plane that is being used in the node, you cannot
place it in a list. It has to be sent down the front list for that node.
Now, there is a second difference. In traditional BSP, you selected the
plane from the list of input polygons, and used it in the node. Here, we do
a similar thing. However, note that polygons are not removed from
consideration when their plane has been selected, as in regular BSP: they
will continue to be pushed down the tree until they hit a leaf. So, your
routine may unknowingly continuosly select the same plane over and over. You
need to mark each plane as used as you build the tree. In addition, we will
use *every* plane of the input polygon list. This is required, because we
cannot calculate whether we are crossing between solid and empty space if we
do not have a plane to mark the transition. Unfortunatly, this may also
bring about an increase in the number of polygons, which is a problem. So
effective plane selection becomes even more important.
When we find that all planes in the given polygon input set have been used,
we have reached a leaf. When we reach the leaf, we can work out if we have a
solid or an empty leaf.
Calculating leaf contents
If a leaf has polygons, we can easily determine whether or not the leaf is
solid or empty. We do this by using the normals of the polygons in the leaf.
If the normals point away from the centre of the leaf (assuming
outward-pointing normals), then the leaf is solid. If they point inwards,
then the leaf is empty. This is easily proved using a cube. A cube could be
a leaf in the BSP tree. The normals of the cube point outwards from the
cube, therefore it is solid.
You can construct your BSP such that any leaf with polygons is an empty
leaf, and that any leaf without polygons is a solid BSP. This is the
simplest way of doing it. It also seems to be the way Quake does it.
However, you can get problems with this, if your input data model contains
things like 2 polygons, back to back, with different planes, such as a wall,
with a box attached to it. To handle that, you need to cut out the piece of
polygon that is between the wall and the box.
Planes of Connection
This is an algorithm I've been thinking about lately. The idea is that we
can use the leaves of a BSP to find the connecting planes, between space.
Heres a diagram for you to consider:
| D | E | F
S S S S
| | |
1 2
- - |---------------------------------------| - - A
| |
| | |
| |
S | E | E | S
| |
8 | | | 3
| |
- - | - - - - - - |--------------------| - - B
| | 4
| | |
| | 5
S | U | S | S
| |
7 | | |
| |
- - |------------------| - - - - - - - - - C
| 6 | |
S S S S
| | |
In this diagram, infinite planes are marked with dashed lines (- - - -).
Polygons are marked using solid lines (-----). Solid leaves are marked with
an 'S'. Empty leaves are marked with an 'E'. Unknown leaves are marked with
a 'U'. Planes are labelled with letters, polygons are labelled with numbers.
If we wanted to flood some kind of information through the model, we can
just calculate the planes of connection, and use them to propagate the
medium throughout the model between leaves. In addition, because of the
solidity information, we can work out where to stop flooding, and where to
continue.
Given a leaf, marked on the diagram as 'U', we want to find out which planes
connect it to other leaves. If we then have that information, we can flood
fille data throughout the model.
| D | E | F
S S S S
| | |
- - |---------------------------------------| - - A
| |
| | |
| |
S | E | E | S
| |
| 1 | | 5
| |
- - | - - - - - - |--------------------| - - B
| |
| | |
| |
S 4 | U | 2 S | S
| |
| | |
| |
- - |------------------| - - - - - - - - - C
3
| | |
S S S S
| | |
The leaves are now marked with numbers. Leaves 1 - 4 are connected
neighbours, leaf 5 is a rogue, put in there to show the theory. Lets build a
table, with planes in the columns, and leaves in the rows. A '+' will mean
that the leaf lies in the positive halfspace, a '-' will mean that the leaf
lies in the negative halfspace:
Leaf | Plane
| A | B | C | D | E | F | Score
--------+---+---+---+---+---+---+------
U | + | - | + | + | + | + | N / A
1 | + | + | + | + | + | + | 5
2 | + | - | + | + | - | + | 5
3 | + | - | - | + | + | + | 5
4 | + | - | + | - | + | + | 5
5 | + | + | + | + | - | - | 3
As you can see from the table, its neighbours will have the highest score,
and its non-neighbours will have the lower scores. So, now we can easily
find its neighbours. Also, its neighbours should all have the same score.
Now, we have a problem. We need to work out what kind of solidity
information to flood. We can find the connecting neighbours, but we can't
select which neghbour to flood information from. And by examining the other
leaves, no clear rule emerges.
The solution is to "borrow" polygons from connecting leaves. We find
polygons that lie on the plane of connection, and borrow these, to calculate
the leaf type. Note that we need at least 2 polygons to calculate the leaf
type.
But how do we calculate the planes of connection? Lets repeat that last
table, but instead of usings + and -, lets use 1 and 0 respectively:
Leaf | Plane
| A | B | C | D | E | F | Score
--------+---+---+---+---+---+---+------
U | 1 | 0 | 1 | 1 | 1 | 1 | N / A
1 | 1 | 1 | 1 | 1 | 1 | 1 | 5
2 | 1 | 0 | 1 | 1 | 0 | 1 | 5
3 | 1 | 0 | 0 | 1 | 1 | 1 | 5
4 | 1 | 0 | 1 | 0 | 1 | 1 | 5
5 | 1 | 1 | 1 | 1 | 0 | 0 | 3
Can't see the connection yet? Well, lets XOR U with each bit code of 1-4:
U = 101111
1 = 111111
2 = 101101
3 = 100111
4 = 101011
U XOR 1 = 010000
U XOR 2 = 000010
U XOR 3 = 001000
U XOR 4 = 000100
Re-arranging back into columns for each plane ...
Code | Plane
| A | B | C | D | E | F
-----+---+---+---+---+---+---
1 | 0 | 1 | 0 | 0 | 0 | 0
2 | 0 | 0 | 0 | 0 | 1 | 0
3 | 0 | 0 | 1 | 0 | 0 | 0
4 | 0 | 0 | 0 | 1 | 0 | 0
-----+---+---+---+---+---+---
OR | 0 | 1 | 1 | 1 | 1 | 0
Any plane that is a plane of connection has a 1. Not bad eh? It must be said
that I haven't tested this theory extensively, nor have I implemented it yet
(hell I only just worked it out), but it seems reasonable. It is a little
complex (understatement!), so it will need some efficient coding behind it.
Perhaps the biggest problem is that it will need a N * M table, where N is
the number of leaves, and M is the number of planes. However that shouldn't
be too much of a problem. Still a clever algorithm I think.
Construction Summary
In summary, the Solid BSP construction process is as follows:
* Build a list of all planes, and polygons in model
* For each BSP node:
o Select best unused plane from list
+ If no planes left, construct leaf
o Partition polygons into two lists. If polygon lies on plane, place
polygon into front list
o Recur with two new lists
* Calculate leaf contents
Collision Detection and Ray Stabbing
As I mentioned earlier, the solid BSP tree lends itself well to performing
tasks like ray stabbing and collision detection. Both algorithms are very
similar.
Collision Detection
Working out if a given line intersects with a solid piece of space is a
necessary technique for a lot of applications, for example Computer Games.
Given a line, defined by two points, at t (time) = 0, and t = 1, ie the
start and end points of our motion, we want to work out whether that line
runs into a solid object, and if so, clip it to the intersection.
Using our solidity information, we can easily check this. What we do is as
follows. First, we classify both endpoints about the root plane. If they are
both in front of the root plane, we go to the front sub-child, and continue.
If they are both behind, we go to the back child, and continue. However, if
they are on opposite sides, we have a potential intersection with a solid.
So, we find the intersection point, and two other points, either side of the
plane, to some small offset:
x
-----------i------------
x
Where 'i' is the intersection, and 'x' are our two points. We will use one
of these 2 points as the new endpoint. We then must work out what side of
the plane the start point lies on. This is easy enough to work out if the
start point does not lie on the plane. If it does lie on the plane, you need
to use the backpoint. If the start point of the line lies in the front
half-space of the plane, then we will adjust our end position to lie in the
positive half-space of the plane. If the start point lies behind the plane,
we adjust our end position to lie in the negative halfspace.
What we do is recur with the line segments (start, intersection) and
(intersection, end). If we find that either segment ends up in a solid leaf,
then we set the end point to be the intersection, slightly offset into
either the positive or negative halfspace. If both points are coincidant to
the plane, we recur down both children. To offset into a half space, we just
add some scalar multiplied by the normal of the plane.
As thats not very easy to understand, perhaps some code is needed to
demonstrate it. The following should help clarify things:
Function ClipNode(VECTOR point start, VECTOR pointer end, BSPNODE pointer node)
While Node.Type == BSP_NODE
Dist1 = DotProduct(node.plane, start)
Dist2 = DotProduct(node.plane, end)
If both in front of plane
node = node.front
Else If both behind plane
node = node.back
Else
Vector delta, mid, split, split2
delta = end - start
mid = Intersection(node.plane, start, end)
split = mid + 5.0 * node.plane.normal
split2 = mid - 5.0 * node.plane.normal
If start in front of plane
retcode = FALSE
If ClipNode(start, mid, node.front)
end = split
retcode = TRUE
End If
If ClipNode(mid, end, node.back)
end = split
retcode = TRUE
End If
return retcode
Else If start behind plane
retcode = FALSE
If ClipNode(start, mid, node.back)
end = split2
retcode = TRUE
End If
If ClipNode(mid, end, node.front)
end = split2
retcode = TRUE
End If
return retcode
Else if coincident
retcode = FALSE
If ClipNode(start, end, node.front)
end = split
retcode = TRUE
End If
If ClipNode(start, end, node.back)
end = split2
retcode = TRUE
End If
return retcode
End If
End If
End While
If node.type == SOLID_LEAF
return TRUE
Else
return FALSE
End Function
What we're doing is pushing a line down the BSP, to see where it ends up.
Where we find that a line will end up in 2 different leaves, we break it,
and push down the back segment, to see where that ends up. Note that we only
push down the back segment, because we're only interested in testing if the
end point needs clipping: we don't generally need to clip the start point,
as the start point will generally be in a correct position. We also use a
point which is slightly offset from the plane as the start of the new back
segment, because sometimes the player can become locked inside of an empty
leaf, doing this stops that.
Ray Stabbing
Ray stabbing works on a similar, but simplified manner. In ray stabbing, we
only want to know if a line is occluded or not. To do so, we use the above
algorithm, but modify it, such that we recur with both parts of the split
line, testing them both for occlusion:
Function RayOccluded(VECTOR point start, VECTOR pointer end, BSPNODE pointer node)
While Node.Type == BSP_NODE
Dist1 = DotProduct(node.plane, start)
Dist2 = DotProduct(node.plane, end)
If both in front of plane
node = node.front
Else If both behind plane
node = node.back
Else
Vector mid
mid = Intersection(node.plane, start, end)
If dist1 > 0.0
If RayOccluded(start, mid, node.front)
return TRUE
If RayOccluded(mid, end, node.back)
return TRUE
return FALSE
Else
If RayOccluded(start, mid, node.back)
return TRUE
If RayOccluded(mid, end, node.front)
return TRUE
return FALSE
End If
End If
End While
If node.type == SOLID_LEAF
return TRUE
Else
return FALSE
End Function
This ray-stabbing code is very handy for making things like lightmaps. Using
this, its very easy (and pretty quick) to stab a ray from a point on a
surface, to a light source.
----------------------------------------------------------------------------
Tom Hammersley, tomh@globalnet.co.uk