Given an arbitrary viewpoint in world space, an algorithm to evaluate the list of static objects in the order that occlusion would occur would be useful for the purpose of determining what objects should be rendered and what objects can be culled from the scene. A BSP tree can be used to accomplish this.

The BSP tree is constructed by processing an arbitrary collection of convex polyhedrons. These could be simplified representations of more complex opaque objects, such as a block within a model of a wall, for example. For outdoor terrain, occlusion blocks could also be added to the interiors of hills and mountains.

We start by computing a minimal volume sphere for any object that doesn't yet have one. We then process the list of spheres to find the two that if surrounded by a minimal-volume hull, would result in the smallest object. The idea is to identify the most likely occludable objects first. We'll need the spheres later to perform fast preliminary occlusion tests, but it might not be the way to go to generate the tree.

Once the two objects for the node have been identified, a plane is generated to separate them. The plane and the two objects are a new BSP tree node.

The newly-formed node's objects are joined by computing a minimal-volume convex hull that encloses them, and the resulting object is added to the list of convex polyhedrons being added to the BSP tree.

This process repeats until all of the objects have been divided by planes and a single BSP node remains. The result is a BSP tree with nodes of dividing planes and leaves of static objects in the world to consider for occlusion and rendering.

To render a frame from an arbitrary viewpoint ('X', for example) we start at the root node and determine which side of its plane the viewpoint is on. We descend the tree, checking each node's plane until we arrive at a leaf object. In this case, we will descend to object 5.

We'll check the flags for object 5 and see if contains an occlusion brush for us to use. If it does, and it meets any other criteria that we have set for use of occluders, we put it on the to-be-rendered list and we compute an occlusion beam to use to test future nodes against.

We descend node C's other branch to node B. We test node B's containment sphere against any occlusion beams that we have and determine that it is fully visible, so we check its plane to decide which branch to take and descend to object 4. We already know that object 4's containment sphere is fully visible (because node B was fully visible), so we put the object on the to-be-rendered list, and check to see if it is also an occluder. If so, and we don't have too many occlusion beams in force, we compute an additional occlusion beam based on its occlusion brush.

We descend node B's other branch to object 3 and test it against our list of occlusion beams. We determine that it is fully within one of our occlusion beams and do not process the object further. We ascend the tree to node D and descend its other branch to node A. We test node A's containment sphere against our occlusion beams and discover that it is fully occluded, so we do not process the node further and do not descend either of its branches. In a larger tree, the elimination of a node could result in the culling of a large number of objects.

There are some sticky implementation issues here. First is the method by which object pairs are chosen to generate a BSP node. Second is the method of generating and merging occlusion beams to take advantage of their cumulative effect. Object 3 is occluded by neither beam 1 nor beam 2, but it is fully occluded by both beams. This situation is very common in densely packed environments.

In the context of Quadtree's tile engine, tiles are objects that themselves contain BSP trees of static objects. During the rendering of a frame, entire tiles are culled against the view frustum, and can also be culled against the list of occlusion beams.