1

So I'm trying to draw a sphere out of discrete "blocks." I need this to be done with integers. I'm trying to shy away from trig functions because of that. Bresenham's circle algorithm is the only thing that seems reasonable to me at this point, but I can't think of a way to make it work in 3 dimensions.

I also want this to work for ellipsoids too.

Also, out of curiosity, I was wondering, how could this algorithm work in N dimensions? There obviously isn't any practical use for this (at least that I can think of) but I'm curious anyway.

SpaceFace
  • 1,492
  • 3
  • 15
  • 29
  • Actually I'm not sure there is a straightforward generalization from the circle algorithm to a sphere. The circle in principle is regularly subdivided into any whole number of equal parts, while the sphere is regularly subdivided into equal parts only in a tightly constrained number of ways. Perhaps it's worth saying a bit more to define the problem. Are blocks cubic, of equal size? Can they overlap? Or is it really a problem of selecting lattice points "closest" to the sphere's surface? – hardmath Mar 20 '12 at 15:56
  • Also, did you see [this earlier Question](http://stackoverflow.com/q/564492/487781) and set of Answers? – hardmath Mar 20 '12 at 15:58

1 Answers1

1

You'll probably have to draw your sphere in layers. For a sphere with radius R, centred on CX, CY, CZ, the bottom-most block will be at CX, CY, (CZ-R). As you step one layer up, test [PX+1, PX, PX-1], [PY+1, PY, PY-1], PZ+1 (here, "P" is for "Plotted" to see which one is closest to the distance R from CX,CY,CZ.

For each individual layer, I'd probably use the (3D) distance from CX,CY,CZ, because it's slightly simpler. There's also a fair bit of symmetry to exploit, to drop the number of calculations needed.

Vatine
  • 20,782
  • 4
  • 54
  • 70