Re: [Algorithms] Fast nearest neighbour queries

[Chad H. <ch...@ha...>]

Eberly's site had to be moved due to a trademark issue.  You can read 
about it here:

http://www.gamedev.net/community/forums/topic.asp?topic_id=310637

The current site for Magic Software is:

http://www.geometrictools.com/

  - Chad

Pete Brubaker wrote:
> I would suggest a k-dimensional tree.  Search for kD tree on google.
>  
> There is also an implementation in the back of this book.
>  
> http://graphics.ucsd.edu/~henrik/papers/book/
>  
> And I was going to suggest David Eberly's site "Magic Software" but it 
> appears that it's gone.  (http://www.magic-software.com)
>  
> --Pete
> 
> ------------------------------------------------------------------------
> *From:* gda...@li... 
> [mailto:gda...@li...] *On Behalf Of 
> *Miles Macklin
> *Sent:* Monday, April 18, 2005 9:27 PM
> *To:* gda...@li...
> *Subject:* [Algorithms] Fast nearest neighbour queries
> 
> We have artist placed sample points in our game levels and would like to 
> find the closest sample to a point in space.  The samples are static and 
> are a 3d position with no size.
>  
> What are some ways of accelerating nearest neighbour queries ?  I have 
> looked at Thatcher's loose octree article but thought it might be 
> overkill for this situation and am also not clear on how to use it to 
> quickly find the nearest neighbour.
>  
> There isn't necessarily a distance bound so we can't just intersect a 
> sphere and check those.  We already use an aabb tree and portal cell 
> system for geometry but neither of these seem particularly well suited.
>  
> Any ides appreciated,
> 
> Miles