3

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

Andre Geo
  • 31
  • 4
  • Hi! So these 3D barriers are unstructured triangulated surfaces, right? Thanks! – blunova Nov 20 '22 at 23:07
  • Hi, no. Right now they are just polygons with a max and min _height_ field (barriers) and also a raster grid (ground surface) – Andre Geo Nov 21 '22 at 10:54
  • Thanks. Can you provide more details in your question about this, please? Because you talked about *3D meshes*, it's kinda confusing at this moment. – blunova Nov 21 '22 at 10:58
  • @AndreGeo Do you need to implement a collision algorithm from scratch or can you use an existing 3D engine that might already have some of these collision detection problems solved (e.g. Unity/Unreal/Godot/etc.) ? (Algos aren't my strongest point, but I like your approach with a coarser check first (convex hull). maybe compute sparse points along the curve and if you know the building heights, check in 2D first if any of the points would be above or inside a building polygon, then increase descrete points only around those building areas ? in 3D the discrete points can boxes and buildings also – George Profenza Nov 21 '22 at 13:14
  • ...for an initial / coarse test (e.g. as a rough "collision mesh") and only if box inside box returns a collision do a more detailed mesh test). It's also worth remembering map data can be outdated so your algo might need to pair with a camera based one (e.g. visual odometry/SLAM/etc.) – George Profenza Nov 21 '22 at 13:17
  • I can use existing engines, and Panda3D has been recommended to me. But it seems to me that a game engine is overkill, and I need the most lightweight solution possible. Even something that just checks line-segment vs triangle intersection should work.. then the hardest part will be converting my data to meshes – Andre Geo Nov 21 '22 at 13:41
  • There are a lot of ray-tracing solutions but my line segments are not rays... I am thinking of drawing a bounding box around the 3D curve and taking all the faces/hulls/triangles inside that box, then check each line segment for intersection with any of them. But it might be faster to use point-in-hull checking? This I don't know at all – Andre Geo Nov 21 '22 at 13:44

1 Answers1

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.

blunova
  • 2,122
  • 3
  • 9
  • 21