/*****************************************************************************
Name            :   mountain.c 
C Author        :   Stel Michael

Copyright       :   1992 by VideoLogic Limited. All rights reserved.
		    No part of this software, either material or conceptual
		    may be copied or distributed, transmitted, transcribed,
		    stored in a retrieval system or translated into any
		    human or computer language in any form by any means,
		    electronic, mechanical, manual or other-wise, or
		    disclosed to third parties without the express written
		    permission of VideoLogic Limited, HomePark Estate,
		    King's Langley, Hertfordshire, WD4 8LZ, U.K.

Description     :   Generates mountain for display list
Program Type    :   ANSI
*****************************************************************************/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include "sgl.h"
#include "mountain.h"

#define ScaleUp 8.0f
#define	REPTIMES	2.0f

// Old define
//#define NEW(X) (X*)malloc(sizeof(X))

// Below is the new change
#define NEW(X) (X*)calloc(1, sizeof(X))


/* Our vertex structure */
typedef struct
{
	sgl_vector position;
	int MeshVertID;			
} FRACT_VERTEX;


/* Edge structure - used to record splitting of edges' data... */
typedef struct tagFRACT_EDGE
{
	FRACT_VERTEX *pV1, *pV2; //end points of edge
	FRACT_VERTEX *pVMid; //pointer to the generated "mid" point	
		
	struct tagFRACT_EDGE * pChildEdge1, *pChildEdge2;

	/* set if we aren't to add vertical displacement
	   when we subdivide the edge */
	sgl_bool constrained;  

} FRACT_EDGE;


/* Our face structure */
typedef struct tagFRACT_FACE
{
	/* Pointers to the vertices forming the face. IT IS ASSUMED,
	   that these are in clockwise order */
	FRACT_VERTEX *pVerts[3];
  
  	/* have pointers to 3 edges forming this face */
	FRACT_EDGE 	*pEdges[3];
   
	/* Pointers to the faces we may generate from this one */
	struct tagFRACT_FACE * pChild[4];

} FRACT_FACE;


static const sgl_vector VertPos[3]=
	{{-100.0f, 0.0f, 0.0f},
	 { 000.0f, 000.0f, 173.2f},
	 {100.0f, 0.0f, 0.0f}};

static int VertID;

/*****************************************************************
* Function Name		: SplitFace  
* Inputs			: pFace - pointer to face
*				      RecDepth - recursive depth
*					  ScaleFactor -	controls vertical position of split
*					  MinHeight - default minimum vertical position 
* Outputs			: none
* Returns			: void 
* Description		: Recursively splits face into random-sized 
*					  areas 
******************************************************************/

