Find shortest path (quickly) on the surface of a 3d model?

Question

Imagine this scenario: we have a 3d model, for instance a doughnut, apple or an orange (possibly something more complex). There's an insect (let's say an ant) on the surface of that food item. Now that ant wishes to reach a certain specific coordinate embedded on the surface of the 3d object in the shortest time possible (using the shortest path, ignoring physics).

Now the ant AI could use Dijkstra on the original mesh but that might be low-res so the ant will zig-zag on the surface, outlining the shapes of blocky faces. You could split the faces but the angular nature of the edges, making up the structure of the mesh will continue to drive the ant to more in ziggy-zaggy like manner (imagine a rougelike with very small squares, you can still only move in 8 directions at any given point).

What we did is split the edges (of the model) to evenly-sized pieces and embedded "navigation vertices" between these pieces, we then connected the vertices of each edge with vertices of other edges sharing a face with it (4 other edges because faces are triangular). This works pretty well cause it means the any can travel freely between faces, ignoring their shape almost completely (unless they are very small and were not split).

We also have the ant "pulled" (dragged even) by an imaginary ant that is a few steps ahead to completely eliminate the more rigid areas in the path (think sharp corners). Sounds great right?

But this is not terribly fast. Any advice about that is appreciated.

Answer 1

Precalculate triangle adjacency data, then what you'll have will basically be a navigation mesh. Any pathfinding algorithm (like A*) will be able to work on that.

That's of course assuming the mesh doesn't have 3 or more triangles sharing the same edge, things could look strange in that case. All connections except the topmost would have to be manually disconnected to fix that.

This could help with building triangle adjacency data: Building triangle adjacency data

One note about data though - it should help performance if you treat the navigation mesh as any other - array of vertices, array of indices (triangles). The typical way is to create a graph and that's just going to slow things down in terms of memory allocations and cache.

As for pathfinding, there's no need to split anything - when you've built a path out of triangles, you also have the edges that connect the triangles. Due to the property of triangles (and convex polygons in general) that every ray that hits a polygon is going to hit it exactly twice (entry and exit points), any point on the edge is going to keep the path inside all visited triangles.

To optimize the path, the method I've found is to iteratively project line between previous/next points on the line of the current point, then limit it inside that line.

EDIT:

This is how I imagine line projection to work:

Intersect line formed by previous/next points with the straight line defined by crossed edge, then project this point onto the straight line, as well as both endpoints of the edge - from there you can limit the projection by the projections of edge endpoints, thus keeping the intersection point inside the edge. To retrieve the new point, subtract the old projection and add the new one.

The last part in pseudocode:

// p1 - edge point 1, p2 - edge point 2
// pp - projection of line between previous/next path points onto straight line formed by the edge
// new_pp - projection, limited to the edge
dir = normalize( p1 - p0 ); // edge axis
proj_p1 = dot( dir, p1 );
proj_p2 = dot( dir, p2 );
proj_pp = dot( dir, pp );
cproj = clamp( proj_pp, proj_p1, proj_p2 );
new_pp = pp + dir * ( cproj - proj_pp );

For the intersection test, look for any segment-plane intersection test. The segment is defined by previous/next path points. A plane can be defined by two cross products - first one between path segment and edge, second from the new vector and the edge - this is the plane normal. Any point on edge is a good plane reference point.