///////////////////////////////////////////////////////////////////////////////
/// @file BrushOctree.cpp
///
/// @brief Brush Octree
///
/// @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 Jan 2003
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "BrushOctree.hpp"
#include "deFunctors.hpp"

static deBrushOctree blahOctree;

#pragma warning (push, 3)
void deBrushOctree::TEST()
{
	Clear();

	int i;
	u16 offset;
	deIndexedPoly *p1, *p2;

	deVec3d pos[7] = {{0,0,0},{2,0,0},{2,2,0},{0,2,0}, {1,1,-1},{2,1,-1},{2,1,1}};
	deVec3d norm[7] = {{0,0,-1},{0,0,-1},{0,0,-1},{0,0,-1}, {0,1,0},{0,1,0},{0,1,0}};
	deVertMat mat[7] = {{0,{0,0}},{0,{0,1}},{0,{1,1}},{0,{1,0}}, {0,{0,0}},{0,{1,0}},{0,{1,1}}};

	AddPolyGetRef(p1);
	AddPolyGetRef(p2);
	AddPositions(pos, 7, offset);
	AddNormals(norm, 7, offset);
	AddVertMats(mat, 7, offset);
	p1->Resize(4);
	p2->Resize(3);

	for (i = 0; i < 4; ++i)
	{
		p1->PosIndices[i] = i;
		p1->NormIndices[i]= i;
		p1->MatIndices[i] = i;
	}
		
	for (i = 0; i < 3; ++i)
	{
		p2->PosIndices[i] = i+4;
		p2->NormIndices[i]= i+4;
		p2->MatIndices[i] = i+4;
	}
	
	//Generate();

	MakePlane(p1);
	MakePlane(p2);
	deVec3d * ResultPair = pos;
	PolyPolyIntersect(p1, p2);
	if (PolyPlaneIntersect(p1->Normal, p1->Dist, p2, ResultPair))
	{
		deIndexedPoly *split1, *split2;
		m_SplittingPlane.Norm = p2->Normal;
		m_SplittingPlane.Dist = p2->Dist;
		SplitPoly(p1, split1, split2);
	}

	Clear();
}
#pragma warning (pop)

#define MAX_NODE_POLYS (15)
#define MAX_TREE_DEPTH (10)

deBrushOctree::deBrushOctree()
: m_SplitPosHash(23), m_SplitNormHash(23), m_SplitMatHash(23)
{
	m_Root = NULL;

#ifdef _DEBUG
	TEST();
#endif
}

deBrushOctree::~deBrushOctree()
{
	Clear();
	m_Root = NULL;
}

deBoolean deBrushOctree::AddPositions(deVec3d *VertArray, u16 NumVerts, u16 &Offset)
{
	int len = m_Positions.Length();
	DEBUG_EXP_RETURN(len+NumVerts < 65536, deFALSE);

	Offset = (u16)(len);
	m_Positions.Resize(len+NumVerts);

	if (!m_Positions.InsertArrayQuick(VertArray, Offset, NumVerts))
		DEBUGRETURN(deFALSE, "AddPositions: insertion into array failed");

	return deTRUE;
}

deBoolean deBrushOctree::AddNormals(deVec3d *VertArray, u16 NumVerts, u16 &Offset)
{
	int len = m_Normals.Length();
	DEBUG_EXP_RETURN(len+NumVerts < 65536, deFALSE);
	
	Offset = (u16)(len);
	m_Normals.Resize(len+NumVerts);
	
	if (!m_Normals.InsertArrayQuick(VertArray, Offset, NumVerts))
		DEBUGRETURN(deFALSE, "AddNormals: insertion into array failed");
	
	return deTRUE;
}

deBoolean deBrushOctree::AddVertMats(deVertMat *VertArray, u16 NumVerts, u16 &Offset)
{
	int len = m_VertMats.Length();
	DEBUG_EXP_RETURN(len+NumVerts < 65536, deFALSE);
	
	Offset = (u16)(len);
	m_VertMats.Resize(len+NumVerts);
	
	if (!m_VertMats.InsertArrayQuick(VertArray, Offset, NumVerts))
		DEBUGRETURN(deFALSE, "AddVertMats: insertion into array failed");
	
	return deTRUE;
}

deBoolean deBrushOctree::AddPolyGetRef(deIndexedPoly* & poly)
{
	// stick the poly into tha array
	long len;
	if (m_PolyRemoveList.Length() == 0)
	{
		if (!m_PolyArray.IncrementSizeQuick(deFALSE, len))
			return deFALSE;
		m_PolyArray[len] = new deIndexedPoly;
	}
	else
	{
		void * ptr = m_PolyRemoveList.GetNext(NULL, len);
		if (!ptr)
			return deFALSE;
		if (!m_PolyRemoveList.RemoveElement(ptr))
			return deFALSE;
	}
	// record that this poly hasn't been inserted into the tree yet
	if (!m_PolyAddList.AddElement(len))
		return deFALSE;
	poly = m_PolyArray[len];
	poly->PolyIndex = len;
	return deTRUE;
}

