#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include "SDL.h"
#include "vector3.h"

using namespace std;

/* Const's / defines */
int xres		= 320;
int yres		= 240;
const double centerz	= 300;
bool dolight		= true;
bool wireframe		= false;
bool ffast		= true;
bool do_stats		= false;

/* Global variables */
SDL_Surface *screen;
double samples[100][3];
int smc;
float *prepass_color;
int   *prepass_ids;
bool  *prepass_ok;
unsigned AA_ed, skip_ed;

struct trio {
	Vector v[3];
	float color[3];
	Vector a, b;
	Vector normal;
};
trio T[1000];
int tc;

Vector center;

typedef struct {
int x, y;
int *data;
}RawImg;
// the 'BM' magic in the beginning of a .BMP phile
#define BM_MAGIC 19778

// the .BMP header structure is taken from http://www.fortunecity.com/skyscraper/windows/364/bmpffrmt.html
typedef struct {
int fs;       // filesize
int lzero;
int bfImgOffset;  // basic header size
}BMHEADER;

typedef struct {
int ihdrsize; 	// info header size
int x,y;      	// image dimensions
Uint16 channels;// number of planes
Uint16 bitsperpixel;
int compression; // 0 = no compression
int biSizeImage; // used for compression; otherwise 0
int pixPerMeterX, pixPerMeterY; // dots per meter settings (why meters and not inches... maybe an attempt to conform to SI? :)
int colors;	 // number of used colors. If all specified by the bitsize are used, then it should be 0
int colorsImportant; // number of "important" colors (All in wonder..)
}BMiHEADER;

int CreateRaw(RawImg *a, int x, int y);
int LoadBmp(const char *fn, RawImg *a);


/**************************************
 * Internal Proc - Create Raw         *
 *------------------------------------*
 * *a - Pointer to the target RawImg  *
 *  x - desired width                 *
 *  y - desired height                *
 *------------------------------------*
 * On failure, a is NULL and CreateRaw*
 * returns 0.                         *
 **************************************/

int CreateRaw(RawImg *a, int x, int y)
{
 int asize, i;
 a->x = x;
 a->y = y;
 asize = x * y * 4;
 a->data = (int*) malloc(asize);
 if (a->data == NULL) {
 	a = NULL;
	return 0;
 	}
 for (i=0;i<x*y;i++) a->data[i] = 0;
 return 1;
}


/**************************************
 * Function - Loads a .bmp file into  *
 *            a RawImg                *
 * Supports 8-,24- and 32-bit images  *
 *------------------------------------*
 * fn - The path to the file.         *
 * *a - The target RawImg structure   *
 *------------------------------------*
 * On failure, LoadBmp returns 0.     *
 **************************************/
