#include "workrec.h"

#include "assert.h"

#include "prim.h"
#include "globals.h"
#include "kdtree.h"
#include "render_worker.h"
#include "raycastablelist.h"
#include "reconmap.h"
#include "render_thread.h"
#include "workqueue.h"
#include "ui_thread.h"
#include "common.h"
#include "intersect.h"
#include "wrlog.h"
#include "rwlog.h"

#define HYBRID_ON (!(truly_GS->_disabled_flags & DISABLE_HYBRID_FC))
#define PURE_ON (truly_GS->_disabled_flags & DISABLE_HYBRID_FC)

float WorkRec::_cr = .2;
float WorkRec::_cg = .2;
float WorkRec::_cb = .2;

#define DRAWOBJ if (drawing_flags & DRAW_WIREFRAME_OBJS) \
		  obj->Draw (RayCastable::WIREFRAME); \
		else \
		  obj->Draw (RayCastable::FILLED); 


int WorkRec::_frustum_straddler_intersect_calls;
int WorkRec::_frustum_straddler_intersect_success;
int WorkRec::_frustum_straddler_bbox_success;
int WorkRec::_frustum_incident_intersect_calls;
int WorkRec::_frustum_incident_intersect_success;
int WorkRec::_frustum_incident_bbox_success;

// CFT -- should be an installable function, with
// an alternative function:  pure octree traversal
void WorkRec::RayCast(const Ray &ray, Hit &hit, int x, int y, int drawing_flags)
{
  //#define DONT_USE_FRUSTA_PLANES
#ifdef DONT_USE_FRUSTA_PLANES
  if (!_cur_cell) return;

  ObjList *betty = _cur_cell->_objs;

  RayCastable *obj;
  const void *place;
  betty->Reset (place);
  while (place)
    {
      obj = betty->Peek (place);
      betty->Next (place);
      obj->Intersect (ray, hit);
    }
  return;
#else
  assert (!_got_total_hit);
  
  PlaneCache *pc = NULL;
  if (!(truly_GS->_disabled_flags & DISABLE_VIEWVEC_T))
    pc = _CS->_plane_cache;
  
  Stats stats;
  stats.num_intersections_overruled = &KDTree::_num_intersects_overruled;
  stats.num_axis_checks = &KDTree::_num_axis_checks;
  stats.num_axis_check_successes = &KDTree::_num_axis_checks_successes;
  stats.num_axis_check_had_to_fail = &KDTree::_num_axis_check_had_to_fail;
  int options = 0;
  if (truly_GS->_disabled_flags & ENABLE_FCULLED_RAY_BBOX_TESTS)
    options |= BBOX_CHECK;
  if (truly_GS->_disabled_flags2 & ENABLE_3_AXIS_CHECK)
    options |= CHECK_3_AXIS;
  if (truly_GS->_disabled_flags2 & ENABLE_1_AXIS_CHECK)
    options |= CHECK_1_AXIS;
  
  if (_straddlers->Size() > 0)
    {
      stats.num_intersect_calls = &_frustum_straddler_intersect_calls;
      stats.num_bbox_successes = &_frustum_straddler_bbox_success;
      stats.num_intersect_successes = &_frustum_straddler_intersect_success;
      
      IntersectObjList (*_CS, x, y, ray, _straddlers, hit, pc, options, drawing_flags, stats);
    }
  
  if (_incident->Size() > 0)
    {
      stats.num_intersect_calls = &_frustum_incident_intersect_calls;
      stats.num_bbox_successes = &_frustum_incident_bbox_success;
      stats.num_intersect_successes = &_frustum_incident_intersect_success;
      IntersectObjList (*_CS, x, y, ray, _incident, hit, pc, options, drawing_flags, stats);
    }
#endif
  //  cerr << "bottom of WR::raycast" << endl;
}


//assumes straddlers & incident are empty
//takes which rw is doing this; we need to pass this down to the LP code
void WorkRec::EatCurCell (int rw)
{
  assert (_cur_cell);

  int center_x = (_frustum.X_left() + _frustum.X_right()) >> 1;
  int center_y = (_frustum.Y_bottom() + _frustum.Y_top()) >> 1;

  Vec4 dir;

  _cur_cell->Update (_CS);

  assert (!_got_total_hit);

  assert (_straddlers->Size() == 0);
  assert (_incident->Size() == 0);

  //did we own the lists in a previous cell?
  if (_own_list)
    {
      assert (_incident == &_real_inc_list);
      assert (_straddlers == &_real_str_list);
      _incident->Clear();
      _straddlers->Clear();
    }

  _incident = &_real_inc_list;
  _straddlers = &_real_str_list;

  WorkRec *parent = this;
  while (parent->_parent) parent = parent->_parent;

  int neednearclip = 0;
  if ((parent->_cur_cell == _cur_cell) && (truly_GS->_disabled_flags & ENABLE_LP_ROOT_FRUSTUM)) neednearclip = 1;

  int wemustfree = 0;
  if (_cur_cell->FrustumQuery (rw, _frustum, wemustfree, _incident, _straddlers, neednearclip))
    {
      assert (_incident == &_real_inc_list);
      assert (_straddlers == &_real_str_list);
      _cur_cell->UncachedFrustumQuery (rw, _frustum, _incident, _straddlers, neednearclip);
      _own_list = 1;
    }
  else //it was cached; out of our hands!
    {
      assert (_incident != &_real_inc_list);
      assert (_straddlers != &_real_str_list);
      assert (!wemustfree); //we shouldn't be responsible for this list. only individual rays that call FrustumQuery should be responsible for clearing their lists.
      _own_list = 0;
    }

  _have_curcell_objs = 1;

  //  cerr << "Ate cell, found " << _incident->Size() << " incident and " << _straddlers->Size() << " straddling objects." << endl;
  //  return _incident->Size() + _straddlers->Size();

  int size = _cur_cell->_objs->Size();
  
  WRLOG (WR_EatCurCell, new WR_EatCurCell_Entry (this, _cur_cell, size, _incident->Size() + _straddlers->Size()));
  //XXX this is incorrect because we're counting quick rejects as full intersects.
  //  _CS->_num_intersections_avoided += NumInsideRays() * (size - NumObjects());
}


