/*
	orxonox - the future of 3D-vertical-scrollers
 
	Copyright (C) 2006 orx
 
	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2, or (at your option)
	any later version.
 
	### File Specific:
	main-programmer: Marco Biasini
 
 */
#include "terrain_page.h"
#include "terrain.h"
#include "glincl.h"
#include <stdio.h>
#include <math.h>

#define CHECK_GL_ERROR( _d ) do { \
	GLenum __err = glGetError(); \
	if ( __err != GL_NO_ERROR ) \
		printf( "check%s: %s\n", _d, (char*)gluErrorString( __err ) );\
	}\
	while ( 0 )

TerrainPage::TerrainPage( Terrain *_owner, int _xOffset, int _zOffset )
: TerrainQuad( _owner, _xOffset, _zOffset )
{
	scale = owner->getScale();
	numVertices = numIndices = 0;
	errors = new LODError[TerrainPage::MAX_LODS];
	vertices = NULL; indices = NULL; coords = NULL;
	position = Triple( scale.x*_xOffset, 0.0f, scale.z*_zOffset );
	isVisible = false;
	next = NULL;
	active = false;
	previous = NULL;
	currentLOD = -1;
	forceTesselation = true;
}

void TerrainPage::tesselateRow( int _z, int _xStride, int _zStride, bool _adaptLeft, bool _adaptRight )
{
	int xStart = 0, xEnd = owner->getPageSize();
	
	int halfStride = _zStride >> 1;


	if ( _z ) {
		addAgain( );
		addIndex( getIndex( 0, _z ) );
	}
	if ( _adaptLeft ) {
		assert( halfStride > 0 ); 		
		addIndex( getIndex( 0, _z ) );
		addIndex( getIndex( 0, _z+halfStride ) );
		addIndex( getIndex( _xStride, _z ) );
		addIndex( getIndex( 0, _z+_zStride ) );
		addIndex( getIndex( _xStride, _z+_zStride ) );
		addAgain();
		xStart = _xStride;
	}
	
	if ( _adaptRight )
		xEnd-=_xStride;
		
	for ( int x = xStart; x < xEnd; x+=_xStride ) {
		addIndex( getIndex( x, _z) );
		addIndex( getIndex( x, _z+_zStride ) );
	}
	
	int w = owner->getPageSize()-1;
	
	if ( _adaptRight ) {
		assert( halfStride > 0 ); 		
		addIndex( getIndex( w-_xStride, _z ) );
		addAgain();
		addIndex( getIndex( w, _z ) );
		addIndex( getIndex( w-_xStride, _z+_zStride ) );
		addIndex( getIndex( w, _z+halfStride ) );
		addIndex( getIndex( w, _z+_zStride ) );
	}
}

//TODO: Perform benchmark to measure if the isVisible test should be included
//in this method.

void TerrainPage::determineBorderAdaption( bool _adapt[] )
{
	_adapt[0] = _adapt[1] = _adapt[2] = _adapt[3] = false;
	
	if ( left  && left->isVisible ) 
		_adapt[TP_LEFT] = ( wantedLOD - left->getWantedLOD() ) > 0;
		
	if ( right && right->isVisible ) 
		_adapt[TP_RIGHT] = ( wantedLOD - right->getWantedLOD() ) > 0;
		
	if ( top && top->isVisible) 
		_adapt[TP_TOP] = ( wantedLOD - top->getWantedLOD() ) > 0;				
		
	if ( bottom && bottom->isVisible ) 
		_adapt[TP_BOTTOM] = ( wantedLOD - bottom->getWantedLOD() ) > 0;		
}

int TerrainPage::chooseLOD()
{
	wantedLOD = -1;
	Triple cam( owner->getCameraPosition() );
	
	for ( int i = TerrainPage::MAX_LODS-1; i >= 0; --i ) {
		Triple distance( cam.x-errors[i].correct.x,
						 cam.y-errors[i].correct.y,
						 cam.z-errors[i].correct.z );
		
		float d = distance.length();
		
		assert( d > 0.000001f );
		float err =  errors[i].diff / d ;
		
		if ( err*scale.y < owner->getDetail() ) {
			wantedLOD = i;
			break;
		}	
	}
	if ( wantedLOD < 0 ) {
		wantedLOD = TerrainPage::MAX_LODS-1;
	}	
	// Calculate the tween factor. The calculation is different if LOD is 0
	// 
	if ( wantedLOD > 0 ) {
		
	}
	else {
		
	}
	return wantedLOD;
}

