A Planar BSP is what people usually think about when someone mentions a BSP tree. In a planar tree, you can effectively ignore the leaves for rendering purposes. You start with all of your polygons in one bucket, choose one via some heuristic, take that polygon and all polygons that a coplanar to it, create a BSP node, split the rest into two buckets and repeat until you have no polygon lying free in any bucket. Traversal of a Planar BSP from front-to-back is basically a variant on a standard binary tree inorder traversal.

void PlanarBSPNode::planar_ftb(const Point & point) { int near = (point dot node.plane_normal >= 0.0); if (child[near]) child[near]->planar_ftb(point); for each polygon facing the near node in this plane { polygon->render() } if (child[near^1]) child[near^1]->planar_ftb(point); }

Note: The 'render' routine for translucent polygons or polygons with transparencies places the polygons on a stack, which is popped away and rendered at the end of the frame.

A Leafy BSP is a useful data structure, often used by portal advocates as a quick-and-dirty means to obtain a portal set for arbitrary geometry. In addition to splitting as you walk down the BSP tree you then need to walk back up the BSP tree splitting the contents of the parent planes as you go. Afterwards you can organize the clipped polygon fragments into their assorted leaves. When this is done you no longer track which polygons lie in a given plane of the BSP tree, but instead you track which polygons act as faces for the individual BSP nodes.