deBoolean deBrushOctree::AddPoly(deIndexedPoly * poly, u16 PosOffset, u16 NormOffset, u16 MatOffset)
{
	// stick the poly into tha array
	long len;
	if (m_PolyRemoveList.Length() == 0)
	{
		if (!m_PolyArray.IncrementSizeQuick(deFALSE, len))
			return deFALSE;
		m_PolyArray[len] = poly;
	}
	else
	{
		void * ptr = m_PolyRemoveList.GetNext(NULL, len);
		if (!ptr)
			return deFALSE;
		if (!m_PolyRemoveList.RemoveElement(ptr))
			return deFALSE;
	}
	// record that this poly hasn't been inserted into the tree yet
	if (!m_PolyAddList.AddElement(len))
		return deFALSE;
	deIndexedPoly * newpoly = m_PolyArray[len];
	newpoly->PolyIndex = len;
	if (PosOffset || NormOffset || MatOffset)
	{
		// apply the offsets if there are any
		s32 i;
		for (i = 0; i < poly->NumVerts; ++i)
		{
			// check for overflow (debug only)
			DE_ASSERT(newpoly->PosIndices[i] + PosOffset < 65536);
			DE_ASSERT(newpoly->NormIndices[i]+ NormOffset < 65536);
			DE_ASSERT(newpoly->MatIndices[i] + MatOffset < 65536);
			#pragma warning (push)
			#pragma warning (disable : 4244)
			newpoly->PosIndices[i] += PosOffset;
			newpoly->NormIndices[i]+= NormOffset;
			newpoly->MatIndices[i] += MatOffset;
			#pragma warning (pop)
		}
	}
	return deTRUE;
}

deBoolean deBrushOctree::GetPoly(deIndexedPoly* & poly, long PolyIndex)
{
	poly = m_PolyArray[PolyIndex];
	return deTRUE;
}

deBoolean deBrushOctree::RemovePoly(const deIndexedPoly * poly)
{
	{
		void * ptr;
		long index;
		ptr = m_PolyAddList.GetPrev(NULL, index);
		while (ptr)
		{
			if (index == poly->PolyIndex)
			{
				if (!m_PolyAddList.RemoveElement(ptr))
					return deFALSE;
				break;
			}
			ptr = m_PolyAddList.GetPrev(ptr, index);
		}
	}
	if (!m_PolyRemoveList.AddElement(poly->PolyIndex))
		return deFALSE;
	return deTRUE;
}

deBoolean deBrushOctree::Generate()
{
	void * ptr;
	long* PolyIndex;
	ptr = m_PolyAddList.GetNext(NULL, PolyIndex);
	while (ptr)
	{
		// the big thing - put the polygon into the tree
		if (!InsertPolyIntoTree(*PolyIndex))
			return deFALSE;

		ptr = m_PolyAddList.RemoveElementGetNext(ptr, PolyIndex);
	}

	return deTRUE;
}

deBoolean deBrushOctree::Clear()
{
	m_PolyArray.IterateAll(deDelPtrsFunctor<deIndexedPoly>());
	m_PolyArray.Resize(0);
	m_PolyAddList.EmptyList();
	m_PolyRemoveList.EmptyList();
	DestroyNode(m_Root);
	return deTRUE;
}

deBoolean deBrushOctree::GetPolysInBox(const deVec3d & Min, const deVec3d & Max, deTArray <deIndexedPoly*> &PolyArray, OctNode * node)
{
#pragma todo(unfinished method: GetPolysInBox)
	node->Min = Min;
	node->Max = Max;
	PolyArray[0];
	return deFALSE;
}

deBoolean deBrushOctree::GetAllPolys(deTArray <deIndexedPoly*>* &PolyArray)
{
	PolyArray = &m_PolyArray;
	return deTRUE;
}

deBoolean deBrushOctree::GetPolyInfo(deIndexedPoly* poly, deVec3d* &PosArray, deVec3d* &NormArray, deVertMat* &VertMatArray)
{
	if (poly == NULL || PosArray == NULL || NormArray == NULL || VertMatArray == NULL)
		return deFALSE;

	s32 i;
	for (i = 0; i < poly->NumVerts; ++i)
	{
		PosArray[i] = m_Positions[poly->PosIndices[i]];
		NormArray[i] = m_Normals[poly->NormIndices[i]];
		VertMatArray[i] = m_VertMats[poly->MatIndices[i]];
	}
	return deTRUE;
}

//private section

void deBrushOctree::DestroyNode(OctNode * node)
{
#pragma todo(unfinished method: DestroyNode)
	node = 0;
}

deBoolean deBrushOctree::InsertPolyIntoTree(long PolyIndex)
{
	// the big-un that's gonna be doing all the work
#pragma todo(unfinished method: InsertPolyIntoTree)
	MakePlane(PolyIndex);
	return deFALSE;

	deAABB			aabb;
	deVec3d*		verts;
	deIndexedPoly*	poly;
	OctNode*		node;
	int i;
	
	poly = m_PolyArray[PolyIndex];
	verts = new deVec3d[poly->NumVerts];
	for (i = 0; i < poly->NumVerts; ++i)
	{
		verts[i] = m_Positions[poly->PosIndices[i]];
	}
	
	deGeometry::ConstructAABB(verts, poly->NumVerts, aabb);
	node = GetSmallestNodeForAABB(aabb);
	InsertPolyIntoNode(PolyIndex, node);
}

