///////////////////////////////////////////////////////////////////////////////
/// @file deScene.cpp
///
/// @brief scene-management routines
///
/// @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 Mar 2002
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "deScene_priv.hpp"
#include "deMath.hpp"
#include "deCamera.hpp"
#include "dePortal.hpp"
#include "deRender.hpp"
#include "deOctree.hpp"
#include "deBoundingVolumes.hpp"

// 100K pixels makes an occluder ... (?)
#define MIN_OCCLUDER_SIZE (100000)

IdeVertexBuffer * s_AABB_VB = NULL;
IdeVertexBuffer * s_OBB_VB = NULL;

static deSceneGraph*  s_pSceneGraph = NULL;
IdeSceneGraph* IdeSceneGraph_GetSceneGraphPtr()
{
	if (!s_pSceneGraph)
		DEBUGRETURN(NULL, "IdeSceneGraph_GetSceneGraphPtr: Call IdeScene_Initialize first");
	return s_pSceneGraph;
}

IdeCollision* IdeCollision_CreateCollision()
{
	return new deCollision;
}

deBoolean IdeScene_Initialize()
{
	s_pSceneGraph = new deSceneGraph;
	if (!s_pSceneGraph)
		DEBUGRETURN(deFALSE, "IdeScene_Initialize: failed to create SceneGraph");
	
	if (!IdeSceneRoom_Initialize())
		DEBUGRETURN(deFALSE, "IdeScene_Initialize: IdeSceneRoom_Initialize() failed");
	if (!IdeSceneObject_Initialize())
		DEBUGRETURN(deFALSE, "IdeScene_Initialize: IdeSceneObject_Initialize() failed");

	{
		// create the AABB & OBB vertex buffers
		int i,j;
		IdeVertexBuffer * VB;
		s_AABB_VB = IdeVertexBuffer_CreateVBuffer();
		s_OBB_VB = IdeVertexBuffer_CreateVBuffer();
		
		deAABB bbox = {{0,0,0},{1,1,1}};
		deOBB obb;
		deVec3d VecArray[8];
		deVertex *VecBuffer;
		deARGB *ColBuffer;
		short *IBuffer;
		
		deGeometry::MakeOBBFromAABB(bbox, deTransform(), obb);
		deGeometry::GetPointsOfOBB(obb, VecArray);
		
		VB = s_AABB_VB;
		for (i = 0; i < 2; ++i)
		{
			VB->Lock();
			VB->CreateBuffer(IdeVertexBuffer::BUFFER_POSITION, deFALSE);
			VB->CreateBuffer(IdeVertexBuffer::BUFFER_DIFFUSE, deFALSE);
			VB->CreateBuffer(IdeVertexBuffer::BUFFER_INDICES16, deFALSE);
			VB->SetBufferSize(8, deFALSE);
			VB->SetBufferSize(24, deTRUE);
			VB->SetRenderType(IdeVertexBuffer::RENDER_LINELIST);
			
			VecBuffer = (deVertex*)VB->GetBuffer(IdeVertexBuffer::BUFFER_POSITION);
			ColBuffer = (deARGB*)VB->GetBuffer(IdeVertexBuffer::BUFFER_DIFFUSE);
			IBuffer = (short*)VB->GetBuffer(IdeVertexBuffer::BUFFER_INDICES16);
			
			for (j = 0; j < 8; ++j)
			{
				// blue for AABB, red for OBB
				ColBuffer[j] = (i == 0) ? 0x800000ff : 0x80ff0000;
				VecBuffer[j] = deMake_Vertex(VecArray[j]);
			}
			
			IBuffer[0] = IBuffer[7] = IBuffer[16] = 0;
			IBuffer[1] = IBuffer[2] = IBuffer[18] = 1;
			IBuffer[4] = IBuffer[3] = IBuffer[20] = 3;
			IBuffer[5] = IBuffer[6] = IBuffer[22] = 2;
			IBuffer[8]  = IBuffer[15] = IBuffer[17] = 4;
			IBuffer[9]  = IBuffer[10] = IBuffer[19] = 5;
			IBuffer[12] = IBuffer[11] = IBuffer[21] = 7;
			IBuffer[13] = IBuffer[14] = IBuffer[23] = 6;
			
			VB->Unlock();
			
			VB = s_OBB_VB;
		}
	}

	return deTRUE;
}