void TerrainPage::activate()
{
	
	pTerrainPage list = owner->getActiveList();
	next = list;
	if ( list )
		list->previous = this;
	owner->setActiveList( this );
}

void TerrainPage::deactivate()
{
	pTerrainPage list = owner->getActiveList();
	
	if ( previous ) {
		previous->next = next;
	}
	if ( next ) {
		next->previous = previous;
	}
	if ( list == this )
		owner->setActiveList( next );
	next = NULL;
	previous = NULL;
	
}

void TerrainPage::calculateError( int _lod )
{
	float	sumError = 0.0f;
	int		numErrors = 0;
	int size = owner->getPageSize();
	if( _lod!=0 )
	{
		int stride = 1 << _lod, x0, y0, xi, yi;
		// Altough these four nested loops look very scary, they're not 
		// that bad and require only about O(n^2). 
		for( y0 = 0 ; y0 < size-stride; y0 += stride ) {
			for( x0 = 0; x0 < size-stride; x0 += stride ) {
				for( yi = 1; yi < stride; yi++ ) {
					for( xi = 1; xi < stride; xi++ )
					{
						int	x = x0+xi,
						y = y0+yi;
						float	fx0 = ( float )xi/( float )stride, fx1 = 1.0f-fx0,
								fy0 = ( float )yi/( float )stride, fy1 = 1.0f-fy0;
						
						float	height00 = getAltitude( x0, y0 ),
								height10 = getAltitude( x0+stride,y0 ),
								height01 = getAltitude( x0,y0+stride ),
								height11 = getAltitude( x0+stride, y0+stride );
						
						float	paintHeight =	fx1*fy1 * height00 +
							fx0*fy1 * height10 +
							fx1*fy0 * height01 +
							fx0*fy0 * height11,
							correctHeight =  getAltitude( x, y );
						
						float	er = ( float )fabs( correctHeight - paintHeight );
						
						numErrors++;
						sumError += er;
					}
				}
			}
		}
		float error = sumError / numErrors;
		getVertex(size/2, size/2, errors[_lod].correct);
		errors[_lod].real = errors[_lod].correct;
		errors[_lod].real.y += error;
		errors[_lod].diff = error;
	}
}

void TerrainPage::calculateBounds()
{
	int size = owner->getPageSize();
	float alt = 0.0f;
	
	Triple	min( xOffset*scale.x ,0.0f, zOffset*scale.z ), 
			max( (xOffset+1)*scale.x, 0.0f, (zOffset+1)*scale.z);
	
	min.y = max.y = getAltitude( 0, 0 );
	for ( int x = 0; x < size; ++x ) {
		for ( int z = 0; z < size; ++z ) {
			alt = getAltitude( x, z );
			min.y = fmin( min.y, alt );
			max.y = fmax( max.y, alt );
		}
	}
	bounds.set( min, max );
}

float TerrainPage::getAltitude( int _x, int _z ) const
{
	assert( _x >= 0 && _x < 17 );
	assert( _z >= 0 && _z < 17 );
	return position.y+scale.y*owner->getAltitude( 
			_x+(owner->getPageSize()-1)*xOffset, 
			_z+(owner->getPageSize()-1)*zOffset );
}

bool TerrainPage::needsRetesselation()
{
	
	bool 	leftChanged 	= ( left && left->isVisible ) && ( left->wantedLOD != left->currentLOD ),
			rightChanged	= ( right && right->isVisible ) && ( right->wantedLOD != right->currentLOD ),
			topChanged		= ( top && top->isVisible ) && ( top->wantedLOD != currentLOD ),
			bottomChanged	= ( bottom && bottom->isVisible ) && ( bottom->wantedLOD != bottom->currentLOD ),
			iChanged		=  wantedLOD != currentLOD;
				
	return ( leftChanged || rightChanged || topChanged || bottomChanged || forceTesselation || iChanged );
}

void TerrainPage::updateTesselation( )
{

	if ( needsRetesselation() ) {
		tesselate( wantedLOD );
	}	
	currentLOD = wantedLOD;
	forceTesselation = false;
}