int LoadBmp(const char *fn, RawImg *a)
{FILE *f;
 int i, j, p, k;
 BMHEADER hd;
 BMiHEADER hi;
 int pal[256];
 int toread = 0;
 unsigned char *xx;
 int rowsz;
 unsigned short sign;

 if ((f = fopen(fn, "rb"))==NULL) {
 	//printf("LoadBmp:Can't open file: `%s'\n", fn);
 	return 0;
	}
 if (!fread(&sign, 2, 1, f)) return 0;
 if (sign!=BM_MAGIC) { printf("LoadBmp:`%s' is not a BMP file.\n", fn); return 0; }
 if (!fread(&hd, sizeof(hd), 1, f)) return 0;
 if (!fread(&hi, sizeof(hi), 1, f)) return 0;

 /* header correctness checks */
 if (!(hi.bitsperpixel==8 || hi.bitsperpixel==24 || hi.bitsperpixel==32))
 	{printf("LoadBmp:Cannot handle file format at %d bpp.\n",hi.bitsperpixel); return 0 ; }
 if (hi.channels!=1) {
 	printf("LoadBmp: cannot load multichannel .bmp!\n");
	return 0;
 	}
 /* ****** header is OK *******/

 // if image is 8 bits per pixel or less (indexed mode), read some pallete data
 if (hi.bitsperpixel <= 8) {
 	toread = (1<<hi.bitsperpixel);
 	if (hi.colors) toread=hi.colors;
 	if (!fread(pal, toread, 4, f)) return 0;
	}
 toread = hd.bfImgOffset - (54 + toread*4);
 if (toread)
 // skip the rest of the header
 	for (i=0;i<toread;i++)
		fgetc(f);
 k = hi.bitsperpixel / 8;
 rowsz = hi.x * k;
 if (rowsz%4)
 	rowsz = (rowsz / 4 + 1) * 4; // round the row size to the next exact multiple of 4
 xx = (unsigned char *) malloc(rowsz);
 p = hi.x * hi.y;
 if (!CreateRaw(a, hi.x, hi.y)) {
 	printf("LoadBmp: cannot allocate memory for bitmap! Check file integrity!\n");
	fflush(stdout);
	free(xx);
	fclose(f);
	return 0;
 	}
#ifdef DEBUG
 printf("LoadBmp: Loading \"%s\":%dx%dx%dbit BMP...", fn, hi.x, hi.y, hi.bitsperpixel); fflush(stdout);
#endif
 for (j=hi.y-1;j>=0;j--) {// bitmaps are saved in inverted y
	if (!fread(xx, 1, rowsz, f)) {
		printf("LoadBmp: short read while opening `%s', file is probably incomplete!\n", fn);
		free(xx);
		fclose(f);
		return 0;
		}
	p -= hi.x;
	for (i=0;i<hi.x;i++){ // actually read the pixels
		if (hi.bitsperpixel>8)
			a->data[p++] = xx[i*k] + ((int) xx[i*k+1])*256 + ((int) xx[i*k+2])*65536;
			else
			a->data[p++] = pal[xx[i*k]];
		}
	p -= hi.x;
 	}
 fclose(f);
 free(xx);
#ifdef DEBUG
 printf("OK\n");
 fflush(stdout);
#endif
 return 1;
}

RawImg bgnd;

int she(void)
{
	SDL_Event e;
	while ( SDL_PollEvent(&e)) { // handle keyboard & mouse
		if ( e.type == SDL_QUIT ) return 1;
		if ( e.type == SDL_KEYDOWN ) {
			if (e.key.keysym.sym == SDLK_ESCAPE) return 1;
		}
	}
	return 0;
}

void init(void)
{
	FILE *f;
	center = Vector(0, 0, centerz);
	f = fopen("data/samples.txt", "rt");
	if (!f) {
		printf("Can't find file `samples.txt' which should contain FSAA samples\n");
		exit(1);
	}
	smc = 0;
	while (3 == fscanf(f, "%lf%lf%lf", samples[smc], samples[smc] + 1, samples[smc] + 2)) smc++;
	fclose(f);

	f = fopen("data/figure.txt", "rt");
	if (!f) {
		printf("Can't find file figure.txt' which should contain the test figure\n");
		printf("This file contains triangles. Each line contains 12 numbers.\n");
		printf("The format is <x1> <y1> <z1> <x2> <y2> <z2> <x3> <y3> <z3> <r> <g> <b>\n");
		printf("<r> <g> and <b> are red-green-blue as floatingpoint numbers 0-1\n");
		exit(1);
	}
	tc = 0;
	bool bye = false;
	while(1) {
		for (int i = 0; !bye && i < 3; i++) {
			for (int j = 0; !bye && j < 3; j++)
				if (1 != fscanf(f, "%lf", &T[tc].v[i].v[j])) {
					bye = true; break;
				}
		}
		if (bye) break;
		if (!bye) {
			for (int i = 0; !bye && i < 3; i++)
				if (1 != fscanf(f, "%f",& T[tc].color[i])) {
					bye = true;
					break;
				}
			if (bye) break;
		}
		tc++;
	}

	fclose(f);
	for (int i = 0; i < tc; i++) {
		for (int j = 0; j < 3; j++) {
			T[i].v[j] += center;
		}
	}
	if (!LoadBmp( "background.bmp", &bgnd) )
	{
		if (!LoadBmp( "data/background.bmp", &bgnd) ) {
			CreateRaw(&bgnd, 1, 1);
			bgnd.data[0] = 0xffffff;
		}
	}
	if (ffast) {
		prepass_color = new float [4 * xres * yres * sizeof(float)];
		prepass_ids   = new int   [    xres * yres * sizeof(int)  ];
		prepass_ok    = new bool  [    xres * yres * sizeof(int)  ];
	}
}