//possibly my finest hour in macros, right here.
//indir provides indirection between the array indices
#define DISTRIBUTE_KID_STUFF(grid,indir,parent,ourfive) \
  grid [BL]indir[BL] = parent[BL]; \
  grid [BL]indir[BR] = ourfive[BOTTOM]; \
  grid [BL]indir[TL] = ourfive[LEFT]; \
  grid [BL]indir[TR] = ourfive[CENTER]; \
\
  grid [BR]indir[BR] = parent[BR]; \
  grid [BR]indir[BL] = ourfive[BOTTOM]; \
  grid [BR]indir[TL] = ourfive[CENTER]; \
  grid [BR]indir[TR] = ourfive[RIGHT]; \
\
  grid [TL]indir[TL] = parent[TL]; \
  grid [TL]indir[TR] = ourfive[TOP]; \
  grid [TL]indir[BL] = ourfive[LEFT]; \
  grid [TL]indir[BR] = ourfive[CENTER]; \
\
  grid [TR]indir[TR] = parent[TR]; \
  grid [TR]indir[TL] = ourfive[TOP]; \
  grid [TR]indir[BL] = ourfive[CENTER]; \
  grid [TR]indir[BR] = ourfive[RIGHT] 



  //returns # of rays shaded
int WorkRec::ShadeSmart (void)
{
  int numrayscast = 0;
  int center_x = (_frustum.X_left() + _frustum.X_right()) >> 1;
  int center_y = (_frustum.Y_bottom() + _frustum.Y_top()) >> 1;

  //only do the left & bottom if they're on the edge
  int leftx = _frustum.X_left();
  if (leftx == 0)
    {
      Render_Worker::Shade (leftx, center_y, *_CS, 1);
      numrayscast++;
    }
  else
    _CS->_samplebuffer->Confirm (leftx,center_y, Render_Worker::_frame_id, Render_Worker::_sub_frame_id);
  
  //y's go up from the bottom. 
  int lowy = _frustum.Y_bottom();
  if (lowy == 0)
    {
      Render_Worker::Shade (center_x, lowy, *_CS, 1);
      numrayscast++;
    }
  else
    _CS->_samplebuffer->Confirm (center_x, lowy, Render_Worker::_frame_id, Render_Worker::_sub_frame_id);
  
  //we are responsible for actually doing the right & top pix
  int totalsize = _CS->_samplebuffer->Size();
  
  int confirm = 0;
  int highy = _frustum.Y_top();
  if (highy == (totalsize-1))
    confirm = 1;
  Render_Worker::Shade (center_x, highy, *_CS, confirm);
  numrayscast++;
  
  confirm = 0;
  int rightx = _frustum.X_right();
  if (rightx == (totalsize - 1))
    confirm = 1;
  Render_Worker::Shade (rightx, center_y, *_CS, confirm);
  numrayscast++;
  
  Render_Worker::Shade(center_x, center_y, *_CS, 1);
  numrayscast++;

  if (!_parent) //if we're the root, we gotta shade the 4 corners too.
    {
      Render_Worker::Shade(leftx, lowy, *_CS, 1);
      Render_Worker::Shade(leftx, highy, *_CS, 1);
      Render_Worker::Shade(rightx, lowy, *_CS, 1);
      Render_Worker::Shade(rightx, highy, *_CS, 1);
      numrayscast+=4;
    }

  return numrayscast;
}


int WorkRec::NumInsideRays()
{
  int area = (_frustum.XSize() * _frustum.YSize() ) - 4;
  if ( _frustum.X_right() < (truly_GS->_x_winsize - 1 ))
    area -= ( _frustum.YSize() - 2 );
  if ( _frustum.Y_top() < (truly_GS->_y_winsize - 1 ))
    area -= ( _frustum.XSize() - 2 );
  //  cerr << "NumInsideRays for side " << _frustum.XSize() << " is " << area << endl;
  return area;
}

