#include "raytrace.h"

/*

RTRay 010
---------

. Hacked raytracer in place
. Made raytrace class hold scene, keeping render code static
. Cut out texture & envmap support ( tex variable )

NEXT STEP

. Make basic non recursive raytracer

  Concentrate on:

    Optimising subdivision
    Pre-calcuation

Quote:
  Think of all you've done, and double it! 200209091949

*/


//---- OLD RAYTRACE CODE------------------------------------------------------//




//---- Raytrace Data Types ---------------------------------------------------//

typedef struct
{
  float ax, ay, az;

  float x, y, z;
}
RT_POINT;


typedef struct __RT_SPHERE
{
  float x1, y1, x2, y2;  //  Screen-space bounding box

  float ax, ay, az;
  
  float x, y, z;
  float rad;
  int col;

  float a, b, c, d;
  float r2;

  int stamp, shadow_stamp, refl_stamp, refl_shadow_stamp;

  struct __RT_SPHERE *shadow_list;
}
RT_SPHERE;



typedef struct
{
  int num;
  RT_SPHERE sphere[4];
}
RT_SUSPECTS;



typedef struct
{
  RT_SPHERE *sphere;
  RT_SPHERE *shadow_sphere;

  RT_SPHERE *refl_sphere;
  RT_SPHERE *refl_shadow_sphere;

  float t;
  float x, y, z;
  float nx, ny, nz;
  float reflx, refly, reflz;

  int col;

  int frame;
}
RT_PIXEL;



typedef struct
{
  float ox, oy, oz;
  float dx, dy, dz;

  float dx2, dy2, dz2;

	float len2, leno22, len42;
}
RT_RAY;




//---- FUNCTIONS


void rt_startup(int *buffer, int width, int height);
void rt_shutdown();

void rt_addSphere(float x, float y, float z, float rad, int col);

void rt_render(float rx, float ry);






//---- DATA ------------------------------------------------------------------//

//---- Render buffer

int *buf;
int w, h;

float bx1, by1, bx2, by2;
float dx, dy, dx2, dy2, dx4, dy4, dx8, dy8;



//---- Scene

RT_SPHERE *sphere;
int numspheres = 0;
RT_SPHERE *rt_sphere_null;

float light_x = 1.0, light_y = 5.0, light_z = 2.0;



//---- Render data

int sw, sh;

RT_PIXEL *spixel;

RT_SPHERE *shadow_list = NULL;

int stamp = 0;
int frame = 0;





//---- Debug data

int shadow_calc_count = 0;
int shadow_calc_pixels = 0;



//---- FUNCTION PROTOS -------------------------------------------------------//

void rt_pix_sphere( RT_RAY *ray, RT_SPHERE *sphere, RT_PIXEL *pix );
RT_SPHERE *rt_shadow( RT_PIXEL *pix );



//---- SETUP FUNCTIONS -------------------------------------------------------//

//---- rt_startup

void rt_startup(int *buffer, int width, int height)
{
  int i, j;

  //- Render buffer

  buf = buffer;
  w = width;
  h = height;

  bx1 = -1.0f*w/h;
  bx2 =  1.0f*w/h;
  dx = 2.0f/h;
  dx2 = dx * 2.0f;
  dx4 = dx * 4.0f;
  dx8 = dx * 8.0f;

  by1 =  1.0f;
  by2 = -1.0f;
  dy = -2.0f/h;
  dy2 = dy * 2.0f;
  dy4 = dy * 4.0f;
  dy8 = dy * 8.0f;

  //- Allocate scene

  sphere = new RT_SPHERE[128];

  //- Allocate render data

  sw = ((w & -2) >> 1) + 1;
  sh = ((h & -2) >> 1) + 1;

  spixel = new RT_PIXEL[sw*sh];

  for(i=0; i<sw*sh; i++) spixel[i].frame = 0;

  rt_sphere_null = new RT_SPHERE;
}



//---- rt_shutdown

void rt_shutdown()
{
  delete[] sphere;

  delete[] spixel;
}


//---- rt_clearScene

void rt_clearScene()
{
  numspheres = 0;
}

//---- rt_tempSphere

void rt_tempSphere(float x, float y, float z, float rad, int col)
{
  sphere[numspheres].ax = x;
  sphere[numspheres].ay = y;
  sphere[numspheres].az = z;
  
  sphere[numspheres].x = x;
  sphere[numspheres].y = y;
  sphere[numspheres].z = z;

  sphere[numspheres].rad = rad;
  sphere[numspheres].col = col;

  sphere[numspheres].shadow_list = shadow_list;
  shadow_list = &sphere[numspheres];

  numspheres ++;
}

