Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Vilya H. <vil...@gm...>]

This is what I currently do. It is nice and fast, but breaks down when
you've got vertices clustered tightly together in screen space. You may have
multiple vertices projecting to the same pixel, but you can only store one
ID. If that's not a problem for your app, it's a great choice.

It would be interesting to try this approach in conjunction with an
A-buffer. Getting a list of the vertices at each pixel is exactly what you
want here.

Vil


On 20 November 2010 12:56, Ola Olsson <ola...@gm...> wrote:

>  Just thought I'd point out that there is, most probably, a device already
> in your target system that is pretty darn good at this sort of thing. That
> is, the GPU, chances are your vertex data is already uploaded as well. So,
> you can draw the vertices as points with ID's as colors, then read back a
> little region around the point of interest and see what's there. If needed
> you can always read back Z as well to check which is closest.
>
> Actually, for snapping you'd get by fine with just a chunk of Z buffer,
> wouldnt you? Reconstruct the position from Z buffer and away you go,
> right? (may have missed something here... Maybe not precise enough?)
>
> The render only needs doing whenever the viewpoint has changed, and reading
> back a handful of pixels over PCI express is not too slow, though I dunno
> what the latencies actually are.
>
> Cheers.
> .ola
>
> ----- Original Message -----
> *From:* Chris Green <cg...@va...>
> *To:* Game Development Algorithms<gda...@li...>
> *Sent:* Friday, November 19, 2010 6:01 PM
> *Subject:* Re: [Algorithms] Acceleration Structures For Vertex Snapping
>
>  If you are optimizing for development time, and you only do this once in
> response to a user action (meaning you don't need to be any faster than 18ms
> or so), don't discount a brute force sequential scan.
>
> If your point data is stored in a memory/simd friendly format, you can
> perform a ridiculous number of point comparison tests per second on a modern
> multicore processor. If you have easy threading primitives in your system,
> it's a trivial operation to thread as well.
>
>
>
> If you are going to use an auxiliary data structure to accelerate this
> operation, you'll have to keep it incrementally updated, since if you built
> the data structure every time you snapped, you'd have to examine all the
> points anyway to build it.
>
>
>
> If you do have such a large number of points or need to do this operation
> for many points per mouse-event, you want to optimize it for cache layout
> and access pattern - it takes much longer to fetch the point position from
> DRAM than it does to perform the distance^2 calculation, so you don't want
> to swallow up all your memory bandwidth with pointers. For example, if using
> a kd-tree, you don't want your leaf nodes to be individual points; you want
> them to be cache-aligned simd arrays of points.
>
>
>
>
>
>
>
>
>
> *From:* Alexander Shafranov [mailto:sha...@gm...]
> *Sent:* Friday, November 19, 2010 5:46 AM
> *To:* Game Development Algorithms
> *Subject:* [Algorithms] Acceleration Structures For Vertex Snapping
>
>
>
> 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.
>
> ------------------------------
>
>
> ------------------------------------------------------------------------------
> 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
>
>
>
> ------------------------------------------------------------------------------
> 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
>