//rwnum: # of render worker doing this
//same: whether the corner rays go into the same k-d cell.
void WorkRec::ShootRaysAndSubdivide (int rwnum, int same, WorkQueue *queue, int &numrayscast)
{
  //  cerr << "sr start" << endl;

  int center_x = (_frustum.X_left() + _frustum.X_right()) >> 1;
  int center_y = (_frustum.Y_bottom() + _frustum.Y_top()) >> 1;
  Vec4 origin = _corner_rays[0].R();

  Vec4 coords[5];
  coords[LEFT].Set (_frustum.X_left(), center_y, 0);
  coords[RIGHT].Set (_frustum.X_right(), center_y, 0);
  coords[TOP].Set (center_x, _frustum.Y_top(), 0);
  coords[BOTTOM].Set (center_x, _frustum.Y_bottom(), 0);
  coords[CENTER].Set (center_x, center_y, 0);

  Ray fiverays[5];
  MakeRays (coords, origin, fiverays);
  //  cerr << "computed rays" << endl;

  static KDTree *kdtree = (KDTree *)(truly_GS->_scene.getObjs());

  _KDTreeNode *destcells[5];
  int faces[5], dirs[5];
  WRLOG (WR_FindNextCells_Start, new WR_FindNextCells_Start_Entry (this));
  CalcCells (fiverays, same, destcells, faces, dirs);
  WRLOG (WR_FindNextCells_End, new WR_FindNextCells_End_Entry (this));
  //  cerr << "got cells" << endl;

  numrayscast = 0;

  int doshoot[5]; //if this is FALSE, we just confirm
  int doconfirm[5]; //if doshoot[i] is true, we pass doconfirm[i] in as the confirm param to DoOneRayFC

  //only do the left & bottom if they're on the edge
  doconfirm[LEFT] = 1;
  if (coords[LEFT].x() == 0)
    {
      doshoot[LEFT] = 1;
    }
  else
    {
      doshoot[LEFT] = 0;
    }
  
  doconfirm[BOTTOM] = 1;
  if (coords[BOTTOM].y() == 0)
    {
      doshoot[BOTTOM] = 1;
    }
  else
    {
      doshoot[BOTTOM] = 0;
    }
  
  //we are responsible for actually doing the right & top pix
  int totalsize = _CS->_samplebuffer->Size();

  doshoot[TOP] = 1;
  if (coords[TOP].y() == (totalsize-1))
    doconfirm[TOP] = 1;
  else
    doconfirm[TOP] = 0;
  
  doshoot[RIGHT] = 1;
  if (coords[RIGHT].x() == (totalsize - 1))
    doconfirm[RIGHT] = 1;
  else
    doconfirm[RIGHT] = 0;

  //and we're responsible for the center pixel
  doshoot[CENTER] = 1;
  doconfirm[CENTER] = 1;

  //passing in:
  //x,y coords
  //world-space rays
  //what cell those rays go to (After _cur_cell)
  //whether to check if the pixel's already done
  //whether to only check this cell or whether to go "all the way" through the k-d tree alone
  //whether to shoot the ray or not
  //whether to confirm the ray or not
  //passing out:
  //the number of rays actually cast
  numrayscast = 0;
  if (HYBRID_ON) {
    CastRays (rwnum, 5, coords, fiverays, destcells, 0, 1, doshoot, doconfirm, numrayscast);
  } else if (LAST_SUBD_LEVEL (_frustum.XSize(), _subd_count)) {
    //if pure FC is on, we only do intersections in the 3x3 case
    CastRays (rwnum, 5, coords, fiverays, destcells, 0, 1, doshoot, doconfirm, numrayscast);

    Vec4 cornerCoords[4];
    cornerCoords[TL].Set (coords[LEFT].x(), coords[TOP].y(),0);
    cornerCoords[TR].Set (coords[RIGHT].x(), coords[TOP].y(), 0);
    cornerCoords[BL].Set (coords[LEFT].x(), coords[BOTTOM].y(),0);
    cornerCoords[BR].Set (coords[RIGHT].x(), coords[BOTTOM].y(), 0);
    
    //this is MT safe, even though it's checking the raycache for
    //a previous hit, b/c the only frusta that could be setting the raycache
    //would be the parents, and this frusta isn't scheduled until the 
    //parents are done.
    
    int cornerdoshoot[4];
    int cornerdoconfirm[4];
    
    for (int i= 0; i < 4; i++)
      cornerdoconfirm[i] = 0;
    
    //we're responsible for our top left corner pixel, if it
    //hasn't already hit something
    cornerdoshoot[TL] = 1;
    cornerdoconfirm[TL] = 1;
    
    //if we're on the right edge, we're responsible for our top right too
    if (coords[RIGHT].x() == (totalsize - 1)) 
      {
	cornerdoshoot[TR] = 1;
	cornerdoconfirm[TR] = 1;
      }
    else
      {
	cornerdoshoot[TR] = 0;
      }
    
    //if we're on the bottom edge, we're responsible for bottom right
    if (coords[BOTTOM].y() == 0)
      {
	cornerdoshoot[BR] = 1;
	cornerdoconfirm[BR] = 1;
      }
    else
      cornerdoshoot[BR] = 0;

    //finally, if we're on the bottom left, we're responsible for the bottom
    //left corner
    if (coords[LEFT].x() == 0 && coords[BOTTOM].y() == 0)
      {
	cornerdoshoot[BL] = 1;
	cornerdoconfirm[BL] = 1;
      }
    else
      cornerdoshoot[BL] = 0;
    
      //that covers all the corners uniquely for any level of subdivision!
    CastRays (rwnum, 4, cornerCoords, _corner_rays, _cell_corner_goesto, 0, 1,  cornerdoshoot, cornerdoconfirm, numrayscast);
  }
  
  //don't subdivide too small!
  if (LAST_SUBD_LEVEL (_frustum.XSize(), _subd_count))
    {
      //      cerr << "rejecting subdivide for frustum of size " << _frustum.XSize() << endl;
      return;
    }

  //  cerr << "starting subdivide" << endl;

  //distribute our corner & center rays to corners[kid][corner]
  Ray *corners[4][4];

  DISTRIBUTE_KID_STUFF (corners,, &_corner_rays, &fiverays);

  //XXX if we do one actual alloc per 4 kids, we've got to do
  //one actual delete[] per 4 kids; aiee!
  //  char *mem = new char [sizeof (WorkRec) * 4];

  for (int i = 0; i < 4; i++)
    {
      assert (_kids[i]);

#ifndef NDEBUG
      //for debugging assistance, I can select a frustum via the debug window
      //and then breakpoint down here to watch it be created.
      if ((_kids[i]->_f_num == UI_Thread::_CB_Object->_which_frustum) && (rwnum == UI_Thread::_CB_Object->_which_rw))
	{
	  int ww = 1;
	}
#endif

      _kids[i]->Init (_CS, (const Ray **)corners[i], _cur_cell);

      //      _kids[i] = new (mem + (i * sizeof (WorkRec))) WorkRec(_frustum.GetCamera(), 0, _CS, this, (const Ray **)corners[i]);
      //      _kids[i] = new WorkRec(_frustum.GetCamera(), 0, _CS, this, (const Ray **)corners[i]);
      if (!_kids[i])
	{
	  cerr << "ran out of memory making workrecs, bye!" << endl;
	}
      

      if (_own_list) //if we own our list, we'll propagate it down
	{
	_kids[i]->_have_curcell_objs = 1; 
	_kids[i]->_own_list = 1;
	assert (_kids[i]->_incident == &_kids[i]->_real_inc_list);
	assert (_kids[i]->_straddlers == &_kids[i]->_real_str_list);

	}
      else
	{
	  //otherwise, the kids will have to get their own lists
	  //from the cache
	  _kids[i]->_own_list = 0;
	  if (_cur_cell)
	    _kids[i]->_have_curcell_objs = 0; 
	  else
	    _kids[i]->_have_curcell_objs = 1; 
	}
    }

  //if we own our list, we have to propagate the objects down
  if (_own_list)
    {
      //looking from eye point,
      //Subdivide gives us a grid like this: _kids[2] _kids[3]
      //                                     _kids[0] _kids[1]
      //y is 0 at the bottom, ywinsize - 1 at the top of the screen window
      //  _frustum.Subdivide(_kids[0]->_frustum, _kids[1]->_frustum,
      //                     _kids[2]->_frustum, _kids[3]->_frustum);
      
      //  cerr << "partitioning kids..." << endl;
      //if we know what the kids are going to hit, no need to do more plane 
      //tests and such!
      if (!_got_total_hit)
	{
	  //cull out stuff from the parent's incident list
	  if (_incident->Size())
	    {
	      assert (_cur_cell);
	      if (truly_GS->_disabled_flags & DISABLE_LP_SUBDIV)
		_cur_cell->PartitionKids (this);
	      else
		_cur_cell->PartitionKidsLP(rwnum, this);

#ifdef CHECK_INCIDENT_SORTEDNESS
	      float prevnear = -MAXFLOAT;
	      //incident should stay sorted by tnear.
	      void *cplace;
	      _incident->Reset (cplace);
	      while (cplace)
		{
		  ObjInfo *info = _incident->Peek (cplace);
		  if (info->_tnear < prevnear)
		    {
		      cerr << "incident info->_tnear is " << info->_tnear << ", prevnear is " << prevnear << endl;
		    }
		  prevnear = info->_tnear;
		  
		  _incident->Next (cplace);
		}
#endif //CHECK_INCIDENT_SORTEDNESS
	    } //if incident objects
	} //!_got_total_hit
      
      PassDownStraddlers();
    } //if we own our lists

  //CFT this stat isn't strictly right because of quick rejects and the
  //optimization based on sorted lists in each k-dtree cell
  //  for (i = 0; i < 4; i++) {
  //    _CS->_num_intersections_avoided += _kids[i]->NumInsideRays() * (NumObjects() -_kids[i]->NumObjects());
  //    }

  //distribute cell corner info to kids
  DISTRIBUTE_KID_STUFF (_kids, ->_cell_corner_goesto, _cell_corner_goesto, destcells);
  DISTRIBUTE_KID_STUFF (_kids, ->_face_corner_goesto, _face_corner_goesto, faces);
  DISTRIBUTE_KID_STUFF (_kids, ->_dir_corner_goesto, _dir_corner_goesto, dirs);

  //in multi-threaded pure FC, we have to add workrecs on the
  //fly b/c they depend on their parents being completed.
#ifndef ONE_THREAD
  //schedule them kids
  for (i = 0; i < 4; i ++)
    {
      _kids[i]->SetOwner (queue->Size(), rwnum);
      queue->AddWorkRec (_kids[i]);
    }
#endif
 
  WRLOG (WR_FrustumSubdivided, new WR_FrustumSubdivided_Entry (this, !(_incident->Size() == 0 && _straddlers->Size() == 0)));

  return;
}


