# Finding shortest path on mesh

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

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.

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

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

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

No problem.

Hmmâ€¦ Maybe switch to a â€śboss-safeâ€ť avatar? (Edit: Much better! )

3 Likes

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

thank you for suggestion

1 Like

i will check it <3

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

Hey @Manoj_Prasad did you manage to get it working?