Jump to content
  • Advertisement
Sign in to follow this  
kalixxx

sphere on a grid

This topic is 3049 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!