gdalgorithms-list

[Algorithms] Acceleration Structures For Vertex Snapping

[Alexander S. <sha...@gm...>]

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.

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Chris G. <cg...@va...>]

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.

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Nicholas F. <nic...@un...>]

As far as I remember, what we did in Unity for our vertex snapping is to find the object under the mouse pointer, then snap to nearest vertex in that (by just going through the vertices in the model and finding the nearest in O(n) time. That drastically reduces the dataset :)

It's cheating, really - but there's a fair chance that if I'm vertexsnapping and dragging something on to a table, then it's because I want to snap the object to the table, and not to the floor below (or even worse: to some vertex that's in another room through 5 walls 3 miles away).

Either way: unless you're very resource constrained, I'd say you should do some broadphase culling (do normal cull-for-rendering in 10 pixels around the mouse) - then you shouldn't need to be very clever about finding the actual vertex. 

This approach also has the look-and-feel advantage that you won't snap an object to very far away in screen space (which looks jarring and feels wrong). It's a bit like docking toolbar windows in photoshop: you want them to snap somewhat, but if the snapping is too 'eager', it'll feel pretty bad.

Cheers,
Nicholas Francis
main editor dude, Unity.


On Nov 19, 2010, at 2:46 PM, Alexander Shafranov wrote:

> 
> 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 ?

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Alexander S. <sha...@gm...>]

Hi guys,

Thanks a lot for your suggestions !

I'm now assured to do a 'brute force' approach.

Cheers,
Alexander.

On Fri, Nov 19, 2010 at 8:08 PM, Nicholas Francis <nic...@un...>wrote:

> As far as I remember, what we did in Unity for our vertex snapping is to
> find the object under the mouse pointer, then snap to nearest vertex in that
> (by just going through the vertices in the model and finding the nearest in
> O(n) time. That drastically reduces the dataset :)
>
> It's cheating, really - but there's a fair chance that if I'm
> vertexsnapping and dragging something on to a table, then it's because I
> want to snap the object to the table, and not to the floor below (or even
> worse: to some vertex that's in another room through 5 walls 3 miles away).
>
> Either way: unless you're very resource constrained, I'd say you should do
> some broadphase culling (do normal cull-for-rendering in 10 pixels around
> the mouse) - then you shouldn't need to be very clever about finding the
> actual vertex.
>
> This approach also has the look-and-feel advantage that you won't snap an
> object to very far away in screen space (which looks jarring and feels
> wrong). It's a bit like docking toolbar windows in photoshop: you want them
> to snap somewhat, but if the snapping is too 'eager', it'll feel pretty bad.
>
> Cheers,
> Nicholas Francis
> main editor dude, Unity.
>
>
> On Nov 19, 2010, at 2:46 PM, Alexander Shafranov wrote:
>
> >
> > 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 ?
>
>
>
> ------------------------------------------------------------------------------
> 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
>

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

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[<chr...@pl...>]

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.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Oscar F. <os...@tr...>]

O(1) implies hash lookup is direct array index ... surely best case lookup
is O(n * log( n ))? Or care to explain where I am going wrong on my
thinking? Ta
On 19 Nov 2010 22:09, <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.
>
>
> Christer Ericson, Director of Tools and Technology
> Sony Computer Entertainment, Santa Monica
>
>
>
------------------------------------------------------------------------------
> 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

Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

On 11/19/2010 2:15 PM, Oscar Forth wrote:
> O(1) implies hash lookup is direct array index ... surely best case
> lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> my thinking? Ta

Vertex snapping: Take your snapping distance d
Imagine an infinite uniform grid with cell edge length e >= 2d.
Every vertex within d units of your query vertex must be either in the 
same cell or in one of the directly adjacent cells (that's 2^n cells to 
check where n is your dimension).
Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite 
grid into a very practical hash-table :)

For vertex welding, the weld operation ensures that the number of points 
in each infinite grid cell is <= some constant C(n,e/d). Size the hash 
table according to the number of vertices and the expected number of 
items in a cell is also a small constant. That makes the whole thing 
expected O(1).

