Spherical mesh fast intersection

Question

given the 3D grid, the 3d point as the center of the sphere and the radius, I would like to quickly calculate all the cells contained or intersected by the sphere.

I am currently taking the (gridaligned) bounding box of a sphere and calculating two cells for the minimum box maximum point of this bounding box. then for each cell between these two cells I do a box intersection test.

it would be great if there was something more effective

thanks!

Answer 1

There is a version of Breshenem's algorithm for drawing circles. Consider a two-dimensional place at z = 0 (suppose that at the moment the sphere is 0,0,0), and look only at the xy plane of the grid points. Starting from x = R, y = 0, follow the Breschenem algorithm to y = y_R, x = 0, except that instead of drawing, you simply use the result to know that all grid points with lower x coordinates are inside the circle, down to x = x_center. Put them on the list, count or otherwise pay attention. When this is done with a two-dimensional problem, repeat with a change in z and using the radius R (z) = sqrt (R ^ 2-z ^ 2) instead of R, until z = R.

If the center of the sphere is really located at the grid point, you know that each grid point inside or outside the right half of the sphere has a mirror partner on the left side, as well as top / bottom, so you can do half counting / enumeration per measurement. You can also save time by running Bresenham only on a 45-degree line, because any point x, y relative to the center has a partner y, x. If the sphere can be anywhere, you will have to calculate the results for each octantant.

Answer 2

Regardless of how efficiently you calculate a single cell inside or outside the sphere, your algorithm will always be O (radius ^ 3), because you have to mark this many cells. The DarenW proposal of the midpoint circle algorithm (aka Bresenham) can give a constant acceleration coefficient, as this can simply be checked for intersection using the square of the radius to avoid calling sqrt ().

If you want to improve O (r ^ 3) performance, you can use octree instead of flat mesh. Each tree node can be marked as completely inside, completely outside, or partially inside a sphere. For partially internal nodes, you return the tree down until you reach the thinnest cells. It will still require labeling the nodes O (r ^ 2 log r) nodes [O (r ^ 2) on the border, O (r ^ 2) goes through the tree to reach each of them], so maybe this is not a problem in your application.