//---- rt_addSphere

void rt_addSphere(float x, float y, float z, float rad, int col)
{
  sphere[numspheres].ax = x;
  sphere[numspheres].ay = y;
  sphere[numspheres].az = z;
  
  sphere[numspheres].x = x;
  sphere[numspheres].y = y;
  sphere[numspheres].z = z;

  sphere[numspheres].rad = rad;
  sphere[numspheres].col = col;

  sphere[numspheres].shadow_list = shadow_list;
  shadow_list = &sphere[numspheres];

  numspheres ++;

/*
  if(numspheres % 3 >= 1) rt_tempSphere(x+rad*1.4, y, z, rad*0.5, col);
  if(numspheres % 4 == 2) rt_tempSphere(x-rad*1.4, y, z, rad*0.5, col);
  if(numspheres % 5 >= 3) rt_tempSphere(x, y+rad*1.4, z, rad*0.5, col);
  if(numspheres % 6 == 3) rt_tempSphere(x, y-rad*1.4, z, rad*0.5, col);
  if(numspheres % 3 >= 1) rt_tempSphere(x, y, z+rad*1.4, rad*0.5, col);
  if(numspheres % 2 == 1) rt_tempSphere(x, y, z-rad*1.4, rad*0.5, col);
*/


}




//---- RAY PRECALC FUNCTIONS -------------------------------------------------//

inline void rt_ray_first_precalc(RT_RAY *ray)
{
  ray->dx2 = ray->dx*ray->dx;
  ray->dy2 = ray->dy*ray->dy;
  ray->dz2 = 1.0f;
	ray->len2 = ray->dx2 + ray->dy2 + 1.0f;
	ray->leno22 = 0.5f / ray->len2;
	ray->len42 = 4.0f * ray->len2;
}



inline void rt_ray_precalc(RT_RAY *ray)
{
  ray->dx2 = ray->dx*ray->dx;
  ray->dy2 = ray->dy*ray->dy;
  ray->dz2 = ray->dz*ray->dz;
	ray->len2 = ray->dx2 + ray->dy2 + ray->dz2;
	ray->leno22 = 0.5f / ray->len2;
	ray->len42 = 4.0f * ray->len2;
}



//---- FIRST HIT RAY FUNCTIONS -----------------------------------------------//



//---- rt_intersect_first_sphere

float rt_intersect_first_sphere(RT_RAY *ray, RT_SPHERE *sphere, RT_PIXEL *pix)
{
  float b = -2.0f*(ray->dx*sphere->x + ray->dy*sphere->y + sphere->z);

  sphere->d = b*b - ray->len42*sphere->c;

  if(sphere->d > 0)
  {
    sphere->d = (float)sqrtf(sphere->d);

    return sphere->d = (-b - sphere->d) * ray->leno22;
  }

  return -1;
}



//---- rt_intersect_first

void rt_intersect_first(RT_RAY *ray, RT_PIXEL *pix)
{
  int i;

  //- Check if there is only one sphere available

  int foundi = -1;
  int count = 0;

  for(i=0; i<numspheres; i++) if(sphere[i].stamp >= stamp) { foundi = i; count++; }

  if(count == 0 && rt_sphere_null->stamp >= stamp)
  {
    foundi = -1;
  }
  else if(count == 1 && rt_sphere_null->stamp < stamp)
  {
  }
  else
  {
    //- Precalculate ray values

    rt_ray_first_precalc(ray);

    //- Find which sphere this ray intersects

    foundi = -1;

    float dd, d = 9999999;

    for(i=0; i<numspheres; i++)
    {
      if(sphere[i].stamp >= stamp && ray->dx > sphere[i].x1 && ray->dx < sphere[i].x2 && ray->dy > sphere[i].y1 && ray->dy < sphere[i].y2)
      {
    	  dd = rt_intersect_first_sphere(ray, &sphere[i], pix);
        if(dd > 0.0001 && dd < d) { d = dd; foundi = i; }
      }
    }
  }

  //- If it doesn't intersect any of them then return blank pixel

  if(foundi < 0)
  {
    pix->sphere = NULL;
    pix->col = 0;
    pix->shadow_sphere = NULL;
  }

  //- If it does then get more info

  else
  {
    rt_pix_sphere(ray, &sphere[foundi], pix);

    pix->sphere = &sphere[foundi];
    pix->shadow_sphere = rt_shadow(pix);
    pix->col = pix->sphere->col;

    if(pix->shadow_sphere)
    {
      pix->col = ((pix->col >> 1) & 0x7F7F7F7F);// + ((pix->shadow_sphere->col >> 3) & 0x1F1F1F1F);
    }
  }

}



