# sphere on a grid

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

## 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 on other sites
is this even the right place to ask this?

##### 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 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 on other sites
im moveing this . but i cant delete it.. so some1 kill it or just dont post here

##### 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 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 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 on other sites
Quote:
 Original post by kalixxxi 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 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.

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• ### Forum Statistics

• Total Topics
631424
• Total Posts
3000008
×