///////////////////////////////////////////////////////////////////////////////
/// @file deOctree.cpp
///
/// @brief octree for use in scenegraph, not for use outside scenegraph library
///
/// @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 Jun 2002
/// @author Assassin
/// @remarks Initial Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "deOctree.hpp"
#include "deMath.hpp"
#include "deDriver.hpp"

/*
        ________Max
       / 6 / 7 /|
      /___/___/7|		Y+  Z+
     / 4 / 5 /| |		|  /
    /___/___/5|/|		| /
    |   |   | /3|		|/____X+
2=>	| 4 | 5 |/| |
    |-------|1|/
    | 0 | 1 | /
    |___|___|/
  Min
*/

#pragma note(the octree has been officially denounced)
// http://www.destiny3d.com/forum/viewtopic.php?topic=1233&forum=1&2

#pragma todo(consider putting a pointer to an object in every octant that it touches and not just the spanning octant)

void deSceneOctree::TEST()
{
	/*
	int i;
	IdeBrushRoom * Room;
	Room = IdeSceneRoom_CreateBrushRoom();
	Room->SetAABB(deMake_Vec3d(-1,0,-10), deMake_Vec3d(1,2,-8));
	InsertNode(Room);
	Room = IdeSceneRoom_CreateBrushRoom();
	Room->SetAABB(deMake_Vec3d(2,0,-10), deMake_Vec3d(3,2,-8));
	InsertNode(Room);
	IdeCollision::deCollideInfo blah;
	TraceRayCollision(deMake_Vec3d(0,1,0), deMake_Vec3d(0,1,-20), blah);
	TraceRayCollision(deMake_Vec3d(0,1,-11), deMake_Vec3d(4,1,-11), blah);
	Octant *oct1, *oct2;
	oct1 = MakeOctant(deMake_Vec3d(0,0,0), deMake_Vec3d(4,4,4), NULL, 8);
	i = DecideChildOctant(oct1, deMake_Vec3d(3,1,1));
	i = DecideParentOctant(oct1, deMake_Vec3d(1,1,1));
	for (i = 0; i < 8; i++)
	{
		oct2 = MakeSubOctant(oct1, i);
		RemoveOctant(oct2, NULL, deFALSE);
	}
	for (i = 0; i < 8; i++)
	{
		oct2 = MakeSubOctant(oct1, (i << 4) + 8);
		oct1->Parent = NULL;
		delete oct2;
	}
	RemoveOctant(oct1, NULL, deTRUE);
	*/
}

static inline void FindCenter(const deVec3d & Min, const deVec3d & Max, deVec3d & Center)
{
	// helper function for finding the average center of a BBox
	Center = Min;
	Center += Max;
	Center /= 2.0;
}

//==================================================
// public section below (helper methods)
//==================================================

deSceneOctree::deSceneOctree()
{
	// minimum size for octant dimension
	m_MinSize = 1.0;
	// max num of nodes per octant
	m_MaxNodes = 1; // some arbitrary default value

	m_TestNumber = 0;

	m_Root = NULL;
	if (!InitializeRoot())
		throw;

	m_LineListVB = IdeVertexBuffer_CreateVBuffer();
	m_LineListVB->Lock();
	m_LineListVB->SetDynamicStatus(deTRUE, deTRUE);
	m_LineListVB->SetBufferSize(0);
	m_LineListVB->CreateBuffer(IdeVertexBuffer::BUFFER_POSITION, deFALSE);
	m_LineListVB->SetRenderType(IdeVertexBuffer::RENDER_LINELIST);
	m_LineListVB->Unlock();
}

deSceneOctree::~deSceneOctree()
{
	// destroy the octant tree
	WipeTree();

	m_LineListVB->Release();
}

int deSceneOctree::Release()
{
	// standard non-ref-counted Release
	delete this;
	return 0;
}

void deSceneOctree::SetMinOctSize(deDouble MinSize)
{
	// set our minimum octant dimension
	m_MinSize = MinSize;
}

deDouble deSceneOctree::GetMinOctSize()
{
	// return our minimum octant dimension
	return m_MinSize;
}

void deSceneOctree::SetMaxNodeNum(int MaxNum)
{
	// set our max objects per octant
	m_MaxNodes = MaxNum;
}

int deSceneOctree::GetMaxNodeNum()
{
	// return our max objects per octant
	return m_MaxNodes;
}

IdeVertexBuffer * deSceneOctree::GetVB(int MaxPoints)
{
	deVertex * PosBuffer;
	int LastPoint = 0;

	m_LineListVB->Lock();
	m_LineListVB->SetBufferSize(MaxPoints);
	PosBuffer = (deVertex *)m_LineListVB->GetBuffer(IdeVertexBuffer::BUFFER_POSITION);

	FillOctantLinePoints(NULL, PosBuffer, LastPoint, MaxPoints);

//	m_LineListVB->SetBufferSize(LastPoint);

	m_LineListVB->DirtyBuffer(IdeVertexBuffer::BUFFER_POSITION);
	m_LineListVB->Unlock();

	return m_LineListVB;
}

deBoolean deSceneOctree::WipeTree()
{
	if (m_Root)
	{
		if (!RemoveOctant(m_Root, NULL, deTRUE, deTRUE))
			return deFALSE;
	}

	return deTRUE;
}

