logo标签列表

如何高效地通过2D网格实现射线投射？

algorithmgraphunity-game-engineraycastingnavmesh
3

我正在实现一个导航网格路径规划系统，需要能够在网格中两点之间进行射线投射，并获取所有被射线穿过的边缘列表。显然，我需要测试每个线段的交点，但我希望有一种有效的方法来选择哪些线段需要被检查，而不是粗暴地迭代整个网格中的每条边缘。有人知道我该如何解决这个问题吗？

导航网格可以是三维的，这意味着您在提问如何使光线与网格相交时需要更具体。典型的方法涉及空间分割，例如kd树，但这取决于您的网格长什么样子。 - Nicko Po
它可以是3D的，但如果我允许这样做，所有的计算（如线交叉等）都会变得更加复杂，而且我并不需要它，所以我将其限制为有效的2D。 - SilentSin
我想我的意思是，如果你在浏览三维地形，你的导航地图将是三维的。无论如何，然后看看kd树，对于2个维度，用于射线跟踪查询。但是，如果你的路径很短，而且经常改变，“聪明”的暴力可能是最好的选择。 - Nicko Po
1个回答
0
2
我尝试实现导航网格的主要原因是为了不受网格限制。 - SilentSin
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接