如何快速计算相邻体素的数量？（这是一个关于IT技术的问题标题）

Question

我有一个3D网格（体素），其中一些体素被填充，而另一些则没有。这个3D网格是稀疏填充的，所以我有一个包含填充体素坐标（x，y，z）的集合filledVoxels。我想做的是找出每个填充体素周围有多少个填充体素。

以下是一个例子：

- filledVoxels包含体素（1,1,1），（1,2,1）和（1,3,1）。 - 因此，邻居计数如下：

- (1,1,1)有1个邻居 - (1,2,1)有2个邻居 - (1,3,1)有1个邻居

目前我有这个算法：

voxelCount = new Map<Voxel, Integer>();

for (voxel v in filledVoxels)
  count = checkAllNeighbors(v, filledVoxels);
  voxelCount[v] = count;
end

checkAllNeighbors()会查找所有26个相邻的体素。因此，总共要做26 * filledVoxels.size()次查找，这非常慢。

有没有办法减少所需的查找次数？当您查看上面的示例时，可以看到我多次检查相同的体素，因此可能可以通过一些聪明的缓存来摆脱查找。

如果有帮助的话，这些体素代表了一个体素化的三维表面（但可能存在空洞）。通常，我想获取具有5或6个相邻体素的所有体素的列表。

- martinus

---

你可能需要添加一些关于filledVoxels数组中元素排序的信息。没有这些信息，回答这个问题只能基于猜测。 - PatrickvL

它并不会减少所需的查找次数，但你的问题看起来可以很容易地并行化处理。 - Trillian

Answer 1

你可以将体素空间转换为一个八叉树，其中每个节点都包含一个指示它是否包含填充体素的标志。

当一个节点不包含填充体素时，你不需要检查它的任何后代节点。

- Dario

---

这对于非常稀疏的数据集或本地化的数据集（大多数体素靠近其他体素）非常有帮助，但每个体素只需要一次查找。对于超过25％随机分布的体素空间，它不会有太大帮助。 - Adam Davis

Answer 2

正如Ilya所说，你无法避免26个邻居的查找。因此，你需要在有效地确定给定邻居是否填充方面取得最大的收益。鉴于暴力解决方案基本上是O（N ^ 2），因此你可以在这个领域获得很多可能的进展。由于你必须至少一次迭代所有填充的体素，我建议采用以下类似的方法：

voxelCount = new Map<Voxel, Integer>();
visitedVoxels = new EfficientSpatialDataType();

for (voxel v in filledVoxels)
  for (voxel n in neighbors(v))
    if (visitedVoxels.contains(n))
      voxelCount[v]++;
      voxelCount[n]++;
    end
  next
  visitedVoxels.add(v);
next

如果您需要高效的空间数据类型，像Zifre所建议的kd-tree可能是一个不错的选择。无论如何，您都需要通过对访问过的体素进行分箱来减少搜索范围。

- Eric

Answer 3

如果每次查找都很慢（O(size)），我建议您在有序列表中使用二分查找进行优化（O(log(size))）。

至于常数26，我不会太担心。如果您更聪明地迭代，可以缓存某些内容并将26 -> 10或其他数字，但除非您已经对整个应用程序进行了剖析并明确发现它是瓶颈，否则我会集中精力处理其他事情。

- ilya n.

Answer 4

如果你按照每个体素一个接一个地进行迭代，你可以保持一个与网格相对应的查找表，这样在使用IsFullVoxel()检查一次后，就将该值放入此网格中。对于你正在遍历的每个体素，你可以检查其查找表值是否有效，并且只有在它无效时才调用IsFullVoxel()。

另一方面，似乎无法避免迭代所有相邻的体素，无论是使用IsFullVoxel()还是LUT。如果你有一些先验信息，它可能会有所帮助。例如，如果你知道最多有x个相邻的填充体素，或者你知道每个方向上最多有y个相邻的填充体素。例如，如果你知道你正在寻找具有5到6个相邻体素的体素，则可以在找到7个满体素或22个空体素后停止。

我假设存在一个函数IsFullVoxel()，如果一个体素是满的，则返回true。

- Nathan Fellman

---

嗨，我觉得有些误解，filledVoxels.size() 给出了所有填充的体素数。我遍历这个集合，并针对每个条目执行 26 次查找以计算邻居的数量。 - martinus

Answer 5

如果你的迭代中大部分移动都是到邻居节点，那么在向前迈步之前不再回头检查刚刚检查过的节点，可以将你的检查次数减少约25%。

- tom10

Answer 6

在这里，您可能会发现Z-order curve是一个有用的概念。它可以让您（在某些条件下）在当前查询点周围保持一个滑动窗口的数据，这样当您移动到下一个点时，您就不必丢弃已经执行的许多查询。

- user60401

Answer 7

有没有办法减少所需的查找次数？

您至少需要对每个体素执行至少1次查找。既然这是最小值，那么任何仅对每个体素执行一次查找的算法都将满足您的要求。

一个简单的想法是初始化一个数组来保存每个体素的计数，然后查看每个体素并在数组中递增该体素的邻居。

伪C代码可能如下所示：

#define MAXX 100
#define MAXY 100
#define MAXZ 100

int x, y, z
char countArray[MAXX][MAXY][MAXZ];

initializeCountArray(MAXX, MAXY, MAXZ);  // Set all array elements to 0

for(x=0; x<MAXX; x++)
   for(y=0;y<MAXY;y++)
      for(z=0;z<MAXZ;z++)
         if(VoxelExists(x,y,z))
            incrementNeighbors(x,y,z);

你需要编写initializeCountArray函数，以便将所有数组元素设置为0。

更重要的是，你还需要编写incrementNeighbors函数，以便它不会在数组外部进行增量操作。这里稍微提高一下速度，只需对内部所有体素执行上述算法，然后对所有外部边缘体素进行单独运行，使用修改后的incrementNeighbrs例程，该例程理解一侧没有邻居。

此算法每个体素结果为1次查找，并且最多每个体素进行26字节的添加。如果您的体素空间是稀疏的，则这将导致非常少量（相对）的添加。如果您的体素空间非常密集，则可以考虑反转算法-将数组初始化为每个条目的值为26，然后在不存在体素时减少邻居。

给定体素的结果（即我有多少邻居？）驻留在数组中。如果您需要知道2、3、5号体素有多少邻居，请查看countArray [2] [3] [5]中的字节。

该数组将消耗每个体素1个字节。您可以通过打包字节来使用更少的空间，并可能稍微提高速度。

如果您了解数据的详细信息，则可以使用更好的算法。例如，非常稀疏的体素空间将从八叉树中受益匪浅，因为已经知道其中没有填充体素时，可以跳过大块的查找。然而，这些大多数算法仍需要至少每个体素进行一次查找才能填充其矩阵，但如果您执行多个操作，则可能比这一个操作更受益。

- Adam Davis

Answer 8

嗯，你的问题不是很清楚。我假设你只有一个填充点列表。在这种情况下，这将会非常慢，因为你必须迭代它（或使用某种树结构，如kd-tree，但这仍然是O(log n)）。

如果可以的话（即网格不太大），只需制作一个布尔值的3D数组。在3D数组中进行26次查找不应该花费太长时间（而且真的没有办法减少查找次数）。

实际上，现在我想起来了，你可以将其制作成64位的3D数组。每个64位块将包含64个（4 x 4 x 4）体素。当你检查块中间体素的邻居时，你可以进行单个64位读取（这将更快）。

- Zifre