//////////////////////////////////////////////////////////////////////
// Alex Epshteyn
// CS 591b Computer Graphics
// Assignment 3
// Program: rendering.cpp
//
//
// Description: 
//////////////////////////////////////////////////////////////////////

#if defined(_MSC_VER)
#include "SDL.h"
#else
#include "SDL/SDL.h"
#endif

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <float.h>
#include <iostream>
using std::cout;


// FUNCTION PROTOTYPES
// Display primitive operations
void render(void);
void renderBox(int x1, int y1, int x2, int y2);
void putPixel(int x, int y, int color);
int getPixelColor(int x, int y);
// Control
void controlLoop(void);


// GLOBALS
#define SCREEN_WIDTH 640
#define SCREEN_HEIGHT 480
#define BG_COLOR 0; 
#define PI 3.141592653589793238462643
#define ROTATION_INCREMENT_X PI/128
#define ROTATION_INCREMENT_Y PI/192
#define ROTATION_INCREMENT_Z PI/256
#define FRAMERATE 20

SDL_Surface *screen;
double zBuffer[SCREEN_WIDTH][SCREEN_HEIGHT];


/** Fills the z-buffer with infinity values */
void clearZBuffer() {
  for (int x = 0; x < SCREEN_WIDTH; x++) {
    for (int y = 0; y < SCREEN_HEIGHT; y++) {
      zBuffer[x][y] = DBL_MAX;
    }
  }
}

/** 
 * Determines whether a point with the given z coord should be drawn.
 * If it turns out to be the closes to the viewer, returns true and updates the zBuffer accordingly.
 */
bool zBufferUpdate(int x, int y, double z) {
  if (x < 0 || x > SCREEN_WIDTH || y < 0 || y > SCREEN_HEIGHT)
    return false;

  if (zBuffer[x][y] >= z) {
    zBuffer[x][y] = z; // update the z buffer for this pixel
    return true;
  }
  else {
    return false;
  }
}



// DATA STRUCTURES AND OPERATIONS ON THEM

/** Represents 3D points and vectors */
struct vector3 {
  double x,y,z;

  vector3() { x = 0; y = 0; z = 0; }
  vector3(double x, double y, double z) { this->x = x; this->y = y; this->z = z; }
  /** Computes the magnitude of the vector */
  double magnitude() { return sqrt(pow(x,2) + pow(y,2) + pow(z,2)); }
  /** Returns string representaion of the vector formatted as (x,y,z) */
  char* toString() {
    char* str = (char*)malloc(sizeof(char)*50); 
    sprintf(str, "(%f,%f,%f)", x, y, z); 
    return str; 
  }
};


/** Subtracts 2 vectors, returning the difference */
vector3 minus(vector3 v1, vector3 v2) {
  return vector3(v1.x - v2.x,
		 v1.y - v2.y,
		 v1.z - v2.z);
}

/** Returns the cross product of the given vectors */
vector3 cross(vector3 a, vector3 b) {
  // From Shirley p.27: a x b = (ay*bz - az*by, az*bx - ax*zb, ax*by-ay*bx)
  return vector3(a.y*b.z - a.z*b.y,
		 a.z*b.x - a.x*b.z, 
		 a.x*b.y - a.y*b.x);
}

/** The primitive that will be used to define 3D shapes */
struct triangle {
  vector3 a, b, c;
  unsigned int color;
  
  triangle() { color = 0; }
  triangle(vector3 a, vector3 b, vector3 c) {
    this->a = a; this->b = b; this->c = c; color = 0;
  }
  triangle(vector3 a, vector3 b, vector3 c, unsigned int color) {
    this->a = a; this->b = b; this->c = c; this->color = color;
  }
  char* toString() {
    char* str = (char*)malloc(sizeof(char)*150); 
    sprintf(str, "<a=%s; b=%s; c=%s>", a.toString(), b.toString(), c.toString()); 
    return str; 
  }
  /** Calculates the area of the 2D projection of the triangle onto the x-y plane */
  double signedAreaXY(); 
  /** Calculates the barycentric coordinates of a point in relation to the triangle */
  void baryXY(vector3 point, double &alpha, double &beta, double &gamma);
  /** Draws the triangle */
  void rasterize();
};


