Finding shortest path on mesh

Questions
1

hello kindly may someone help me with finding shortest path i want to draw line ( curves ) like lasso tool on mesh with many face and nodes so may anyone kindly help me please because i found something similar but slow and not accurate something like this video


2

Yes, it is a really sketchy implementation, and for the old Geometry class. But it does something right too, by building a graph of the faces and applying a search algorithm. It should IMO more cleanly have separated the original geometry from the graph, and (definitely) the temporary structures of the search from the graph too. Also, the A* algorithm, or one of its variants, is a much better fit when you want to find the shortest distance, as it will (in this case) use straight-line distance as a guide to narrowing the search. It is easy to implement, but you will need a priority queue, which can be a min-heap.

3

kindly could you give me example , and do you mean i should stick with that algorithm that i linked from github ?

4

No, I do not think you should stick to that, as it neither works nor is efficient or cleanly implemented.

And no, I will not write an example. I recommend checking out the graph and graph search implementations in @Mugen87 's repository https://github.com/Mugen87/yuka (which I assume is well-made, although I think you can get away with an even lighter and less general structure)

1 Like
5

thank you a lot :slight_smile: is there any other recommendations you want to suggest ?

6

No problem.

Hmm… Maybe switch to a “boss-safe” avatar? :wink: (Edit: Much better! :smiley: )

3 Likes
7

There is a fast implementation of A* in three-pathfinding. The library has a couple limitations because it assumes the input mesh was generated by a navigation mesh tool:

  1. Self-intersecting geometry, and probably several other cases that would be common in an arbitrary 3D model, may give unpredictable results.
  2. The path is not guaranteed to be the shortest possible – good results require fairly uniform triangle sizes in the mesh.
1 Like
8

thank you for suggestion :smiley:

1 Like
9

i will check it <3

10

Can someone help me to implement lasso tool on mesh? something like in video. @nesquik011

11

Hey @Manoj_Prasad did you manage to get it working?