deBoolean deBrushOctree::InsertPolyIntoNode(long PolyIndex, OctNode* Node)
{
	u8 InChild;
	int i;
	InChild = DecideChildNodes(PolyIndex, Node);
	
	for (i = 0; i < 8; ++i)
	{
		if ((InChild >> i) & 0x01)
		{
//			if (!(Node->Children[i]))
//				CreateNode()
			if (!InsertPolyIntoNode(PolyIndex, Node->Children[i]))
				return deFALSE;
		}
	}
	return deTRUE;
}

u8 deBrushOctree::DecideChildNodes(long /*PolyIndex*/, OctNode* /*Node*/)
{
#pragma todo(unfinished method: DecideChildNodes)


	/*
	bool FrontFacing[6];
	int i, NumFrontFacers, LastFrontFacer=0, LastBackFacer=0;
	deVec3d vec;
	deVec3d* norm = &(m_PolyArray[PolyIndex]->Normal);
	deDouble dist = m_PolyArray[PolyIndex]->Dist;
	NumFrontFacers = 0;
	for (i = 0; i < 6; ++i)
	{
		OctNodeMidPoint(Node, (char)i, vec);
		if (!deGeometry::PointOnPlaneBack(vec, *norm, dist))
		{
			FrontFacing[i] = true;
			NumFrontFacers++;
			LastFrontFacer = i;
		}
		else
		{
			FrontFacing[i] = false;
			LastBackFacer = i;
		}
	}
	switch(NumFrontFacers)
	{
	case 0:
		// all midpoints were behind the plane
		// only passes through one node
		return FrontmostOctNodeCorner(*norm);
		break;
	case 6:
		// all midpoints were in front of the plane
		// only passes through one node
		return (u8)(7 - FrontmostOctNodeCorner(*norm));
		break;
	case 5:
		// one midpoint is behind the plane - 4 child octants are passed through
		// LastBackFacer contains that one
		LastFrontFacer = LastBackFacer;
		// drop through
	case 1:
		// one midpoint is in front of the plane - 4 child octants are passed through
		// LastFrontFacer contains that one
		switch (LastFrontFacer)
		{
		case 0: return 1<<0 | 1<<2 | 1<<4 | 1<<6; // left
		case 1: return 1<<1 | 1<<3 | 1<<5 | 1<<7; // right
		case 2: return 1<<0 | 1<<1 | 1<<4 | 1<<5; // bottom
		case 3: return 1<<2 | 1<<3 | 1<<6 | 1<<7; // top
		case 4: return 1<<0 | 1<<1 | 1<<2 | 1<<3; // front
		case 5: return 1<<4 | 1<<5 | 1<<6 | 1<<7; // back
		}
		break;
#pragma todo (figure out a way around the case of a tilted plane that penetrates diagonally into a lower octant)
	}
	*/
	
	return 0;
}

deBoolean deBrushOctree::MakePlane(deIndexedPoly * poly)
{
	if (poly->NumVerts < 3 || poly->PosIndices == NULL)
	{
		DEBUGRETURN(deFALSE, "MakePlane: invalid polygon");
	}
	deVec3d vec0, vec1, vec2;
	vec0 = m_Positions[poly->PosIndices[0]];
	vec1 = m_Positions[poly->PosIndices[1]];
	vec2 = m_Positions[poly->PosIndices[2]];
	vec1 -= vec0;
	vec2 -= vec0;
	Vec3d_Cross(vec1, vec2, poly->Normal);
	if (Vec3d_Normalize(poly->Normal) == 0.0)
		DEBUGRETURN(deFALSE, "MakePlane: invalid polygon");
	poly->Dist = Vec3d_Dot(poly->Normal, vec0);
	return deTRUE;
}

deBoolean deBrushOctree::MakePlane(long PolyIndex)
{
	deIndexedPoly* Poly = m_PolyArray[PolyIndex];
	return MakePlane(Poly);
}












#if 0
#include "deBrush.hpp"
#include "deStack.hpp"
#include "deMath.hpp"

#include <cstdio>

#define MAXPOLYS	(10)
#define MINSIZE		(0.25)

deDouble PlanePointDist(const deBPoly &poly, const deVec3d & vec)
{
	return	Vec3d_Dot(poly.Normal, vec) - poly.Dist;
}

bool PlaneLineIntersect(const deBPoly & p, const deVec3d & LineP1, const deVec3d & LineP2, deVec3d & Result)
{
	// P1, P2 on line
	// P3 on plane, N normal
	// P = P1 + d(P2 - P1)
	// t = (N dot (P3 - P1)) / (N dot (P2 - P1))
	deVec3d P3;
	deDouble den, num, t;

#pragma todo(check the modifications work)

	P3 = LineP2;
	P3 -= LineP1;
	den = Vec3d_Dot(p.Normal, P4);
	if (den == 0)
	{
		return false;
	}
	num = Vec3d_Dot(p.Normal, LineP1);
	num = -p.Dist - num;
	t = num / den;
	// it will return coincident points
	if (t < 0 || t > 1)
		return false;
	Result = P3;
	Result *= t;
	Result += LineP1;
	return true;
}