void IdeScene_ShutDown()
{
	if (s_AABB_VB)
		s_AABB_VB->Release();
	if (s_OBB_VB)
		s_OBB_VB->Release();
	s_AABB_VB = NULL;
	s_OBB_VB = NULL;

	IdeSceneRoom_ShutDown();
	IdeSceneObject_ShutDown();

	delete s_pSceneGraph;
}


//=============================================================
// deSceneGraph
//=============================================================

deSceneGraph::deSceneGraph()
{
	m_CurrentPassNum = 1;
	m_SphereCullFront = m_SphereCullBack = NULL;
	m_NumOccluders = 0;
	m_CurrentCamera = NULL;
	m_MinPixelCull = 5;

	m_CullFlags = 0;
	m_CullFlags |= deCullFrustum;
//	m_CullFlags |= deCullDetail;
//	m_CullFlags |= deCullOccludeSphere;
	m_CullFlags |= deCullFarPlaneOptimize;

	m_DebugFlags = 0;
//	m_DebugFlags |= deDrawAABB;
//	m_DebugFlags |= deDrawOBB;
//	m_DebugFlags |= deDrawSpatialPartition;
}

deSceneGraph::~deSceneGraph()
{
	IdeSceneRoom * Room1 = NULL;
	IdeSceneRoom * Room2 = NULL;
	void * ptr;

	ptr = m_Rooms.GetNext(NULL, Room1);
	while (ptr)
	{
		// cache the next one, because releasing the current one could/should remove it from the list
		ptr = m_Rooms.GetNext(ptr, Room2);

		if (Room1)
			(Room1)->Release();

		Room1 = Room2;

	}
//	m_Octree->Release();
}

long deSceneGraph::Traverse(deSceneTraversal* Params)
{
	if (Params->cam == NULL)
		DEBUGRETURN(0, "Traverse: Params->cam was NULL");
	if (Params->render == NULL)
		DEBUGRETURN(0, "Traverse: Params->render was NULL");
	if (Params->MaxTPortalDepth < 0 || Params->MaxTPortalDepth > 100) // just an arbitrary "high" number for MaxTPortalDepth
		DEBUGRETURN(0, "Traverse: MaxTPortalDepth value invalid");
	IdeSceneObject * so;
	//deFrustum f;
	IdePlaneFrustum* f;
	IdeSceneRoom * StartRoom = NULL;
	int RenderedPolys = 0;
	void * ptr;
	
	f = IdeFrustum_CreatePlaneFrustum();
	m_CurrentPassNum++;
	Params->cam->BuildRootFrustum(f);
	m_Objects.EmptyList();
	m_SphereCullFront = m_SphereCullBack = NULL;
	m_NumOccluders = 0;
	m_CurrentCamera = Params->cam;
	
	((deTransform*)( &(m_CurrentCamera->Position()) ))->GetIn(m_CurrentCamFwd);
	Vec3d_Normalize(m_CurrentCamFwd);
	
/*
	if (m_DebugFlags & deDrawSpatialPartition)
	{
		IdeRender::deRenderObject obj;
		memset(&obj, 0, sizeof(IdeRender::deRenderObject));
		
		((deTransform&)obj.Transform).Reset();
		
		// remove all empty octants
		//m_Octree->CleanUp();
		obj.VB = m_Octree->GetVB(1000);
		obj.Lights[0] = NULL;
		Params->render->RenderPrepBuffer(obj);
	}
*/

	// set up the starting temporary and return values
	Params->CurrentPortalDepth = 0;
	Params->CurrentPassNum = m_CurrentPassNum;
	Params->CurrentSceneGraph = this;
	if (m_CullFlags & IdeSceneGraph::deCullFarPlaneOptimize)
		Params->FarthestDistanceFound = Params->cam->GetNearClip()*10;
	else
		Params->FarthestDistanceFound = Params->cam->GetFarClip();
	Params->CurrentFrustum = f;
	((deTransform&)Params->CurrentTransform).Reset();
	
	//find starting room
#pragma todo(make scenegraph really find correct starting room)
	
	// for now we'll just do it for each room
	ptr = m_Rooms.GetNext(NULL, StartRoom);
	while (ptr) // no, we'll do it for the first one added -using if instead of while
	{
		RenderedPolys += StartRoom->Traverse(Params);
		ptr = m_Rooms.GetNext(ptr, StartRoom);
	}
	
	// new stuff (optimized for multi-pass)
	if (m_CullFlags & deCullDetail)
		DetailCullObjects(m_MinPixelCull);
	if (m_CullFlags & deCullOccludeSphere)
		OcclusionSphereCullObjects();
	
	// render all the non-culled objects
	deTList<IdeSceneObject*>::iterator objIt = m_Objects.begin();
	deTList<IdeSceneObject*>::iterator objEnd = m_Objects.end();
	for (; objIt != objEnd; ++objIt)
	{
		so = *objIt;
		RenderedPolys += so->Traverse(Params);
	}
	
	f->Release();
	CleanUpSphereCullList();
	m_Objects.EmptyList();
	return RenderedPolys;
}

