// Author : Chris Tolley
// Date   : 6/29/2004
// quadTreeTerrain.cpp contains the class definition for a class that uses
// a quad tree to render terrain.

#pragma warning ( disable : 4244 )

#include <windows.h>
#include <gl/gl.h>
#include <vector>
#include <math.h>

using namespace std;

#include "quadTreeTerrain.h"
#include "HeightBasedTexture.h"
#include "viewFrustum.h"

// Constructor.  size is the size of the tree matrix
quadTreeTerrain::quadTreeTerrain( int size, const char* heightFile, 
								  int texSize, float HeightScale )
: m_iSize( size ), m_bMatrix( NULL ), m_hTex( texSize )
{
	// Do some error checking on the size
	if( ( m_iSize - 1 ) % 2 != 0 )
	{
		MessageBox( NULL, "Invalid size for the quadTree.", NULL, NULL );
		return;
	}// End if

	// Initialize the boolean matrix
	m_bMatrix = new bool[ m_iSize * m_iSize ];

	// Initialize the matrix to all falses
	memset( m_bMatrix, false, ( m_iSize * m_iSize ) * sizeof( bool ) );

	// Load the height data
	HeightData hData( heightFile, m_iSize, m_iSize );

	// Create all the coordinates
	for( int z = 0; z < m_iSize; ++z )
	{
		for( int x = 0; x < m_iSize; ++x )
		{
			// Calculate the average heights around this point
			float height = hData.at( x, z );
			if( x > 0 )
			{
				height += hData.at( x - 1, z );
				height /= 2;
			}// End if
			if( x < m_iSize - 1 )
			{
				height += hData.at( x + 1, z );
				height /= 2;
			}// End if

			if( z > 0 )
			{
				height += hData.at( x, z - 1 );
				height /= 2;
			}// End if
			if( z < m_iSize - 1 )
			{
				height += hData.at( x, z + 1 );
				height /= 2;
			}// End if

			// Create the geometric coordinates
			m_vCoords.push_back( x );
			m_vCoords.push_back( height );
			m_vCoords.push_back( z );

			// Create the texture coordinates
			m_vTexCoords.push_back( float( x ) / float( size ) );
			m_vTexCoords.push_back( float( z ) / float( size ) );
		}// End for x
	}// End for z

	// Create the height based texture
	// Set up the color values
	vector< colorSet > colors;
	colorSet lowest;
	lowest.height_ = 0;
	lowest.text_.load( "images/lowestTile.bmp" );
	colors.push_back( lowest );

	colorSet low;
	low.height_ = 64;
	low.text_.load( "images/lowTile.bmp" );
	colors.push_back( low );

	colorSet high;
	high.height_ = 128;
	high.text_.load( "images/HighTile.bmp" );
	colors.push_back( high );

	colorSet highest;
	highest.height_ = 192;
	highest.text_.load( "images/highestTile.bmp" );
	colors.push_back( highest );

	// Generate the texture for this terrain
	m_hTex.initializeTexture( colors, hData );

	// Scale the height values
	for( int n = 1; n < m_vCoords.size(); n += 3 )
	{
		m_vCoords[n] = m_vCoords[n] * HeightScale;
	}// End for n

}// End quadTree::Constructor


// Destructor
quadTreeTerrain::~quadTreeTerrain()
{
	// Delete the matrix is there is one
	if( m_bMatrix )
	{
		delete[] m_bMatrix;
	}// End if
}// End 