-Fabian

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Jeff R. <je...@8m...>]

It's not *really* O(1), since you can have an arbitrary number of vertices
in a single hash cell (worst case would be the entire mesh). Only perfect
hashing would allow for O(1) worst case behavior. It's really O(n) worst
case, but since the n is divided by such a large constant in practice it is
still a very fast approach.

On Fri, Nov 19, 2010 at 4:31 PM, Fabian Giesen <ry...@gm...> wrote:

> On 11/19/2010 2:15 PM, Oscar Forth wrote:
> > O(1) implies hash lookup is direct array index ... surely best case
> > lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> > my thinking? Ta
>
> Vertex snapping: Take your snapping distance d
> Imagine an infinite uniform grid with cell edge length e >= 2d.
> Every vertex within d units of your query vertex must be either in the
> same cell or in one of the directly adjacent cells (that's 2^n cells to
> check where n is your dimension).
> Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite
> grid into a very practical hash-table :)
>
> For vertex welding, the weld operation ensures that the number of points
> in each infinite grid cell is <= some constant C(n,e/d). Size the hash
> table according to the number of vertices and the expected number of
> items in a cell is also a small constant. That makes the whole thing
> expected O(1).
>
> -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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

On Fri, Nov 19, 2010 at 10:43 PM, Jeff Russell <je...@8m...>wrote:

> It's not *really* O(1), since you can have an arbitrary number of vertices
> in a single hash cell (worst case would be the entire mesh). Only perfect
> hashing would allow for O(1) worst case behavior. It's really O(n) worst
> case, but since the n is divided by such a large constant in practice it is
> still a very fast approach.
>
>
If we're talking about welding (which was not the original question, as I
understand it). Then you can probably modify the distance threshold criteria
slightly so that it's okay to weld with any vertex in the 3x3 neighbourhood
of current cell in the appropriately sized grid. Then you'll only ever get
at most one vertex per cell (the second, etc., will be discarded due to
welding).

-- 
Sebastian Sylvan

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Mat N. <mat...@bu...>]

On a related note, is there a way to hash two points such that they map to the same value if they are within specified distance d of each other? Obviously you can hash down to their positions quantized to a cell of d, but if the two points happen to be in two different cells but less than d apart they hash to different values.

MSN
From: Jeff Russell [mailto:je...@8m...]
Sent: Friday, November 19, 2010 2:43 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Acceleration Structures For Vertex Snapping

It's not *really* O(1), since you can have an arbitrary number of vertices in a single hash cell (worst case would be the entire mesh). Only perfect hashing would allow for O(1) worst case behavior. It's really O(n) worst case, but since the n is divided by such a large constant in practice it is still a very fast approach.
On Fri, Nov 19, 2010 at 4:31 PM, Fabian Giesen <ry...@gm...<mailto:ry...@gm...>> wrote:
On 11/19/2010 2:15 PM, Oscar Forth wrote:
> O(1) implies hash lookup is direct array index ... surely best case
> lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> my thinking? Ta
Vertex snapping: Take your snapping distance d
Imagine an infinite uniform grid with cell edge length e >= 2d.
Every vertex within d units of your query vertex must be either in the
same cell or in one of the directly adjacent cells (that's 2^n cells to
check where n is your dimension).
Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite
grid into a very practical hash-table :)

For vertex welding, the weld operation ensures that the number of points
in each infinite grid cell is <= some constant C(n,e/d). Size the hash
table according to the number of vertices and the expected number of
items in a cell is also a small constant. That makes the whole thing
expected O(1).

-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
GDA...@li...<mailto:GDA...@li...>
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



--
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com<http://www.8monkeylabs.com>

Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

On 11/19/2010 3:18 PM, Mat Noguchi wrote:
> On a related note, is there a way to hash two points such that they map
> to the same value if they are within specified distance d of each other?
> Obviously you can hash down to their positions quantized to a cell of d,
> but if the two points happen to be in two different cells but less than
> d apart they hash to different values.

