生成BSP树中每个对象的组合(不重复)

本文关键字：组合 对象 BSP 生成 | 更新日期: 2023-09-27 18:07:33

我正在制作一个碰撞检测系统二叉空间分区树。我有两种对象:

  • 需要检查与其他物体碰撞的动态对象(角色、弹丸)，
  • 静态对象(如墙壁)，这些对象不会被测试彼此之间的碰撞，但只能针对动态对象进行测试。

为此，我使用了两种数据结构:用于存储所有动态对象的列表，以及包含所有对象(动态或静态)的BSP树。因此，每个动态对象都存储在这两个结构中。

最后，我通过循环列表并使用树来测试每个对象来执行碰撞检测，如下所示:

foreach(DynamicObject dynobj in myListOfDynamicObjects)
{
    //check the collision against every close dynamic or static objects
    myBSPtree.CheckCollision(dynobj);
}

然而，在这一点上，我没有想到一些事情:两个动态对象之间的每次碰撞检查都要进行两次。例如:

<>之前＼动态对象列表:{dynA, dynB}树:dynA/'static1 dynB之前

测试组合:

  • dynA - dynA(无用的情况处理)
  • dynA - static1
  • dynA - dynB
  • dynB - dynA(同上)
  • dynB - static1
  • dynB - dynB

为了跳过无用的检查，我想到在每个对象上添加一个属性 order :它将是在对象构造时给出的唯一标识符，并像这样使用:

if(dynA.Order < dynB.Order){ CheckCollision(dynA,dynB); }

这样，对每个对象的组合只进行一次碰撞检查。

我的问题是:如果这种技术是正确的(我的意思是它是一个好的设计吗?)，并且因为每个对象在c#中都有一个唯一的引用，我可以像这样直接比较它们的引用吗:(?) 
if(dynA.Reference < dynB.Reference){ CheckCollision(dynA,dynB); }

可以使用object。ReferenceEquals查看两个引用是否相等，但是我们可以对这些引用进行实际比较吗?

生成BSP树中每个对象的组合(不重复)

我会好好看看Quake/2/3是如何处理这个问题的。这里有一些您可以考虑的优化:

1)使用立方子体积作为三维网格来缓存每个实体所在的BSP区域。这样，您只需要针对整个树的一个子集测试每个动态对象。这是一个巨大的性能改进，因为你的BSP树的大小增长。

这是我的实现，从Quake2中借用，并为可读性进行了大量修改:

https://github.com/jdolan/quetoo/blob/master/src/server/sv_world.c

2)为了避免重复的碰撞检查，只需在主碰撞入口点上引入一个计数器，并在每次调用函数时增加它。测试给定对象时，将其自身的碰撞计数器设置为当前计数器值。在做任何工作之前检查该值。这就是Quake避免两次检查相同BSP节点的原因。

if (obj->collisionCounter == _collisionCounter) {
    return;
}
obj->collisionCounter = _collisionCounter;

如果你希望你的碰撞代码是线程安全的，确保你有一个碰撞上下文结构为所有的碰撞参数和状态，并传递该结构的一个实例到所有的碰撞函数。当然，在那个结构体中实现collisionCounter。顺便说一句，Quake将这种结构称为trace_t。如果有帮助的话，这里是我的:

https://github.com/jdolan/quetoo/blob/master/src/collision/cm_trace.c

相关文章：