// rtray.cpp : Defines the entry point for the application.
//



#define RT_DEBUG_MODE

#include "stdafx.h"

#include <windows.h>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
#include <mmsystem.h>

#include "text.h"

#include "rt.h"


/*


  - Optimisations
    . Sphere screen space bounding boxes
      . Calculate based on cube
      . Make list of possible spheres at the start of each scanline
    . Work out differential by 4 pixels for a sphere

  # 3D point to screen point function


*/




//---- rt_view_create

RT_VIEW* rt_view_create( int w, int h )
{
  RT_VIEW* view = (RT_VIEW *)malloc( sizeof( RT_VIEW ) );

  //- Initialise view struct

  memset( (void *)view, 0, sizeof( RT_VIEW ) );

  view->w = w;
  view->h = h;
  view->size = w*h;

  view->buf = (int *)malloc( sizeof( int ) * view->size );
  view->obj = (unsigned int *)malloc( sizeof( unsigned int ) * view->size );

  //- Useful precalculated numbers

  view->bx1 = -1.0f*w/h;
  view->bx2 =  1.0f*w/h;
  view->bdx = 2.0f/h;
  //view->dx2 = dx * 2.0f;

  view->by1 =  1.0f;
  view->by2 = -1.0f;
  view->bdy = -2.0f/h;
  //view->dy2 = dy * 2.0f;

  //- Precalculate various values

  view->w2 = w*2;
  view->w3 = w*3;
  view->w4 = w*4;
  view->wm4 = w-4;

  //- Done

  return view;
}



//---- rt_view_destroy

void rt_view_destroy( RT_VIEW *view )
{
  //- Delete screen buffer then view structure

  free( (void *)view->obj );
  free( (void *)view->buf );
  free( (void *)view );
}



//---- rt_scene_create

RT_SCENE* rt_scene_create( )
{
  RT_SCENE* scene = (RT_SCENE *)malloc( sizeof( RT_SCENE ) );

  //- Initialise scene struct

  memset( (void *)scene, 0, sizeof( RT_SCENE ) );

  scene->numSpheres = 1;  //  Sphere 0 is a black background sphere

  //- Done

  return scene;
}



//---- rt_scene_destroy

void rt_scene_destroy( RT_SCENE *scene )
{
  free( (void *)scene );
}



//---- rt_scene_sphere

int rt_scene_sphere( RT_SCENE *scene, float x, float y, float z, float r, int col )
{
  int num = scene->numSpheres;

  //- ERROR: Cannot add sphere to scene - reached maximum (RT_SCENE_MAXSPHERES)

  if( scene->numSpheres >= RT_SCENE_MAXSPHERES ) return false;

  //- Initialise sphere struct

  memset( (void *)(scene->sphere + num), 0, sizeof( RT_SPHERE ) );

  scene->sphere[ num ].ax = x;
  scene->sphere[ num ].ay = y;
  scene->sphere[ num ].az = z;
  scene->sphere[ num ].col = col;
  scene->sphere[ num ].rad = r;

  scene->sphere[ num ].r2 = r*r;

  //- Increase number of spheres in scene

  scene->numSpheres ++;

  //- DONE: Returns an ID for the sphere

  return num;
}



//---- rt_scene_setRotation

void rt_scene_setRotation( RT_SCENE *scene, float rx, float ry )
{
  int i;

  //- Per-rotation constants

  float xs = (float)sin(3.14159*rx);
  float xc = (float)cos(3.14159*rx);
  float ys = (float)sin(3.14159*ry);
  float yc = (float)cos(3.14159*ry);

  scene->rx = rx;
  scene->ry = ry;
  scene->xs = xs;
  scene->xc = xc;
  scene->ys = ys;
  scene->yc = yc;

  //- Transform spheres

  RT_SPHERE *sphere = scene->sphere;

  float tx, ty, tz;

  for(i=0; i<scene->numSpheres; i++)
  {
    tx = sphere[i].ax * yc + sphere[i].az * ys;
    tz = sphere[i].az * yc - sphere[i].ax * ys;
    ty = sphere[i].ay;

    sphere[i].x =      tx;
    sphere[i].y =      ty * xc + tz * xs;
    sphere[i].z =  5 + tz * xc - ty * xs;
  }

  //- Work out constants for first ray (assumed to be from origin)

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

}



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



//---- INTERSECTION ROUTINES -------------------------------------------------//



