using-fft-to-simulate-gravity.txt

Operation
-

The universe is DIM x DIM, and DIM must be a power of two.
The universe is tiling (wraps around at the edges)

(because it uses &(DIM-1) as a quick way of wrapping around,
and because the FFT expects powers of two (i think) )

The universe is represented by a mass and an x and y direction (velocity)
for each pixel in a DIM x DIM square.

The gravity calculation involves calculating the force on each pixel
from the rest of the universe:

  for each pixel A
  {
    force_x = 0
    force_y = 0

    for each pixel B except A
    {
      force_x += horizontal force on pixel A of pixel B
      force_y += vertical force on pixel A of pixel B
    }

    //  (force_x, force_y) is the total force on this pixel
    //  from the rest of the universe
  }

After the force is calculated it is used to modify the velocity of the pixel.

Because the universe wraps around, each of the other copies of the universe
has an influence.

  for each pixel A
  {
    force_x = 0
    force_y = 0

    for each tile
    {
      for each pixel B except A  //  i think you need to include A in all galaxies apart from real one?
      {
        force_x += horizontal force on pixel A of pixel B
        force_y += vertical force on pixel A of pixel B
      }
    }

    //  (force_x, force_y) is the total force on this pixel
    //  from the rest of the universe
  }

The force is a convolution of the mass array and the gravity force array.

To move the mass based on the force, start with an empty array (zero's)

  NEW_MASS = zero array

  for each pixel
  {
    M,DX,DY = pixel's mass and velocity

    NEW_X = pixel's x position + DX
    NEW_Y = pixel's y position + DY

    Place mass and velocity into NEW_MASS with sub-pixel accuracy
  }

To do a fast convolution of A and B (both power of two
The full sequence is:

  Create gravity lookup tables LOOKUPX and LOOKUPY

  each frame
  {
    FORCE_X = convolution of LOOKUPX and MASS
    FORCE_Y = convolution of LOOKUPY and MASS
    Apply FORCE_X,FORCE_Y to MASS
  }






  Create gravity lookup tables LOOKUPX and LOOKUPY
  Calculate fft of LOOKUPX as V0
  Calculate fft of LOOKUPY as V1

  each frame
  {
  }


The gravity force array can be precalculated and saved off.






Notes
-

. Horizontal and vertical bias because of the grid nature of the universe
  . Horiz and vertical streams coming out of tiny heavy galaxies when matter should be fired out in all directions
  . Long thin galaxies form which suspiciously travel exactly in the x or y dir