Binary Space Partitioning FPS with CAD level editor from scratch.

Chopping out polygons at the right place in order to construct balanced binary trees might be an exhausting task.

The results are promising even though I still end up with some concave polys that are not properly processed. I’ve coded simple algo that takes the decision where to split each poly/polyline recursively using a rating system. It evaluates each polyline part of a polygon and takes decision if it’s a good splitter for the rest of the polylines within the given tree node (simply a range of polylines laying inside an already split space).

The binary partitioning itself might be from simple to quite complex depending on the result you are targeting. In my case I didn’t aimed for solid leaves which simplified the process.

The visible surface determination (VSD) is probably the main benefit of the BSP Tree when it comes to the rendering part. You however can use it for way more than that, a collision detection for instance.

However here is a ruff visualization of the final result of the VSD which demonstrates the process of cancelling out all non visible surfaces from the rendering process.