Re: [Algorithms] Acceleration Structures For Vertex Snapping

[<chr...@pl...>]

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