class LeafyBSPCommonParent { // you can do this with typecasting and structs if need be. .... void leafy_ftb(const Point & point); } void LeafyBSPNode::leafy_ftb(const Point & point) { int near = (point dot node.plane_normal >= 0.0); child[near]->leafy_ftb(point); child[near^1]->leafy_ftb(point); } void LeafyBSPLeaf::leafy_ftb(const Point & point) { for each polygon that forms a face that faces into this node { polygon->render(); } }

If you are using a front-end rasterization routine like passing directly to hardware, an S-Buffer, Active Edge List, or Active Edge Heap, then there is little purpose to splitting the polygons as you walk down the BSP tree. Simply make a second reference to it in the compiler and all is well. If you allow multiple references to a given polygon to float around the tree you can simply adjust the polygon rendering routine to keep a frame index counter like the following:

void Polygon::render() { if (last_seen != frame_no) { last_seen = frame_no; ...do rendering here... } }

The walk does not provide front-to-back ordering of the polygons. However in many cases you do not need this. It may cause additional overhead when dealing with translucent polygons (which will need to be sorted back to front). Since this walk will not provide front-to-back ordering in any event, there is little point in doing the scene traversal inorder. Quake gets away with much this same approach, by just taking the nodes from the potentially visible set and throwing their contents down the pipeline at the Active Edge List or openGL hardware.

In this case, the purpose of the BSP then is to provide convex subregions and to serve as an aid to collision detection. It does not serve any ordering function for visitation.

A convex node engine only allows a convex polyhedron to act as a node. Portals serve to connect individual nodes. Within a convex node engine it is quite possible to get perfect front-to-back ordering.

A concave node engine allows just about anything to serve as a node. It could be a room with some complex geometry, a BSP tree, an undulating mass of procedurally generating flesh, etc... A concave node engine does not lend itself to easily providing front-to-back ordering. As such it is really only suitable to frontend rasterizers such as hardware, S-Buffers, Active Edge Lists and Active Edge Heaps, like the Quake BSP approach above.

The most obvious portal traversal is recursive. The algorithm is generally implemented something like the following:

void Node::visit(PortalSilhouette & silhouette) { if (last_seen != this_frame) { last_seen = this_frame; for each polygon do { if (s->is_a_portal) { Silhouette s = clip polygon using silhouette planes next if s is empty. s->remote_node->visit(s); } else { Polygon p = clipped polygon using silhouette planes p->render(); } } } }

I cannot emphasize enough how poorly this algorithm scales up to higher polygon counts. You may wind up visiting a node several times because you reach it through different nodes, and because of the recursive clipping you may have to render each polygon in multiple discrete fragments. This engine is usually built because it seems to show promise when your engine is just a few rooms. This algorithm is designed to work with convex nodes.

In an effort to fix the problems with the previous algorihm, another common variant that works if the nodes are obtained from a BSP tree is to use the BSP key for a given node and viewpoint to provide a sorting criteria. This assumes that the data structure used is roughly similar to that for the Leafy BSP above with the addition of portal information for the empty faces shared with neighboring nodes. The concept of sorting by a BSP key is introduced in Michael Abrash's Black Book.

This walk involves a small binomial heap (priority queue) or sorted list of nodes not yet visited but adjacent to ones visited and visible. The contents of the queue are pulled off in front-to-back order, the nodes are rendered and checked for visible neighbors, which are then placed on the priority queue sorted by their BSP key.

There are two forms of BSP keys that I have used. One can be generated by walking the BSP tree inorder from a given viewpoint while incrementing a counter at each leaf. The other can be created by walking down the BSP tree towards a given node and by recording as a bitstring every place where the side of the plane the eye resides on differs from the side the given node lies on. Two of these bitstrings can be compared to determine if a given node is nearer to the viewer than the other.

Note even though this uses a BSP tree for sorting it is technically a portal algorithm because it traverses into its neighbors through the portals. The advantages this holds over Recursive Traversal is that a given node is only rendered once. The disadvantage is the cost of computing the keys.

The simplest algorithm here for traversal is to allow anything to be in a node and to maintain a potentially visible set between concave nodes. The traversal is identical to the Quake BSP traversal above. Collision can be much harder to detect and handle; Collision detection is very important in a game, so consider this solution with care. Other issues include detecting what node you are presently in in the absence of convex boundaries. Usual fixes include declaring the node to be convex in shape but containing arbitrary geometry. This is a nice fast-and-loose algorithm for getting polygons on the screen though.

for each node in the PVS for the viewpoint { node->render(); }

One could also use convex nodes for this algorithm which would improve collision detection and may offer other benefits to AI and software rendering, but this still leave determining the current node as a potential problem, if you have no a priori knowledge of the container for a point.

Hierarchical traversal of an octree is based on the same plane separation principle that makes a BSP front-to-back walk work. In this case, think of a single node with its eight children as mimicking 3 levels of a BSP tree:

z plane / \ y plane y plane / \ / \ x plane x plane x plane x plane

All of the BSP traversals above will then work on the octree just as well as they will on a BSP tree itself. However, observation can simplify some of these traversals. Given which side of the 3 planes subdividing an octree node that the eye point is on you can perform a simpler traversal based on bit toggling. You have three planes and thus 3 sign bits. If you toggle any one bit you will get one of the 3 nodes which share a face with the leaf in question. If you toggle all 3 bits you will get the node in the far corner of the octree. Given this you can simply walk a given octree node from front-to-back by the following sequence.

octree_node::hierarchical_ftb(Point & eye) { int first = ((eye.x() < avg_x()) ? 1 : 0) | ((eye.y() < avg_y()) ? 2 : 0) | ((eye.z() < avg_z()) ? 4 : 0); child[first].hierarchical_ftb(eye); child[first^1].hierarchical_ftb(eye); // toggle bit 0 \ child[first^2].hierarchical_ftb(eye); // toggle bit 1 these 3 can be in any order child[first^4].hierarchical_ftb(eye); // toggle bit 2 / child[first^3].hierarchical_ftb(eye); // toggle bits 0 & 1 \ child[first^5].hierarchical_ftb(eye); // toggle bits 0 & 2 these 3 can be in any order child[first^6].hierarchical_ftb(eye); // toggle bits 1 & 2 / child[first^7].hierarchical_ftb(eye); // toggle bits 0, 1 & 2 }

This walk has the benefit of simplicity. On the other hand it incurs the overhead of walking through the hierarchy for the traversal.

Neighbor Traversal requires some minor slight addition to the octree definition:

class octree_common { ... int last_seen; ... } class octree_leaf : public octree_common { ... octree_common * neighbors[6]; ... }

These six pointers represent the node that lies adjacent to this leaf through any of its six faces.

If you are deeper or of equal depth in the tree than the neighbor is then one or many little nodes will point into the same same-sized or larger adjacent node through a common face. If you are at the same height as the neighboring node you will both share the common face on a 1:1 correspondance.

If you are higher in the tree then your one face will abutt have many leaves_ on the one side of you. This is perfectly acceptable, and in this case you will not attach to the leaf, but to the parent or grandparent node that is at the same height as you in the tree. This is why the links are of an octree_common type xrather than an octree_leaf.

To traverse from front-to-back through this kind of scene is virtually identical to the Keyed Queuing approach mentioned in the Portal section above. The primary change required is when you link from a leaf to a parent node through a common face, you need to recursively walk down checking the 4 children that share that face's corresponding face for visibility.

There are some consequences to the modifications that this requires to the data structure. First of all, the neighbor links can become quite onerous to maintain if your octree is rapidly changing. Secondly, your traversal is now complicated by a priority queue and other data structures which may complicate development.

Hierarchical traversal of a kd-tree is identical to hierarchical traversal of an octree as described above or to a front-to-back traversal of a BSP tree.

Neighbor traversal of a kd-tree can be performed in a similar manner to the neighbor traversal of the octree above, but it is not as effective. The reason is because the faces of the octree children at a given level all line up perfectly. In the kd-tree using the figure above, the two y aligned planes are likely to have chosen different offsets to split upon. This means that the neighbor traversal winds up severely handicapped as the traversal algorithm has to walk down to the leaf from a higher level node as the norm rather than the exception, unlike the octree neighbor traversal.

An adaptive octree is an octree which allows the position of the split point in the center of an octree node to be displaced. In practice, I tend to prefer a kd-tree to an adaptive octree, but in some cases, the adaptive octree may consume less memory. In addition, the neighbor front-to-back traversal of an adaptive octree tends to be faster than for a kd-tree, because within a given octree node the partitioning planes line up.