//---- GENERAL (NON-FIRST HIT) RAY FUNCTIONS ---------------------------------//



//---- rt_intersect_sphere

float rt_intersect_sphere(RT_RAY *ray, RT_SPHERE *sphere, RT_PIXEL *pix)
{
  float x = sphere->x;
  float y = sphere->y;
  float z = sphere->z;
  float r = sphere->rad;

//  float a = ray->dx*ray->dx + ray->dy*ray->dy + ray->dz*ray->dz;
  float b = 2*(ray->dx*(ray->ox-x) + ray->dy*(ray->oy-y) + ray->dz*(ray->oz-z));
  float c = (ray->ox-x)*(ray->ox-x) + (ray->oy-y)*(ray->oy-y) + (ray->oz-z)*(ray->oz-z) - r*r;
//  float d = b*b - 4*a*c;

//  float b = -2.0f*(ray->dx*(ray->ox-sphere->x) + ray->dy*(ray->oy-sphere->y) + ray->dz*(ray->oz-sphere->z));

  sphere->d = b*b - ray->len42*c;

  if(sphere->d > 0)
  {
    sphere->d = sqrtf(sphere->d);

    return sphere->d = (-b - sphere->d) * ray->leno22;
  }

  return -1;
}



//---- rt_intersect

void rt_intersect(RT_RAY *ray, RT_PIXEL *pix)
{
  int i;

  //- Check if there is only one sphere available

  int foundi;
  int count = 0;

  for(i=0; i<numspheres; i++) if(sphere[i].refl_stamp >= stamp) { foundi = i; count++; }

  if(count == 0 && rt_sphere_null->refl_stamp >= stamp)
  {
    foundi = -1;
  }
  else if(count > 1)
  {
    foundi = -1;

    //- Precalculate ray values

    rt_ray_precalc(ray);

    //- Find which sphere this ray intersects

    float dd, d = 9999999;

    for(i=0; i<numspheres; i++)
    {
      if(sphere[i].refl_stamp >= stamp)
      {
    	  dd = rt_intersect_sphere(ray, &sphere[i], pix);
        if(dd > 0.0001 && dd < d) { d = dd; foundi = i; }
      }
    }
  }

  //- If it doesn't intersect any of them then return blank pixel

  if(foundi < 0)
  {
    pix->sphere = NULL;
    pix->col = 0;
    pix->shadow_sphere = NULL;
  }

  //- If it does then get more info

  else
  {
    rt_pix_sphere(ray, &sphere[foundi], pix);

    pix->sphere = &sphere[foundi];
    pix->shadow_sphere = rt_shadow(pix);
    pix->col = pix->sphere->col;

    if(pix->shadow_sphere)
    {
      pix->col = ((pix->col >> 1) & 0x7F7F7F7F);// + ((pix->shadow_sphere->col >> 2) & 0x3F3F3F3F);
    }
  }

}



//---- SHADOW & PIXEL FUNCTIONS ----------------------------------------------//

//---- rt_shadow_sphere

bool rt_shadow_sphere(RT_RAY *ray, RT_SPHERE *sphere)
{
  float x = sphere->x;
  float y = sphere->y;
  float z = sphere->z;
//  float r = sphere->rad;

//  float a = ray->dx2 + ray->dy2 + ray->dz2;
  float b = 2.0f*(ray->dx*(ray->ox-sphere->x) + ray->dy*(ray->oy-sphere->y) + ray->dz*(ray->oz-sphere->z));
  float c = (ray->ox-x)*(ray->ox-x) + (ray->oy-y)*(ray->oy-y) + (ray->oz-z)*(ray->oz-z) - sphere->r2;
  float d = b*b - ray->len42*c;

/*
  float b = 2.0f*(ray->dx*(ray->ox-sphere->x) + ray->dy*(ray->oy-sphere->y) + ray->dz*(ray->oz-sphere->z));
  float d = b*b - ray->len42*sphere->c;
*/

  if(d > 0)
  {
  	if(b > 0) b *= b; else b *= -b;
    return d > b;
  }

  return false;
}



//---- rt_shadow

