Sign in to follow this  
kalixxx

sphere on a grid

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. 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
The way I would do it, would be to represent the grid with a spatial partitioning tree. One could use simple math to test which node of the tree, whether it is by simply testing if the center of the sphere is in the cube or another method, and after that, you could check which other cubes or nodes are withing the radius of the sphere from the center point.

Share this post


Link to post
Share on other sites
i dont want to look if each node is in the sphere!
i know there is an algorithm out there to do this!
like drawing a circle only in 3d.
http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

Share this post


Link to post
Share on other sites
breadth first search of the sectors starting at the center of the sphere. Do a box-in-sphere test to see if each sector is in the sphere.

-me

Share this post


Link to post
Share on other sites
If you make an axis aligned bounding box of the sphere (by using it's radius to come up with the width, height and depth of the box -> dont forget that width, height and depth will be DOUBLE the radius) it should be a pretty simple problem to solve.

If i asked you "how would i know which grid cells an axis aligned box sits in" i think you could give me the answer pretty easily :P

Since your world is divided into grids, you'll get the same answer for your sphere as you would a bounding box for your sphere anyhow.

HTH!

Share this post


Link to post
Share on other sites
Your problem is very similar to the problem of drawing a 2D circle, where you need to figure out which pixels should be colored.

Only in your case it's in 3D. But the algorithm should be the same.

Here's something that may be a good start:

http://cs.fit.edu/~wds/classes/graphics/Rasterize/rasterize/rasterize.html#SECTION00053000000000000000

Share this post


Link to post
Share on other sites
Quote:
Original post by kalixxx
i dont want to look if each node is in the sphere!
i know there is an algorithm out there to do this!
like drawing a circle only in 3d.
http://en.wikipedia.org/wiki/Midpoint_circle_algorithm


...How were you intending to find which nodes were in the sphere without looking?

Share this post


Link to post
Share on other sites
Quote:
Original post by Ectara
...How were you intending to find which nodes were in the sphere without looking?


He wants a raster-scan-style algorithm, rather than a rejection-test-style algorithm.

Share this post


Link to post
Share on other sites

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