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