deBoolean deSceneOctree::AddNode(IdeSceneRoom * Node)
{
	return InsertNode(Node);
}

deBoolean deSceneOctree::RemoveNode(IdeSceneRoom * Node)
{
#pragma todo(finish me)
	Node = NULL;
	return deFALSE;
}

IdeSceneRoom * deSceneOctree::FindContainerNode(const deVec3d &Position)
{
	Octant * oct = FindOctant(Position);
	if (!oct)
		return NULL;

	IdeSceneRoom * Node;
	void * ptr;
	deVec3d Min, Max;

	ptr = oct->FixedNodes.GetNext(NULL, Node);
	while (ptr)
	{
		Node->GetAABB(Min, Max);
		if (deGeometry::PointInAABB(Position, Min, Max))
			return Node;

		ptr = oct->FixedNodes.GetNext(ptr, Node);
	}
	ptr = oct->AddedNodes.GetNext(NULL, Node);
	while (ptr)
	{
		Node->GetAABB(Min, Max);
		if (deGeometry::PointInAABB(Position, Min, Max))
			return Node;

		ptr = oct->AddedNodes.GetNext(ptr, Node);
	}

	return NULL;
}

IdeSceneRoom * deSceneOctree::FindClosestNode(const deVec3d &Position)
{
#pragma todo(finish me)
	deDouble x = Position.x; x++;
	return NULL;
}

deBoolean deSceneOctree::FindIntersectingNodes(deTList <IdeSceneRoom*> &List, const deVec3d * Mins, const deVec3d * Maxs)
{
#pragma todo(finish me)
	List.Length();
	Mins = Maxs = NULL;
	return deFALSE;
}

deBoolean deSceneOctree::TraceRayCollision(const deVec3d &Start, const deVec3d &End, IdeCollision::deCollideInfo &Collision)
{
	Octant * OctStart = FindOctant(Start);
	return RayTestNodes(OctStart, Start, End, &Collision);
}

void deSceneOctree::CleanUp()
{
	if (m_Root)
	{
		CleanUp(m_Root);

		bool HasChildren = false;
		int index;
		for (int i = 0; i < 8; i++)
		{
			if (m_Root->Child[i])
			{
				if (!HasChildren)
				{
					HasChildren = true;
					index = i;
				}
				else
					return;
			}
		}
	}
}

//==================================================
// private section below (helper methods)
//==================================================

deBoolean deSceneOctree::FillOctantLinePoints(Octant * oct, deVertex * Buffer, int & LastPoint, int MaxPoints)
{
	int i;

	if (!oct)
	{
		oct = m_Root;
	}

	if (LastPoint + 24 >= MaxPoints)
		return deTRUE;

#pragma warning (push)
#pragma warning (disable : 4244) // double to float conversion
	// lower square
	Buffer[LastPoint+ 0] = deMake_Vertex(oct->Min.x, oct->Min.y, oct->Min.z);
	Buffer[LastPoint+ 1] = deMake_Vertex(oct->Max.x, oct->Min.y, oct->Min.z);
	Buffer[LastPoint+ 2] = deMake_Vertex(oct->Max.x, oct->Min.y, oct->Min.z);
	Buffer[LastPoint+ 3] = deMake_Vertex(oct->Max.x, oct->Min.y, oct->Max.z);
	Buffer[LastPoint+ 4] = deMake_Vertex(oct->Max.x, oct->Min.y, oct->Max.z);
	Buffer[LastPoint+ 5] = deMake_Vertex(oct->Min.x, oct->Min.y, oct->Max.z);
	Buffer[LastPoint+ 6] = deMake_Vertex(oct->Min.x, oct->Min.y, oct->Max.z);
	Buffer[LastPoint+ 7] = deMake_Vertex(oct->Min.x, oct->Min.y, oct->Min.z);
	LastPoint += 8;

	// upper square
	Buffer[LastPoint+ 0] = deMake_Vertex(oct->Min.x, oct->Max.y, oct->Min.z);
	Buffer[LastPoint+ 1] = deMake_Vertex(oct->Max.x, oct->Max.y, oct->Min.z);
	Buffer[LastPoint+ 2] = deMake_Vertex(oct->Max.x, oct->Max.y, oct->Min.z);
	Buffer[LastPoint+ 3] = deMake_Vertex(oct->Max.x, oct->Max.y, oct->Max.z);
	Buffer[LastPoint+ 4] = deMake_Vertex(oct->Max.x, oct->Max.y, oct->Max.z);
	Buffer[LastPoint+ 5] = deMake_Vertex(oct->Min.x, oct->Max.y, oct->Max.z);
	Buffer[LastPoint+ 6] = deMake_Vertex(oct->Min.x, oct->Max.y, oct->Max.z);
	Buffer[LastPoint+ 7] = deMake_Vertex(oct->Min.x, oct->Max.y, oct->Min.z);
	LastPoint += 8;

	// vertical lines
	Buffer[LastPoint+ 0] = deMake_Vertex(oct->Min.x, oct->Min.y, oct->Min.z);
	Buffer[LastPoint+ 1] = deMake_Vertex(oct->Min.x, oct->Max.y, oct->Min.z);
	Buffer[LastPoint+ 2] = deMake_Vertex(oct->Max.x, oct->Min.y, oct->Min.z);
	Buffer[LastPoint+ 3] = deMake_Vertex(oct->Max.x, oct->Max.y, oct->Min.z);
	Buffer[LastPoint+ 4] = deMake_Vertex(oct->Min.x, oct->Min.y, oct->Max.z);
	Buffer[LastPoint+ 5] = deMake_Vertex(oct->Min.x, oct->Max.y, oct->Max.z);
	Buffer[LastPoint+ 6] = deMake_Vertex(oct->Max.x, oct->Min.y, oct->Max.z);
	Buffer[LastPoint+ 7] = deMake_Vertex(oct->Max.x, oct->Max.y, oct->Max.z);
	LastPoint += 8;
#pragma warning (pop)

	for (i = 0; i < 8; i++)
	{
		if (oct->Child[i])
		{
			if (!FillOctantLinePoints(oct->Child[i], Buffer, LastPoint, MaxPoints))
				return deFALSE;
		}
	}

	return deTRUE;
}

