Re: Acceleration Structures For Vertex Snapping

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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list