title: algorithm to rasterize and fill a hypersphere?
body: <p>I'm trying to rasterize and fill a hypersphere. In essence, I have a d-dimensional grid of fixed size and a sphere (center, radius) and want to find out which cells of the grid overlap with the sphere and store their coordinates.</p>
  
  <p>I am aware of the <a href="http://en.wikipedia.org/wiki/Midpoint_circle_algorithm" rel="nofollow noreferrer">Midpoint circle algorithm</a> which takes advantage of 8-way mirroring and produces the outer cells (border) of a circle. I have also altered the linked wikipedia code so as to fill the circle (that is, to produce the coordinates of all cells inside the border).</p>
  
  <p>However I am unaware of any algorithms for higher dimension. For example in 4d, I've been thinking of implementing by producing all possible circles like in the following pseudocode. The basic idea is that since a 4d sphere is (x-x0)<strong>2 + (y-y0)**2 + (z-z0)**2 + (k-k0)**2 = r</strong>2, this is equal to (x-x0)<strong>2 + (y-y0)**2 = r</strong>2 - (z-z0)**2 - (k-k0)**2. Since I know how to draw a circle, i just need to produce all circles for all possible values of z and k. </p>
  
  <pre><code>assume center=(x0,y0,z0,k0) and radius r
  
  for all dimensions equal or higher than 2://this is z and k
    //make a list of possible values this dimension can take
    //from z0 to z0+radius with a step of 1
    all_lists.append([dim0,dim0+1,...,dim0+radius])
  
  produce the product of all the lists in all_lists
  //now i have a list [[z0,k0],[z0,k0+1],....,[z0+1,k0],[z0+1,k0+1],....,[z0+radius,k0],...[z0+radius,k0+radius]]
  
  for every element l of the list, compute the radius of the circular "cut"
    l.append(r**2 - z**2 - k**2)
  
  Now call the Midpoint Circle Algorithm, but for every (x,y) pair that it produces, we need to export 4 points, namely (x,y,±z,±k)
  </code></pre>
  
  <p>This <a href="https://stackoverflow.com/questions/3613190/need-an-algorithm-to-pixelate-an-n-dimensional-hypersphere">question</a> seems relevant, but I don't understand the answer.</p>