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

#if !defined(AFX_QUADTREE_H__342566C9_A1EA_4EDD_B81E_85F0AC26C5B4__INCLUDED_)
#define AFX_QUADTREE_H__342566C9_A1EA_4EDD_B81E_85F0AC26C5B4__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <vector>
#include <math.h>
using std::vector;

#include "HeightData.h"
#include "HeightBasedTexture.h"

class quadTreeTerrain
{
public:
	// Constructor.  size is the size of the tree matrix
	quadTreeTerrain( int size, const char* heightFile, int texSize,
					 float HeightScale );

	// Destructor
	virtual ~quadTreeTerrain();
	
	// Refines the quadTree
	void RefineNode( int maxX, int minX, int maxZ, int minZ, int c );

	// Renders the entire tree
	void Render( int maxX, int minX, int maxZ, int minZ );

	// Renders a quadTree node
	void RenderNode( int maxX, int minX, int maxZ, int minZ );

	// Draws a grid over the area of the quadtree
	void DrawGrid() const;

	// Returns the height at x,z
	inline float GetHeightAt( const float x, const float z );

	// Returns a normal vector to the plane at x,z
	inline void GetNormal( float x, float z, 
	  					   float& nx, float& ny, float& nz );

	inline void SetHeightAt( int x, int z, float h )
	{ m_vCoords[ ( ( z * m_iSize + x ) * 3 ) + 1 ] = h; };

	// Returns the size of the quadTree
	inline int GetSize() const { return m_iSize - 1; };

	// Sets the center point of the scene
	inline void SetCenter( float x, float y, float z )
	{ m_fCenterX = x; m_fCenterY = y; m_fCenterZ = z; };
protected:
	// The size of the tree.  Must satisfy the equation 2n + 1;
	int m_iSize;

	// A pointer to the boolean matrix that this tree is based on
	bool* m_bMatrix;

	// The array to hold all the geometric coordinates for this tree
	vector< float > m_vCoords;

	// The array to hold all the texture coordinates for this tree
	vector< float > m_vTexCoords;

	// The texture for this terrain
	HeightBasedTexture m_hTex;

	// The center point of the scene
	float m_fCenterX;
	float m_fCenterY;
	float m_fCenterZ;
};


// Inline functions

// Returns the height at x,z
float quadTreeTerrain::GetHeightAt( const float x, const float z )
{
	// Get the decimal point of x and z
	double m = 1;
	float dx = modf( x, &m );
	float dz = modf( z, &m );

	// Create pointers to the three points we need to make a triangle
	float* p1;
	float* p2;
	float* p3;

	// Cast x and z to ints so we can get the correct point from the points
	int ix = x;
	int iz = z;

	// Get the points of the triangle from the coordinates
	if( dx > .5 )
	{
		if( dz > .5 )
		{
			// Top left point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize + 
							     ( ix + 1 ) ) * 3 ) ];

			// Bottom left point
			p2 = &m_vCoords[ ( iz * m_iSize + ( ix + 1 ) ) * 3 ];

			// Top right point
			p3 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize ) + ix ) * 3 ];
		}// End if
		else
		{
			// Top left point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize + 
							     ( ix + 1 ) ) * 3 ) ];

			// Bottom left point
			p2 = &m_vCoords[ ( iz * m_iSize + ( ix + 1 ) ) * 3 ];

			// Bottom right point
			p3 = &m_vCoords[ ( iz * m_iSize + ix ) * 3 ];
		}// End else
	}// End if
	else
	{
		if( dz > .5 )
		{
			// Top right point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize ) + ix ) * 3 ];

			// Bottom right point
			p2 = &m_vCoords[ ( iz * m_iSize + ix ) * 3 ];

			// Top left point
			p3 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize + 
							     ( ix + 1 ) ) * 3 ) ];
		}// End if
		else
		{
			// Top right point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize ) + ix ) * 3 ];

			// Bottom right point
			p2 = &m_vCoords[ ( iz * m_iSize + ix ) * 3 ];

			// Bottom left point
			p3 = &m_vCoords[ ( iz * m_iSize + ( ix + 1 ) ) * 3 ];
		}// End else
	}// End else

	// With those three points, calculate the equation for a plane formed
	// by that triangle

	// Calculate two vectors from the above points
	float v1[3] = { p2[0] - p1[0], p2[1] - p1[1], p2[2] - p1[2] };
	float v2[3] = { p3[0] - p2[0], p3[1] - p2[1], p3[2] - p2[2] };

	// Calculate the cross product from the above two vectors, which will
	// give us the plane's normal vector
	float N[3] = { v1[1] * v2[2] - v1[2] * v2[1],
				   v1[2] * v2[0] - v1[0] * v2[2],
				   v1[1] * v2[2] - v1[2] * v2[1] };

	// Using the vector normal N and a point on the triangle, p1, calculate
	// the coefficient D by taking the dot product of the two.
	float D = N[0] * p1[0] + N[1] * p1[1] + N[2] * p1[2];
	// Negate D
	D = -D;

	// Set up a few other variables to use in the equation for the plant
	float A = N[0];
	float B = N[1];
	float C = N[2];

	// To avoid a divide by zero error, return 0 if B is zero
	if( B == 0 )
		return 0;

	// Return the calculated height at point x,z
	return ( ( A * x ) + ( C * z ) + D ) / ( -B );
}// End quadTreeTerrain::GetHeightAt



