Re: Acceleration Structures For Vertex Snapping

On 11/19/2010 1:31 PM, [email protected] wrote:
>
> Sebastian Sylvan wrote:
>>> 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.
>>> [...]
>>
>> You could try some sort of BVH (e.g. an AABB tree) in world space,
>
> Vertex snapping is the same as vertex welding, for which
> a spatial hash gives you O(1) operations for a single vertex.

To snap based on screen-space coordinates, you either need to use a 2D 
hash that you rebuild every time the camera position/data changes, or 
visit all hash cells along a "fat ray" (intersection of a cone with your 
partitioning grid - messy and not O(1)).

2D hash is pretty damn practical though. You build it the first time 
it's needed after a camera position change (it's a fairly trivial 
addition to the brute-force solution and doesn't make it much more 
expensive), and then you can use it for subsequent frames. As long as 
you're not moving the camera every frame while moving a vertex, you're fine.

-Fabian

------------------------------------------------------------------------------
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list