Re: Acceleration Structures For Vertex Snapping

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

------------------------------------------------------------------------------
Increase Visibility of Your 3D Game App & Earn a Chance To Win $500!
Tap into the largest installed PC base & get more eyes on your game by
optimizing for Intel(R) Graphics Technology. Get started today with the
Intel(R) Software Partner Program. Five $500 cash prizes are up for grabs.
http://p.sf.net/sfu/intelisp-dev2dev
_______________________________________________
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