// Returns a normal vector to the plane at x,z
void quadTreeTerrain::GetNormal( float x, float z, 
								 float& nx, float& ny, float& nz )
{
	// Get the decimal point of x and z
	double m = 1;
	float dx = modf( x, &m );
	float dz = modf( z, &m );

	// Create pointers to the three points we need to make a triangle
	float* p1;
	float* p2;
	float* p3;

	// Cast x and z to ints so we can get the correct point from the points
	int ix = x;
	int iz = z;

	// Get the points of the triangle from the coordinates
	if( dx > .5 )
	{
		if( dz > .5 )
		{
			// Top left point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize + 
							     ( ix + 1 ) ) * 3 ) ];

			// Bottom left point
			p2 = &m_vCoords[ ( iz * m_iSize + ( ix + 1 ) ) * 3 ];

			// Top right point
			p3 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize ) + ix ) * 3 ];
		}// End if
		else
		{
			// Top left point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize + 
							     ( ix + 1 ) ) * 3 ) ];

			// Bottom left point
			p2 = &m_vCoords[ ( iz * m_iSize + ( ix + 1 ) ) * 3 ];

			// Bottom right point
			p3 = &m_vCoords[ ( iz * m_iSize + ix ) * 3 ];
		}// End else
	}// End if
	else
	{
		if( dz > .5 )
		{
			// Top right point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize ) + ix ) * 3 ];

			// Bottom right point
			p2 = &m_vCoords[ ( iz * m_iSize + ix ) * 3 ];

			// Top left point
			p3 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize + 
							     ( ix + 1 ) ) * 3 ) ];
		}// End if
		else
		{
			// Top right point
			p1 = &m_vCoords[ ( ( ( iz + 1 ) * m_iSize ) + ix ) * 3 ];

			// Bottom right point
			p2 = &m_vCoords[ ( iz * m_iSize + ix ) * 3 ];

			// Bottom left point
			p3 = &m_vCoords[ ( iz * m_iSize + ( ix + 1 ) ) * 3 ];
		}// End else
	}// End else

	// With those three points, calculate the equation for a plane formed
	// by that triangle

	// Calculate two vectors from the above points
	float v1[3] = { p2[0] - p1[0], p2[1] - p1[1], p2[2] - p1[2] };
	float v2[3] = { p3[0] - p2[0], p3[1] - p2[1], p3[2] - p2[2] };

	// Calculate the cross product from the above two vectors, which will
	// give us the plane's normal vector
	nx = v1[1] * v2[2] - v1[2] * v2[1];
	ny = v1[2] * v2[0] - v1[0] * v2[2];
	nz = v1[1] * v2[2] - v1[2] * v2[1];
}// End quadTreeTerrain::GetNormal
#endif // !defined(AFX_QUADTREE_H__342566C9_A1EA_4EDD_B81E_85F0AC26C5B4__INCLUDED_)