deBoolean deSceneGraph::SetCullFlags(long CullFlags)
{
	if (CullFlags < 0 || CullFlags > deCull_Max)
		DEBUGRETURN(deFALSE,"SetCullFlags: invalid cull flag value");
	m_CullFlags = CullFlags;
	return deTRUE;
}

long deSceneGraph::GetCullFlags()
{
	return m_CullFlags;
}

deBoolean deSceneGraph::SetDebugFlags(long DebugFlags)
{
	if (DebugFlags < 0 || DebugFlags > deDebugFlag_Max)
		DEBUGRETURN(deFALSE,"SetDebugFlags: invalid debug flag value");
	m_DebugFlags = DebugFlags;
	return deTRUE;
}

long deSceneGraph::GetDebugFlags()
{
	return m_DebugFlags;
}

IdeSceneRoom * deSceneGraph::FindRoomWithID(deWorldID WorldID, deObjectID ObjectID)
{
	IdeWorld * pWorld;
	IdeWorldObject * pWO = NULL;
	IdeSceneRoom * pSR = NULL;

	if (WorldID == 0 || ObjectID == 0)
		return NULL;

	pWorld = IdeWorld_GetManager()->GetWorld(WorldID);
	if (!pWorld)
		return NULL;

	pWO = pWorld->GetWorldObject(ObjectID);
	if (!pWO)
		return NULL;

	pSR = (IdeSceneRoom*)(pWO->GetWOInterface(IdeSceneRoom_GetWOInterfaceID()));

	return pSR;
}

deBoolean deSceneGraph::AddRoom(IdeSceneRoom * Room)
{
	if (!Room)
		return deFALSE;

	Room->Claim();

	void * ptr = m_Rooms.AddElement(Room);
	if (!ptr)
		return deFALSE;

	Room->SetRoomListPtr(ptr);

	return deTRUE;
}

//#pragma todo (unfinished function: deSceneGraph::RemoveNode) // done
deBoolean deSceneGraph::RemoveRoom(IdeSceneRoom* Room)
{
	if (!Room)
		return deFALSE;

	void * ptr;
	ptr = Room->GetRoomListPtr();
	if (ptr)
	{
		if (!m_Rooms.RemoveElement(ptr))
			return deFALSE;
		Room->Release();
	}
	Room->SetRoomListPtr(NULL);

	return deTRUE;
}

deBoolean deSceneGraph::AddSceneObject(IdeSceneObject* Object)
{
	if (!Object)
		return deFALSE;
	if (Object->GetSOIType() == IdeSceneObject::iface_IdeSceneLight)
		return m_LightTree.AddObject(Object);
	else
		return m_ObjectTree.AddObject(Object);
}

