3D Binary Space Partitioning со сплошными / пустыми листьями - PullRequest
Новая
       81

3D Binary Space Partitioning со сплошными / пустыми листьями

1 голос
/ 28 апреля 2020

Я недавно начал изучать 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 псевдокод raycast: 

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

Эта система, однако, требует использования определения пересечения луч-треугольник, что является дорогостоящей процедурой. Хуже всего то, что существует вероятность того, что треугольник, по которому вы итерируете, будет пропущен лучом, что приводит к относительно большому количеству дорогостоящих радиопередач, которые необходимо выполнить, прежде чем найти ближайший удар в триме sh.

Какие методы я могу использовать для оптимизации структуры и прохождения BSP?

...