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>