bool TriLineIntersect(const deBPoly & p, const deVec3d & LineP1, const deVec3d & LineP2, deVec3d & Result)
{
	if (!PlaneLineIntersect(p, LineP1, LineP2, Result))
		return false;

	deVec3d u,v,w;
	u = p.Verts[1].Pos - p.Verts[0].Pos;
	v = p.Verts[2].Pos - p.Verts[0].Pos;
	w = Result - p.Verts[0].Pos;

	deDouble s,t, den;
	deDouble uv,uu,vv,wu,wv;
	uv = Vec3d_Dot(u,v);
	uu = Vec3d_Dot(u,u);
	vv = Vec3d_Dot(v,v);
	wu = Vec3d_Dot(w,u);
	wv = Vec3d_Dot(w,v);
	den = uv*uv - uu*vv;
	s = (uv*wv - vv*wu)/den;
	if (s < 0.0)
		return false;
	t = (uv*wu - vv*wu)/den;
	if (t < 0.0)
		return false;
	if (s+t > 1.0)
		return false;

	return true;
}

bool TriTriIntersect(const deBPoly & p1, const deBPoly & p2)
{
	int i, j, lim;
	deVec3d vec;
	lim = p1.NumVerts;
	for (i = 0; i < lim; i++)
	{
		j = i+1;
		if (j >= lim)
			j = 0;
		if (TriLineIntersect(p2, p1.Verts[i].Pos, p1.Verts[j].Pos, vec))
			return true;
	}
	lim = p2.NumVerts;
	for (i = 0; i < lim; i++)
	{
		j = i+1;
		if (j >= lim)
			j = 0;
		if (TriLineIntersect(p1, p2.Verts[i].Pos, p2.Verts[j].Pos, vec))
			return true;
	}
	return false;
}

void MakePlane(deBPoly & face)
{
	if (face.NumVerts < 3)
		return;

	deVec3d vec1, vec2;
	vec1 = face.Verts[0].Pos - face.Verts[1].Pos;
	vec2 = face.Verts[0].Pos - face.Verts[2].Pos;
	face.Normal = Vec3d_Cross(vec1, vec2);
	Vec3d_Normalize(face.Normal);
	Vec3d_Squeeze(face.Normal);
	face.Dist = Vec3d_Dot(face.Normal, face.Verts[0].Pos);
}

void MakeTri(const deLVert &v1, const deLVert &v2, const deLVert &v3, deBPoly & face)
{
	face.Resize(3);
	face.Verts[0] = v1;
	face.Verts[1] = v2;
	face.Verts[2] = v3;

	deVec3d t1, t2;
	t1 = v1.Pos;
	t1 -= v2.Pos;
	t2 = v1.Pos;
	t2 -= v3.Pos;
	face.Normal = Vec3d_Cross(t1, t2);
	Vec3d_Normalize(face.Normal);
	face.Dist = Vec3d_Dot(face.Normal, face.Verts[0].Pos);
}

long GetTris(deBPoly & in, deTArray <deBPoly> & outlist)
{
	if (in.NumVerts == 3)
	{
		outlist.Resize(1);
		outlist[0] = in;
		return 1;
	}
	int i, lim = in.NumVerts-1;
	outlist.Resize(lim-1);
	deBPoly face;
	for (i = 1; i < lim; i++)
	{
		MakeTri(in.Verts[0], in.Verts[i], in.Verts[i+1], face);
		outlist[i-1] = face;
	}
	return i-2;
}

bool PolyLineIntersect(deBPoly & p, const deVec3d & LineP1, const deVec3d & LineP2, deVec3d & Result)
{
	int i,lim=1;
	deTArray <deBPoly> list;
	if (GetTris(p, list))
		lim = list.Length();
	for (i = 0; i < lim; i++)
	{
		if (TriLineIntersect(list[i], LineP1, LineP2, Result))
			return true;
	}
	return false;
}

bool PolyPolyIntersect(deBPoly & p1, deBPoly & p2)
{
	if (p1.NumVerts == 3 && p2.NumVerts == 3)
		return TriTriIntersect(p1, p2);
	int i,j, lim1=1, lim2=1;
	deTArray <deBPoly> list1;
	deTArray <deBPoly> list2;
	if (GetTris(p1, list1))
		lim1 = list1.Length();
	if (GetTris(p2, list2))
		lim2 = list2.Length();
	for (i = 0; i < lim1; i++)
	{
		for (j = 0; j < lim2; j++)
		{
			if (TriTriIntersect(list1[i], list2[j]))
				return true;
		}
	}
	return false;
}

