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