//---- rt_intersect_first_sphere

//  Given a sphere and a ray returns the distance along the ray that the sphere intersects
//  If the ray does not intersect the sphere, returns < 0

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

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

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

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

  return -1.0f;
}



//---- rt_intersect_first

int rt_intersect_first( RT_SCENE *scene, RT_RAY *ray )
{
  //- Find which sphere this ray intersects

  int i, foundi = 0;
  float dd, d = 9999999.f;

  for(i=1; i<scene->numSpheres; i++)
  {
    dd = rt_intersect_first_sphere( ray, scene->sphere+i );
    if(dd > 0.0001f && dd < d) { d = dd; foundi = i; }
  }

  return foundi;
}



//---- SCREEN SPACE & 3D FUNCTIONS -------------------------------------------//



//---- rt_rotatePoint

//  Transforms the point by the scene's object roataion and z offset

void rt_rotatePoint( RT_SCENE *scene, float x, float y, float z, float *ax, float *ay, float *az )
{
  float tx, ty, tz;

  tx = x * scene->yc + z * scene->ys;
  tz = z * scene->yc - x * scene->ys;
  ty = y;

  *ax =      tx;
  *ay =      ty * scene->xc + tz * scene->xs;
  *az = 10 + tz * scene->xc - ty * scene->xs;
}



//---- rt_screenPoint

//  Calculates the screen co-ords of the given 3d point

//  Screen point returned is -1..1

void rt_viewPoint( RT_SCENE *scene, RT_VIEW *view, float x, float y, float z, float *vx, float *vy )
{
  //- Transform (x,y,z) by the scene's transformation

  rt_rotatePoint( scene, x, y, z, &x, &y, &z );

  //- Screen point ( ranges - X: -w/h to w/h, Y: -1 to 1 ) 

  float oz = 1.0f / z;

  x *= oz;
  y *= -oz;

  //  Calculate view point by scaling by view buffer size etc

  *vx = 0.5f * view->w + 0.5f * x * view->h;
  *vy = 0.5f * (y+1) * view->h;
}



//---- RENDERING ROUTINES ----------------------------------------------------//



//---- rt_scene_pixel_sphere

//  Returns the index of the sphere at this point
//  Inefficient for repeated calling

int rt_scene_pixel_sphere( RT_VIEW *view, RT_SCENE *scene, int x, int y )
{
  //- Set up ray

  RT_RAY ray;

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

  ray.dx = view->bx1 + x*view->bdx;
  ray.dy = view->by1 + y*view->bdy;
  ray.dz = 1;

  //- Precalculate some ray values

  rt_ray_first_precalc( &ray );

  //- Find out what this ray intersects

  return rt_intersect_first( scene, &ray );
}



//---- rt_scene_pixel

//  Finds what object is at the specified pixel

int rt_scene_pixel( RT_VIEW *view, RT_SCENE *scene, int x, int y )
{
  //- Set up ray

  RT_RAY ray;

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

  ray.dx = view->bx1 + x*view->bdx;
  ray.dy = view->by1 + y*view->bdy;
  ray.dz = 1;

  //- Precalculate some ray values

  rt_ray_first_precalc( &ray );

  //- Find out what this ray intersects

  int i = rt_intersect_first( scene, &ray );

  return scene->sphere[i].col;
}



//---- rt_render_area

//  Just a basic (slow) render

void rt_render_area( RT_SCENE *scene, int x1, int y1, int x2, int y2, RT_VIEW *view )
{
  int i, j;

  if( x1 < 0 ) x1 = 0;
  if( x1 >= view->w ) return;
  if( x2 > view->w ) x2 = view->w;
  if( x2 <= 0 ) return;

  if( y1 < 0 ) y1 = 0;
  if( y1 >= view->h ) return;
  if( y2 > view->h ) y2 = view->h;
  if( y2 <= 0 ) return;

  for( j=y1; j<y2; j++ )
    for( i=x1; i<x2; i++ )
      view->buf[ i + j * view->w ] = rt_scene_pixel( view, scene, i, j );
}




//---- rt_render_4x4

//  Renders at 4x deresolution

