3

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

这是一个例子：

  • fillVoxels 包含体素 (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 个邻居的所有体素的列表。

4

8 回答 8

5

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

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

于 2009-06-13T17:44:28.013 回答
2

我会说如果您的每个查找都很慢（O（size）），您应该通过在有序列表中的二进制搜索（O（log（size）））来优化它。

常数26，我不会太担心。如果你迭代得更聪明，你可以缓存一些东西并有 26 -> 10 或其他东西，我认为，但除非你已经分析了整个应用程序并果断地发现它是我会专注于其他东西的瓶颈。

于 2009-06-14T17:26:58.517 回答
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 可能是一个好主意。在任何情况下，您都希望通过合并访问的体素来减少搜索空间。

于 2009-06-15T20:22:34.857 回答
1

如果您一次一个地沿着体素前进，您可以保留一个与网格相对应的查找表，以便在您检查过一次后，IsFullVoxel()您将值放入此网格中。对于您正在前进的每个体素，您可以检查它的查找表值是否有效，并且只称它为IsFullVoxel()无效。

OTOH，您似乎无法避免迭代所有相邻体素，无论是使用IsFullVoxel()还是使用 LUT。如果您有更多先验信息，它可能会有所帮助。例如，如果您知道最多有 x 个相邻的填充体素，或者您知道每个方向最多有 y 个相邻的填充体素。例如，如果您知道要查找具有 5 到 6 个邻居的体素，则可以在找到 7 个完整邻居或 22 个空邻居后停止。

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

于 2009-06-13T17:09:36.413 回答
1

如果您迭代中的大部分移动都是针对邻居的，那么您可以通过在迈出这一步之前不回头查看刚刚检查的那些来减少大约 25% 的检查。

于 2009-06-13T22:14:48.113 回答
1

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

于 2009-06-16T15:12:56.167 回答
0

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

如果可以（即网格不是太大），只需制作一个 3d 布尔数组。3d 数组中的 26 次查找实际上不应该花费那么长时间（而且确实没有办法减少查找次数）。

实际上，现在我想到了，您可以将其设为 3d 长数组（64 位）。每个 64 位块将包含 64 (4 x 4 x 4) 体素。当您检查块中间体素的邻居时，您可以进行一次 64 位读取（这会快得多）。

于 2009-06-13T17:36:52.370 回答
0

有什么方法可以减少所需查找的数量吗？

您至少必须对每个体素执行至少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 个字节。您可以使用更少的空间，并可能通过打包字节来提高速度。

如果您了解有关数据的详细信息，则有更好的算法。例如，一个非常稀疏的体素空间将极大地受益于八叉树，当您已经知道内部没有填充体素时，您可以跳过大块的查找。然而，这些算法中的大多数仍然需要每个体素至少进行一次查找来填充它们的矩阵，但是如果您正在执行多个操作，那么它们可能比这一次操作受益更多。

于 2010-10-12T19:28:22.893 回答