Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Fabian G. <ry...@gm...>]

On 11/19/2010 1:31 PM, chr...@pl... 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