/** 
 * Computes the signed area of the 2D projection of the triangle onto the x-y plane.
 * Softsurfer.com gives the vector formula: Area = mag(V x W)/2 where V, W are vectors for the
 * two sides of the triangle: V = (b-a), W = (c-a).  The article also explains that
 * "the signed area will be positive if V0V1V2 are oriented counterclockwise around the triangle,
 * and will be negative if the triangle is oriented clockwise; and so, this area computation can be
 * used to test for a triangle's orientation.  The signed area can also be used to test whether the
 * point V2 is to the left (positive) or the right (negative) of the directed line segment V0V1.
 * So this is a very useful primitive, and it's great to have such an efficient formula for it.
 */
double triangle::signedAreaXY() {
  vector3 side1 = minus(b,a); 
  vector3 side2 = minus(c,a); 
  // project onto x,y plane
  side1.z = 0;
  side2.z = 0;
  vector3 crossProd = cross(side1, side2);
  // the cross product of 2 xy plane vectors is a signed vector in the z direction,
  // so the z component of the cross product of the sides is also its own signed magnitude
  return cross(side1, side2).z / 2;
}

/** 
 * Calculates the barycentric coordinates of a point in relation to the triangle.
 * Shirley, p. 46 gives the equations the coords of point P in terms of the area, A, of triangle ABC:
 *   alpha = Aa / A  (where Aa is the area of the triangle PBC)
 *   beta = Ab / A  (where Ab is the area of the triangle PCA)
 *   gamma = Ac / A  (where Ac is the area of the triangle PAB)
 */
void triangle::baryXY(vector3 point, double &alpha, double &beta, double &gamma) {
  double myArea = signedAreaXY();
  // Note: must make sure the vertices in the subtriangles are counterclockwise
  // since the area function is computed counterclockwise in order to get matching signs
  triangle Aa = triangle(point, b, c);
  triangle Ab = triangle(point, c, a);
  triangle Ac = triangle(point, a, b);

  alpha = Aa.signedAreaXY() / myArea;
  beta  = Ab.signedAreaXY() / myArea;
  gamma = Ac.signedAreaXY() / myArea;
}


#define max(A,B) ( (A) > (B) ? (A) : (B) )
#define min(A,B) ( (A) < (B) ? (A) : (B) )

/** 
 * Draws the triangle's orthographic projection on the xy plane into the frame buffer.
 * The screen pixels for which the triangle's  bary coords are all nonnegative are part of the triangle.
 */
void triangle::rasterize() {
  // determine the bounding box of this triangle
  int minX = (int)floor(min(min(a.x, b.x), c.x));
  int maxX = (int)ceil (max(max(a.x, b.x), c.x));
  int minY = (int)floor(min(min(a.y, b.y), c.y));
  int maxY = (int)ceil (max(max(a.y, b.y), c.y));

  for (int x = minX; x <= maxX; x++) {
    for (int y = minY; y < maxY; y++) {
      vector3 p(x, y, 0);
      double alpha, beta, gamma;
      baryXY(p, alpha, beta, gamma);
      if (alpha >= 0 && beta >= 0 && gamma >= 0) {
	// interpolate the pixel's z-coordinate
	double z = alpha * a.z + beta * b.z + gamma * c.z;
	// check with the z-buffer whether this pixel is on top
	if (zBufferUpdate(x, y, z)) {
	  putPixel(x, y, color);
	}
      }
    }
  }
}


/** A 4D homogeneous matrix (to be used for transforming 3D vectors */
struct mat3h {
  double val[4][4];

  mat3h() {}

  /** Initializes the matrix to the given values */
  mat3h(double entries[4][4]) {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
	val[i][j] = entries[i][j];
      }
    }
  }
    
  /** Fills the matrix with zeros */
  void zero() {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
	val[i][j] = 0;
      }
    }
  }

  /** Fills the main diagonal with 1s and the rest with 0s */
  void identity() {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
	if (i == j) 
	  val[i][j] = 1;
	else
	  val[i][j] = 0;
      }
    }
  }
};


/** Multiplies the given matrices */
mat3h mat3hMult(mat3h a, mat3h b) {
  mat3h prod;
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      // prod(i,j) is the dot product of the i-th row of a and the j-th col of b
      prod.val[i][j] = 0;
      for (int k = 0; k < 4; k++) {
	prod.val[i][j] += a.val[i][k] * b.val[k][j];
      }
    }
  }
  return prod;
}

/** Multiplies a matrix and a vector (extending it to 4D) */
vector3 matMult(mat3h a, vector3 v) {
  double vArr[4] = {v.x, v.y, v.z, 1};
  double prod[4] = {0};
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
      prod[i] += a.val[i][j] * vArr[j];
    }
  }
  return vector3(prod[0], prod[1], prod[2]);
}

