//
// C++ Implementation: BVTree
//
// Description:
//
//
// Authors: Dalla Corte Ludovic (C) 2011
//          Phan Laurent
//          Etudiants Infographie Groupe 1 2010-2011
//
// Copyright: See COPYING file that comes with this distribution
//
//

#include "BVTree.h"
#include "scene.h"

BVTree::BVTree(Gscene* scene) {
	std::list<BVNode*> nodes;
	Gscene::iteratorModel it_models = scene->beginModel();
	for (; it_models != scene->endModel(); ++it_models) {
		BoundingBox* box = new BoundingBox(*it_models);
		nodes.push_back(new BVNode(box));
	}

	std::list<BVNode*> parentNodes;
	while(nodes.size() > 1) {
		parentNodes.clear();

		std::list<BVNode*>::iterator it_nodes = nodes.begin();
		for (; it_nodes != nodes.end(); it_nodes = nodes.begin()) {

			// Noeud courant
			BVNode* node = *it_nodes;
			point_t box_center = (node->getBVNodeInfo())->getBBoxCenter();

			// Dernier noeud
			if(it_nodes == --nodes.end()) {
				parentNodes.push_back(node);
				break;
			}
			else {
				// Supprimer le noeud courant de la liste
				nodes.erase(it_nodes);

				// On va trouver le noeud le plus proche
				std::list<BVNode*>::iterator it2_nodes = nodes.begin();
				std::list<BVNode*>::iterator del = nodes.begin();
				// Prendre le suivant pour commencer les tests
				point_t box2_center = ((*it2_nodes)->getBVNodeInfo())->getBBoxCenter();
				double dist = sqrt(((box_center.X - box2_center.X) * (box_center.X - box2_center.X))
						+ ((box_center.Y - box2_center.Y) * (box_center.Y - box2_center.Y))
						+ ((box_center.Z - box2_center.Z) * (box_center.Z - box2_center.Z)));

				++it2_nodes;
				for (; it2_nodes != nodes.end(); ++it2_nodes) {
					box2_center = ((*it2_nodes)->getBVNodeInfo())->getBBoxCenter();
					double dist_tmp = sqrt(((box_center.X - box2_center.X) * (box_center.X - box2_center.X))
							+ ((box_center.Y - box2_center.Y) * (box_center.Y - box2_center.Y))
							+ ((box_center.Z - box2_center.Z) * (box_center.Z - box2_center.Z)));

					if (dist_tmp < dist) {
						del = it2_nodes;
						dist = dist_tmp;
					}
				}

				// Supprimer le second élément de la liste
				BVNode* node2 = *del;
				BVNode* parentNode = new BVNode(new BoundingBox(node->getBVNodeInfo(),
						node2->getBVNodeInfo()));
				parentNode->setBVNodeLeft(node);
				parentNode->setBVNodeRight(node2);
				parentNodes.push_back(parentNode);

				nodes.erase(del);
			}
		}

		nodes = parentNodes;
		// Niveau suivant
	}

	if(!nodes.empty()) {
		root = nodes.front();
	}
	else {
		root = NULL;
	}
}

BVTree::~BVTree() {
	freeBVTree(root);
}

void BVTree::intersectionBBox(BVNode* node, ray* ray, std::vector<Gmodel*>* intersectModels) {
	if(node == NULL) {
		return;
	}
	if(node->isBVNodeLeaf()) {
		Gmodel* model = node->getBVNodeInfo()->getModel();
		intersectModels->push_back(model);
	}
	else {
		if(node->getBVNodeInfo()->intersect(ray)) {
			intersectionBBox(node->getBVNodeLeft(), ray, intersectModels);
			intersectionBBox(node->getBVNodeRight(), ray, intersectModels);
		}
	}
}

void BVTree::freeBVTree(BVNode* node) {
	if(node == NULL) {
		return;
	}
 	if(node->isBVNodeLeaf()) {
		delete(node->getBVNodeInfo());
		delete(node);
	}
	else {
		freeBVTree(node->getBVNodeLeft());
		freeBVTree(node->getBVNodeRight());
		delete(node);
	}
}