bool SplitPoly(deBPoly & input, deBPoly & splitter, deBPoly & output1, deBPoly & output2)
{
	if (input.NumVerts < 3 || splitter.NumVerts < 3)
		return false;
//	if (!PolyPolyIntersect(input, splitter))
//		return false;
	deVec3d intersect1, intersect2;
	int i,j, start, stop;
	for (i = 0; i < input.NumVerts; i++)
	{
		j = i+1;
		if (j >= input.NumVerts)
			j = 0;
		if (PlaneLineIntersect(splitter, input.Verts[i].Pos, input.Verts[j].Pos, intersect1))
		{
			start = i;
			i++;
			break;
		}
	}
	for (; i < input.NumVerts; i++)
	{
		j = i+1;
		if (j >= input.NumVerts)
			j = 0;
		if (PlaneLineIntersect(splitter, input.Verts[i].Pos, input.Verts[j].Pos, intersect2))
		{
			stop = i;
			break;
		}
	}
	if (i >= input.NumVerts || Vec3d_Compare(intersect1,intersect2))
	{
		output1 = input;
		return false;
	}

	int NumVerts;

	output2.Resize(stop-(start)+2);
	NumVerts = 0;
	output2.Verts[0].Pos = intersect2;
	output2.Verts[1].Pos = intersect1;
	NumVerts += 2;
	for (i = start+1; i <= stop; i++)
	{
		if (Vec3d_Compare(input.Verts[i].Pos, intersect2))
		{
			output2.NumVerts = NumVerts;
			break;
		}
		output2.Verts[NumVerts] = input.Verts[i];
		NumVerts++;
	}

	output1.Resize(start+2+input.NumVerts-stop);
	NumVerts = 0;
	for (i = 0; i <= start; i++)
	{
		if (Vec3d_Compare(input.Verts[i].Pos, intersect1))
		{
			output1.NumVerts--;
			break;
		}
		output1.Verts[i] = input.Verts[i];
		NumVerts++;
	}
	output1.Verts[i].Pos = intersect1;
	output1.Verts[i+1].Pos = intersect2;
	NumVerts += 2;
	for (i = stop+1; i < input.NumVerts; i++)
	{
		if (Vec3d_Compare(input.Verts[i].Pos, intersect2))
		{
			output1.NumVerts = NumVerts;
			break;
		}
		output1.Verts[NumVerts] = input.Verts[i];
		NumVerts++;
	}

	
	MakePlane(output1);
	MakePlane(output2);
	
//	output1.Normal = output2.Normal = input.Normal;
//	output1.Dist = output2.Dist = input.Dist;

	return true;
}

template <class T>
void Swap(T & t1, T & t2)
{
	T temp = t1;
	t1 = t2;
	t2 = temp;
}

void ReversePoly(deBPoly & poly)
{
	int i, lim;
	lim = poly.NumVerts;
	for (i = 0; i < lim/2; i++)
	{
		Swap(poly.Verts[i], poly.Verts[lim-i-1]);
	}
	poly.Dist *= -1.0;
	poly.Normal = poly.Normal * -1.0;
}

BrushOctree::BrushOctree()
{
	m_UseID = 0;
	m_Root = NULL;
	m_PolyNum = 0;
}

BrushOctree::~BrushOctree()
{
	DestroyNode(m_Root);
}

void BrushOctree::AddPoly(const deBPoly & poly)
{
	int i=0;
	if (m_PolyList.Length() == 0)
	{
		TargetMin.x = poly.Verts[0].Pos.x;
		TargetMin.y = poly.Verts[0].Pos.y;
		TargetMin.z = poly.Verts[0].Pos.z;
		TargetMax.x = poly.Verts[0].Pos.x;
		TargetMax.y = poly.Verts[0].Pos.y;
		TargetMax.z = poly.Verts[0].Pos.z;
		i = 1;
	}
	for (; i < poly.NumVerts; i++)
	{
		deVec3d & vert = poly.Verts[i].Pos;
		if (vert.x < TargetMin.x)
			TargetMin.x = vert.x;
		if (vert.y < TargetMin.y)
			TargetMin.y = vert.y;
		if (vert.z < TargetMin.z)
			TargetMin.z = vert.z;
		if (vert.x > TargetMax.x)
			TargetMax.x = vert.x;
		if (vert.y > TargetMax.y)
			TargetMax.y = vert.y;
		if (vert.z > TargetMax.z)
			TargetMax.z = vert.z;
	}
	m_PolyList.AddElement(poly);
}

void BrushOctree::Copy(BrushOctree & target)
{
	DestroyNode(target.m_Root);
	CopyNode(m_Root, target.m_Root);
	target.m_PolyArray = m_PolyArray;
	target.m_PolysUsed = m_PolysUsed;
	target.m_UseID = m_UseID + 1;
	target.m_PolyNum = m_PolyNum;
}

void BrushOctree::CopyNode(OctNode * source, OctNode * & target)
{
	int i;
	target = new OctNode;
	if (source->child[0])
	{
		for (i = 0; i < 8; i++)
		{
			CopyNode(source->child[i],target->child[i]);
			target->child[i]->ID = i;
			target->child[i]->child[8] = target;
		}
	}
	else
	{
		for (i = 0; i < 8; i++)
		{
			target->child[i] = NULL;
		}
	}
	target->Min = source->Min;
	target->Max = source->Max;
	target->child[8] = NULL;
	target->polylist = source->polylist;
}

void BrushOctree::DestroyNode(OctNode * node)
{
	if (node == NULL)
		return;
	int i;
	for (i = 0; i < 8; i++)
	{
		DestroyNode(node->child[i]);
		node->child[i] = NULL;
	}
	node->child[8] = NULL;
	delete node;
}

