// System-includes
#include <stdlib.h>
#include <stdio.h>
#include <math.h>							// für "pow"
#include <time.h>							// für Zufallsgenerator

// OpenGl-includes
#include <GL/glut.h>

#define WIN_SIZE_X 600						// Fenstergröße
#define WIN_SIZE_Y 600
#define LENGTH 10000.						// Seitenlänge eines Dreiecks

int win_width=WIN_SIZE_X;					// anfängliche Fenstergröße in win_width und win_height speichern
int win_height=WIN_SIZE_Y;
int azimut=0, elevation=0,					// für Kameraführung
	radius=LENGTH,							// Entfernung der Kamera vom Punkt (0,0,0)
	recDepth;								// Rekursionstiefe
float **points;								// 2dim. Array von Höhen
int Ax, Bx, By, Cy, raster;

// prüft, ob zu einem Punkt bereits eine Höhe existiert
float pointHeight (float x, float y, int count) {
	int i=0,iX,iY;
	float height;

	/* Array-Index anhand der Rasterung berechnen und prüfen, ob Punkt bereits existiert.
	 * Der Array-Index wird einfach durch eine Integer-Division der genauen Koordinaten durch den zuvor
	 * ermittelten Raster ermittelt. Der Index wurde dafür so klein gewählt, daß nicht 2 unterschiedliche Punkte
	 * den gleichen Index haben können. */
	iX=(x-Ax)/raster;
	iY=(y-By)/raster;
	//if ((points[iX][iY]>=0) || (points[iX][iY]==-1)) height = points[iX][iY]; else height = 0;
	height = points[iX][iY];

	// Punkt existiert noch nicht --> Höhe zufällig ermitteln (in Abhängigkeit der Rekursionstiefe) und Punkt speichern
	if (height==-1) {
		if ((rand()%2)==0)					// damit Höhe auch negativ werden kann
			height = rand() % (int)((LENGTH)/(pow(2,recDepth-count+1)));
		else
			height = -(rand() % (int)((LENGTH)/(pow(2,recDepth-count+1))));
		//if ((rand()%2)==0) height = -height;
		//height = height - 350.0;
		//printf("%f\n", height);
		//if (height<0) height=0;
		//printf("%f\n", height);
		//height = 400.0;
		points[iX][iY] = height;			// neue Höhe speichern
	}
	return height;							// zufällig ermittelte Höhe zurückgeben
}

// rekursive Methode zur Berechnung der Dreiecke
void recDraw (int x1, int y1, int z1,		// 3 Koordinaten des 1.,
			  int x2, int y2, int z2,		// 2. und 
			  int x3, int y3, int z3,		// 3. Punktes des neuen Dreiecks
			  int count) {					// Rekursionstiefe
	// Koordinaten der Kantenhalbierenden
	int x1New, y1New, z1New, x2New, y2New, z2New, x3New, y3New, z3New;
	float h;
	GLfloat tri_ambient0[] = {0.0,0.0,0.2,1.0};  // blau
	GLfloat tri_ambient1[] = {1.0,1.0,0.5,1.0};  // gelb
	GLfloat tri_ambient2[] = {0.5,1.0,0.5,1.0};  // hellgrün
	GLfloat tri_ambient3[] = {0.0,0.5,0.0,1.0};  // dunkelgrün
	GLfloat tri_ambient4[] = {0.8,0.8,0.5,1.0};  // braun
	GLfloat tri_ambient5[] = {0.7,0.7,0.7,1.0};  // grau
	GLfloat tri_ambient6[] = {1.0,1.0,1.0,1.0};  // weiß
	srand((unsigned)time(NULL));			// Zufallsgenerator mit aktueller Zeit initialisieren

	z1 = -z1; z2 = -z2; z3 = -z3;
	if (z1<0) z1 = 0;
	if (z2<0) z2 = 0;
	if (z3<0) z3 = 0;

	if (count>0) {
		// Punkte der Kantenhalbierenden berechnen und für diese Punkte zufällige Höhe ermitteln.
		// Wenn Punkt schon existiert: Höhe dieses Punkte übernehmen, ansonsten Höhe zufällig ermitteln
		x1New=(x1+x2)/2; y1New=(y1+y2)/2; 
		h = pointHeight(x1New,y1New,count);
		//if (h<0) h=0;
		z1New = (z1+z2)/2 + h;
		//if (z1<0) printf("1: %d / ", z1);
		//if (z1New<0) z1New = 0;
		x2New=(x2+x3)/2; y2New=(y2+y3)/2; 
		h = pointHeight(x2New,y2New,count);
		//printf("2: %f / ", h);
		//if (h<0) h=0;
		z2New = (z2+z3)/2 + h;
		//if (z2<0) printf("2: %d / ", z2);
		//if (z2New<0) z2New = 0;
		x3New=(x1+x3)/2; y3New=(y1+y3)/2; 
		h = pointHeight(x3New,y3New,count);
		//printf("3: %f / ", h);
		//if (h<0) h=0;
		z3New = (z1+z3)/2 + h;
		//if (z3<0) printf("3: %d / ", z3);
		//if (z3New<0) z3New = 0;

		// für die 4 neuen Dreiecke Methode mit neuen Koordinaten rekursiv aufrufen
		// (alle Dreicke gegen Uhrzeigersinn zeichnen --> einfache Berechnung der Normalvektoren)
		recDraw(x1,y1,z1, x1New,y1New,z1New, x3New,y3New,z3New, count-1);
		recDraw(x1New,y1New,z1New, x2,y2,z2, x2New,y2New,z2New, count-1);
		recDraw(x3,y3,z3, x3New,y3New,z3New, x2New,y2New,z2New, count-1);
		recDraw(x3New,y3New,z3New, x1New,y1New,z1New, x2New,y2New,z2New, count-1);	// mittleres Dreieck
	} else {								// unterste Rekursionsebene erreicht --> aktuelles Dreieck zeichnen
		// Normalvektor muß für korrekte Beleuchtung übergeben werden (Berechnung mittels Skalarprodukt)
		x1New = x1-x2; y1New = y1-y2; z1New = z1-z2;	// [Vektor1] - [Vektor2]
		x2New = x2-x3; y2New = y2-y3; z2New = z2-z3;	// [Vektor2] - [Vektor3]
		z3New = x1New*y2New - y1New*x2New;				// [Vektor1New] x [Vektor2New] (Skalarprodukt)
		x3New = y1New*z2New - z1New*y2New;
		y3New =	z1New*x2New - x1New*z2New;
		//h1 = pointHeight(x1New,y1New,0);
		//h1 = pointHeight(x2New,y2New,0);
		//h3 = pointHeight(x3New,y3New,0);
		//printf("%f\n", h1);

		// Dreieck zeichnen
		glBegin(GL_TRIANGLES);
			glNormal3f(x3New,y3New,z3New);
			h = (z1+z2+z3)/3.0;
			if (h==0) glMaterialfv(GL_FRONT, GL_AMBIENT, tri_ambient0);
			if (h>0) glMaterialfv(GL_FRONT, GL_AMBIENT, tri_ambient1);
			if (h>100) glMaterialfv(GL_FRONT, GL_AMBIENT, tri_ambient2);
			if (h>1000) glMaterialfv(GL_FRONT, GL_AMBIENT, tri_ambient3);
			if (h>2000) glMaterialfv(GL_FRONT, GL_AMBIENT, tri_ambient4);
			if (h>2500) glMaterialfv(GL_FRONT, GL_AMBIENT, tri_ambient5);
			if (h>2800) glMaterialfv(GL_FRONT, GL_AMBIENT, tri_ambient6);
			if (h<0) printf("%f\n", h);
			glVertex3f(x1, y1, z1);
			glVertex3f(x2, y2, z2);
			glVertex3f(x3, y3, z3);
		glEnd();
	}
}

