在3D地形上，给定3D线，找到线和地形之间的交点

我有一个三维地形网格，每个网格的每个坐标(x,y,z)都是已知的。现在，我有一个单调增加/减少的线，其起点也是已知的。我想找到地形和线相交的点。算法是做什么的？

我能想到的是将3D地形的坐标存储在nxn矩阵中。然后我会根据地形中的网格对线进行分段。然后我将从最接近该线的网格开始，然后尝试计算该平面是否与该线相交，如果是，则获取坐标并退出。如果不是，那么我将进入下一部分。

但我的算法是最好的还是最优的解决方案？或者是否有任何现有的库已经这样做了？

另一种方法是对地形网格进行三角测量以生成一组切面，然后将线与这些切面相交。

显然，您需要进行一些优化，例如只检查与线的边界框相交的那些面。你可以做一个非常便宜/快速的小平面边界框到行边界框检查，这将很快折扣地形中的大多数三角形。

如果你将三角形排列成一个八叉树（建议使用@ sum1stolemyname但是这些点），那么这个检查可以从“自上而下”完成，你应该能够通过一次计算来折叠地形的整个部分。

不是直接和优化，只是一些提示：

如果您的网格很大，那么从您的地形构建八叉树可能是值得的，以便快速减少必须检查线路的网格节点的数量。这可以在巨大的网格（如512 * 512 ndoes）中更有效，因为只需要考虑光线穿过的叶子节点。

此外，八叉树可用作决定网格部分是否可见的手段，因此必须通过检查视锥体中的哪些离开节点来绘制。

但是有一个问题：构建八叉树必须提前完成，花一些时间，树是静态的。它在构造之后不能轻易修改，因为一个节点中的修改可能会影响其他几个节点，而不一定是相邻的节点。

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

UPDATE

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

线性地查找最近的邻居具有O（N）的运行时复杂度，而如果O（log N），则空间分区应用具有平均运行时复杂度。

如果地形不是通过一个很好的function构建的，则必须进行光线跟踪，即逐步遍历线以找到交叉点。此过程可能需要一些时间。

该过程有几个参数。例如，在每一步中都有行走的偏移量。如果偏移太大，可能会忽略地形的某些“高度”，从而得不到正确的交叉点。如果偏移量很小，则会减慢您的过程。

但是，有一个很好的技巧可以节省时间。这里描述了它。在这里。它为地形使用某种优化结构，即通过以下方式构建多个级别的细节：最精细的细节层次只是地形本身。下一个（较粗略的）细节级别仅包含地形纹理中原始“像素”数量的四分之一，并将4个像素合并为一个，取最大值。下一级细节是类似地构建的：

  . . . . ... . ... .. . ....... .... .. . ........ => .... => .. => . 01234567 0246 04 0 1357 26 4 fine => => => => => coarse

如果现在执行光线投射，首先，检查更粗糙的细节级别：

  / / /. . . .

如果光线已经错过了粗略的细节水平，则不必检查更精细的水平。这只是一个非常粗略的想法，如何优化工作。但它运作得很好。实施它是相当多的工作，但是这篇论文是一个很好的帮助。