void TerrainPage::tesselateLevelFourPatch( bool _adapt[] )
{
	const int	halfStride = 8, stride = 16;
	
	enum { ADAPT_L = 1, ADAPT_R = 2, ADAPT_B = 4, ADAPT_T = 8,
		ADAPT_LR = 3, ADAPT_LB = 5, ADAPT_LT = 9, ADAPT_RB = 6, 
		ADAPT_RT = 10, ADAPT_BT = 12, ADAPT_LRB = 7, ADAPT_LBT = 13, ADAPT_LRT = 11, 
		ADAPT_RBT = 14, ADAPT_LRBT = 15, ADAPT_NONE = 0 };
		
	int			code =  ( _adapt[TP_LEFT] 	? ADAPT_L : 0 ) | 
						( _adapt[TP_RIGHT] 	? ADAPT_R : 0 ) | 
						( _adapt[TP_BOTTOM] ? ADAPT_B : 0 ) | 
						( _adapt[TP_TOP]	? ADAPT_T : 0 );
	switch( code ) {
		case ADAPT_NONE:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( stride, stride ) );
			break;
			
	 	case ADAPT_L:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, stride ) );
			addAgain(  );
		 	break;
		
		case ADAPT_R:
			addIndex( getIndex( stride, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, 0 ) );
			addAgain(  );
			break;

		case ADAPT_LR:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( stride, stride ) );
			break;

		case ADAPT_B:
			addIndex( getIndex( 0, 0 ) );
			addAgain(  );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( stride, stride ) );
			break;

		case ADAPT_LB:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( stride, stride ) );
			break;

		case ADAPT_RB:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( stride, 0 ) );
			addAgain(  );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( stride, stride ) );
			break;

		case ADAPT_LRB:
			addIndex( getIndex( stride, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( 0, 0 ) );
			addAgain(  );
			break;

		case ADAPT_T:
			addIndex( getIndex( stride, stride ) );
			addAgain(  );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( 0, 0 ) );
			break;

		case ADAPT_LT:
			addIndex( getIndex( stride, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( 0, stride ) );
			addAgain(  );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( 0, 0 ) );
			break;

		case ADAPT_RT:
			addIndex( getIndex( stride, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( 0, 0 ) );
			break;

		case ADAPT_LRT:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( stride, stride ) );
			addAgain(  );
			break;

		case ADAPT_BT:
			addIndex( getIndex( 0, 0 ) );
			addAgain(  );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( stride, stride ) );
			addAgain(  );
			break;

		case ADAPT_LBT:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( stride, stride ) );
			addAgain(  );
			break;

		case ADAPT_RBT:
			addIndex( getIndex( stride, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( 0, 0 ) );
			addAgain(  );
			break;

		case ADAPT_LRBT:
			addIndex( getIndex( 0, 0 ) );
			addIndex( getIndex( 0, halfStride ) );
			addIndex( getIndex( halfStride, 0 ) );
			addIndex( getIndex( 0, stride ) );
			addIndex( getIndex( stride, 0 ) );
			addIndex( getIndex( halfStride, stride ) );
			addIndex( getIndex( stride, halfStride ) );
			addIndex( getIndex( stride, stride ) );
			break;
	}
}


void TerrainPage::tesselate( int _lod )
{

	int count = owner->getPageSize()*owner->getPageSize();	

	memset( indexHash, 0xffff, 
			sizeof(unsigned short)*count );
	
	numVertices = 0; numIndices = 0;
	
	//Calculate the pace, based on the lod.
	int stride = 1 << _lod;
		
	bool adapt[4];
	determineBorderAdaption( adapt );
	assert( isVisible );
	if ( _lod == TerrainPage::MAX_LODS-1 ) {
		tesselateLevelFourPatch( adapt );
		return;
	}
	
	int zStart = 0, zEnd = owner->getPageSize()-stride;
	
	if ( adapt[TP_TOP] ) {
		tesselateRow( 0, stride / 2, stride, adapt[TP_LEFT], adapt[TP_RIGHT] );
		zStart+= stride;
	}
	
	if ( adapt[TP_BOTTOM] )
		zEnd-= stride;
		
	for ( int z = zStart; z < zEnd; z+=stride )
		tesselateRow( z, stride, stride, adapt[TP_LEFT], adapt[TP_RIGHT] );
	

	if ( !adapt[TP_BOTTOM] )
		return;
		
	addAgain( );
	addIndex( getIndex( 0, owner->getPageSize()-1-stride ) );
	
	tesselateRow( owner->getPageSize()-1-stride, stride / 2, stride, adapt[TP_LEFT], adapt[TP_RIGHT] );

}


