假设我们有一个跨越某些 3D 空间的 3D 网格。该网格由立方体组成，立方体不需要具有整数长度，它们可以具有任何可能的浮点长度。

我们的目标是，给定一个点和一个方向，对路径中的每个立方体进行一次且恰好一次的线性检查。

因此，如果这只是一个常规 3D 数组，并且方向为 X 方向，则从位置 (1,2,0) 开始，算法将是:

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

但是，原点和方向当然是任意的 float ，因此它不像仅迭代 3D 数组的一维那么容易。事实上，立方体的边长也是任意 float ，这也使得它变得稍微困难​​一些。

请您参考如下方法:

假设立方体边长为 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 

我省略了同时更改两个或三个单元格的情况。上面的代码一次只会改变一个。如果您需要这个，请随意相应地调整代码。