Sign in to follow this  

sphere on a grid

This topic is 2838 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites

This topic is 2838 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this