//make sure there's no case where we leave along the same face but
//in a different dir.
int WorkRec::AdjacentExitFaces()
{
  int i;
  for (i = 1; i < 4; i++)
    {
      if (_face_corner_goesto[0] == _face_corner_goesto[i])
	{
	  if (_dir_corner_goesto[0] != _dir_corner_goesto[i]) return 0;
	}
    }

  for (i = 2; i < 4; i++)
    {
      if (_face_corner_goesto[1] == _face_corner_goesto[i])
	{
	  if (_dir_corner_goesto[1] != _dir_corner_goesto[i]) return 0;
	}
    }

  if (_face_corner_goesto[2] == _face_corner_goesto[3])
    {
      if (_dir_corner_goesto[3] != _dir_corner_goesto[3]) return 0;
    }
  
  return 1;
}


//do all our corners go to the same cell?
int WorkRec::SameExits()
{
  if ( (_cell_corner_goesto[0] != _cell_corner_goesto[1]) ||
       (_cell_corner_goesto[2] != _cell_corner_goesto[3]) ||
       (_cell_corner_goesto[0] != _cell_corner_goesto[2]) )
    return 0;
  else
    return 1;
}

//returns numskipped, which is pretty much unused now but could be used
//to allow one workrec to stop subdivision and be responsible for
// all the pixels in its area - it would just return the # of kid frusta
//it would have made (down to the pixel level!) on the first subframe.

