c++ - 根据世界位置在一维数组中查找通用项目？

Question

我有一个数据数组(通用顶点数据)。我需要能够根据位置搜索数组的元素。目前，每个顶点元素都记录自己的位置，我只是使用 for-loop 来搜索每个元素并比较位置。我必须在我的程序中经常这样做，而且它对性能非常关键。遍历每个元素似乎真的非常低效。

顺便说一句，我使用 C++。

我的问题是:有没有更好的方法？也就是说，有没有一种方法可以直接根据 3D 位置访问必要的元素？这些职位是整数，所以这可能会有所帮助。

我考虑过简单地使用 3D 数组(即顶点[256][256][256])，但我不能承受浪费的内存，因为只有大约 30-50% 的顶点位置实际上包含一个顶点。也许这可以通过指针来实现？他们在未分配时是否使用内存？

3D 数组的另一个问题是顶点可以分布在几乎无限的区域中，这将构成一个非常非常大的数组。此外，顶点可以有效地动态添加，这意味着它们可以添加到 <0 位置，这意味着数组必须向后移动并重新分配每个元素。

如果有人有任何建议，我将不胜感激:)

Answer 1

八叉树可能是基于体素的地形(或相关模型)的最佳解决方案。八叉树的基本概念由节点和叶子组成。每个节点(和叶子)代表立方体空间，每个节点包含 8 个子节点(或叶子)，这样每个子节点占用其父节点空间的 1/8(参见 picture)。

叶子与节点的不同之处在于没有更多的子节点但包含数据本身 - 在您的例子中是顶点数组。

八叉树的深度由您决定，它实际上取决于地形的详细程度。现在，如果您想将顶点组织到树中，对于每个顶点，您将首先将其发送到主节点(树的根节点，即包含所有其他节点)，然后主节点将确定该顶点属于哪个子节点基于一个职位。然后递归传递顶点，直到它到达存储在数组中的叶节点。

为简单起见，这里是四叉树的二维示例:

                (4,4)
-----------------
|   3   |   4   |
|       |       |
-----------------
|   1   |   2   |
|       |       |
-----------------
(0,0)

假设地形的大小是 4x4。在这个例子中我们只使用主节点作为包含叶节点的节点。如果我们现在有顶点让我们说 (0.2, 3.2) 。顶点被传递到根节点。由于 0.2 < 4/2 和 3.2 > 4/2 ，节点将顶点发送到叶子编号。 3 存储位置。如果您要搜索空间(或本示例中的平面)中的位置，您将按照与描述的存储类似的方式进行搜索。

在您的实现中，您可以使用指针表示节点的子节点/叶子。如果你想优化空间，你根本不需要存储每个节点的尺寸和位置，而是隐式地说每个节点的尺寸是 1x1x1，然后在传递之前相应地转换每个顶点。IE。你有大小为 1000x1000x1000 的地形和位置为 (600,600,100) 的顶点。现在将位置除以大小，得到传递给节点的位置 (0.6,0.6,0.1)。由于 0.6 > 1/2 和 0.1 < 1/2，您将相应地将它传递给节点，但在您对其进行转换之前，它再次通过从高分量中减去 1/2，然后将所有分量乘以 2(因为子节点在所有维度上都小两倍)到获得位置 (0.2, 0.2, 0.2)，您将传递给它……等等。但是，这有点高级，因为您每次使用树时都需要依靠它。

在 Internet 上很难找到关于该主题的教程，但有许多实现可供学习。这是我发现的一对:

http://www.flipcode.com/archives/Octree_Implementation.shtml https://github.com/brandonpelfrey/SimpleOctree

还有一个实际的教程(但是很重): http://www.xbdev.net/maths_of_3d/octree/tutorial/