Today’s JavaScript engines are dramatically faster than they were even a few years ago, but they still have a long way to go. WebGL applications can’t afford to sacrifice even a few milliseconds; if you can gain them, you need to do so in any way possible.
One of the major techniques introduced in DOOM in 1993 was the application of binary space partitioning, or BSP, trees. These allowed the engine to predict with consistent accuracy which geometry was going to be rendered to the screen before the rendering actually took place. If the engine didn’t need to render a particular set of geometry, it could completely omit it from the rendering phase. This saved a huge amount of time.
The performance issues of JavaScript-based graphics engines today aren’t entirely different from the same issues of machines in the early 1990s. CPU speed is a major bottleneck; in fact, the JavaScript interpreter is generally far slower than the graphics processor, and the vast majority of your bottlenecks are going to be here — on the CPU.
BSP trees work by splitting the geometry to be rendered into two sections. Each section has a bounding box associated with it, which occupies half of the total area of the BSP. The geometry is then split again, with each half of the BSP containing two more halves, and so on. The last level of the BSP tree contains leaf nodes, which are the actual objects to be processed.
In this implementation, we’ll continue subdividing the tree until we have bounding boxes which only contain a single triangle each. It’s worth noting that this is usually not ideal for rendering in WebGL (in which case it’s usually best to stop on a per-object basis), but it’s very helpful for accurate collision detection, which usually involves figuring out exactly which triangles are intersecting.
In googling for other implementations, I found that most BSPs are constructed in a top-down manner. In other words, you start with the root node and work your way down to the individual leaf nodes. However, I decided to try something a bit different with my tree.
A particular sticking point in generating top-down BSP trees is how to efficiently divide the node to create two new sub-nodes. Intuition might suggest simply dividing the node down the center, but this is often insufficient. If most of your triangles are in one half and only a few are in the other half, then dividing them down the center will result in a huge waste of CPU power in each frame as you iterate through empty or nearly-empty BSP nodes.
Another approach is to iterate through each triangle in the scene, decide how many triangles lie in front of and behind its plane, and choose the one that balances the node most appropriately. I’m concerned with this approach, however, due to the inherent slowness of JavaScript interpreters today. At a minimum, this approach would require the BSP to iterate through the number of triangles in the scene squared, and do so again at each level of the BSP. I believe the majority of sizable 3D scenes would cause the browser to hang using this approach, making it unacceptable for any 3D scene that is large enough to actually make use of a BSP tree in the first place.
Instead, I opted for a completely different solution: a bottom-up algorithm that starts with the leaf nodes (the triangles) and moves upward toward a single root node. This allows us to completely skip choosing a dividing plane; all we have to do is choose two nodes from a pool of nodes and recurse upward from there. If we choose nodes that are very close to each other, our leaf nodes will be tightly packed together, resulting in a BSP tree that is very efficient all the way up to its root.
This approach may not be well suited to other languages like C, but as you’ll see, JavaScript certainly has no issue with building the tree in such a dynamic manner.
Assumptions
Before we jump into some code, I’m going to assume you have some basic supporting objects in place, namely Triangle, Plane, and Box. (If not, you can get implementations of each of these from the source code for this project, linked to at the top of this article.) Their signatures look like this:
new Plane([a, b, c]):
If a, b, and c are given, they are passed to #set.
Otherwise, a plane whose extents are undefined is created.
set(a, b, c):
resets this plane according to the vertices
whereis(point):
returns whether the given point is in FRONT, BACK or
INTERSECT-ing the plane
new Triangle([a, b, c]):
If a, b, and c are given, they are passed to #set.
Otherwise, a triangle whose extents are undefined is created.
set(a, b, c):
sets up a triangle from the given 3 vertices
center:
a vec3 assigned by #set(a,b,c) representing the
calculated center of this triangle
new Box(position, size):
Creates an axis-aligned bounding box (AABB) with the given
position (a vec3) and size (also a vec3).
intersectOBB(other_box, transform):
Tests the other box with this one as an oriented
bounding box (OBB). Uses the given matrix to transform
the other box into the coordinate space of this one.
In addition to these, I’m assuming you are making use of a matrix library like glMatrix. I’ve also added the following new functions to glMatrix, which you can feel free to copy-and-paste for convenience:
/**
* vec3.min(a, b[, dest]) -> vec3
* – a (vec3): first vector
* – b (vec3): second vector
* – dest (vec3): optional destination vector
*
* Stores the minimum value for each element of a and b
* within dest. If dest is omitted, a new vec3 is created.
**/
vec3.min = function(a, b, dest) {
if (!dest) dest = vec3.create();
dest[0] = Math.min(a[0], b[0]);
dest[1] = Math.min(a[1], b[1]);
dest[2] = Math.min(a[2], b[2]);
return dest;
};
/**
* vec3.max(a, b[, dest]) -> vec3
* – a (vec3): first vector
* – b (vec3): second vector
* – dest (vec3): optional destination vector
*
* Stores the maximum value for each element of a and b
* within dest. If dest is omitted, a new vec3 is created.
**/
vec3.max = function(a, b, dest) {
if (!dest) dest = vec3.create();
dest[0] = Math.max(a[0], b[0]);
dest[1] = Math.max(a[1], b[1]);
dest[2] = Math.max(a[2], b[2]);
return dest;
};
Now that we’ve gotten those formalities out of the way, let’s start building a BSP!
We’ll store the resultant function in a variable called, creatively, BSP:
var BSP = (function() {
/* CODE GOES HERE */
})();
This code creates a temporary function, immediately calls it, and then assigns the return value of the function to the BSP variable. This gives us the flexibility of defining “private” helper functions that can only be used internally within the BSP object.
We will define two such helper functions: one to build the tree from the bottom up, and another for calculating a bounding box around a single triangle. First I’ll show the functions in their entirety, and then I’ll explain them line-by-line.
The buildLevel Function
// +level+ is an array, containing either Triangles or BSP nodes.
// This function replaces every 2 elements in the array with a single
// parent BSP node. The array is modified in-place and the size of the
// array will be cut in half, to a minimum of 1.
function buildLevel(level) {
var nextLevel = [];
var plane = new Jax.Geometry.Plane();
while (level.length > 0) {
var front = level.shift(), back = null;
var dist = vec3.create();
var closest = null, closest_index;
var result = front;
if (level.length > 0) {
for (var j = 0; j level.length; j++) {
var len = vec3.length(
vec3.subtract(front.center, level[j].center, dist));
if (closest == null || closest > len) {
closest = len;
closest_index = j;
}
}
back = level[closest_index];
level.splice(closest_index, 1);
// See if back and front are accurate. If not, swap them.
// If triangle, use the plane created by the current triangle.
// If node, use the first triangle in the box for a plane.
if (front instanceof Jax.Geometry.Triangle)
plane.set(front.a, front.b, front.c);
else {
var tri = front.front;
while (tri instanceof BSP) tri = tri.front;
plane.set(tri.a, tri.b, tri.c);
}
if (plane.whereis(back.center) == Jax.Geometry.Plane.FRONT)
result = new BSP(back, front);
else result = new BSP(front, back);
}
nextLevel.push(result);
}
for (var i = 0; i nextLevel.length; i++)
level.push(nextLevel[i]);
}
The buildLevel function is the meat of the BSP tree, and is responsible for building up the tree hierarchy, so it’s important that you understand what it’s doing. Let’s go through it a few lines at a time.
var nextLevel = [];
var plane = new Jax.Geometry.Plane();
We’re creating a few local variables to act as buffers. The nextLevel array contains the parent nodes we’re about to create; we don’t want to stick them right back into level just yet because level has to reach an empty state in order for our function to execute properly.
The plane variable will be used to check whether a given triangle or BSP node is in front of or behind another.
while (level.length > 0) {
var front = level.shift(), back = null;
Here we’re starting a loop that won’t end until we’ve exhausted the entire level array. Once within the loop, the first thing we do is shift the first element out of the array and store it in the front variable. We’re also creating a back variable; for now we’re just setting it to null.
var dist = vec3.create();
var closest = null, closest_index;
We’ll use the dist variable to check the distance from the front element to all other elements, and we’ll use the closest and closest_index variables to make a note of the closest elements.
var result = front;
if (level.length > 0) {
for (var j = 0; j level.length; j++) {
var len = vec3.length(
vec3.subtract(front.center, level[j].center, dist));
if (closest == null || closest > len) {
closest = len;
closest_index = j;
}
}
Here’s where things start to get interesting, and maybe a bit confusing. We’re creating yet another variable called result. The result will ideally be a parent instance of BSP, but we don’t want to create parents that have only 1 child, because this would just make the BSP tree slower to traverse. If the parent is only going to contain a single child, then the parent’s dimensions are going to be equal to the dimensions of the child, and it’s faster to optimize the parent out of the equation. Therefore, we’re initially setting result to the child front element.
Next, we’re making sure the level array isn’t empty yet. This is necessary because the previous call to shift may have emptied the array; we have no guarantee that the number of triangles (or BSP nodes) is divisible by 2, so we need to be aware of that possibility.
Assuming the level array isn’t empty, we’ll iterate through all of its elements. Each time we find an element closer to front than the previous, we store its distance and the array index of the element itself.
back = level[closest_index];
level.splice(closest_index, 1);
At this point, we have a front element and we’ve noted the closest element to it in the array. We’re going to assign the closest element to the back variable, and then remove it from the array using splice.
It’s important to note that the names front and back are, at this point, misnomers. We have no guarantee that they are actually the front and back elements; the only thing we know is that they were two elements from the same soup, and that they are closer to each other than they are to any other element.
if (front instanceof Jax.Geometry.Triangle)
plane.set(front.a, front.b, front.c);
else {
var tri = front.front;
while (tri instanceof BSP) tri = tri.front;
plane.set(tri.a, tri.b, tri.c);
}
In order for the BSP tree to be truly effective, we want to make front and back correspond to true “front” and “back” elements. That’s what the above code does.
First, we need to check whether we’re currently working with a Triangle or a BSP node. If the former, the plane is very simply constructed from the triangle’s 3 vertices.
If, however, we’re dealing with a BSP node, we need to find a plane within the BSP node to test against. I don’t think it matters which node we select at this point, so I just selected the front-most triangle using a while loop. The loop exits as soon as it encounters a node which is not a BSP; it is assumed to be a Triangle, and the plane is set from those vertices.
if (plane.whereis(back.center) == Jax.Geometry.Plane.FRONT)
result = new BSP(back, front);
else result = new BSP(front, back);
The last step to constructing the parent node is to test whether the second element, stored in back, is in front the plane. Since the plane is itself assumed to correspond to the front element, we must ensure that the back element is indeed behind the plane.
This condition simply performs that test; if the back element tests to be in front of the front plane, then we’ve got the two reversed, and we just switch the order of the elements so that back is front and front is back.
If the condition fails, then our ordering is correct and we construct the parent as planned.
It’s important to make a distinction here. Traditional BSP trees also test for an intersect result from the plane. If the plane intersects a triangle, the BSP should probably consider splitting it into two triangles and adding the new triangles to the array before starting again. I don’t do this here for a number of reasons:
- JavaScript. Adding more triangles is going to add more BSP nodes and reduce overall efficiency, because it is inherently much slower than its C code counterpart.
-
WebGL. If the BSP is to be used for rendering, your leaf nodes will likely be entire objects, not individual triangles, because the triangles will be grouped together into Vertex Buffer Objects (VBOs). It makes no sense to split triangles if they have to be rendered together anyway.
-
For collision detection, it makes even less sense to split triangles because the front/back test can afford to be less accurate. During collision detection, we’re generally more interested in whether the bounding cubes intersect than we are the order of intersection. It’s a nice-to-have, but not necessarily a must-have.
- There are only 2 major reasons for splitting polygons in this manner:
-
If you’re completely skipping use of the Z buffer, which was the story with DOOM. Back in the early ‘90s, depth buffer tests were expensive to perform, and DOOM had to avoid them wherever possible. Splitting polygons allowed polies to overlap each other at odd angles without causing depth-related rendering glitches.
-
If you’re performing alpha blending, in which case you want to ensure that the back-most polygons are always drawn first or else the blending won’t come out right. However, going back to the WebGL argument above, you’re likely going to be rendering an entire object at one time (in which case you can’t dynamically control the order triangles appear in), so this argument breaks down.
With that, let’s move on to the remainder of the function:
}
nextLevel.push(result);
}
for (var i = 0; i nextLevel.length; i++)
level.push(nextLevel[i]);
}
This last chunk of code is pretty simple; we close out the condition we started earlier, push the result (which is now either a parent BSP or the last element in the level array) into the local nextLevel array, and close out the while loop.
The last thing this function does is iterate through nextLevel and push its contents into the now-empty level array so that the original array can be used in a loop.
The calcTriangleDimensions Function
// Calculates the dimensions of a bounding box around
// the given Triangle. If the triangle is axis-aligned,
// one of the dimensions will be 0; in this case,
// that dimension of the bounding box will be set to a
// very small positive value, instead.
function calcTriangleDimensions(tri) {
var result = vec3.create();
var min = vec3.create(), max = vec3.create();
vec3.min(vec3.min(tri.a, tri.b, min), tri.c, min);
vec3.max(vec3.max(tri.a, tri.b, max), tri.c, max);
min_size = Math.EPSILON * 2;
for (var i = 0; i 3; i++) {
result[i] = max[i] - min[i];
if (result[i] min_size) result[i] = min_size;
}
return vec3.scale(result, 0.5);
}
Leaf nodes in the BSP tree are triangles. However, its immediate parents will wrap around the triangle and need some information about the dimensions of the triangle in order to form an accurate bounding box around it. That’s what this function takes care of.
var result = vec3.create();
var min = vec3.create(), max = vec3.create();
vec3.min(vec3.min(tri.a, tri.b, min), tri.c, min);
vec3.max(vec3.max(tri.a, tri.b, max), tri.c, max);
First we create some local variables to work with, all of which are vec3s, and then we store within them the maximum and minimum extents of the triangle. Together, these extents describe a bounding box.
min_size = Math.EPSILON * 2;
for (var i = 0; i 3; i++) {
result[i] = max[i] - min[i];
if (result[i] min_size) result[i] = min_size;
}
To get the dimensions of the bounding box without its world-space position, we subtract the minimum extents from the maximum extents.
There’s an additional consideration, however: if the triangle is axis-aligned, it will have a height, width or depth equal to 0. The problem is, if we create a bounding box with a dimension of 0, it’ll be impossible for that box to intersect another! In order to work around this caveat, here we program a special case to handle a near-0-dimension triangle. If the size in any of the 3 dimensions is less than some very small value (called epsilon), we simply set it to that value. It’s multiplied by 2 to account for the final line in the function:
return vec3.scale(result, 0.5);
Here we simply return half of the size of the triangle. Each node of the BSP tree is defined with a center point, and a half-dimension.
The BSP Object
Now we need to create a constructor which, when instantiated, will make use of these helper functions to build and traverse the BSP tree:
var bsp = function(front, back) {
this.front = null;
this.back = null;
this.triangles = [];
if (front || back) this.set(front, back);
};
/* MORE FUNCTIONS HERE */
return bsp;
Before we go further, note that we’re returning the bsp object. This wraps up our anonymous function and assigns the bsp object to the BSP variable that we defined at the beginning of this tutorial. This allows BSP to be instantiated directly, like so:
var myBSP = new BSP(front, back);
This very simple constructor merely creates a few variables and an array to hold triangles as they are added to the BSP tree. If the node was constructed with a front and/or back element, they are passed into the set() function, which we’ll go over next:
bsp.prototype.set = function(nodeFront, nodeBack) {
this.front = nodeFront;
this.back = nodeBack;
this.center = vec3.create();
var c = 0;
if (nodeFront) {
vec3.add(this.center, nodeFront.center,this.center);
c++;
}
if (nodeBack) {
vec3.add(this.center, nodeBack.center, this.center);
c++;
}
if (c > 0) vec3.scale(this.center, 1.0 / c);
var halfSize = this.calcHalfSize();
var boxPosition = vec3.subtract(this.center, halfSize, vec3.create());
var boxDimensions = vec3.scale(halfSize, 2, vec3.create());
this.box = new Box(boxPosition, boxDimensions);
};
The set() function is responsible for storing the front and back nodes, and then recalculating its center property, which is done by taking the average of the centers of this node’s children. It also recalculates the half-size of this node by calling calcHalfSize() and then rebuilds the bounding box for this node.
bsp.prototype.getHalfSize = function() {
return this.halfSize || this.calcHalfSize();
};
This very simple function simply returns the half-size of this node without recalculating it; an exception is if the half-size hasn’t been calculated yet, in which case it calls calcHalfSize().
bsp.prototype.calcHalfSize = function() {
this.halfSize = this.halfSize || vec3.create();
var min, max;
function calcSide(side) {
var size, cmin, cmax;
if (side instanceof BSP) size = side.getHalfSize();
else size = calcTriangleDimensions(side);
cmin = vec3.subtract(side.center, size, vec3.create());
cmax = vec3.add(side.center, size, vec3.create());
if (min) {
vec3.min(min, cmin, min);
vec3.max(max, cmax, max);
} else {
min = vec3.create(cmin);
max = vec3.create(cmax);
}
}
if (this.front) calcSide(this.front);
if (this.back) calcSide(this.back);
vec3.subtract(max, min, this.halfSize);
vec3.scale(this.halfSize, 0.5);
return this.halfSize;
};
The calcHalfSize() function looks more daunting at first glance than it really is; all it does is get the minimum and maximum extents of each sub-node, and then calculate the minimum and maximum extents of both nodes combined. By subtracting the minimum from the maximum, we’re left with the overall size of the node; scaling that down by half yields the half-size, and we’re done.
bsp.prototype.getTreeDepth = function() { return this.treeDepth; };
The getTreeDepth() function simply returns the maximum depth of the tree starting from the current node, which is calculated by the finalize() function.
bsp.prototype.addTriangle = function(triangle) {
this.triangles.push(triangle);
};
The addTriangle() function simply adds the given triangle to the list of triangles. If you’re using something other than triangles (for instance, an entire vertex buffer object), youll want to add a function to correspond with whatever you plan to use. You’ll also want to tweak the other triangle-related functions to taste.
bsp.prototype.finalize = function() {
var level = [];
for (var i = 0; i this.triangles.length; i++)
level.push(this.triangles[i]);
this.treeDepth = 1;
while (level.length > 2) {
buildLevel(level);
this.treeDepth++;
}
this.set(level[0], level[1]);
this.finalized = true;
};
This function, finalize(), is the last function which will be called when we are constructing a BSP tree. It builds a single, flat level of triangles, then starts a loop. Until the list of triangles has length 2 or less, the helper function buildLevel() is called repeatedly on the list. By the time the list is complete, it’s guaranteed to only have a maximum of 2 elements. We don’t really care whether those elemenst are Triangles or BSP nodes, as all of the special handling is taken care of elsewhere.
Finally, the finalize() function calls set() with the remaining elements in the array, thus making this instance of BSP the ultimate root node. A further optimization might be to check whether level has one or two elements; if it only has one, then we can remove it and assume its children, thus making the tree one node smaller and that much quicker to traverse.
Traversing the Tree
Now that we have a BSP tree, we need to think about how to traverse it. Each node has at most two sub-nodes, front and back, associated with it. That means that if we have a point in space, we can always tell which direction to traverse first: the one closest to the point. In this way, we can guarantee that all of our objects are rendered back-to-front by first traversing the tree down to its leaf nodes, and then rendering as the stack unravels. Here’s an example:
/**
* BSP#traverse(point, renderCallback) -> undefined
* – point (vec3): the position of the camera, used for polygon sorting
* – renderCallback (Function): a callback function to call with each
* leaf node as an argument
*
* Traverses the BSP tree using the given point as a reference; leaf
* nodes will be sent to the +renderCallback+ function in back-to-front
* order.
**/
bsp.prototype.traverse = function(point, renderCallback) {
// handle the (hopefully infrequent!) special
// case of having only 1 child
if (!this.front || !this.back) {
var result = this.front || this.back;
if (result instanceof BSP) result.traverse(point, callback);
else renderCallback(result);
return;
}
// find the distance from front to point, and from back to point
var dist = vec3.create(), frontLen, backLen;
vec3.subtract(this.front.center, point, dist);
frontLen = vec3.dot(dist, dist);
vec3.subtract(this.back.center, point, dist);
backLen = vec3.dot(dist, dist);
if (frontLen backLen) {
// closer to front, traverse back first
if (this.back instanceof BSP) this.back.traverse(point, callback);
else renderCallback(this.back);
if (this.front instanceof BSP) this.front.traverse(point, callback);
else renderCallback(this.front);
} else {
// closer to back, traverse front first
if (this.front instanceof BSP) this.front.traverse(point, callback);
else renderCallback(this.front);
if (this.back instanceof BSP) this.back.traverse(point, callback);
else renderCallback(this.back);
}
};
This is the simplest example I could think of to demonstrate the approach; however, simplicity adds waste, and there are quite a few optimizations that could be made to it. Most notably, it’s a bad idea to recursively call functions during a render pass in JavaScript, because there’s a significant amount of overhead created by function calls. To keep the function calls to a minimum, this should be expanded into a flat loop using some sort of stack. That’s the approach I took in my collision detection algorithm, demonstrated below:
/**
* BSP#collide(other, transform) -> Boolean | Object
* – other (BSP): the potentially-colliding BSP model
* – transform (mat4): a transformation matrix which is used to convert
* +other+ into this BSP’s coordinate space.
*
* Applies the given transformation matrix to +other+; if any triangle
* within +other+ is intersecting any triangle in this BSP tree, then
* a generic object containing the properties +first+, +second+ and
* +second_transformed+ is returned. They have the following meanings:
*
* * +first+ : the colliding triangle in this BSP tree
* * +second+: the colliding triangle in the +other+ BSP tree
* * +second_transformed+: a copy of the colliding triangle in the
* +other+ BSP tree, transformed by the matrix
* to be in this BSP tree’s coordinate space.
*
* If no collision has occurred, +false+ is returned.
*
**/
bsp.prototype.collide = function(other, transform) {
if (!this.finalized) this.finalize();
if (!other.finalized) other.finalize();
// buffer checks for GC optimization
var checks = this.checks = this.checks || [{}];
var check_id = 1;
checks[0][0] = this;
checks[0][1] = other;
var tri = new Jax.Geometry.Triangle(),
a = vec3.create(), b = vec3.create(), c = vec3.create();
while (check_id > 0) {
var check = checks[--check_id];
var first = check[0], second = check[1];
if (first instanceof BSP && second instanceof BSP) {
// both elements are nodes, if they intersect move to the next level;
// if they don’t intersect, let them disappear.
if (first.box.intersectOBB(second.box, transform)) {
while (checks.length - check_id 4) checks.push([{}]);
checks[check_id ][0] = first.front;
checks[check_id ][1] = second.front;
checks[check_id+1][0] = first.back;
checks[check_id+1][1] = second.front;
checks[check_id+2][0] = first.front;
checks[check_id+2][1] = second.back;
checks[check_id+3][0] = first.back;
checks[check_id+3][1] = second.back;
check_id += 4;
}
} else if (first instanceof Jax.Geometry.Triangle &&
second instanceof BSP) {
// first is a tri, keep it to retest against second’s children
while (checks.length - check_id 2) checks.push([{}]);
checks[check_id ][0] = first;
checks[check_id ][1] = second.front;
checks[check_id+1][0] = first;
checks[check_id+1][1] = second.back;
check_id += 2;
} else if (first instanceof BSP &&
second instanceof Jax.Geometry.Triangle) {
// second is a tri, keep it to retest against first’s children
while (checks.length - check_id 2) checks.push([{}]);
checks[check_id ][0] = first.front;
checks[check_id ][1] = second;
checks[check_id+1][0] = first.back;
checks[check_id+1][1] = second;
check_id += 2;
} else {
// dealing with 2 triangles, perform intersection test
// transform second into first’s coordinate space
mat4.multiplyVec3(transform, second.a, a);
mat4.multiplyVec3(transform, second.b, b);
mat4.multiplyVec3(transform, second.c, c);
tri.set(a, b, c);
if (first.intersectTriangle(tri)) {
return {
first: first,
second: second,
second_transformed: new Jax.Geometry.Triangle(
tri.a, tri.b, tri.c)
};
}
}
}
return false;
};
The collision detection is made a little more complicated by the addition of a second BSP, but hopefully it’s not too difficult to understand.
First, we create a stack, which is just an array with a single element. That first element is used to test the root node of this BSP with the root node of the potentially-colliding BSP. If the root nodes don’t intersect, we’re done.
Within the loop, we check whether the nodes to be tested are both BSPs. If they are, and if their bounding boxes are colliding, then each subnode of the first BSP must be compared with each subnode of the second, so 4 more checks are added onto the stack. If they are not colliding, then there’s nothing else to do except move on to the next check in the stack.
If one node is a BSP and the other is a triangle, then we only need to work our way down the BSP’s children and hold onto the triangle for testing against those children.
Finally, when both nodes are triangles, we can convert the second triangle into the first triangle’s coordinate space using the matrix that was passed into the function, and then do a simple triangle-triangle intersection test. If the triangles intersect, then obviously we have a collision.
There are a lot of ways you could code the collision response. I chose to create and return a generic object which contains information about the collision. Since the object evaluates to a non-false value, I can use this to simultaneously check for collisions and then respond to the collision without an extra function call. If you have the CPU performance to spare, you could just as easily fire a callback function or emit a ‘collided’ event instead.
Using the BSP Tree
We’re done coding the BSP tree, so let’s use it!
Let’s say, for sake of argument, that we have a mesh object with a getTriangles() function. Then, we could construct the BSP tree quite simply:
var bsp = new BSP();
var triangles = mesh.getTriangles();
for (var i = 0; i triangles.length; i++)
bsp.addTriangle(triangles[i]);
bsp.finalize();
This will create a new BSP, iterate through the mesh’s triangles, add them one-by-one to the tree, and then finalize it. Finalization causes the single root node to become, well, a tree.
Now that we’ve created the tree, let’s make use of it. Here’s an example of rendering it using our (unoptimized!) traverse() function:
bsp.traverse(camera.getPosition(), function(leaf) {
// render the node
});
And of course, here’s a demonstration of checking for collisions using a mythical second BSP, presumably created in an identical manner to above:
var collision;
var xform = mat4.inverse(mesh.getTransform(), mat4.create());
mat4.multiply(otherMesh.getTransform(), xform, xform);
if (collision = bsp.collide(other_bsp, xform)) {
// collision detected! it’s stored in +collision+
}
In case you’re not very familiar with matrix operations, the inverse of any given matrix is effectively its opposite; since an object’s transformation matrix is used to convert any given point from that object’s local space into world space, the inverse of an object’s transformation matrix will do the opposite, converting from world space into object space. So to test otherMesh against mesh, we combine the transform matrix of otherMesh, which converts otherMesh into world space, with the inverse transform matrix of mesh, which converts world space into mesh’s space. The combination of the two will go straight from otherMesh’s space into mesh’s space, and that’s exactly what we need to perform collision detection. If that was confusing, see this illustration:
Conclusion
Hopefully, this tutorial was informative for you. If you have any questions or comments, feel free to leave them here or on the Jax forums. There are other approaches to segregating scene data, such as using octrees or k-trees, though the others have more trouble replicating one of the major gains to using a BSP tree: the ability to render the scene back-to-front without having to sort the geometry first.
As a side note, octrees seem to have more-or-less replaced BSPs in C programs; I’m still unconvinced that they’re fast enough to replace BSPs just yet in JavaScript, however. In any case, BSPs are still used today for most collision detection, in which they supposedly outperform octrees in most cases. At least, that’s what Google says; I hope to do some benchmarking to come up with more definitive, JavaScript-specific results sometime in the near future.