algorithm - 3D 网格顶点的交集

Question

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

我需要一种算法来与网格的元素相交，原点在网格之外，方向进入它。即，光线可能穿过这个巨大的网格的一半，然后击中一个图元。由于网格的范围，迭代方法 [编辑：（如光线行进）] 的速度慢得令人无法接受。我需要的是一些封闭形式的[编辑：常数时间]解决方案来寻找原始命中。

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

笔记：

我真的只关心基元的表面法线（我可以很容易地找到相交的距离，但我不关心距离本身）。
在这一点上，相交的基元类型并不重要。理想情况下，它将是一个盒子。第二个选择，球体。但是，我假设使用的任何算法都可以推广到其他原语，并且如果最坏的情况出现在最坏的情况下，无论如何对于这个应用程序来说并不重要。

谢谢，
伊恩

score 1 · Accepted Answer

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

p=p0 + t * v

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

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

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

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

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

score 0 · Accepted Answer

您在问题中指出迭代解决方案的速度慢得令人无法接受 - 我假设您的意思是迭代，即针对线测试网格中的每个对象。

而是迭代线相交的网格立方体，并为每个立方体测试立方体相交的 8 个对象。查看Bresenham 的线条绘制算法，了解如何找到线条相交的立方体。请注意，Bresenham's 不会绝对返回光线相交的每个立方体，但为了找到要测试的基元，我相当确定它会足够好。它还具有很好的特性：

score 0 · Accepted Answer

基本上，您需要做的是以函数的形式表达线。从那里，您只需要在数学上计算射线是否与每个物体相交，然后如果它确实确保您得到最接近源的它与它发生碰撞的那个。

这并不快，因此您必须在此处进行大量优化。最明显的是使用边界框而不是实际形状。从那里，您可以执行诸如使用八叉树或 BST（二进制空间分区）之类的事情。

好吧，无论如何，由于系统的额外限制，我可能会忽略某些事情，但这就是我必须为课程制作光线追踪器的方式。

score 0 · Accepted Answer

试试这个方法：

4 回答 4