//takes a queue to add our kids onto
int WorkRec::Work (int rwnum, int &rayscast, CycleState &latestCS, WorkQueue *queue)
{
  //  cerr << "starting wr::work" << endl;
  _CS = &latestCS;

  if (_just_shade) //have we reached the second round of action yet? 
    {
      rayscast += ShadeSmart();
      return 0;
    }

#ifndef NDEBUG
  if (_parent) assert (_parent->_just_shade); //parent should be done 1st.


  //for debugging assistance, I can select a frustum via the debug window
  //and then breakpoint down here to watch it go.
  if ((_f_num == UI_Thread::_CB_Object->_which_frustum) && (rwnum == UI_Thread::_CB_Object->_which_rw))
    {
      int q = 1;
    }
#endif

  //ok...down to the nitty-gritty of frustum casting 
  static KDTree *kdtree = (KDTree *)(truly_GS->_scene.getObjs());
  
  int same;
  int empty;
  const int UNKNOWN = -1;

  same = UNKNOWN;
  empty = UNKNOWN;

  while(1)
    {
      int i;
#ifdef HEAVY_DUTY_BUT_SLOW
      //make sure our preconditions are good
      for (i = 0; i < 4; i++)
	{
	  if (_cell_corner_goesto[i])
	    assert (kdtree->IsValidCell (_cell_corner_goesto[i]));
	}
  #endif
      same = SameExits();

      //if we've got the object, leave!
      if (_got_total_hit) 
	break;

      //if we need to do plane tests, do.
      if (!_have_curcell_objs)
	{
	  assert (_cur_cell);
	  EatCurCell(rwnum);
	}

      //at this point we have a list of all the objects in our
      //frustum and a list of which cell our corner rays go to next.
      empty = Empty();

      //if we're outside the tree, we shouldn't have any objects yet
      if (_cur_cell == NULL) 
	assert (empty);
        
      //if there's stuff in our frustum, 
      //or our cells are leaving different places...
      //time to subdivide.
      if ( !empty || !same ) 
	break;

      //at this point we know that we're empty and our corners go to
      //the same k-d cell.
  
      //if that k-d cell is NULL, it means that either
      // all our interior rays are actually leaving OR
      // the corner rays are leaving but there's more k-d tree in the middle,
      // which happens when:
      //   we were in a cell and they're leaving along opposite faces
      //   we were outside the tree and the k-d tree bbox is incident in the frustum
      if (_cell_corner_goesto[0] == NULL)
	{
	  if (_cur_cell && !AdjacentExitFaces()) break;

	  static KDTree *kdtree = (KDTree *)(truly_GS->_scene.getObjs());
	  if (!_cur_cell && (kdtree->IsInFrustum (_CS, rwnum, _frustum)))
	    break;
	  
	  WRLOG (WR_FloodNo, new WR_FloodNo_Entry (this));
	  _got_total_hit = 1;
	  totalhit.obj = NULL;
	  totalhit.hitcell = NULL;
	  totalhit.t = MAXFLOAT;
	  break;
	}
      else
	//if we're empty and all the corners leave the same place,
	//we can proceed to the next cell.
	{
	  _num_kdcells_walked++;

	  WRLOG (WR_FrustumWalked, new WR_FrustumWalked_Entry (this, _cur_cell, _cell_corner_goesto[0]));
	  
	  _cur_cell = _cell_corner_goesto[0];
#ifndef NDEBUG
	  //keep track of stuff!
	  //	  _cur_cell->_num_times_touched.Add (_CS->_frame_id, _frustum.XSize());
#endif

	  _have_curcell_objs = 0;
	  same = UNKNOWN;
	  empty = UNKNOWN;
	  
	  _CS->_num_traversals_avoided += NumInsideRays();
	  
	  WRLOG (WR_FindNextCells_Start, new WR_FindNextCells_Start_Entry (this));
	  for (i = 0; i < 4; i++)
	    {
	      assert (_cell_corner_goesto[i]);
	      _cell_corner_goesto[i] = kdtree->Traverse (_corner_rays[i], _face_corner_goesto[i], _dir_corner_goesto[i], _cell_corner_goesto[i]);
	      _num_kdcells_traversed++;
	    }
	  WRLOG (WR_FindNextCells_End, new WR_FindNextCells_End_Entry (this));
	} //if cell corner goes to == NULL
    } //while 1

  //if all our corners hit the same object and hit it in this
  //cell and all other objects are completely behind this one,
  //then by convexity we know all the
  //interior points hit that object. 
  if (_got_total_hit)
    {
      if (totalhit.obj)
	assert (totalhit.t == -1);
    }
  else
    {
      //try to flood yes
      if (!empty)
	{
	  int left = _frustum.X_left();
	  int right = _frustum.X_right();
	  int top = _frustum.Y_top();
	  int bottom = _frustum.Y_bottom();
	  int totalsize = _CS->_samplebuffer->Size();

	  RayCache *ul = GET_RAY_INFO_PTR (left, top);
	  RayCache *ur = GET_RAY_INFO_PTR (right, top);
	  RayCache *ll = GET_RAY_INFO_PTR (left, bottom);
	  RayCache *lr = GET_RAY_INFO_PTR (right, bottom);

	  if ( (ul->frameID == ur->frameID) &&
	       (ll->frameID == lr->frameID) &&
	       (ul->frameID == Render_Worker::_frame_id) )
	    {
	      _KDTreeNode *cellhit = ul->objhit.hitcell;
	      RayCastable *magic = ul->objhit.obj;

	      if ( cellhit &&
		   ((cellhit == ur->objhit.hitcell) &&
		    (cellhit == lr->objhit.hitcell) &&
		    (cellhit == ll->objhit.hitcell) &&
		    (cellhit == _cur_cell))
		   &&
		   ((magic) &&
		    (magic->IsConvex()) &&
		    (magic == ur->objhit.obj) &&
		    (magic == lr->objhit.obj) &&
		    (magic == ll->objhit.obj))
		   )
		{
		  //if that object is in the incident list, promote it to a straddler
		  const void *place;
		  _incident->Reset (place);
		  ObjInfo *check;
		  while (place)
		    {
		      check =_incident->Peek (place);
		      if (magic == check->_obj)
			{
			  _straddlers->PlaceInSortedList(check, _KDTreeNode::tnearsort);
			  _incident->Remove (place);
			  break;
			}
		      _incident->Next (place);
		    }

		  //if that object is the first object in the straddling list and
		  //its far t < the near t of the second straddler
		  //and the first incident, we're golden!

		  //get the first & second straddler and the first incident obj.
		  _straddlers->Reset (place);
		  ObjInfo *s1, *s2, *i1;
		  assert (place);

		  s1 = _straddlers->Peek (place);
		  _straddlers->Next (place);
		  if (place)
		    s2 = _straddlers->Peek (place);
		  else
		    s2 = NULL;

		  _incident->Reset (place);
		  if (place)
		    {
		      i1 = _incident->Peek (place);
		    }
		  else
		    i1 = NULL;

		  int allgood = 0;
		  //we've got to be first straddler
		  if (s1->_obj == magic)
		    {
		      //try the easy case
		      if (!s2 && !i1) allgood = 1;
		      else if (!(truly_GS->_disabled_flags & DISABLE_VIEWVEC_T))
			{
			  //take the t's of the four corner intersections and 
			  //project them onto
			  //the view ray.set tfar to be the max one.
			  float tfar;
			  tfar = MAXFLOAT;
			  float t1 = _CS->_plane_cache->ComputeViewVecT (left, top, ul->objhit.t);
			  if (t1 < tfar) tfar = t1;
			  t1 = _CS->_plane_cache->ComputeViewVecT (right, top, ur->objhit.t);
			  
			  if (t1 < tfar) tfar = t1;
			  t1 = _CS->_plane_cache->ComputeViewVecT (right, bottom, lr->objhit.t);
			  
			  if (t1 < tfar) tfar = t1;
			  t1 = _CS->_plane_cache->ComputeViewVecT (left, bottom, ll->objhit.t);
			  
			  if (t1 < tfar) tfar = t1;

			  //if we're first in the straddling list and the rest are
			  //behind us, and we're convex!
			  allgood = (((!s2) || (s2->_tnear >= tfar)) && ((!i1) || (i1->_tnear >= tfar)) );
			} //if viewvec t optimization is on
		    } //if we're first in straddling list and convex

		  if (allgood && !(truly_GS->_disabled_flags & DISABLE_FLOOD_YES))
		    {
		      //		  if ( (left == 64) && (right == 128) && (top == 128) && (bottom == 64))
		      //		    cerr << "we won for (" << left << ", " << bottom << " - (" << right << ", " << top << ")" << endl;
		      //all four corners hit the same object
		      //and it's our straddler, baby. we can flood with yes's!
		      _got_total_hit = 1;
		  
		      totalhit = ur->objhit;
		      //we didn't do any work for this cell or for its kids!
		      //no traverses, no nothing!
		      totalhit.ClearWorkDone();
		      totalhit.t = -1; //clues in raycaster that we need to calc t.
		      totalhit.normalcalced = 0;
		      totalhit.texcalced = 0;
		      _CS->_num_intersections_avoided += NumInsideRays();

		      assert (totalhit.obj);
		      WRLOG (WR_FloodYes, new WR_FloodYes_Entry (this, totalhit.obj));
		    }
		  else
		    {
		      if (truly_GS->_disabled_flags & DISABLE_FRAME_CONTINUE)
			{
#if 0
			  Bounds3d bbox = magic->bbox();
			  bbox.ClipToBbox (_cur_cell->_bounds);
			  //		      bbox.ClipToFrontOfRay (_CS->_camera.R(), _CS->_camera.D());
			  cerr << "----" << endl << "hit same obj of bbox " << bbox << " in cell " << _cur_cell->_bounds << "." << endl;
			  cerr << "straddlers: ";
			  const void *p;
			  _straddlers->Reset (p);
			  while (p)
			    {
			      bbox = _straddlers->Peek(p)->bbox();
			      bbox.ClipToBbox (_cur_cell->_bounds);
			      //			  bbox.ClipToFrontOfRay (_CS->_camera.R(), _CS->_camera.D());
			      cerr << bbox;
			      _straddlers->Next (p);
			    }

			  cerr << endl << "incident: ";
		      
			  _incident->Reset (p);
			  while (p)
			    {
			      bbox = _incident->Peek(p)->bbox();
			      bbox.ClipToBbox (_cur_cell->_bounds);
			      //			  bbox.ClipToFrontOfRay (_CS->_camera.R(), _CS->_camera.D());
			      cerr << bbox;
			      _incident->Next (p);
			    }
			  cerr << endl;

			  //		cerr << "all hit same obj, straddlers " << _straddlers->Size() << ", inc: " << _incident->Size() << endl;
#endif
			}

		    } //if object is in front of the others
		} //if corners all hit the same object
	    }//if corners have the right frame id
	} //if we have objects
    } //if we didn't flood already

  assert (same != UNKNOWN);

  //time to shoot rays and subdivide!
  //Wait...I've got the *perfect* routine
  //  cerr << "sr & subdivide" << endl;
  int numcast;
  ShootRaysAndSubdivide(rwnum, same, queue, numcast);
  rayscast += numcast;
  _just_shade = 1;

  //  cerr << "workrec::work done" << endl;
  return 0;
}