void deSceneGraph::RemoveSceneObject(IdeSceneObject* Object)
{
	if (Object->GetSOIType() == IdeSceneObject::iface_IdeSceneLight)
		m_LightTree.RemoveObject(Object);
	else
		m_ObjectTree.RemoveObject(Object);
}

void deSceneGraph::RepositionSceneObject(IdeSceneObject* Object)
{
	if (Object->GetSOIType() == IdeSceneObject::iface_IdeSceneLight)
		m_LightTree.RepositionObject(Object);
	else
		m_ObjectTree.RepositionObject(Object);
}

void deSceneGraph::AddObjectList(deTList <IdeSceneObject*> &list)
{
	if (m_CullFlags & (deCullDetail | deCullOccludeSphere))
		BuildSphereCullList(list);
	m_Objects.MergeList(list);
}

deBoolean deSceneGraph::PointsOccluded(deVec3d points[], long num)
{
	if (!(m_CullFlags & deCullOccludeSphere))
		return deFALSE;
	deBoolean isOccluded = deTRUE;
	cull_sphere_t * sphere;
	deDouble z, oneoverz, radiussq;
	deVec3d campos, pointpos, xycomp;
	int i, j;

	campos = m_CurrentCamera->Position().Translation;

	j = 0;
	sphere = m_SphereCullFront;
	while (sphere && j < m_NumOccluders)
	{
		radiussq = sphere->occluderadius;
		radiussq *= radiussq;
		for (i = 0; isOccluded && i < num; i++)
		{
			pointpos = points[i] - campos;
			z = Vec3d_Dot(m_CurrentCamFwd, pointpos);
			if (z < sphere->zval)
			{
				isOccluded = deFALSE;
				break;
			}
			if (m_CurrentCamera->IsOrtho())
				oneoverz = 1;
			else
				oneoverz = 1/z;
			xycomp = pointpos - (m_CurrentCamFwd * z);
			pointpos = xycomp * oneoverz;
			if (Vec3d_DistSq(sphere->occludecenter, pointpos) > radiussq)
				isOccluded = deFALSE;
		}
		sphere = sphere->next;
		j++;
	}

	return isOccluded;
}

deBoolean deSceneGraph::PortalOccluded(IdePortal * portal)
{
	deVec3d * points;
	long num;
	points = portal->GetVertices(num);
	return PointsOccluded(points, num);
}