void BrushOctree::SubdivideNode(OctNode * node)
{
	int i,j;
	deVec3d Middle = (node->Min + node->Max) * (1.0/2);
	for (i = 0; i < 8; i++)
	{
		node->child[i] = new OctNode;
		node->child[i]->ID = i;
		for (j = 0; j<8; j++)
			node->child[i]->child[j] = NULL;
		node->child[i]->child[8] = node;
		if (i/4 == 0)	// bottom
		{
			node->child[i]->Min.Y = node->Min.Y;
			node->child[i]->Max.Y = Middle.Y;
		}
		else
		{
			node->child[i]->Min.Y = Middle.Y;
			node->child[i]->Max.Y = node->Max.Y;
		}
		if (i%2 == 0)	// left side
		{
			node->child[i]->Min.X = node->Min.X;
			node->child[i]->Max.X = Middle.X;
		}
		else
		{
			node->child[i]->Min.X = Middle.X;
			node->child[i]->Max.X = node->Max.X;
		}
		if ((i/2)%2 == 0)	// front side
		{
			node->child[i]->Min.Z = node->Min.Z;
			node->child[i]->Max.Z = Middle.Z;
		}
		else
		{
			node->child[i]->Min.Z = Middle.Z;
			node->child[i]->Max.Z = node->Max.Z;
		}
		PolyPointer * p;
		void * ptr = node->polylist.GetNext(NULL, p);
		while (ptr)
		{
			if (PolyInNode(p->polyindex, node->child[i]))
			{
				node->child[i]->polylist.AddElement(p);
			}
			ptr = node->polylist.GetNext(ptr, p);
		}
	}
}

void BrushOctree::Optimize(OctNode * node)
{
	int i;
	if (node == NULL)
		return;
	if (!node->child[0])
	{
		int Length = node->polylist.Length();
		if (Length > MAXPOLYS && Vec3d_Dist(node->Min,node->Max) > MINSIZE)
		{
			SubdivideNode(node);
		}
	}
	if (node->child[0])
	{
		for (i = 0; i < 8; i++)
		{
			Optimize(node->child[i]);
		}
	}
}

void BrushOctree::InsertPoly(long index)
{
	if (m_Root == NULL)
	{
		return;
	}
	PolyPointer * p = new PolyPointer;
	p->UseID = m_UseID-1;
	p->polyindex = index;
	InsertPoly(p, m_Root);
}

bool BrushOctree::InsertPoly(PolyPointer * p, OctNode * node)
{
	int i;
	if (PolyInNode(p->polyindex, node))
	{
		if (node->child[0])
		{
			for (i = 0; i < 8; i++)
			{
				if (InsertPoly(p, node->child[i]))
					return true;
			}
		}
		//else
		{
			node->polylist.AddElement(p);
			p->InNodes.AddElement(node);
			if (node->polylist.Length() > MAXPOLYS)
				Optimize(node);
			return true;
		}
	}
	return false;
}

void BrushOctree::RemovePoly(PolyPointer * p)
{
	OctNode * n;
	void * ptr = p->InNodes.GetNext(NULL, n);
	void *ptr2;
	while (ptr)
	{
		ptr2 = n->polylist.FindData(NULL, p);
		n->polylist.RemoveElement(ptr2);
		ptr = p->InNodes.GetNext(ptr, n);
	}
	m_PolysUsed[p->polyindex] = false;
	m_PolyNum--;
}

void BrushOctree::Generate()
{
	if (m_Root == NULL)
	{
		int x;
		m_Root = new OctNode;
		for(x=0; x<9; x++)
		{
			m_Root->child[x] = NULL;
		}
		m_Root->ID = 8;
		/*
		m_Root->Min.x = m_Root->Min.y = m_Root->Min.z 
			= min(min(TargetMin.x, TargetMin.y), TargetMin.z);
		m_Root->Max.x = m_Root->Max.y = m_Root->Max.z 
			= max(max(TargetMax.x, TargetMax.y), TargetMax.z);
		*/
		m_Root->Min = TargetMin;
		m_Root->Max = TargetMax;
		//SubdivideNode(m_Root);
	}
	deBPoly *p;
	int i = -1;
	void * ptr = NULL;
	ptr = m_PolyList.GetNext(ptr, p);
	while (ptr)
	{
		do
		{
			i++;
			if (i >= m_PolyArray.Length())
			{
				m_PolyArray.Resize(i + MAXPOLYS);
				m_PolysUsed.Resize(m_PolyArray.Length());
				for (int k = i; k < m_PolysUsed.Length(); k++)
					m_PolysUsed[k] = false;
			}
		}
		while(m_PolysUsed[i] == true);
		m_PolyArray[i] = *p;
		m_PolysUsed[i] = true;
		m_PolyNum++;
		InsertPoly(i);
		ptr = m_PolyList.GetNext(ptr, p);
	}
	m_PolyList.EmptyList();
}

void BrushOctree::Clear()
{
	DestroyNode(m_Root);
	m_Root = 0;
	m_PolyList.EmptyList();
	m_PolyArray.Resize(0);
	m_PolysUsed.Resize(0);
	m_PolyNum = 0;
}

bool BrushOctree::PointInBox(const deVec3d & vert, const deVec3d &Min, const deVec3d &Max)
{
	if (vert.x < Min.x)
		return false;
	if (vert.y < Min.y)
		return false;
	if (vert.z < Min.z)
		return false;
	if (vert.x > Max.x)
		return false;
	if (vert.y > Max.y)
		return false;
	if (vert.z > Max.z)
		return false;
	return true;
}
	