There isn't (except for the trivial case where your hash function maps 
everything into the same bucket). Look at the set of points

   H(v) := { x | h(x) = v }

where h is your hash function and v is some arbitrary hash bucket. H(v) 
is a set, and that set has a boundary. Pick a point on the boundary and 
there'll be "adjacent" points just outside the set (which by definition 
means they hash to a different cell).

-Fabian

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Niklas F. <ni...@fr...>]

On Sat, Nov 20, 2010 at 12:18 AM, Mat Noguchi <mat...@bu...> wrote:

> On a related note, is there a way to hash two points such that they map to
> the same value if they are within specified distance d of each other?
> Obviously you can hash down to their positions quantized to a cell of d, but
> if the two points happen to be in two different cells but less than d apart
> they hash to different values.
>

No. If any points within distance e should hash to the same value then p and
p + e should hash to the same value. But p + e and p + 2e should also hash
to the same value. By extension p and p + ne should hash to the same value.
You can only do that if all points hash to the same value.

But what you can do (that sometimes is interesting) is find two hash
functions h & g such that if |p - q| < e then either h(p) == h(q) or g(p) ==
g(q).

For 1-dimensional floats you could for instance use:

h(x) = floor(x / 2e)
g(x) = floor(x / 2e + 0.5)

// Niklas

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Richard F. <ra...@gm...>]

Although theoretically impossible, it might be practically possible.
Fabian and Niklas are right in that you cannot hash to similar values,
and Niklas even has a good idea on how to circumvent the problem, the
only issue is, you need 2^D where D is the dimensionality of your data
set. This is probably why Niklas mentions using two hashes.

for a 3D solution (which I think is what you're after), then
quantisation is key. You could quantise to e (where e is your largest
snap), and then inside that space, hash the 8 closest different
positions around your point.

assuming an e of 1

v(5.2,1.3,2.2) -> q(5,1,2) & d(.2,.3,.2)
from this produce a set of 8 ([2,2,2]) hashes from the floor and
ceiling values, but, store the hashes based on the evenness of the
quantised axes.

e.g. hash for (5,1,2) goes into the [1,1,0] element of the 2x2x2 array
becuase 5 and 1 are odd they go in the second element of their axis.
other hashes: (5,1,3)->[1,1,1], (6,1,2)->[0,1,0], etc...
this means that hashes for 5-6,1,2,2-3 are the the 2x2x2 array.

with this done, you can know you're within 'e', if any of the 8 parts
of the array match.

e.g.testing against v(6.1,1.3, 1.8) (hashes 6-7,1-2,1,2 in the 2x2x2 array)
the hashes at [0,1,0], and [0,0,0] will match as they will be the
hashes for (6,2,2) and (6,1,2).



so


On 19 November 2010 23:18, Mat Noguchi <mat...@bu...> wrote:
> On a related note, is there a way to hash two points such that they map to
> the same value if they are within specified distance d of each other?
> Obviously you can hash down to their positions quantized to a cell of d, but
> if the two points happen to be in two different cells but less than d apart
> they hash to different values.
>
>
>
> MSN
>
> From: Jeff Russell [mailto:je...@8m...]
> Sent: Friday, November 19, 2010 2:43 PM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Acceleration Structures For Vertex Snapping
>
>
>
> It's not *really* O(1), since you can have an arbitrary number of vertices
> in a single hash cell (worst case would be the entire mesh). Only perfect
> hashing would allow for O(1) worst case behavior. It's really O(n) worst
> case, but since the n is divided by such a large constant in practice it is
> still a very fast approach.
>
> On Fri, Nov 19, 2010 at 4:31 PM, Fabian Giesen <ry...@gm...> wrote:
>
> On 11/19/2010 2:15 PM, Oscar Forth wrote:
>> O(1) implies hash lookup is direct array index ... surely best case
>> lookup is O(n * log( n ))? Or care to explain where I am going wrong on
>> my thinking? Ta
>
> Vertex snapping: Take your snapping distance d
> Imagine an infinite uniform grid with cell edge length e >= 2d.
> Every vertex within d units of your query vertex must be either in the
> same cell or in one of the directly adjacent cells (that's 2^n cells to
> check where n is your dimension).
> Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite
> grid into a very practical hash-table :)
>
> For vertex welding, the weld operation ensures that the number of points
> in each infinite grid cell is <= some constant C(n,e/d). Size the hash
> table according to the number of vertices and the expected number of
> items in a cell is also a small constant. That makes the whole thing
> expected O(1).
>
> -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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
> --
> Jeff Russell
> Engineer, 8monkey Labs
> www.8monkeylabs.com
>
> ------------------------------------------------------------------------------
> 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
>



