在三维地形上，给定一条三维直线，找到该直线与地形之间的交点。

Question

我有一个3D地形网格，其中每个网格的坐标(x,y,z)都已知。现在，我有一条单调递增/递减的线，其起点也已知。我想找到地形和该线相交的点。如何实现该算法？

我的想法是将3D地形的坐标存储在nxn矩阵中。然后基于地形网格对该线进行分段。接下来，我将从最靠近线的网格开始，并尝试计算该平面是否与线相交，如果是，则获取该坐标并退出。如果没有，则继续下一个片段。

但是，我的算法是否最佳或最优解？或者是否存在已经实现此功能的库？

- Graviton

---

如果您使用两个三角形来表示网格四边形，那么当节点的四个角不在同一平面上时（想象一下对角线折叠的正方形），您可以避免问题。特别是如果您正在使用OpenGL进行可视化。 - sum1stolemyname

@sum1stolemyname，我也想过这个问题。但我的观点是要找到最有效的算法来获取地形和线之间的交点，因为矩形网格在2x2矩阵中表示是理想的（为了便于访问哪个网格），所以我正在使用矩形网格。 - Graviton

网格顶点的x，y坐标是等间距的，对吗？这是我从“网格”中理解的，但我只是想确认一下。每个顶点的z值是任意的，但已知。 - LarsH

@LarsH，是的，x，y是等间距的。 - Graviton

Answer 1

并非直接优化，只是一些提示：

如果您的网格很大，建议从地形中构建八叉树，以便快速减少您必须检查线路的网格节点数。这在巨大的网格（如512 * 512个节点）中可能更有效，因为只有通过射线的叶节点必须考虑。

此外，八叉树可以用作决定哪些部分的网格是可见的，因此必须绘制，方法是检查哪些叶节点在视锥体内。

然而，有一个问题：必须提前构建八叉树，需要一些时间，并且该树是静态的。一旦构建完成后，它不能轻松修改，因为对一个节点的修改可能会影响其他几个节点，不一定是相邻的节点。

但是，如果您不打算在创建网格后修改它，则八叉树将非常有用。

更新

现在我理解了你计划如何存储网格，我相信空间分割将是一种有效的方法来查找交叉线的最近邻居。

线性查找最近邻居的运行时间复杂度为O(N)，而空间分割方法的平均运行时间复杂度为O(log N)。

- sum1stolemyname

---

不确定为什么您建议使用八叉树，但由于我已经有了一个z坐标矩阵，所以我可以轻松地检查线段落在哪个部分，不是吗？ - Graviton

@ngu soon hui：我不太确定如何用2x2矩阵表示网格。2x2矩阵可以存储4个值——2行2列。你能否澄清一下？我建议使用八叉树快速排除地形上那些离直线不够近以至于无法相交的区域，以便产生更多“提前完成”的情况，从而减少需要检查的线段数量。 - sum1stolemyname

Answer 2

另一种方法是将地形网格三角化，生成一组面，并将线与这些面相交。

显然，您需要进行一些优化，例如仅检查与线的边界框相交的那些面。您可以进行相当便宜/快速的面边界框到线边界框检查，这将非常快速地排除地形中的大多数三角形。

如果您将三角形排列成八叉树（如@sum1stolemyname建议的那样，但针对点），则可以从“自上而下”的方式进行此检查，并且您应该能够使用单个计算来排除整个地形的部分。

- ChrisF

---

三角测量的问题在于我必须检查每个三角形，以确定它是否错过或命中，这不会花费很长时间吗？你说可以检查与线框盒相交的面片，但我看不出这实际上如何优化这个问题。 - Graviton

@Ngu - 抱歉，您需要进行面边界框到线边界框的检查，这非常快速，您将能够迅速排除地形中的大多数三角形。 - ChrisF

你有关于这个的参考资料/算法吗？ - Graviton

@Ngu - 抱歉，我手头没有相关资料。我已经有一段时间没有进行严肃的三维图形工作了，所以我只能通过谷歌搜索“八叉树”和“三角形线相交”等关键词来获取最新的信息。 - ChrisF

Answer 3

如果地形不是通过一个好的函数建立的，那么你将不得不进行光线追踪，即逐步遍历该线以找到交点。这个过程可能需要一些时间。

该过程有几个参数。例如，有一个偏移量，你在每一步沿着该线行走。如果你取一个太大的偏移量，你可能会忽略地形的一些“高度”，从而无法得到正确的交点。如果偏移量太小，它会减慢你的过程。

然而，有一个很好的技巧可以节省时间。它在这里或这里中进行了描述。它使用某种优化结构来处理地形，即按以下方式构建几个细节级别：最精细的细节级别仅是地形本身。下一个（更粗糙的）细节级别仅包含地形纹理中原始“像素”数量的四分之一，并将4个像素组合成一个，取最大值。下一个细节级别类似地构建：

     .             .       .    .
    ... .         ...     ..    .
  .......        ....     ..    .
 ........    =>  ....  => .. => .

 01234567        0246     04    0
                 1357     26    4

   fine   =>  =>   =>   =>  =>  coarse

如果现在进行光线投射，则首先检查较粗的细节级别：

   /
  / 
 /.
  .
  .
  .

如果光线已经错过了粗略的细节级别，就不必检查更细的级别。这只是优化工作的一个非常粗略的想法。但它运行得相当不错。实现它需要相当多的工作，但这篇论文是一个很好的帮助。

- phimuemue

---

您的第三个文档无法查看。 - Graviton

1. 在我的电脑上可以正常查看。
2. 光线追踪用于寻找交点。

- phimuemue

@Ngu - 光线追踪只是算法的名称。您正在跟踪光线的路径（即您的线）。在这种情况下，您只需要执行一次。在更常见的用法中（用于图像），您需要为场景中的每个像素执行此操作。 - ChrisF

@phimuemue，我已经第二次阅读了您上面的答案，现在更清楚了。但有一件事我想问，就是对于初步调查，您尝试使用几个较细的像素组合的过山车像素，并将最大值作为高度。但实际上，这些较粗的像素可能会覆盖起伏的地形，而光线实际上可能已经击中了地形，但较粗的像素不会显示出来。 - Graviton

@ Ngu Soon Hui，我认为更粗的像素表示命中，因为它们是使用底层像素的最大值构建的。如果光线错过了最高点，那么它怎么会击中任何低于最高点的点呢？我曾经想象过这个问题，但是我画了一些图来澄清我的思路。唯一的问题是你不能跳过某些像素 - 但是论文也提供了一种方法来防止这种情况发生。 - phimuemue