Timeline for Find shortest path (quickly) on the surface of a 3d model?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:18 | history | edited | CommunityBot | replaced http://gamedev.stackexchange.com/ with https://gamedev.stackexchange.com/ | |
| Oct 15, 2015 at 13:14 | comment | added | AturSams | The idia (intuition) I'm getting is that once you find a path of faces, you can essentially flatten this path and then finding the shortest path on the series of flattened faces can be done with the same tools used to find the shortest paths in a 3d polygonal obstacle course (i.e you embed the start point, end point and obstacle corners as vertices in a graph and use Dijkstra on the resulting graph). | |
| Oct 15, 2015 at 13:10 | vote | accept | AturSams | ||
| Oct 15, 2015 at 11:07 | history | edited | snake5 | CC BY-SA 3.0 | added 1254 characters in body |
| Oct 15, 2015 at 10:51 | comment | added | snake5 | @zehelvion In other words, you should 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. I'll update the answer to include pseudocode. | |
| Oct 15, 2015 at 10:38 | comment | added | AturSams | Ok, I reread the last part of the answer. It is not clear to me. Specifically "any point on the edge is going to keep the path inside all visited triangles." and "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."; I think in essence this is the answer to the question and it's pretty brief and not lucid. | |
| Oct 15, 2015 at 10:33 | comment | added | AturSams | Ok, thanks! now I get it. So there is a refinement phase after you compute the shortest path on the dual graph (a graph where faces are vertices). | |
| Oct 15, 2015 at 10:32 | comment | added | snake5 | @zehelvion The path is not computed along edges, it's computed over triangles, across edges. Triangles are nodes, edges are links. When a path of triangles is computed, path points can be placed on crossing edge midpoints and then iterated towards the shortest path using the method described in the last paragraph. With enough iterations (even 1-5 should give a fairly good result) you should have a good approximation of the shortest path. | |
| Oct 15, 2015 at 10:25 | comment | added | AturSams | I mean, I don't see how the absolute shortest path is computed. I don't think you understood the ziggy zaginess issue described in the question or I don't understand the answer. It smells like this would still ziggy zag rougelike style instead of providing a good approximation of the true shortest path. | |
| Oct 15, 2015 at 10:00 | comment | added | snake5 | @zehelvion Length? I don't see it mentioned in the original question. Anyway, path is an ordered set of points, every two consecutive points form a path segment. Seems obvious to add path segment lengths together. | |
| Oct 15, 2015 at 9:50 | comment | added | AturSams | There are no orbifolds. I've got triangle adjacency computed. Do not understand how the length of a path is computed in this answer. | |
| Oct 15, 2015 at 8:20 | history | answered | snake5 | CC BY-SA 3.0 |