sphere on a grid
Author
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!
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
