1
\$\begingroup\$

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[0]) // Generates the plane position and normal of the node
loop (Triangle tri : mesh)
   if (onPlane(tri, node))
      node.triangles.add(tri)
   else if (inFront(tri, node))
      front.add(tri)
   else if (Behind(tri, node))
      back.add(tri)
   // 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))
            front.add(tri)
         else if (Behind(tri2, node))
            back.add(tri)

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?

Improve this question
\$\endgroup\$

0

Reset to default

You must log in to answer this question.