-- 
fabs();
Just because the world is full of people that think just like you,
doesn't mean the other ones can't be right.

Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

On 22.11.2010 02:59, Richard Fabian wrote:
> Although theoretically impossible, it might be practically possible.
> Fabian and Niklas are right in that you cannot hash to similar values,
> and Niklas even has a good idea on how to circumvent the problem, the
> only issue is, you need 2^D where D is the dimensionality of your data
> set. This is probably why Niklas mentions using two hashes.
>
> for a 3D solution (which I think is what you're after), then
> quantisation is key. You could quantise to e (where e is your largest
> snap), and then inside that space, hash the 8 closest different
> positions around your point.

That's the algorithm I described earlier :)

You still have a 2^D factor in there though, which is impractical for 
high dimensions (as are most conventional spatial partitioning methods). 
A different construction based on hashing is Locality Sensitive Hashing 
(LSH) which solves this problem approximately (to a given error 
tolerance) and is significantly faster in practice for data with high 
dimensionality.

-Fabian

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

Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

On 11/19/2010 2:43 PM, Jeff Russell wrote:
> It's not *really* O(1), since you can have an arbitrary number of
> vertices in a single hash cell (worst case would be the entire mesh).
> Only perfect hashing would allow for O(1) worst case behavior.

What do you mean by "not *really* O(1)"? Big O notation just means we're 
talking about asymptotic complexity, it doesn't have to be worst-case 
(hence "expected O(1)").

 > It's
 > really O(n) worst case, but since the n is divided by such a large
 > constant in practice it is still a very fast approach.

No, that's not true. Hash tables are fast in practice because they do a 
small number of reasonably fast operations in the average case, not 
because they do a large number of operations in a magically ultra-fast 
fashion (which would be the O(N) with tiny constant that you decribe). 
Their worst-case is definitely linear and the constant isn't tiny as 
everyone who's ever used a bad hash function knows :). Worst-case and 
average-case analysis are just different things.

-Fabian

Re: [Algorithms] Acceleration Structures For Vertex Snapping

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

On Fri, Nov 19, 2010 at 11:28 PM, Fabian Giesen <ry...@gm...> wrote:

> On 11/19/2010 2:43 PM, Jeff Russell wrote:
> > It's not *really* O(1), since you can have an arbitrary number of
> > vertices in a single hash cell (worst case would be the entire mesh).
> > Only perfect hashing would allow for O(1) worst case behavior.
>
> What do you mean by "not *really* O(1)"? Big O notation just means we're
> talking about asymptotic complexity, it doesn't have to be worst-case
> (hence "expected O(1)").
>

O(1) only means that "something" is bounded by some constant as n goes to
infinity, so you're both right, but you're talking about different
"somethings".

Its a good idea to specify what that "something" is, e.g. "average case
time", "worst case time", "best case time", or "amortized time". It's a
fuzzy convention, I guess, but generally people probably assume you're
talking about worst case running times if you aren't explicit about meaning
one of the others (probably because upper bounds are somewhat more
interesting for the worst cases than for the others, where Big Theta or Big
Omega are more used). Or maybe that's just me. I tend to slap a "more or
less" on there to cover my bases :-).

-- 
Sebastian Sylvan

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Jeff R. <je...@8m...>]

