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.
i looked on the net and i think there is a name for this and im just asking the wrong question!
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.
Author
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
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
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
-me
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!
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!
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
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
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
