Orthogonal BSP tree for Editor

News about the Cafu Engine. Subscribe to the related ImageCafu News feed to stay informed.
Locked
User avatar
Carsten
Site Admin
Posts:2170
Joined:2004-08-19, 13:46
Location:Germany
Contact:
Orthogonal BSP tree for Editor

Post by Carsten » 2009-11-02, 11:29

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:
OrthoBsp04.png
OrthoBsp05.png
OrthoBsp06.png
OrthoBsp09.png
OrthoBsp11.png
OrthoBsp14.png

Best regards,
Carsten
scott
Posts:173
Joined:2004-08-23, 09:11

Re: Orthogonal BSP tree for Editor

Post by scott » 2009-11-02, 22:43

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

I take it the old BSP just wasnt doing the job.
User avatar
Carsten
Site Admin
Posts:2170
Joined:2004-08-19, 13:46
Location:Germany
Contact:

Re: Orthogonal BSP tree for Editor

Post by Carsten » 2009-11-03, 11:39

Hi Scott,
scott wrote:wow this is interesting. What sort of speed difference does it make at compile time? :mrgreen:
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. :D

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. :up:

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.
Best regards,
Carsten
Locked

Who is online

Users browsing this forum: No registered users and 5 guests