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.