Re: [Algorithms] Acceleration Structures For Vertex Snapping
Brought to you by:
vexxed72
Menu
▾
▴
Re: [Algorithms] Acceleration Structures For Vertex Snapping
|
From: Ola O. <ola...@gm...> - 2010-11-20 12:56:59
|
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 To: Game Development Algorithms 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 |
