您如何通过3D网格进行线性迭代? [英] How can you iterate linearly through a 3D grid?

问题描述

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

Assume we have a 3D grid that spans some 3D space. This grid is made out of cubes, the cubes need not have integer length, they can have any possible floating point length.

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

Our goal is, given a point and a direction, to check linearly each cube in our path once and exactly once.

因此，如果这只是一个普通的3D数组，并且方向是沿X方向说的，那么从位置(1,2,0)开始，算法将是:

So if this was just a regular 3D array and the direction is say in the X direction, starting at position (1,2,0) the algorithm would be:

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

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

But of course the origin and the direction are arbitrary and floating point numbers, so it's not as easy as iterating through only one dimension of a 3D array. And the fact the side lengths of the cubes are also arbitrary floats makes it slightly harder as well.

推荐答案

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

Assume that your cube side lengths are s = (sx, sy, sz), your ray direction is d = (dx, dy, dz), and your starting point is p = (px, py, pz). Then, the ray that you want to traverse is r(t) = p + t * d, where t is an arbitrary positive number.

让我们专注于一个维度.如果当前位于多维数据集的下边界，那么要到达多维数据集的上边界需要在射线上进行的步长dt为:dt = s / d.我们可以针对三个维度分别计算该步长，即dt也是3D向量.

Let's focus on a single dimension. If you are currently at the lower boundary of a cube, then the step length dt that you need to make on your ray in order to get to the upper boundary of the cube is: dt = s / d. And we can calculate this step length for each of the three dimensions, i.e. dt is also a 3D vector.

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

Now, the idea is as follows: Find the cell where the ray's starting point lies in and find the parameter values t where the first intersection with the grid occurs per dimension. Then, you can incrementally find the parameter values where you switch from one cube to the next for each dimension. Sort the changes by the respective t value and just iterate.

更多详细信息:

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

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

I will only cover the case where the direction is positive. There are some minor changes if you go in the negative direction but I am sure that you can do these.

找到每个尺寸的第一个交点(nextIntersection是3D矢量):

Find the first intersections per dimension (nextIntersection is a 3D vector):

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

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

I have omitted the case where two or three cells are changed at the same time. The above code will only change one at a time. If you need this, feel free to adapt the code accordingly.

这篇关于您如何通过3D网格进行线性迭代?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！