我有一个 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() 查找，这非常慢。
有什么办法可以减少所需查找的次数吗？ 当您查看上面的示例时，您可以看到我多次检查相同的体素，因此可以通过一些巧妙的缓存来摆脱查找。
如果这有任何帮助，则体素代表体素化 3D 表面（但其中可能有孔）。 我通常想要获取具有 5 或 6 个邻居的所有体素的列表。
I have got a 3D grid (voxels), where some of the voxels are filled, and some are not. The 3D grid is sparsely filled, so I have got a set filledVoxels with coordinates (x, y, z) of the filled voxels. What I am trying to do is find out is for each filled voxel, how many neighboring voxels are filled too.
Here is an example:
- filledVoxels contains the voxels (1, 1, 1), (1, 2, 1), and (1, 3, 1).
- Therefore, the neighbor counts are:
- (1,1,1) has 1 neighbor
- (1,2,1) has 2 neighbors
- (1,3,1) has 1 neighbor.
Right now I have this algorithm:
voxelCount = new Map<Voxel, Integer>();
for (voxel v in filledVoxels)
count = checkAllNeighbors(v, filledVoxels);
voxelCount[v] = count;
end
checkAllNeighbors() looks up all 26 surrounding voxels. So in total I am doing 26*filledVoxels.size() lookups, which is quite slow.
Is there any way to cut down the number of required lookups? When you look at the above example you can see that I am checking the same voxels several times, so it might be possible to get rid of lookups with some clever caching.
If this helps in any way, the voxels represent a voxelized 3D surface (but there might be holes in it). I usually want to get a list of all voxels that have 5 or 6 neighbors.
发布评论
评论（8）
如果您一次沿着体素行进，则可以保留一个与网格相对应的查找表，以便在使用
IsFullVoxel()检查一次后，将值放入此表中网格。 对于您要进入的每个体素，您可以检查其查找表值是否有效，只有在无效时才调用IsFullVoxel()。OTOH 似乎您无法避免迭代所有相邻体素，无论是使用 IsFullVoxel() 还是 LUT。 如果您有更多先验信息，它可能会有所帮助。 例如，如果您知道最多有 x 个相邻填充体素，或者您知道每个方向上最多有 y 个相邻填充体素。 例如，如果您知道正在寻找具有 5 到 6 个邻居的体素，则可以在找到 7 个完整邻居或 22 个空邻居后停止。
我假设存在一个函数
IsFullVoxel()，如果体素已满，该函数将返回 true。If you're marching along the voxels one at a time, you can keep a lookup table corresponding to the grid, so that after you've checked it once using
IsFullVoxel()you put the value in this grid. For each voxel you're marching in you can check if its lookup table value is valid, and only callIsFullVoxel()it it isn't.OTOH it seems like you can't avoid iterating over all neighboring voxels, either using
IsFullVoxel()or the LUT. If you had some more a priori information it could help. For instance, if you knew that there were at most x neighboring filled voxels, or you knew that there were at most y neighboring filled voxels in each direction. For instance, if you know you're looking for voxels with 5 to 6 neighbors, you can stop after you've found 7 full neighbors or 22 empty neighbors.I'm assuming that a function
IsFullVoxel()exists that returns true if a voxel is full.如果迭代中的大部分移动都是针对邻居的，那么通过在执行该步骤之前不回顾刚刚检查的移动，您可以减少大约 25% 的检查。
If most of the moves in your iteration were to neighbors, you could reduce your checking by around 25% by not looking back at the ones you just checked before you made the step.
您可能会发现 Z 顺序曲线是一个有用的概念。 它可以让您（在某些条件下）在当前查询的点周围保留一个数据滑动窗口，这样当您移动到下一个点时，您不必丢弃许多已经执行的查询。
You may find a Z-order curve a useful concept here. It lets you (with certain provisos) keep a sliding window of data around the point you're currently querying, so that when you move to the next point, you don't have to throw away many of the queries you've already performed.
嗯，你的问题不是很清楚。 我假设您只有一个已填充点的列表。 在这种情况下，这将会非常慢，因为您必须迭代它（或使用某种树结构，例如kd-tree，但这仍然是
O(log n))。如果可以的话（即网格不是太大），只需制作一个 3d 布尔数组即可。 3d 数组中的 26 次查找实际上不应该花费那么长时间（并且确实没有办法减少查找次数）。
实际上，现在我想到了，你可以将其设为一个 3d 长整型数组（64 位）。 每个 64 位块可容纳 64 (4 x 4 x 4) 体素。 当您检查块中间体素的邻居时，您可以执行单个 64 位读取（这会快得多）。
Um, your question is not very clear. I'm assuming you just have a list of the filled points. In that case, this is going to be very slow, because you have to iterate through it (or use some kind of tree structure such as a kd-tree, but this will still be
O(log n)).If you can (i.e. the grid is not too big), just make a 3d array of bools. 26 lookups in a 3d array shouldn't really take that long (and there really is no way to cut down on the number of lookups).
Actually, now that I think of it, you could make it a 3d array of longs (64 bits). Each 64 bit block would hold 64 (4 x 4 x 4) voxels. When you are checking the neighbors of a voxel in the middle of the block, you could do a single 64 bit read (which would be much faster).
有什么方法可以减少所需查找的次数吗？
您至少必须对每个体素至少执行 1 次查找。 由于这是最小值，因此任何仅对每个体素执行一次查找的算法都将满足您的要求。
一个简单的想法是初始化一个数组来保存每个体素的计数，然后查看每个体素并递增数组中该体素的邻居。
伪 C 可能看起来像这样：
您需要编写initializeCountArray，以便将所有数组元素设置为0。
更重要的是，您还需要编写incrementNeighbors，以便它不会在数组之外递增。 这里稍微提高速度是仅对内部的所有体素执行上述算法，然后使用修改后的incrementNeighbrs例程对所有外部边缘体素进行单独的运行，该例程了解一侧不会有邻居。
该算法导致每个体素进行 1 次查找，并且每个体素最多添加 26 字节。 如果您的体素空间稀疏，那么这将导致很少的（相对）添加。 如果您的体素空间非常密集，您可能会考虑反转算法 - 将每个条目的数组初始化为 26 的值，然后在体素不存在时递减邻居。
给定体素的结果（即，我有多少个邻居？）驻留在数组中。 如果您需要知道体素 2,3,5 有多少个邻居，只需查看 countArray[2][3][5] 中的字节即可。
该数组每个体素将消耗 1 个字节。 您可以使用更少的空间，并且可能通过打包字节来稍微提高速度。
如果您了解数据的详细信息，就会有更好的算法。 例如，非常稀疏的体素空间将从八叉树中受益匪浅，当您已经知道内部没有填充体素时，您可以跳过大块的查找。 然而，大多数这些算法仍然需要每个体素至少进行一次查找来填充其矩阵，但如果您正在执行多项操作，那么它们可能比这一项操作受益更多。
Is there any way to cut down the number of required lookups?
You will, at minimum, have to perform at least 1 lookup per voxel. Since that's the minimum, then any algorithm which only performs one lookup per voxel will meet your requirement.
One simplistic idea is to initialize an array to hold the count for each voxel, then look at each voxel and increment the neighbors of that voxel in the array.
Pseudo C might look something like this:
You'll need to write initializeCountArray so it sets all array elements to 0.
More importantly you'll also need to write incrementNeighbors so that it won't increment outside the array. A slight speed increase here is to only perform the above algorithm on all voxels on the interior, then do a separate run on all the outside edge voxels with a modified incrementNeighbrs routine that understands there won't be neighbors on one side.
This algorithm results in 1 lookup per voxel, and at most 26 byte additions per voxel. If your voxel space is sparse then this will result in very few (relative) additions. If your voxel space is very dense, you might consider reversing the algorithm - initialize the array to the value of 26 for each entry, then decrement the neighbors when a voxel doesn't exist.
The results for a given voxel (ie, how many neighbors do I have?) reside in the array. If you need to know how many neighbors voxel 2,3,5 has, just look at the byte in countArray[2][3][5].
The array will consume 1 byte per voxel. You could use less space, and possibly increase the speed a little bit by packing the bytes.
There are better algorithms if you know details about your data. For instance, a very sparse voxel space will benefit greatly from an octree, where you can skip large blocks of lookups when you already know there are no filled voxels inside. Most of these algorithms, however, would still require at least one lookup per voxel to fill their matrix, but if you are performing several operations then they may benefit more than this one operation.
您可以将体素空间转换为 八叉树，其中每个节点都包含一个标志，指定它是否完全包含填充体素。
当节点不包含填充体素时，您不需要检查其任何后代。
You can transform your voxel space into a octree in which every node contains a flag that specifies whether it contains filled voxels at all.
When a node does not contain filled voxels, you don't need to check any of its descendants.
我想说，如果你的每个查找都很慢（O（size）），你应该通过有序列表中的二分搜索来优化它（O（log（size）））。
常数 26，我不会太担心。 如果你更聪明地迭代，你可以缓存一些东西并拥有 26 -> 我认为 10 左右，但除非您已经分析了整个应用程序并果断地发现这是瓶颈，否则我会专注于其他事情。
I'd say if each of your lookups is slow (O(size)), you should optimize it by binary search in an ordered list (O(log(size))).
The constant 26, I wouldn't worry much. If you iterate smarter, you could cache something and have 26 -> 10 or something, I think, but unless you have profiled the whole application and found out decisively that it is the bottleneck I would concentrate on something else.
正如 ilya 所说，您无能为力来绕过 26 次邻居查找。 您必须在有效识别给定邻居是否已满方面取得最大收益。 鉴于强力解决方案本质上是 O(N^2)，您在该领域有很多可能的优势。 由于您必须至少对所有填充的体素进行一次迭代，因此我将采用类似于以下的方法：
对于高效的空间数据类型，正如 Zifre 建议的那样，kd 树可能是一个好主意。 无论如何，您都希望通过对访问过的体素进行分箱来减少搜索空间。
As ilya states, there's not much you can do to get around the 26 neighbor look-ups. You have to make your biggest gains in efficiently identifying whether a given neighbor is filled or not. Given that the brute force solution is essentially O(N^2), you have a lot of possible ground to gain in that area. Since you have to iterate over all filled voxels at least once, I would take an approach similar to the following:
For your efficient spatial data type, a kd-tree, as Zifre suggested, might be a good idea. In any case, you're going to want to reduce your search space by binning visited voxels.