Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Sebastian S. <seb...@gm...>]

On Fri, Nov 19, 2010 at 1:46 PM, Alexander Shafranov <sha...@gm...>wrote:

> 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.
>
>
You could try some sort of BVH (e.g. an AABB tree) in world space, and then
just send a ray through it from the eye to the pivot point, and find the
nearest point to the ray by descending the tree. This means you don't have
to update the acceleration structure when the camera moves. And BVHs are
easy enough to update incrementally as objects themselves move, which is
nice.

As for the actual query, the first approach I can think of right now for an
AABB tree is based on the observation that you know that there's at least
one point on each /face/ of each AABB in the tree (assuming your AABBs were
built correctly), so for each child in a node find the furthest point on the
closest face, w.r.t. the ray. That gives you an upper bound of how far the
nearest point is, which you can then use to cull what children you need to
visit (by discarding any boxes whose closest point is further than this
distance).

I'll also plug my talk on R-trees from last GDC too (slides should be on
their website), which basically is just a very cache friendly way of
organising AABB trees. It's not clear that PCs have severe enough cache
penalties to motivate them, but it turned out (somewhat surprisingly to me)
that the construction logic for high-branching-factor trees ended up being
much simpler/robust than binary ones (esp. if you need to insert new objects
dynamically, which you frequently do), so even if you're not on an in-order
CPU with slow memory, it might still be worthwhile for simplicity reasons.
-- 
Sebastian Sylvan