# sphere on a grid

## Recommended Posts

kalixxx    105
ok lets say i got a 3d grid (sectors of the same size) and there is a sphere in it(middle point and radius) i want to know what sectors are in or touching the sphere. like drawing a circle only in 3d. http://en.wikipedia.org/wiki/Midpoint_circle_algorithm i looked on the net and i think there is a name for this and im just asking the wrong question!

##### Share on other sites
CaspianB    309
Each sector, I assume, is going to be defined as a unit cube with corners at specific x, y, and z positions in your 3d world.

If you only want the sectors that have some point inside the sphere (not fully contained within the sphere) then I think the easiest way to find that would be like this:

Using the radius of your sphere, cull out all sectors that are obviously too far away (by making a bounding cube that envelops your sphere). The remaining sectors are those that are contained inside your cube. You would then check the distance from those sectors' corners to your sphere's center. If that distance is less than your sphere's radius, the sector is partially inside the sphere. You can somewhat speed up the distance check by squaring the radius and not calculating the square root of the distance.

##### Share on other sites
Atrix256    539
Since everything is axis aligned, you can simplify this.

Instead of checking the distance of the corners, you can do a simple AABB vs AABB test which is just made up of a couple < and > checks, no distance tests at all so it would be UBER fast.

But even more simply, you can look at the minimum x and figure out which column that lies in, and look at the maximum x and figure out which column that lies in and then you'd know that those 2 columns (assuming they are different) and all columns between them contain the cube (sphere).

Do that for the Y and Z axis too and you have the full range of all the grid cells that this sphere lies in.

That would be really simple math and amazingly fast due to extremely simple calculations.

##### Share on other sites
kalixxx    105
whats AABB test??

##### Share on other sites
DevFred    840
Quote:
 Original post by kalixxxwhats AABB test??

AABB