在3D Terrain上，给定一条3D线，查找该线与Terrain之间的交点

Question

我有一个三维地形网格，其中每个网格的坐标(x,y,z)都是已知的。现在，我有了一条单调递增/递减的线，它的起点也是已知的。我想找出地形和直线相交的点。做这件事的算法是什么？

​

​

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

但是我的算法是最好的，还是最优的解决方案？或者有没有现成的库已经做到了这一点？

Answer 1

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

如果您的栅格很大，那么从您的地形构建octree可能是值得的，以便快速减少您必须检查直线的栅格节点的数量。这在一个巨大的网格(如512*512节点)中可能会更有效率，因为只需要考虑光线通过的叶节点。

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

然而，有一个问题:构建八叉树必须提前完成，需要一些时间，并且树是静态的。它在构造后不能很容易地修改，因为在一个节点中的修改可能会影响其他几个节点，而不一定是相邻的节点。

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

更新

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

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

Answer 2

一种不同的方法是对地形网格进行三角剖分，以生成一组面，然后将线与这些面相交。

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

如果你把你的三角形排列成一个八叉树(按照@sum1stolemyname的建议，但是对于点)，那么这种检查可以从“自上而下”完成，并且你应该能够通过一次计算来打折地形的整个部分。

Answer 3

如果地形不是通过一个很好的函数构建的，你将不得不做一个ray trace，即一步一步地遍历线以找到交叉点。此过程可能需要一些时间。

该过程有几个参数。例如，你在每一步中沿着这条线走的偏移量。如果偏移量太大，可能会遗漏地形的一些“高度”，从而无法获得正确的交叉点。如果偏移量太小，它将减慢您的过程。

然而，有一个很好的技巧可以节省时间。它分别描述了here。here。它对地形使用了某种优化结构，也就是说，它以以下方式构建了几个层次的细节:最好的细节层次就是地形本身。下一个(较粗糙的)细节级别仅包含地形纹理中原始“像素”数量的四分之一，并将4个像素合并为1，取最大值。下一层次的细节以类似的方式构造：

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

 01234567        0246     04    0
                 1357     26    4

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

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

   /
  / 
 /.
  .
  .
  .

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