deBoolean deSceneOctree::InitializeRoot()
{
	if (!WipeTree())
		return deFALSE;

	// start off with a root that has the origin right in the middle
	deVec3d Min = {-m_MinSize, -m_MinSize, -m_MinSize};
	deVec3d Max = {m_MinSize, m_MinSize, m_MinSize};
	m_Root = MakeOctant(Min, Max, NULL, 0);

	if (!m_Root)
		return deFALSE;

	return deTRUE;
}

void deSceneOctree::CleanUp(Octant * oct)
{
//this recursive function removes all the octants that have no contained nodes or child octants
	if (!oct)
		return;

	bool HasChildren = false;
	// clean up all the children too
	for (int i = 0; i < 8; i++)
	{
		if (oct->Child[i])
		{
			// if we have a child, still a chance that it can be deleted and not count as a child
			CleanUp(oct->Child[i]);
			if (oct->Child[i]->CanBeRemoved)
			{
				// might not actually get removed due to neighbor-list restrictions
				if (!RemoveOctant(oct->Child[i], NULL, deTRUE))
					HasChildren = true;
			}
			else
				HasChildren = true;
		}
	}

	// if we have no nodes and no children, we can be deleted
	if (oct->AddedNodes.Length() == 0 && oct->FixedNodes.Length() == 0)
	{
		if (!HasChildren)
			oct->CanBeRemoved = deTRUE;
	}

	// the octant doesn't delete itself, it just says "hey i can be removed" which the parent can then check
	// nothing should delete the root, that would be BAD
}

deBoolean deSceneOctree::SubdivideOctant(Octant * oct)
{
//this function creates children for oct at each location where nodes exist and puts the nodes into the correct octants

	// no octant. no good
	if (!oct)
		return deFALSE;

	// loop through the child positions, making new octants for them
	int i;
	IdeSceneRoom *node, **node2;
	void *ptr;
	deVec3d Min, Max, Center;
	ptr = oct->AddedNodes.GetNext(NULL, node);
	// loop through all the nodes in the current octant, and decide which child octant to put them in
	while (ptr)
	{
		// get the bbox for the node
		node->GetAABB(Min, Max);
		FindCenter(Min, Max, Center);
		// figure out which direction from the center of this is best to use
		i = DecideChildOctant(oct, Center);
		if (oct->Child[i] == NULL)
		{
			// only make children as needed
			oct->Child[i] = MakeSubOctant(oct, i);
			if (oct->Child[i] == NULL)
				return deFALSE;
		}
		// test if the bbox fits inside the child in that direction
		if (TestOctantBBox(oct->Child[i], Min, Max))
		{
			// if it does, remove from this list and add to child's
			if (!(oct->Child[i]->AddedNodes.AddElement(node)))
				return deFALSE;
			ptr = oct->AddedNodes.RemoveElementGetNext(ptr, node2);
			if (node2)
				node = *node2;
		}
		else
		{
			// if it doesn't, just keep it in this octant, but in a separate list
			if (!(oct->FixedNodes.AddElement(node)))
				return deFALSE;
			ptr = oct->AddedNodes.RemoveElementGetNext(ptr, node2);
			if (node2)
				node = *node2;
		}
	}

	CleanUp(oct);
	for (i = 0; i < 8; i++)
	{
		if (oct->Child[i])
		{
			if (!CalcNeighbors(oct->Child[i]))
				return deFALSE;
		}
	}
	return deTRUE;
}

deBoolean deSceneOctree::Optimize(Octant * oct)
{
//this recursive function splits octants until a base case is met

	if (!oct)
		return deFALSE;

	// stop if we have an acceptable number of nodes
	if (oct->AddedNodes.Length() <= m_MaxNodes)
	{
		return deTRUE;
	}

	// stop if the size of the node is at our size threshold
	deDouble Diff = oct->Max.x - oct->Min.x;
	if (Diff <= m_MinSize)
		return deTRUE;

	// split into 8 children
	if (!SubdivideOctant(oct))
		return deFALSE;

	// optimize all the children too
	for (int i = 0; i < 8; i++)
	{
		if (oct->Child[i])
		{
			if (!Optimize(oct->Child[i]))
				return deFALSE;
		}
	}

	return deTRUE;
}