#define get_id(x,y) (((x)<0||(x)>=xres||(y)<0||(y)>=yres)?-2:prepass_ids[(x)+(y)*xres])
#define get_ok(x,y) (((x)<0||(x)>=xres||(y)<0||(y)>=yres)?false:prepass_ok[(x)+(y)*xres])

void secpass_prepare(void)
{
	int p=0;
	for (int j = 0; j < yres; j++) {
		for (int i = 0; i < xres; i++,p++) {
			prepass_ok[p] = i <= xres - 3 ? 
				(prepass_ids[p]==prepass_ids[p+1] && 
					prepass_ids[p]==prepass_ids[p+2])
				: false;
		}
	}
}

unsigned toRGB32(float *a)
{
	a[0] <?= 1.0f;
	a[0] >?= 0.0f;
	a[1] <?= 1.0f;
	a[1] >?= 0.0f;
	a[2] <?= 1.0f;
	a[2] >?= 0.0f;
	return (((int)(255.0f*a[0])) << 16) +(((int)(255.0f*a[1])) << 8)+(((int)(255.0f*a[2])));
}
const float rcp255 = 0.00392156862745098f;
void fromRGB32(float *a, unsigned u)
{
	a[0] = ((u>>16)&0xff) * rcp255;
	a[1] = ((u>>8)&0xff) * rcp255;
	a[2] = ((u>>8)&0xff) * rcp255;
}

#define ma3x(a,b,c) (	  a.v[0] * b.v[1] * c.v[2] - a.v[0] * b.v[2] * c.v[1]\
			- b.v[0] * a.v[1] * c.v[2] + b.v[0] * a.v[2] * c.v[1]\
	 		+ c.v[0] * a.v[1] * b.v[2] - c.v[0] * b.v[1] * a.v[2])

double cross(Vector & v, trio & t)
{
	Vector &a = t.a;
	Vector &b = t.b;
	double Dcr= ma3x(a, b, v);
	if (fabs(Dcr) < 1e-9)
		return 1e9;
	double rDcr = 1.0 / Dcr;
	Vector h = t.v[0]*(-1.0);
	double q = ma3x(h,b,v) * rDcr;
	if (q < 0.0 || q > 1.0) return 1e9;
	double r = ma3x(a,h,v) * rDcr;
	if ( wireframe ) {
		if ( r < 0.0 || (r > 0.04 && q >0.04) || q+r>1) return 1e9;
	} else {
		if ( r < 0.0 || r > 1.0 || q + r > 1.0) return 1e9;
	}
	double p = ma3x(a,b,h) * -rDcr;
	return p;
}