int WorkRec::HasAncestor (WorkRec *parent)
{
  if (!parent)
    return 0;

  WorkRec *par = _parent;

  while (par)
    {
      if (par == parent) return 1;
      par = par->_parent;
    }
  return 0;
}


WorkRec *WorkRec::GetFloodParent (void)
{
  if (!_got_total_hit)
    return this;

  WorkRec *current = this;
  while (current->_parent && current->_parent->_got_total_hit)
    current = current->_parent;

  return current;
}


void WorkRec::MakeRays (Vec4 coords[5], const Vec4 &origin, Ray fiverays[5])
{
  for (int i = 0; i < 5; i ++)
    {
    fiverays[i].SetR(origin);
    fiverays[i].SetD (_CS->_plane_cache->ComputeEyeRayDirection (coords[i].x(), coords[i].y()));
    fiverays[i].SetID (coords[i].y() * truly_GS->_x_winsize + coords[i].x());
    }
}

void WorkRec::CalcCells (Ray fiverays[5], int same, _KDTreeNode *cells[5], int faces[5], int dirs[5])
{
  //if we've already got a total hit, we don't care where we're going, 
  //so we can save 5 traversals. 
  //or, if all the corners hit the same cell (and they're not all missing),
  //the interior points are going to to the same cell. (if they all miss,
  //maybe the entire kdtree is hiding in the interior of the frustum,
  //so we have to check.)
						  
  static KDTree *kdtree = (KDTree *)(truly_GS->_scene.getObjs());

  if (_got_total_hit)
    {
      for (int i = 0; i < 5; i++)
	{
	cells[i] = NULL;
	faces[i] = dirs[i] = -1;
	}
    }
  //if they all miss the k-dtree, we have no guarantee about interior rays.
  //XXX unless they all leave on the same cell or if the frustum doesn't
  //include the k-d tree bbox. 
  else if (same && (_cell_corner_goesto[0] != NULL))
    {
      for (int i = 0; i < 5; i++)
	{
	  cells[i] = _cell_corner_goesto[0];
	  faces[i] = _face_corner_goesto[0];
	  dirs[i] = _dir_corner_goesto[0];
	  //#define DEBUG_THIS_OPTIMIZATION
#ifdef DEBUG_THIS_OPTIMIZATION
	  int face, dir;
	  assert (cells[i] == kdtree->Traverse (fiverays[i], face, dir, _cur_cell));
	  assert (faces[i] == face);
	  assert (dirs[i] == dir);
#endif
	}
    }
  else
    {
#define COPY_CELL(src,dest) { \
	cells[dest] = _cell_corner_goesto[src]; \
	faces[dest] = _face_corner_goesto[src]; \
        dirs[dest] = _dir_corner_goesto[src]; }
#define CALC_CELL(src) \
	cells[src] = kdtree->Traverse (fiverays[src], faces[src], dirs[src], _cur_cell)

      //if two corners go to the same non-NULL cell, so should their center
      if ((_cell_corner_goesto [BL] == _cell_corner_goesto[TL]) && _cell_corner_goesto [TL]) 
	{
	  COPY_CELL (BL, LEFT);
	}
      else
	{
	  CALC_CELL (LEFT);
	_num_kdcells_traversed++;
	}

      if ((_cell_corner_goesto [BR] == _cell_corner_goesto[TR]) && _cell_corner_goesto [TR]) 
	{
	  COPY_CELL (BR, RIGHT);
	}
      else
	{
	  CALC_CELL (RIGHT);
	  _num_kdcells_traversed++;
	}

      if ((_cell_corner_goesto [TL] == _cell_corner_goesto[TR]) && _cell_corner_goesto [TL]) 
	{
	  COPY_CELL (TL, TOP);
	}
      else
	{
	  CALC_CELL (TOP);
	  _num_kdcells_traversed++;
	}

      if ((_cell_corner_goesto [BR] == _cell_corner_goesto[BL]) && _cell_corner_goesto [BR]) 
	{
	  COPY_CELL (BR, BOTTOM);
	}
      else
	{
	  CALC_CELL (BOTTOM);
	  _num_kdcells_traversed++;
	}

      if ((cells[LEFT] == cells[RIGHT]) && cells[LEFT])
	{
	  cells[CENTER] = cells[LEFT];
	  faces[CENTER] = faces[LEFT];
	  dirs[CENTER] = dirs[LEFT];
	}
      else
	{
	  CALC_CELL (CENTER);
	  _num_kdcells_traversed++;
	}

#ifdef DEBUG_THIS_OPTIMIZATION
      for (int i = 0; i < 5; i++)
	{
	  int face, dir;
	  if (cells[i] != kdtree->Traverse (fiverays[i], face, dir, _cur_cell))
	    cerr << "BAD CELL TRAVERSE!" << endl;
	  if ((faces[i] != face) || (dirs[i] != dir))
	    cerr << "BAD FACE/DIR TRAVERSE!" << endl;
	}
#endif

    }

}

