[Algorithms] Acceleration Structures For Vertex Snapping

[Alexander S. <sha...@gm...>]

Hi guys,

I'm working on the vertex snapping feature for our level editor.

So, in vertex snapping mode all translates are snapped to the nearest vertex
on screen.

Brute force approach would be something like --

- project all vertices to screen-space
- find closest vertex to object's projected pivot

I know, that nearest point query is an O(log N) problem with kd-tree.
But, building kd-tree for mesh vertices doesn't help here, because the query
is 'nearest point in screen-space'.
Kd-tree can be built for a set of projected (2d) vertices, it doesn't sound
great though, since tree has to be rebuilt on any camera moves.

What would you recommend ?

Or maybe I'm overengineering here and something more brute force will work
good enough.

Cheers,
Alex.