algorithm - 如何快速计算相邻体素的数量？

我有一个 3D 网格(体素)，其中一些体素被填充，有些没有。 3D 网格是稀疏填充的，所以我得到了一组 filledVoxels，其中包含填充体素的坐标 (x, y, z)。我想要做的是找出每个填充的体素，也填充了多少相邻的体素。

下面是一个例子:

填充体素包含体素 (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() 查找，这很慢。

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

如果这有任何帮助，体素表示体素化的 3D 表面(但其中可能有孔)。我通常想获得所有具有 5 或 6 个邻居的体素的列表。

最佳答案

您可以将体素空间转换为 octree，其中每个节点都包含一个标志，用于指定它是否完全包含填充体素。

当节点不包含填充体素时，您无需检查其任何后代。

关于algorithm - 如何快速计算相邻体素的数量？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/991049/