您如何通过3D网格进行线性迭代？

一尘不染

您如何通过3D网格进行线性迭代？

algorithm

假设我们有一个跨越某些3D空间的3D网格。该网格由多维数据集组成，多维数据集不必具有整数长度，它们可以具有任何可能的浮点长度。

我们的目标是给定一个点和一个方向，一次线性地检查路径中的每个立方体。

因此，如果这只是一个常规的3D数组，并且方向是沿X方向说的，那么从位置（1,2,0）开始，算法将是：

for(i in number of cubes)
{
     grid[1+i][2][0]
}

但是当然，原点和方向是任意的和浮点数，因此它不像仅遍历3D数组的一个维度那样容易。而且，立方体的边长也是任意的浮点数，这也使得它变得有点硬。

阅读 297

2020-07-28

共1个答案

一尘不染

假设您的立方体边长为s = (sx, sy, sz)，射线方向为d = (dx, dy, dz)，起点为p = (px, py, pz)。然后，您要遍历的射线是r(t) = p + t * d，其中t是任意正数。

让我们关注一个维度。如果您当前位于多维数据集的下边界，那么dt为了到达多维数据集的上边界，您需要在射线上进行的步长为：dt = s / d。我们可以为三个维度中的每个维度计算该步长，即dt它也是一个3D向量。

现在，想法如下：找到射线起点所在的像元，并找到t每个维度与网格的第一个交点所在的参数值。然后，您可以逐步找到每个维度从一个多维数据集切换到另一个多维数据集的参数值。按相应的t值对更改进行排序，然后进行迭代。

一些更多的细节：

cell = floor(p - gridLowerBound) / s   <-- the / is component-wise division

我只会介绍方向为正的情况。如果您朝负面方向走，会有一些细微的变化，但是我相信您可以做到。

找到每个尺寸的第一个交点（nextIntersection是3D向量）：

nextIntersection = ((cell + (1, 1, 1)) * s - p) / d

并计算步长：

dt = s / d

现在，迭代一下：

if(nextIntersection.x < nextIntersection.y && nextIntersection.x < nextIntersection.z)
    cell.x++
    nextIntersection.x += dt.x
else if(nextIntersection.y < nextIntersection.z)
    cell.y++
    nextIntersection.y += dt.y
else
    cell.z++
    nextIntersection.z += dt.z
end if
if cell is outside of grid
    terminate

我省略了同时更改两个或三个单元格的情况。上面的代码一次只能更改一个。如果需要，请随意修改代码。

2020-07-28