hi!
given a 3D grid, a 3d point as sphere center and a radius, i'd like to quickly calculate all cells contained or intersected by the sphere.
Currently i take the the (gridaligned) boundingbox of the sphere and calculate the two cells for the min anx max point of this boundingbox. then, for each cell between those two cells, i do a box-sphere intersection test.
would be great if there was something more efficient
thanks!
There's a version of the Bresenham algorithm for drawing circles. Consider the two dimensional place at z=0 (assume the sphere is at 0,0,0 for now), and look at only the x-y plane of grid points. Starting at x= R, y=0, follow the Bresenham algorithm up to y = y_R, x=0, except instead of drawing, you just use the result to know that all grid points with lower x coordinates are inside the circle, down to x=x_center. Put those in a list, count them or otherwise make note of. When done with two dimensional problem, repeat with varying z and using a reduced radius R(z) = sqrt(R^2-z^2) in place of R, until z=R.
If the sphere center is indeed located on a grid point, you know that every grid point inside or outside the right half of the sphere has a mirror partner on the left side, and likewise top/bottom, so you can do half the counting/listing per dimension. You can also save time running Bresenham only to the 45 degree line, because any x,y point relative to the center has a partner y,x. If the sphere can be anywhere, you will have to compute results for each octant.
No matter how efficiently you calculate an individual cell being inside or outside the sphere, your algorithm will always be O(radius^3) because you have to mark that many cells. DarenW's suggestion of the midpoint (aka Bresenham) circle algorithm could give a constant factor speedup, as could simply testing for intersection using the squared radius to avoid the sqrt() call.
If you want better than O(r^3) performance, then you may be able to use an octree instead of a flat grid. Each node of the tree could be marked as being entirely inside, entirely outside, or partially inside the sphere. For partially inside nodes, you recurse down the tree until you get to the finest-grained cells. This will still require marking O(r^2 log r) nodes [O(r^2) nodes on the boundary, O(log r) steps through the tree to get to each of them], so it might not be worth the trouble in your application.