RT_SPHERE *rt_shadow(RT_PIXEL *pix)
{
  //  Calculate shadow ray

  RT_RAY shadow_ray;

  shadow_ray.dx = light_x - pix->x;
  shadow_ray.dy = light_y - pix->y;
  shadow_ray.dz = light_z - pix->z;

  //  Check object normal

  float d = pix->nx * shadow_ray.dx + pix->ny * shadow_ray.dy + pix->nz * shadow_ray.dz;
  if(d < 0) return pix->sphere;

//  return false;

  shadow_ray.ox = pix->x;
  shadow_ray.oy = pix->y;
  shadow_ray.oz = pix->z;

  shadow_ray.dx2 = shadow_ray.dx * shadow_ray.dx;
  shadow_ray.dy2 = shadow_ray.dy * shadow_ray.dy;
  shadow_ray.dz2 = shadow_ray.dz * shadow_ray.dz;

	rt_ray_precalc(&shadow_ray);
  
	//  Test against objects

  int i;

  RT_SPHERE *ls = NULL, *s = shadow_list;

  shadow_calc_pixels ++;

  //- Check if there is only one sphere available

  int foundi = -1;
  int count = 0;

  for(i=0; i<numspheres; i++) if(sphere[i].shadow_stamp >= stamp) { foundi = i; count++; }

  if(count == 0 && rt_sphere_null->shadow_stamp >= stamp)
  {
    return NULL;
  }
  else if(count == 1 && rt_sphere_null->stamp < stamp)
  {
    return &sphere[foundi];
  }
  else
  {
    for(i=0; i<numspheres; i++)
    {
      if(s != pix->sphere)
      {
        shadow_calc_count ++;

  	    if( s->shadow_stamp >= stamp && rt_shadow_sphere(&shadow_ray, s) )
        {
	        if(ls)
          {
            ls->shadow_list = s->shadow_list;
	          s->shadow_list = shadow_list;
	          shadow_list = s;
          }
  	      return s;
        }
      }

  	  ls = s;
      s = s->shadow_list;
    }
  }

  return NULL;
}



//---- rt_pix_sphere

void rt_pix_sphere(RT_RAY *ray, RT_SPHERE *sphere, RT_PIXEL *pix)
{
  if(sphere->d > 0)
  {
    pix->t = sphere->d;

    pix->x = ray->ox + pix->t*ray->dx;
    pix->y = ray->oy + pix->t*ray->dy;
    pix->z = ray->oz + pix->t*ray->dz;

    float a = 1.0f/sphere->rad;
    pix->nx = a*(pix->x - sphere->x);
    pix->ny = a*(pix->y - sphere->y);
    pix->nz = a*(pix->z - sphere->z);

    a = - 2.0f * (ray->dx*pix->nx + ray->dy*pix->ny + ray->dz*pix->nz);
    pix->reflx = ray->dx + pix->nx*a;
    pix->refly = ray->dy + pix->ny*a;
    pix->reflz = ray->dz + pix->nz*a;

    float d = 1.0f / sqrtf(pix->reflx*pix->reflx + pix->refly*pix->refly + pix->reflz*pix->reflz);
    pix->reflx *= d;
    pix->refly *= d;
    pix->reflz *= d;
  }
}



//--------------------------------------------------------------------------




//---- rt_comparePixelObjects

inline bool rt_comparePixelObjects(RT_PIXEL *pix1, RT_PIXEL *pix2)
{
  return pix1->sphere == pix2->sphere;
}



//---- rt_comparePixels

inline bool rt_comparePixels(RT_PIXEL *pix1, RT_PIXEL *pix2)
{
  return
    pix1->sphere == pix2->sphere &&
    ((bool)pix1->shadow_sphere) == (bool)(pix2->shadow_sphere)
  &&
    pix1->refl_sphere == pix2->refl_sphere &&
    ((bool)pix1->refl_shadow_sphere) == (bool)(pix2->refl_shadow_sphere)
  ;
}

//#define rt_comparePixels(a, b) ((a)->sphere == (b)->sphere && (a)->shadow == (b)->shadow)



//---- rt_copyPixel
/*
void rt_copyPixel(RT_PIXEL *dest, RT_PIXEL *src)
{
  dest->col = src->col;
  dest->sphere = src->sphere;
  dest->shadow_sphere = src->shadow_sphere;
}
*/


//---- rt_blendRGB

int rt_blendRGB(int col1, int col2, int alpha)
{
  int r1 = (col1>>16)&255;
  int g1 = (col1>>8)&255;
  int b1 = (col1)&255;

  int r2 = (col2>>16)&255;
  int g2 = (col2>>8)&255;
  int b2 = (col2)&255;

  r1 += (r2-r1)*alpha/256;
  g1 += (g2-g1)*alpha/256;
  b1 += (b2-b1)*alpha/256;

  return (r1<<16)+(g1<<8)+b1;
}



//---- rt_spix

