# 3D Binary Space Partitioning with solid/empty leaves

I've recently started looking into BSPs for real-time collision detection, and I'm now looking into improving the performance of my solution.

The system that I've implemented is rather similar to the solution found on wikipedia (https://en.wikipedia.org/wiki/Binary_space_partitioning), where each node contains triangles found located on the node's hyperplane, and references to two nodes found on each side of the hyperplane.

BSP generation pseudocode:

Node generate_bsp(Trimesh mesh)
Trimesh back, front
Node node(mesh) // Generates the plane position and normal of the node
loop (Triangle tri : mesh)
if (onPlane(tri, node))
else if (inFront(tri, node))
else if (Behind(tri, node))
// Not fully in front or behind means that the triangle is found on both sides
// and needs to be split
else
Triangle[] trisSplit = tri.split(node)
loop (tri2 : trisSplit)
if (inFront(tri2, node))
else if (Behind(tri2, node))

node.nodeBack = generate_bsp(back)
node.nodeFront = generate_bsp(front)

return node


This means that for a raycast, I iterate over the hyperplanes sorted from front to back, and determine if my ray hits any of the triangles found on each hyperplane.

BSP raycast pseudocode:

Bool ray_intersect_bsp(Vector rayPos, Vector rayDir, Node* BSP)
if (BSP == null)
return false

if (onPlane(rayPos, node))
if (ray_intersect_triangles(rayPos, rayDir, BSP->triangles))
return true
if (ray_intersect_bsp(rayPos, rayDir, BSP->nodeFront))
return true
if (ray_intersect_bsp(rayPos, rayDir, BSP->nodeBack))
return true
else if (inFront(rayPos, node))
if (ray_intersect_bsp(rayPos, rayDir, BSP->nodeFront))
return true
if (ray_intersect_triangles(rayPos, rayDir, BSP->triangles))
return true
if (ray_intersect_bsp(rayPos, rayDir, BSP->nodeBack))
return true
else
if (ray_intersect_bsp(rayPos, rayDir, BSP->nodeBack))
return true
if (ray_intersect_triangles(rayPos, rayDir, BSP->triangles))
return true
if (ray_intersect_bsp(rayPos, rayDir, BSP->nodeFront))
return true

return false


This system however demands using ray-triangle intersection determination, which is a costly procedure. What makes matters worse is that there's a high chance that the triangles you iterate on are missed by the ray, which results in a relatively large amount of costly raycasts that need to be performed before finding the closest hit on the trimesh.

What methods can I use to optimize my BSP structure and traversal?