3D geometry intersections in Python

Question

I have a genetic programming algorithm that evolves solutions for a drone trajectory (3D lines) through obstacles, which are no-fly zones in a city. In order to evaluate the fitness of the solutions I need to check if they intersect the no-fly areas (~200 evaluations per iteration for thousands of iterations)

example route through barriers

In 2D I have done it pretty easily using Shapely. However, the 3D problem is much more complicated. I am currently using solutions with 100 vertices, or 99 line segments. Typical 3D flight paths (in test cases) are 2-10km long and involve 10 to 20 barriers in the immediate vicinity.

Currently the barriers are 2D polygons with a height property, but I would like to be able to use concave 3D meshes for the barriers (as well as surfaces). Converting/creating meshes, polyhedrons or sets of faces is not an issue as it will only have to be done once. The evaluations however have to be done 1000s of times..

I am curious if anyone is aware of a simpler/faster way to do this kind of Boolean intersection check. I am considering these options, none of them perfect so far:

• check if line vertices are contained in convex hulls of polygons (scipy.spatial or this) this limits my barriers to convexity
• check if line segments intersect/collide with mesh faces (Panda3D, Blender API, ..)

Using Shapely to check if the intersection geometry bound lies within the "active" z-coordinate range of the barriers works, but is severely limiting to the kind of 3D barriers that can be used. I would call it a 2.5D solution..

Here is a bad example gif of a 2D scenario: I get hundreds of lines and want to check if they cross the green zones (only a few lines are shown here)

solution evolution

There are 3D geometry packages like trimesh and rhino3dm but they only support line-plane intersections. I don't know if I need a huge library or if it makes more sense to write something myself..

Also since speed is a priority, I also consider solutions not using Python. I am hoping that there is a mostly mathematical way to do it (without the overhead that I suspect comes with Panda3D or Blender, for example).

Answer 1

In one of your comments, you said:

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

So what I could suggest is to use the Möller–Trumbore algorithm for fast, minimum storage ray-triangle intersection.

I have developed a Python implementation that you can find here. As you can see from the docs, it's quite easy to use, for instance:

>>> 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)

And yes, you said that you are not actually dealing with rays, but that could be a starting point.