deBoolean deSceneOctree::InsertNode(IdeSceneRoom * Node)
{
	Octant * oct;
	deVec3d Min, Max;
	Node->GetAABB(Min, Max);

	// values this extreme are most likely uninitialized and/or erroneous
	if (Min.x < -1000000000000.0f || Max.x > 1000000000000.0f)
	{
		return deFALSE;
	}

	// find the already-created octant that contains this node
	oct = FindOctant(Min, Max);

	// if no octant could be found, we must create one bigger than the current root
	if (oct == NULL)
	{
		// it's possible that someone wiped the tree entirely clean
		if (m_Root == NULL)
		{
			if (!InitializeRoot())
				DEBUGRETURN(deFALSE, "InsertNode: Failed to create a root node");
		}

		int i;
		deVec3d Center;
		Octant * NewRoot;
		FindCenter(Min, Max, Center);
		// continue expanding the octree
		while (oct == NULL)
		{
			// figure out where it's meant to go
			i = DecideParentOctant(m_Root, Center);
			// create a new octant to hold it
			NewRoot = MakeSubOctant(m_Root, i);
			// fail if octant-creation fails
			if (NewRoot)
				m_Root = NewRoot;
			else
				return deFALSE;

			// test again to see if the new root is big enough
			oct = FindOctant(Min, Max);
		}
	}

	if (!oct->AddedNodes.AddElement(Node))
		return deFALSE;
	if (!Optimize(oct))
		return deFALSE;

	return deTRUE;
}

deBoolean deSceneOctree::CalcNeighbors(Octant * oct)
{
// this method is intended to find all neighbors of this octant
// possibly also put in mutual links for octants that now have this as a neighbor

	int i;

	oct->Neighbor[n_Left] = TraceNeighbor(oct, oct, n_Left, 0);
	oct->Neighbor[n_Bottom] = TraceNeighbor(oct, oct, n_Bottom, 0);
	oct->Neighbor[n_Front] = TraceNeighbor(oct, oct, n_Front, 0);

	oct->Neighbor[n_Right] = TraceNeighbor(oct, oct, n_Right, 0);
	oct->Neighbor[n_Top] = TraceNeighbor(oct, oct, n_Top, 0);
	oct->Neighbor[n_Back] = TraceNeighbor(oct, oct, n_Back, 0);

	// all our new neighbors must be informed that they are now being pointed at by stuff
	// this is a cheap way to avoid keeping a mutual neighbor list, which could get quite large
	for (i = 0; i < 6; i++)
	{
		if (oct->Neighbor[i])
			(oct->Neighbor[i]->NeighborRefs)++;
	}

	return deTRUE;
}

