algorithm - 如何快速统计相邻体素的个数？

Question

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

这是一个例子:

• 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() 次查找，这非常慢。

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

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

Answer 1

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

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