/** Constructs a matrix for rotation abound the x-axis */
mat3h rot3hX(double theta) {
  double c = cos(theta);
  double s = sin(theta);
  double val[4][4] = 
    {{1,   0,   0,  0}, 
     {0,   c,  -s,  0},
     {0,   s,   c,  0},
     {0,   0,   0,  1}};
  return mat3h(val);
}

/** Constructs a matrix for rotation about the y-axis */
mat3h rot3hY(double theta) {
  double c = cos(theta);
  double s = sin(theta);
  double val[4][4] = 
    {{c,  0,    s,   0}, 
     {0,  1,    0,   0},
     {-s, 0,    c,   0},
     {0,  0,    0,   1}};
  return mat3h(val);
}

/** Constructs a matrix for rotation about the z-axis */
mat3h rot3hZ(double theta) {
  double c = cos(theta);
  double s = sin(theta);
  double val[4][4] = 
    {{c,  -s,   0,   0}, 
     {s,  c,    0,   0},
     {0,  0,    1,   0},
     {0,  0,    0,   1}};
  return mat3h(val);
}

/** Constructs a matrix for the given translation */
mat3h translation3h(int dx, int dy, int dz) {
  double val[4][4] = 
    {{1,  0,   0,   dx}, 
     {0,  1,   0,   dy},
     {0,  0,   1,   dz},
     {0,  0,   0,   1}};
  return mat3h(val);
}



// GLOBALS

vector3 cubeVertices[8] = 
  {vector3(300, 200, 0), vector3(400, 200, 0),      // front square
   vector3(300, 300, 0), vector3(400, 300, 0),
   
   vector3(300, 200, 100), vector3(400, 200, 100),  // back square
   vector3(300, 300, 100), vector3(400, 300, 100)};

/** 
 * Tesselates the given cube with triangles, writes them into the given array.
 * There should be 8 vertices and 12 blank triangles given as parameters.
 */
void tesselateCube(vector3* cubeVertices, triangle* t) {
    t[0] = triangle(cubeVertices[2], cubeVertices[1], cubeVertices[0], 0xffffff);  // front
    t[1] = triangle(cubeVertices[2], cubeVertices[3], cubeVertices[1], 0xffffff);
     
    t[2] = triangle(cubeVertices[0], cubeVertices[1], cubeVertices[4], 0xffff00);  // top
    t[3] = triangle(cubeVertices[1], cubeVertices[5], cubeVertices[4], 0xffff00);
     
    t[4] = triangle(cubeVertices[2], cubeVertices[3], cubeVertices[6], 0xff00ff);  // bottom
    t[5] = triangle(cubeVertices[3], cubeVertices[7], cubeVertices[6], 0xff00ff);
     
    t[6] = triangle(cubeVertices[2], cubeVertices[0], cubeVertices[6], 0xff0000);  // left
    t[7] = triangle(cubeVertices[6], cubeVertices[0], cubeVertices[4], 0xff0000);
     
    t[8] = triangle(cubeVertices[7], cubeVertices[1], cubeVertices[3], 0x0000ff);  // right
    t[9] = triangle(cubeVertices[7], cubeVertices[5], cubeVertices[1], 0x0000ff);
     
    t[10] = triangle(cubeVertices[7], cubeVertices[6], cubeVertices[4], 0x00ffff);  // back
    t[11] = triangle(cubeVertices[7], cubeVertices[4], cubeVertices[5], 0x00ffff);
}

double xrot = 0;
double yrot = 0;
double zrot = 0;



