1

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

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

我的问题是：有更好的方法吗？也就是说，有没有办法直接基于 3D 位置访问必要的元素？这些位置是整数，所以这可能会有所帮助。

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

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

如果有人有任何建议，我将非常感激:)

4

2 回答 2

2

您可能考虑的一个解决方案是使用稀疏网格作为您的 ADT。

这std::unordered_map是一个哈希映射，可用于创建稀疏网格数据结构。如果你为 3d 向量编写了一个好的散列，你可以获得很好的 O(1) 读取性能，这将接近原始数组的性能。

散列映射还允许您使用“几乎无限”的区域（当然，约束将在基础数据类型中。

抱歉耽搁了。

对于 unordered_map，这是一个很好的信息资源：unordered_map hash function c++

我在自己的项目中使用一对整数实现，但我确信它可以用于三维坐标。

namespace std {
    template <class T>
    inline void hash_combine(std::size_t & seed, const T & v) {
        std::hash<T> hasher;
        seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
    }

    template<> struct hash<pair<int, int> > {size_t operator()(pair<int, int> x) const { size_t seed=0; hash_combine(seed, x.first); hash_combine(seed, x.second); return(seed); } };
}

然后你可以声明你的unordered_map

std::unordered_map<std::pair<int, int>, [VALUE] > my_map; //[VALUE] being the data type of vertex

在此之后，您可以将结构视为常规std::map. 如果您不确定如何使用其中一个，这里有很多示例。

对于 3d 坐标，您可以声明自己的结构

struct vector
{
    int i,j,k;
};

然后修改哈希函数（为了可读性而格式化）

template<> struct hash<vector > {
    size_t operator()(vector x) const {
        size_t seed=0;
        hash_combine(seed, x.i);
        hash_combine(seed, x.j);
        hash_combine(seed, x.k);
        return(seed);
    }
};
于 2013-10-20T00:57:02.523 回答
2

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

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

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

为简单起见，这里是四叉树的 2D 示例：

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

假设地形的大小是 4x4。在此示例中，我们仅使用主节点作为包含叶节点的节点。如果我们现在有顶点，可以说(0.2, 3.2)。顶点被传递到根节点。因为0.2 < 4/2和3.2 > 4/2，节点将顶点发送到叶号。3 存放的地方。如果您正在搜索空间（或本例中的平面）中的位置，您将按照与所述存储类似的方式进行操作。

在您的实现中，您可以使用指针表示节点的子节点/叶子。如果要优化空间，则根本不必存储每个节点的尺寸和位置，而是隐含地说每个节点的尺寸是1x1x1，然后在传递每个顶点之前相应地转换每个顶点。即你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)您将传递...等等。但是，这有点高级，因为您每次使用树时都需要依靠它。

在互联网上很难找到有关该主题的教程，但有很多实现可供学习。这是我找到的一对：

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

还有一个实际的教程（但它很重）： http: //www.xbdev.net/maths_of_3d/octree/tutorial/

于 2013-10-20T01:54:43.363 回答