void rt_render_area_4x4( RT_SCENE *scene, int x1, int y1, int x2, int y2, RT_VIEW *view )
{
  int i, j;

  if( x1 < 0 ) x1 = 0;
  if( x1 >= view->w ) return;
  if( x2 > view->w ) x2 = view->w;
  if( x2 <= 0 ) return;

  if( y1 < 0 ) y1 = 0;
  if( y1 >= view->h ) return;
  if( y2 > view->h ) y2 = view->h;
  if( y2 <= 0 ) return;

  int w = view->w - 4;

  for( j=y1; j<y2; j+=4 )
  {
    for( i=x1; i<x2; i+=4 )
    {
      int o = i + j * view->w;
      int c = rt_scene_pixel( view, scene, i, j );
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      o += w;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      o += w;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      o += w;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
      view->buf[ o++ ] = c;
    }
  }
}



//---- ACCELERATED RENDERING FUNCTIONS ---------------------------------------//

/*

  Renders pixels in top corner of 4x4 squares

*/


//---- rt_render_sq

//  Renders a 4x4 square in the given colour at the offset in view->buf

//  NOTE: Do this inline for maximum efficiency

void rt_render_sq( RT_VIEW *view, int offset, int col )
{
  int wm4 = view->w - 4;

  view->buf[ offset++ ] ^= 0;//= col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  offset += wm4;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  offset += wm4;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  offset += wm4;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
  view->buf[ offset++ ] = col;
}



//---- rt_render_h4

void rt_render_h4( RT_SCENE *scene, RT_VIEW *view, int offset, int i, int j )
{
  unsigned int *obj = view->obj;
  int *buf = view->buf;

  int obj10 = obj[ offset + 1 ] = rt_scene_pixel_sphere( view, scene, i+1, j );
  int obj20 = obj[ offset + 2 ] = rt_scene_pixel_sphere( view, scene, i+2, j );
  int obj30 = obj[ offset + 3 ] = rt_scene_pixel_sphere( view, scene, i+3, j );

  RT_SPHERE *sphere = scene->sphere;

  int col10 = buf[ offset + 1 ] = sphere[ obj10 ].col;
  int col20 = buf[ offset + 2 ] = sphere[ obj20 ].col;
  int col30 = buf[ offset + 3 ] = sphere[ obj30 ].col;
}



//---- rt_render_v4

void rt_render_v4( RT_SCENE *scene, RT_VIEW *view, int offset, int i, int j )
{
  unsigned int *obj = view->obj;
  int *buf = view->buf;

  int obj10 = obj[ offset + view->w ] = rt_scene_pixel_sphere( view, scene, i, j+1 );
  int obj20 = obj[ offset + view->w2 ] = rt_scene_pixel_sphere( view, scene, i, j+2 );
  int obj30 = obj[ offset + view->w3 ] = rt_scene_pixel_sphere( view, scene, i, j+3 );

  RT_SPHERE *sphere = scene->sphere;

  int col10 = buf[ offset + view->w ] = sphere[ obj10 ].col;
  int col20 = buf[ offset + view->w2 ] = sphere[ obj20 ].col;
  int col30 = buf[ offset + view->w3 ] = sphere[ obj30 ].col;
}



//---- rt_render

//  Renders full scene using optimisations for realtime performance