void render_frame(void)
{
	unsigned *pixbuf = (unsigned*) screen->pixels;
	unsigned p;
	Vector ti = Vector(2.0 / xres, 0, 0);
	Vector tti= Vector(0, 2.0 / xres, 0);
	Vector tt;
	Vector t;
	float rsmc = 1.0f/smc; float rfirst = 1.0 / samples[0][2];
	long imgp = 0;
	bool skip[1000] = {false};
	float all = 0, rall;

	for (int i = 0; i < smc; i++) {
		all += samples[i][2];
	}
	rall = 1/all;

	for (int i = 0; i < tc; i++) {
		T[i].a.make_vector(T[i].v[2], T[i].v[0]);
		T[i].b.make_vector(T[i].v[1], T[i].v[0]);
		T[i].normal = T[i].a^T[i].b;
		T[i].normal.norm();
		if (!wireframe) if (T[i].normal * Vector(0,0,1) < 0) skip[i] = true;
	}
	
	for (int pass = 0; pass < (ffast ? 2 : 1); pass++) {
		bool prepass = ffast && (pass == 0);
		bool secpass = ffast && (pass == 1);
		int samplecount = prepass ? 1 : smc;
		
		if (secpass) {
			secpass_prepare();
		}
		
		tt = Vector(-1.0, -1.0 / xres * yres, 1);
		p = 0;
		for (int j = 0; j < yres; j++, tt+=tti, imgp=bgnd.x*(j%bgnd.y)) {
			t = tt;
			int imgrl = bgnd.x;
			for (int i = 0; i < xres; i++, p++,t+=ti) {
	
				float c[3] = {0,0,0};
				if ( 	secpass && 
					get_ok(i-1, j-1) && 
					get_ok(i-1, j) && 
					get_ok(i-1, j+1) &&
					get_id(i, j-1) == get_id(i, j) &&
					get_id(i, j-1) == get_id(i, j+1)
				   ) {
					c[0] = prepass_color[4*p  ] * rfirst;
					c[1] = prepass_color[4*p+1] * rfirst;
					c[2] = prepass_color[4*p+2] * rfirst;
					++skip_ed;
				} else {
					++AA_ed;
					for (int k = 0; k < samplecount; k++) {
						Vector pp;
						float weight = samples[k][2];
						pp.macc(t, ti, samples[k][0]);
						pp+=tti*samples[k][1];
						int bl = -1;
						double cdist = 1e8;
						for (int l = 0; l < tc; l++) {
							if (!skip[l]) {
								double tmp = cross(pp, T[l]);
								if (tmp < cdist) {
									cdist = tmp;
									bl = l;
								}
							}
						}
						if (bl == -1) {
							float tc[3];
							fromRGB32(tc, bgnd.data[imgp]);
							c[0] += weight*tc[0];
							c[1] += weight*tc[1];
							c[2] += weight*tc[2];
						}
						else
						{
							double z =1;
							if (dolight) {
								Vector q  = T[bl].normal;
								Vector one(0,0,1);
								z = one*q;
							}
		
							c[0] += weight*T[bl].color[0]*z;
							c[1] += weight*T[bl].color[1]*z;
							c[2] += weight*T[bl].color[2]*z;
						}
						if (prepass) {
							--AA_ed;
							prepass_ids[p] = bl;
							prepass_color[4*p  ] = c[0];
							prepass_color[4*p+1] = c[1];
							prepass_color[4*p+2] = c[2];
						}
	
					}
					for (int h = 0; h < 3; h++)
						c[h] *= rall;
				}
				pixbuf[p] = toRGB32(c);
				imgp++;
				if (--imgrl==0) {
					imgrl = bgnd.x;
					imgp-=bgnd.x;
				}
			}
		}
	}
	SDL_Flip(screen);
}

//#define apply(dst, src, i, j, a) \
//	dst.v[i] = cos(a)*src[i] - sin(a)*src[j];\
//	dst.v[j] = sin(a)*src[i] + cos(a)*src[j]
#define apply(dst, src, f, s, a) \
	m = atan2(src[s], src[f]);\
	r = sqrt(src[f]*src[f]+ src[s]*src[s]);\
	dst=src;\
	dst.v[f] = cos(m+a)*r;\
	dst.v[s] = sin(m+a)*r;

