algorithm - 3D 网格顶点的交集

Question

想象一个巨大的 3D 网格(程序定义，并且可能是无限的；至少，每边 10^6 个坐标)。在每个网格坐标处，都有一个图元(例如，一个球体、一个盒子或其他一些简单、易于数学定义的函数)。

我需要一种算法来使一条射线与网格元素相交，射线的原点在网格之外，方向进入网格。也就是说，光线可能会穿过这个巨大的网格，然后击中一个基元。由于网格的范围，迭代方法[编辑:(例如光线行进)]慢得令人无法接受。我需要的是一些封闭形式的 [编辑:恒定时间 ]解决方案来找到原始命中。

我想到的一种可能的方法是确定光线将在每个时间步长向基元收敛的数量，在每个时间步中的某个模块化算术空间中围绕网格单元的八个坐标中的每一个x、y 和 z，然后除以射线的方向并取最小的距离。除了直觉，我没有其他证据认为这可能有效，而谷歌也无济于事； “与网格相交”是指与网格的面相交。

注意事项:

• 我真的只关心基元的表面法线(我可以很容易地找到给定相交距离，但我不关心距离本身)。
• 此时相交的图元类型并不重要。理想情况下，它将是一个盒子。第二选择，球体。但是，我假设无论使用什么算法都可以推广到其他原语，如果最坏的情况发生，无论如何它对这个应用程序来说并不重要。

Answer 1

这是另一个想法:只有当所有 x、y 和 z 坐标都接近整数值时，光线才能击中图元。如果我们考虑射线的参数方程，其中线上的一个点由

p=p0 + t * v

其中 p0 是起点，v 是射线的方向向量，我们可以绘制从射线到每个轴上整数值的距离作为 t 的函数。例如:

dx = abs( ( p0.x + t * v.x + 0.5 ) % 1 - 0.5 )

这将产生三个锯齿图，其周期取决于方向向量的分量(例如，如果方向向量为 (1, 0, 0)，则 x-plot 将在 0 和 0.5 之间线性变化，周期为1，而其他地 block 将保持不变，无论 p0 是多少。

您需要找到所有三个图都低于某个阈值水平的第一个 t 值，该阈值水平由您的基元大小决定。因此，在检查高频图之前，首先考虑具有最长(非无限)周期的图，可以大大减少要检查的 t 值的数量。

我无法摆脱这样一种感觉，即可以根据三个图的周期计算出正确的 t 值，但我无法想出任何不被起始位置破坏的东西是原点，阈值不为零。 :-/