static void SplitFace(FRACT_FACE *pFace, const int RecDepth, 
				const float ScaleFactor,
				const float MinHeight)
{
	int i,j;
	FRACT_EDGE 	*pEdge;
	FRACT_EDGE 	*pInsideEdges[3];
	FRACT_FACE 	*pNewFace;

	/* First subdivide each edge */

	for(i = 0; i<3; i++)
	{
		pEdge = pFace->pEdges[i];

		/* if this edge has already been split by another face,
		   just jitter the point a little bit more by the vertex
		   opposite to the end points of this edge */

		if(pEdge->pVMid != NULL)
		{
			/*not implemented*/
		}

		/* if no "mid point" has been generated yet, use the end points
		   of the edge + a little bit of "noise" to jitter the point a
		   bit */

		else
		{
			float xzLen;
			float f1, f2, f3, ftotal;
		
			/* Allocate a new vertex */
			pEdge->pVMid = NEW(FRACT_VERTEX);

			/* Determine the "horizontal" length of the edge.
			   This is used to determine how much to displace the
			   point by */

			xzLen = 0.0f;
			for(j=0; j<3; j++)
			{
				float tmp;	  
				tmp = (pEdge->pV1->position[j] - pEdge->pV2->position[j]);
				tmp *=tmp;	
				xzLen += tmp;
			}
			xzLen = (float)sqrt(xzLen);

			/* Jittering factors. Jitter by the end points a lot, and 
			   the diagonally opposite */

			f1 = ((float)(sgl_rand() % 1000)) + 500.0f;
			f2 = ((float)(sgl_rand() % 1000)) + 500.0f;
			f3 = ((float)(sgl_rand() % 200))  - 100.0f;

			ftotal = f1 + f2 +f3;

			f1 /= ftotal;
			f2 /= ftotal;
			f3 /= ftotal;

			/* Compute the "mid" point. Compute a factor to allow it to 
			   be jittered so that we don't get creases */	

			for(j=0; j<3; j++)
			{	
				pEdge->pVMid->position[j] = 
					f1 * pEdge->pV1->position[j] +
					f2 * pEdge->pV2->position[j] +
					f3 * pFace->pVerts[(i + 2)%3]->position[j];				

				/* Determine how much to displace the surface vertically */

				if((j == 1) && (!pEdge->constrained))
				{
					
					pEdge->pVMid->position[j] += 
						xzLen * ScaleFactor *
						(((float)(sgl_rand() % 1000)) / 1000.0f - 0.5f);

					if(pEdge->pVMid->position[j] < MinHeight)
					{
						pEdge->pVMid->position[j] = MinHeight;
					}	 			
				} 		
			}

			/* Clear the "been output" id */
			pEdge->pVMid->MeshVertID = -2;

			/* Allocate the two new edges */
			pEdge->pChildEdge1 = NEW(FRACT_EDGE);
			pEdge->pChildEdge2 = NEW(FRACT_EDGE);

			/* Set up the child edge details
			   First the end points	*/
			pEdge->pChildEdge1->pV1= pEdge->pV1;
			pEdge->pChildEdge1->pV2= pEdge->pVMid;

			pEdge->pChildEdge2->pV1= pEdge->pVMid;
			pEdge->pChildEdge2->pV2= pEdge->pV2;


			pEdge->pChildEdge1->constrained =  pEdge->constrained;
			pEdge->pChildEdge2->constrained =  pEdge->constrained;
		
			/* And no mid points on these new edges yet.. */
		  	pEdge->pChildEdge1->pVMid= NULL;
		  	pEdge->pChildEdge2->pVMid= NULL;

		}
		
	}

	/* generate the 3 edges which are in the middle of the
	   face	*/
	
	for(i = 0; i<3; i++)
	{
		pInsideEdges[i] = NEW(FRACT_EDGE);
		pEdge = pInsideEdges[i];

		/* Set up the end points - these will be the mid points
		   of the outside edges	*/
		pEdge->pV1 = pFace->pEdges[i]->pVMid;
		pEdge->pV2 = pFace->pEdges[(i + 1) % 3]->pVMid;
	 
		pEdge->constrained = FALSE;

		/* Clear the mid point of the new edge */
		pEdge->pVMid = NULL;
	}


	/* generate the four faces from these edges
	   First do the 3 around the outside */

	for(i = 0; i<3; i++)
	{
		pFace->pChild[i] = NEW(FRACT_FACE);
		pNewFace = pFace->pChild[i];

		/* Set up the vertices around the outside
		   One from the corner of the original face
		   then two from the mid points of 2 edges */

		pNewFace->pVerts[0] = pFace->pVerts[i];
		pNewFace->pVerts[1] = pFace->pEdges[i]->pVMid;
		pNewFace->pVerts[2] = pFace->pEdges[(i+2)%3]->pVMid;

		/* Set up the edges that make the face
		   Make sure order is correct */

		if(pNewFace->pVerts[0] == pFace->pEdges[i]->pV1)
		{
			pNewFace->pEdges[0]=pFace->pEdges[i]->pChildEdge1;
		}
		else
		{
			assert(pNewFace->pVerts[0] == pFace->pEdges[i]->pV2);

			pNewFace->pEdges[0]=pFace->pEdges[i]->pChildEdge2;
		}

		pNewFace->pEdges[1]=pInsideEdges[(i + 2) % 3];


		if(pNewFace->pVerts[0] == pFace->pEdges[(i+2)%3]->pV1)
		{
			pNewFace->pEdges[2]=pFace->pEdges[(i+2)%3]->pChildEdge1;
		}
		else
		{
			assert(pNewFace->pVerts[0] == pFace->pEdges[(i+2)%3]->pV2);
			pNewFace->pEdges[2]=pFace->pEdges[(i+2)%3]->pChildEdge2;
		}
	 
		/* Set all the child pointers to Null */

		for(j = 0; j < 4; j++)
		{
			pNewFace->pChild[j]=NULL;
		}

	}
  
	/* Generate the centre face - note we still have to
	   define in clockwise order */
	pFace->pChild[3] = NEW(FRACT_FACE);
	pNewFace = pFace->pChild[3];

	/* Set up the vertices around the outside
	   ALL are taken from mid points */

	pNewFace->pVerts[0] = pFace->pEdges[0]->pVMid;
	pNewFace->pVerts[1] = pFace->pEdges[1]->pVMid;
	pNewFace->pVerts[2] = pFace->pEdges[2]->pVMid;

	/* Set up the edges that make the face */
	pNewFace->pEdges[0]= pInsideEdges[0];
	pNewFace->pEdges[1]= pInsideEdges[1];
	pNewFace->pEdges[2]= pInsideEdges[2];
  
	/* Decide if we need to recurse	*/

	if(RecDepth != 0)
	{
		SplitFace(pFace->pChild[0], RecDepth -1, ScaleFactor, MinHeight);
		SplitFace(pFace->pChild[1], RecDepth -1, ScaleFactor, MinHeight);
		SplitFace(pFace->pChild[2], RecDepth -1, ScaleFactor, MinHeight);
		SplitFace(pFace->pChild[3], RecDepth -1, ScaleFactor, MinHeight);
	}
}