void rt_spix(RT_PIXEL *spix, int x, int y)
{
  if(spix->frame >= frame) return;
  spix->frame = frame;

  RT_RAY ray;

  ray.ox = 0;
  ray.oy = 0;
  ray.oz = 0;

  ray.dx = bx1 + x*dx;
  ray.dy = by1 + y*dy;
  ray.dz = 1;

  rt_intersect_first(&ray, spix);

  //- Do reflection

  if(spix->sphere != NULL)
  {
    int temp_stamp = stamp;
    stamp = 0;

    ray.ox = spix->x;
    ray.oy = spix->y;
    ray.oz = spix->z;
    ray.dx = spix->reflx;
    ray.dy = spix->refly;
    ray.dz = spix->reflz;

    RT_PIXEL spix2;
    rt_intersect(&ray, &spix2);

    spix->refl_sphere = spix2.sphere;
    spix->refl_shadow_sphere = spix2.shadow_sphere;

    spix->col = rt_blendRGB(spix->col, spix2.col, 48);

    stamp = temp_stamp;
  }
  else
  {
    spix->refl_sphere = NULL;
    spix->refl_shadow_sphere = NULL;
  }
}



//---- rt_pixel

void rt_pixel(int x, int y, int col)
{
  if(x >= 0 && x < w && y >= 0 && y < h) buf[y*w+x] = col;
}



//---- rt_dot

void rt_dot(int x, int y, int col)
{
  int i, j, col2;

  if((col&255) + ((col>>8)&255) + ((col>>16)&255) < 384) col2 = 0xFFFFFF; else col2 = 0x000000;

  for(i=-1; i<=1; i++)
  {
    rt_pixel(x-2, y+i, col2);
    rt_pixel(x+2, y+i, col2);
    rt_pixel(x+i, y-2, col2);
    rt_pixel(x+i, y+2, col2);
  }

  for(j=-1; j<=1; j++) for(i=-1; i<=1; i++) rt_pixel(x+i, y+j, col);
}



//---- rt_box

void rt_box(int x1, int y1, int x2, int y2, int col)
{
  int i;

  for(i=x1; i<x2; i++) rt_pixel(i, y1, col);
  for(i=x1; i<x2; i++) rt_pixel(i, y2, col);

  for(i=y1; i<y2; i++) rt_pixel(x1, i, col);
  for(i=y1; i<y2; i++) rt_pixel(x2, i, col);
}



//---- rt_frame

void rt_frame(int x1, int y1, int x2, int y2, int col)
{
  int col2;

  if((col&255) + ((col>>8)&255) + ((col>>16)&255) < 384) col2 = 0xFFFFFF; else col2 = 0x000000;

  rt_box(x1-1, y1-1, x2+1, y2+1, col2);
  rt_box(x1+1, y1+1, x2-1, y2-1, col2);

  rt_box(x1, y1, x2, y2, col);
}


//---- rt_render_recursive

