Sign in to follow this  

Locating neigbours within a radius R in a octree

This topic is 4659 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I am using an octree for storing 3d points. How can you efficient locate the neighbours within a radius R of a point P? I was thinking to create a sphere around P. Then to traverse the octree and do a sphere-box collision. Only if the sphere collides with a box in the octree and that box is not a leaf, i will recurse on his children. If the box is a leaf, i will store the this box in a list. After traversing the octree, i got all the boxes with points that are posible neighbours. If i go on with this method, how can you do simple sphere box collission? I hope someone can help me. Thanks at advance Takis

Share this post


Link to post
Share on other sites
thats not a bad method. sphere box intersection isnt too hard to figure out, and can be googled easily.

another method would be neighbor pointers, recursing into all neighbors that lie within the sphere to obtain your set.

also, if a box lies completely within a sphere, all points inside it are guaranteed to do so aswell. but then again testing a point against a sphere is trivial anyway.

Share this post


Link to post
Share on other sites
Thank you very much for "Arvo's algorithm: box-sphere collision".
I works very fine and quick. Eelco you are also welcome for your solution, but i stick to the first one.

Thanks
Takis

Share this post


Link to post
Share on other sites

This topic is 4659 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this