// glutMainLoop() ruft die Methode display() auf
void display (void) {
	double x,y,z,pi=3.14;
	glClearColor (0.3f, 0.3f, 0.3f, 1.0f);					// Hintergrundfarbe auf dunkelgrau setzen
	glClear (GL_COLOR_BUFFER_BIT|GL_DEPTH_BUFFER_BIT);		// Farb- und Z-Puffer löschen

	glMatrixMode (GL_PROJECTION);							// PROJEKTIONSMATRIX (für Perspektive und sichtbaren Bereich) auswählen
	glLoadIdentity ();										// Proj.-Matrix zurücksetzen auf Einheitsmatrix (Ändern der Fenstergröße)
	gluPerspective(90, 1.0, LENGTH/4, 10*LENGTH);			// perspektivische Projektion (Blickfeld: 90°, W:H=1:1, near:, far:)

	glMatrixMode(GL_MODELVIEW);								// ANSICHTSMATRIX (manipuliert direkt das darzustellende Objekt) ...
	glLoadIdentity ();										// ... alle folgenden Operationen beziehen sich auf diese Matrix!

	// Punkt (x,y,z) auf der Kugel berechnen (für Kameraposition)
	x= radius * cos( (elevation*pi)/180 );
	z = x * sin ( ((azimut+90)*pi)/180 );
	x= x * cos ( ((azimut+90)*pi)/180 );
	y= radius * sin( (elevation*pi)/180 );
	
	// Kameraposition und Blickrichtung setzen
	gluLookAt(x,z,y, 0.0,0.0,0.0, 0,0,1);

	glCallList(1);											// Inhalt der Displayliste ausgeben
	glutSwapBuffers ();										// Front- und Backbuffer werden vertauscht
}

// (nicht-proporionale!) Anpassung des Fensterausschnittes an die aktuelle Fenstergröße
void reshape (int w, int h) {							
	win_width  = w;
	win_height = h;
	glViewport (0, 0, w, h);
}