/*****************************************************************
* Function Name		: OutputVertices 
* Inputs			: pFace - pointer to face
* Outputs			: none
* Returns			: void 
* Description		: Adds vertices to current display list  
******************************************************************/

void OutputVertices(FRACT_FACE *pFace)
{
	int i;

	/* Output each vertex, but only for the child faces
	   If this isn't a child, then recurse */
	
	if(pFace->pChild[0] != NULL)
	{
		/* Recurse */
	 	OutputVertices(pFace->pChild[0]);
	 	OutputVertices(pFace->pChild[1]);
	 	OutputVertices(pFace->pChild[2]);
	 	OutputVertices(pFace->pChild[3]);
	}
	
	/* Else add each of the vertices to the mesh,
	   unless they have already been added */
	
	else
	{

		for(i = 0; i < 3; i++)
		{
			if(pFace->pVerts[i]->MeshVertID < 0)
			{
				sgl_2d_vec UVs;

				/* Base texture wrapping on the XZ coordinates */
				UVs[0] = pFace->pVerts[i]->position[0]/ (128.0f / REPTIMES);
				UVs[1] = pFace->pVerts[i]->position[2]/ (128.0f / REPTIMES);

				sgl_add_vertices(1,
					&pFace->pVerts[i]->position,
					NULL, &UVs);

				pFace->pVerts[i]->MeshVertID =VertID;
				VertID ++;
			}
		}

	} /*end else output the faces vertices*/
}


/*****************************************************************
* Function Name		: OutputFaces 
* Inputs			: pFace - pointer to face
* Outputs			: none
* Returns			: void 
* Description		: Adds faces to current display list  
******************************************************************/

static void OutputFaces(FRACT_FACE *pFace)
{
	int i;
	int VertIDList[3];

	/* Output each child face
	   If this isn't a child, then recurse */

	if(pFace->pChild[0] != NULL)
	{
		/* Recurse */
	 	OutputFaces(pFace->pChild[0]);
	 	OutputFaces(pFace->pChild[1]);
	 	OutputFaces(pFace->pChild[2]);
	 	OutputFaces(pFace->pChild[3]);
	}

	/* Else Output this face....*/
	 
	else
	{
	   	for(i = 0; i < 3; i++)
		{
			VertIDList[i] = pFace->pVerts[i]->MeshVertID;
		}

		sgl_add_face(3,   VertIDList);
	}
}


/*****************************************************************
* Function Name		: GenerateMountain  
* Inputs			: level - recursive depth for fn SplitFace
*				      ScaleFactor -	scale of face splitting
*					  MinHeight - default minimum height of split
* Outputs			: none
* Returns			: void 
* Description		: Generate a mesh of given complexity at 
					  the current position in the display list 	  
******************************************************************/

void GenerateMountain(const int level, 
					const float ScaleFactor,
					const float MinHeight)
{
	FRACT_FACE InitialFace;	
	FRACT_EDGE InitialEdges[3];
	FRACT_VERTEX InitialVerts[3];

	int i, j;

	sgl_create_mesh(FALSE); 
	sgl_set_cull_mode(sgl_cull_anticlock);

	/*  Set up the Vertices	*/
	
	for(i = 0; i < 3; i++)
	{
		/* Set the corner positions */

		for(j = 0; j < 3; j++)
		{
			InitialVerts[i].position[j] = VertPos[i][j] * ScaleUp;
		}
		
		/* Mark that it hasn't been put in the SGL mesh yet */
		InitialVerts[i].MeshVertID = -1;
	}

	/*  Set up the initial edges */

	for(i = 0; i < 3; i++)
	{
		/*  Set up pointers to the ends of the edge */
		InitialEdges[i].pV1 = &InitialVerts[i];
		InitialEdges[i].pV2 = &InitialVerts[(i+1)%3];

		/* No mid point created yet so set to NULL */
		InitialEdges[i].pVMid = NULL;

		/* The first edges are constrained */
		InitialEdges[i].constrained = TRUE;
	}

	/* set up the initial face */
  
	for(i = 0; i < 3; i++)
	{
		InitialFace.pVerts[i] = &InitialVerts[i]; 
		InitialFace.pEdges[i] = &InitialEdges[i];
	}

	for(i = 0; i < 4; i++)
	{
		InitialFace.pChild[i] = NULL;
	}

	/* Recursively subdivide and generate new faces etc */
	SplitFace(&InitialFace, level, ScaleFactor, MinHeight);
   
	VertID = 0;

	/* Output the generated vertices */
	OutputVertices(&InitialFace);

	/* Output the child faces */
	OutputFaces(&InitialFace);
}

