1

我最近开始研究用于实时碰撞检测的 BSP，现在我正在研究提高我的解决方案的性能。

我实现的系统与维基百科（https://en.wikipedia.org/wiki/Binary_space_partitioning）上的解决方案非常相似，其中每个节点都包含位于节点超平面上的三角形，以及对找到的两个节点的引用在超平面的每一边。

BSP生成伪代码：

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

这意味着对于光线投射，我遍历从前到后排序的超平面，并确定我的光线是否击中每个超平面上找到的任何三角形。

BSP 光线投射伪代码：

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

然而，该系统需要使用射线-三角形相交确定，这是一个昂贵的过程。更糟糕的是，您迭代的三角形很有可能被射线遗漏，这导致需要执行相对大量昂贵的射线投射，然后才能找到最接近修剪的命中。

我可以使用哪些方法来优化我的 BSP 结构和遍历？

4

0 回答 0