// Refines the quadTree
void quadTreeTerrain::RefineNode( int maxX, int minX, int maxZ, int minZ, 
								  int c )
{
	// Calculate the edge size
	int edge = maxX - minX;

	// Calculate the middle point of this node
	int midX = ( maxX + minX ) / 2;
	int midZ = ( maxZ + minZ ) / 2;

	// Set the mid point for this node to true in the matrix
	m_bMatrix[ midZ * m_iSize + midX ] = true;

	// Basecase:
	// If the edge size is two then we can't subdivide any further down
	if( edge == 2 )
	{
		return;
	}// End if

	// Get the distance from the center of the scene for this node
	float distance = abs( midZ - m_fCenterZ ) + abs( midX - m_fCenterX );

	// Get the distance from the camera for this node
// 	float distance = viewFrustum::distanceFromNear( 
//				m_vCoords[ ( ( midZ * m_iSize + midX ) * 3 ) ],
//				m_vCoords[ ( ( midZ * m_iSize + midX ) * 3 ) + 1 ]
//														* m_fHeightScale,
//				m_vCoords[ ( ( midZ * m_iSize + midX ) * 3 ) + 2 ]	);

	// If the distance from the camera divided by the edge size is less
	// than c, then we subdivide this node
	if( ( distance / edge ) < c )
	{
		// Call this function on each child node
		// The bottom left child
		RefineNode( maxX, midX, midZ, minZ, c );
		
		// The bottom right child
		RefineNode( midX, minX, midZ, minZ, c ); 

		// The upper left child
		RefineNode( maxX, midX, maxZ, midZ, c );

		// the upper right child
		RefineNode( midX, minX, maxZ, midZ, c );
	}// End if
	else
	{
		// Otherwise we need to place a false in each of the childs midpoints
		// The bottom left child
		m_bMatrix[ ( ( midZ + minZ ) / 2 ) * m_iSize + 
				   ( ( maxX + midX ) / 2 ) ] = false;
		// The bottom right child
		m_bMatrix[ ( ( midZ + minZ ) / 2 ) * m_iSize + 
				   ( ( midX + minX ) / 2 ) ] = false;
		// The upper left child
		m_bMatrix[ ( ( maxZ + midZ ) / 2 ) * m_iSize + 
				   ( ( maxX + midX ) / 2 ) ] = false;
		// The upper right child
		m_bMatrix[ ( ( maxZ + midZ ) / 2 ) * m_iSize + 
				   ( ( midX + minX ) / 2 ) ] = false;
	}// End if 
}// End quadTree::RefineNode


// Renders the entire tree
void quadTreeTerrain::Render( int maxX, int minX, int maxZ, int minZ )
{
	// Set up the height scale value
	glPushMatrix();

	// Enable vertex and color arrays
	glEnableClientState( GL_VERTEX_ARRAY );
	glEnableClientState( GL_TEXTURE_COORD_ARRAY );

	// Enable texturing
	glEnable( GL_TEXTURE_2D );

	// Select this tree's texture
	m_hTex.select();

	// Set the vertex and color arrays
	glVertexPointer( 3, GL_FLOAT, 0, &m_vCoords[0] );
	glTexCoordPointer( 2, GL_FLOAT, 0, &m_vTexCoords[0] );

	// Call the render node
	RenderNode( maxX, minX, maxZ, minZ );

	// Disable texturing
	glDisable( GL_TEXTURE_2D );

	// Disable vertex arrays
	glDisableClientState( GL_VERTEX_ARRAY );

	// Reset the matrix stack
	glPopMatrix();
}// End quadTree::Render


