///////////////////////////////////////////////////////////////////////////////
/// @file deMapLoader.cpp
///
/// @brief Loader for Quake-style MAP files
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date May 2003
/// @author Assassin
/// @remarks Creation
///
/// @date Dec 2003
/// @author Assassin
/// @remarks Shifted into external CLI tool
///
///////////////////////////////////////////////////////////////////////////////

//#define LEAK_HUNTING  // comment out to disable leak-hunts

#include "deMapLoader.hpp"
#include "deScene.hpp"
#include "deBitmap.hpp"
#include "deMath.hpp"
#include "deString.hpp"
#include "deWorld.hpp"
#include "deRenderStates.hpp"
#include "deHash.hpp"
#include "deFunctors.hpp"
#include "deFileSystem.hpp"
#include "deFile.hpp"
#include <ctype.h>

namespace deMapConverter
{
enum FileType_t
{
	MAPFILE_Undecided = -1,
	MAPFILE_Q1,
	MAPFILE_Q3,
	MAPFILE_HL,
	MAPFILE_Force32bit = 0x7fffffff
};

enum TextLine_t
{
	MAP_Undecided = -1,
	MAP_None = 0,
	MAP_BraceOpen,
	MAP_BraceClose,
	MAP_Q1Plane,
	MAP_Q3Plane,
	MAP_HLPlane,
	MAP_Error_Mismatched_Parens,
	MAP_Error_Mismatched_Brackets,
	MAP_Force32bit = 0x7fffffff
};

enum TextData_t
{
	MAPData_None = 0,
	MAPData_OpenParen,
	MAPData_OpenBracket,
	MAPData_CloseParen,
	MAPData_CloseBracket,
	MAPData_OpenBrace,
	MAPData_CloseBrace,
	MAPData_Quote,
	MAPData_Num,
	MAPData_Other,
	MAPData_Force32bit = 0x7fffffff
};

enum BrushContent_t
{
    CONTENTS_EMPTY = -1,
	CONTENTS_SOLID = -2,
	CONTENTS_WATER = -3,
	CONTENTS_SLIME = -4,
	CONTENTS_LAVA = -5,
	CONTENTS_SKY = -6,
	CONTENTS_ORIGIN = -7,			// removed at csg time
	CONTENTS_CLIP = -8,				// changed to contents_solid
	
	CONTENTS_CURRENT_0 = -9,
	CONTENTS_CURRENT_90 = -10,
	CONTENTS_CURRENT_180 = -11,
	CONTENTS_CURRENT_270 = -12,
	CONTENTS_CURRENT_UP = -13,
	CONTENTS_CURRENT_DOWN = -14,
	