//input:
//the render-worker num
//the # of rays to shoot
//arrays:
//x,y coords of the rays
//the actual world-space rays
//the cells that each ray goes into
//whether to check if the ray's already been fully shot
//whether to shoot the ray all the way, if we're going to shoot it
//whether to shoot the ray 
//whether to confirm the ray

//output: num rays actually cast
void WorkRec::CastRays (int rwnum, int numrays, Vec4 *coords, Ray *fiverays, _KDTreeNode **destcells, int checkprevint, int alltheway, int *doshoot, int *doconfirm, int &numrayscast)
{
  RayCache *info;
  for (int i = 0; i < numrays; i++)
    {
      if (checkprevint)
	{
	  info = GET_RAY_INFO_PTR ((int)coords[i].x(), (int)coords[i].y());
	  if (info->frameID == Render_Worker::_frame_id)
	    continue;
	}

      if (doshoot[i])
	{
	  RWLOG (RW_Work_CastRay, new RW_Work_CastRay_Entry (this, fiverays[i], coords[i].x(), coords[i].y(), 1));
	  Render_Worker::DoOneRayFC (rwnum, this, fiverays[i], coords[i].x(), coords[i].y(), *_CS, doconfirm[i], alltheway,  destcells[i]);
	  numrayscast++;
	}
      else if (doconfirm[i])
	{
	  RWLOG (RW_Work_ConfirmRay, new RW_Work_ConfirmRay_Entry (this, coords[i].x(), coords[i].y()));
	_CS->_samplebuffer->Confirm (coords[i].x(), coords[i].y(), Render_Worker::_frame_id, Render_Worker::_sub_frame_id);
	}
    }

}