deSceneOctree::Octant* deSceneOctree::TraceNeighbor(Octant * Start, Octant * Current, Neighbor_t N, int Depth)
{
// this recursive method traces octants until it finds an appropriate octant
// appropriate means less or equal depth, and must border on teh side indicated

	if (!Current || !Start)
		return NULL;

	// of course the start isn't the neighbor
	if (Start == Current)
	{
		return TraceNeighbor(Start, Current->Parent, N, Depth-1);
	}

	// if we've re-descended to the same depth, we must have a neighbor
	if (Depth == 0)
	{
		int N2;
		N2 = ((int)N) ^ 0x01;
		if (Current->Neighbor[N2])
		{
			(Current->Neighbor[N2]->NeighborRefs)--;
		}
		Current->Neighbor[N2] = Start;
		(Start->NeighborRefs)++;
		return Current;
	}

	Octant* Possibles[4];
	deDouble Epsilon = m_MinSize / 10.0;

	// look for direct match-ups
	if ((N == n_Left && Compare_Epsilon(Current->Max.x, Start->Min.x, Epsilon)) ||
		(N == n_Right && Compare_Epsilon(Current->Center.x, Start->Max.x, Epsilon)))
	{
		// the right 4
		Possibles[0] = Current->Child[1];
		Possibles[1] = Current->Child[3];
		Possibles[2] = Current->Child[5];
		Possibles[3] = Current->Child[7];
	}
	else if ((N == n_Left && Compare_Epsilon(Current->Center.x, Start->Min.x, Epsilon)) ||
			(N == n_Right && Compare_Epsilon(Current->Min.x, Start->Max.x, Epsilon)))
	{
		// the left 4
		Possibles[0] = Current->Child[0];
		Possibles[1] = Current->Child[2];
		Possibles[2] = Current->Child[4];
		Possibles[3] = Current->Child[6];
	}
	else if (N == n_Left || N == n_Right)
		return TraceNeighbor(Start, Current->Parent, N, Depth-1);
	else if ((N == n_Bottom && Compare_Epsilon(Current->Max.y, Start->Min.y, Epsilon)) ||
			(N == n_Top && Compare_Epsilon(Current->Center.y, Start->Max.y, Epsilon)))
	{
		// the top 4
		Possibles[0] = Current->Child[4];
		Possibles[1] = Current->Child[5];
		Possibles[2] = Current->Child[6];
		Possibles[3] = Current->Child[7];
	}
	else if ((N == n_Bottom && Compare_Epsilon(Current->Center.y, Start->Min.y, Epsilon)) ||
			(N == n_Top && Compare_Epsilon(Current->Min.y, Start->Max.y, Epsilon)))
	{
		// the bottom 4
		Possibles[0] = Current->Child[0];
		Possibles[1] = Current->Child[1];
		Possibles[2] = Current->Child[2];
		Possibles[3] = Current->Child[3];
	}
	else if (N == n_Bottom || N == n_Top)
		return TraceNeighbor(Start, Current->Parent, N, Depth-1);
	else if ((N == n_Front && Compare_Epsilon(Current->Max.z, Start->Min.z, Epsilon)) ||
			(N == n_Back && Compare_Epsilon(Current->Center.z, Start->Max.z, Epsilon)))
	{
		// the back 4
		Possibles[0] = Current->Child[2];
		Possibles[1] = Current->Child[3];
		Possibles[2] = Current->Child[6];
		Possibles[3] = Current->Child[7];
	}
	else if ((N == n_Front && Compare_Epsilon(Current->Center.z, Start->Min.z, Epsilon)) ||
			(N == n_Back && Compare_Epsilon(Current->Min.z, Start->Max.z, Epsilon)))
	{
		// the front 4
		Possibles[0] = Current->Child[0];
		Possibles[1] = Current->Child[1];
		Possibles[2] = Current->Child[4];
		Possibles[3] = Current->Child[5];
	}
	else if (N == n_Front || N == n_Back)
		return TraceNeighbor(Start, Current->Parent, N, Depth-1);

	int i;
	Octant * Result = NULL;
	deVec3d & StartMin = Start->Min;
	deVec3d & StartMax = Start->Max;
	for (i = 0; i < 4; i++)
	{
		if (!Possibles[i])
			continue;
		deVec3d & TempMin = Possibles[i]->Min;
		deVec3d & TempMax = Possibles[i]->Max;
		switch (N)
		{
		default:
			return NULL;
		case n_Left:
		case n_Right:
			if ((StartMax.y < TempMax.y || Compare_Epsilon(StartMin.y, TempMin.y)) &&
				(StartMin.y > TempMax.y || Compare_Epsilon(StartMax.y, TempMax.y)) &&
				(StartMax.z < TempMax.z || Compare_Epsilon(StartMin.z, TempMin.z)) &&
				(StartMin.z > TempMax.z || Compare_Epsilon(StartMax.z, TempMax.z)))
			{
				Result = TraceNeighbor(Start, Possibles[i], N, Depth+1);
				if (!Result)
					Result = Possibles[i];
			}
			break;
		case n_Bottom:
		case n_Top:
			if ((StartMax.x < TempMax.x || Compare_Epsilon(StartMin.x, TempMin.x)) &&
				(StartMin.x > TempMax.x || Compare_Epsilon(StartMax.x, TempMax.x)) &&
				(StartMax.z < TempMax.z || Compare_Epsilon(StartMin.z, TempMin.z)) &&
				(StartMin.z > TempMax.z || Compare_Epsilon(StartMax.z, TempMax.z)))
			{
				Result = TraceNeighbor(Start, Possibles[i], N, Depth+1);
				if (!Result)
					Result = Possibles[i];
			}
			break;
		case n_Front:
		case n_Back:
			if ((StartMax.x < TempMax.x || Compare_Epsilon(StartMin.x, TempMin.x)) &&
				(StartMin.x > TempMax.x || Compare_Epsilon(StartMax.x, TempMax.x)) &&
				(StartMax.y < TempMax.y || Compare_Epsilon(StartMin.y, TempMin.y)) &&
				(StartMin.y > TempMax.y || Compare_Epsilon(StartMax.y, TempMax.y)))
			{
				Result = TraceNeighbor(Start, Possibles[i], N, Depth+1);
				if (!Result)
					Result = Possibles[i];
			}
			break;
		}

		if (Result)
			break;
	}

	return Result;
}

deBoolean deSceneOctree::RayTestFromOctant(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo & Collision)
{
	static const deVec3d NeighborNormals[6] = {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};

	deVec3d Dir = End;
	deDouble DistSq = Vec3d_DistSq(Start, End);
	Dir -= Start;
	Vec3d_Normalize(Dir);
	deVec3d LastStart;
	deVec3d Stop;
//	IdeSceneGraph::deCollideInfo TempCollision;
//	deBoolean ParentCollided;

	m_TestNumber++;

	// assert(oct == FindOctant(Start));
	LastStart = Start;
//	IdeSceneNode * Node;
//	void * ptr;
	Neighbor_t N;
	while (oct)
	{
		// decide which direction the next neighbor will be
		// record exit point to do line-segment intersection test
		N = RayToNeighbor(oct, LastStart, Dir, Stop);

		if (Vec3d_DistSq(Start, Stop) > DistSq)
			Stop = End;

#pragma todo( NOT FINISHED )

		if (RayTestNodes(oct, LastStart, Stop, &Collision))
			return deTRUE;

		// now we have to go to the neighbor
		if (oct->Neighbor[N])
			oct = oct->Neighbor[N];
		else
			oct = oct->Parent;

		if (oct)
		{
			// find the deepest octant at the new point
			LastStart = NeighborNormals[N];
			LastStart *= (m_MinSize * 0.5);
			LastStart += Stop;
			oct = FindSubOctant(oct, LastStart);
		}
		LastStart = Stop;
	}

	return deFALSE;
}