void deSceneGraph::BuildSphereCullList(deTList <IdeSceneObject*> &list)
{
	if (!(m_CullFlags & (deCullDetail | deCullOccludeSphere)))
		return;

	IdeSceneObject * so;
	void * ptr;
	deBoolean isOccluder;
	cull_sphere_t * sphere;
	deVec3d camfwd, campos;
	deDouble z, oneoverz, minradius;
	deVec3d xycomp;
	
	campos = m_CurrentCamera->Position().Translation;
	camfwd = m_CurrentCamFwd;

	{
		deDouble projplane;
		deRect r;
		r = m_CurrentCamera->GetRect();
		if (m_CurrentCamera->IsOrtho())
		{
			#pragma todo(handle ortho projection plane)
			projplane = m_CurrentCamera->GetOrthoWidth();
			projplane = (r.Right - r.Left) / projplane;
		}
		else
		{
			projplane = tan(DEG2RAD(m_CurrentCamera->GetFOV()/2)) * 2;
			projplane = (r.Right - r.Left) / projplane;
		}
		minradius = sqrt(MIN_OCCLUDER_SIZE / DE_PI) / projplane;
	}

	// foreach object:
	//  calc projected sphere size (plane dist = 1)
	//  if (size > min_occluder) add to front of list, increment numoccluders
	//  else add to back of list
	ptr = list.GetNext(NULL, so);
	while (ptr)
	{
		isOccluder = deFALSE;
		sphere = new cull_sphere_t;
		
		if (m_CullFlags & deCullOccludeSphere)
		{
			// goin all the way!
			sphere->occludecenter = so->GetWorldOccludeCenter() - campos;
			z = Vec3d_Dot(camfwd, sphere->occludecenter);
			if (z < 0 || so->IsTransparent())
			{
				// objects with center behind us can't reliably occlude stuff in front of us
				// neither can objects that are transparent
				// they might still be visible however, so let's keep em in the scene
				// not putting them in the spherecull list means they can't be culled
				ptr = list.GetNext(ptr, so);
				delete sphere;
				continue;
			}
			if (m_CurrentCamera->IsOrtho())
				oneoverz = 1;
			else
				oneoverz = 1/z;
			xycomp = sphere->occludecenter - (camfwd * z);
			sphere->occludecenter = xycomp * oneoverz;
			sphere->occluderadius = so->GetOccludeRadius() * oneoverz;
			sphere->zval = z;

			sphere->boundcenter = so->GetWorldBoundCenter() - campos;
			z = Vec3d_Dot(camfwd, sphere->boundcenter);
			if (m_CurrentCamera->IsOrtho())
				oneoverz = 1;
			else
				oneoverz = 1/z;
			xycomp = sphere->boundcenter - (camfwd * z);
			sphere->boundcenter = xycomp * oneoverz;
			sphere->boundradius = so->GetBoundRadius() * oneoverz;
			if (sphere->boundradius < 0)
				sphere->boundradius *= -1;
			sphere->zval = max(z, sphere->zval);

			if (sphere->boundradius > minradius)
				isOccluder = deTRUE;
		}
		else
		{
			// only doing a detail cull
			sphere->boundcenter = so->GetWorldBoundCenter() - campos;
			z = Vec3d_Dot(camfwd, sphere->boundcenter);
			if (m_CurrentCamera->IsOrtho())
				oneoverz = 1;
			else
				oneoverz = 1/z;
			sphere->boundradius = so->GetBoundRadius() * oneoverz;
			if (sphere->boundradius < 0)
				sphere->boundradius *= -1;
			sphere->zval = z;
		}

		sphere->object = so;
		sphere->listptr = ptr;
		if (isOccluder)
		{
			m_NumOccluders++;
			sphere->next = m_SphereCullFront;
			m_SphereCullFront = sphere;
			if (!m_SphereCullBack)
				m_SphereCullBack = sphere;
		}
		else
		{
			if (m_SphereCullBack)
			{
				m_SphereCullBack->next = sphere;
				m_SphereCullBack = sphere;
				sphere->next = NULL;
			}
			else
			{
				m_SphereCullFront = sphere;
				m_SphereCullBack = sphere;
				sphere->next = NULL;
			}
		}

		ptr = list.GetNext(ptr, so);
	}
}

void deSceneGraph::CleanUpSphereCullList()
{
	cull_sphere_t *temp, *temp2;
	temp = m_SphereCullFront;
	while (temp)
	{
		temp2 = temp->next;
		delete temp;
		temp = temp2;
	}
}

int deSceneGraph::DetailCullObjects(deDouble MinPixels)
{
	int StartLength = m_Objects.Length();
	int i;
	cull_sphere_t * sphere;
	deDouble minradius;
	{
		deDouble projplane;
		deRect r;
		r = m_CurrentCamera->GetRect();
		if (m_CurrentCamera->IsOrtho())
		{
			projplane = m_CurrentCamera->GetOrthoWidth();
			projplane = (r.Right - r.Left) / projplane;
		}
		else
		{
			projplane = tan(DEG2RAD(m_CurrentCamera->GetFOV()/2)) * 2;
			projplane = (r.Right - r.Left) / projplane;
		}
		minradius = sqrt(MinPixels / DE_PI) / projplane;
	}

	i = 0;
	sphere = m_SphereCullFront;
	while (sphere)
	{
		if (sphere->boundradius < minradius)
		{
			m_Objects.RemoveElement(sphere->listptr);
			if (i < m_NumOccluders)
			{
				m_NumOccluders--;
				i--;
			}
		}
		i++;
		sphere = sphere->next;
	}
	return m_Objects.Length() - StartLength;
}