void rt_render_recursive(int i, int j, int size)
{
  int offset = j*sw + i;
  int pixoffset = i*2 + j*w*2;

  int hsize = size >> 1;
  int dsize = size << 1;

  if( 1 || rt_comparePixels(&spixel[ offset ], &spixel[ offset + size]) &&
      rt_comparePixels(&spixel[ offset ], &spixel[ offset + sw*size]) &&
      rt_comparePixels(&spixel[ offset ], &spixel[ offset + sw*size + size]) )
  {
    //  TODO: Render square here!!

    register int u, v;

    if(0 && spixel[ offset ].sphere != NULL)
    {
      register int col = spixel[ offset ].col;

      for(v=0; v<dsize; v++)
      {
        for(u=0; u<dsize; u++)
        {
          buf[ pixoffset ++ ] = col;
        }
        pixoffset += w - dsize;
      }

    }
    else
    {
      int col = spixel [ offset ].col;

      for(v=0; v<dsize; v++)
      {
        for(u=0; u<dsize; u++)
        {
          buf[ pixoffset ++ ] = col;
        }
        pixoffset += w - dsize;
      }
    }
    
////    buf[i*2 + j*2*w] = 0xFFFFFF;
  }
  else if(size > 1)
  {
    int oldstamp = stamp;

//    if(size < 4)
/*
    {
      stamp ++;

      (spixel[ offset              ].sphere ? spixel[ offset              ].sphere : rt_sphere_null)->stamp = stamp;
      (spixel[ offset+size         ].sphere ? spixel[ offset+size         ].sphere : rt_sphere_null)->stamp = stamp;
      (spixel[ offset+sw*size      ].sphere ? spixel[ offset+sw*size      ].sphere : rt_sphere_null)->stamp = stamp;
      (spixel[ offset+sw*size+size ].sphere ? spixel[ offset+sw*size+size ].sphere : rt_sphere_null)->stamp = stamp;

      (spixel[ offset              ].shadow_sphere ? spixel[ offset              ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
      (spixel[ offset+size         ].shadow_sphere ? spixel[ offset+size         ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
      (spixel[ offset+sw*size      ].shadow_sphere ? spixel[ offset+sw*size      ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
      (spixel[ offset+sw*size+size ].shadow_sphere ? spixel[ offset+sw*size+size ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
*/
/*
      (spixel[ offset              ].refl_sphere ? spixel[ offset              ].sphere : rt_sphere_null)->refl_stamp = stamp;
      (spixel[ offset+size         ].refl_sphere ? spixel[ offset+size         ].sphere : rt_sphere_null)->refl_stamp = stamp;
      (spixel[ offset+sw*size      ].refl_sphere ? spixel[ offset+sw*size      ].sphere : rt_sphere_null)->refl_stamp = stamp;
      (spixel[ offset+sw*size+size ].refl_sphere ? spixel[ offset+sw*size+size ].sphere : rt_sphere_null)->refl_stamp = stamp;

      (spixel[ offset              ].refl_shadow_sphere ? spixel[ offset              ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
      (spixel[ offset+size         ].refl_shadow_sphere ? spixel[ offset+size         ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
      (spixel[ offset+sw*size      ].refl_shadow_sphere ? spixel[ offset+sw*size      ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
      (spixel[ offset+sw*size+size ].refl_shadow_sphere ? spixel[ offset+sw*size+size ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
*/
//    }
//    else stamp = 0;

    rt_spix( &spixel[ offset + hsize ], i*2+size, j*2);
    rt_spix( &spixel[ offset + sw*hsize ], i*2, j*2+size);
    rt_spix( &spixel[ offset + sw*hsize + hsize ], i*2+size, j*2+size);

    rt_spix( &spixel[ offset + sw*hsize + size ], i*2+size+size, j*2+size);
    rt_spix( &spixel[ offset + sw*size + hsize ], i*2+size, j*2+size+size);

    rt_render_recursive(i, j, hsize);
    rt_render_recursive(i+hsize, j, hsize);
    rt_render_recursive(i, j+hsize, hsize);
    rt_render_recursive(i+hsize, j+hsize, hsize);

////    buf[i*2 + j*2*w] = 0xFFFFFF;

    if(size >= 4) stamp = oldstamp;
  }
  else
  {
/*
    stamp ++;

      (spixel[ offset              ].sphere ? spixel[ offset              ].sphere : rt_sphere_null)->stamp = stamp;
      (spixel[ offset+size         ].sphere ? spixel[ offset+size         ].sphere : rt_sphere_null)->stamp = stamp;
      (spixel[ offset+sw*size      ].sphere ? spixel[ offset+sw*size      ].sphere : rt_sphere_null)->stamp = stamp;
      (spixel[ offset+sw*size+size ].sphere ? spixel[ offset+sw*size+size ].sphere : rt_sphere_null)->stamp = stamp;

      (spixel[ offset              ].shadow_sphere ? spixel[ offset              ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
      (spixel[ offset+size         ].shadow_sphere ? spixel[ offset+size         ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
      (spixel[ offset+sw*size      ].shadow_sphere ? spixel[ offset+sw*size      ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
      (spixel[ offset+sw*size+size ].shadow_sphere ? spixel[ offset+sw*size+size ].shadow_sphere : rt_sphere_null)->shadow_stamp = stamp;
*/
/*
      (spixel[ offset              ].refl_sphere ? spixel[ offset              ].sphere : rt_sphere_null)->refl_stamp = stamp;
      (spixel[ offset+size         ].refl_sphere ? spixel[ offset+size         ].sphere : rt_sphere_null)->refl_stamp = stamp;
      (spixel[ offset+sw*size      ].refl_sphere ? spixel[ offset+sw*size      ].sphere : rt_sphere_null)->refl_stamp = stamp;
      (spixel[ offset+sw*size+size ].refl_sphere ? spixel[ offset+sw*size+size ].sphere : rt_sphere_null)->refl_stamp = stamp;

      (spixel[ offset              ].refl_shadow_sphere ? spixel[ offset              ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
      (spixel[ offset+size         ].refl_shadow_sphere ? spixel[ offset+size         ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
      (spixel[ offset+sw*size      ].refl_shadow_sphere ? spixel[ offset+sw*size      ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
      (spixel[ offset+sw*size+size ].refl_shadow_sphere ? spixel[ offset+sw*size+size ].shadow_sphere : rt_sphere_null)->refl_shadow_stamp = stamp;
*/

    buf[ pixoffset ] = spixel[offset].col;

    RT_PIXEL spix;

    spix.frame = 0; rt_spix( &spix, i*2+1, j*2  ); buf[ pixoffset + 1     ] = spix.col;
    spix.frame = 0; rt_spix( &spix, i*2  , j*2+1); buf[ pixoffset + w     ] = spix.col;
    spix.frame = 0; rt_spix( &spix, i*2+1, j*2+1); buf[ pixoffset + w + 1 ] = spix.col;

    ////    buf[i*2 + j*2*w] = 0xFFFFFF;
  }

}



