Range search within specified radius in an Octree

I am interested in particle algorithms like the N-Body, and SPH. One of the important steps in these applications is, given a query point, to find the particles lying within a specified sphere of radius 'h'.

Now I have heard that Octrees are good spatial data structures for problems like N-body or SPH.

But after the octree construction, I cannot understand how the "locate particles within a radius" step is performed . Can someone please开发者_运维技巧 point me to some references, papers or articles for doing this step?

Guessing that Octree contains 3dPoint objects: "locate particles within a radius 3 of Point p" can be expressed as "Return all points contained in Octreecells touching or intersecting with Sphere(center p, radius r)" To test if a cell intersects a sphere:

dx,dy,dz = 0;
if (pX < minX of Cell)
    dx = |px - minX|
else if (px > maxX of Cell)
    dx = |px-maxX|
Same for other dimensions

return (|dx,dy,dz|<=r)

k-d trees are also good data structures to use for this and are commonly used for nearest neighbor searches.