void TerrainPage::show( )
{
	int count = owner->getPageSize()*owner->getPageSize();
	
	vertices = new Triple[count];
	// Not the economical way, but we just want to have space for all indices.
	indices = new unsigned short[count*3];
	indexHash = new unsigned short[count];	
	coords = new TexCoord[count];
	forceTesselation = true;
	activate();
	active = true;
}

void TerrainPage::hide( )
{
	if ( vertices ) {
		delete[] vertices;
		vertices = NULL;
	}
	delete[] coords;	
	if ( indices ) {
		delete[] indices;
		indices = NULL;
		numIndices = 0;
	}
	deactivate();
}

void TerrainPage::drawBox()
{
	glMatrixMode( GL_MODELVIEW );
	glPushMatrix();
	glTranslatef( bounds.corner.x, bounds.corner.y, bounds.corner.z );
	glBegin( GL_QUADS );
		glVertex3f( 0.0f, 0.0f, 0.0f );
		glVertex3f(  bounds.x, 0.0f, 0.0f );
		glVertex3f( bounds.x, bounds.y, 0.0f );
		glVertex3f( 0.0f, bounds.y, 0.0f );
		
		glVertex3f( 0.0f, 0.0f, bounds.z );
		glVertex3f(  bounds.x, 0.0f, bounds.z );
		glVertex3f( bounds.x, bounds.y, bounds.z );
		glVertex3f( 0.0f, bounds.y, bounds.z );		
		
		glVertex3f( 0.0f, 0.0f, 0.0 );
		glVertex3f(  0.0, 0.0f, bounds.z );
		glVertex3f( 0.0f, bounds.y, bounds.z );
		glVertex3f( 0.0f, bounds.y, 0.0f );				
		
		glVertex3f( bounds.x, 0.0f, 0.0 );
		glVertex3f(  bounds.x, 0.0f, bounds.z );
		glVertex3f( bounds.x, bounds.y, bounds.z );
		glVertex3f( bounds.x, bounds.y, 0.0f );						
	glEnd();
	glPopMatrix();
}

void TerrainPage::draw( )
{
	//These give an error
	assert( glIsEnabled( GL_VERTEX_ARRAY ) );
	assert( !glIsEnabled( GL_NORMAL_ARRAY ) );
	assert( isVisible ); assert( numIndices > 0 );
	assert( active );
	active = false;
	CHECK_GL_ERROR( "1" );	
	glVertexPointer( 3, GL_FLOAT, 0, vertices );
	glTexCoordPointer( 2, GL_FLOAT, 0, coords );	
	glDrawElements( GL_TRIANGLE_STRIP, numIndices, 
					GL_UNSIGNED_SHORT, indices );
	
	if ( owner->debug() )
		drawBox( );
		
	CHECK_GL_ERROR( "2" );	
}

short TerrainPage::getIndex( int _x, int _z )
{
	unsigned short index = _z*owner->getPageSize()+_x;
	if ( indexHash[index] == 0xffff ) {
		//The vertex didn't exists before, lets create it.
		indexHash[index] = numVertices;
		getVertex( _x, _z, vertices[numVertices] );
		getCoord( _x, _z, coords[numVertices] );
		numVertices++;
	}
	return indexHash[index];
}

void TerrainPage::getCoord( int _x, int _z, TexCoord& _coord ) const 
{
	owner->getCoord( _x+xOffset*(owner->getPageSize()-1 ), 
					 _z+zOffset*(owner->getPageSize()-1 ), _coord );
}

void TerrainPage::getVertex( int _x, int _z, Triple& _vertex ) const
{
	_vertex.x = position.x+scale.x*_x/
		( owner->getPageSize()-1 );
	_vertex.y = getAltitude( _x, _z );
	_vertex.z = position.z+scale.z*_z/( owner->getPageSize()-1 );
}

void TerrainPage::calculateErrors()
{
	for ( int i = 0; i < TerrainPage::MAX_LODS; ++i )
		calculateError( i );
}