int deSceneGraph::OcclusionSphereCullObjects()
{
	if (m_NumOccluders <= 0)
		return 0;

	int StartLength = m_Objects.Length();
	cull_sphere_t *occluder, *occludee, *temp, *occluder_end;
	deDouble radiussq;
	int i, j;

	// have occluders occlude each other first, to reduce amount of processing later
	j = 0;
	occluder = m_SphereCullFront;
	while (occluder)
	{
		i = 0;
		occludee = m_SphereCullFront;
		if (!occludee)
			break;
		temp = NULL;
		while (occludee)
		{
			if (occludee->zval > occluder->zval) // also handles occludee == occluder
			{
				radiussq = occluder->occluderadius - occludee->boundradius;
				if (radiussq > 0)
				{
					radiussq = radiussq * radiussq;
					if (Vec3d_DistSq(occluder->occludecenter, occludee->boundcenter) < radiussq)
					{
						j--;
						m_NumOccluders--;
						m_Objects.RemoveElement(occludee->listptr);
						if (temp == NULL)
							m_SphereCullFront = occludee->next;
						else
							temp->next = occludee->next;
						delete occludee;
						if (temp == NULL)
							occludee = m_SphereCullFront;
						else
							occludee = temp->next;
						if (m_NumOccluders <= i)
							break;
						continue;
					}
				}
			}
			i++;
			if (i >= m_NumOccluders)
				break;
			temp = occludee;
			occludee = occludee->next;
		}
		j++;
		if (j >= m_NumOccluders)
			break;
		occluder = occluder->next;
	}
	if (!occluder)
		return m_Objects.Length() - StartLength;
	occluder_end = m_SphereCullFront;
	for (i = 1; i < m_NumOccluders; i++)
		occluder_end = occluder_end->next;

	j = 0;
	occluder = m_SphereCullFront;
	while (occluder)
	{
		i = j+1;
		occludee = occluder_end->next;
		if (!occludee)
			break;
		temp = occluder_end;
		while (occludee)
		{
			radiussq = occluder->occluderadius - occludee->boundradius;
			if (radiussq > 0)
			{
				radiussq = radiussq * radiussq;
				if (Vec3d_DistSq(occluder->occludecenter, occludee->boundcenter) < radiussq)
				{
					if (i < m_NumOccluders)
					{
						j--;
						i--;
						m_NumOccluders--;
					}
					m_Objects.RemoveElement(occludee->listptr);
					temp->next = occludee->next;
					delete occludee;
					occludee = temp->next;
					continue;
				}
			}
			i++;
			temp = occludee;
			occludee = occludee->next;
		}
		j++;
		if (j >= m_NumOccluders)
			break;
		occluder = occluder->next;
	}

	return m_Objects.Length() - StartLength;
}

#pragma todo(unfinished function TestIntersection)
DWORD deSceneGraph::TestIntersection(const deVec3d& Position, 
									 const deVec3d* Mins, 
									 const deVec3d* Maxs)
{
	deTList <IdeSceneRoom*> RoomList;
	IdeSceneRoom *	pRoom;
	void *			ptr;
	DWORD			ContentsFound, dwTemp;
	deVec3d			LocalMin, LocalMax;
/*
	if (Mins && Maxs)
	{
		LocalMin = *Mins;
		LocalMax = *Maxs;
		LocalMin += Position;
		LocalMax += Position;
		if (!m_Octree->FindIntersectingNodes(RoomList, &LocalMin, &LocalMax))
			return 0;
	}
	else
	{
		if (!m_Octree->FindIntersectingNodes(RoomList, NULL, NULL))
			return 0;
	}
*/
	ContentsFound = deContentsNone;
	ptr = RoomList.GetNext(NULL, pRoom);
	while (ptr)
	{
		dwTemp = pRoom->GetContents();
		ContentsFound &= dwTemp;

		ptr = RoomList.GetNext(ptr, pRoom);
	}

	return ContentsFound;
}

