#pragma once

#include "volumeshop.h"

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <limits>
#include "Vector.h"
#include "Box.h"
#include "Exception.h"

template <class Type>
class Volume
{
public:

	class Block
	{	
	public:
		class Reference
		{
			friend class Block;

		public:

			Reference() : m_uCount(0), m_bDefault(true)
			{
				static const Type tDefault;

				m_tMinimum = m_vtData[0];
				m_tMaximum = m_vtData[0];

				for (unsigned int i=1;i<BLOCKSIZE;i++)
				{
					m_tMinimum = std::min(m_tMinimum,m_vtData[i]);
					m_tMaximum = std::max(m_tMaximum,m_vtData[i]);
				}

				for (unsigned int i=0;i<BLOCKSIZE;i++)
				{
					if (m_vtData[i] != tDefault)
					{
						const unsigned int uPositionZ = (i / (BLOCKDIMENSION*BLOCKDIMENSION));
						const unsigned int uPositionY = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION)) / BLOCKDIMENSION;
						const unsigned int uPositionX = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION) - uPositionY * BLOCKDIMENSION);
						m_boxBounds += (Vector(float(uPositionX),float(uPositionY),float(uPositionZ)));
						break;
					}
				}

				for (unsigned int i=BLOCKSIZE-1;i>0;i--)
				{
					if (m_vtData[i] != tDefault)
					{
						const unsigned int uPositionZ = (i / (BLOCKDIMENSION*BLOCKDIMENSION));
						const unsigned int uPositionY = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION)) / BLOCKDIMENSION;
						const unsigned int uPositionX = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION) - uPositionY * BLOCKDIMENSION);
						m_boxBounds += (Vector(float(uPositionX),float(uPositionY),float(uPositionZ)));
						break;
					}
				}
			};

			Reference(const Type *pData) : m_uCount(0), m_bDefault(false)
			{
				static const Type tDefault;

				m_tMinimum = pData[0];
				m_tMaximum = pData[0];

				for (unsigned int i=1;i<BLOCKSIZE;i++)
				{
					m_tMinimum = std::min(m_tMinimum,pData[i]);
					m_tMaximum = std::max(m_tMaximum,pData[i]);
				}

				for (unsigned int i=0;i<BLOCKSIZE;i++)
				{
					if (pData[i] != tDefault)
					{
						const unsigned int uPositionZ = (i / (BLOCKDIMENSION*BLOCKDIMENSION));
						const unsigned int uPositionY = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION)) / BLOCKDIMENSION;
						const unsigned int uPositionX = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION) - uPositionY * BLOCKDIMENSION);
						m_boxBounds += (Vector(float(uPositionX),float(uPositionY),float(uPositionZ)));
						break;
					}
				}

				for (unsigned int i=BLOCKSIZE-1;i>0;i--)
				{
					if (pData[i] != tDefault)
					{
						const unsigned int uPositionZ = (i / (BLOCKDIMENSION*BLOCKDIMENSION));
						const unsigned int uPositionY = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION)) / BLOCKDIMENSION;
						const unsigned int uPositionX = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION) - uPositionY * BLOCKDIMENSION);
						m_boxBounds += (Vector(float(uPositionX),float(uPositionY),float(uPositionZ)));
						break;
					}
				}

				memcpy((void*) m_vtData,(void*) pData,sizeof(Type)*BLOCKSIZE);

				Type *pOldData = m_vtData;

				unsigned int uOldBlockDimension = BLOCKDIMENSION;
				unsigned int uOldBlockSize = BLOCKSIZE;

				unsigned int uNewBlockDimension = uOldBlockDimension >> 1;
				unsigned int uNewBlockSize = uNewBlockDimension*uNewBlockDimension*uNewBlockDimension;

				while (uNewBlockSize >= 1)
				{					
					Type *pNewData = pOldData + uOldBlockSize;

					for (unsigned int k=0;k<uNewBlockDimension;k++)
					{
						const unsigned int uZ = (k<<1);

						for (unsigned int j=0;j<uNewBlockDimension;j++)
						{
							const unsigned int uY = (j<<1);

							for (unsigned int i=0;i<uNewBlockDimension;i++)
							{
								const unsigned int uX = (i<<1);

								const Type & tValue = pOldData[uX+ uY*uOldBlockDimension + uZ*uOldBlockDimension*uOldBlockDimension];
								pNewData[i + j*uNewBlockDimension + k*uNewBlockDimension*uNewBlockDimension] = tValue;
							}
						}
					}

					pOldData = pNewData;

					uOldBlockDimension = uNewBlockDimension;
					uOldBlockSize = uNewBlockSize;

					uNewBlockDimension = uNewBlockDimension >> 1;
					uNewBlockSize = uNewBlockDimension*uNewBlockDimension*uNewBlockDimension;
				}
			};

			Reference(const Reference &refOther) : m_uCount(0), m_bDefault(false)
			{
				m_tMinimum = refOther.m_tMinimum;
				m_tMaximum = refOther.m_tMaximum;
				m_boxBounds = refOther.m_boxBounds;
				memcpy((void*) m_vtData,(void*) refOther.m_vtData,sizeof(Type)*BLOCKMEMORY);
			};

			~Reference()
			{
			};

			void Set(const unsigned int uX, const unsigned int uY, const unsigned int uZ, const Type &tValue)
			{
				static const Type tDefault;

				const Type tPrevious = m_vtData[uX + uY*BLOCKDIMENSION + uZ*BLOCKDIMENSION*BLOCKDIMENSION];
				m_vtData[uX + uY*BLOCKDIMENSION + uZ*BLOCKDIMENSION*BLOCKDIMENSION] = tValue;

				if ((uX & 1) == 0 && (uY & 1) == 0 && (uZ & 1) == 0)
				{
					Type * pData = m_vtData + BLOCKSIZE;

					unsigned int uPositionX = uX >> 1;
					unsigned int uPositionY = uY >> 1;
					unsigned int uPositionZ = uZ >> 1;

					unsigned int uBlockDimension = BLOCKDIMENSION >> 1;
					unsigned int uBlockSize = uBlockDimension*uBlockDimension*uBlockDimension;

					while (uBlockSize >= 1)
					{
						pData[uPositionX + uPositionY*uBlockDimension + uPositionZ*uBlockDimension*uBlockDimension] = tValue;

						if ((uPositionX & 1) != 0 || (uPositionY & 1) != 0 || (uPositionZ & 1) != 0)
							break;

						pData = pData + uBlockSize;

						uPositionX = uPositionX >> 1;
						uPositionY = uPositionY >> 1;
						uPositionZ = uPositionZ >> 1;

						uBlockDimension = uBlockDimension >> 1;
						uBlockSize = uBlockDimension*uBlockDimension*uBlockDimension;
					}
				}

				if (tValue != tDefault && tPrevious == tDefault)
					m_boxBounds += Vector(float(uX),float(uY),float(uZ));
				else if (tValue == tDefault && tPrevious != tDefault)
				{
					Box boxBounds;

					for (unsigned int i=0;i<BLOCKSIZE;i++)
					{
						if (m_vtData[i] != tDefault)
						{
							const unsigned int uPositionZ = (i / (BLOCKDIMENSION*BLOCKDIMENSION));
							const unsigned int uPositionY = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION)) / BLOCKDIMENSION;
							const unsigned int uPositionX = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION) - uPositionY * BLOCKDIMENSION);
							boxBounds += Vector(float(uPositionX),float(uPositionY),float(uPositionZ));
							break;
						}
					}

					for (unsigned int i=BLOCKSIZE-1;i>0;i--)
					{
						if (m_vtData[i] != tDefault)
						{
							const unsigned int uPositionZ = (i / (BLOCKDIMENSION*BLOCKDIMENSION));
							const unsigned int uPositionY = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION)) / BLOCKDIMENSION;
							const unsigned int uPositionX = (i - uPositionZ * (BLOCKDIMENSION*BLOCKDIMENSION) - uPositionY * BLOCKDIMENSION);
							boxBounds += Vector(float(uPositionX),float(uPositionY),float(uPositionZ));
							break;
						}
					}

					m_boxBounds = boxBounds;

				}				

				if ((tPrevious == m_tMinimum  && tValue > tPrevious) || (tPrevious == m_tMaximum && tValue < tPrevious))
				{
					m_tMinimum = m_vtData[0];
					m_tMaximum = m_vtData[0];

					for (unsigned int i=1;i<BLOCKSIZE;i++)
					{
						m_tMinimum = std::min(m_tMinimum,m_vtData[i]);
						m_tMaximum = std::max(m_tMaximum,m_vtData[i]);
					}
				}
				else
				{
					m_tMinimum = std::min(m_tMinimum,tValue);
					m_tMaximum = std::max(m_tMaximum,tValue);
				}
			};

			const Type & Get(const unsigned int uX, const unsigned int uY, const unsigned int uZ) const
			{
				return m_vtData[uX + uY*BLOCKDIMENSION + uZ*BLOCKDIMENSION*BLOCKDIMENSION];
			};

			const Type * Get() const
			{
				return m_vtData;
			};

			const Type & Get(const unsigned int uLevelOfDetail, const unsigned int uX, const unsigned int uY, const unsigned int uZ) const
			{
				const unsigned int uBlockDimension = BLOCKDIMENSIONLOD(uLevelOfDetail);
				return (m_vtData + BLOCKOFFSET(uLevelOfDetail))[uX + uY*uBlockDimension + uZ*uBlockDimension*uBlockDimension];
			};

			const Type * Get(const unsigned int uLevelOfDetail) const
			{
				return m_vtData + BLOCKOFFSET(uLevelOfDetail);
			};

			const Type & GetMinimum() const
			{
				return m_tMinimum;
			};

			const Type & GetMaximum() const
			{
				return m_tMaximum;
			};

			const Box & GetBounds() const
			{
				return m_boxBounds;
			};

			const Reference & operator=(const Reference &refOther)
			{
				m_tMinimum = refOther.m_tMinimum;
				m_tMaximum = refOther.m_tMaximum;
				m_boxBounds = refOther.m_boxBounds;
				memcpy((void*) m_vtData,(void*) refOther.m_vtData,sizeof(Type)*BLOCKMEMORY);
				return *this;
			};

			const bool operator==(const Reference &refOther) const
			{
				if (m_tMinimum != refOther.m_tMinimum)
					return false;

				if (m_tMaximum != refOther.m_tMaximum)
					return false;

				if (m_boxBounds != refOther.m_boxBounds)
					return false;

				return memcmp((void*) m_vtData,(void*) refOther.m_vtData,sizeof(Type)*BLOCKSIZE) == 0;
			};

			const bool operator!=(const Reference &refOther) const
			{
				return !(*this == refOther);
			};

			void incrementReferenceCount()
			{
				m_uCount++;
			};

			void decrementReferenceCount()
			{
				m_uCount--;

				if (m_uCount == 0)
					if (!m_bDefault)
						delete this;
			};

			const unsigned int GetReferenceCount() const
			{
				return m_uCount;
			};

			const bool IsDefault() const
			{
				return m_bDefault;
			};

			static Reference * GetDefault()
			{
				static Reference *s_pDefault =  NULL;

				if (!s_pDefault)
					s_pDefault = new Reference();

				return s_pDefault;
			};

		private:

			Type m_vtData[BLOCKMEMORY];
			Type m_tMinimum;
			Type m_tMaximum;
			Box m_boxBounds;
			unsigned int m_uCount;
			bool m_bDefault;
		};

	public:

		Block()
		{
			m_pReference = Reference::GetDefault();
			m_pReference->incrementReferenceCount();
		};

		Block(const Type *pData)
		{
			m_pReference = new Reference(pData);
			m_pReference->incrementReferenceCount();
		};

		Block (const Block &bloOther)
		{
			m_pReference = bloOther.m_pReference;
			m_pReference->incrementReferenceCount();
		};

		~Block()
		{
			m_pReference->decrementReferenceCount();
		};

		void clear()
		{
			Reference::GetDefault()->incrementReferenceCount();
			m_pReference->decrementReferenceCount();
			m_pReference = Reference::GetDefault();
		};

		void Set(const unsigned int uX, const unsigned int uY, const unsigned int uZ, const Type &tValue)
		{
			if (m_pReference->GetReferenceCount() == 1 && !m_pReference->IsDefault())
				m_pReference->Set(uX,uY,uZ,tValue);
			else
			{
				if (m_pReference->Get(uX,uY,uZ) != tValue)
				{
					Reference *pReference = new Reference(*m_pReference);
					pReference->incrementReferenceCount();

					pReference->Set(uX,uY,uZ,tValue);

					m_pReference->decrementReferenceCount();
					m_pReference = pReference;
				}
			};
		};

		const Type & Get(const unsigned int uX, const unsigned int uY, const unsigned int uZ) const
		{
			return m_pReference->Get(uX,uY,uZ);
		};

		const Type * Get() const
		{
			return m_pReference->Get();
		};

		const Type & Get(const unsigned int uLevelOfDetail, const unsigned int uX, const unsigned int uY, const unsigned int uZ) const
		{
			return m_pReference->Get(uLevelOfDetail,uX,uY,uZ);
		};

		const Type * Get(const unsigned int uLevelOfDetail) const
		{
			return m_pReference->Get(uLevelOfDetail);
		};

		const Type & GetMinimum() const
		{
			return m_pReference->GetMinimum();
		};

		const Type & GetMaximum() const
		{
			return m_pReference->GetMaximum();
		};

		const Box & GetBounds() const
		{
			return m_pReference->GetBounds();
		};

		const Block & operator=(const Block &bloOther)
		{
			if (m_pReference != bloOther.m_pReference)
			{
				m_pReference->decrementReferenceCount();
				m_pReference = bloOther.m_pReference;
				m_pReference->incrementReferenceCount();
			}

			return *this;
		};

		const bool operator==(const Block &bloOther) const
		{
			if (m_pReference == bloOther.m_pReference)
				return true;
			else
				return *(m_pReference) == *(bloOther.m_pReference);
		};

		const bool operator!=(const Block &bloOther) const
		{
			return !(*this == bloOther);
		};

	private:

		Reference *m_pReference;
	};

	class Octree
	{
	public:

		class Node
		{
		public:

			Node()
			{
			};

			~Node()
			{
			};

			void SetPosition(const Vector &vecPosition)
			{
				m_vecPosition = vecPosition;
			};

			const Vector & GetPosition() const
			{
				return m_vecPosition;
			};

			void SetSize(const Vector &vecSize)
			{
				m_vecSize = vecSize;
			};

			const Vector & GetSize() const
			{
				return m_vecSize;
			};

			void SetMinimum(const Type & tMinimum)
			{
				m_tMinimum = tMinimum;
			};

			const Type & GetMinimum() const
			{
				return m_tMinimum;
			};

			void SetMaximum(const Type & tMaximum)
			{
				m_tMaximum = tMaximum;
			};

			const Type & GetMaximum() const
			{
				return m_tMaximum;
			};

			void SetBounds(const Box & boxBounds)
			{
				m_boxBounds = boxBounds;
			};

			const Box & GetBounds() const
			{
				return m_boxBounds;
			};

		private:

			Vector m_vecPosition;
			Vector m_vecSize;
			Type m_tMinimum;
			Type m_tMaximum;
			Box m_boxBounds;
		};


		class Iterator
		{
			friend class Octree;

		public:

			Iterator(const Octree &octOctree) : m_pData(octOctree.Get()), m_uThisOffset((octOctree.GetSize()-1) >> 3), m_uNextOffset((m_uThisOffset-1) >> 3)
			{
			};

			~Iterator()
			{
			};

			Node & operator*()
			{
				return *m_pData;
			}

			const Node & operator*() const
			{
				return *m_pData;
			};

			const bool IsLeaf() const
			{
				return m_uThisOffset < 1;
			};

			const Iterator operator[](const unsigned int uIndex) const
			{
				return Iterator(m_pData+1+uIndex*m_uThisOffset,m_uNextOffset);
			};

			const Iterator operator[](const Vector & vecPosition) const
			{
				const unsigned int uIndex = ((vecPosition.GetZ() >= m_pData->GetPosition().GetZ()) << 2) | ((vecPosition.GetY() >= m_pData->GetPosition().GetY()) << 1) | ((vecPosition.GetX() >= m_pData->GetPosition().GetX()) << 0);
				return Iterator(m_pData+1+uIndex*m_uThisOffset,m_uNextOffset);
			};

		protected:

			Iterator(Node *pData, const unsigned int uOffset) : m_pData(pData), m_uThisOffset(uOffset), m_uNextOffset((uOffset-1) >> 3)
			{
			};

			Node *m_pData;
			unsigned int m_uThisOffset;
			unsigned int m_uNextOffset;
		};

		class FrontToBackIterator : public Iterator
		{
			friend class Octree;

		public:

			FrontToBackIterator(const Octree & octOctree, const Vector & vecEye)  : Iterator(octOctree), m_vecEye(vecEye), m_uTable(GetIndex(vecEye,(*octOctree.Get()).GetPosition()))
			{			
			};

			~FrontToBackIterator()
			{
			};

			const FrontToBackIterator operator[](const unsigned int uIndex) const
			{
				/*
				static const unsigned int vuTraversal[8][8] =
				{
				{RUF,RUB,RDF,RDB,LUF,LUB,LDF,LDB}, // LDB
				{LUF,LUB,LDF,LDB,RUF,RUB,RDF,RDB}, // RDB
				{RDF,RDB,RUF,RUB,LDF,LDB,LUF,LUB}, // LUB
				{LDF,LDB,LUF,LUB,RDF,RDB,RUF,RUB}, // RUB

				{RUB,RUF,RDB,RDF,LUB,LUF,LDB,LDF}, // LDF
				{LUB,LUF,LDB,LDF,RUB,RUF,RDB,RDF}, // RDF
				{RDB,RDF,RUB,RUF,LDB,LDF,LUB,LUF}, // LUF
				{LDB,LDF,LUB,LUF,RDB,RDF,RUB,RUF}, // RUF
				};*/

				static const unsigned int vuTraversal[8][8] =
				{
					{LDB,LDF,LUB,LUF,RDB,RDF,RUB,RUF}, // LDB
					{RDB,RDF,RUB,RUF,LDB,LDF,LUB,LUF}, // RDB
					{LUB,LUF,LDB,LDF,RUB,RUF,RDB,RDF}, // LUB
					{RUB,RUF,RDB,RDF,LUB,LUF,LDB,LDF}, // RUB

					{LDF,LDB,LUF,LUB,RDF,RDB,RUF,RUB}, // LDF
					{RDF,RDB,RUF,RUB,LDF,LDB,LUF,LUB}, // RDF
					{LUF,LUB,LDF,LDB,RUF,RUB,RDF,RDB}, // LUF
					{RUF,RUB,RDF,RDB,LUF,LUB,LDF,LDB}, // RUF
				};


				return FrontToBackIterator(m_pData+1+vuTraversal[m_uTable][uIndex]*m_uThisOffset,m_uNextOffset,m_vecEye);
			};

		protected:

			FrontToBackIterator(Node *pData, const unsigned int uOffset, const Vector & vecEye) : Iterator(pData,uOffset), m_vecEye(vecEye), m_uTable(GetIndex(vecEye,(*pData).GetPosition()))
			{
			};

			static const unsigned int GetIndex(const Vector & vecEye, const Vector & vecPosition)
			{
				return ((vecEye.GetZ() >= vecPosition.GetZ()) << 2) | ((vecEye.GetY() >= vecPosition.GetY()) << 1) | ((vecEye.GetX() >= vecPosition.GetX()) << 0);
			};

		private:

			unsigned int m_uTable;
			Vector m_vecEye;

			enum
			{
				LDB = 0, RDB = 1, LUB = 2, RUB = 3, LDF = 4, RDF = 5, LUF = 6, RUF = 7
			};
		};



		Octree(const Volume & volVolume) : m_volVolume(volVolume), m_pData(NULL)
		{
			unsigned int uDimension = std::max(GetNextPowerOfTwo(m_volVolume.GetBlocksX()),std::max(GetNextPowerOfTwo(m_volVolume.GetBlocksY()),GetNextPowerOfTwo(m_volVolume.GetBlocksZ())));
			unsigned int uSize = 0;

			while (uDimension > 0)
			{
				uSize = uSize + uDimension * uDimension * uDimension;
				uDimension = uDimension >> 1;
			}

			m_uSize = uSize;
			m_pData = new Node[uSize];

			build();
		};

		~Octree()
		{
			if (m_pData)
				delete[] m_pData;
		};

		void update(const unsigned int uX, const unsigned int uY, const unsigned int uZ)
		{
			std::vector<Iterator> vecIterators;
			const Vector vecPosition = Vector(float(uX),float(uY),float(uZ));
			
			Iterator iter(*this);		

			while (!iter.IsLeaf())
			{
				vecIterators.push_back(iter);
				iter = iter[vecPosition];
			}

			const Block & bloBlock = m_volVolume.GetBlock(uX,uY,uZ);
			
			Type tOldMinimum = (*iter).GetMinimum();
			Type tOldMaximum = (*iter).GetMaximum();
			Box boxOldBounds = (*iter).GetBounds();

			Type tNewMinimum = bloBlock.GetMinimum();
			Type tNewMaximum = bloBlock.GetMaximum();
			Box boxNewBounds = bloBlock.GetBounds().GetTranslated(-(*iter).GetSize()*0.5f);

			(*iter).SetMinimum(tNewMinimum);
			(*iter).SetMaximum(tNewMaximum);
			(*iter).SetBounds(boxNewBounds);

			while (!vecIterators.empty())
			{
				Iterator & iteCurrent = vecIterators.back();

				if ((tOldMinimum == (*iteCurrent).GetMinimum() && tNewMinimum > tOldMinimum) || (tOldMaximum == (*iteCurrent).GetMaximum() && tNewMaximum < tOldMaximum) || (boxNewBounds != boxOldBounds))
				{
					tNewMinimum = (*(iteCurrent[0])).GetMinimum();
					tNewMaximum = (*(iteCurrent[0])).GetMaximum();
					boxNewBounds = (*(iteCurrent[0])).GetBounds().GetTranslated((*(iteCurrent[0])).GetPosition() - (*iteCurrent).GetPosition());

					for (unsigned int i=1;i<8;i++)
					{
						tNewMinimum = std::min(tNewMinimum,(*(iteCurrent[i])).GetMinimum());
						tNewMaximum = std::max(tNewMaximum,(*(iteCurrent[i])).GetMaximum());
						boxNewBounds += (*(iteCurrent[i])).GetBounds().GetTranslated((*(iteCurrent[i])).GetPosition() - (*iteCurrent).GetPosition());
					}
				}
				else
				{
					tNewMinimum = std::min(tNewMinimum,(*iteCurrent).GetMinimum());
					tNewMaximum = std::max(tNewMaximum,(*iteCurrent).GetMaximum());
					boxNewBounds = (*iteCurrent).GetBounds();
				}

				tOldMinimum = (*iteCurrent).GetMinimum();
				tOldMaximum = (*iteCurrent).GetMaximum();
				boxOldBounds = (*iteCurrent).GetBounds();

				(*iteCurrent).SetMinimum(tNewMinimum);
				(*iteCurrent).SetMaximum(tNewMaximum);
				(*iteCurrent).SetBounds(boxNewBounds);

				vecIterators.pop_back();

				if (tNewMinimum == tOldMinimum && tNewMaximum == tOldMinimum && boxNewBounds == boxOldBounds)
					break;
			};
		};

	private:

		Node * Get() const
		{
			return m_pData;
		};

		const unsigned int GetSize() const
		{
			return m_uSize;
		};

		void build()
		{
			unsigned int uDimension = std::max(GetNextPowerOfTwo(m_volVolume.GetBlocksX()),std::max(GetNextPowerOfTwo(m_volVolume.GetBlocksY()),GetNextPowerOfTwo(m_volVolume.GetBlocksZ())));
			const Vector vecSize(float(uDimension*BLOCKDIMENSION),float(uDimension*BLOCKDIMENSION),float(uDimension*BLOCKDIMENSION));

			Iterator iter(*this);
			(*iter).SetPosition(vecSize*0.5f);
			(*iter).SetSize(vecSize);

			build(iter);
		};

		void build(Iterator & iter)
		{
			if (iter.IsLeaf())
			{
				const int iX = int((*iter).GetPosition().GetX());
				const int iY = int((*iter).GetPosition().GetY());
				const int iZ = int((*iter).GetPosition().GetZ());

				if (iX >= 0 && iY >=0 && iZ >= 0 &&  iX < int(m_volVolume.GetSizeX()) && iY < int(m_volVolume.GetSizeY()) && iZ < int(m_volVolume.GetSizeZ()))
				{
					const Block &bloBlock = m_volVolume.GetBlock(unsigned int(iX),unsigned int(iY),unsigned int(iZ));
					(*iter).SetMinimum(bloBlock.GetMinimum());
					(*iter).SetMaximum(bloBlock.GetMaximum());
					(*iter).SetBounds(bloBlock.GetBounds().GetTranslated(-(*iter).GetSize()*0.5f));
				}
			}
			else
			{
				const Vector vecChildFullSize = (*iter).GetSize() * 0.5f;
				const Vector vecChildHalfSize = vecChildFullSize * 0.5f;

				const Vector vecPositions[] = 
				{
					Vector(-vecChildHalfSize.GetX(),-vecChildHalfSize.GetY(),-vecChildHalfSize.GetZ()),
					Vector( vecChildHalfSize.GetX(),-vecChildHalfSize.GetY(),-vecChildHalfSize.GetZ()),
					Vector(-vecChildHalfSize.GetX(), vecChildHalfSize.GetY(),-vecChildHalfSize.GetZ()),
					Vector( vecChildHalfSize.GetX(), vecChildHalfSize.GetY(),-vecChildHalfSize.GetZ()),
					Vector(-vecChildHalfSize.GetX(),-vecChildHalfSize.GetY(), vecChildHalfSize.GetZ()),
					Vector( vecChildHalfSize.GetX(),-vecChildHalfSize.GetY(), vecChildHalfSize.GetZ()),
					Vector(-vecChildHalfSize.GetX(), vecChildHalfSize.GetY(), vecChildHalfSize.GetZ()),
					Vector( vecChildHalfSize.GetX(), vecChildHalfSize.GetY(), vecChildHalfSize.GetZ())
				};

				Iterator first = iter[0];

				(*first).SetPosition((*iter).GetPosition()+vecPositions[0]);
				(*first).SetSize(vecChildFullSize);

				build(first);

				Type tMinimum = (*first).GetMinimum();
				Type tMaximum = (*first).GetMaximum();
				Box boxBounds((*first).GetBounds().GetTranslated((*(first)).GetPosition() - (*iter).GetPosition()));

				for (unsigned int i=1;i<8;i++)
				{
					Iterator child = iter[i];

					(*child).SetPosition((*iter).GetPosition()+vecPositions[i]);
					(*child).SetSize(vecChildFullSize);

					build(child);

					tMinimum = std::min(tMinimum,(*child).GetMinimum());
					tMaximum = std::max(tMaximum,(*child).GetMaximum());
					boxBounds += (*child).GetBounds().GetTranslated((*child).GetPosition() - (*iter).GetPosition());
				}

				(*iter).SetMinimum(tMinimum);
				(*iter).SetMaximum(tMaximum);
				(*iter).SetBounds(boxBounds);
			}
		};

	private:

		const Volume & m_volVolume;
		unsigned int m_uSize;
		Node *m_pData;
	};

	class RayIterator
	{
		friend class Volume;

	public:

		RayIterator(const Volume &volVolume, const Vector &vecPosition, const Vector &vecDirection) : m_volVolume(volVolume), m_vecPosition(vecPosition), m_vecDirection(vecDirection.GetNormalized())
		{
			intersect();
		};

		~RayIterator()
		{
		};

		const bool IsAtEnd() const
		{
			return m_bAtEnd;
		};

		const Vector & GetPosition() const
		{
			return m_vecPosition;
		};

		const unsigned int GetX() const
		{
			return unsigned int(m_vecPosition.GetX());
		};

		const unsigned int GetY() const
		{
			return unsigned int(m_vecPosition.GetY());
		};

		const unsigned int GetZ() const
		{
			return unsigned int(m_vecPosition.GetZ());
		};

		const RayIterator & operator++()
		{
			m_vecPosition += m_vecDirection;
			m_bAtEnd = (m_vecPosition.GetX() < 0.0f || m_vecPosition.GetY() < 0.0f || m_vecPosition.GetZ() < 0.0f || m_vecPosition.GetX() > float(m_volVolume.GetSizeX()-1) || m_vecPosition.GetY() > float(m_volVolume.GetSizeY()-1) || m_vecPosition.GetZ() > float(m_volVolume.GetSizeZ()-1));
			return *this;
		};

		const Type & operator*() const
		{
			return m_volVolume.Get(unsigned int(m_vecPosition.GetX()),unsigned int(m_vecPosition.GetY()),unsigned int(m_vecPosition.GetZ()));
		};

	protected:

		void intersect()
		{
			m_bAtEnd = false;

			const Vector vecMinimum(0.0f,0.0f,0.0f);
			const Vector vecMaximum(float(m_volVolume.GetSizeX()-1),float(m_volVolume.GetSizeY()-1),float(m_volVolume.GetSizeZ()-1));

			bool bInside = true;
			Vector vecCandidate;

			enum Quadrant
			{
				LEFT=0,RIGHT=1,MIDDLE=2
			} eQuadrant[3];


			/* Find candidate planes; this loop can be avoided if
			rays cast all from the eye(assume perpsective view) */
			for (unsigned int i=0; i < 3; i++)
			{
				if(m_vecPosition[i] < vecMinimum[i])
				{
					eQuadrant[i] = LEFT;
					vecCandidate[i] = vecMinimum[i];
					bInside = false;
				}
				else if (m_vecPosition[i] > vecMaximum[i])
				{
					eQuadrant[i] = RIGHT;
					vecCandidate[i] = vecMaximum[i];
					bInside = false;
				}
				else
				{
					eQuadrant[i] = MIDDLE;
				}
			}

			if (!bInside)
			{
				m_bAtEnd = true;

				Vector vecT;

				/* Calculate T distances to candidate planes */
				for (unsigned int i = 0; i < 3; i++)
				{
					if (eQuadrant[i] != MIDDLE && m_vecDirection[i] != 0.0f)
						vecT[i] = (vecCandidate[i]-m_vecPosition[i]) / m_vecDirection[i];
					else
						vecT[i] = -1.0f;
				}

				unsigned int uPlane = 0;

				/* Get largest of the maxT's for final choice of intersection */
				for (unsigned int i = 1; i < 3; i++)
				{
					if (vecT[uPlane] < vecT[i])
						uPlane = i;
				}

				/* Check final candidate actually inside box */
				if (vecMaximum[uPlane] < 0.0f)
					return;

				Vector vecIntersection;

				for (unsigned int i = 0; i < 3; i++)
				{
					if (uPlane != i)
					{
						vecIntersection[i] = m_vecPosition[i] + vecT[uPlane] * m_vecDirection[i];

						if (vecIntersection[i] < vecMinimum[i] || vecIntersection[i] > vecMaximum[i])
							return;
					}
					else
					{
						vecIntersection[i] = vecCandidate[i];
					}
				}

				m_vecPosition = vecIntersection;
				m_bAtEnd = false;
			}
		};

	private:

		const Volume & m_volVolume;
		Vector m_vecPosition;
		Vector m_vecDirection;
		bool m_bAtEnd;
	};

	Volume() : m_uTexture(0), m_uSizeX(0), m_uSizeY(0), m_uSizeZ(0), m_uBlocksX(0), m_uBlocksY(0), m_uBlocksZ(0), m_pData(NULL), m_pOctree(NULL), m_vecScale(1.0f,1.0f,1.0f), m_bUpdate(false), m_bResize(false), m_uLevelOfDetail(0)
	{
		glGenTextures(1,&m_uTexture);
		const GLenum glError = glGetError();

		if (glError != GL_NO_ERROR)
		{
			std::cerr << "Error generating texture (" << gluErrorString(glError) << ")." << std::endl << std::endl;
			throw Exception("Error generating texture (%s).",gluErrorString(glError));
		}

		resize(BLOCKDIMENSION,BLOCKDIMENSION,BLOCKDIMENSION);
	};

	Volume(const Volume & volOther) : m_uTexture(0), m_uSizeX(0), m_uSizeY(0), m_uSizeZ(0), m_uBlocksX(0), m_uBlocksY(0), m_uBlocksZ(0), m_pData(NULL), m_pOctree(NULL), m_vecScale(1.0f,1.0f,1.0f), m_bUpdate(false), m_bResize(false), m_uLevelOfDetail(0)
	{
		glGenTextures(1,&m_uTexture);
		const GLenum glError = glGetError();

		if (glError != GL_NO_ERROR)
		{
			std::cerr << "Error generating texture (" << gluErrorString(glError) << ")." << std::endl << std::endl;
			throw Exception("Error generating texture (%s).",gluErrorString(glError));
		}

		(*this) = volOther;
	};
	
	~Volume(void)
	{
		if (m_pOctree)
		{
			delete m_pOctree;
			m_pOctree = NULL;
		}

		if (m_pData)
		{
			delete[] m_pData;
			m_pData = NULL;
		}

		if (m_uTexture)
		{
			glDeleteTextures(1,&m_uTexture);
			const GLenum glError = glGetError();

			if (glError != GL_NO_ERROR)
			{
				std::cerr << "Error deleting texture (" << gluErrorString(glError) << ")." << std::endl << std::endl;
				throw Exception("Error deleting texture (%s).",gluErrorString(glError));
			}
		}
	};

	void resize(const unsigned int uSizeX,const unsigned int uSizeY,const unsigned int uSizeZ)
	{
		if (uSizeX != m_uSizeX || uSizeY != m_uSizeY || uSizeZ != m_uSizeZ)
		{
			m_uSizeX = uSizeX;
			m_uSizeY = uSizeY;
			m_uSizeZ = uSizeZ;

			m_uBlocksX = uSizeX / BLOCKDIMENSION;
			m_uBlocksY = uSizeY / BLOCKDIMENSION;
			m_uBlocksZ = uSizeZ / BLOCKDIMENSION;

			m_uBlocksX += (uSizeX % BLOCKDIMENSION) > 0;
			m_uBlocksY += (uSizeY % BLOCKDIMENSION) > 0;
			m_uBlocksZ += (uSizeZ % BLOCKDIMENSION) > 0;
			
			std::cout << "Resizing volume ..." << std::endl;
			std::cout << "Volume dimensions: (" << m_uSizeX << "," << m_uSizeY << "," << m_uSizeZ << ")" << std::endl;
			std::cout << "Volume blocks: (" << m_uBlocksX << "," << m_uBlocksY << "," << m_uBlocksZ << ")" << std::endl;

			if (m_pData)
			{
				delete[] m_pData;
				m_pData = NULL;
			}

			m_pData = new Block[m_uBlocksX*m_uBlocksY*m_uBlocksZ];

			if (m_pOctree)
			{
				delete m_pOctree;
				m_pOctree = NULL;
			}

			m_pOctree = new Octree(*this);

			m_vecUpdate.assign(m_uBlocksX*m_uBlocksY*m_uBlocksZ,true);
			m_bUpdate = true;
			m_bResize = true;
			m_uLevelOfDetail = 0;

			std::cout << "Success resizing volume." << std::endl;
		}
	};

	void clear()
	{
		for (unsigned int i=0;i < GetBlocks(); i++)
		{
			m_pData[i].clear();
			m_vecUpdate[i] = true;
		}
		
		if (m_pOctree)
		{
			delete m_pOctree;
			m_pOctree = NULL;
		}

		m_pOctree = new Octree(*this);
		m_bUpdate = true;
	};

	const unsigned int GetSize() const
	{
		return m_uSizeX*m_uSizeY*m_uSizeZ;
	};

	const unsigned int GetSizeX() const
	{
		return m_uSizeX;
	};

	const unsigned int GetSizeY() const
	{
		return m_uSizeY;
	};

	const unsigned int GetSizeZ() const
	{
		return m_uSizeZ;
	};

	const unsigned int GetBlocks() const
	{
		return m_uBlocksX*m_uBlocksY*m_uBlocksZ;
	};

	const unsigned int GetBlocksX() const
	{
		return m_uBlocksX;
	};

	const unsigned int GetBlocksY() const
	{
		return m_uBlocksY;
	};

	const unsigned int GetBlocksZ() const
	{
		return m_uBlocksZ;
	};

	void SetScale(const Vector & vecScale)
	{
		m_vecScale = vecScale;
	};

	const Vector & GetScale() const
	{
		return m_vecScale;
	};

	const Octree & GetOctree() const
	{
		return *m_pOctree;
	};

	void Set(const unsigned int uX, const unsigned int uY, const unsigned int uZ, const Type & tValue)
	{
		if (uX < GetSizeX() && uY < GetSizeY() && uZ < GetSizeZ())
		{
			const unsigned int uBlockX = uX / BLOCKDIMENSION;
			const unsigned int uBlockY = uY / BLOCKDIMENSION;
			const unsigned int uBlockZ = uZ / BLOCKDIMENSION;
			const unsigned int uBlockIndex = uBlockX + uBlockY*m_uBlocksX + uBlockZ*m_uBlocksX*m_uBlocksY;

			const unsigned int uOffsetX = uX % BLOCKDIMENSION;
			const unsigned int uOffsetY = uY % BLOCKDIMENSION;
			const unsigned int uOffsetZ = uZ % BLOCKDIMENSION;

			m_pData[uBlockIndex].Set(uOffsetX,uOffsetY,uOffsetZ,tValue);
			m_pOctree->update(uX,uY,uZ);
			
			m_vecUpdate[uBlockIndex] = true;
			m_bUpdate = true;
/*
			Type tDefault;

			if (tValue != tDefault)
			{
				Vector vecPosition(float(uX),float(uY),float(uZ));
				Vector vecMinimum
			}
*/
		}
	};

	const Type & Get(const unsigned int uX, const unsigned int uY, const unsigned int uZ) const
	{
		const unsigned int uVolumeX = uX % GetSizeX();
		const unsigned int uVolumeY = uY % GetSizeY();
		const unsigned int uVolumeZ = uZ % GetSizeZ();

		const unsigned int uBlockX = uVolumeX / BLOCKDIMENSION;
		const unsigned int uBlockY = uVolumeY / BLOCKDIMENSION;
		const unsigned int uBlockZ = uVolumeZ / BLOCKDIMENSION;
		const unsigned int uBlockIndex = uBlockX + uBlockY*m_uBlocksX + uBlockZ*m_uBlocksX*m_uBlocksY;

		const unsigned int uOffsetX = uVolumeX % BLOCKDIMENSION;
		const unsigned int uOffsetY = uVolumeY % BLOCKDIMENSION;
		const unsigned int uOffsetZ = uVolumeZ % BLOCKDIMENSION;
		
		return m_pData[uBlockIndex].Get(uOffsetX,uOffsetY,uOffsetZ);
	};

	void SetBlock(const unsigned int uX, const unsigned int uY, const unsigned int uZ, const Block &bloBlock)
	{
		if (uX < GetSizeX() && uY < GetSizeY() && uZ < GetSizeZ())
		{
			const unsigned int uBlockX = uX / BLOCKDIMENSION;
			const unsigned int uBlockY = uY / BLOCKDIMENSION;
			const unsigned int uBlockZ = uZ / BLOCKDIMENSION;
			const unsigned int uBlockIndex = uBlockX + uBlockY*m_uBlocksX + uBlockZ*m_uBlocksX*m_uBlocksY;

			m_pData[uBlockIndex] = bloBlock;
			m_pOctree->update(uX,uY,uZ);

			m_vecUpdate[uBlockIndex] = true;
			m_bUpdate = true;
		}
	};

	const Block & GetBlock(const unsigned int uX, const unsigned int uY, const unsigned int uZ) const
	{
		const unsigned int uVolumeX = uX % GetSizeX();
		const unsigned int uVolumeY = uY % GetSizeY();
		const unsigned int uVolumeZ = uZ % GetSizeZ();

		const unsigned int uBlockX = uVolumeX / BLOCKDIMENSION;
		const unsigned int uBlockY = uVolumeY / BLOCKDIMENSION;
		const unsigned int uBlockZ = uVolumeZ / BLOCKDIMENSION;
		const unsigned int uBlockIndex = uBlockX + uBlockY*m_uBlocksX + uBlockZ*m_uBlocksX*m_uBlocksY;

		return m_pData[uBlockIndex];
	};

	const unsigned int GetLevelOfDetail() const
	{
		return m_uLevelOfDetail;
	};

	void bind(unsigned int uLevelOfDetail = 1)
	{
		if (m_uTexture)
		{
			glEnable(GL_TEXTURE_3D);
			glBindTexture(GL_TEXTURE_3D,m_uTexture);

			const GLenum glError = glGetError();

			if (glError != GL_NO_ERROR)
			{
				std::cerr << "Error binding texture (" << gluErrorString(glError) << ")." << std::endl << std::endl;
				throw Exception("Error binding texture (%s).",gluErrorString(glError));
			}
/*
			if (m_uLevelOfDetail != uLevelOfDetail)
			{
				m_vecUpdate.assign(m_uBlocksX*m_uBlocksY*m_uBlocksZ,true);
				m_bUpdate = true;
				m_bResize = true;
				m_uLevelOfDetail = uLevelOfDetail;
			}
*/
			if (m_bUpdate)
			{
				float vfBorderColor[4] = {0.0f,0.0f,0.0f,0.0f};
				glTexParameterfv(GL_TEXTURE_3D, GL_TEXTURE_BORDER_COLOR, vfBorderColor);
				glTexParameteri(GL_TEXTURE_3D,GL_TEXTURE_WRAP_S,GL_CLAMP_TO_BORDER);
				glTexParameteri(GL_TEXTURE_3D,GL_TEXTURE_WRAP_T,GL_CLAMP_TO_BORDER);
				glTexParameteri(GL_TEXTURE_3D,GL_TEXTURE_WRAP_R,GL_CLAMP_TO_BORDER);

				glTexParameteri(GL_TEXTURE_3D,GL_TEXTURE_MAG_FILTER,GL_LINEAR);
				glTexParameteri(GL_TEXTURE_3D,GL_TEXTURE_MIN_FILTER,GL_LINEAR);

				if (m_bResize)
				{
					GLenum glError = GL_NO_ERROR;

					do				
					{
						const unsigned int uBlockDimension = BLOCKDIMENSIONLOD(m_uLevelOfDetail);
						const unsigned int uSizeX = (m_uBlocksX*uBlockDimension);
						const unsigned int uSizeY = (m_uBlocksY*uBlockDimension);
						const unsigned int uSizeZ = (m_uBlocksZ*uBlockDimension);

						glTexImage3D(GL_TEXTURE_3D,0, glInternalFormat<Type>(),uSizeX,uSizeY,uSizeZ,0,glFormat<Type>(),glType<Type>(),NULL);
						glError = glGetError();

						if (glError != GL_NO_ERROR)
							m_uLevelOfDetail++;
					}
					while(glError != GL_NO_ERROR);


					/*
					if (glError != GL_NO_ERROR)
					{
						std::cerr << "Error uploading texture (" << gluErrorString(glError) << ")." << std::endl << std::endl;
						exit(EXIT_FAILURE);
					}
					*/

					m_bResize = false;
				}

				const unsigned int uBlockDimension = BLOCKDIMENSIONLOD(m_uLevelOfDetail);

				for (unsigned int uZ=0;uZ < m_uBlocksZ;uZ++)
				{
					for (unsigned int uY=0;uY < m_uBlocksY;uY++)
					{
						for (unsigned int uX=0;uX < m_uBlocksX;uX++)
						{
							const unsigned int uBlockIndex = uX + uY*m_uBlocksX + uZ*m_uBlocksX*m_uBlocksY;
							const unsigned int uPositionX = uX * uBlockDimension;
							const unsigned int uPositionY = uY * uBlockDimension;
							const unsigned int uPositionZ = uZ * uBlockDimension;

							if (m_vecUpdate[uBlockIndex])
							{
								glTexSubImage3D(GL_TEXTURE_3D,0,uPositionX,uPositionY,uPositionZ,uBlockDimension,uBlockDimension,uBlockDimension,glFormat<Type>(),glType<Type>(),(void*)(m_pData[uBlockIndex].Get(m_uLevelOfDetail)));
								const GLenum glError = glGetError();

								if (glError != GL_NO_ERROR)
								{
									std::cerr << "Error updating block (" << gluErrorString(glError) << ")." << std::endl << std::endl;
									throw Exception("Error updating block (%s).",gluErrorString(glError));
								}

								m_vecUpdate[uBlockIndex] = false;
							}
						}
					}
				}

				m_bUpdate = false;
			}
		}
	};

	void release()
	{
		if (m_uTexture)
		{
			glDisable(GL_TEXTURE_3D);
			glBindTexture(GL_TEXTURE_3D,0);

			const GLenum glError = glGetError();

			if (glError != GL_NO_ERROR)
			{
				std::cerr << "Error binding texture (" << gluErrorString(glError) << ")." << std::endl << std::endl;
				throw Exception("Error binding texture (%s).",gluErrorString(glError));
			}
		}
	};

	Volume & operator=(const Volume & volOther)
	{
		m_uSizeX = volOther.m_uSizeX;
		m_uSizeY = volOther.m_uSizeY;
		m_uSizeZ = volOther.m_uSizeZ;

		m_uBlocksX = volOther.m_uBlocksX;
		m_uBlocksY = volOther.m_uBlocksY;
		m_uBlocksZ = volOther.m_uBlocksZ;

		std::cout << "Copying volume ..." << std::endl;
		std::cout << "Volume dimensions: (" << m_uSizeX << "," << m_uSizeY << "," << m_uSizeZ << ")" << std::endl;
		std::cout << "Volume blocks: (" << m_uBlocksX << "," << m_uBlocksY << "," << m_uBlocksZ << ")" << std::endl;

		if (m_pData)
		{
			delete[] m_pData;
			m_pData = NULL;
		}

		m_pData = new Block[m_uBlocksX*m_uBlocksY*m_uBlocksZ];

		for (unsigned int i=0;i<m_uBlocksX*m_uBlocksY*m_uBlocksZ;i++)
			m_pData[i] = volOther.m_pData[i];

		if (m_pOctree)
		{
			delete m_pOctree;
			m_pOctree = NULL;
		}

		m_pOctree = new Octree(*this);

		m_vecUpdate.assign(m_uBlocksX*m_uBlocksY*m_uBlocksZ,true);
		m_bUpdate = true;
		m_bResize = true;

		m_vecScale = volOther.m_vecScale;
		m_uLevelOfDetail = volOther.m_uLevelOfDetail;

		std::cout << "Success copying volume." << std::endl;
		return *this;
	};

private:

	unsigned int m_uTexture;
	
	unsigned int m_uSizeX;
	unsigned int m_uSizeY;
	unsigned int m_uSizeZ;

	unsigned int m_uBlocksX;
	unsigned int m_uBlocksY;
	unsigned int m_uBlocksZ;

	unsigned int m_uLevelOfDetail;
	Vector m_vecScale;

	Block *m_pData;
	Octree *m_pOctree;
	
	std::vector<bool> m_vecUpdate;	
	bool m_bUpdate;
	bool m_bResize;
};