Re: [Algorithms] Acceleration Structures For Vertex Snapping

[Sebastian S. <seb...@gm...>]

On Fri, Nov 19, 2010 at 10:43 PM, Jeff Russell <je...@8m...>wrote:

> 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.
>
>
If we're talking about welding (which was not the original question, as I
understand it). Then you can probably modify the distance threshold criteria
slightly so that it's okay to weld with any vertex in the 3x3 neighbourhood
of current cell in the appropriately sized grid. Then you'll only ever get
at most one vertex per cell (the second, etc., will be discarded due to
welding).

-- 
Sebastian Sylvan