I have a triangle strip in 3D. see illustration here

The triangles do not lie in one plane. The number of triangles is limited (around 20). Furthermore I have two points (the start point and the end point). The two points lie either on an edge of a triangle or inside a triangle.

For programming I am looking for an algorithm which calculates the polyline representing the shortest line between the two points on the triangle strip.

I had a look at different books, papers, discussions etc on the subject of calculating the shortest path or the geodesic path on triangle meshes. The suggested algorithms seem quite complex.

Since my setup looks simpler (only a triangle strip - not a mesh, limited number of triangles) I try to find an easier solution.

One idea is to flatten the triangle strip so that all triangles lie in the plane of the first triangle. The plan is to rotate the second triangle around its connecting edge with the first triangle so that it becomes in plane with the first triangle. Then I continue this method for the other triangles until all of them are in plane. Then I draw a straight line between the two points and calculate the intersections with the connecting triangle edges to get the polyline.

Two questions:

  1. Is such a claculated polyline really the shortest path between the two points?

  2. What other strategies or algorithms (simple and fast) could be used to solve the problem?


A partial answer: Yes, a straight line on the flattened strip is the shortest path. Think about what happenes to the total path length as you shift any of the intersection points of this path with a triangle edge: the path gets longer.

Be careful, though. Your strip may connect in such a way that a straight line joining the two points will leave the strip. You’ll have to take that possibility into account for a full solution.

Update: I haven’t proven this, but my intuition tells me that if the straight-line path does leave the strip, then adjusting it to get the shortest path is pretty simple. Find the first edge crossing that takes you off the strip and move this intersection to the vertex of that triangle that’s nearest the ultimate goal. Then, take that as your new starting point, draw the straight line from there and iterate.

  • 1
    $\begingroup$ Exactly, and I think that the case of the straight line leaving the strip is the crux of the problem. This is where the actual challenge is hiding. The rest is more or less straight forward. $\endgroup$ – Futurologist Oct 1 '16 at 3:59
  • $\begingroup$ I wonder if it would help if you made a line in 3d from start point to end point, and then try to project it to all of the planes specified by the triangles, and then calculate the line-line intersection points of neighbouring triangles? $\endgroup$ – tp1 Oct 1 '16 at 13:33
  • $\begingroup$ @tp1 I am not sure if I understand you correctly. You suggest to project the direct line between the two points in space onto each triangle individually. Two questions: 1. Do the projected lines intersect the triangle edge in such a way that for two neighbouring triangles the intersection points are always identical so that they result in a polyline? 2. If 1. is true does the resulting polyline is the shortest path? $\endgroup$ – user3384674 Oct 1 '16 at 14:20
  • $\begingroup$ @user3384674 When you modify the initial line to avoid an exit, the new line might exit the strip at a point closer to the starting point than the exit you’re trying to avoid, so you’ll have to start over with that new exit point/edge. $\endgroup$ – amd Oct 3 '16 at 18:08

I'll write that in a answer instead of comments:

The following algorithm should work:

  1. Take a line in 3d from start point to end point
  2. Project it to a plane specified by the 3 points of each triangle
  3. End result is (infinite) line in the same plane where triangle is in
  4. Finding the endpoints could be done by 3d line-line intersection of neighbouring triangle's lines.
  5. Connecting the line segments should be easy since they're in same order than your original triangles
  • $\begingroup$ Let's assume the triangle strip and the two points are set up in such a way the the line in 3d between the two points is perpendicular to the plane of a triangle (e.g. the first triangle). The projection of the line on this triangle would result in a point. $\endgroup$ – user3384674 Oct 1 '16 at 18:28

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.