void runTests() {
  // vectors
  vector3 v1(3, 4, 5);
  vector3 v2(1, 2, 3);

  cout << "Testing vectors\n";
  cout << v1.toString() << " - " << v2.toString() << " = " << minus(v1,v2).toString() << "\n";
  cout << v1.toString() << " x " << v2.toString() << " = " << cross(v1,v2).toString() << "\n";
  cout << v1.toString() << " x " << v1.toString() << " = " << cross(v1,v1).toString() << "\n";
  
  // triangles
  triangle t1(vector3(0, 0, 0), vector3(5, 0, 0), vector3(0, 6, 0), 99);  // xy-area = 15 (counterclockwise)
  triangle t2(vector3(0, 0, 0), vector3(0, 6, 0), vector3(5, 0, 0), 99);  // xy-area = -15 (clockwise)
  triangle t3(vector3(0, 0, 45), vector3(5, 0, 5), vector3(0, 6, 6), 99); // xy-area = 15
  triangle t4(vector3(0+5, 0+5, 45), vector3(5+5, 0+5, 5), vector3(0+5, 6+5, 6), 99); // xy-area = 15
  triangle t5(vector3(345, 1, 2), vector3(345, 3, 4), vector3(345, 5, 6), 99); // xy-area = 0 (same x-coord)
  triangle t6(vector3(1, 345, 2), vector3(3, 345, 4), vector3(5, 345, 6), 99); // xy-area = 0 (same y-coord)

  cout << "\nTesting triangles:\n";
  printf("Area(%s) = %f (Expected: 15)\n", t1.toString(), t1.signedAreaXY());
  printf("Area(%s) = %f (Expected: -15)\n", t2.toString(), t2.signedAreaXY());
  printf("Area(%s) = %f (Expected: 15)\n", t3.toString(), t3.signedAreaXY());
  printf("Area(%s) = %f (Expected: 15)\n", t4.toString(), t4.signedAreaXY());
  printf("Area(%s) = %f (Expected: 0)\n", t5.toString(), t5.signedAreaXY());
  printf("Area(%s) = %f (Expected: 0)\n", t6.toString(), t6.signedAreaXY());

  // barycentric coords: compute at a few points for the triangle t (same as t4)
  triangle t(vector3(5, 5, 45), vector3(10, 5, 5), vector3(5, 11, 6), 99); // xy-area = 15
  vector3 p[8];
  p[0] = vector3(5, 5, 1000);   // point at vertex A (origin) of the triangle
  p[1] = vector3(6, 6, 1000);   // point close to vertex A inside the xy projection of ABC
  p[2] = vector3(8, 8, 1234);   // point somewhere in the middle inside the xy projection of ABC
  p[3] = vector3(5, 8, 4321);   // point on the AC (vertical) edge of the triangle
  p[4] = vector3(8, 5, 0);      // point on the AB (horizontal) edge of the triangle
  p[5] = vector3(9, -2, 1000);  // point southeast of the triangle on the outside
  p[6] = vector3(50, 40, 1000); // point northeast of the triangle
  p[7] = vector3(-10, 6, 1000); // point west of the triangle
  vector3 baryCoords[8];
  printf("\nTesting bary coords of triangle %s\n", t.toString());
  for (int i = 0; i < 8; i++) {
    t.baryXY(p[i], baryCoords[i].x, baryCoords[i].y, baryCoords[i].z);
    printf("point%d%s => %s\n", i, p[i].toString(), baryCoords[i].toString());
  }

  clearZBuffer();
  // draw some triangles
  triangle(vector3(12, 54, 24), vector3(12, 300, 24), vector3(345, -45, 24), 0x00fefe11).rasterize();
  triangle(vector3(97, 67, 25), vector3(65, 200, 32), vector3(312, 5, 14), 0x0011fe11).rasterize();

  // test transformations
  vector3 pt(3,3,3);
  double angle = PI/4;
  printf("point%s rotated %f radians around x-axis => %s\n", pt.toString(), angle,
	 matMult(rot3hX(angle), pt).toString());
  printf("point%s rotated %f radians around y-axis => %s\n", pt.toString(), angle,
	 matMult(rot3hY(angle), pt).toString());
  printf("point%s rotated %f radians around z-axis => %s\n", pt.toString(), angle,
	 matMult(rot3hZ(angle), pt).toString());
}


/** Entry point */
int main(int argc, char *argv[])
{
  // Initialize SDL's subsystems - in this case, only video.
  if ( SDL_Init(SDL_INIT_VIDEO) < 0 ) 
    {
      fprintf(stderr, "Unable to init SDL: %s\n", SDL_GetError());
      exit(1);
    }

  // Register SDL_Quit to be called at exit; makes sure things are
  // cleaned up when we quit.
  atexit(SDL_Quit);
    
  // Attempt to create a SCREEN_WIDTHxSCREEN_HEIGHT window with 32bit pixels.
  screen = SDL_SetVideoMode(SCREEN_WIDTH, SCREEN_HEIGHT, 32, SDL_SWSURFACE);
  
  // If we fail, return error.
  if ( screen == NULL ) 
    {
      fprintf(stderr, "Unable to set %dx%d video: %s\n", SCREEN_WIDTH,
	      SCREEN_HEIGHT, SDL_GetError());
      exit(1);
    }


  //runTests();
  controlLoop();

  return 0;
}