bool BrushOctree::BoxInBox(const deVec3d & Min1, const deVec3d & Max1, const deVec3d & Min2, const deVec3d & Max2)
{
	if (Min1.x < Min2.x)
		return false;
	if (Min1.y < Min2.y)
		return false;
	if (Min1.z < Min2.z)
		return false;

	if (Max1.x > Max2.x)
		return false;
	if (Max1.y > Max2.y)
		return false;
	if (Max1.z > Max2.z)
		return false;

	return true;
}

bool BrushOctree::BoxBoxIntersect(const deVec3d & Min1, const deVec3d & Max1, 
								  const deVec3d & Min2, const deVec3d & Max2)
{
	if (Max1.x < Min2.x)
		return false;
	if (Max1.y < Min2.y)
		return false;
	if (Max1.z < Min2.z)
		return false;

	if (Max2.x < Min1.x)
		return false;
	if (Max2.y < Min1.y)
		return false;
	if (Max2.z < Min1.z)
		return false;

	return true;
}

bool BrushOctree::PolyInNode(long index, OctNode * node)
{
	int i;
	deVec3d Min, Max;
	if (node == NULL)
		return false;
	Min = node->Min;
	Max = node->Max;
	deBPoly * poly = &m_PolyArray[index];
	for (i = 0; i < poly->NumVerts; i++)
	{
		if (!PointInBox(poly->Verts[i].Pos, Min, Max))
			return false;
	}
	return true;
	//=====================
	// test against sides
	//=====================
	return false;
}

long BrushOctree::GetAllPolys(deTList <deBPoly*> & polylist)
{
	int i;
	for (i = 0; i < m_PolyNum; i++)
	{
		polylist.AddElement(&(m_PolyArray[i]));
	}
	return i;
}

long BrushOctree::GetAllPolys(deTList <PolyPointer*> & polylist, OctNode * node)
{
	int i, count=0;
	if (node == NULL)
	{
		node = m_Root;
	}
	// add all child polys
	if (node->child[0])
	{
		for (i = 0; i < 8; i++)
		{
			count += GetAllPolys(polylist, node->child[i]);
		}
	}
	// add local polys
	PolyPointer * p;
	void * ptr;
	ptr = node->polylist.GetNext(NULL, p);
	while (ptr)
	{
		polylist.AddElement(p);
		count++;
		ptr = node->polylist.GetNext(ptr, p);
	}
	return count;
}

/*
	four cases:
	node does not intersect bbox
	node does intersect bbox, but neither is "inside" the other
	bbox is inside node
	node is inside bbox
*/
long BrushOctree::GetPolysInBox(const deVec3d & Min, const deVec3d & Max, deTList <PolyPointer*> & polylist, OctNode * node)
{
	int i, count=0;
	if (node == NULL)
	{
		m_UseID++;
		node = m_Root;
	}
	// no intersection, no polys
	if (!BoxBoxIntersect(Min, Max, node->Min, node->Max))
	{
		return 0;
	}
	// node in bbox, return all polys in here
	if (BoxInBox(node->Min, node->Max, Min, Max))
	{
		return GetAllPolys(polylist, node);
	}
	// bbox in node, could be in a smaller node
	if (BoxInBox(Min, Max, node->Min, node->Max))
	{
		if (node->child[0])
		{
			for (i = 0; i < 8; i++)
			{
				count += GetPolysInBox(Min, Max, polylist, node->child[i]);
			}
			return count;
		}
		else
		{
			return GetAllPolys(polylist, node);
		}
	}
	// boxes intersect only, so check children for intersections
	{
		count = GetAllPolys(polylist, node);
		if (node->child[0])
		{
			for (i = 0; i < 8; i++)
			{
				if (BoxBoxIntersect(Min, Max, node->child[i]->Min, node->child[i]->Max))
					count += GetPolysInBox(Min, Max, polylist, node->child[i]);
			}
		}
		else
		{
			// if no children, just dump em all
			count += GetAllPolys(polylist, node);
		}
	}
	return count;
}

long BrushOctree::PolysIntersecting(deBPoly & poly, deTList <PolyPointer*> & polylist, bool CheckIntersection)
{
	int i, count, lim;
	deVec3d Min, Max;
	// get bbox for poly
	i = 0;
	{
		Min.x = poly.Verts[0].Pos.x;
		Min.y = poly.Verts[0].Pos.y;
		Min.z = poly.Verts[0].Pos.z;
		Max.x = poly.Verts[0].Pos.x;
		Max.y = poly.Verts[0].Pos.y;
		Max.z = poly.Verts[0].Pos.z;
		i = 1;
	}
	for (; i < poly.NumVerts; i++)
	{
		deVec3d & vert = poly.Verts[i].Pos;
		if (vert.x <= Min.x)
			Min.x = vert.x;
		if (vert.y <= Min.y)
			Min.y = vert.y;
		if (vert.z <= Min.z)
			Min.z = vert.z;
		if (vert.x >= Max.x)
			Max.x = vert.x;
		if (vert.y >= Max.y)
			Max.y = vert.y;
		if (vert.z >= Max.z)
			Max.z = vert.z;
	}
	if (CheckIntersection)
	{
		deTList <PolyPointer*> list;
		PolyPointer * p;
		lim = GetPolysInBox(Min, Max, list);
		count = 0;
		void * ptr = list.GetNext(NULL, p);
		while (ptr)
		{
			if (PolyPolyIntersect(poly, m_PolyArray[p->polyindex]))
			{
				polylist.AddElement(p);
				count++;
			}
			ptr = list.GetNext(ptr, p);
		}
	}
	else
	{
		count = GetPolysInBox(Min, Max, polylist, NULL);
	}
	return count;
}