// Initialisierungen
void myInit (void) {
	// Werte für Lichtart und Lichtposition festlegen
	GLfloat mat_ambient[] = {1.0,1.0,1.0,1.0};				// Reflexionseig. des Materials festlegen
	GLfloat light_ambient[]  = {0.0,0.0,0.0,0.5};			// Streulicht-Farbe auf weiß setzen

	// Materialeigenschaft festlegen
	glMaterialfv(GL_FRONT, GL_AMBIENT, mat_ambient);

	// Lichtquelle0 initialisieren
	glLightfv  (GL_LIGHT0,  GL_AMBIENT,  light_ambient);	// Typ der Lichtquelle0 festlegen

	glDepthFunc (GL_LESS);									// für Tiefenberechnung notwendig
	glEnable (GL_DEPTH_TEST);								// Z-Puffer-Test ein
	glEnable (GL_LIGHTING);									// Beleuchtung generell aktivieren
	glEnable (GL_LIGHT0);									// Lichtquelle0 aktivieren

    glEnable (GL_NORMALIZE);   // Normalvektoren werden automatisch normalisiert
	glEnable (GL_DEPTH_TEST);  // Tiefenbuffer aktivieren
}

// wird bei Drücken einer Taste aufgerufen
void keyboard (unsigned char key, int x, int y) {
	if (key==27) {
		exit(0);											// ASCII-Code für Escape
		glDeleteLists (1,1);								// Löschen der Liste 1		
	}
}
static void specialkey (int key, int x, int y) {
	switch (key) {
		case GLUT_KEY_DOWN:
			if (elevation > -85)							// Elevation auf +-85° beschränken, da ab 90° der
				elevation=elevation-5;						// UP-Vektor geändert werden müßte.
			break;
		case GLUT_KEY_UP: 
			if (elevation < 85)
				elevation=elevation+5;
			break;		
		case GLUT_KEY_LEFT: 
			azimut=(azimut-5)%360;							// %360, damit Werte nicht zu groß werden können
			break;		
		case GLUT_KEY_RIGHT:
			azimut=(azimut+5)%360;
			break;
		case GLUT_KEY_PAGE_UP:								// Entfernung zum Objekt verringern
			if (radius>LENGTH)
				radius-=LENGTH/10;
			break;
		case GLUT_KEY_PAGE_DOWN:
			if (radius<10*LENGTH)
				radius+=LENGTH/10;
			break;
	}
	glutPostRedisplay ();										// beim nächsten Durchlauf der glutMainLoop wird das Fenster neu gezeichnet
}

// erzeugt das GL-Fenster. Hier werden auch Callback-Funktionen (keyboard, mouse, display ...) definiert
void initialGLUT (void) {
	glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGBA | GLUT_DEPTH);	// Modus festlegen (Double-Genauigkeit, RGB-Farbe, Depth-Buffer)
	glutInitWindowSize (win_width, win_height);
	glutInitWindowPosition (0,0);
	glutCreateWindow ("Fractal Landscape");						// Window-Titel
	glutSpecialFunc (specialkey);
	glutKeyboardFunc (keyboard);
	glutReshapeFunc (reshape);
	myInit ();
	glutDisplayFunc (display);									// jedesmal, wenn sich Fensterinhalt ändert, wird diese Methode aufgerufen
}

// main function
void main (int argc, char **argv) {
	int numOfPoints, i, j;

	glutInit (&argc, argv);										// initialisiert die GLUT-library
	initialGLUT ();

	// Rekursionstiefe einlesen
	if (argc<2 || !strtol(argv[1],0,10) || strtol(argv[1],0,10)>10) {	// maximale Rekursionstiefe von 10
		printf ("Fehler!");
		return;
	} else
		recDepth = strtol(argv[1],0,10);
	
	// 2dim. Array für Höhen initialisieren
	numOfPoints = pow(2,recDepth+1);							// Anzahl der Punkte auf der äußersten Kante = Zeilenanzahl
	points = (float**) malloc (numOfPoints*sizeof(int));		// Platz für Zeiger reservieren
	for (i=0; i<numOfPoints; i++)
		points[i] = (float*) malloc (numOfPoints*sizeof(float));

	Ax=-LENGTH/2; Bx=LENGTH/2; By=-2886; Cy=LENGTH-2886;
	raster=0.5+(LENGTH/(numOfPoints-1));						// Rasterung für virtuelle Koordinaten iX und iY

	/* Es wird ein Raster errechnet, anhand dessen ein 2dimensionales Array aufgebaut wird. Die Indizes des Arrays sind die
	 * Koordinaten der Punkte, zu denen bereits eine Höhe errechnet wurde. An dieser Stelle wird im Array die Höhe gespeichert.
	 * Gibt es zu diesem Punkt noch keine Höhe, so steht an dieser Stelle -1. */
	for (i=0; i<numOfPoints; i++)
		for (j=0; j<numOfPoints; j++)
			points[i][j]=-1;									// alle Arrayfelder mit -1 initialisieren

	// Dreiecke berechnen und in Display-Liste speichern
	glNewList(1, GL_COMPILE);									// speichert Anweisungen in Liste
		recDraw(Ax,By,0,Bx,By,0,0,Cy,0,recDepth);				// (0,0,0) in der Mitte des (äußeren) Dreiecks
	glEndList();												// Ende der Liste

	// Speicherbereich für Array wieder freigeben
	for (i=0; i<numOfPoints; i++)
		free(points[i]);
	free(points);

	glutMainLoop ();											// Endlosschleife, ruft Callbackfunktionen auf
}