Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

Hi guys,

Thanks a lot for your suggestions !

I'm now assured to do a 'brute force' approach.

Cheers,
Alexander.

On Fri, Nov 19, 2010 at 8:08 PM, Nicholas Francis <nic...@un...>wrote:

> 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 ?
>
>
>
> ------------------------------------------------------------------------------
> Beautiful is writing same markup. Internet Explorer 9 supports
> standards for HTML5, CSS3, SVG 1.1,  ECMAScript5, and DOM L2 & L3.
> Spend less time writing and  rewriting code and more time creating great
> experiences on the web. Be a part of the beta today
> http://p.sf.net/sfu/msIE9-sfdev2dev
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>