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

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

    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

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.

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.

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

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:
  • Select best unused plane from list
  • If no planes left, construct leaf
  • Partition polygons into two lists. If polygon lies on plane, place polygon into front list
  • 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