//---- rt_subdiv8 (NEW)

void rt_subdiv8( int x, int y )
{
/*
  if( bottom right == bottom left && bottom right == top right && !(top || lhs mid pixels) )
  {
    // render square

  }
  else
  {
    // render triplet

    rt010_renderPixel( x+4, y+4 );
    rt010_renderPixel( x+8, y+4 );
    rt010_renderPixel( x+4, y+8 );

    // subdivide

    rt_subdiv4( x  , y   );
    rt_subdiv4( x+4, y   );
    rt_subdiv4( x  , y+4 );
    rt_subdiv4( x+4, y+4 );
  }
*/
}



//---- rt_render

void rt_render(float rx, float ry)
{
  int i, j, k, kk, x, y, u, v;

  int offset;

  //- TEMP: Animate spheres
/*
  int t = timeGetTime();

  for(i=0; i<numspheres-1; i++)
  {
    int r = 0xFF - 0x66 * i/numspheres;
    int g = 0xFF - 0xFF * i/numspheres;
    int b = 0x00 + 0x33 * i/numspheres;

    sphere[i].col = (r<<16)+(g<<8)+(b);

    sphere[i].ax = 5.0*sin(3.14159*(t/1982.0 + 0.5*2.3*(i+0.0)/(numspheres+0.0)));
    sphere[i].ay = 5.0*sin(3.14159*(t/1226.0 + 0.5*3.9*(i+0.0)/(numspheres+0.0)));
    sphere[i].az = 5.0*sin(3.14159*(t/5723.0 + 0.5*1.5*(i+0.0)/(numspheres+0.0)));
    sphere[i].rad = sin((0.14159*0.5+3.0*i)/numspheres)*(1.5 + 0.5*sin(3.14159*(t/1500.0 + 2.0*(i+0.0)/(numspheres+0.0))));
  }
*/
  //- Transform spheres

  float tx, ty, tz, s, c;

  float camera_z = 6.0;//13.0;//6.0

  for(i=0; i<numspheres; i++)
  {
    s = (float)sin(3.14159*ry);
    c = (float)cos(3.14159*ry);

    tx = sphere[i].ax * c + sphere[i].az * s;
    tz = sphere[i].az * c - sphere[i].ax * s;
    ty = sphere[i].ay;

    s = (float)sin(3.14159*rx);
    c = (float)cos(3.14159*rx);

    sphere[i].x = tx;
    sphere[i].y = ty * c + tz * s;
    sphere[i].z = camera_z + tz * c - ty * s;
  }

  //- Work out screen-space bounding boxes

  for(i=0; i<numspheres; i++)
  {
    float sx = w*0.5 + h*0.5 * sphere[i].x / sphere[i].z;
    float sy = h*0.5 + h*0.5 * sphere[i].y / sphere[i].z;

//    rt_dot(sx, sy, sphere[i].col);

    float radx = sphere[i].rad * h*0.75 / sphere[i].z;
    float rady = sphere[i].rad * h*0.75 / sphere[i].z;

    if(sx-w*0.5-radx < -h*0.5 || sx-w*0.5+radx > h*0.5) radx *= w/h;

//    radx = 20;
//    rady = 20;

    sphere[i].x1 = (sx-radx-w*0.5)/(h*0.5);
    sphere[i].y1 = (sy-rady-h*0.5)/(h*0.5);
    sphere[i].x2 = (sx+radx-w*0.5)/(h*0.5);
    sphere[i].y2 = (sy+rady-h*0.5)/(h*0.5);
  }

  //- Work out per-frame constants

  for(i=0; i<numspheres; i++)
  {
    sphere[i].r2 = sphere[i].rad*sphere[i].rad;
    sphere[i].c = sphere[i].x*sphere[i].x + sphere[i].y*sphere[i].y + sphere[i].z*sphere[i].z - sphere[i].r2;
  }

  //- Mark all objects as active

  stamp = 0;
  for(i=0; i<numspheres; i++) sphere[i].stamp = sphere[i].shadow_stamp = 0;
  for(i=0; i<numspheres; i++) sphere[i].refl_stamp = sphere[i].refl_shadow_stamp = 0;
  rt_sphere_null->stamp = 0;
  rt_sphere_null->shadow_stamp = 0;
  rt_sphere_null->refl_stamp = 0;
  rt_sphere_null->refl_shadow_stamp = 0;

  //- Reset debug data

  shadow_calc_count = 0;
  shadow_calc_pixels = 0;

  frame ++;

  //- Clear (debug)

  for(j=0; j<sh; j++)
  {
    for(i=0; i<sw; i++)
    {
      spixel[ j*sw + i ].col = 0xFF00FF;
      spixel[ j*sw + i ].sphere = NULL;
      spixel[ j*sw + i ].shadow_sphere = NULL;
    }
  }

//  for(i=0; i<w*h; i++) buf[i] = 0x0000FF;

  //- Render 8x8

  int subdiv_size = 4;

  for(j=0; j<sh; j+=subdiv_size)
  {
    for(i=0; i<sw; i+=subdiv_size)
    {
      rt_spix(&spixel[ j*sw + i ], i*2, j*2);
    }
  }

  //  TEST: Recursive method

  for(j=0; j<sh-subdiv_size; j+=subdiv_size)
  {
    for(i=0; i<sw-subdiv_size; i+=subdiv_size)
    {
      rt_render_recursive(i, j, subdiv_size);
    }
  }

  //- Testing stuff
/*
  for(i=0; i<numspheres; i++)
  {
    float sx = w*0.5 + h*0.5 * sphere[i].x / sphere[i].z;
    float sy = h*0.5 - h*0.5 * sphere[i].y / sphere[i].z;

    float r = sphere[i].rad;

    rt_dot(sx, sy, sphere[i].col);

    float minx = w, miny = h, maxx = 0, maxy = 0;

    int a, b, c;

    for(a=-1; a<=1; a+=2) for(b=-1; b<=1; b+=2) for(c=-1; c<=1; c+=2)
    {
      float px = w*0.5 + h*0.5 * (sphere[i].x + a*r) / (sphere[i].z + c*r);
      float py = h*0.5 - h*0.5 * (sphere[i].y + b*r) / (sphere[i].z + c*r);

      if(px < minx) minx = px;
      if(py < miny) miny = py;

      if(px > maxx) maxx = px;
      if(py > maxy) maxy = py;
    }

    rt_frame(minx, miny, maxx, maxy, sphere[i].col);
  }

  float sx = w*0.5 + h*0.5 * light_x / light_z;
  float sy = h*0.5 - h*0.5 * light_y / light_z;

  rt_dot(sx, sy, 0x0000FF);
*/
/*
for(k=0; k<10; k++)
  for(j=0; j<h-1; j++)
  {
    int o = j*w;

    for(i=0; i<w-1; i++)
    {
      buf[o] = ((buf[o]>>2)&0x3F3F3F) + ((buf[o+1]>>2)&0x3F3F3F) + ((buf[o+w]>>2)&0x3F3F3F) + ((buf[o+w+1]>>2)&0x3F3F3F);
      o++;
    }
  }
*/
  return;
}



















