/*
    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


  Changelog

  2005-11-12
    Put new way of inserting spheres into the linked lists (look for "LINKED LIST: Add")
    Now z sorts them in a really basic O(N^2) way
    Hopefully the speed improvement will come from not having to check every sphere
      when hit testing a pixel

  */


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

#define RT_SCANLINE_HEAP_ARRAY_SIZE      1000000
#define RT_SCANLINE_MAX_SPHERES_PER_LINE 1000000



#ifdef RT_SORT_SPHERES_ON_Z

void rt_scanline_processTree( int index );

#endif

  //- 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

#ifdef RT_SORT_SPHERES_ON_Z
  //  v0014: we only need to go through the linked list once because the spheres are in order
  int a, n;
  a = 0;
#endif

    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

      //  LINKED LIST: Add

      if( sphere[s].in_xy == 3 )
      {
        //- pre v0014: put at end of list

        //  TODO: RT_SCANLINE_ADD_TO_LINKED_LIST( s ) because it's used in a few places
#ifdef RT_SORT_SPHERES_ON_Z
        //- v0014: put in order of sphere.z - sphere.rad - smallest first
        
        //  Step through list until we pass behind or reach the end
///*
        float zz = sphere[s].z - sphere[s].rad;

        //  This loop finds the point where the new sphere should be inserted

        n = sphere[a].in_next;

        while( n > 0 && zz > sphere[n].z - sphere[n].rad )
        {
          a = n;
          n = sphere[a].in_next;
        }

        //  insert into list after a

        sphere[n].in_prev = s;  //  set previous pointer in one after
        sphere[s].in_next = n;

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

        a = s;
//*/

#else
        //- pre v0014: put at end of list
        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;
#endif


      }
    }


  }



  //---- 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)

      //  LINKED LIST: Remove

      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

#ifdef RT_SORT_SPHERES_ON_Z
  //  v0014: we only need to go through the linked list once because the spheres are in order
  int a, n;
  a = 0;
#endif

    //  v0014: TODO: Make the list sorted already, so we just need one pass

    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

        //  LINKED LIST: Add
#ifdef RT_SORT_SPHERES_ON_Z
        //- v0014: put in order of sphere.z - sphere.rad - smallest first
        
        //  Step through list until we pass behind or reach the end
///*
        float zz = sphere[s].z - sphere[s].rad;

        //  This loop finds the point where the new sphere should be inserted

        n = sphere[a].in_next;

        while( n > 0 && zz > sphere[n].z - sphere[n].rad )
        {
          a = n;
          n = sphere[a].in_next;
        }

        //  insert into list after a

        sphere[ n ].in_prev = s;  //  set previous pointer in one after
        sphere[s].in_next = n;

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

        a = s;
//*/

#else
        //- pre v0014: put at end of list
        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;
#endif
      
      
      }
    }

    //  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

#ifdef RT_SORT_SPHERES_ON_Z
  //  v0014: we only need to go through the linked list once because the spheres are in order
  int a, n;
  a = 0;
#endif

    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

        //  LINKED LIST: Add

#ifdef RT_SORT_SPHERES_ON_Z
        //- v0014: put in order of sphere.z - sphere.rad - smallest first
        
        //  Step through list until we pass behind or reach the end
///*
        float zz = sphere[s].z - sphere[s].rad;

        //  This loop finds the point where the new sphere should be inserted

        n = sphere[a].in_next;

        while( n > 0 && zz > sphere[n].z - sphere[n].rad )
        {
          a = n;
          n = sphere[a].in_next;
        }

        //  insert into list after a

        sphere[ n ].in_prev = s;  //  set previous pointer in one after
        sphere[s].in_next = n;

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

        a = s;
//*/

#else
        //- pre v0014: put at end of list
        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;
#endif
      }
    }

    //  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

#ifdef RT_SORT_SPHERES_ON_Z
    extern RT_SPHERE_BTREE_NODE rt_sphere_btree_node[ RT_SCENE_MAXSPHERES ];

    RT_SCENE *rt_scanline_scene;
    RT_VIEW *rt_scanline_view;

#endif


  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

    //  v0014: Put on in order defined by binary tree of spheres

#ifdef RT_SORT_SPHERES_ON_Z

    rt_scanline_scene = scene;
    rt_scanline_view = view;

    rt_scanline_processTree( 0 );

#else

    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 x-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 );
        }
      }

    }

#endif

  }




//---- rt_scanline_processTree

#ifdef RT_SORT_SPHERES_ON_Z

//  added in v0014 to insert into linked lists in z minus radius order

void rt_scanline_processTree( int index )
{
  float bounds[4];

  /*
    process the more tree first then the node itself then the less tree
    it's done this way round because the spheres are inserted on the front of the linked lists
    so need to be processed in reverse order.
  */

  //  Process more tree

  if( rt_sphere_btree_node[index].more > -1 )
  {
    rt_scanline_processTree( rt_sphere_btree_node[index].more );
  }

  //  Add the sphere at this node

  int i = rt_sphere_btree_node[index].sphere_index;

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

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

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

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

      if( rt_scanline_scene->sphere[i].x1 < rt_scanline_view->w )
      {
        int x = rt_scanline_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 x-end list

      if( rt_scanline_scene->sphere[i].x2 >= 0 && rt_scanline_scene->sphere[i].x2 < rt_scanline_view->w )
      {
        int x = rt_scanline_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( rt_scanline_scene->sphere[i].y1 < rt_scanline_view->h )
      {
        int y = rt_scanline_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( rt_scanline_scene->sphere[i].y2 >= 0 && rt_scanline_scene->sphere[i].y2 < rt_scanline_view->h )
      {
        int y = rt_scanline_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 ++;
      }
    }
  }




  //  Process more tree

  if( rt_sphere_btree_node[index].less > -1 )
  {
    rt_scanline_processTree( rt_sphere_btree_node[index].less );
  }



}


#endif