LordHavoc's BSP Tree Article I originally began to write this as merely a short intro to BSP trees in an email reply, but it quickly grew to be an entire article.

To begin, lets follow the process of BSP tree building...

You have a single non-solid world, with a lot of polygons, now you find the largest polygon (or preferably the one that intersects the least), and you declare that the world is now split in two along that plane, you've just entered node 0 into the BSP tree.

Now there are two worlds, side A, and side B, lets say this was a floor polygon in a room with a Z (altitude) value of 96, then that means there is now the world above 96, and the world below 96, they are seperate spaces, that polygon is now encoded and ignored for the purposes of finding the next largest polygon, lets say the next largest polygon is a wall of the room, you classify the wall polygon as to which side of node 0 it is on, if it is below 96 you say it is child[0], if it is above, you say it is child[1], if it intersects (overlaps) you split the polygon in half along the intersection and add the respective halves to each of the two children (sides), you now have nodes 0, 1, and possibly 2 (if it intersected and therefore was added to both sides), this continues until you run out of surfaces.

If you want to know the bounded area for a particular leaf node (only the leaves have the polygons, at this point, Quake's engine is another story which I'll get back to), you could pretend you have an infinite solid space, and you clip it by the leaf node and it's parents, going back up the tree (the leaf itself is merely a wall facing into the space), now you have a convex area (convex meaning it has no dents, essentially, as opposed to concave), this convex area can be said to have a particular content value (CONTENTS_SOLID, for example), and you can do all sorts of useful things with it.

That was merely a little excursion into theory, now back to the more efficient world of Quake...

Consider that a leaf node (which is always the last surface defining an area) has a contents value, a leaf node does not need a valid splitting plane or children because it is never meant to be recursed past (it does need a valid parent however, for backing out of the tree), when the pointcontents code (SV_HullPointContents code in world.c) wishs to know what node a point belongs to, it simply recurses down the tree, choosing the appropriate children, until it finds a leaf node (leaf nodes are the only ones that have content values, after all), then returns that node.

Now think about how to trace a line through this space (SV_RecursiveHullCheck in world.c), you check if the node plane intersects the desired line segment, if it does, you check if the other side is CONTENTS_SOLID (that child is a leaf node... like before), and if so, you've found the impact point, and return that point, otherwise, go down the relevant side (or sides if it intersects) of the tree recursively, note that this should be done 'front side first' (meaning if it intersects the plane, the side facing the start point of the trace should be followed first), so that you find the nearest impact point. (rather than the farthest, or a chaotic choice inbetween) This principle can also be used for rendering the BSP tree front to back or back to front. (Quake does this, although it does not use it for visibility purposes like Unreal does - more on this later)

Now, a little explanation about how planes (infinite surfaces) are stored, a plane is a direction (surface normal), and a distance from origin (0 0 0), the reason it is stored like this (rather than a triangle, or polygon), is because it is very efficient (in speed and space), and there is an implicit infinity to it's dimensions. Implementation note: to calculate the plane for a polygon, you calculate the normal (normalized cross-product of the distances from point 1 to point 0, and point 1 to point 2), then use a DotProduct(point0, normal) to get the distance. (for that point; if these distances mismatch eachother, you've got a non-planar polygon (a triangle can never be non-planar), which is invalid, but that's a little off-topic)

Now lets say we want to classify a box (rather than a point) as being in a particular node (this is used by Quake for visibility purposes, to know if an object is visible to the player), it proceeds similarly to point checking, except that you are checking the box's corners against the plane, if all are one one side, you know to go down that side, however if some are on one side, and some on the other, you have found the deepest node in the tree before splitting would occur, for visibility purposes you stop here (if this node is visible, then the model is reasonably close to being in the view), however if you were checking to make sure a monster was not in a solid (or is in water, or whatever), you would make a clipped copy of all the vertices (clipping them by simply offseting them back by how far they exceed the plane distance in the plane normal direction - this is why I explained how planes are stored), then continue downward recursively, until you found out that a vertex of the clipped bounding box was on a CONTENTS_SOLID side of a node (that is to say, the child on that side is a leaf node, and therefore has a content value, in this case CONTENTS_SOLID), and thus declared the monster as being in an invalid position. (obviously this should never happen, but spitting out an error message might be appropriate)

As you probably realized when that got complicated (clipping), you can classify any number of points. Therefore you could clip movement to any planes that clip the vertices defining the move box. This can be used to solve the very hacky bounding box issues in quake. (if you've ever tried to write a crouching mod, or made a monster the size of Chthon who could actually move around, you'll understand the problem I'm talking about - Quake only understood 3 sizes!)

Additionally this could easily be a rotated object.

Side note:
The visibility engine in Quake (as mentioned briefly at the end of the pointcontents paragraph) is very fast - Quake knows which nodes are visible from the node the eye is in (this is precomputed when compiling the map) and only renders the polygons belonging to nodes that are visible... Unreal has to do this determination manually at great cost - this is why Unreal and Unreal Tournament have slightly lower polygon maps (although map size is not an issue in Unreal, that is unrelated to the visibility engine - it's actually because quake splits surfaces into smaller fragments for lightmap purposes, and also splits heavily based on the BSP tree, thus suffering from ever climbing polygon counts, but that is getting off-topic), however that does allow Unreal engine to easily do something very interesting - portals leading into other unrelated parts of the map, you could easily be walking through a hall and never know you walked through one of these silent teleporters... This actually can be done in Quake (and done better than Quake3 did), however the compiling utilities would have to be modified to support going through portals of that type for visibility purposes, and the engine would also need to be modified to support it.