Search code examples
algorithmgeometrycomputational-geometrymesh

Shortest distance between two point on surface

I'm working on my bachelor thesis (on Computer Science) and right now I'm having a problem about finding shortest path between two points on 3D triangular mesh that is manifold. I already read about MMP, but which computes distance function $d(x)$ between given point and vertex $x$ on mesh.

I got to know that the problem I'm solving is named Geodesics but What I really couldn't find is some good algorithm which uses A* for finding shortest path between two given points on two given vertices.

I 'invented' also algorithm which uses A* by using Euclidian Distance Heuristics and correction after finding new Point on any Edge.. I also have edges saved in half-edge structure.

So my main idea is this:

  1. We will find closest edge by A* algorithm and find on this edge point with minimalizing function $f(x) + g(x)$ where $f$ is our current distance and $g$ is heuristics(euclidean distance)
  2. Everytime we find new edge, we will unfold current mesh and find closest path to our starting point

So now my questions:

  • Do you know some research paper which talks about this problem ??
  • Why nobody wrote about algorithm that uses A* ??
  • What are your opinions about algorithm I proposed ?
Solution

  • I am no expert in the matter so read with prejudice. Also sorry this is more of a comment than answer...

    First You should clarify some things:

    • the mesh is convex or concave?
    • are the path always on surface or can fly between faces on the outside (if concave) but never inside?
    • are the start/end points on edges of faces or can be inside?

    Assuming concave, points on edges and only surface paths...

    I think the graph A* approach is unusable as there is infinite possible paths between point and any edge of the same face so how you test all of them?

    If you really want A* then you can do something similar to raster A*

    1. so resample all your edges to more points

      so either n points or use some density like 10 points per average edge length or some detail size.

    2. use graph A* on resampled points (do not handle them as edges anymore)

    However this will produce only close to shortest path so in order to improve the accuracy you should recursively resample the edges near used point with higher and higher density until the distance between resampled points get smaller than accuracy.

    Another option would be using something similar to CCD (cyclic coordinate descent) so:

    1. create plane that goes through your 2 points and center of your mesh
    2. create path that goes through all intersection of plane and faces between the 2 points (use the shorter on from the 2 options)
    3. iterativelly move intersections back and forward and use greedy approach to get the result

    However this might get stuck in local minima... You could use search/fitting approaches instead but those will get very slow with increasing number of faces

    I got the feeling you might also do this using RANSAC ...

    From my point of view I think the first A* approach is the most promising, you just need linked list of points per each edge and one cost counter per each its point from this you can simply encode even the recursive improvement of accuracy. It can be done even in-place so no reallocation needed in the recursion ... And also the algo is not complicated so you should have no problems implementing it, and the result is guaranteed which is not the case with other approaches I mention... Another pros is that it can be used even if start/endpoint does not belong to edge...