void rt_render( RT_SCENE *scene, RT_VIEW *view )
{
  int i, j, k;
  int col;

  //  Precalc

  int w2 = view->w*2;
  int w3 = view->w*3;
  int w4 = view->w*4;
  int wm4 = view->w - 4;
  int hm4 = view->h - 4;

  int w = view->w;
  int h = view->h;

  //  Debug: clear everything

  memset( (void *)view->buf, 0, view->w*view->h*sizeof(int) );
  memset( (void *)view->obj, 0, view->w*view->h*sizeof(int) );

  //  Set up ray

  RT_RAY ray;

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

  ray.dy = view->by1;

  int offset;

  //  Do 4x4 subsample first

  offset = 0;

  for( j=0; j<view->h; j+=4 )
  {
    ray.dx = view->bx1;

    for( i=0; i<view->w; i+=4 )
    {
      rt_ray_first_precalc( &ray );

      view->obj[ offset ] = k = rt_intersect_first( scene, &ray );
      view->buf[ offset ] = scene->sphere[k].col;

      ray.dx += view->bdx*4.0f;
      offset += 4;
    }

    ray.dy += view->bdy*4.0f;
    offset += w3;
  }

  //  Fill in any which are solid

  RT_SPHERE *sphere = scene->sphere;

  int *buf = view->buf;
  unsigned int *obj = view->obj;

  offset = 4 + 4*w;

  for( j=4; j<hm4; j+=4 )
  {
    for( i=4; i<wm4; i+=4 )
    {
      //  Do 4x4 square if necessary

      unsigned int obj00 = obj[ offset ];
      unsigned int col00 = buf[ offset ];

      if( obj00 == view->obj[ offset-w4 ] && obj00 == view->obj[ offset-4 ] && obj00 == view->obj[ offset-w4-4 ] )
      {
        rt_render_sq( view, offset-w4-4, (col00 >> 1) & 0x7F7F7F7F );
      }
      else
      {
        rt_render_v4( scene, view, offset-w4-4, i-4, j-4 );

        rt_render_h4( scene, view, offset-w4-4, i-4, j-4 );
        rt_render_h4( scene, view, offset-w3-4, i-4, j-3 );
        rt_render_h4( scene, view, offset-w2-4, i-4, j-2 );
        rt_render_h4( scene, view, offset-w -4, i-4, j-1 );

/*
        int obj10 = obj[ offset - w  ] = rt_scene_pixel_sphere( view, scene, i, j-1 );
        int obj20 = obj[ offset - w2 ] = rt_scene_pixel_sphere( view, scene, i, j-2 );
        int obj30 = obj[ offset - w3 ] = rt_scene_pixel_sphere( view, scene, i, j-3 );

        int col10 = buf[ offset - w  ] = sphere[ obj10 ].col;
        int col20 = buf[ offset - w2 ] = sphere[ obj20 ].col;
        int col30 = buf[ offset - w3 ] = sphere[ obj30 ].col;

        // /

        offset -= w4;

        for( k=0; k<4; k++)
        {
          if( obj[ offset-4 ] == obj[ offset ] )
          {
            col = buf[ offset ];

            buf[ offset-3 ] = col;
            buf[ offset-2 ] = col;
            buf[ offset-1 ] = col;
          }
          offset += w;
        }
*/
      }

      offset += 4;
    }

    offset += w3+8;
  }

}



//---- DEBUG FUNCTIONS -------------------------------------------------------//



//---- rt_drawFrameRate

void rt_drawFrameRate( RT_VIEW *view )
{
  int i, j;

  //  Frame rate indicator

  static int frame = 0;
  frame ++;

  for(j=0; j<8; j++) for(i=0; i<8; i++)
  {
    view->buf[j*view->w+i] = ((-(((i+j+frame)>>2)&1)) ^ 0xFFFF00 );
  }

  //  FPS based on current frame

  static int lastTime = 0;
  int time = timeGetTime();
  float fps = time > lastTime ? (1000.0f / (time-lastTime)) : 0.0f;
  lastTime = time;

  static int startTime = 0;
  if( startTime == 0 ) startTime = time;

  //- Frame rate based on last 10 frames

  static int times[10] ={0,0,0,0,0,0,0,0,0,0};
  static int timeptr = 0;

  int time10 = time-times[timeptr];

  times[timeptr] = time;
  timeptr = (timeptr+1)%10;

  //- Frame rate based on last second

  static float fps1sec = 0;
  static int fps1secLast = 0;
  static int fps1secFrame = 0;

  if( time > fps1secLast+1000 )
  {
    fps1sec = ( frame-fps1secFrame ) / (0.001f * (time-fps1secLast) );

    fps1secLast  = time;
    fps1secFrame = frame;
  }

  //- Display string

  char s[64] = "hello";

  sprintf( s, "%d %9.03f %9.03f %9.03f %9.03f",
              frame, (time-startTime)*0.001f, fps, fps1sec, 10000.0f / time10 );

  text_draw( view->buf, view->w, view->h ,9, 1, s, 0xFFFFFF );
}



//---- rt_drawHUD

void rt_drawHUD( RT_SCENE *scene, RT_VIEW *view )
{
  int i;

  float sx, sy;
  int x, y;

  //- Sphere centres

  RT_SPHERE *sphere = scene->sphere;

  for( i=0; i<scene->numSpheres; i++ )
  {
    rt_viewPoint( scene, view, sphere->ax, sphere->ay, sphere->az, &sx, &sy );
    x = (int)sx;
    y = (int)sy;

    if( x >= 0 && x < view->w && y >= 0 && y < view->h )
    {
      view->buf[ x + y * view->w ] = 0xFF00FF;
    }

    sphere ++;
  }
}



//---- END OF FILE -----------------------------------------------------------//