用于冲突检测实现的四叉树

Question

我正在尝试为我的3D环境创建一个四叉树（所有元素都在平坦的地形上，因此它们可以用2D数据表示），但我对它的精细部分的实现有点迷路。

我将首先描述我当前的四叉树，然后讨论它的缺陷，然后提出问题。

我目前拥有的是一个四边形树，它接受一个非常具体的矩形，我在其中定义了x，z，宽度和前向。以下是我的操作概述。

将对象插入四元树：

检查当前节点是否有子节点。如果是，请检查对象是否能够完全适应四个节点中的任何一个。如果可能，递归并重复。如果对象不完全适合四个节点，或者根本没有节点，它会将其添加到std向量中，然后检查是否应该拆分。如果拆分，则将其拆分并将当前对象拆分为各自的节点。

从四叉树中删除对象:

检查对象是否在当前节点内。而不是转移到孩子身上。如果找到，则从矢量中弹出对象。

更新四叉树：

移动和静态对象存储在不同的四叉树中。移动四叉树将始终删除已移动的内容并重新插入。静态四叉树只是冷了。

检索对象

首先找到它属于四个节点中的哪一个，然后递归移动，获取节点的所有当前对象，并将其添加到最后返回的向量中。

我的缺点是：不是所有的矩形都位于叶子上。我不知道应该如何处理节点之间相交的节点。这也使得四叉树中的碰撞检测检查有点愚蠢；为什么我需要在父节点中放置矩形？我对检索对象函数非常不满意。

我的第二个缺点是我只能接受一个矩形。虽然这在制作四叉树和调试它时很有用，但我想继续，能够直接将我的对象放入游戏中。

因此，这是我读过的Quadtree for 2D碰撞检测的问题。一切似乎都足够好了，直到“对象可以属于四边形树内的多个集合。你将需要在四边形之外有一个额外的线性集合来枚举每个对象，而不会有重复项。

我不知道这意味着什么，也不知道该怎么做。碰撞检测的操作似乎也比我目前拥有的要好得多。我想知道他是什么意思，以及它是如何做到的。

我的第二个问题是关于将对象插入到树中。我在游戏中的所有对象都是基类的一部分。我应该让它们直接添加基类吗？或者我应该将对象转换为矩形，然后添加指向对象的指针？我也正在为我的游戏加载一些模型，它们被拉伸并由glScalef（）使用。因此，在缩放后获得模型的缩放和位置似乎非常困难（但可能）。

另一方面，我之所以缩放模型，主要是因为我基本上是在为迷宫游戏制作墙壁。所以我需要它们完美地配合在一起，而我不能在玛雅上进行数学运算。

Answer 1

你可以试着用莫顿曲线来寻找重叠区域。我还认为你需要一个八叉树：http://dmytry.com/texts/collision_detection_using_z_order_curve_aka_Morton_order.html.以下是重叠对象的示例：https://books.google.fr/books?id=1mu099DN9UwC

Answer 2

如何使用四叉树进行3d？也许你指的是2d？因为通常八叉树用于3d。关于你的第一个问题。你的对象可能属于四叉树中的几个四边形。当你检索对象的时候，你需要检查碰撞，你只需要检查你是否已经检测到两个对象之间的碰撞，如果你已经检测到了，你就不要再做检测来绕过重复。例如，在一个四边形中有两个对象。你检查第一和第二之间的碰撞，然后检查第二和第一之间的碰撞。您需要检查之前是否已经检测到这个碰撞。

请尝试阅读此链接了解详细信息。