/*
	CBoundingBoxTree.cpp

	Implementation of top level CBoundingBoxTree class
*/
#include "stdafx.h"
#include "BoundingBoxTree.h"


//********************************************
// Constructor
//********************************************
CBoundingBoxTree::CBoundingBoxTree()
{
	m_objectsFaces = NULL;
	m_leftTree = NULL;
	m_rightTree = NULL;
}

//********************************************
// Destructor
//********************************************
CBoundingBoxTree::~CBoundingBoxTree()
{
	delete(m_pBox);
	if (m_leftTree)
		delete(m_leftTree);
	if (m_rightTree)
		delete(m_rightTree);
}

//create a tree leaf element for ourselves
void CBoundingBoxTree::CreateFrom(CList<CFace*, CFace*>* faces)
{
	m_objectsFaces = faces;

	m_pBox = new CBoundingBox();
	m_pBox->CreateFrom(faces);

}

double CBoundingBoxTree::GetVolume(void)
{
	return m_pBox->GetVolume();
}

double CBoundingBoxTree::GetUnionVolumeWith(CBoundingBoxTree* tree)
{
	CBoundingBox* box = m_pBox->GetUnionWith(*(tree->m_pBox));
	double dVolume = box->GetVolume();
	delete(box);
	return dVolume;
}

void CBoundingBoxTree::CreateFromUnionOf(CBoundingBoxTree *tree1, CBoundingBoxTree *tree2)
{
	m_pBox = ((tree1->m_pBox)->GetUnionWith(*(tree2->m_pBox)));
	m_objectsFaces = NULL;

	m_leftTree = tree1;
	m_rightTree = tree2;
}

//return null if no intersection, else return the point
//on the face that is in our way
C3DPoint* CBoundingBoxTree::Intersects(C3DPoint p1, C3DPoint p2)
{
		//see if we are in our bounding box
	if (m_pBox->IsInBetween(p1,p2) >= 1)
		return NULL;

	if (m_objectsFaces != NULL)
	{
		//we are a leaf
		//sequence through our list of faces and see if we intersect any of them
		POSITION pos = m_objectsFaces->GetHeadPosition();
		while (pos != NULL)
		{
			CFace* obj = m_objectsFaces->GetAt(pos);
			C3DPoint *intersection = NULL;
			intersection = obj->IsInBetween(p1,p2);
			if (intersection)
			{
				return intersection;
			}
			m_objectsFaces->GetNext(pos);
		}
		return NULL;

	}

	//else check our left subtree
	C3DPoint* intersection = NULL;
	intersection = m_leftTree->Intersects(p1,p2); 
	if (intersection)
		return intersection;
	else
	{
		intersection = m_rightTree->Intersects(p1,p2); 
		return intersection;
	}
	return NULL;
}

//return null if no intersection, else return the face
CFace* CBoundingBoxTree::IntersectsFace(C3DPoint p1, C3DPoint p2)
{
		//see if we are in our bounding box
	if (m_pBox->IsInBetween(p1,p2) >= 1)
		return NULL;

	if (m_objectsFaces != NULL)
	{
		//we are a leaf
		//sequence through our list of faces and see if we intersect any of them
		POSITION pos = m_objectsFaces->GetHeadPosition();
		while (pos != NULL)
		{
			CFace* obj = m_objectsFaces->GetAt(pos);
			C3DPoint *intersection = NULL;
			intersection = obj->IsInBetween(p1,p2);
			if (intersection)
			{
				delete(intersection);
				return obj;
			}
			m_objectsFaces->GetNext(pos);
		}
		return NULL;

	}

	//else check our left subtree
	CFace* intersection = NULL;
	intersection = m_leftTree->IntersectsFace(p1,p2); 
	if (intersection)
		return intersection;
	else
	{
		intersection = m_rightTree->IntersectsFace(p1,p2); 
		return intersection;
	}
	return NULL;
}


