Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Nicholas F. <nic...@un...>]

As far as I remember, what we did in Unity for our vertex snapping is to find the object under the mouse pointer, then snap to nearest vertex in that (by just going through the vertices in the model and finding the nearest in O(n) time. That drastically reduces the dataset :)

It's cheating, really - but there's a fair chance that if I'm vertexsnapping and dragging something on to a table, then it's because I want to snap the object to the table, and not to the floor below (or even worse: to some vertex that's in another room through 5 walls 3 miles away).

Either way: unless you're very resource constrained, I'd say you should do some broadphase culling (do normal cull-for-rendering in 10 pixels around the mouse) - then you shouldn't need to be very clever about finding the actual vertex. 

This approach also has the look-and-feel advantage that you won't snap an object to very far away in screen space (which looks jarring and feels wrong). It's a bit like docking toolbar windows in photoshop: you want them to snap somewhat, but if the snapping is too 'eager', it'll feel pretty bad.

Cheers,
Nicholas Francis
main editor dude, Unity.


On Nov 19, 2010, at 2:46 PM, Alexander Shafranov wrote:

> 
> 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 ?