0
$\begingroup$

The following is an excerpt from a 2005 paper on geodesics on triangular meshes, taken from section 3.5

enter image description here

In this case $p$ is a point on some arbitrary face in a mesh, $p'$ is a point on one of the 3 edges in the triangle and $D(p')$ is the geodesic distance to that point.

I am very confused as to how this minimization is achieved. The paper doesn't go into detail, so I assume it's trivial, but I am not seeing the solution of the top of my head.

Given an arbitrary interval (segment) the shortest point to it is either the orthogonal projection of the point $p$ onto the segment or one of the end points of the segment (depending on where $p$ is located with respect to the segment).

However, this is not necessarily the point that minimizes the expression $||p - p'|| + D(p')$ or in other words, $p'$ is not, in general, the orthogonal projection of $p$ onto the segment.

The only algorithm I have is to naively check epsilon offsets along the segment and picking the shortest one. There has to be a better way than that.

I have drawn a diagram on Geogebra to show the problem:

enter image description here

$\overline{BA}$ is the segment, $C$ is the point we are looking to minimize the distance from. $D$ is the frontier point, which is the orthogonal projection of the Geodesic source (the source point of all geodesics in the mesh), $E$ is the orthogonal projection of $C$ onto $\overline{BA}$. Clearly the optimal point is somewhere between $E$ and $D$ but I don't know how to find it.

$\endgroup$
  • 1
    $\begingroup$ Doesn't 4.3 and onwards deal with this? It's probably also a good idea to consider: code.google.com/archive/p/geodesic/wikis/ExactGeodesic.wiki $\endgroup$ – lightxbulb Jul 4 at 7:08
  • $\begingroup$ Unfortunately section 4, section 4,3 included deals with their approximating method, however I need to use the exact geodesic, not the approximation. Those notes are indeed interesting, but they don't seem to address the problem I am currently facing, at minimum not explicitly. I have a hypothesis as to what the proper way to do this is, I am testing it right now, if successful I will answer my own question. $\endgroup$ – Makogan Jul 4 at 20:03
0
$\begingroup$

The solution I found to this problem is to ALWAYS intersect the edge. In other words the distance to the geodesic source $v$ from a point $p$ is $||v-p'|| + ||p - p'||$ where $p'$ is the intersection of the line $\overline{vp}$ with the current edge. In cases where $p'$ is "behind" $p$ with respect to $v$ we set the distance to the edge to be infinity.

The above seems to work in the simple tests I have generated at minimum.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.