void drawCube() {
  // apply the rotation to the cube's original vertices
  vector3 vertices[8];
  for (int i = 0; i < 8; i++) {
    // translate to the origin first, then rotate, then back
    mat3h translateToOrigin = translation3h(-350,-250,-50);
    mat3h compositeRotation = mat3hMult(mat3hMult(rot3hX(xrot), rot3hY(yrot)), rot3hZ(zrot));
    mat3h translateBack = translation3h(350,250,50);
    mat3h finalTransform = mat3hMult(translateBack, mat3hMult(compositeRotation, translateToOrigin));

    vertices[i] = matMult(finalTransform, cubeVertices[i]);
  }
   
  triangle triangles[12];
  tesselateCube(vertices, triangles);

  // draw the triangles of the cube
  for (int i = 0; i < 12; i++) {
    triangles[i].rasterize();
  }
}

void controlLoop() {
  int lastFrameTime = 0;
  // main animation loop
  while (true) {
    
    // wait for a new frame to start
    while (SDL_GetTicks() < (lastFrameTime + FRAMERATE + 1)) {
      SDL_Delay(1);
    }
    lastFrameTime = SDL_GetTicks();
    //printf("New frame started at %d ms\n", SDL_GetTicks());
    

    // Render stuff
    SDL_FillRect(screen, NULL, 0); // clear screen
    clearZBuffer();
    drawCube();
    render();

    // update the angles
    xrot += ROTATION_INCREMENT_X;
    yrot += ROTATION_INCREMENT_Y;
    zrot += ROTATION_INCREMENT_Z;

    int keyDownTime = 0; // when a key was pressed down

    // Poll for events, and handle the ones we care about.
    SDL_Event event;
    while (SDL_PollEvent(&event)) 
      {
	switch (event.type) 
	  {
	  case SDL_KEYDOWN:
	    // keep track of the time an arrow key is held down
	    // will take this into account when a key is released
	    keyDownTime = SDL_GetTicks();
	    break;
	  case SDL_KEYUP:  

	    // determine which key is released
	    switch (event.key.keysym.sym)
	      {
	      case SDLK_LEFT:
		break;
	      case SDLK_RIGHT:
		break;
	      case SDLK_UP:
		break;
		// If escape is pressed, quit
	      case SDLK_ESCAPE:
		exit(0);
		break;
	      }

	    break;
	  case SDL_MOUSEMOTION:
	    printf("Mouse moved by %d,%d to (%d,%d)\n", 
		   event.motion.xrel, event.motion.yrel,
		   event.motion.x, event.motion.y);
	    break;
	  case SDL_MOUSEBUTTONDOWN:
	    printf("Mouse button %d pressed at (%d,%d)\n",
		   event.button.button, event.button.x, event.button.y);
	    break;
	  case SDL_QUIT:
	    exit(0);
	  }
      }
  }
}



// DRAWING FUNCTIONS

/** Renders the given region of the screen */
void renderBox(int x1, int y1, int x2, int y2)
{   
  // Lock surface if needed
  if (SDL_MUSTLOCK(screen)) 
    if (SDL_LockSurface(screen) < 0) 
      return;

  // Unlock if needed
  if (SDL_MUSTLOCK(screen)) 
    SDL_UnlockSurface(screen);

  // Tell SDL to update the whole screen
  SDL_UpdateRect(screen, x1, y1, x2, y2);    
}


/** Renders the whole screen */
void render(void) {
  renderBox(0, 0, 640, 480);
}


/** Draws a pixel on the screen.  Does nothing if coords are out of bounds. */
void putPixel(int x, int y, int color) {
  if (x < 0 || x >= SCREEN_WIDTH || y < 0 || y >= SCREEN_HEIGHT)
    return;
  ((unsigned int *) screen->pixels)[y*SCREEN_WIDTH+x] = color;
}

/** 
 * Returns the color of pixel at the given coordinates or BG_COLOR
 * if out of bounds.
 */
int getPixelColor(int x, int y) {
  if (x < 0 || x >= SCREEN_WIDTH || y < 0 || y >= SCREEN_HEIGHT)
    return BG_COLOR;
  return ((unsigned int *) screen->pixels)[y*SCREEN_WIDTH+x];
}