/*********************************************************************

Name:		Raytracer
Author:		Kamil Szatkowski "Netrix" (C)
Website:	http://www.netrix.org.pl/

*********************************************************************/
#include "UniformSpaceSubdivision.hpp"
#include "TriBoxIntersection.hpp"
#include <stdio.h>
#pragma warning(disable: 4996)
using namespace NIne;
using namespace Regions;

namespace
{
	const NIne::NUint32 DATA_VECTOR_REALLOC_SIZE = 4;
	const float BIG_FLOAT = 99999999999999999999.9f;
}

//////////////////////////////////////////////////////////
UniformSpaceSubdivision::UniformSpaceSubdivision()
: m_bCreate(false)
{
}
/********************************************************/
void UniformSpaceSubdivision::createSubdivision(Scene* pScene, bool bResetCache)
{
	const FaceDataArray& aFaceData = pScene->getFaceData();
	const NMVector3f& vMin = pScene->getDomainMin();
	const NMVector3f& vMax = pScene->getDomainMax();

	m_pScene = pScene;

	printf("Loading uss from file... ");
	if(loadSubdivision("uss.tmp"))	
	{ 
		printf("OK\n");
		return; 
	}
	else if(bResetCache)	{ printf("RESET\n"); }
	else					{ printf("FAILED\n"); }

	printf("Building uss\n");

	m_v3Size = vMax - vMin;
	m_v3Min = vMin;		// Global min
	m_v3Max = vMax;		// Global max

	// Subdivision dimensions
	NSize_t iFaceCount = aFaceData.GetSize();
	float v = pow((float)iFaceCount / (m_v3Size.x * m_v3Size.y * m_v3Size.z), 0.333333333f);

	NMVector3f vDim = v * m_v3Size;		// Voxel Dimension

	m_subdivDim[0] = (NUint32)vDim.x;
	m_subdivDim[1] = (NUint32)vDim.y;
	m_subdivDim[2] = (NUint32)vDim.z;

	m_v3Size /= NMVector3fLoad((float)m_subdivDim[0], (float)m_subdivDim[1], (float)m_subdivDim[2]);

	// Creating structure
	m_aHashes.Create(m_subdivDim[0] * m_subdivDim[1] * m_subdivDim[2]);
	m_aCells.Create(DATA_VECTOR_REALLOC_SIZE);

	for(NSize_t i = 0; i < m_aHashes.GetSize(); ++i)
	{
		m_aHashes[i] = NMAX_UINT32;
	}

	// Filling voxels with triangles
	NMVector3f v3VoxelMin, v3VoxelMax;

	v3VoxelMin.y = m_v3Min.y;
	v3VoxelMax.y = m_v3Min.y + m_v3Size.y;

	for(int y = 0; y < m_subdivDim[1]; ++y)
	{
		v3VoxelMin.z = m_v3Min.z;
		v3VoxelMax.z = m_v3Min.z + m_v3Size.z;

		for(int z = 0; z < m_subdivDim[2]; ++z)
		{
			v3VoxelMin.x = m_v3Min.x;
			v3VoxelMax.x = m_v3Min.x + m_v3Size.x;

			for(int x = 0; x < m_subdivDim[0]; ++x)
			{
				NUint32 uIndex = y * m_subdivDim[2] * m_subdivDim[0] + z * m_subdivDim[0] + x;

				// For each face
				for(NUint32 iFace = 0; iFace < iFaceCount; ++iFace)
				{
					if(TriBoxIntersection((v3VoxelMax + v3VoxelMin) * 0.5f,
											(v3VoxelMax - v3VoxelMin) * 0.5f,
											aFaceData[iFace].pVertices[0]->v3Position,
											aFaceData[iFace].pVertices[1]->v3Position,
											aFaceData[iFace].pVertices[2]->v3Position))
					{
						if(m_aHashes[uIndex] == NMAX_UINT32)
						{
							NUint32Vector vec;
							vec.Create(DATA_VECTOR_REALLOC_SIZE, DATA_VECTOR_REALLOC_SIZE);
							m_aHashes[uIndex] = (NUint32)m_aCells.GetSize();
							m_aCells.PushElement(vec);
						}

						m_aCells[m_aHashes[uIndex]].PushElement(iFace);
					}
				}

				v3VoxelMin.x += m_v3Size.x;
				v3VoxelMax.x += m_v3Size.x;
			}

			v3VoxelMin.z += m_v3Size.z;
			v3VoxelMax.z += m_v3Size.z;
		}

		v3VoxelMin.y += m_v3Size.y;
		v3VoxelMax.y += m_v3Size.y;
	}

	m_bCreate = true;

	saveSubdivision("uss.tmp");
}
/********************************************************/
void UniformSpaceSubdivision::saveSubdivision(const char* szFile)
{
	FILE* pFile = fopen(szFile, "w");

	fprintf(pFile, "SceneFile %s\n", m_pScene->getSceneName());
	fprintf(pFile, "v3Min %f %f %f\n", m_v3Min.x, m_v3Min.y, m_v3Min.z);
	fprintf(pFile, "v3Max %f %f %f\n", m_v3Max.x, m_v3Max.y, m_v3Max.z);
	fprintf(pFile, "v3Size %f %f %f\n", m_v3Size.x, m_v3Size.y, m_v3Size.z);
	fprintf(pFile, "subdivDim %d %d %d\n\n", m_subdivDim[0], m_subdivDim[1], m_subdivDim[2]);

	fprintf(pFile, "hashes %d\n", m_aHashes.GetSize());

	for(NUint32 i = 0; i < m_aHashes.GetSize(); ++i)
	{
		fprintf(pFile, "%d\n", m_aHashes[i]);
	}

	fprintf(pFile, "cells %d\n", m_aCells.GetSize());

	for(NUint32 i = 0; i < m_aCells.GetSize(); ++i)
	{
		fprintf(pFile, "%d: ", m_aCells[i].GetSize());

		for(NUint32 k = 0; k < m_aCells[i].GetSize(); ++k)
		{	
			fprintf(pFile, "%d ", m_aCells[i][k]);
		}

		fprintf(pFile, "\n");
	}

	fclose(pFile);
}
/********************************************************/
bool UniformSpaceSubdivision::loadSubdivision(const char* szFile)
{
	FILE* pFile = fopen(szFile, "r");
	if(pFile == 0) return false;

	char szName[255];
	fscanf(pFile, "SceneFile %s\n", szName);
	if(strcmp(szName, m_pScene->getSceneName()) != 0)	{ return false; }

	fscanf(pFile, "v3Min %f %f %f\n", &m_v3Min.x, &m_v3Min.y, &m_v3Min.z);
	fscanf(pFile, "v3Max %f %f %f\n", &m_v3Max.x, &m_v3Max.y, &m_v3Max.z);
	fscanf(pFile, "v3Size %f %f %f\n", &m_v3Size.x, &m_v3Size.y, &m_v3Size.z);
	fscanf(pFile, "subdivDim %d %d %d\n\n", &m_subdivDim[0], &m_subdivDim[1], &m_subdivDim[2]);

	NUint32 uSize = 0;
	fscanf(pFile, "hashes %d\n", &uSize);
	if(uSize == 0) return false;
	m_aHashes.Create(uSize);

	for(NUint32 i = 0; i < m_aHashes.GetSize(); ++i)
	{
		fscanf(pFile, "%d\n", &m_aHashes[i]);
	}

	fscanf(pFile, "cells %d\n", &uSize);
	m_aCells.Create(uSize);
	m_aCells.Resize(uSize);

	for(NUint32 i = 0; i < m_aCells.GetSize(); ++i)
	{
		fscanf(pFile, "%d: ", &uSize);

		m_aCells[i].Create(uSize);
		m_aCells[i].Resize(uSize);

		for(NUint32 k = 0; k < m_aCells[i].GetSize(); ++k)
		{	
			fscanf(pFile, "%d ", &m_aCells[i][k]);
		}

		fscanf(pFile, "\n");
	}

	fclose(pFile);
	return true;
}
/********************************************************/
void UniformSpaceSubdivision::releaseSubdivision()
{
	// Removing cells
	for(NSize_t i = 0; i < m_aCells.GetSize(); ++i)
	{
		m_aCells[i].Release();
	}
	m_aCells.Release();
	m_aHashes.Release();
}
/********************************************************/
bool UniformSpaceSubdivision::setUpTriangleSearch(const NIne::NMVector3f& v3Origin, const NIne::NMVector3f& v3Direction)
{
	// Looking for Origin beginning voxel
	NMVector3f v3Temp = v3Direction;
	m_v3TVec = v3Origin;

	NUint32 uTVecRegion = GetRegion(m_v3Min, m_v3Max, v3Origin);
	
	if(uTVecRegion != 0)
	{
		// Origin outside voxel - calculating second point
		float fMaxLength = NMVector3fLength(m_v3Max - m_v3Min);
		NMVector3f vSndPoint = v3Origin + v3Direction * fMaxLength;

		// Not in scene
		if(!InRegion(uTVecRegion, GetRegion(m_v3Min, m_v3Max, vSndPoint)))
		{
			return false;
		}
		
		// Moving origin to scene voxel
		if(!InRegion(uTVecRegion, X_MIN))
		{
			float fScale = (m_v3Min.x - m_v3TVec.x) / v3Temp.x;
			m_v3TVec += v3Direction * fScale;
			uTVecRegion ^= X_MIN;
		}
		if(!InRegion(uTVecRegion, X_MAX))
		{
			float fScale = (m_v3Max.x - m_v3TVec.x) / v3Temp.x;
			m_v3TVec += v3Direction * fScale;
			uTVecRegion ^= X_MAX;
		}
		if(!InRegion(uTVecRegion, Y_MIN))
		{
			float fScale = (m_v3Min.y - m_v3TVec.y) / v3Temp.y;
			m_v3TVec += v3Direction * fScale;
			uTVecRegion ^= Y_MIN;
		}
		if(!InRegion(uTVecRegion, Y_MAX))
		{
			float fScale = (m_v3Max.y - m_v3TVec.y) / v3Temp.y;
			m_v3TVec += v3Direction * fScale;
			uTVecRegion ^= Y_MAX;
		}
		if(!InRegion(uTVecRegion, Z_MIN))
		{
			float fScale = (m_v3Min.z - m_v3TVec.z) / v3Temp.z;
			m_v3TVec += v3Direction * fScale;
			uTVecRegion ^= Z_MIN;
		}
		if(!InRegion(uTVecRegion, Z_MAX))
		{
			float fScale = (m_v3Max.z - m_v3TVec.z) / v3Temp.z;
			m_v3TVec += v3Direction * fScale;
			uTVecRegion ^= Z_MAX;
		}
	}

	m_v3TVec = NMVector3fMax((m_v3TVec - m_v3Min) / m_v3Size, NMVector3fLoadZeros());	

	// Start voxel Indices 
	m_voxelIndex[0] = min((int)m_v3TVec.x, m_subdivDim[0] - 1);
	m_voxelIndex[1] = min((int)m_v3TVec.y, m_subdivDim[1] - 1);
	m_voxelIndex[2] = min((int)m_v3TVec.z, m_subdivDim[2] - 1);

	// Voxels direction steps
	m_voxelSteps[0] = v3Temp.x < 0.0f ? -1 : 1;
	m_voxelSteps[1] = v3Temp.y < 0.0f ? -1 : 1;
	m_voxelSteps[2] = v3Temp.z < 0.0f ? -1 : 1;

	// t-vec voxel begins
	m_v3TVec.x = v3Temp.x != 0.0f ? (m_v3Min.x + (m_voxelIndex[0] + (v3Temp.x < 0.0f ? 1 : 0)) * m_v3Size.x - v3Origin.x) / v3Temp.x : v3Origin.x;
	m_v3TVec.y = v3Temp.y != 0.0f ? (m_v3Min.y + (m_voxelIndex[1] + (v3Temp.y < 0.0f ? 1 : 0)) * m_v3Size.y - v3Origin.y) / v3Temp.y : v3Origin.y;
	m_v3TVec.z = v3Temp.z != 0.0f ? (m_v3Min.z + (m_voxelIndex[2] + (v3Temp.z < 0.0f ? 1 : 0)) * m_v3Size.z - v3Origin.z) / v3Temp.z : v3Origin.z;

	// dt-vec voxel steps
	m_v3DtVec.x = v3Temp.x != 0.0f ? fabsf(m_v3Size.x / v3Temp.x) : BIG_FLOAT;
	m_v3DtVec.y = v3Temp.y != 0.0f ? fabsf(m_v3Size.y / v3Temp.y) : BIG_FLOAT;
	m_v3DtVec.z = v3Temp.z != 0.0f ? fabsf(m_v3Size.z / v3Temp.z) : BIG_FLOAT;

	return true;
}
/********************************************************/
bool UniformSpaceSubdivision::findNextVoxel()
{
	NUint32 uIndex;
	NMVector3f v3Tn;
	bool bValue;

	do
	{
		if((v3Tn.x = m_v3TVec.x + m_v3DtVec.x) < (v3Tn.y = m_v3TVec.y + m_v3DtVec.y))
		{
			if(v3Tn.x < (v3Tn.z = m_v3TVec.z + m_v3DtVec.z))
			{
				m_voxelIndex[0] += m_voxelSteps[0];
				m_v3TVec.x = v3Tn.x;
			}
			else
			{
				m_voxelIndex[2] += m_voxelSteps[2];
				m_v3TVec.z = v3Tn.z;
			}
		}
		else
		{
			if(v3Tn.y < (v3Tn.z = m_v3TVec.z + m_v3DtVec.z))
			{
				m_voxelIndex[1] += m_voxelSteps[1];
				m_v3TVec.y = v3Tn.y;
			}
			else
			{
				m_voxelIndex[2] += m_voxelSteps[2];
				m_v3TVec.z = v3Tn.z;
			}
		}

		uIndex = m_voxelIndex[1] * m_subdivDim[2] * m_subdivDim[0] + m_voxelIndex[2] * m_subdivDim[0] + m_voxelIndex[0];
		bValue = m_voxelIndex[0] >= 0 && m_voxelIndex[0] < m_subdivDim[0]
			  && m_voxelIndex[1] >= 0 && m_voxelIndex[1] < m_subdivDim[1]
			  && m_voxelIndex[2] >= 0 && m_voxelIndex[2] < m_subdivDim[2];
	}
	while(bValue && m_aHashes[uIndex] == NMAX_UINT32);

	m_bCalculated = false;

	return bValue;
}
/********************************************************/
bool UniformSpaceSubdivision::findNextVoxel(float fMaxT)
{
	NUint32 uIndex;
	NMVector3f v3Tn;
	bool bValue = true;

	do
	{
		if((v3Tn.x = m_v3TVec.x + m_v3DtVec.x) < (v3Tn.y = m_v3TVec.y + m_v3DtVec.y))
		{
			if(v3Tn.x < (v3Tn.z = m_v3TVec.z + m_v3DtVec.z))
			{
				m_voxelIndex[0] += m_voxelSteps[0];
				m_v3TVec.x = v3Tn.x;
				bValue = v3Tn.x < fMaxT;
			}
			else
			{
				m_voxelIndex[2] += m_voxelSteps[2];
				m_v3TVec.z = v3Tn.z;
				bValue = v3Tn.z < fMaxT;
			}
		}
		else
		{
			if(v3Tn.y < (v3Tn.z = m_v3TVec.z + m_v3DtVec.z))
			{
				m_voxelIndex[1] += m_voxelSteps[1];
				m_v3TVec.y = v3Tn.y;
				bValue = v3Tn.y < fMaxT;
			}
			else
			{
				m_voxelIndex[2] += m_voxelSteps[2];
				m_v3TVec.z = v3Tn.z;
				bValue = v3Tn.z < fMaxT;
			}
		}

		uIndex = m_voxelIndex[1] * m_subdivDim[2] * m_subdivDim[0] + m_voxelIndex[2] * m_subdivDim[0] + m_voxelIndex[0];
		bValue = bValue && m_voxelIndex[0] >= 0 && m_voxelIndex[0] < m_subdivDim[0]
			  && m_voxelIndex[1] >= 0 && m_voxelIndex[1] < m_subdivDim[1]
			  && m_voxelIndex[2] >= 0 && m_voxelIndex[2] < m_subdivDim[2];
	}
	while(bValue && m_aHashes[uIndex] == NMAX_UINT32);

	m_bCalculated = false;

	return bValue;
}
/********************************************************/
bool UniformSpaceSubdivision::checkPointInVoxel(const NIne::NMVector3f& v3Point)
{
	if(!m_bCalculated)
	{
		// X
		if(m_v3DtVec.x < 0.0f)
		{
			m_v3LocalMax.x = m_v3TVec.x;
			m_v3LocalMin.x = m_v3LocalMax.x - m_v3Size.x;
		}
		else
		{
			m_v3LocalMin.x = m_v3TVec.x;
			m_v3LocalMax.x = m_v3LocalMin.x + m_v3Size.x;
			
		}
		// Y
		if(m_v3DtVec.y < 0.0f)
		{
			m_v3LocalMax.y = m_v3TVec.y;
			m_v3LocalMin.y = m_v3LocalMax.y - m_v3Size.y;
		}
		else
		{
			m_v3LocalMin.y = m_v3TVec.y;
			m_v3LocalMax.y = m_v3LocalMin.y + m_v3Size.y;
			
		}
		// Z
		if(m_v3DtVec.z < 0.0f)
		{
			m_v3LocalMax.z = m_v3TVec.z;
			m_v3LocalMin.z = m_v3LocalMax.z - m_v3Size.z;
		}
		else
		{
			m_v3LocalMin.z = m_v3TVec.z;
			m_v3LocalMax.z = m_v3LocalMin.z + m_v3Size.z;
			
		}
		m_bCalculated = true;
	}

	return GetRegion(m_v3LocalMin, m_v3LocalMax, v3Point) == 0;
}
/********************************************************/
const UniformSpaceSubdivision::NUint32Vector* UniformSpaceSubdivision::getTriangles() const
{
	NUint32 uIndex = m_voxelIndex[1] * m_subdivDim[2] * m_subdivDim[0] + m_voxelIndex[2] * m_subdivDim[0] + m_voxelIndex[0];

	return m_aHashes[uIndex] != NMAX_UINT32 ? &m_aCells[m_aHashes[uIndex]] : null;
}
/********************************************************/
const UniformSpaceSubdivision::NUint32Vector* UniformSpaceSubdivision::getTriangles(NUint32 uIndex) const
{
		return m_aHashes[uIndex] != NMAX_UINT32 ? &m_aCells[m_aHashes[uIndex]] : null;
}
/********************************************************/
NUint32 UniformSpaceSubdivision::getVoxelIndex() const
{
	return m_voxelIndex[1] * m_subdivDim[2] * m_subdivDim[0] + m_voxelIndex[2] * m_subdivDim[0] + m_voxelIndex[0];
}
/********************************************************/
const FaceData* UniformSpaceSubdivision::findNearestFace(const NIne::NMVector3f& v3Origin, const NIne::NMVector3f& v3Direction, float fMaxDistance, RayTestOutput* opRTO)
{
	const FaceData* pOutFace = null;
	bool bChanges = false;

	_NALIGN_16 RayTestOutput rto;
	opRTO->t = fMaxDistance;

	if(setUpTriangleSearch(v3Origin, v3Direction))
	{
		const NUint32Vector* pTriangles;

		do
		{
			bChanges = false;

			pTriangles = getTriangles();
			for(NUint32 iFace = 0; pTriangles != null && iFace < pTriangles->GetSize(); ++iFace)
			{
				const FaceData* pFace = m_pScene->getFaceData().GetBuffer() + (*pTriangles)[iFace];

				if(m_pScene->testTriangle(pFace, v3Origin, v3Direction, opRTO->t, &rto))
				{
					pOutFace = pFace;
					*opRTO = rto;
					bChanges = true;
				}
			}
		}
		while(!(bChanges && checkPointInVoxel(opRTO->oPoint)) && findNextVoxel());
	}

	return pOutFace;
}
/********************************************************/
bool UniformSpaceSubdivision::findObstacle(const NIne::NMVector3f& v3Origin, const NIne::NMVector3f& v3Direction, float fMaxDistance)
{
	_NALIGN_16 RayTestOutput rto;
	bool bFound = false;

	if(setUpTriangleSearch(v3Origin, v3Direction))
	{
		const NUint32Vector* pTriangles;

		do
		{
			pTriangles = getTriangles();

			for(NUint32 iFace = 0; !bFound && pTriangles != null && iFace < pTriangles->GetSize(); ++iFace)
			{
				const FaceData* pFace = m_pScene->getFaceData().GetBuffer() + (*pTriangles)[iFace];

				bFound = m_pScene->testTriangle(pFace, v3Origin, v3Direction, fMaxDistance, &rto);
			}
		}
		while(!bFound && findNextVoxel(fMaxDistance));
	}

	return bFound;
}