/*
    The does precalculation to work out what spheres can possibly be on each
     horizontal and vertical line of pixels on the screen.

    Stores linked lists for each pixel row & column for:
      . Spheres which are in this line but not the last
      . Spheres which are in this line but not in the next

    Stored in reverse order (largest spherenumber first in linked list)


  Then when you iterate over the pixels on the screen line by line, pixel by pixel
    flags in each sphere are changed to signify whether we are in any of it's rows or columns.

  An active list is maintained of spheres whose bounding boxes we are currently inside.
    This list is a doubly-linked list, kept inside the sphere structures themselves.

  Sphere 0 (the background) uses it's in_next and in_prev to point to the start and end of the list

  */


//  excessive sizes for arrays until I make it more intelligent

#define RT_SCANLINE_HEAP_ARRAY_SIZE      100000
#define RT_SCANLINE_MAX_SPHERES_PER_LINE 100000



  //- Sphere bounding boxes

  //  There are four arrays of linked lists.
  //  . for each horizontal pixel position, which spheres start on this pixel
  //  . for each horizontal pixel position, which spheres end on this pixel
  //  . for each vertical pixel position, which spheres start on this pixel
  //  . for each vertical pixel position, which spheres end on this pixel

  int y_spheres_start_count = 0;
  int y_spheres_end_count = 0;
  int x_spheres_start_count = 0;
  int x_spheres_end_count = 0;

  union
  {
    struct  //  Linked list node - serves two purposes:
    {
      int sphere;  //  As an object node, stores a sphere number
      int next;
    } node;
    struct
    {
      int count;   //   as a header node - this field stores a count of the number of spheres in the list
      int first;
    } header;
  }
  y_spheres_start[ RT_SCANLINE_HEAP_ARRAY_SIZE ],
  y_spheres_end[ RT_SCANLINE_HEAP_ARRAY_SIZE ],
  x_spheres_start[ RT_SCANLINE_HEAP_ARRAY_SIZE ],
  x_spheres_end[ RT_SCANLINE_HEAP_ARRAY_SIZE ];



  //---- Data for scanline iteration

  int rt_scanline_current;
  int rt_scanline_sphere_list[ RT_SCANLINE_MAX_SPHERES_PER_LINE ];
  int rt_scanline_sphere_count;



  //---- rt_scanline_firstRow

  //  Sets the scanline thingy up for the first row of superpixels

  void rt_scanline_firstRow( RT_SCENE *scene )
  {
    int i, s;

    RT_SPHERE *sphere = scene->sphere;

    // Clear the doubly-linked list of currently available spheres

    sphere[0].in_next = 0;  //  only need to do these on sphere 0 I think
    sphere[0].in_prev = 0;

    for(i=0; i<scene->numSpheres; i++ )
    {
      sphere[i].in_xy = 0;
    }

    //  Set the flags for the spheres which first appear at x position 0

    for( i = x_spheres_start[0].header.first; i != -1; i = x_spheres_start[i].node.next )
    {
      s = x_spheres_start[i].node.sphere;

      //  s is the index of each sphere appearing on column 0

      sphere[s].in_xy = 1;
    }

    //  Set the flags for the spheres which first appear at y position 0
    //  While I am doing this I build the linked list of spheres available in the top left superpixel

    for( i = y_spheres_start[0].header.first; i != -1; i = y_spheres_start[i].node.next )
    {
      s = y_spheres_start[i].node.sphere;

      //  s is the index of each sphere appearing on row 0

      sphere[s].in_xy |= 2;

      //  If both flags are set this gets added to linked list

      if( sphere[s].in_xy == 3 )
      {
        sphere[s].in_prev = sphere[0].in_prev;
        sphere[s].in_next = 0;

        sphere[ sphere[0].in_prev ].in_next = s;

        sphere[0].in_prev = s;
      }
    }


  }



  //---- rt_scanline_nextColumn

  //  Moves onto the next superpixel horizontally, updating linked list of available spheres

  void rt_scanline_nextColumn( RT_SCENE *scene, int x )
  {
    int i, s;
    int prev, next;

    RT_SPHERE *sphere = scene->sphere;

    x >>= 2;

    //  Go through each sphere we have just left, removing from list

    for( i = x_spheres_end[x].header.first; i != -1; i = x_spheres_end[i].node.next )
    {
      s = x_spheres_end[i].node.sphere;

      //  remove from linked list if the flag was 3 (ie it was in both x and y)

      if( sphere[s].in_xy == 3 )
      {
        prev = sphere[s].in_prev;
        next = sphere[s].in_next;

        sphere[ prev ].in_next = next;
        sphere[ next ].in_prev = prev;
      }

      sphere[s].in_xy &= 0xFFFFFFFE;  // remove the x flag (0x1)
    }

    //  Go through each sphere we have just come into, adding to list

    for( i = x_spheres_start[x].header.first; i != -1; i = x_spheres_start[i].node.next )
    {
      s = x_spheres_start[i].node.sphere;

      if( ( sphere[s].in_xy |= 1 ) == 3 ) //  set x flag
      {
        //  add to linked list if x and y flags both set

        sphere[s].in_prev = sphere[0].in_prev;
        sphere[s].in_next = 0;

        sphere[ sphere[0].in_prev ].in_next = s;

        sphere[0].in_prev = s;
      }
    }

    //  Phew!  Now we have an up-to-date linked list of the spheres available in this superpixel
  }



  //---- rt_scanline_nextRow

  //  Moves to the next row of pixels
  //  

  void rt_scanline_nextRow( RT_SCENE *scene, int y )
  {
    int i, s;

    RT_SPHERE *sphere = scene->sphere;

    y >>= 2;

    //  Wipe linked list

    sphere[0].in_next = 0;
    sphere[0].in_prev = 0;

    //  Go through each sphere we have just left, clearing it's y-flag

    for( i = y_spheres_end[y].header.first; i != -1; i = y_spheres_end[i].node.next )
    {
      s = y_spheres_end[i].node.sphere;
      sphere[s].in_xy &= 0xFFFFFFFD;  // remove the y flag (0x2)
    }

    //  Go through each sphere we have just come into, setting flag

    for( i = y_spheres_start[y].header.first; i != -1; i = y_spheres_start[i].node.next )
    {
      s = y_spheres_start[i].node.sphere;
      sphere[s].in_xy |= 2;  //  set y-flag
    }

    //  Now add add spheres from column 0 to linked list if they are also in this row

    for( i = x_spheres_start[0].header.first; i != -1; i = x_spheres_start[i].node.next )
    {
      s = x_spheres_start[i].node.sphere;

      if( ( sphere[s].in_xy |= 1 ) == 3 ) //  set x flag
      {
        //  add to linked list if x and y flags both set

        sphere[s].in_prev = sphere[0].in_prev;
        sphere[s].in_next = 0;

        sphere[ sphere[0].in_prev ].in_next = s;
        sphere[0].in_prev = s;
      }
    }

    //  Phew!  Now we have an up-to-date linked list of the spheres available in this superpixel
  }



  //---- rt_doScanlinePrecalc
  
  //  Sets up the linked lists of which spheres come and go across and down the screen

  void rt_doScanlinePrecalc( RT_VIEW *view, RT_SCENE *scene )
  {
    //  Set up blank linked lists (the first w & h elements just point to the start of the lists

    int i;

    x_spheres_start_count = 0;
    y_spheres_start_count = 0;
    x_spheres_end_count = 0;
    y_spheres_end_count = 0;

    for( i=0; i<view->w; i ++ )
    {
      x_spheres_start[ x_spheres_start_count ].header.count = 0;
      x_spheres_end  [ x_spheres_end_count   ].header.count = 0;
      x_spheres_start[ x_spheres_start_count ++ ].header.first = -1;
      x_spheres_end  [ x_spheres_end_count   ++ ].header.first = -1;
    }

    for( i=0; i<view->h; i ++ )
    {
      y_spheres_start[ y_spheres_start_count ].header.count = 0;
      y_spheres_end  [ y_spheres_end_count   ].header.count = 0;
      y_spheres_start[ y_spheres_start_count ++ ].header.first = -1;
      y_spheres_end  [ y_spheres_end_count   ++ ].header.first = -1;
    }

    //  Now loop through spheres calculating bounding box and adding to linked lists

    float bounds[4] = {0.1f, 0.2f, 0.3f, 0.4f};

    for( i=0; i < scene->numSpheres; i++ )
    {
      //  Get bounding box

      bool result = rt_sphere_boundingRect( scene->sphere[i].x, scene->sphere[i].y, scene->sphere[i].z, scene->sphere[i].rad, bounds );

      //  If onscreen, set sphere's details and add u1,v1,u2,v2 to appropriate linked lists

      if( result )
      {
        scene->sphere[i].x1 = (int)(( bounds[0]-view->bx1) / view->bdx     );
        scene->sphere[i].y1 = (int)( (bounds[1]-view->by1) / view->bdy     );
        scene->sphere[i].x2 = (int)( (bounds[2]-view->bx1) / view->bdx + 4 );
        scene->sphere[i].y2 = (int)( (bounds[3]-view->by1) / view->bdy + 4 );

        if( scene->sphere[i].x1 < 0 ) scene->sphere[i].x1 = 0;
        if( scene->sphere[i].y1 < 0 ) scene->sphere[i].y1 = 0;

        if( scene->sphere[i].y2 >= scene->sphere[i].y1 &&
            scene->sphere[i].y1 < view->h &&
            scene->sphere[i].x2 >= scene->sphere[i].x1 &&
            scene->sphere[i].x1 < view->w
          )
        {
          //  Add to x-start list

          if( scene->sphere[i].x1 < view->w )
          {
            int x = scene->sphere[i].x1 >> 2;

            x_spheres_start[ x_spheres_start_count ].node.sphere = i;
            x_spheres_start[ x_spheres_start_count ].node.next = x_spheres_start[ x ].header.first;
            x_spheres_start[ x ].header.first = x_spheres_start_count;
            x_spheres_start[ x ].header.count ++;
            x_spheres_start_count ++;
          }

          //  Add to y-end list

          if( scene->sphere[i].x2 >= 0 && scene->sphere[i].x2 < view->w )
          {
            int x = scene->sphere[i].x2 >> 2;
            x_spheres_end[ x_spheres_end_count ].node.sphere = i;
            x_spheres_end[ x_spheres_end_count ].node.next = x_spheres_end[ x ].header.first;
            x_spheres_end[ x ].header.first = x_spheres_end_count;
            x_spheres_end[ x ].header.count ++;
            x_spheres_end_count ++;
          }

          //  Add to y-start list

          if( scene->sphere[i].y1 < view->h )
          {
            int y = scene->sphere[i].y1 >> 2;
            y_spheres_start[ y_spheres_start_count ].node.sphere = i;
            y_spheres_start[ y_spheres_start_count ].node.next = y_spheres_start[ y ].header.first;
            y_spheres_start[ y ].header.first = y_spheres_start_count;
            y_spheres_start[ y ].header.count ++;
            y_spheres_start_count ++;
          }

          //  Add to y-end list

          if( scene->sphere[i].y2 >= 0 && scene->sphere[i].y2 < view->h )
          {
            int y = scene->sphere[i].y2 >> 2;
            y_spheres_end[ y_spheres_end_count ].node.sphere = i;
            y_spheres_end[ y_spheres_end_count ].node.next = y_spheres_end[ y ].header.first;
            y_spheres_end[ y ].header.first = y_spheres_end_count;
            y_spheres_end[ y ].header.count ++;
            y_spheres_end_count ++;
          }

  //        rt_setPixelAbs( view, scene->sphere[i].x1, scene->sphere[i].y1, scene->sphere[i].col );
  //        rt_setPixelAbs( view, scene->sphere[i].x2, scene->sphere[i].y1, scene->sphere[i].col );
  //        rt_setPixelAbs( view, scene->sphere[i].x1, scene->sphere[i].y2, scene->sphere[i].col );
  //        rt_setPixelAbs( view, scene->sphere[i].x2, scene->sphere[i].y2, scene->sphere[i].col );
        }
      }

    }
  }