	CONTENTS_TRANSLUCENT = -15,
	CONTENTS_HINT = -16				// Filters down to CONTENTS_EMPTY by bsp, ENGINE SHOULD NEVER SEE THIS
};
#pragma todo(drop brushes with invisible contents) // recorded in ParseBrush

/////////////////////////////////////
// NOTE:: taken from halflife, change once new format devised
/////////////////////////////////////

BrushContent_t TextureContents(const char* const name)
{
    if (!strcmpi(name, "sky"))
        return CONTENTS_SKY;
	
    if (!strcmpi(name + 1, "!lava"))
        return CONTENTS_LAVA;
	
    if (!strcmpi(name + 1, "!slime"))
        return CONTENTS_SLIME;
	
    if (!strcmpi(name, "!cur_90"))
        return CONTENTS_CURRENT_90;
    if (!strcmpi(name, "!cur_0"))
        return CONTENTS_CURRENT_0;
    if (!strcmpi(name, "!cur_270"))
        return CONTENTS_CURRENT_270;
    if (!strcmpi(name, "!cur_180"))
        return CONTENTS_CURRENT_180;
    if (!strcmpi(name, "!cur_up"))
        return CONTENTS_CURRENT_UP;
    if (!strcmpi(name, "!cur_dwn"))
        return CONTENTS_CURRENT_DOWN;
	
    if (name[0] == '!')
        return CONTENTS_WATER;
	
    if (!strcmpi(name, "origin"))
        return CONTENTS_ORIGIN;
	
    if (!strcmpi(name, "clip"))
        return CONTENTS_CLIP;
	
    if (!strcmpi(name, "hint"))
        return CONTENTS_HINT;
    if (!strcmpi(name, "skip"))
        return CONTENTS_HINT;
	
    if (!strcmpi(name, "translucent"))
        return CONTENTS_TRANSLUCENT;
	
    if (name[0] == '@')
        return CONTENTS_TRANSLUCENT;
	
    return CONTENTS_SOLID;
}



struct ParseInfo_t
{
	char * CurrentLine;
	long LineLen;
	long TokenStart;
	long TokenEnd;
	long LineNum;
	char * FileData;
	long   FileSize;
	FileType_t FileType;
};

// info about a file being converted
struct ConvertInfo_t
{
	ConvertInfo_t() : TextureHash(101) {}
	deTransform ScaleTForm;
	deTransform NormalTForm;
	deDouble Scale;
	deString2 TexDir;
	const char * filename;
	IdeRenderTexture* DefaultTex;
	ParseInfo_t parseInfo;
	deTHashString <long> TextureHash;
};

FileType_t IdentifyFileTypeFromPlaneDef(const ParseInfo_t& parseInfo);
deBoolean NextLine(ParseInfo_t& parseInfo);
void RewindToken(ParseInfo_t& info);
TextData_t ParseToken(ParseInfo_t& info,  deString2& buffer, TextData_t expectation = MAPData_None);
deBoolean ParseVertex(ParseInfo_t& info, deVec3d& Vertex, deString2& buffer, deBoolean ThrowFailure);
deBoolean ParseBracketTuple(ParseInfo_t& info, deVec3d& Axis, deDouble& Offset, deString2& buffer, deBoolean ThrowFailure);
void GetAxisBase(const deVec3d & Normal0, deVec3d & texS, deVec3d & texT);
BrushContent_t ParsePlane(ConvertInfo_t * pInfo, FullData_t * pData, BrushPlane_t * pPlane);
void ParseBrush(ConvertInfo_t * pInfo, FullData_t * pData, Entity_t * pEntity);
deBoolean ParseEntity(ConvertInfo_t * pInfo, FullData_t * pData, Entity_t * pEntity);
void ParseMAPFile(ConvertInfo_t * pInfo, FullData_t * pData);
char* ReadFile(ConvertInfo_t * pInfo, long & size);

deString2 GetEntityData(Entity_t* pEntity, deString2 name);
Entity_t* FindEntityNamed(FullData_t * pData, const deString2& name);

deBoolean PlaneIntersectionPoint(const BrushPlane_t& p1,
								 const BrushPlane_t& p2,
								 const BrushPlane_t& p3,
								 deVec3d& p)
{
	const deVec3d &n1 = p1.Normal;
	const deVec3d &n2 = p2.Normal;
	const deVec3d &n3 = p3.Normal;
	deDouble denom = Vec3d_Dot(n1, Vec3d_Cross(n2, n3));
	
	if (denom >= -Plane_Epsilon && denom <= Plane_Epsilon)
		return deFALSE;
	
	p = (Vec3d_Cross(n2, n3) * (-p1.Dist));
	p -= (Vec3d_Cross(n3, n1) * (p2.Dist));
	p -= (Vec3d_Cross(n1, n2) * (p3.Dist));
	p /= denom;
	
	return deTRUE;
}
	
void IntersectBrushFaces(FullData_t * pData, Brush_t * pBrush)
{
//#pragma todo (test IntersectBrushFaces further) // appears to be functional using test geometry
	int CCW_Winding = 1;

	int a, NumPlanes;
	deDouble Dist, TempVal;
	deVec3d Vertex;
	deVec3d Center;

	// need at least 4 planes to make a hull
	NumPlanes = pBrush->mPlanes.size();
	if (NumPlanes < 4)
	{
		LogExportMsg("Brush 0x%.8x found with fewer than 4 planes\n", pBrush);
		return;
	}

	// 1 = CCW, 0 = CW
	CCW_Winding = (CCW_Winding == 0) ? 0 : 1;

	deTArray<deVec3d> isectPoints; // stores the intersection points
	deTArray< deTArray<long> > Faces(NumPlanes); // remembers which points each plane caused
	const deTArray<BrushPlane_t>& Planes = pBrush->mPlanes;

	// cycle through all the planes, testing 3 at a time for collisions against each other
	for (a = 0; a < NumPlanes-2; ++a)
	{
		int b;
		for (b = a+1; b < NumPlanes-1; ++b)
		{
			int c;
			for (c = b+1; c < NumPlanes; ++c)
			{
				if (a != b && a != c && b != c)
				{
					// find intersection point of the 3 planes, if there is one
					if (PlaneIntersectionPoint(Planes[a], Planes[b], Planes[c], Vertex))
					{
						int d;
						deBoolean Legal = deTRUE;

						// test if the point found is outside of the hull
						for (d = 0; d < NumPlanes; ++d)
						{
							if (d == a || d == b || d == c)
								continue;
							const deVec3d& Normal = Planes[d].Normal;
							TempVal = Vec3d_Dot(Normal, Vertex);
							Dist = Planes[d].Dist;
							if (TempVal + Dist > Plane_Epsilon)
							{
								Legal = deFALSE;
								break;
							}
						}

						// add the point to all three plane entries
						if (Legal)
						{
							long newIdx = isectPoints.size();
							isectPoints.push_back(Vertex);
							Faces[a].push_back(newIdx);
							Faces[b].push_back(newIdx);
							Faces[c].push_back(newIdx);
						}
					}
				}
			}
		}
	}

	if (isectPoints.size() < 4)
	{
		LogExportMsg("Brush 0x%.8x found with fewer than 4 corners\n", pBrush);
		return;
	}

	pBrush->BBox.Min = isectPoints[0];
	pBrush->BBox.Max = isectPoints[0];
	for (a = 0; a < isectPoints.size(); ++a)
	{
		deGeometry::AABBAddPoint(pBrush->BBox, isectPoints[a]);
	}
	
	int index = 0;
	for (a = 0; a < NumPlanes; ++a)
	{
		if (Faces[a].size() > 0)
			++index;
	}
	pBrush->mFaces.Reserve(index);

	// now we have to put the vertices on each face in the correct winding order
	deDouble lowest;
	// cycle through all the faces that we now have, putting each one's vertices in order
	for (a = 0; a < NumPlanes; ++a)
	{
		deTArray <long>& VertArray = Faces[a];
		const int len = VertArray.size();
		if (len == 0)
			continue;

		// calculate the average center of the face
		Center = deZeroVec;
		deTArray<long>::iterator vIt = VertArray.begin();
		deTArray<long>::iterator stop = VertArray.end();
		for (; vIt != stop; ++vIt)
		{
			Center += isectPoints[*vIt];
		}
		Center /= (deDouble)len;

		int b;
		// cycle through all the vertices, swapping them as necessary to be "next in line"
		for (b = 0; b < len-1; b++)
		{
			deVec3d Normal;
			deVec3d Vertex2;
			Vertex = isectPoints[VertArray[b]]; // current point
			Vertex -= Center; // delta from center to current point
			Vec3d_Normalize(Vertex);
			// depending on the winding, the plane normal goes one way or the other
			if (CCW_Winding)
				Vec3d_Cross(Vertex, Planes[a].Normal, Normal);
			else
				Vec3d_Cross(Planes[a].Normal, Vertex, Normal);
			// splitting plane passing through current point and center
			// with normal perpendicular to normal of face
			Vec3d_Normalize(Normal);
			Dist = Vec3d_Dot(Normal, Center);

			// -1.0 = 180 degrees. +1.0 = 0 degrees. 0.0 = 90 degrees.
			lowest = -1.0;
			index = b;
			int c;
			// start at next point and go to last point, looking for closest angle that's in the right geometric order
			for (c = b+1; c < len; ++c)
			{
				// make sure that the vertex we're testing is on the correct side of the splitting plane
				TempVal = Vec3d_Dot(Normal, isectPoints[VertArray[c]]) - Dist;
				if (TempVal <= 0)
					continue;
				// calculate the delta from tested point to center, to find angle between it and current point
				Vertex2 = isectPoints[VertArray[c]];
				Vertex2 -= Center;
				Vec3d_Normalize(Vertex2);
				// dot product of 2 normalized vectors gives cosine of angle between them
				TempVal = Vec3d_Dot(Vertex, Vertex2);
				// yeah, it's called "lowest" but the dot product is bigger when the angle is smaller
				if (TempVal > lowest)
				{
					// record the new low
					lowest = TempVal;
					index = c;
				}
			}
			// swap em if the one found isn't already in place
			if (index != b+1)
			{
				deSwap(VertArray[index], VertArray[b+1]);
			}
		}

		deTArray<Face_t>::iterator faceIt = pBrush->mFaces.IncrementSize();
		faceIt->mTexture = Planes[a].Texture;
		faceIt->mVertices.resize(len);
		faceIt->Normal = Planes[a].Normal;
		for (b = 0; b < len; ++b)
		{
			// grab a point on the face
			Center = isectPoints[VertArray[b]];
			faceIt->mVertices[b].Pos = Center;

			// calculate the dot product of the current vertex (Center) and the appropriate texture axis normal
			deTexCoord2 coord;
			coord.u = (deFloat)Vec3d_Dot(Center, Planes[a].Axes[0]);
			coord.v = (deFloat)Vec3d_Dot(Center, Planes[a].Axes[1]);
			
			// divide by scale
			coord.u /= Planes[a].Scales[0];
			coord.v /= Planes[a].Scales[1];
			// add offset
			coord.u += Planes[a].Offsets[0];
			coord.v += Planes[a].Offsets[1];
			
			// record data
			faceIt->mVertices[b].TexCoord = coord;
		}
	}
}

void ThrowParseError(const ParseInfo_t& parseInfo, const char* expected, const char* got)
{
	deString error;
	error.Format("Position %d.%d: expected '%s', got '%s'", parseInfo.LineNum, parseInfo.TokenEnd, expected, got);
	throw mapException(error);
}

void RewindToken(ParseInfo_t& parseInfo)
{
	if (parseInfo.TokenEnd <= parseInfo.TokenStart)
		return;
	parseInfo.TokenEnd = parseInfo.TokenStart;
}

// grab some data and decide what it is
TextData_t ParseToken(ParseInfo_t& parseInfo,
					  deString2& buffer,
					  TextData_t expectation)
{
	TextData_t RetVal;
	int k;
	char * CurrentPos = parseInfo.CurrentLine;
	long DataStart, DataEnd;

	RetVal = expectation;

	while (1)
	{
		// eliminate starting whitespace
		for (k = parseInfo.TokenEnd; k < parseInfo.LineLen; ++k)
		{
			if (CurrentPos[k] != ' ' && CurrentPos[k] != '\t' && CurrentPos[k] != '\r')
			{
				break;
			}
		}
		// start new line if necessary
		if (k == parseInfo.LineLen)
		{
			parseInfo.CurrentLine += k+1;
			if (!NextLine(parseInfo))
				return MAPData_None;
			k = parseInfo.TokenEnd;
			CurrentPos = parseInfo.CurrentLine;
			continue;
		}
		// munch comments
		if ((CurrentPos[k] == '/') && (k+1 < parseInfo.LineLen) && (CurrentPos[k+1] == '/'))
		{
			for (k += 2; k < parseInfo.LineLen && CurrentPos[k] != '\n'; ++k)
			{}
			if (k >= parseInfo.FileSize)
				return MAPData_None;
			parseInfo.CurrentLine += k+1;
			NextLine(parseInfo);
			k = parseInfo.TokenEnd;
			CurrentPos = parseInfo.CurrentLine;
		}
		// different comment style
		if (CurrentPos[k] == ';')
		{
			for (k += 1; k < parseInfo.LineLen && CurrentPos[k] != '\n'; ++k)
			{}
			if (k >= parseInfo.FileSize)
				return MAPData_None;
			parseInfo.CurrentLine += k+1;
			NextLine(parseInfo);
			k = parseInfo.TokenEnd;
			CurrentPos = parseInfo.CurrentLine;
		}
		else
			break;
	}

	parseInfo.TokenStart = k;
	DataStart = k;

	deBoolean InQuote = deFALSE;
	// read data
	for (; k < parseInfo.LineLen; ++k)
	{
		switch (CurrentPos[k])
		{
		case '\r':
		case '\n':
			DataEnd = k;
			goto loop_out;
		case ' ':
		case '\t':
			if (!InQuote)
			{
				DataEnd = k;
				goto loop_out;
			}
			break;
		case '"':
			if (InQuote)
			{
				InQuote = deFALSE;
				DataEnd = k;
				++k;
				goto loop_out;
			}
		default:
			break;
		}
		if (RetVal == MAPData_None)
		{
			switch (CurrentPos[k])
			{
			case '(': RetVal = MAPData_OpenParen;
				++k; DataEnd = k; goto loop_out;
			case ')': RetVal = MAPData_CloseParen;
				++k; DataEnd = k; goto loop_out;
			case '[': RetVal = MAPData_OpenBracket;
				++k; DataEnd = k; goto loop_out;
			case ']': RetVal = MAPData_CloseBracket;
				++k; DataEnd = k; goto loop_out;
			case '{': RetVal = MAPData_OpenBrace;
				++k; DataEnd = k; goto loop_out;
			case '}': RetVal = MAPData_CloseBrace;
				++k; DataEnd = k; goto loop_out;
			case '"': RetVal = MAPData_Quote;
				DataStart = k+1; InQuote = deTRUE; break;
			case '.': RetVal = MAPData_Num; break; // decimal point
			case '-': RetVal = MAPData_Num; break; // negative number
			default:
				if (isdigit(CurrentPos[k]))
					RetVal = MAPData_Num;
				else
					RetVal = MAPData_Other;
				break;
			}
		}
	}
loop_out:
	parseInfo.TokenEnd = k;

	buffer.resize(DataEnd - DataStart);
	for (k = DataStart; k < DataEnd; ++k)
	{
		buffer.set_at(k - DataStart, CurrentPos[k]);
	}
	
	return RetVal;
}

// read the values of a vertex entry (3 floats)
deBoolean ParseVertex(ParseInfo_t& parseInfo, 
							 deVec3d& Vertex, 
							 deString2& buffer,
							 deBoolean ThrowFailure)
{
	try
	{
		if (MAPData_OpenParen != ParseToken(parseInfo, buffer))
			throw mapException();

		if (MAPData_Num != ParseToken(parseInfo, buffer))
			throw mapException();
		Vertex.x = atof(buffer.const_str());

		if (MAPData_Num != ParseToken(parseInfo, buffer))
			throw mapException();
		Vertex.y = atof(buffer.const_str());

		if (MAPData_Num != ParseToken(parseInfo, buffer))
			throw mapException();
		Vertex.z = atof(buffer.const_str());

		if (MAPData_CloseParen != ParseToken(parseInfo, buffer))
			throw mapException();
	}
	catch (mapException e)
	{
		if (!ThrowFailure)
			return deFALSE;
		ThrowParseError(parseInfo, "( x y z )", buffer.const_str());
	}

	return deTRUE;
}

// read the values inside some brackets [4 floats]
deBoolean ParseBracketTuple(ParseInfo_t& parseInfo, 
								   deVec3d& Axis, 
								   deDouble& Offset, 
								   deString2& buffer,
								   deBoolean ThrowFailure)
{
	try
	{
		if (MAPData_OpenBracket != ParseToken(parseInfo, buffer))
			throw mapException();
		
		if (MAPData_Num != ParseToken(parseInfo, buffer))
			throw mapException();
		Axis.x = atof(buffer.const_str());
		
		if (MAPData_Num != ParseToken(parseInfo, buffer))
			throw mapException();
		Axis.y = atof(buffer.const_str());
		
		if (MAPData_Num != ParseToken(parseInfo, buffer))
			throw mapException();
		Axis.z = atof(buffer.const_str());
		
		if (MAPData_Num != ParseToken(parseInfo, buffer))
			throw mapException();
		Offset = atof(buffer.const_str());
		
		if (MAPData_CloseBracket != ParseToken(parseInfo, buffer))
			throw mapException();
	}
	catch (mapException e)
	{
		if (!ThrowFailure)
			return deFALSE;
		ThrowParseError(parseInfo, "[ a b c d ]", buffer.const_str());
	}
	
	return deTRUE;
}

// algorithm from Q3R as provided by Timothee Besset
void GetAxisBase(const deVec3d & Normal0, deVec3d & texS, deVec3d & texT)
{
	deVec3d Normal;
	deDouble RotY, RotZ;
	
	Normal = Normal0;
	// do some cleaning
	Vec3d_Squeeze(Normal);
	RotY = -atan2(Normal.y,sqrt(Normal.x*Normal.x+Normal.z*Normal.z));
	RotZ = atan2(Normal.x,Normal.z);
	// rotate (0,1,0) and (0,0,1) to compute texS and texT
	texS.z = -sin(RotZ);
	texS.x = cos(RotZ);
	texS.y = 0.0;
	Vec3d_Squeeze(texS);
	// the texT vector is along -Z ( T texture coorinates axis )
	texT.z = -sin(RotY);
	texT.x = texT.z;
	texT.z *= (texS.x);
	texT.x *= -(texS.z);
	texT.y = -cos(RotY);
	Vec3d_Squeeze(texT);
}

/*
void GetAxisBase(const deVec3d & Normal0, deVec3d & texS, deVec3d & texT)
{
	deVec3d Normal;
	deDouble RotY, RotZ;

	Normal = Normal0;
	// do some cleaning
	Vec3d_Squeeze(Normal);
	RotY = -atan2(Normal.Z,sqrt(Normal.Y*Normal.Y+Normal.X*Normal.X));
	RotZ = atan2(Normal.Y,Normal.X);
	// rotate (0,1,0) and (0,0,1) to compute texS and texT
	texS.X = -sin(RotZ);
	texS.Y = cos(RotZ);
	texS.Z = 0.0;
	Vec3d_Squeeze(texS);
	// the texT vector is along -Z ( T texture coorinates axis )
	texT.X = -sin(RotY);
	texT.Y = texT.X;
	texT.X *= (texS.Y);
	texT.Y *= -(texS.X);
	texT.Z = -cos(RotY);
	Vec3d_Squeeze(texT);
}

// from 
void CoordShift(const deVec3d & P, const deVec3d & texO, const deVec3d & texS, const deVec3d & texT, deVec3d & Result)
{
	deVec3d D;
	D = P;
	D -= texO;
	Result.x = Vec3d_Dot(D, texS);
	Result.y = Vec3d_Dot(D, texT);
	Result.z = 0.0;
}

void InvertDenom(const deVec3d & P0, const deVec3d & P1, const deVec3d & P2, deDouble & Result)
{
	Result = -P2.x*P1.y + P2.x*P0.y + P2.y*P1.x
		    - P2.y*P0.x + P0.x*P1.y - P0.y*P1.x;
}

// based on information about Q3R brush primitives format
// provided by Timothee Besset
void GetPXPY(const deVec3d & Normal, deVec3d V[3], deVec3d & PX, deVec3d & PY, deDouble Dist)
{
	deVec3d texS, texT, texO, P0, P1, P2;
	deDouble D;
	//	get basis vectors for affine plane of face
	GetAxisBase(Normal, texS, texT);
	//	origin of plane's coordindate system
	texO = Normal;
	texO *= Dist;
	//	get the texture points.  V has been provided by
	//	Face.GetThreePointsUserTex, so if texture scale
	//	is 1:1, (P1-P0) will be texture width, P2-P0
	//	texture height.  In written out map, for 1:1
	//	texture scale these #'s will be 128
	 
	P0 = V[0];
	P1 = V[1];
	P2 = V[2];
   
	//	redo threepoints in plane coordinate system }
	CoordShift(P0, texO, texS, texT, P0);
	CoordShift(P1, texO, texS, texT, P1);
	CoordShift(P2, texO, texS, texT, P2);
   
	//	Now solve the equation system produced
	//	where PX, PY are to be row 1 and row 2
	//	of the homogenous matrix that will map
	//	(0,0), (1,0) and (0,-1) onto P0, P1, P2
	//	respectively (note sign swap)
   
	InvertDenom(P0, P1, P2, D);
  
	PX.x = (P2.y - P0.y)/D;
	PX.y = (P0.x - P2.x)/D;
	PX.z = (-P2.y*P0.x + P2.x*P0.y)/D;
	PY.x = (P1.y - P0.y)/D;
	PY.y = (P0.x - P1.x)/D;
	PY.z = (-P0.x*P1.y + P0.y*P1.x)/D;
}
*/

deString2 GetEntityData(Entity_t* pEntity, deString2 name)
{
	deTArray<Entity_t::entity_var_t>::iterator it = pEntity->mVars.begin();
	for (; it != pEntity->mVars.end(); ++it)
	{
		if (it->mName == name)
			return it->mValue;
	}
	return deString2();
}

Entity_t* FindEntityNamed(FullData_t * pData, const deString2& name)
{
	deString2 classname = "classname";
	deTList<Entity_t>::iterator it = pData->mEntities.begin();
	for (; it != pData->mEntities.end(); ++it)
	{
		if (name == GetEntityData(&*it, classname))
			return &*it;
	}
	return NULL;
}

// read a line from the MAP file and add it to a brush
BrushContent_t ParsePlane(ConvertInfo_t * pInfo, FullData_t * pData, BrushPlane_t * pPlane)
{
	deString2 buffer;
	IdeBitmapProxy * BMP;
	IdeRenderTexture * TextureState;
	deString2 TexName;
	deVec3d verts[3];
	deVec3d Normal;
	deVec3d Axes[2];
	deDouble Offsets[2];
	deDouble Scales[2];
	BrushContent_t contents = CONTENTS_SOLID;
	int TexWidth, TexHeight;
	int k;

	TexWidth = 1;
	TexHeight = 1;

	// grab the plane vertices
	ParseVertex(pInfo->parseInfo, verts[0], buffer, deTRUE);
	ParseVertex(pInfo->parseInfo, verts[1], buffer, deTRUE);
	ParseVertex(pInfo->parseInfo, verts[2], buffer, deTRUE);
	// transform them into the space we want them in
	verts[1] -= verts[0];
	verts[2] -= verts[0];
	Vec3d_Cross(verts[2], verts[1], Normal);
	verts[1] += verts[0];
	verts[2] += verts[0];
	Vec3d_Normalize(Normal);
	pPlane->Dist = -pInfo->Scale * Vec3d_Dot(Normal, verts[0]);
	pInfo->NormalTForm.Transform(Normal, pPlane->Normal);

	if (pInfo->parseInfo.FileType == MAPFILE_Undecided)
	{
		pInfo->parseInfo.FileType = IdentifyFileTypeFromPlaneDef(pInfo->parseInfo);
	}
	
	if (pInfo->parseInfo.FileType == MAPFILE_Q3) // Brush Primitives
	{
		// load specific texture coord information
		if (MAPData_OpenParen != ParseToken(pInfo->parseInfo, buffer))
			ThrowParseError(pInfo->parseInfo, "(", buffer.const_str());
		ParseVertex(pInfo->parseInfo, Axes[0], buffer, deTRUE);
		ParseVertex(pInfo->parseInfo, Axes[1], buffer, deTRUE);
		if (MAPData_CloseParen != ParseToken(pInfo->parseInfo, buffer))
			ThrowParseError(pInfo->parseInfo, ")", buffer.const_str());

		// texture name is last in q3 format
		if (MAPData_Other != ParseToken(pInfo->parseInfo, buffer, MAPData_Other))
			ThrowParseError(pInfo->parseInfo, "texname", buffer.const_str());
		contents = TextureContents(buffer.const_str());
		TexName = pInfo->TexDir + buffer;

		// now process the matrix so that we can get some texture axes we can use
		deDouble Denom;
		deVec3d TexS, TexT, Tex0;
		deVec3d P0, P1, P2;
		deTransform TexMat;
		Denom = Axes[0].X*Axes[1].Y-Axes[0].Y*Axes[1].X;
		P0.X = (-Axes[0].Z*Axes[1].Y+Axes[0].Y*Axes[1].Z)/Denom;			//-a13*a22+a12*a23
		P0.Y = -(Axes[0].X*Axes[1].Z-Axes[0].Z*Axes[1].X)/Denom;			//-(a11*a23-a13*a21)
		P0.Z = 0.0;
		P1.X = (-Axes[0].Z*Axes[1].Y+Axes[1].Y+Axes[0].Y*Axes[1].Z)/Denom;	//-a13*a22+a22+a12*a23
		P1.Y = -(Axes[0].X*Axes[1].Z-Axes[0].Z*Axes[1].X+Axes[1].X)/Denom;	//-(a11*a23-a13*a21+a21)
		P1.Z = 0.0;
		P2.X = (Axes[0].Y*Axes[1].Z+Axes[0].Y-Axes[0].Z*Axes[1].Y)/Denom;	//a12*a23+a12-a13*a22
		P2.Y = -(-Axes[0].Z*Axes[1].X+Axes[0].X*Axes[1].Z+Axes[0].X)/Denom;	//-(-a13*a21+a11*a23+a11)
		P2.Z = 0.0;
		// Convert to map space
		GetAxisBase(Normal, TexS, TexT);
		Tex0 = Normal;
		Tex0 *= Vec3d_Dot(verts[0], Normal);
		TexMat.SetRight(TexS);
		TexMat.SetUp(TexT);
		TexMat.Transform(P0, P0);
		P0 += Tex0;
		TexMat.Transform(P1, P1);
		P1 += Tex0;
		TexMat.Transform(P2, P2);
		P2 += Tex0;

		Axes[0] = (P1 - P0)*(1/Vec3d_Dist(verts[1], verts[0]));
		Axes[1] = (P2 - P0)*(1/Vec3d_Dist(verts[2], verts[0]));
		Axes[0].y = -Axes[0].y;
		Axes[1].y = -Axes[1].y;
	   
		Offsets[0] = pInfo->Scale * P0.x;
		Offsets[1] = pInfo->Scale * -P0.y;
		Vec3d_Normalize(Axes[0]);
		Vec3d_Normalize(Axes[1]);
		Scales[0] = pInfo->Scale;
		Scales[1] = pInfo->Scale;
	}
	else
	{
		// texture name is first in these ones
		if (MAPData_Other != ParseToken(pInfo->parseInfo, buffer, MAPData_Other))
			ThrowParseError(pInfo->parseInfo, "texname", buffer.const_str());
		contents = TextureContents(buffer.const_str());
		TexName = pInfo->TexDir + buffer;
		
		// load specific texture coord information
		if (pInfo->parseInfo.FileType == MAPFILE_Q1) // Classic Quake
		{
			// x,y offset
			// rotation
			// x,y scale
			deDouble TexVals[5];

			for (k = 0; k < 5; ++k)
			{
				if (MAPData_Num != ParseToken(pInfo->parseInfo, buffer))
					ThrowParseError(pInfo->parseInfo, "ox oy rot sx sy", buffer.const_str());
				TexVals[k] = atof(buffer.const_str());
			}

			k = 0;
			if (fabs(Normal.x) < fabs(Normal.y))
				k = 1;
			if (fabs(Vec3d_GetElement(Normal, k)) < fabs(Normal.z))
				k = 2;

			switch (k)
			{
			case 0:
				Axes[1] = -deVecY;
				Axes[0] = deVecZ;
				break;
			case 1:
				Axes[0] = deVecX;
				Axes[1] = deVecZ;
				break;
			case 2:
				Axes[0] = deVecX;
				Axes[1] = -deVecY;
				break;
			}

			Offsets[0] = TexVals[0];
			Offsets[1] = TexVals[1];
			Scales[0] = pInfo->Scale * TexVals[3];
			Scales[1] = pInfo->Scale * TexVals[4];
		}
		else if (pInfo->parseInfo.FileType == MAPFILE_HL) // Valve 220
		{ 
			// U axis
			ParseBracketTuple(pInfo->parseInfo, Axes[0], Offsets[0], buffer, deTRUE);
			// V axis
			ParseBracketTuple(pInfo->parseInfo, Axes[1], Offsets[1], buffer, deTRUE);

			pInfo->NormalTForm.TransformArray(Axes, Axes, 2);

			// unused value
			if (MAPData_Num != ParseToken(pInfo->parseInfo, buffer))
				ThrowParseError(pInfo->parseInfo, "dummyval", buffer.const_str());

			// U scale
			if (MAPData_Num != ParseToken(pInfo->parseInfo, buffer))
				ThrowParseError(pInfo->parseInfo, "uscale", buffer.const_str());
			Scales[0] = pInfo->Scale * atof(buffer.const_str());

			// V scale
			if (MAPData_Num != ParseToken(pInfo->parseInfo, buffer))
				ThrowParseError(pInfo->parseInfo, "vscale", buffer.const_str());
			Scales[1] = pInfo->Scale * atof(buffer.const_str());
		}
		else
			throw mapException("Unknown File Format");
	}

	{
		long* pTexNum;
		pTexNum = pInfo->TextureHash.FindElement(TexName.const_str());
		if (pTexNum)
		{
			TextureState = pData->mTextures[*pTexNum];
			pPlane->Texture = *pTexNum;
		}
		else
			TextureState = NULL;
	}
	if (TextureState == NULL)
	{
		IdeResourceBase * rsc;
		long texnamelen = TexName.size();
		deString2 AddedExt;
		AddedExt = TexName;
		AddedExt.reserve(texnamelen + 4);
		int i;
		const char* exts[] = {".bmp", ".png", ".tga"};
		for (i = 0; i < sizeof(exts)/sizeof(exts[0]); ++i)
		{
			AddedExt += exts[i];
			rsc = IdeResourceManager_GetManager()->GetResource(AddedExt.const_str(), NULL);
			if (rsc)
			{
				BMP = IdeBitmap_CreateProxy(rsc);
				TextureState = IdeRenderState_CreateRenderTexture();
//				TextureState->SetWorldID(pData->mWorldID);
				TextureState->Lock();
				TextureState->SetBitmap(0, BMP);
				if (BMP)
				{
					BMP->SettingSavePixels(deTRUE);
//					BMP->SetWorldID(pData->mWorldID);
					BMP->Release();
				}
				TextureState->SetColorArg(0, 1, IdeRenderTexture::TEXTUREARG_TEXTURE);
				TextureState->SetColorArg(0, 2, IdeRenderTexture::TEXTUREARG_DIFFUSE);
				TextureState->SetColorOperation(0, IdeRenderTexture::TEXTUREOP_MODULATE);
				TextureState->Unlock();
				long TexNum = pData->mTextures.size();
				if (!pData->mTextures.PushBack(TextureState))
				{
					deString error;
					error.Format("error adding texture '%s'", AddedExt.const_str());
					throw mapException(error);
				}
				pInfo->TextureHash.AddElement(TexNum, TexName.const_str());
				pPlane->Texture = TexNum;
				break;
			}
			AddedExt.Trim(texnamelen);
		}
		if (!rsc)
		{
			// resource manager spits out a message too
			LogExportMsg("Failed to load texture '%s'\n", TexName.const_str());
			TextureState = pInfo->DefaultTex;
			int x;
			long TexNum;
			for (x = 0; x < pData->mTextures.size(); ++x)
			{
				if (pData->mTextures[x] == TextureState)
				{
					break;
				}
			}
			TexNum = x;
			if (x == pData->mTextures.size())
			{
				TexNum = pData->mTextures.size();
				pData->mTextures.PushBack(TextureState);
				TextureState->Claim();
			}
			pPlane->Texture = x;
			pInfo->TextureHash.AddElement(TexNum, TexName.const_str());
		}
	}
	/*
	else
	{
		TextureState->Claim();
	}
	*/

	TexWidth = 1;
	TexHeight = 1;
	for (k = 0; k < TEXTURESTAGE_COUNT; ++k)
	{
		BMP = TextureState->GetBitmap(k);
		if (BMP)
		{
			TexWidth = BMP->GetWidth();
			TexHeight = BMP->GetHeight();
			break;
		}
	}

	Offsets[0] /= TexWidth;
	Offsets[1] /= TexHeight;
	Scales[0] *= TexWidth;
	Scales[1] *= TexHeight;
	// get rid of super-offsets, we only need floating-point
	Offsets[0] -= (int)Offsets[0];
	Offsets[1] -= (int)Offsets[1];

	pPlane->Axes[0] = Axes[0];
	pPlane->Axes[1] = Axes[1];
	pPlane->Offsets[0] = (deFloat)Offsets[0];
	pPlane->Offsets[1] = (deFloat)Offsets[1];
	pPlane->Scales[0] = (deFloat)Scales[0];
	pPlane->Scales[1] = (deFloat)Scales[1];

	return contents;
}

void ParseBrush(ConvertInfo_t * pInfo, FullData_t * pData, Entity_t * pEntity)
{
	deString2 buffer;
	TextData_t token;

	if (pInfo->parseInfo.FileType == MAPFILE_Undecided)
	{
		// try to decide what format of MAP file we're reading
		if (GetEntityData(pEntity, "mapversion") == "220")
		{
			// Half-Life uses a "mapversion" "220" entity variable
			pInfo->parseInfo.FileType = MAPFILE_HL;
		}
		else
		{
			// quake3 has text saying "brushDef" at the beginning of a brush
			token = ParseToken(pInfo->parseInfo, buffer);
			buffer.SetCaseSensitivity(deFALSE);
			if (token == MAPData_Other && buffer == "brushDef")
				pInfo->parseInfo.FileType = MAPFILE_Q3;
			RewindToken(pInfo->parseInfo);
		}
	}

	Brush_t* pBrush = &*(pEntity->mBrushes.push_back());
	pBrush->Invisible = deFALSE;

	int BraceDepth = 1;
	while (1)
	{
		token = ParseToken(pInfo->parseInfo, buffer);
		switch (token)
		{
		case MAPData_OpenParen:
			{
				RewindToken(pInfo->parseInfo);
				deTArray<BrushPlane_t>::iterator plane = pBrush->mPlanes.IncrementSize();
				BrushContent_t contents = ParsePlane(pInfo, pData, &*plane);
				switch(contents)
				{
				case CONTENTS_SOLID:
				case CONTENTS_SKY:
					break;
				default:
					pBrush->Invisible = deTRUE;
					break;
				}
			}
			break;
		case MAPData_OpenBrace:
			BraceDepth += 1;
			break;
		case MAPData_CloseBrace:
			BraceDepth -= 1;
			if (BraceDepth == 0)
				goto loop_out;
			break;
		default:
			ThrowParseError(pInfo->parseInfo, "( or }", buffer.const_str());
		}
	}
loop_out:
	IntersectBrushFaces(pData, pBrush);
}

deBoolean ParseEntity(ConvertInfo_t * pInfo, FullData_t * pData, Entity_t * pEntity)
{
	deString2 buffer;

	TextData_t token = ParseToken(pInfo->parseInfo, buffer);
	if (token == MAPData_None)
		return deFALSE;
	if (token != MAPData_OpenBrace)
		ThrowParseError(pInfo->parseInfo, "{", buffer.const_str());
	while (1)
	{
		int k;
		k = pInfo->parseInfo.CurrentLine - pInfo->parseInfo.FileData + pInfo->parseInfo.TokenEnd;
		if (k >= pInfo->parseInfo.FileSize)
			return deFALSE;
		token = ParseToken(pInfo->parseInfo, buffer);
		switch (token)
		{
		case MAPData_Quote:
			{
				// variable name
				deTArray<Entity_t::entity_var_t>::iterator it = pEntity->mVars.push_back(Entity_t::entity_var_t(buffer));
				token = ParseToken(pInfo->parseInfo, buffer);
				it->mValue = buffer;
				if (it->mName == "classname")
				{
					LogExportMsg("Reading entity '%s'\n", it->mValue.const_str());
				}
				break;
			}
		case MAPData_OpenBrace:
			//RewindToken(pInfo->parseInfo);
			ParseBrush(pInfo, pData, pEntity);
			break;
		case MAPData_CloseBrace:
			goto loop_out;
		default:
			ThrowParseError(pInfo->parseInfo, "\" or {", buffer.const_str());
		}
	}
loop_out:
	if (MAPData_None == ParseToken(pInfo->parseInfo, buffer))
		return deFALSE;
	RewindToken(pInfo->parseInfo);
	return deTRUE;
}

void ParseMAPFile(ConvertInfo_t * pInfo, FullData_t * pData)
{
	if (!pInfo)
		throw mapException("ReadMAPFile: Paramater 'pInfo' was NULL");
	if (!pData)
		throw mapException("ReadMAPFile: Paramater 'pData' was NULL");
	if (!pInfo->filename)
		throw mapException("ReadMAPFile: Paramater 'pInfo->filename' was NULL");
	
	int			k;
	pInfo->parseInfo.FileData = NULL;

	try 
	{
		pInfo->parseInfo.FileData = ReadFile(pInfo, pInfo->parseInfo.FileSize);
		
		deString2 TexDirName(pInfo->filename);
		TexDirName.Replace('\\', '/');
		k = TexDirName.Find('/', 0, deString2::search_backwards);
		TexDirName.Trim(k+1);
		TexDirName += "textures/";
		pInfo->TexDir = TexDirName;
		
		pInfo->TextureHash.RemoveAllElements();
		k = 0;
		pInfo->parseInfo.CurrentLine = pInfo->parseInfo.FileData;
		pInfo->parseInfo.LineNum = 0;
		pInfo->parseInfo.FileType = MAPFILE_Undecided;
		NextLine(pInfo->parseInfo);
		while (1)
		{
			deTList<Entity_t>::iterator eIt = pData->mEntities.push_back(Entity_t());
			// do nothing here, work is done in ParseEntity
			if (!ParseEntity(pInfo, pData, &*eIt))
				break;
		}
	}
	catch (mapException e)
	{
		delete[] pInfo->parseInfo.FileData;
		pInfo->parseInfo.FileData = NULL;
		throw e;
	}
	delete[] pInfo->parseInfo.FileData;
	pInfo->parseInfo.FileData = NULL;
}	

// reads the data out of a file and appends a single newline character at the end
char* ReadFile(ConvertInfo_t * pInfo, long & size)
{
	IdeFileSystem*	FS = NULL;
	IdeFile*		pFile = NULL;
	char*			FileData = NULL;
	
	size = 0;
	
	try
	{
		// create our file
		FS = IdeFileSystem_CreateFSReal();
		
		if (!FS)
		{
			deString error;
			error.Format("Could not open local filesystem to read file '%s'", pInfo->filename);
			throw mapException(error);
		}
		
		// open the requested filename
		pFile = FS->Open(pInfo->filename, deFile_Open_Existing | deFile_Open_Read);
		if (!pFile)
		{
			deString error;
			error.Format("Could not open file '%s'", pInfo->filename);
			throw mapException(error);
		}
		
		// grab the size
		long k;
		k = pFile->GetPosition();
		pFile->SetPosition(0, deFile_Seek_End);
		size = pFile->GetPosition() - k;
		pFile->SetPosition(k, deFile_Seek_Start);
		FileData = new char[size+1];
		
		// grab the data
		if (size != pFile->Read(FileData, size))
		{
			deString error;
			error.Format("Could not read data for file '%s'", pInfo->filename);
			throw mapException(error);
		}
		// make sure the file ends in a newline!!!
		FileData[size] = '\n';
	}
	catch (mapException e)
	{
		if (pFile)
		{
			pFile->Close();
			pFile->Release();
		}
		if (FS)
			FS->Release();
		throw e;
	}	

	if (pFile)
	{
		pFile->Close();
		pFile->Release();
	}
	if (FS)
		FS->Release();
	return FileData;
}

deBoolean NextLine(ParseInfo_t& parseInfo)
{
	int k, DataLeft;
	DataLeft = parseInfo.FileSize - (parseInfo.CurrentLine - parseInfo.FileData);
	if (DataLeft <= 0)
		return deFALSE;
	for (k = 0; k < DataLeft; ++k)
	{
		if (parseInfo.CurrentLine[k] == '\n')
		{
			break;
		}
	}
	parseInfo.LineLen = k;
	parseInfo.TokenEnd = 0;
	parseInfo.LineNum += 1;
	return deTRUE;
}

// decide what type of MAP file format we're reading - Quake, Half-Life, Quake3
FileType_t IdentifyFileTypeFromPlaneDef(const ParseInfo_t& parseInfo)
{
	const char* CurrentLine = parseInfo.CurrentLine;
	deBoolean CommentStarted;
	int OpenParenNum, OpenBracketNum;
	int CloseParenNum, CloseBracketNum;
	int k, DataLeft;
	
	DataLeft = parseInfo.FileSize - (parseInfo.CurrentLine - parseInfo.FileData);
	OpenParenNum = 0;
	CloseParenNum = 0;
	OpenBracketNum = 0;
	CloseBracketNum = 0;
	CommentStarted = deFALSE;
	
	for (k = 0; k < DataLeft; ++k)
	{
		if (CurrentLine[k] == '\n')
		{
			break;
		}
		else if (CurrentLine[k] == '/')
		{
			if (CommentStarted)
				break;
			CommentStarted = deTRUE;
		}
		else
		{
			CommentStarted = deFALSE;
			switch (CurrentLine[k])
			{
			case ' ':
			case '\t':
			case '\r':
				break;
			case '(':
				++OpenParenNum; break;
			case ')':
				++CloseParenNum; break;
			case '[':
				++OpenBracketNum; break;
			case ']':
				++CloseBracketNum; break;
			}
		}
	}
	
	if (OpenParenNum != CloseParenNum)
		ThrowParseError(parseInfo, "matching parentheses", "unmatched parentheses");
	else if (OpenBracketNum != CloseBracketNum)
		ThrowParseError(parseInfo, "matching brackets", "unmatched brackets");
	else if (OpenBracketNum > 0)
		return MAPFILE_HL;	// only HL format uses brackets
	else if (OpenParenNum > 3)
		return MAPFILE_Q3;	// Q3 format uses more parentheses than normal
	return MAPFILE_Q1;	
}

void LoadMAP(const char* filename, deDouble Scale, IdeRenderTexture * DefaultTex, 
			 bool doUnion, bool doWeld, FullData_t& outData)
{
	ConvertInfo_t MapInfo;
	outData.mEntities.EmptyList();
	outData.mTextures.resize(0);

	{
		// Quake3 levels are stored like a 3DS file... Z is up or down or something
		// we use Y as up, so we need to flip it around
//		deVec3d tempvec;
		// convert Y to Z
		MapInfo.ScaleTForm.R = deVecX;
		MapInfo.ScaleTForm.U = deVecZ;
		MapInfo.ScaleTForm.I = deVecY;
		// scale
		MapInfo.ScaleTForm.ApplyScaling(Scale);
		MapInfo.ScaleTForm.SqueezeVectors();
		/*
		// switch from right-handed to left-handed
		MapInfo.ScaleTForm.GetLeft(tempvec);
		tempvec = -tempvec;
		MapInfo.ScaleTForm.SetLeft(tempvec);
		*/
		// get a normal-transforming one (can't do scaling, just rotation)
		MapInfo.NormalTForm = MapInfo.ScaleTForm;
		MapInfo.NormalTForm.OrthoNormalize();
		MapInfo.Scale = Scale;
	}

	MapInfo.DefaultTex = DefaultTex;
	
	MapInfo.filename = filename;
	ParseMAPFile(&MapInfo, &outData);
}

} // namespace deMapConverter