//---- RAYTRACE CLASS --------------------------------------------------------//

/*

DOING:



*/


//---- Raytrace

Raytrace::Raytrace( Image *im )
{
  rt_startup( im->buf, im->w, im->h );

  numspheres = 0;
  sphere = new Raytrace_Sphere[100];
}

//---- ~Raytrace

Raytrace::~Raytrace( )
{
  delete sphere;
}

//---- addSphere

void Raytrace::addSphere( float x, float y, float z, float r, int col )
{
  sphere[ numspheres ].x = x;
  sphere[ numspheres ].y = y;
  sphere[ numspheres ].z = z;
  sphere[ numspheres ].rad = r;
  sphere[ numspheres ].col = col;

  numspheres ++;
}

//---- setRotation

void Raytrace::setRotation( float rx, float ry )
{
  this->rx = rx;
  this->ry = ry;
}

//---- setLight

void Raytrace::setLight( float x, float y, float z )
{
  light[0] = x;
  light[1] = y;
  light[2] = z;
}

//---- render

void Raytrace::render( )
{
  light_x = light[0];
  light_y = light[1];
  light_z = light[2];

  rt_clearScene();

  for( int i=0; i<numspheres; i++)
  {
    rt_addSphere( sphere[i].x, sphere[i].y, sphere[i].z, sphere[i].rad, sphere[i].col );
  }

  rt_render( rx, ry );
}