python - Python 中的 3D 几何相交

Question

我有一个遗传编程算法，可以通过障碍物为无人机轨迹(3D 线)演化出解决方案，这些障碍物是城市中的禁飞区。为了评估解决方案的适用性，我需要检查它们是否与禁飞区相交(对于数千次迭代，每次迭代约 200 次评估)

example route through barriers

在 2D 中，我可以使用 Shapely 轻松完成。然而，3D 问题要复杂得多。我目前正在使用具有 100 个顶点或 99 条线段的解决方案。典型的 3D 飞行路径(在测试用例中)长 2-10 公里，附近有 10 到 20 个障碍物。

目前障碍物是具有高度属性的 2D 多边形，但我希望能够为障碍物(以及表面)使用凹 3D 网格。转换/创建网格、多面体或面组不是问题，因为它只需完成一次。然而，评估必须进行 1000 次。

我很好奇是否有人知道进行这种 bool 交集检查的更简单/更快的方法。我正在考虑这些选项，目前还没有一个是完美的:

• 检查线顶点是否包含在多边形的凸包中(scipy.spatial 或 this)这限制了我的凸性障碍
• 检查线段是否与网格面相交/碰撞(Panda3D、Blender API，..)

使用 Shapely 检查交叉点几何边界是否位于障碍物的“事件”z 坐标范围内有效，但严重限制了可以使用的 3D 障碍物的种类。我将其称为 2.5D 解决方案..

这是一个 2D 场景的错误示例 gif:我有数百条线，想检查它们是否穿过绿色区域(此处只显示几条线)

solution evolution

有像 trimesh 和 rhino3dm 这样的 3D 几何包，但它们只支持线面相交。我不知道我是否需要一个庞大的图书馆，或者自己写点东西是否更有意义..

此外，由于速度是重中之重，我还考虑了不使用 Python 的解决方案。我希望有一个主要是数学的方法来做到这一点(没有我怀疑的开销，例如 Panda3D 或 Blender)。

Answer 1

在您的一条评论中，您说:

Even something that just checks line-segment vs triangle intersection should work

所以我的建议是对 fast, minimum storage ray-triangle intersection 使用 Möller–Trumbore 算法.

我开发了一个 Python 实现，您可以找到 here .从文档中可以看出，它非常易于使用，例如:

>>> vertices = np.array([[0.0, 0.0, 0.0], [0.0, 10.0, 0.0], [10.0, 0.0, 0.0]])
>>> ray_origin = np.array([1.0, 1.0, 1.0])
>>> ray_direction = np.array([0.0, 0.0, -1.0])
>>> intersection = ray_triangle_intersection(vertices, ray_origin, ray_direction)
(1.0, 0.1, 0.1)

是的，您说过您实际上并没有处理射线，但这可能是一个起点。