Okay, worst case is different from average case, granted. But since the cell
size in this case is fixed (related to snap distance), the number of mesh
vertices that cell will contain varies with n. An example: if your mesh was
evenly tessellated in space, the number of vertices in a single cell would
be n / k, where k is the number of cells your mesh intersects. That makes
finding the closest vertex an "n / k" operation, which is definitely not
constant time. That is what I meant when I said it was O(n). It would only
be O(1) average case if we had a "vertices per cell" limit we could somehow
enforce, but we don't.

No, that's not true. Hash tables are fast in practice because they do a
> small number of reasonably fast operations in the average case, not
> because they do a large number of operations in a magically ultra-fast
> fashion (which would be the O(N) with tiny constant that you decribe).
>

There's no magic, an O(N) algorithm does not necessarily do N operations.
Hash tables are fast because they run in O(n / k) time, where k is
comparable to or larger than n. If you make k a function of n, as is often
done, then it becomes constant time average case.

-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[<chr...@pl...>]

Fabian Giesen wrote:

> On 11/19/2010 2:15 PM, Oscar Forth wrote:
> > O(1) implies hash lookup is direct array index ... surely best case
> > lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> > my thinking? Ta
>
> Vertex snapping: Take your snapping distance d
> Imagine an infinite uniform grid with cell edge length e >= 2d.
> Every vertex within d units of your query vertex must be either in the
> same cell or in one of the directly adjacent cells (that's 2^n cells to
> check where n is your dimension).
> Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite
> grid into a very practical hash-table :)
>
> For vertex welding, the weld operation ensures that the number of points
> in each infinite grid cell is <= some constant C(n,e/d). Size the hash
> table according to the number of vertices and the expected number of
> items in a cell is also a small constant. That makes the whole thing
> expected O(1).

Exactly. I've described this in various internet posts over the
years, and also describe it in detail in Section 12.1 of RTCD
along with code in case anyone needs further elaboration.

For vertex welding/snapping within a threshold this approach
cannot be beat.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Jeff R. <je...@8m...>]

Christer is right (as usual) about the weld operation, it would allow you to
get expected O(1). In my posts I was talking about the snapping question the
OP had, so maybe we were talking about different things Fabian.

Jeff

On Fri, Nov 19, 2010 at 6:27 PM, <chr...@pl...>wrote:

>
> Fabian Giesen wrote:
>
> > On 11/19/2010 2:15 PM, Oscar Forth wrote:
> > > O(1) implies hash lookup is direct array index ... surely best case
> > > lookup is O(n * log( n ))? Or care to explain where I am going wrong on
> > > my thinking? Ta
> >
> > Vertex snapping: Take your snapping distance d
> > Imagine an infinite uniform grid with cell edge length e >= 2d.
> > Every vertex within d units of your query vertex must be either in the
> > same cell or in one of the directly adjacent cells (that's 2^n cells to
> > check where n is your dimension).
> > Hash on grid cell coordinates (x,y,z) to turn the theoretical infinite
> > grid into a very practical hash-table :)
> >
> > For vertex welding, the weld operation ensures that the number of points
> > in each infinite grid cell is <= some constant C(n,e/d). Size the hash
> > table according to the number of vertices and the expected number of
> > items in a cell is also a small constant. That makes the whole thing
> > expected O(1).
>
> Exactly. I've described this in various internet posts over the
> years, and also describe it in detail in Section 12.1 of RTCD
> along with code in case anyone needs further elaboration.
>
> For vertex welding/snapping within a threshold this approach
> cannot be beat.
>
>
> Christer Ericson, Director of Tools and Technology
> Sony Computer Entertainment, Santa Monica
>
>
>
> ------------------------------------------------------------------------------
> 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
>



-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Ola O. <ola...@gm...>]

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

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
>