//==============================================================================
/*! \file
 * OpenMesh Toolkit for mesh analysis    \n
 * Copyright (c) 2010 by Rostislav Hulik     \n
 *
 * Author:  Rostislav Hulik, rosta.hulik@gmail.com  \n
 * Date:    2010/10/20                          \n
 *
 * This file is part of software developed for support of Rostislav Hulik's dissertation thesis at dcgm-robotics@FIT group.
 *
 * This file is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This file is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this file.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * Description:
 * - Class for constructing BDP tree for raycasting
 *
 * TODO Better tree passing
 * TODO Functions for both ray directions
 */

#ifndef OM_BSP_TREE_H
#define OM_BSP_TREE_H

#include <OMToolkit\OMTriBSPTreeAABB.h>
#include <OMToolkit\OMTriBSPTreeTriangle.h>
#include <OMToolkit\OMTriBSPTreeRay.h>
#include <vector>
#include <algorithm>

//#define USE_MULTIPLE_IN_ONE

namespace OMToolkit
{
	/**
	 * BSP Tree class
	 */
	class OMTriBSPTree
	{
		public:
			/**
			 * Mesh Type
			 */
			typedef OMToolkit::Types::ModuleMeshd MeshT;

			/**
			 * Point Type
			 */
			typedef MeshT::Point PointT;

			/**
			 * Face handle Type
			 */
			typedef MeshT::FaceHandle FaceHT;

			/**
			 * Vertex handle Type
			 */
			typedef MeshT::VertexHandle VertexHT;

			/**
			 * Scalar type used in vectors
			 */
			typedef PointT::value_type ScalarT;

			/**
			 * Constructor - creates a BSP from a mesh
			 * @param mesh Pointer to a mesh
			 * @param maxPointsInElement Maximum number of vertices in one tree cell
			 */
			OMTriBSPTree(MeshT *mesh);

			/**
			 * Function returns a nearest intersected triangle (both directions)
			 * @param origin Ray origin - intersection is computed also in inverse direction
			 * @param vector Ray direction
			 * @param face Returned face handle
			 */
			void getPassingFace(PointT& origin, PointT &vector, FaceHT &face);

			/**
			 * Function returns all intersected triangles
			 * @param origin Ray origin - intersection is computed also in inverse direction
			 * @param vector Ray direction
			 * @param faces Returned face handles
			 */
			void getAllPassingFaces(PointT& origin, PointT &vector, std::vector<FaceHT> &faces);

		public:
			/**
			 * Root node
			 */
			TreeElement *m_root;

			/**
			 * Aux function for tree construction (used in constructor)
			 * @param maxPointsInElement Maximum number of vertices in one tree cell
			 */
			void ConstructTree();

			/**
			 * Sorting function - X axis values
			 */
			static bool sortXFunc (TriCenter const &first, TriCenter const &second);

			/**
			 * Sorting function - Y axis values
			 */
			static bool sortYFunc (TriCenter const &first, TriCenter const &second);

			/**
			 * Sorting function - Z axis values
			 */
			static bool sortZFunc (TriCenter const &first, TriCenter const &second);
			/**
			 * Sorting function - index values
			 */
			static bool sortIndexFunc (TriCenter const &first, TriCenter const &second);


			// static mesh variable (due to static sorting)
			MeshT *m_mesh;
			std::vector<TriCenter> m_sorted;
	};

	
	/**
	 * Class used as stack element for bsp tree construction
	 */
	class StackElement
	{
		public:
			/**
			 * Constructor - initializes variables
			 * @param low Lowest index
			 * @param high End - first non valid item
			 * @param sort Sorting axis
			 * @param div Border between left and right after division
			 * @param p Parent tree element
			 */
			StackElement(int low, int high, int sort, OMTriBSPTree::ScalarT div, TreeElement *p, int id)
			{
				lower = low;
				higher = high;
				sorted = sort;
				parent = p;
				_id = id;
			}
		
			/**
			 * Lowest index
			 */
			int _id;
			int lower;

			/**
			 * End - first non valid item
			 */
			int higher;

			/**
			 * Sorting axis
			 */
			int sorted;

			/**
			 * Parent tree element
			 */
			TreeElement *parent;
	};
} // namespace OMToolkit

#endif