在 BSP 树中生成每个对象组合（无重复）

Question

我正在使用 Binary Space Partitioning Tree。我有两种对象：

需要检查与其他对象的碰撞的动态对象（角色、射弹），
静态对象（如墙）未进行相互碰撞测试，只能针对动态对象进行测试。

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

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

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

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

                                                                \
List of dynamic objects : {dynA, dynB}            Tree :       dynA
                                                              /    \
                                                          static1  dynB

测试组合：

~~dynA - dynA~~ （处理无用的情况）
动态A-静态1
dynA - dynB
dynB - dynA（同上）
动态B-静态1
~~dynB - dynB~~

为了跳过无用的检查，我想在每个对象上添加一个属性 Order ：它将是在构造对象时给出的唯一标识符并使用 like所以 :

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

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

我的问题是：如果这种技术是正确的（我的意思是它是一个好的设计吗？），并且由于每个对象在 C# 中都有一个唯一的引用，我可以直接比较它们的引用吗:(?)

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

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

Answer 1

我会好好看看 Quake/2/3 如何处理这个问题。您可以在此处考虑一些优化：

1) 使用立方子体积作为 3 维网格来缓存每个实体所在的 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

在 BSP 树中生成每个对象组合（无重复）

Generate every combination of objects (without duplicate) in a BSP Tree

c#

tree

collision-detection

bsp-tree