#pragma todo(unfinished function TestCollision)
deBoolean deSceneGraph::TestCollision(const IdeCollision::deCollideParams & Params, IdeCollision * Collision)
{
	deTList <IdeSceneRoom*> RoomList;
	IdeSceneRoom *	pRoom;
	void *			ptr;
	deBoolean		CollisionFound;

#pragma todo (fix this code when spatial division is working)
	{
		IdeSceneRoom * Room;
		if (m_Rooms.GetNext(NULL, Room))
			RoomList.AddElement(Room);
	}

	CollisionFound = deFALSE;

	ptr = RoomList.GetNext(NULL, pRoom);
	while (ptr)
	{
		if (pRoom->TestCollision(Params, Collision))
			CollisionFound = deTRUE;

		ptr = RoomList.GetNext(ptr, pRoom);
	}

	return CollisionFound;
}

void deSceneGraph::ObjectExtents(IdeBoundingVolume* volume, IdeCollision * Results)
{
#pragma todo(test deSceneGraph::ObjectExtents)
	deTList<IdeSceneObject*> out;
	m_ObjectTree.IntersectionTest(volume, out);

	Results->Reset();
	deTList<IdeSceneObject*>::iterator it = out.begin(),
		end = out.end();
	for (; it != end; ++it)
	{
		IdeSceneObject* object = *it;
		if (object)
		{
            if (object->GetActivation(IdeSceneObject::activate_collide))
            {
                IdeCollision::deCollideInfo info;
                memset(&info, 0, sizeof(IdeCollision::deCollideInfo));
                info.HitObject = object;
                Results->AddCollision(info);
            }
		}
	}
}

long deSceneGraph::LightExtents(const deVec3d& pos, const deAABB& bbox, IdeSceneLight** outBuffer, long bufferSize)
{
	IdeBoundingVolume* BV = IdeBoundingVolume_Create(IdeBoundingVolume::BVType_AABB);
	{
		IdeBV_AABB* BV_AABB = (IdeBV_AABB*)BV->GetBVInterface(IdeBoundingVolume::BVType_AABB);
		BV_AABB->SetPosition(pos);
		BV_AABB->SetBBox(bbox);
	}
	deTList<IdeSceneObject*> out;
	m_LightTree.IntersectionTest(BV, out);
	BV->Release();

	int numthings = out.size();
	if (!outBuffer || numthings == 0)
		return numthings;
	
	int k;
	deTList<IdeSceneObject*>::iterator it = out.begin(),
		end = out.end();
	for (k = 0; k < bufferSize && it != end; ++it)
	{
		IdeSceneObject* object = *it;
		IdeSceneLight* light = (IdeSceneLight*)object->GetSOInterface(IdeSceneObject::iface_IdeSceneLight);
		if (light)
		{
			outBuffer[k] = light;
			++k;
		}
	}
	return numthings;
}


//=====================================================
//
// deCollision
//
//=====================================================
deCollision::deCollision()
{
}

deCollision::~deCollision()
{
}


long deCollision::Release()
{
	delete this;
	return 0;
}

void deCollision::Reset()
{
	m_Collisions.ResizeQuick(0);
}

long deCollision::GetNumCollisions()
{
	return m_Collisions.Length();
}

void deCollision::GetCollision(long ColNum, deCollideInfo & collision)
{
	collision = m_Collisions[ColNum];
}

deBoolean deCollision::AddCollision(const deCollideInfo & collision)
{
	if (collision.Percent < 0 || collision.Percent > 1)
		DEBUGRETURN(deFALSE,"collision does not occur in valid range");

	long i;
	m_Collisions.IncrementSizeQuick();
	for (i = m_Collisions.Length()-1; i > 0; --i)
	{
		if (m_Collisions[i-1].Percent > collision.Percent)
		{
			m_Collisions[i] = m_Collisions[i-1];
		}
		else
		{
			break;
		}
	}
	m_Collisions[i] = collision;
	return deTRUE;
}

#pragma todo(deTest the dePravity of non-Destiny engines)
#pragma todo(deSpair should Destiny dePress you instead of deLighting you)
#pragma todo(dePrecate and deFile other engines which deSire to dePrive us of more members)