void BrushOctree::Split(BrushOctree & In1, BrushOctree & In2, 
						BrushOctree & Out1, BrushOctree & Out2)
{
	if (In1.m_Root == NULL || In2.m_Root == NULL)
		return;
	{
		deVec3d Min[2], Max[2];
		Min[0] = In1.m_Root->Min;
		Min[1] = In2.m_Root->Min;
		Max[0] = In1.m_Root->Max;
		Max[1] = In2.m_Root->Max;
		// no overlapping area;
		if (!BoxBoxIntersect(Min[0], Max[0], Min[1], Max[1]))
			return;
	}
	int i, count;
	In1.Copy(Out1);
	In2.Copy(Out2);
	deTList <PolyPointer*> inlist;
	//deTList <deBPoly> outlist;
	deBPoly out1, out2;
	for(i = 0; i < In1.m_PolyArray.Length(); i++)
	{
		inlist.EmptyList();
		count = Out2.PolysIntersecting(In1.m_PolyArray[i], inlist, false);
		if (count == 0)
			continue;
		PolyPointer * p;
		void * ptr = inlist.GetNext(NULL, p);
		while (ptr)
		{
			if (SplitPoly(Out2.m_PolyArray[p->polyindex], In1.m_PolyArray[i], out1, out2))
			{
				Out2.RemovePoly(p);
				Out2.AddPoly(out1);
				Out2.AddPoly(out2);
			}
			ptr = inlist.GetNext(ptr, p);
		}
		Out2.Generate();
	}
	for(i = 0; i < In2.m_PolyArray.Length(); i++)
	{
		inlist.EmptyList();
		count = Out1.PolysIntersecting(In2.m_PolyArray[i], inlist, false);
		if (count == 0)
			continue;
		PolyPointer * p;
		void * ptr = inlist.GetNext(NULL, p);
		while (ptr)
		{
			if (SplitPoly(Out1.m_PolyArray[p->polyindex], In2.m_PolyArray[i], out1, out2))
			{
				Out1.RemovePoly(p);
				Out1.AddPoly(out1);
				Out1.AddPoly(out2);
			}
			ptr = inlist.GetNext(ptr, p);
		}
		Out1.Generate();
	}
}

void BrushOctree::Subtract(BrushOctree & cutter)
{
	BrushOctree Copy1, Copy2;
	Split(*this, cutter, Copy1, Copy2);

	deBPoly *opposite=NULL, *poly=NULL;
	deVec3d intersect;
	deDouble Length = Vec3d_Dist(m_Root->Max, m_Root->Min);

	Clear();
	DestroyNode(m_Root);
	m_Root = NULL;

	int i, lim;
	lim = Copy2.m_PolyNum;
	//lim=0;
	for (i = 0; i < lim; i++)
	{
		poly = &(Copy2.m_PolyArray[i]);
		deVec3d Start = (poly->Verts[0].Pos + poly->Verts[1].Pos + poly->Verts[2].Pos) * (1.0/3); 
		deVec3d Finish = Start + (poly->Normal * Length);
		// if the cut polygon intersects
		if (this->RayTrace(Start, Finish, opposite, intersect))
		{
			// and the two face each other, then it's inside
			if (Vec3d_Dot(opposite->Normal, poly->Normal) > 0)
				AddPoly(*poly);
		}
	}
	lim = Copy1.m_PolyNum;
	for (i = 0; i < lim; i++)
	{
		poly = &(Copy1.m_PolyArray[i]);
		deVec3d Start = (poly->Verts[0].Pos + poly->Verts[1].Pos + poly->Verts[2].Pos) * (1.0/3); 
		deVec3d Finish = Start + (poly->Normal * Length);
		// if the cut polygon intersects
		if (cutter.RayTrace(Start, Finish, opposite, intersect))
		{
			// and the two face each other, then it's inside
			if (Vec3d_Dot(opposite->Normal, poly->Normal) < 0)
			{
				ReversePoly(*poly);
				AddPoly(*poly);
			}
		}
		else
		{
			AddPoly(*poly);
		}
	}
	Generate();
}

void BrushOctree::Intersection(BrushOctree & brush)
{
}

bool BrushOctree::RayTrace(	const deVec3d & start, const deVec3d & end, 
							deBPoly * & poly, deVec3d & intersect)
{
	int i;
	deVec3d closest;
	deBPoly * closepoly = NULL;
	for (i = 0; i < m_PolyNum; i++)
	{
		if (PolyLineIntersect(m_PolyArray[i], start, end, intersect))
		{
			if (closepoly == NULL)
			{
				closepoly = &m_PolyArray[i];
				closest = intersect;
			}
			else if (Vec3d_DistSq(intersect, start) < Vec3d_DistSq(closest, start))
			{
				closepoly = &m_PolyArray[i];
				closest = intersect;
			}
		}
	}
	if (closepoly == NULL)
		return false;
	poly = closepoly;
	intersect = closest;
	return true;
}

#endif