#pragma warning (disable : 4100)
deBoolean deSceneOctree::RayTestNodes(Octant * oct, const deVec3d & Start, const deVec3d & End, IdeCollision::deCollideInfo * Collision)
{
	if (!oct)
		return deFALSE;

	if (oct->TestNumber == m_TestNumber)
		return deFALSE;

	IdeSceneRoom * Node;
	void * ptr;

	// test all the nodes in this octant
	ptr = oct->FixedNodes.GetNext(NULL, Node);
	while (ptr)
	{
#pragma todo (do a ray-test on the node between LastStart and Stop)
#pragma todo (go up the tree testing parents node lists also...)

		ptr = oct->FixedNodes.GetNext(ptr, Node);
	}
	ptr = oct->AddedNodes.GetNext(NULL, Node);
	while (ptr)
	{
		//insert same stuff here as above

		ptr = oct->AddedNodes.GetNext(ptr, Node);
	}

	return deFALSE;
}

deBoolean deSceneOctree::RayTestParents(Octant * oct, const deVec3d & Start, const deVec3d & Dir, IdeCollision::deCollideInfo * Collision)
{
#pragma todo(finish me)
	return deFALSE;
}

deSceneOctree::Neighbor_t deSceneOctree::RayToNeighbor(Octant * oct, const deVec3d & RayStart, const deVec3d & RayDir, deVec3d & ExitPoint)
{
// this method figures out which neighbor is "next" along the ray from the one passed in

	static const deVec3d SideNormals[6] = {{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
	int SidesUsed[3];
	deVec3d &Min = oct->Min;
	deVec3d &Max = oct->Max;
	deDouble SideDists[6] = {Min.x, -Max.x, Min.y, -Max.y, Min.z, -Max.z};
	int count;

DEBUG_ONLY(
	if (!Compare_Epsilon(Vec3d_Length(RayDir), 1.0, 0.00001))
		DEBUGRETURN(n_None, "RayToNeighbor: need a normalized direction vector");
);

	count = 0;
	// do some quick tests without doing any math
	if (RayDir.x < 0)
	{
		SidesUsed[count] = (int)n_Left;
		count++;
	}
	else if (RayDir.x > 0)
	{
		SidesUsed[count] = (int)n_Right;
		count++;
	}

	if (RayDir.y < 0)
	{
		SidesUsed[count] = (int)n_Bottom;
		count++;
	}
	else if (RayDir.y > 0)
	{
		SidesUsed[count] = (int)n_Top;
		count++;
	}

	if (RayDir.z < 0)
	{
		SidesUsed[count] = (int)n_Front;
		count++;
	}
	else if (RayDir.z > 0)
	{
		SidesUsed[count] = (int)n_Back;
		count++;
	}

	int i, x;
	deDouble CosAngle, deltaD;
	for (x = 0; x < count; x++)
	{
		i = SidesUsed[x];

		CosAngle = Vec3d_Dot(SideNormals[i], RayDir);
		deltaD = SideDists[i];
		deltaD -= Vec3d_Dot(SideNormals[i], RayStart);

		ExitPoint = RayDir;
		ExitPoint *= deltaD/CosAngle;
		ExitPoint += RayStart;

		if (i < 2)
		{
			// it's on an X-aligned plane, so don't need to test X
			if (ExitPoint.z < Min.z || ExitPoint.z > Max.z || ExitPoint.y < Min.y || ExitPoint.y > Max.y)
				continue;
			return (Neighbor_t)(i);
		}
		else if (i < 4)
		{
			// Y-aligned plane
			if (ExitPoint.x < Min.x || ExitPoint.x > Max.x || ExitPoint.z < Min.z || ExitPoint.z > Max.z)
				continue;
			return (Neighbor_t)(i);
		}
		else
		{
			// Z-aligned plane
			if (ExitPoint.x < Min.x || ExitPoint.x > Max.x || ExitPoint.y < Min.y || ExitPoint.y > Max.y)
				continue;
			return (Neighbor_t)(i);
		}
	}

	return (n_None);
}

int deSceneOctree::DecideChildOctant(Octant * Parent, const deVec3d & Position)
{
	// let's use a reference so we dereference less
	deVec3d &Center = Parent->Center;
	int RetVal = 0;

	if (Position.x > Center.x)	// right
		RetVal += 1;
	//else RetVal += 0;			// left

	if (Position.y > Center.y)	// top
		RetVal += 4;
	//else RetVal += 0;			// bottom


	if (Position.z > Center.z)	// back
		RetVal += 2;
	//else RetVal += 0			// front

	return RetVal;
}

int deSceneOctree::DecideParentOctant(Octant * Child, const deVec3d & Position)
{
	// subtract from 7 to inverse the octant ID
	// shift by 4 to make it a parent
	// add 8 to make sure it's always >= 8
	return ((7 - DecideChildOctant(Child, Position)) << 4) + 8;
}

deSceneOctree::Octant* deSceneOctree::MakeOctant(const deVec3d &Min, const deVec3d &Max, Octant * ParentChild, int ParentID)
{
	int i;
	// make an Octant to play with
	Octant * oct = new Octant;

	// allocation failed, uh-oh
	if (!oct)
		return NULL;
	
	oct->CanBeRemoved = deFALSE;
	oct->NeighborRefs = 0;
	oct->TestNumber = 0;

	// set the min & max
	oct->Min = Min;
	oct->Max = Max;

	// set the center (avg of min & max)
	FindCenter(Min, Max, oct->Center);

	// NULL out the children
	for (i = 0; i < 8; i++)
		oct->Child[i] = NULL;
	
	// and the neighbors
	for (i = 0; i < 6; i++)
		oct->Neighbor[i] = NULL;
	
	oct->Parent = NULL;
	oct->ParentIndex = -1;

	// ParentID = [0-7] oct becomes a child of ParentChild, at index ParentID
	if (ParentID < 8)
	{
		// no invalid indices, please
		if (ParentID < 0)
			DEBUGRETURN(NULL, "MakeOctant: invalid parent index");
		// no mem-leaks, thank you
		if (ParentChild && ParentChild->Child[ParentID])
			DEBUGRETURN(NULL, "MakeOctant: imminent memory leak");
		// this octant's parent is ParentChild
		oct->Parent = ParentChild;
		// and we will be stored at 
		oct->ParentIndex = ParentID;
		// might be creating the root node, so Parent would be NULL
		if (ParentChild)
			ParentChild->Child[ParentID] = oct;
	}
	else if (ParentID < 256)
	{
		// disjointed linkages are bad. only create new parents for orphans
		if (ParentChild && ParentChild->Parent)
			DEBUGRETURN(NULL, "MakeOctant: trying to create a parent when child is not orphaned");
		// shift by value of 8
		ParentID = ParentID >> 4;
		// ParentChild becomes a child of the new octant, at index ParentID
		if (ParentChild)
		{
			ParentChild->Parent = oct;
			ParentChild->ParentIndex = ParentID;
			oct->Child[ParentID] = ParentChild;
		}
	}

	return oct;
}

deSceneOctree::Octant * deSceneOctree::MakeSubOctant(Octant * ParentChild, int ParentID)
{
	// this one needs a reference
	if (!ParentChild)
		return NULL;

	deVec3d Min, Max;
	// no invalid indices, please
	if (ParentID < 0 || ParentID >= 256)
		DEBUGRETURN(NULL, "MakeSubOctant: invalid parent index");

	// let's do some fancy math to figure out which coords to take for min & max
	// refer to the octant diagram at the top of this file to see where all this comes from
	if (ParentID < 8)
	{
		// ID less than 8 means we are making a child
		if (ParentID % 2 == 0)	// left
		{
			Min.x = ParentChild->Min.x;
			Max.x = ParentChild->Center.x;
		}
		else					// right
		{
			Min.x = ParentChild->Center.x;
			Max.x = ParentChild->Max.x;
		}
		
		if (ParentID < 4)			// bottom
		{
			Min.y = ParentChild->Min.y;
			Max.y = ParentChild->Center.y;
		}
		else					// top
		{
			Min.y = ParentChild->Center.y;
			Max.y = ParentChild->Max.y;
		}
		
		if ((ParentID % 4) < 2)	// front
		{
			Min.z = ParentChild->Min.z;
			Max.z = ParentChild->Center.z;
		}
		else					// back
		{
			Min.z = ParentChild->Center.z;
			Max.z = ParentChild->Max.z;
		}
	}
	else
	{
		// ID more than 8 means we are making a parent (usually for a node that wasn't big enough to contain something)
		int tempID;
		deVec3d Diff;
		
		tempID = ParentID >> 4;
		Diff = ParentChild->Max;
		Diff -= ParentChild->Min;

		if (tempID % 2 == 0)	// left
		{
			Min.x = ParentChild->Min.x;
			Max.x = ParentChild->Max.x + Diff.x;
		}
		else					// right
		{
			Min.x = ParentChild->Min.x - Diff.x;
			Max.x = ParentChild->Max.x;
		}
		
		if (tempID < 4)			// bottom
		{
			Min.y = ParentChild->Min.y;
			Max.y = ParentChild->Max.y + Diff.y;
		}
		else					// top
		{
			Min.y = ParentChild->Min.y - Diff.y;
			Max.y = ParentChild->Max.y;
		}
		
		if ((tempID % 4) < 2)	// front
		{
			Min.z = ParentChild->Min.z;
			Max.z = ParentChild->Max.z + Diff.z;
		}
		else					// back
		{
			Min.z = ParentChild->Min.z - Diff.z;
			Max.z = ParentChild->Max.z;
		}
	}

	return MakeOctant(Min, Max, ParentChild, ParentID);
}

deBoolean deSceneOctree::RemoveOctant(Octant * oct, deTList <IdeSceneRoom*> * DumpList, deBoolean RemoveChildren, deBoolean IgnoreNeighbors)
{
	// kinda hard to remove an octant if we don't have one to remove
	if (!oct)
		return deFALSE;

	// don't go removing octants that are still pointed-to
	if (oct->NeighborRefs > 0)
	{
		int N1, N2;
		for (N1 = 0; N1 < 6; N1++)
		{
			N2 = N1 ^ 0x01;
			if (oct->Neighbor[N1])
			{
				if (oct->Neighbor[N1] == oct->Parent)
				{
				}
				else if (oct->Neighbor[N1]->Neighbor[N2] == oct)
				{
					oct->Neighbor[N1]->Neighbor[N2] = NULL;
				}
				else if (!IgnoreNeighbors)
					return deFALSE;
			}
		}
	}
	
	int i;
	// loop through all our children
	for (i = 0; i < 8; i++)
	{
		// if we have a child, we want to remove it to avoid memory leaks
		if (oct->Child[i])
		{
			if (RemoveChildren)
			{
				// fail if we can remove child but fail to
				if (!RemoveOctant(oct->Child[i], DumpList, RemoveChildren))
					return deFALSE;
				continue;
			}
			// fail if we have a child and can't remove it
			else
				return deFALSE;
		}
	}
	
	// if the list to dump to is specified, we'll dump out all our nodes into it to avoid mem leaks
	if (DumpList)
	{
		DumpList->MergeList(oct->AddedNodes);
		DumpList->MergeList(oct->FixedNodes);
	}
	else
	{
		// if we don't have a list, we have to release the nodes to free the mem
		IdeSceneRoom * node;
		void * ptr;
		ptr = oct->AddedNodes.GetNext(NULL, node);
		while (ptr)
		{
			// loop through our linked list and release each node
			if (node)
			{
				node->Release();
			}
			ptr = oct->AddedNodes.GetNext(ptr, node);
		}
		ptr = oct->FixedNodes.GetNext(NULL, node);
		while (ptr)
		{
			// loop through our linked list and release each node
			if (node)
			{
				node->Release();
			}
			ptr = oct->FixedNodes.GetNext(ptr, node);
		}
	}
	
	// let all our neighbors know that we're no longer pointing at them
	for (i = 0; i < 6; i++)
	{
		if (oct->Neighbor[i])
			(oct->Neighbor[i]->NeighborRefs)--;
	}

	// if we aren't a root-node, must inform parent of our destruction
	if (oct->Parent)
		oct->Parent->Child[oct->ParentIndex] = NULL;
	
	// finally delete the thing
	delete oct;
	
	return deTRUE;
}

deSceneOctree::Octant* deSceneOctree::FindOctant(const deVec3d &Position)
{
	// no root, no good
	if (!m_Root || !TestOctantPoint(m_Root, Position))
		return NULL;

	// it's in the root, so do a recursive search on it
	return FindSubOctant(m_Root, Position);
}

deSceneOctree::Octant* deSceneOctree::FindSubOctant(Octant * oct, const deVec3d &Position)
{
	int i;
	i = DecideChildOctant(oct, Position);
	#ifdef _DEBUG
	if (i >= 0 && i < 8)
	#endif
	{
		if (oct->Child[i])
		{
			// if this child contains the point, it might have more specific children
			//if (TestOctantPoint(oct->Child[i], Position))
			{
				return FindSubOctant(oct->Child[i], Position);
			}
		}
	}
	// no children to contain the point, so just return the current one
	return oct;
}

deSceneOctree::Octant* deSceneOctree::FindOctant(const deVec3d &Min, const deVec3d &Max)
{
	// no root, no good
	if (!m_Root)
		return NULL;
	// both points gotta be in the root octant
	if (!TestOctantBBox(m_Root, Min, Max))
		return NULL;

	return FindSubOctant(m_Root, Min, Max);
}

deSceneOctree::Octant* deSceneOctree::FindSubOctant(Octant * oct, const deVec3d &Min, const deVec3d &Max)
{
	int i;
	// only use one of the values, they both have to be inside the same child
	i = DecideChildOctant(oct, Min);
	if (i != DecideChildOctant(oct, Max))
		return oct;
	#ifdef _DEBUG
	if (i >= 0 && i < 8)
	#endif
	{
		if (oct->Child[i])
		{
			// if this child contains the bbox, it might have more specific children
			//if (TestOctantBBox(oct->Child[i], Min, Max))
			{
				return FindSubOctant(oct->Child[i], Min, Max);
			}
		}
	}
	// no children to contain the bbox, so just return the current one
	return oct;
}

deBoolean deSceneOctree::TestOctantPoint(Octant * oct, const deVec3d &Position)
{
	// no octant, no good
	if (!oct)
		return deFALSE;
	
	// if the point is below any min value, it's outside
	if (Position.x < oct->Min.x || Position.y < oct->Min.y || Position.z < oct->Min.z)
		return deFALSE;

	// if the point is above any max value, it's outside
	if (Position.x > oct->Max.x || Position.y > oct->Max.y || Position.z > oct->Max.z)
		return deFALSE;

	// otherwise, it's inside
	return deTRUE;
}

deBoolean deSceneOctree::TestOctantBBox(Octant * oct, const deVec3d &Min, const deVec3d &Max)
{
	// no octant, no good
	if (!oct)
		return deFALSE;

	// if the bbox extends in any direction outside the octant, it's not inside
	if (Min.x < oct->Min.x || Min.y < oct->Min.y || Min.z < oct->Min.z)
		return deFALSE;
	if (Max.x > oct->Max.x || Max.y > oct->Max.y || Max.z > oct->Max.z)
		return deFALSE;

	// otherwise, it's inside
	return deTRUE;
}

