我有一个 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 个邻居的所有体素的列表。
最佳答案
您可以将体素空间转换为 octree其中每个节点都包含一个标志,指定它是否完全包含填充体素。
当一个节点不包含填充的体素时,您不需要检查它的任何后代。
关于algorithm - 如何快速统计相邻体素的个数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/991049/