search

mattrdowney / planetaria

A Unity framework for Euclidean 2-sphere games (e.g. 2D virtual reality games) [quasi-MIT license]
Other
10 stars 2 forks source link

Closest Vertex on Mesh algorithm #101

Open mattrdowney opened 6 years ago

mattrdowney commented 6 years ago

Pre-processing: compute Dictionary<int, List> (vertex and its adjacent vertices)

start at vertex 0 and move to next closest node via dot product (save previous node), whenever next closest node is previous node, find the closer of the two and return it.

mattrdowney commented 6 years ago

This is related to both pathfinding and vertex/grid snapping

mattrdowney commented 5 years ago

I feel like the end condition could have a logic error.

Originally I thought the issue was it could pick a 2nd or 3rd closest vertex (I don't think this is true, but it might be).

The real problem would be an infinite loop when you get to a triangle of closest values (rather than two points being the closest). This sort of issue could be due to determinism combined with triangle vertex ordering on a triangle that is equidistant from the target point. (This can be fixed by a greedy approach that stops when the distance from the target increases over an iteration, whereupon it can return the last value.)

Additionally, you can improve the expected running time by taking a sample of points (random or deterministic) during the setup phase and picking the closest one to the target location (it's a short-circuit technique, of sorts).

mattrdowney commented 5 years ago

It's worth noting that the above "fix" to avoid the infinite loop will cause an infinite loop if you continue searching when a solution is equally optimal. (Basically, be careful of < versus <=)

Another interesting note: since there can be more than one solution, the algorithm should not employ randomness anywhere. E.g. a user could become frustrated by a vertex clamp function teleporting between two or more vertices despite no user input.