Last week we completed a new BSP tree implementation for the Cafu World Editor CaWE: The new BSP tree is orthogonal, meaning that it only uses axis-aligned planes for its split planes, so that it can be build, updated and traversed very quickly.

The new tree is used for accelerating the 3D rendering, that is, culling the map elements against the camera view frustum quickly and for sorting them front-to-back or back-to-front (for translucent surfaces).
In the future, the new BSP tree implementation can be used for other purposes as well, such as accelerating ray traces through the world.

For development and debugging, we've also added some code to CaWE that optionally visualizes the BSP tree split planes graphically. Here are some screenshots from the TechDemo map:

wow this is interesting. What sort of speed difference does it make at compile time?

I take it the old BSP just wasnt doing the job.

Hi Scott,

scott wrote:

wow this is interesting. What sort of speed difference does it make at compile time? I take it the old BSP just wasnt doing the job.

Well, please note that this is the run-time BSP tree internal to the editor CaWE. Just like the Cafu engine itself, the editor needs a tree for organizing the map elements. The old tree implementation was an "Octree" whose implementation was clumsy and very limited in features. While the old Octree provided basic view frustum culling, it also required cumbersome and intricate maintenance (e.g. when map elements were transformed, moved or otherwise edited). The new tree comes with more powerful culling facilities, is much easier to maintain (updates requires much less code now as they are essentially automatic; only inserting new elements and deleting old ones requires explicit calls), and allows for sorting the map elements front-to-back (as required for opaque elements) and back-to-front (as required for translucent elements) in linear time.
The performance that we obtained from the new tree is in fact very good.

The map compilers, especially CaBSP, continue to build their even more sophisticated, fully generic BSP trees (not limited to orthogonal split planes), that are augmented with lots of additional data that is used by the engine core. However, we indeed obtained some insight from the CaWE tree implementation that can help to make CaBSP generate faster trees in the future.

By the way, the Cafu physics worlds have yet another BSP tree structure of their own, which however is very similar to the one used in CaWE and shown in the images above.