void WorkRec::PassDownStraddlers (void)
{
  int ssize = _straddlers->Size();
  ObjInfo *info;

  const void *place;
  _straddlers->Reset (place);

#if !defined (NDEBUG) || defined (CHECK_KID_STRADDLER_SORTEDNESS)
  float prevnear = -MAXFLOAT;
#endif

#ifdef CHECK_KID_STRADDLER_SORTEDNESS
  //straddlers should stay sorted by tnear.
  prevnear = -MAXFLOAT;
  void *cplace;
  _kids[0]->_straddlers->Reset (cplace);
  while (cplace)
    {
      ObjInfo *info = _kids[0]->_straddlers->Peek (cplace);
      if (info->_tnear < prevnear)
	{
	  cerr << "b4 kid straddler info->_tnear is " << info->_tnear << ", prevnear is " << prevnear << endl;
	}
      prevnear = info->_tnear;

      _kids[0]->_straddlers->Next (cplace);
    }
#endif

  #ifndef NDEBUG
  prevnear = -MAXFLOAT;
  #endif
  for (int i = 0; i < ssize; i++)
    {
      assert (place);
      info = _straddlers->Peek (place);
      _straddlers->Next (place);
#ifndef NDEBUG     
      //they should already be sorted by tnear.
      if (info->_tnear < prevnear) 
	{
	  cerr << "straddler info->_tnear is " << info->_tnear << ", prevnear is " << prevnear << endl;
	}
      prevnear = info->_tnear;
#endif

      //gotta place in sorted list because the kid may already have straddlers
      //in it and we need to preserve sorting order.
      _kids[0]->_straddlers->PlaceInSortedList (info, _KDTreeNode::tnearsort);
      _kids[1]->_straddlers->PlaceInSortedList (info, _KDTreeNode::tnearsort);
      _kids[2]->_straddlers->PlaceInSortedList (info, _KDTreeNode::tnearsort);
      _kids[3]->_straddlers->PlaceInSortedList (info, _KDTreeNode::tnearsort);
    }

  assert (!place);
}