void rotate(double alpha, double beta)
{
	for (int i = 0; i < tc; i++) {
		for (int j = 0; j < 3; j++) {
			Vector t = T[i].v[j] - center, t1, t2;
			double r, m;
			apply(t1, t, 0, 2, alpha);
			apply(t2, t1, 1, 2, beta);
			T[i].v[j] = t2+center;

		}
	}
}
bool freerotate = false;

bool gesture(double & yy, double & xx)
{
	int deltax, deltay;
	int r = SDL_GetRelativeMouseState(&deltax, &deltay);
	if (r || (deltax || deltay)) {
		if (r) {
			yy = deltax/100.0;
			xx = deltay/100.0;
			} else {xx=yy=0; return false;}
		return true;
	}
	return false;
}

int main(int argc, char *argv[])
{
	int frames=0;
	for (int i = 1; i < argc; i++) {
		bool parsed = false;
		if (0 == strcmp(argv[i], "--nolight")) {
			dolight = false;
			parsed = true;
		}
		if (0 == strncmp(argv[i], "--xres=", 7)) {
			sscanf(argv[i], "--xres=%d", &xres);
			parsed = true;
		}
		if (0 == strncmp(argv[i], "--yres=", 7)) {
			sscanf(argv[i], "--yres=%d", &yres);
			parsed = true;
		}
		if (0 == strcmp(argv[i], "--rotate")) {
			freerotate = true;
			parsed = true;
		}
		if (0 == strcmp(argv[i], "--wire") || 0 == strcmp(argv[i], "--wireframe")) {
			wireframe = true;
			parsed = true;
		}
		if (0 == strcmp(argv[i], "--full")) {
			ffast = false;
			parsed = true;
		}
		if (0 == strcmp(argv[i], "--stats")) {
			do_stats = true;
			parsed = true;
		}
		if (0 == strcmp(argv[i], "--help")) {
			printf("Useful options: \n");
			printf("\t--xres=...\n");
			printf("\t--yres=...\n");
			printf("\t--rotate\n");
			printf("\t--nolight\n");
			printf("\t--wireframe\n");
			printf("\t--full\n");
			printf("\t--stats\n");
			exit(0);
		}
		if (!parsed) {
			printf("Unknown parameter `%s'; use `--help' to see available parameters.\n", argv[i]);
		}
	}
	if(SDL_Init(SDL_INIT_VIDEO | SDL_INIT_TIMER)< 0) {
		cout <<"Could not initialize SDL:" << SDL_GetError() << endl;
	} else {
		screen = SDL_SetVideoMode(xres, yres, 32, 0);
		SDL_WM_SetCaption("FSAA Test", NULL);
		init();
		rotate(0.5, 0.9);
		unsigned t1 = SDL_GetTicks();
		
		while (!she()) {
			render_frame();
			frames++;
			double aa, bb;
			if (freerotate) {
				rotate(M_PI/12.162536152, M_PI/17.545412);

				if (gesture(aa, bb)) {
					freerotate = false;
					rotate(aa,bb);
				}
			}
			else {
				if (gesture(aa, bb)) {
					rotate(aa, bb);
				}
			}
		}
		t1 = SDL_GetTicks() - t1;
		printf("%.3lf FPS\n", frames / (double) t1 * 1000.0);
	}
	if (ffast) {
		delete [] prepass_color;
		delete [] prepass_ids;
		delete [] prepass_ok;
		if (do_stats) {
			unsigned aaa = AA_ed + skip_ed;
			printf("All frames: %d; all pixels %u\n", frames, aaa);
			printf("Average %1.lf pixels (%6.2lf%% of the frame) per frame are fully traced\n", 
			       (double) AA_ed / frames, 100* (double) AA_ed / frames / (xres*yres));
			printf("Average %1.lf pixels (%6.2lf%% of the frame) per frame are single sampled\n", 
			       (double) skip_ed / frames, 100 *(double) skip_ed / frames / (xres*yres));
			
		}
	}
	SDL_Quit();
}