Re: Acceleration Structures For Vertex Snapping

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 <[email protected]> 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:[email protected]]
> 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 <[email protected]> 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
> [email protected]
> 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
> [email protected]
> 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.

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