The Im­pact of BSP Tree Con­struc­ti­on on Oc­clu­si­on Cul­ling Per­for­mance: A Com­pa­ri­son of Com­mon BSP Tree Im­ple­men­ta­ti­ons

Binary Space Partitioning (BSP) Trees are a well-established spatial data structure used in computer graphics for visibility determination and occlusion culling. Their performance depends strongly on the selected hyperplanes during BSP tree construction. Existing approaches to hyperplane selection rely on fixed algorithms that optimize criteria such as tree balance, polygon fragmentation, or traversal cost.
This thesis investigates the use of artificial intelligence for hyperplane-selection. Multiple approaches will be developed and compared to established, algorithmic methods. The evaluation will consider both tree quality and rendering efficiency of the resulting BSP trees. Tree quality will be measured by the construction time, memory usage, polygon fragmentation and tree balance. Rendering efficiency is determined by the number of node visits, the amount of visibility tests, and the culling efficiency and will be measured during runtime. To ensure a fair comparison, all construction methods will be evaluated on multiple scenes with differing amounts of objects and occlusion.
The objective is to determine whether artificial intelligence can provide improvements to BSP tree construction and to show the differences to classic approaches.