// Renders a quadTree node
void quadTreeTerrain::RenderNode( int maxX, int minX, int maxZ, int minZ )
{
	// Calculate the mid points of this node
	int midX = ( maxX + minX ) / 2;
	int midZ = ( maxZ + minZ ) / 2;

	// Calculate the edge size of this node
	int edge = maxX - minX;

	// If this node is not in the frustum
	if( ! viewFrustum::sphereInFrustum(  
			m_vCoords[ ( ( midZ * m_iSize + midX ) * 3 ) ],
			m_vCoords[ ( ( midZ * m_iSize + midX ) * 3 ) + 1 ],
			m_vCoords[ ( ( midZ * m_iSize + midX ) * 3 ) + 2 ],

			m_vCoords[ ( ( maxZ * m_iSize + maxX ) * 3 ) ],
			m_vCoords[ ( ( maxZ * m_iSize + maxX ) * 3 ) + 1 ],
			m_vCoords[ ( ( maxZ * m_iSize + maxX ) * 3 ) + 2 ] ) )
	{
		// then we don't need to draw this node or any of it's children
		return;
	}// End if

	// Base Case: 
	// If the edge size is two then we can subdivide any further and we
	// just draw a fan omitting any vertices that we need to.
	if( edge == 2 )
	{
		// Start the triangle fan
		glBegin( GL_TRIANGLE_FAN );
		
		// Draw the center vertex
		glArrayElement( midZ * m_iSize + midX );

		// Draw the diagonal up and to the left
		glArrayElement( maxZ * m_iSize + maxX );

		// If this node is the left most node of if our left neighbor has as
		// at least as high a level of detail as this node
		if( maxX == m_iSize - 1 || 
						m_bMatrix[ midZ * m_iSize + ( midX + edge ) ] )
		{
			// draw the line to the left
			glArrayElement( midZ * m_iSize + maxX );
		}// End if

		// Draw the diagonal down and to the right
		glArrayElement( minZ * m_iSize + maxX );

		// If this node is the bottom most node or if our right neighbor has as
		// at least as high a level of detail as this node
		if( minZ == 0 ||
					m_bMatrix[ ( midZ - edge ) * m_iSize + midX ] )
		{
			// Draw the line straight down
			glArrayElement( minZ * m_iSize + midX );
		}// End if

		// Draw the diagonal down and to the right
		glArrayElement( minZ * m_iSize + minX );

		// If this node is the right most node or if our right neighbor has as
		// at least as high a level of detail as this node
		if( minX == 0 ||
					m_bMatrix[ midZ * m_iSize + ( midX - edge ) ] )
		{
			// Draw the line straigt to the right
			glArrayElement( midZ * m_iSize + minX );
		}// End if

		// Draw the diagonal up and to the right
		glArrayElement( maxZ * m_iSize + minX );

		// If this node is the up most node or if our upper neighbor has as 
		// at least as high a level of detail as this node
		if( maxZ == m_iSize - 1 ||
					m_bMatrix[ ( midZ + edge ) * m_iSize + midX ] )
		{
			// Draw the line straight up
			glArrayElement( maxZ * m_iSize + midX );
		}// End if

		// Draw the diagonal up and to the left to finish the fan
		glArrayElement( maxZ * m_iSize + maxX );

		glEnd();
	}// End if
	else
	{// Otherwise we have to draw a partial fan and then call render node on
		// the children that need a fan drawn.

		// Get the status of each child
		// Get the status of the upper left child
		bool UL = m_bMatrix[ ( ( maxZ + midZ ) / 2 ) * m_iSize +
							 ( ( maxX + midX ) / 2 ) ];
		// Get the status of the upper right child
		bool UR = m_bMatrix[ ( ( maxZ + midZ ) / 2 ) * m_iSize +
							 ( ( midX + minX ) / 2 ) ];
		// Get the status of the lower left child
		bool LL = m_bMatrix[ ( ( midZ + minZ ) / 2 ) * m_iSize +
							 ( ( maxX + midX ) / 2 ) ];
		// Get the status of the lower right child
		bool LR = m_bMatrix[ ( ( midZ + minZ ) / 2 ) * m_iSize +
							 ( ( midX + minX ) / 2 ) ];

		// Now it gets complicated.  We need to draw partial fans
		// based on the status of the children and the status of the
		// neighbors.
		// Start a fan and draw the upper section \|/
		glBegin( GL_TRIANGLE_FAN );
			// Draw the center of the fan
			glArrayElement( midZ * m_iSize + midX );

			// If the upper right child does not have it's own fan
			if( ! UR )
			{
				// Draw the diagonal up and to the right
				glArrayElement( maxZ * m_iSize + minX );
			}// End if

			// If this node is the up most node or if our upper neighbor has  
			// as at least as high a level of detail as this node
			if( maxZ == m_iSize - 1 ||
						m_bMatrix[ ( midZ + edge ) * m_iSize + midX ] )
			{
				// Draw the line straight up
				glArrayElement( maxZ * m_iSize + midX );
			}// End if

			// If the upper left child does not have it's own fan
			if( ! UL )
			{
				// Draw the diagonal up and to the left
				glArrayElement( maxZ * m_iSize + maxX );
			}// End if
		glEnd();

		// Start a fan and draw the right section 
		// \
		// -
		// /
		glBegin( GL_TRIANGLE_FAN );
			// Draw the center of the fan
			glArrayElement( midZ * m_iSize + midX );

			// If the upper left child does not have it's own fan
			if( ! UL )
			{
				// Draw the diagonal up and to the left
				glArrayElement( maxZ * m_iSize + maxX );
			}// End if

			// If this node is the left most node of if our left neighbor has
			// at least as high a level of detail as this node
			if( maxX == m_iSize - 1 || 
							m_bMatrix[ midZ * m_iSize + ( midX + edge ) ] )
			{
				// draw the line to the left
				glArrayElement( midZ * m_iSize + maxX );
			}// End if

			// If the lower left child does not have it's own fan
			if( ! LL )
			{
				// Draw the diagonal down and to the left
				glArrayElement( minZ * m_iSize + maxX );
			}// End if
		glEnd();

		// Start a new fan to draw the bottom section /|\
		
		glBegin( GL_TRIANGLE_FAN );
			// Draw the center of the fan
			glArrayElement( midZ * m_iSize + midX );

			// If the lower left child does not have it's own fan
			if( ! LL )
			{
				// Draw the diagonal down and to the left
				glArrayElement( minZ * m_iSize + maxX );
			}// End if

			// If this node is the bottom most node or if our right neighbor
			// has at least as high a level of detail as this node
			if( minZ == 0 ||
						m_bMatrix[ ( midZ - edge ) * m_iSize + midX ] )
			{
				// Draw the line straight down
				glArrayElement( minZ * m_iSize + midX );
			}// End if

			// If the lower right child does not have it's own fan
			if( ! LR )
			{
				// Draw the diagonal down and to the right
				glArrayElement( minZ * m_iSize + minX );
			}// End if
		glEnd();

		// Start a fan to draw the left section
		// /
		// -
		// \
		
		glBegin( GL_TRIANGLE_FAN );
			// Draw the center point
			glArrayElement( midZ * m_iSize + midX );

			// If the lower right child does not have it's own fan
			if( ! LR )
			{
				// Draw the diagonal down and to the right
				glArrayElement( minZ * m_iSize + minX );
			}// End if

			// If this node is the right most node or if our right neighbor
			// has at least as high a level of detail as this node
			if( minX == 0 ||
						m_bMatrix[ midZ * m_iSize + ( midX - edge ) ] )
			{
				// Draw the line straigt to the right
				glArrayElement( midZ * m_iSize + minX );
			}// End if

			// If the upper right child does not have it's own fan
			if( ! UR )
			{
				// Draw the diagonal up and to the right
				glArrayElement( maxZ * m_iSize + minX );
			}// End if
		glEnd();

		// Call render node on any children that are true
		if( LL )
			RenderNode( maxX, midX, midZ, minZ );
		
		if( LR )
			RenderNode( midX, minX, midZ, minZ ); 

		if( UL )
			RenderNode( maxX, midX, maxZ, midZ );

		if( UR )
			RenderNode( midX, minX, maxZ, midZ );
	}// End else
}// End quadTree::RenderNode


// Draws a grid over the area of the quadtree
void quadTreeTerrain::DrawGrid() const
{
	glColor3f( .5, .5, .5 );
	// Draw a grid to help me debug
	glBegin( GL_LINES );
	for( int n = 0; n < m_iSize; ++n )
	{
		glVertex3f( 0, 0, n );
		glVertex3f( m_iSize, 0, n );

		glVertex3f( n, 0, 0 );
		glVertex3f( n, 0, m_iSize );
	}// End for n
	glEnd();

	glColor3f( 1, 1, 1 );

	glPointSize( 5 );
	glBegin( GL_POINTS );
	for( int z = 0; z < m_iSize; ++z )
	{
		for( int x = 0; x < m_iSize; ++x )
		{
			if( m_bMatrix[ z * m_iSize + x ] )
			{
				glVertex3f( x, 0, z );
			}// End if
		}// End for x
	}// End for z
	glEnd();
	glPointSize( 1 );
}// End quadTree::DrawGrid
