/*
	Tools_Adjacency.cpp

	Created by Richard Rice - 24/06/2002

	Copyright 2002 Rebellion, All Rights Reserved.
*/

#include "Core/Asura.h"
#include "Misc/Tools_Adjacency.h"

#include "Debugging/Asura_Assert.h"
#include "Debugging/Asura_Debug_Timers.h"
#include "Rendering/Asura_Module.h"
#include "Mesh/Asura_Mesh.h"
#include "Misc/list_tem.hpp"
#include "Streaming/Tools_Streaming_System.h"

// Use this define to output info on the module-module adjacencies,
// so we can check different algorithms give the same results.
//#define TOOLS_LOG_ADJACENCY_INFO

#ifdef TOOLS_LOG_ADJACENCY_INFO
#include "Debugging/Asura_Logfile.h"
#define TOOLS_ADJACENCY_LOGFILE "logfiles/adjacency.txt"
#endif

// KJFL - 21 February 2006 - I've removed the "Computing adjacencies for module x" messages, since 
// all it was doing was spamming the Tools_Timed_Message_System - the user wouldn't see the messages
// until the adjacencies were all finished, at which point many hundreds of them would be displayed 
// simultaneously, which makes them pretty pointless. (You'd need to begin and end frames occasionally
// if you want the user to actually see them while the adjacencies are being calculated.)
//
//#include "Misc/Tools_Timed_Messages.h"

/* SSE seems to help, but not a lot */
#define TOOLS_ADJACENCY_SSE 1

/* Astonishingly, copying into aligned table slows things down a bit */
#undef TOOLS_ADJACENCY_SSE_COPY

/* Filtering both ways helps a lot, so don't disable it */
#undef TOOLS_ADJACENCY_THATNOFILTER

/* The value is what matters for this macro */
#define PG_PROFILE 0

#if PG_PROFILE
	#include "Debugging/Asura_Logfile.h"
	/* The value is what matters for these macros */
	#define PG_ADJACENCY_STATS 0
	#define PG_ADJACENCY_TICKS 1
#endif

#if PG_ADJACENCY_STATS || PG_ADJACENCY_TICKS
	#undef NDEBUG
#endif

/*
	Check which polygon of this module is adjacent to which polygon of
	another module. In order to avoid checking every polygon of this
	with every poligon of that, we only check those within the slightly
	fattened bounding box of the other.
*/

#if defined TOOLS_ADJACENCY_SSE
	#include <xmmintrin.h>

	static inline __m128 _mm_tools_loadu3_ps(register const float* const afV)
	{
		/* Klimovitski hints: scalar load and store better */
		register const __m128 afX = _mm_load_ss(&afV[0]);
		register const __m128 afY = _mm_load_ss(&afV[1]);
		register const __m128 afZ = _mm_load_ss(&afV[2]);

		return _mm_shuffle_ps(_mm_movelh_ps(afX,afY),afZ,_MM_SHUFFLE(3,0,2,0));
	}

	static inline bool _mm_tools_tween3_ps(register const __m128 afV,
		register const __m128 afL,register const __m128 afU)
	{
		register const __m128 aiMask = _mm_and_ps(
			_mm_cmple_ps(afL,afV),_mm_cmple_ps(afV,afU));

		return (_mm_movemask_ps(aiMask) & 0x07) == 0x07;
	}
#endif

#if !PG_ADJACENCY_STATS
	#define TOOLS_ADJACENCY_STATS_INCR(K)
	#define TOOLS_ADJACENCY_STATS_SET(K,V)
#else
	class Tools_PG_Stats
	{
	public:
		unsigned* m_auStat;

		Tools_PG_Stats(const char* const* const pszName,const int iCount)
			: m_pszName(pszName),m_iCount(iCount),m_auStat(new unsigned[iCount])
		{
			Asura_Assert(m_auStat != 0,"'new' failed: stats table");

			this->CountZero();
		}

		virtual ~Tools_PG_Stats()
		{
			delete[] m_auStat;
			m_auStat = 0;
			m_pszName = 0;
		}

		void CountZero()
		{
			for (int i = 0; i < m_iCount; i++)
				m_auStat[i] = 0;
		}

		void CountPrint()
		{
			for (int i = 0; i < m_iCount; i++)
			{
				Asura_OutputToDebugger_Retail(("%10d: %s\n",
					m_auStat[i],m_pszName[i]));
			}
		}

	protected:
		const char* const* m_pszName;
		const int m_iCount;
	};

	enum
	{
		TOOLS_ADJACENCY_STATS_CVA_CALLS,
		TOOLS_ADJACENCY_STATS_CPA_CALLS,
		TOOLS_ADJACENCY_STATS_CAA_CALLS,
		TOOLS_ADJACENCY_STATS_CAA_MODULES,

		TOOLS_ADJACENCY_STATS_CAWM_CALLS,
		 TOOLS_ADJACENCY_STATS_CAWM_NOINTERSECT,

		 TOOLS_ADJACENCY_STATS_CAWM_MYVERT,
		  TOOLS_ADJACENCY_STATS_CAWM_MYVERT_INBOX,
		   TOOLS_ADJACENCY_STATS_CAWM_OTHERVERT,
			TOOLS_ADJACENCY_STATS_CAWM_OTHERVERT_NEAR,

		 TOOLS_ADJACENCY_STATS_CAWM_VERT_NOSHARED,

		  TOOLS_ADJACENCY_STATS_CAWM_MYVERTPOLY,
		   TOOLS_ADJACENCY_STATS_CAWM_MYVERTPOLY_HASADJ,
			TOOLS_ADJACENCY_STATS_CAWM_MYVERTPOLY_OTHERPOLY,
			 TOOLS_ADJACENCY_STATS_CAWM_MYVERTPOLY_OTHERPOLYVERT,
			  TOOLS_ADJACENCY_STATS_CAWM_MYVERTPOLY_VERTCONTAINS,

		  TOOLS_ADJACENCY_STATS_CAWM_MYPOLY,
		   TOOLS_ADJACENCY_STATS_CAWM_MYPOLYVERT,
			TOOLS_ADJACENCY_STATS_CAWM_MYPOLYVERT_HASLIST,
			 TOOLS_ADJACENCY_STATS_CAWM_MYPOLYVERT_LISTSZ,

			  TOOLS_ADJACENCY_STATS_CAWM_OTHERPOLY,
			   TOOLS_ADJACENCY_STATS_CAWM_OTHERPOLY_VERT,
				TOOLS_ADJACENCY_STATS_CAWM_OTHERPOLY_VERTCOMMON,

		TOOLS_ADJACENCY_STATS_AL_CALLS,
		TOOLS_ADJACENCY_STATS_DL_CALLS,
		TOOLS_ADJACENCY_STATS_ILM_CALLS,

		TOOLS_ADJACENCY_STATS_COUNT
	};

	static const char* const g_aszStatsName[TOOLS_ADJACENCY_STATS_COUNT] =
	{
		"CalculateVertexAdjacencies calls",
		"CalculatePolygonAdjacencies calls",
		"CalculateAllAdjacencies calls",
		"CalculateAllAdjacencies modules",

		"CalculateAdjacenciesWithModule calls",
		" CAWM module AABBs don't overlap",

		" CAWM vertices in this module",
		"  CAWM vertices of this module in the other module's AABB",
		"	CAWM vertices in other module",
		"	 CAWM vertices in other module near one in this module",

		" CAWM modules with overlapping AABBs having no shared vertices",

		" CAWM vertices in this module, polygon checking",
		"  CAWM vertices in this module having an intra module adjacency list",
		"	CAWM polygons in other module when vertex has adjacency list",
		"	 CAWM vertices in other module when vertex has adjacency list",
		"	  CAWM vertex adjacency list contains other module's vertex",

		"  CAWM polygons in this module",
		"	CAWM vertices in polygons in this module",
		"	 CAWM polygon in this module has a vertex with an adjacency list",
		"	  CAWM vertex adjacency list size",

		"	   CAWM other module's polygons tested for adjacency",
		"		CAWM vertices in other module polygons tested for adjacencies",
		"		 CAWM common vertices in other module's polygons",

		"AddLink calls",
		"DeleteLink calls",
		"InvalidateLinkedModules calls"
	};

	static Tools_PG_Stats g_xStats(g_aszStatsName,TOOLS_ADJACENCY_STATS_COUNT);

	#define TOOLS_ADJACENCY_STATS_INCR(K) \
		((void) g_xStats.m_auStat[TOOLS_ADJACENCY_STATS_##K]++)
	#define TOOLS_ADJACENCY_STATS_SET(K,V) \
		((void) (g_xStats.m_auStat[TOOLS_ADJACENCY_STATS_##K] = (V)))
#endif

#if !(PG_ADJACENCY_TICKS && defined WIN32)
	#define TOOLS_ADJACENCY_TICKS_BEG(K)
	#define TOOLS_ADJACENCY_TICKS_END(K)
#else
	typedef unsigned __int64 Tools_Adjacency_Ticks;
	struct Tools_Adjacency_TSC { unsigned m_uL; unsigned m_uH; };

	#define TOOLS_ADJACENCY_TICKS_GET(K)		\
		do { \
			struct Tools_Adjacency_TSC *_p = \
				(struct Tools_Adjacency_TSC *) &((K)[0]); \
			__asm { cpuid } /* serializes the pipeline */ \
			__asm { rdtsc } __asm { mov ecx,_p } \
			__asm { mov dword ptr [ecx+0],eax } \
			__asm { mov dword ptr [ecx+4],edx }; \
		} while (0)

	#include <windows.h>

	class Tools_PG_Ticks
	{
	public:
		static const int s_iDepthMax = 60;

		Tools_Adjacency_Ticks* m_aluTicks;
		Tools_Adjacency_Ticks m_aluStack[s_iDepthMax];
		int m_iDepth;

		Tools_PG_Ticks(const char* const* const pszName,const int iTicks)
			: m_pszName(pszName),m_iCount(iTicks),
			  m_aluTicks(new Tools_Adjacency_Ticks[iTicks]), m_iDepth(0)
		{
			Asura_Assert(m_aluTicks != 0,"'new' failed: ticks table");

			this->TicksZero();
			m_iDepth = 0;

			if (s_luTicksPerMicro == 0)
			  Tools_PG_Ticks::TicksCalibrate();
		}

		virtual ~Tools_PG_Ticks()
		{
			delete[] m_aluTicks;
			m_aluTicks = 0;
			m_pszName = 0;
			m_iDepth = 0;
		}

		void TicksZero(void)
		{
			for (int i = 0; i < m_iCount; i++)
			{
				m_aluTicks[i] = 0;
			}
			m_iDepth = 0;
		}

		static void TicksCalibrate(void)
		{
			const int iCalibRuns = 4;
			const int iCalibMs = 32;

			Tools_Adjacency_Ticks luTicksTotal = 0;
			__int64 luClockTotal = 0;

			/* Hopefully get to the start of a 'Sleep' interval' */
			Sleep(1);

			for (int i = 0; i < iCalibRuns; i++)
			{
				Tools_Adjacency_Ticks luTicksBegin,luTicksEnd;
				FILETIME xClockBegin,xClockEnd;
				__int64 luClockElapsed;

				/*
					'GetSystemTimeAsFileTime' returns values in 1/64s
					increments, but in units of 100 nanoseconds that
					is 0.1 microseconds or 1/10000 milliseconds.
				*/
				GetSystemTimeAsFileTime(&xClockBegin);
				TOOLS_ADJACENCY_TICKS_GET(&luTicksBegin);
				Sleep(iCalibMs);
				TOOLS_ADJACENCY_TICKS_GET(&luTicksEnd);
				GetSystemTimeAsFileTime(&xClockEnd);

				luTicksTotal += luTicksEnd - luTicksBegin;
				luClockElapsed =
					((((__int64) xClockEnd.dwHighDateTime) << 32)
						+ ((__int64) xClockEnd.dwLowDateTime))
					- ((((__int64) xClockBegin.dwHighDateTime) << 32)
						+ ((__int64) xClockBegin.dwLowDateTime));
				luClockTotal += luClockElapsed;
			}

			s_luTicksPerMicro = luTicksTotal/(luClockTotal/10);
		}

		void TicksPrint(void)
		{
			Asura_OutputToDebugger_Retail(("Times in microsecs (%I64u %s)\n",
				s_luTicksPerMicro,"ticks per microsec"));

			for (int i = 0; i < m_iCount; i++)
			{
				Asura_OutputToDebugger_Retail(("%12I64u: %s\n",
					m_aluTicks[i]/s_luTicksPerMicro,m_pszName[i]));
			}
		}

	protected:
		const char* const* m_pszName;
		const int m_iCount;

		static __int64 s_luTicksPerMicro;

	};

	__int64 Tools_PG_Ticks::s_luTicksPerMicro = 0;

	enum
	{
		TOOLS_ADJACENCY_TICKS_CAA_INTRAVERT,
		TOOLS_ADJACENCY_TICKS_CAA_INTRAPOLY,
		TOOLS_ADJACENCY_TICKS_CAA_INTER,

		TOOLS_ADJACENCY_TICKS_CAWM_CALL,
		 TOOLS_ADJACENCY_TICKS_CAWM_VERTVERT,
		  TOOLS_ADJACENCY_TICKS_CAWM_OTHERINMY,
		  TOOLS_ADJACENCY_TICKS_CAWM_OTHERVERT,
		   TOOLS_ADJACENCY_TICKS_CAWM_OTHERVERT_NEAR,
		 TOOLS_ADJACENCY_TICKS_CAWM_VERTPOLY,
		 TOOLS_ADJACENCY_TICKS_CAWM_POLYPOLY,
		 TOOLS_ADJACENCY_TICKS_CAWM_MISC,
		 TOOLS_ADJACENCY_TICKS_CAWM_ADDLINK,
		 TOOLS_ADJACENCY_TICKS_CAWM_VV,
		 TOOLS_ADJACENCY_TICKS_CAWM_LIST,

		TOOLS_ADJACENCY_TICKS_COUNT
	};

	static const char* const g_aszTicksName[TOOLS_ADJACENCY_TICKS_COUNT] =
	{
		"CalculateAllAdjacencies intra-module vertices",
		"CalculateAllAdjacencies intra-module polygons",
		"CalculateAllAdjacencies inter-module",

		"CAWM call",
		" CAWM vertices in this module against vertices in other module",
		"     CAWM vertices in other module in this module's AABB",
		"     CAWM vertices in other module tested against vertex in this module",
		"	      CAWM vertices in other module added to this module adjacency list",
		" CAWM vertices in this module against polygons in other module",
		" CAWM polygons in this module against polygons in other module",
		" CAWM Misc",
		" CAWM Add Link",
		" CAWM VV",
		" CAWM List",
	};

	static Tools_PG_Ticks g_xTicks(g_aszTicksName,TOOLS_ADJACENCY_TICKS_COUNT);

	#define TOOLS_ADJACENCY_TICKS_BEG(K) \
		do { \
			Tools_Adjacency_Ticks _t; \
			TOOLS_ADJACENCY_TICKS_GET(&_t); \
			g_xTicks.m_aluStack[g_xTicks.m_iDepth++] = _t; \
		} while (0)

	#define TOOLS_ADJACENCY_TICKS_END(K) \
		do { \
			Tools_Adjacency_Ticks _t; \
			TOOLS_ADJACENCY_TICKS_GET(&_t); \
			g_xTicks.m_aluTicks[TOOLS_ADJACENCY_TICKS_##K] \
				+= _t - g_xTicks.m_aluStack[--g_xTicks.m_iDepth]; \
		} while (0)
#endif

////////////////////////////////////////////////////////////////////////////////////////////////////
/*-----------------------------**
** Tools_Adjacency_VertexMatch **
**-----------------------------*/

static const int g_iVERTEX_MATCH_MAX_VERTS = 65536;


int Tools_Adjacency_VertexMatch::s_iNumVerts = 0;

u_short* Tools_Adjacency_VertexMatch::s_pusNumMatches = 0;
u_short** Tools_Adjacency_VertexMatch::s_ppusMatchedVerts = 0;

u_short* Tools_Adjacency_VertexMatch::s_pusBuffer = 0;
int Tools_Adjacency_VertexMatch::s_iSpaceUsed = 0;
int Tools_Adjacency_VertexMatch::s_iBufferSize = 0;
int Tools_Adjacency_VertexMatch::s_iMostRecentVert = -1;



void Tools_Adjacency_VertexMatch::Initialise()
{
	s_iNumVerts = 0;
	s_pusNumMatches = new u_short[g_iVERTEX_MATCH_MAX_VERTS];
	s_ppusMatchedVerts = new u_short*[g_iVERTEX_MATCH_MAX_VERTS];

	s_iBufferSize = g_iVERTEX_MATCH_MAX_VERTS*2;
	s_iSpaceUsed = 0;
	s_pusBuffer = new u_short[s_iBufferSize];
}

void Tools_Adjacency_VertexMatch::Shutdown()
{
	delete [] s_pusNumMatches;
	s_pusNumMatches = 0;
	delete [] s_ppusMatchedVerts;
	s_ppusMatchedVerts = 0;
	delete [] s_pusBuffer;
	s_pusBuffer = 0;
}

void Tools_Adjacency_VertexMatch::StartVertMatch(int iNumVerts)
{
	Asura_Assert(s_pusBuffer,"Not initialised");
	Asura_Assert(!s_iNumVerts,"Already in use");
	Asura_Assert(s_iNumVerts <= g_iVERTEX_MATCH_MAX_VERTS,"Too many vertices");

	s_iSpaceUsed = 0;
	s_iMostRecentVert = -1;

	memset(s_pusNumMatches,0,sizeof(u_short)*iNumVerts);
}

void Tools_Adjacency_VertexMatch::EndVertMatch()
{
	s_iNumVerts = 0;
}

void Tools_Adjacency_VertexMatch::AddEntry(int iThisVert,int iThatVert)
{
	if(s_iSpaceUsed == s_iBufferSize)
	{
		Asura_Assert(0,"Ran out of working space for finding matching vertices");
		return;
	}

	//All matches for any given vertex need to be done in sequence.
	if(s_iMostRecentVert != iThisVert)
	{
		Asura_Assert(s_pusNumMatches[iThisVert] == 0,"Already finished adding matches to this vertex");

		//Moved onto a new vertex , so grab the current position in the buffer ,and start filling in values for it from there
		s_ppusMatchedVerts[iThisVert] = &s_pusBuffer[s_iSpaceUsed];
		s_iMostRecentVert = iThisVert;
	}

	//add as the next entry for this vert
	s_pusBuffer[s_iSpaceUsed++] = (u_short) iThatVert;
	s_pusNumMatches[iThisVert]++;
}

bool Tools_Adjacency_VertexMatch::IsMatched(int iThisVert,int iThatVert)
{
	for(int i=0;i<s_pusNumMatches[iThisVert];i++)
	{
		if(iThatVert == s_ppusMatchedVerts[iThisVert][i]) return true;
	}
	return false;
}







////////////////////////////////////////////////////////////////////////////////////////////////////
/*-------------------------**
** Tools_Adjacency_Handler **
**-------------------------*/
Tools_Adjacency_Handler::Tools_Adjacency_Handler()
{
	m_bInitialised = false;
	#ifdef ASURA_USE_STREAMING
	Initialise();
	#endif
}

Tools_Adjacency_Handler::~Tools_Adjacency_Handler()
{
	#ifdef ASURA_USE_STREAMING
	Shutdown();
	#endif
}


void Tools_Adjacency_Handler::Initialise()
{
	Asura_Assert(!m_bInitialised,"Already been initialised");

	m_iModulesCount = 0;
	m_paxModules = 0;
	m_paxCollModules = 0;

	#ifndef ASURA_USE_STREAMING
	m_uZoneHash = 0;
	#endif

	m_bInitialised = true;
}

void Tools_Adjacency_Handler::Shutdown()
{
	Asura_Assert(m_bInitialised,"Not yet initialised");

	m_bInitialised = false;
	m_iModulesCount = 0;
	delete[] m_paxModules;
	m_paxModules = 0;
	delete[] m_paxCollModules;
	m_paxCollModules = 0;
}

void Tools_Adjacency_Handler::Invalidate()
{
	if (m_iModulesCount > 0)
	{
		if (m_iModulesCount != Asura_Module_System::GetNumberOfModules())
		{
			m_iModulesCount = 0;
			delete[] m_paxModules;
			m_paxModules = 0;
			delete[] m_paxCollModules;
			m_paxCollModules = 0;
		}
		else
		{
			for (int i = 0; i < m_iModulesCount; i++)
			{
				m_paxModules[i].Invalidate();
				m_paxCollModules[i].Invalidate();
			}
		}
	}
}

void Tools_Adjacency_Handler::InvalidateCollision()
{
	if (m_iModulesCount > 0)
	{
		if (m_iModulesCount != Asura_Module_System::GetNumberOfModules())
		{
			m_iModulesCount = 0;
			delete[] m_paxModules;
			m_paxModules = 0;
			delete[] m_paxCollModules;
			m_paxCollModules = 0;
		}
		else
		{
			for (int i = 0; i < m_iModulesCount; i++)
			{
				m_paxCollModules[i].Invalidate();
			}
		}
	}
}

void Tools_Adjacency_Handler::InvalidateModule(const int iModuleId)
{
	if (m_paxModules != 0)
	{
		Tools_Module_Adjacency& m = m_paxModules[iModuleId];

		m.InvalidateLinkedModules();
		m.Invalidate();
		m.Initialise(m_uZoneHash,iModuleId,false);//reinitialise in case a new mesh is bieng used

		Tools_Module_Adjacency& xCollModule = m_paxCollModules[iModuleId];

		xCollModule.InvalidateLinkedModules();
		xCollModule.Invalidate();
		xCollModule.Initialise(m_uZoneHash,iModuleId,true);


	}
}

void Tools_Adjacency_Handler::InvalidateCollisionModule(const int iModuleId)
{
	if (m_paxCollModules != 0)
	{
		Tools_Module_Adjacency& xCollModule = m_paxCollModules[iModuleId];

		xCollModule.InvalidateLinkedModules();
		xCollModule.Invalidate();
		xCollModule.Initialise(m_uZoneHash,iModuleId,true);

	}
}


const Tools_Polygon_Adjacency*
Tools_Adjacency_Handler::GetPolygonAdjacencies(const int iModuleId,const int iPolyId)
{
	if (m_paxModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleId >= 0 && iModuleId < m_iModulesCount,"");

	return m_paxModules[iModuleId].GetPolygonAdjacencies(iPolyId);

}

const Tools_Polygon_Adjacency*
Tools_Adjacency_Handler::GetVertexAdjacencies(const int iModuleId,const int iVertexId)
{
	if (m_paxModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleId>=0 && iModuleId<m_iModulesCount,"");

	return m_paxModules[iModuleId].GetVertexAdjacencies(iVertexId);
}

int Tools_Adjacency_Handler::GetNumLooseVertices(const int iModuleId)
{
	if (m_paxModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleId>=0 && iModuleId<m_iModulesCount,"");

	return m_paxModules[iModuleId].GetNumLooseVertices();
}

int Tools_Adjacency_Handler::GetLooseVertex(int iModuleId,int iIndex)
{
	if (m_paxModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleId>=0 && iModuleId<m_iModulesCount,"");

	return m_paxModules[iModuleId].GetLooseVertex(iIndex);
}


const Tools_Polygon_Adjacency*
Tools_Adjacency_Handler::GetCollPolygonAdjacencies(const int iModuleId,const int iPolyId)
{
	if (m_paxCollModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleId >= 0 && iModuleId < m_iModulesCount,"");

	return m_paxCollModules[iModuleId].GetPolygonAdjacencies(iPolyId);

}

const Tools_Polygon_Adjacency*
Tools_Adjacency_Handler::GetCollVertexAdjacencies(const int iModuleId,const int iVertexId)
{
	if (m_paxCollModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleId>=0 && iModuleId<m_iModulesCount,"");

	return m_paxCollModules[iModuleId].GetVertexAdjacencies(iVertexId);
}



void Tools_Adjacency_Handler::AddLink(int iModuleIndex,Asura_Hash_ID uLinkZoneHash,int iLinkModuleIndex,bool bCollision)
{
	if (m_paxModules == 0 || m_paxCollModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleIndex>=0 && iModuleIndex<m_iModulesCount,"");

	if(bCollision)
		m_paxCollModules[iModuleIndex].AddLink(uLinkZoneHash,iLinkModuleIndex);
	else
		m_paxModules[iModuleIndex].AddLink(uLinkZoneHash,iLinkModuleIndex);

}

void Tools_Adjacency_Handler::DeleteLink(int iModuleIndex,Asura_Hash_ID uLinkZoneHash,int iLinkModuleIndex,bool bCollision)
{
	if (m_paxModules == 0 || m_paxCollModules == 0)
	{
		InitialiseModuleArray();
	}

	Asura_Assert(iModuleIndex>=0 && iModuleIndex<m_iModulesCount,"");

	if(bCollision)
		m_paxCollModules[iModuleIndex].DeleteLink(uLinkZoneHash,iLinkModuleIndex);
	else
		m_paxModules[iModuleIndex].DeleteLink(uLinkZoneHash,iLinkModuleIndex);

}


void Tools_Adjacency_Handler::InitialiseModuleArray()
{
	if (m_paxModules == 0)
	{
		#ifdef ASURA_USE_STREAMING
		Asura_Module_Handler* pxModHandler = Asura_Module_System::GetHandler(m_uZoneHash);
		#else
		Asura_Module_Handler* pxModHandler = &Asura_Module_System::GetCurrentHandler();
		#endif

		m_iModulesCount = pxModHandler->GetNumberOfModules();
		m_paxModules = new Tools_Module_Adjacency[m_iModulesCount];
		m_paxCollModules = new Tools_Module_Adjacency[m_iModulesCount];

		Asura_Assert(m_paxModules != 0,"'new' failed: adjacency table");

		for (int i = 0; i < m_iModulesCount; i++)
		{
			m_paxModules[i].Initialise(m_uZoneHash,i,false);
			m_paxCollModules[i].Initialise(m_uZoneHash,i,true);
		}
	}
}



////////////////////////////////////////////////////////////////////////////////////////////////////
/*-----------------**
** Tools_Adjacency **
**-----------------*/
/*
	Tools_Adjacency class. It extends intra-mesh adjacency work, as done
	in Tools_MeshAdjacency, to a collection of modules.
*/

#if defined(ASURA_USE_STREAMING)
Asura_TemplateHashTree<Tools_Adjacency_Handler>	Tools_Adjacency::s_xHandlerTree;
Tools_Adjacency_Handler*						Tools_Adjacency::s_pxCurrentHandler	= NULL;
#else
Tools_Adjacency_Handler	Tools_Adjacency::s_xHandler;
#endif	// defined(ASURA_USE_STREAMING)

bool Tools_Adjacency::s_bInitialised = false;

void Tools_Adjacency::Initialise()
{
	Tools_Adjacency_VertexMatch::Initialise();

	#ifndef ASURA_USE_STREAMING
	s_xHandler.Initialise();
	#endif
	s_bInitialised = true;
}

void Tools_Adjacency::Shutdown()
{
	Tools_Adjacency_VertexMatch::Shutdown();

	#if PG_ADJACENCY_STATS
	g_xStats.CountPrint();
	#endif
	#if PG_ADJACENCY_TICKS
	g_xTicks.TicksPrint();
	#endif

	#if defined(ASURA_USE_STREAMING)
	// Reset the entire handler tree...
	s_xHandlerTree.Reset();

	// Remove the current handler...
	s_pxCurrentHandler	= NULL;
	#else
	// Reset the current instance...
	s_xHandler.Shutdown();
	#endif	// defined(ASURA_USE_STREAMING)
	
	s_bInitialised = false;
}

#if defined(ASURA_USE_STREAMING)
Tools_Adjacency_Handler* Tools_Adjacency::CreateHandler (const Asura_Hash_ID uHash)
{
	Tools_Adjacency_Handler*	pxHandler	= s_xHandlerTree.GetDataByHash(uHash);

	// Do we already have this handler?
	if(pxHandler == NULL)
	{
		// No - create one...
		pxHandler	= s_xHandlerTree.AddNode(uHash);
		pxHandler->m_uZoneHash = uHash;
	}
	else
	{
		// Yes - this shouldn't happen...
		Asura_Assert(false, "Already have an adjacency handler with this hash-ID.");
	}

	// Return the handler...
	return(pxHandler);
}

bool Tools_Adjacency::DestroyHandler (const Asura_Hash_ID uHash)
{
	// Is this the current handler?
	if(s_pxCurrentHandler == s_xHandlerTree.GetDataByHash(uHash))
	{
		s_pxCurrentHandler	= NULL;
	}

	// Call the delete function...
	return(s_xHandlerTree.DeleteNodeByHash(uHash));
}

void Tools_Adjacency::SetCurrentHandler(Tools_Adjacency_Handler* pxHandler)
{
	if(pxHandler != s_pxCurrentHandler)
	{
		s_pxCurrentHandler = pxHandler;
	}
}

#endif	// defined(ASURA_USE_STREAMING)

void Tools_Adjacency::Invalidate()
{
	#ifdef ASURA_USE_STREAMING
	s_xHandlerTree.Traverse(InvalidateCallback);
	#else
	s_xHandler.Invalidate();
	#endif
}

void Tools_Adjacency::InvalidateAllCollisionModules()
{
	#ifdef ASURA_USE_STREAMING
	s_xHandlerTree.Traverse(InvalidateCollisionCallback);
	#else
	s_xHandler.InvalidateCollision();
	#endif
}

////////////////////////////////////////////////////////////////////////////////////////////////
/*------------------------**
** Tools_Module_Adjacency **
**------------------------*/

/*
	The Tools_Module_Adjacency class. It inherits from Tools_MeshAdjacency,
	and here we override some of its methods to use the mesh inside a module.
*/

Tools_Module_Adjacency::Tools_Module_Adjacency()
{
	m_iModuleId = -1;

	m_pxLinkedModules = 0;
	m_iLinkedModulesCount = 0;
	m_iLinkedModulesCapacity = 0;

	m_bCollisionMesh = false;
}

Tools_Module_Adjacency::~Tools_Module_Adjacency()
{
	delete[] m_pxLinkedModules;
	m_pxLinkedModules = 0;
	m_iLinkedModulesCount = 0;
	m_iLinkedModulesCapacity = 0;
}

void Tools_Module_Adjacency::Initialise(Asura_Hash_ID uZoneHash,const int iModuleId,bool bCollisionMesh)
{
	m_uZoneHash = uZoneHash;
	m_iModuleId = iModuleId;
	m_bCollisionMesh = bCollisionMesh;

	#ifdef ASURA_USE_STREAMING
	Asura_Module_Handler* pxModHandler = Asura_Module_System::GetHandler(m_uZoneHash);
	#else
	Asura_Module_Handler* pxModHandler = &Asura_Module_System::GetCurrentHandler();
	#endif
	if(m_bCollisionMesh)
	{
		m_xMesh.Initialise_CollMesh(pxModHandler, iModuleId);
	}
	else
	{
		m_xMesh.Initialise(pxModHandler->GetMeshForModule(iModuleId));
	}

	Asura_Assert(m_xMesh.IsValid(),"");
}

void Tools_Module_Adjacency::CalculateVertexAdjacencies()
{
	TOOLS_ADJACENCY_STATS_INCR(CVA_CALLS);

	this->CalculateAllAdjacencies();
}

void Tools_Module_Adjacency::CalculatePolygonAdjacencies()
{
	TOOLS_ADJACENCY_STATS_INCR(CPA_CALLS);

	this->CalculateAllAdjacencies();
}

void Tools_Module_Adjacency::CalculateAllAdjacencies()
{
	//ASURA_CPU_PROFILE_SCOPED_TIMER( "Tools_Module_Adjacency::CalculateAllAdjacencies - per module" );

	#ifdef ASURA_MAIN //don't want to do this in max plugins etc. RAR 16/02/2006
	
	// KJFL - 21 February 2006 - I've removed the "Computing adjacencies for module x" messages, since 
	// all it was doing was spamming the Tools_Timed_Message_System - the user wouldn't see the messages
	// until the adjacencies were all finished, at which point many hundreds of them would be displayed 
	// simultaneously, which makes them pretty pointless. (You'd need to begin and end frames occasionally
	// if you want the user to actually see them while the adjacencies are being calculated.)
	//
	//Tools_Timed_Message_System::AddMessage(
	//	Tools_Timed_Message_System::COLOUR_INFO,
	//	"Computing adjacencies for module %d...",m_iModuleId
	//);
	#endif

	TOOLS_ADJACENCY_STATS_INCR(CAA_CALLS);

	/*
		First compute the intra-module adjacencies
		for this module.
	*/
	{
		//ASURA_CPU_PROFILE_SCOPED_TIMER( "Tools_Module_Adjacency::CalculateAllAdjacencies - internal verts" );

	
		TOOLS_ADJACENCY_TICKS_BEG(CAA_INTRAVERT);
		this->CalculateInternalVertexAdjacencies();
		TOOLS_ADJACENCY_TICKS_END(CAA_INTRAVERT);
	}
	{
		//ASURA_CPU_PROFILE_SCOPED_TIMER( "Tools_Module_Adjacency::CalculateAllAdjacencies - internal polys" );

		TOOLS_ADJACENCY_TICKS_BEG(CAA_INTRAPOLY);
		this->CalculateInternalPolygonAdjacencies();
		TOOLS_ADJACENCY_TICKS_END(CAA_INTRAPOLY);
	}
	/*
		Next check every other module for adjacencies with this module.
	*/
	for(Tools_Streaming_Iterator xIt(false);!xIt.Done();xIt.Next())
	{
		//ASURA_CPU_PROFILE_SCOPED_TIMER( "Tools_Module_Adjacency::CalculateAllAdjacencies - external" );

		const Asura_Hash_ID uZoneHash = xIt.GetHash();

		Asura_Module_Handler* pxModuleHandler;
		#ifdef ASURA_USE_STREAMING
		pxModuleHandler = Asura_Module_System::GetHandler(uZoneHash);
		#else
		pxModuleHandler = &Asura_Module_System::GetCurrentHandler();
		#endif
		Asura_Assert(pxModuleHandler,"");

		const int modules = pxModuleHandler->GetNumberOfModules();


		TOOLS_ADJACENCY_STATS_SET(CAA_MODULES,modules);

		TOOLS_ADJACENCY_TICKS_BEG(CAA_INTER);
		for (int i = 0; i < modules; i++)
		{
			if (i != m_iModuleId || uZoneHash != m_uZoneHash)
			{
				this->CalculateAdjacenciesWithModule(pxModuleHandler,uZoneHash,i);
			}
		}
		TOOLS_ADJACENCY_TICKS_END(CAA_INTER);
	}
}



#if !defined( TOOLS_USE_OLD_ADJACENCY_CODE )
//////////////////////////////////////////////////////////////////////////
// New optimised O(N+M) version of module-module adjacency
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////

// TODO - split vertex finder class into own files?
class Tools_EquivalentVertexFinder_HashEntry
{
	public:

		void Set( Asura_Hash_ID uHashID, const Asura_Vector_3& xPosition, u_int uVertex, Tools_EquivalentVertexFinder_HashEntry* pxNext )
		{
			m_uHashID = uHashID;
			m_uVertex = uVertex;
			m_xPosition = xPosition;
			m_pxNextEntry = pxNext;
		}

		Asura_Hash_ID							m_uHashID;
		Asura_Vector_3							m_xPosition;

		u_int									m_uVertex;

		Tools_EquivalentVertexFinder_HashEntry*	m_pxNextEntry;
};

class Tools_EquivalentVertexFinder_Match
{
	public:

		void Set( u_int uVertex, Tools_EquivalentVertexFinder_Match* pxNext ) 
		{
			m_uVertex = uVertex;
			m_pxNext = pxNext;
		}

		u_int									m_uVertex;
		Tools_EquivalentVertexFinder_Match*		m_pxNext;
};

// TODO: move this include to top if we're not moving the finder class to another file
#include "Core/Asura_Mempool.h"

class Tools_EquivalentVertexFinder
{
	public:
		Tools_EquivalentVertexFinder( u_int uNumberOfVertsInSet1, u_int uNumberOfVertsInSet2 )
		{
			// TODO: refine hash table size?
			m_uSizeOfHashTable = 1001;

			m_ppxHashTable = new Tools_EquivalentVertexFinder_HashEntry* [ m_uSizeOfHashTable ];
			for ( u_int u=0; u<m_uSizeOfHashTable; ++u )
			{
				m_ppxHashTable[u] = 0;
			}

			m_pxHashEntries = new Tools_EquivalentVertexFinder_HashEntry[ uNumberOfVertsInSet1 ];
			m_uMaxNumberOfEntries = uNumberOfVertsInSet1;
			m_uFreeEntry = 0;

			m_pxMatchesMempool = new Asura_ResizingMempool( 32, sizeof( Tools_EquivalentVertexFinder_Match), __FILE__, __LINE__ );
            m_ppxMatches = new Tools_EquivalentVertexFinder_Match*[ uNumberOfVertsInSet2 ];
			for ( u_int u=0; u<uNumberOfVertsInSet2; ++u )
			{
				m_ppxMatches[u] = 0;
			}

			m_uNumberOfVertexMatches = 0;
		}

		~Tools_EquivalentVertexFinder()
		{
			delete [] m_ppxHashTable;
			delete [] m_pxHashEntries;

			delete [] m_ppxMatches;
			delete m_pxMatchesMempool;
		}

		void AddVertexFromSet1( const Asura_Vector_3& xPosition, u_int uVertex )
		{
			const float fSpatialHashScale = 100.0f;
	
			const int iX = Asura_Maths::FloatToInt(xPosition.x * fSpatialHashScale);
			const int iY = Asura_Maths::FloatToInt(xPosition.y * fSpatialHashScale);
			const int iZ = Asura_Maths::FloatToInt(xPosition.z * fSpatialHashScale);

			Asura_Hash_ID uHashID = GetHash( iX, iY, iZ );
			AddEntry( uHashID, xPosition, uVertex );
		}

		void AddVertexFromSet2( const Asura_Vector_3& xPosition, u_int uVertex )
		{
			const float fCellSize = 0.001f ; // tolerance for matching vertices
			const float fSpatialHashScale = 100.0f;
	
			// find ranges of bounding box
			const int iMinX = Asura_Maths::FloatToInt( (xPosition.x - fCellSize) * fSpatialHashScale);
			const int iMinY = Asura_Maths::FloatToInt( (xPosition.y - fCellSize) * fSpatialHashScale);
			const int iMinZ = Asura_Maths::FloatToInt( (xPosition.z - fCellSize) * fSpatialHashScale);

			const int iMaxX = Asura_Maths::FloatToInt( (xPosition.x + fCellSize) * fSpatialHashScale);
			const int iMaxY = Asura_Maths::FloatToInt( (xPosition.y + fCellSize) * fSpatialHashScale);
			const int iMaxZ = Asura_Maths::FloatToInt( (xPosition.z + fCellSize) * fSpatialHashScale);

			for (int iX = iMinX; iX <= iMaxX; iX++)
			{
				for (int iY = iMinY; iY <= iMaxY; iY++)
				{
					for (int iZ = iMinZ; iZ <= iMaxZ; iZ++)
					{
						Asura_Hash_ID uHashID = GetHash( iX, iY, iZ );

						// TODO - actually... if with (hash % number of table entries)
						// you end up with the same number as a previous hash, skip it.
						// This will skip duplicate records.
						// UPDATE: now checking hashID as well, so shouldn't be a problem.
						ReportMatches( uHashID, xPosition, uVertex );
					}
				}
			}
		}

		u_int GetNumberOfVertexMatches( void ) const
		{
			return m_uNumberOfVertexMatches;
		}

		const Tools_EquivalentVertexFinder_Match* GetFirstMatch( u_int uSet2Vertex ) const 
		{
			return m_ppxMatches[ uSet2Vertex ];
		}

	private:

		Asura_Hash_ID GetHash( int iX, int iY, int iZ ) const
		{
			return 7* iX + 503 * iY + 24847 * iZ;
		}

		void AddEntry( u_int uHashID, const Asura_Vector_3& xPosition, u_int uVertex )
		{
			Tools_EquivalentVertexFinder_HashEntry* pxHashEntry = m_ppxHashTable[ uHashID % m_uSizeOfHashTable ];

			Tools_EquivalentVertexFinder_HashEntry* pxNewEntry = &(m_pxHashEntries[ m_uFreeEntry++ ]);

			pxNewEntry->Set( uHashID, xPosition, uVertex, pxHashEntry );

			m_ppxHashTable[ uHashID % m_uSizeOfHashTable ] = pxNewEntry;
		}

		void ReportMatches( u_int uHashID, const Asura_Vector_3& xPosition, u_int uVertex )
		{
			const Tools_EquivalentVertexFinder_HashEntry* pxHashEntry = m_ppxHashTable[ uHashID % m_uSizeOfHashTable ];

			while ( pxHashEntry )
			{
				if ( pxHashEntry->m_uHashID == uHashID )
				{
					const Asura_Vector_3 xVertexDist = xPosition - pxHashEntry->m_xPosition;
					
					if ( Tools_Adjacency::IsDistanceWithinTolerance(xVertexDist) )
					{
						AddMatch( pxHashEntry->m_uVertex, uVertex );
					}
				}

				pxHashEntry = pxHashEntry->m_pxNextEntry;
			}
		}

		void AddMatch( u_int uVertex1, u_int uVertex2 )
		{
			Tools_EquivalentVertexFinder_Match* pxNew = static_cast<Tools_EquivalentVertexFinder_Match*>(m_pxMatchesMempool->Allocate());
			
			pxNew->Set( uVertex1, m_ppxMatches[ uVertex2 ] );

			m_ppxMatches[ uVertex2 ] = pxNew;

			++m_uNumberOfVertexMatches;
		}

		u_int										m_uSizeOfHashTable;
		u_int										m_uMaxNumberOfEntries;
		u_int										m_uFreeEntry;
	
		Tools_EquivalentVertexFinder_HashEntry**	m_ppxHashTable;
		Tools_EquivalentVertexFinder_HashEntry*		m_pxHashEntries;

		Asura_ResizingMempool*						m_pxMatchesMempool;
		Tools_EquivalentVertexFinder_Match**		m_ppxMatches;
		u_int										m_uNumberOfVertexMatches;
};

void Tools_Module_Adjacency::CalculateAdjacenciesWithModule( Asura_Module_Handler* pxOtherModuleHandler, const Asura_Hash_ID uOtherZoneHash, const int iOtherId )
{
	const int iMyId = m_iModuleId;

	Tools_RenderOrCollMesh& xMyMesh = m_xMesh;
	Tools_RenderOrCollMesh xOtherMesh;

	if(xMyMesh.IsCollMesh())
	{
		xOtherMesh.Initialise_CollMesh(pxOtherModuleHandler, iOtherId);
	}
	else
	{
		xOtherMesh.Initialise(pxOtherModuleHandler->GetMeshForModule(iOtherId));
	}

	/*
		Make *copies* of the bounding boxes and fatten them slightly.
	*/
	Asura_Bounding_Box xMyBox = xMyMesh.GetBoundingBox();
	Asura_Bounding_Box xOtherBox = xOtherMesh.GetBoundingBox();

	const float fFat = 0.01f;
	xMyBox.Grow( fFat );
	xOtherBox.Grow( fFat );

	/*
		Grab the origins of the meshes, and compute the offset
		of the other relative to this. Vertex positions in a
		mesh are relative to the origin in the mesh.
	*/

	Asura_Vector_3 xMyPosition;
	Asura_Vector_3 xOtherPosition;

	Asura_Module_System::GetPositionOfModule(iMyId,xMyPosition);
	pxOtherModuleHandler->GetPositionOfModule(iOtherId,xOtherPosition);

	const Asura_Vector_3 xOffOtherFromMy = xOtherPosition-xMyPosition;

	/*
		If the (fattened) bounding boxes do not intersect at all, no
		adjacencies are possible, so give up.
	*/
	if (!xMyBox.Intersects(xOtherBox,xOffOtherFromMy))
	{
		return;
	}

	Tools_EquivalentVertexFinder xFinder( xMyMesh.GetNumberOfVertices(), xOtherMesh.GetNumberOfVertices() ) ;

	{
	//	ASURA_CPU_PROFILE_SCOPED_TIMER( "Tools_Module_Adjacency::CalculateAllAdjacencies - add verts" );

		Asura_Bounding_Box xOtherBB = xOtherBox;
		xOtherBB.Displace( xOffOtherFromMy );

		const int iMyVertexCount	= xMyMesh.GetNumberOfVertices();
		for (int v = 0; v < iMyVertexCount; v++)
		{
			const Asura_Vector_3& xPosition = xMyMesh.GetVertex( v );

			if ( xOtherBB.Contains( xPosition ) )
			{
				xFinder.AddVertexFromSet1( xPosition, v );
			}
		}
	}
	{
	//	ASURA_CPU_PROFILE_SCOPED_TIMER( "Tools_Module_Adjacency::CalculateAllAdjacencies - test verts" );

		for (int v = 0; v < xOtherMesh.GetNumberOfVertices(); v++)
		{
			const Asura_Vector_3 xPosition = xOtherMesh.GetVertex( v ) + xOffOtherFromMy;

			if ( xMyBox.Contains( xPosition ) )
			{
				xFinder.AddVertexFromSet2( xPosition, v );
			}
		}
	}
	if ( !xFinder.GetNumberOfVertexMatches() )
	{
		return;
	}

	u_int uAdjacenciesFound = 0;

	// KJFL - 17 October 2007 - in theory I should be able to get rid of the outer loop
	// if I'm allowed to access the internal vertex adjacencies of the other module, though
	// of course they may not exist at this point. Currently not seeming to be a bottleneck.
	int iNumPolys = xOtherMesh.GetNumberOfPolygons();
	for(int i=0;i<iNumPolys;i++)
	{
		int iNumPolyVerts = xOtherMesh.GetNumberOfVertsInPoly(i);

		for(int j=0;j<iNumPolyVerts;j++)
		{
			//add this polygon to the list for this vertex
			u_int uVertexID = xOtherMesh.GetVertexIndex( i, j );

			const Tools_EquivalentVertexFinder_Match* pxMatch = xFinder.GetFirstMatch( uVertexID );

			while (pxMatch)
			{
				const Tools_Adjacent_Polygon* pxAdj = Vertices[ pxMatch->m_uVertex ].GetFirstAdjacency();

				while ( pxAdj )
				{
					// is this one of our own polys?
#ifdef ASURA_USE_STREAMING
					if ( pxAdj->m_uZoneHash == m_uZoneHash )
#endif
					{
						if ( pxAdj->GetModuleIndex() == m_iModuleId ) 
						{
							// then tell our poly about the other module's one
							this->Polygons[ pxAdj->GetPolygonIndex() ].AddAdjacency( uOtherZoneHash, iOtherId, i );
							++uAdjacenciesFound;
						}
					}

					pxAdj = pxAdj->GetNext();
				}

				Vertices[ pxMatch->m_uVertex ].AddAdjacency( uOtherZoneHash, iOtherId, i );		
				++uAdjacenciesFound;
				
				pxMatch = pxMatch->m_pxNext;
			}
		}
	}


	if (uAdjacenciesFound > 0)
	{
		this->AddLink(uOtherZoneHash,iOtherId);
		#ifdef ASURA_USE_STREAMING
		Tools_Adjacency_Handler* pxOtherAdjHandler = Tools_Adjacency::GetHandler(uOtherZoneHash);
		#else
		Tools_Adjacency_Handler* pxOtherAdjHandler = &Tools_Adjacency::GetCurrentHandler();
		#endif
		pxOtherAdjHandler->AddLink(iOtherId,m_uZoneHash,iMyId,m_bCollisionMesh);
	}


#ifdef TOOLS_LOG_ADJACENCY_INFO
	Asura_Logfile_Retail(( TOOLS_ADJACENCY_LOGFILE, "Mods: %d:%d\t\tVerts:%d\t\tPolys:%d\n", iMyId, iOtherId, xFinder.GetNumberOfVertexMatches(), uAdjacenciesFound ));
#endif
}

#else // old n*m code


/*
Check each vertex in this mesh [which is in the fattened bounding
box of the other mesh] against every vertex in that mesh [which is
in the fattened bounding box of that mesh], and add those of the
latter that are ''nearby'' to the list of ''equivalent'' vertices.

In order for the filtering the vertices in that mesh to be cheaper,
we must prefilter the list of such vertices, and thus assume that
mesh is rather big.

This is where most of the time goes...
*/
static void Tools_Module_Adjacencies_VV(
										int* const piVertexListCount,
										const Tools_RenderOrCollMesh& xThisMesh,
										const Asura_Bounding_Box& xThisBox,
										const Tools_RenderOrCollMesh& xThatMesh,
										const Asura_Bounding_Box& xThatBox,
										const Asura_Vector_3& xOffThisFromThat
										)
{
	TOOLS_ADJACENCY_TICKS_BEG(CAWM_VERTVERT);

	const int iThisVertexCount	= xThisMesh.GetNumberOfVertices();
	const int iThatVertexCount	= xThatMesh.GetNumberOfVertices();

#if defined TOOLS_ADJACENCY_SSE
	/* The bounding box extrema of this module */
	register const __m128 afThisBoxMin
		= _mm_set_ps(0.0f,xThisBox.MinZ,xThisBox.MinY,xThisBox.MinX);
	register const __m128 afThisBoxMax
		= _mm_set_ps(0.0f,xThisBox.MaxZ,xThisBox.MaxY,xThisBox.MaxX);

	/* The bounding box extrema of the other module */
	register const __m128 afThatBoxMin
		= _mm_set_ps(0.0f,xThatBox.MinZ,xThatBox.MinY,xThatBox.MinX);
	register const __m128 afThatBoxMax
		= _mm_set_ps(0.0f,xThatBox.MaxZ,xThatBox.MaxY,xThatBox.MaxX);

	/* The distance between origins of that module from this module */
	register const __m128 afOffThisFromThat
		= _mm_tools_loadu3_ps(&xOffThisFromThat.x);

	register const __m128 afPlusFuzz = _mm_set_ps1(0.001f);
	register const __m128 afMinusFuzz = _mm_set_ps1(-0.001f);
#endif

	TOOLS_ADJACENCY_TICKS_BEG(CAWM_OTHERINMY);
	/*
	The arrays of vertex positions and numbers in the other module
	that are within the bounding box of this module. Hopefully
	very few. The maximum size is the same as the total number
	of vertex positions.
	*/
	int iThatInThisCount = 0;
	const int iThatInThisCapacity = iThatVertexCount;
	int* aiNumThatInThis = new int[iThatInThisCapacity];

	Asura_Assert(aiNumThatInThis != 0,"'new' failed");

#if defined TOOLS_ADJACENCY_SSE
#if defined TOOLS_ADJACENCY_SSE_COPY
	__m128* const aafPosThatInThis = reinterpret_cast<__m128*>
		(_mm_malloc(iThatInThisCapacity*sizeof (__m128),
		sizeof (__m128)));

	Asura_Assert(aafPosThatInThis != 0,"'_mm_malloc' failed");
#else
	const Asura_Vector_3** apxPosThatInThis
		= new const Asura_Vector_3* [iThatInThisCapacity];
#endif
	register const __m128 afThisBoxMinRelThat
		= _mm_add_ps(afThisBoxMin,afOffThisFromThat);
	register const __m128 afThisBoxMaxRelThat
		= _mm_add_ps(afThisBoxMax,afOffThisFromThat);

	for (int w = 0; w < iThatVertexCount; w++)
	{
		register const Asura_Vector_3* const pxThatVertexPos
			= &xThatMesh.GetVertex(w);
		register const __m128 afThatVertexPos
			= _mm_tools_loadu3_ps(&pxThatVertexPos->x);
#if defined TOOLS_ADJACENCY_THATNOFILTER
		register const bool bThatPosInThisBox = true;
#else
		register const bool bThatPosInThisBox
			= _mm_tools_tween3_ps(afThatVertexPos,
			afThisBoxMinRelThat,afThisBoxMaxRelThat);
#endif

		if (bThatPosInThisBox)
		{
			aiNumThatInThis[iThatInThisCount] = w;
#if TOOLS_ADJACENCY_SSE_COPY
			aafPosThatInThis[iThatInThisCount++] = afThatVertexPos;
#else
			apxPosThatInThis[iThatInThisCount++] = pxThatVertexPos;
#endif
		}
	}
#else
	const Asura_Vector_3** apxPosThatInThis
		= new const Asura_Vector_3* [iThatInThisCapacity];

	Asura_Assert(apxPosThatInThis != 0,"'new' failed");

	register Asura_Bounding_Box xThisBoxRelThat = xThisBox;
	xThisBoxRelThat.Displace(xOffThisFromThat);

	for (int w = 0; w < iThatVertexCount; w++)
	{
		register const Asura_Vector_3* const pxThatVertexPos
			= &xThatMesh.GetVertex(w);
#if defined TOOLS_ADJACENCY_THATNOFILTER
		register const bool bThatPosInThisBox = true;
#else
		register const bool bThatPosInThisBox
			= xThisBoxRelThat.Contains(*pxThatVertexPos);
#endif

		if (bThatPosInThisBox)
		{
			aiNumThatInThis[iThatInThisCount] = w;
			apxPosThatInThis[iThatInThisCount++] = pxThatVertexPos;
		}
	}
#endif
	TOOLS_ADJACENCY_TICKS_END(CAWM_OTHERINMY);

	/*
	Now ideally we would produce an array of just the vertices in
	this module that are in the other module's bounding box, and
	then do a merge-join, either using hash tables or sorting both
	the ''this-in-that'' and ''that-in-this'' arrays ''fuzzily'' and
	then match-join the two arrays in a single pass.

	But then even more ideally this would be done on a whole-set of
	modules so that we don't have to rebuild and resort on every
	module-module comnbination, and would give intra-module
	adjacencies too in the same pass...

	But for now we shall just do a nested loop join, hoping the
	filtered arrays are small enough this is good enough. Indeed
	may be _better_ because hash table building/sorting might
	be slower because of memory writes or cache trashing.
	*/

	int iVertexListAdded = 0;
	for (int v = 0; v < iThisVertexCount; v++)
	{
		TOOLS_ADJACENCY_STATS_INCR(CAWM_MYVERT);

		/*
		First convert a vertex relative to this mesh to be relative
		to the other mesh, then check if it is in the AABB of the
		other mesh.
		*/
#if defined TOOLS_ADJACENCY_SSE
		register const __m128 afThisVertexPosRelThat = _mm_add_ps(
			_mm_tools_loadu3_ps(&xThisMesh.GetVertex(v).x),
			afOffThisFromThat);

		register const bool bThisPosInThatBox
			= _mm_tools_tween3_ps
			(afThisVertexPosRelThat,afThatBoxMin,afThatBoxMax);
#else
		register const Asura_Vector_3 xThisVertexPosRelThat
			= xThisMesh.GetVertex(v) + xOffThisFromThat;

		register const bool bThisPosInThatBox
			= xThatBox.Contains(xThisVertexPosRelThat);
#endif

		if (bThisPosInThatBox)
		{
			TOOLS_ADJACENCY_STATS_INCR(CAWM_MYVERT_INBOX);

			for (int w = 0; w < iThatInThisCount; w++)
			{
				TOOLS_ADJACENCY_STATS_INCR(CAWM_OTHERVERT);

				TOOLS_ADJACENCY_TICKS_BEG(CAWM_OTHERVERT);
#if defined TOOLS_ADJACENCY_SSE
#if defined TOOLS_ADJACENCY_SSE_COPY
				register const __m128 afVertexDist = _mm_sub_ps
					(afThisVertexPosRelThat,aafPosThatInThis[w]);
#else
				register const __m128 afThatVertexPos
					= _mm_tools_loadu3_ps(&apxPosThatInThis[w]->x);
				register const __m128 afVertexDist = _mm_sub_ps
					(afThisVertexPosRelThat,afThatVertexPos);
#endif
				register const bool bThisPosNearbyThatPos
					= _mm_tools_tween3_ps
					(afVertexDist,afMinusFuzz,afPlusFuzz);
#else
				register const Asura_Vector_3 xVertexDist
					= xThisVertexPosRelThat - *(apxPosThatInThis[w]);

				register const bool bThisPosNearbyThatPos
					= Tools_Adjacency
					::IsDistanceWithinTolerance(xVertexDist);
#endif
				TOOLS_ADJACENCY_TICKS_END(CAWM_OTHERVERT);

				if (bThisPosNearbyThatPos)
				{
					TOOLS_ADJACENCY_STATS_INCR(CAWM_OTHERVERT_NEAR);

					TOOLS_ADJACENCY_TICKS_BEG(CAWM_OTHERVERT_NEAR);
					Tools_Adjacency_VertexMatch::AddEntry(v,aiNumThatInThis[w]);
					iVertexListAdded++;
					TOOLS_ADJACENCY_TICKS_END(CAWM_OTHERVERT_NEAR);
				}
			}
		}
	}
	TOOLS_ADJACENCY_TICKS_END(CAWM_VERTVERT);

#if 0 && PG_PROFILE
	Asura_OutputToDebugger_Retail((
		"Filtering: this %d, that %d (of %d), shared %d\n",
		iThisVertexCount,iThatInThisCount,iThatVertexCount,iVertexListAdded));
#endif

	delete[] aiNumThatInThis;

#if defined TOOLS_ADJACENCY_SSE && defined TOOLS_ADJACENCY_SSE_COPY
	_mm_free(aafPosThatInThis);
#else
	delete[] apxPosThatInThis;
#endif

	*piVertexListCount += iVertexListAdded;
}

void Tools_Module_Adjacency::CalculateAdjacenciesWithModule(Asura_Module_Handler* pxOtherModuleHandler,const Asura_Hash_ID uOtherZoneHash,const int iOtherId)
{
	const int iMyId = m_iModuleId;

	TOOLS_ADJACENCY_STATS_INCR(CAWM_CALLS);
	TOOLS_ADJACENCY_TICKS_BEG(CAWM_CALL);
	TOOLS_ADJACENCY_TICKS_BEG(CAWM_MISC);

	Tools_RenderOrCollMesh& xMyMesh = m_xMesh;
	Tools_RenderOrCollMesh xOtherMesh;

	if(xMyMesh.IsCollMesh())
		xOtherMesh.Initialise(pxOtherModuleHandler->GetCollisionMeshForModule(iOtherId));
	else
		xOtherMesh.Initialise(pxOtherModuleHandler->GetMeshForModule(iOtherId));

	
	

	/*
		Make *copies* of the bounding boxes and fatten them slightly.
	*/
	Asura_Bounding_Box xMyBox = xMyMesh.GetBoundingBox();
	Asura_Bounding_Box xOtherBox = xOtherMesh.GetBoundingBox();

	const float fFat = 0.01f;

	xMyBox.MinX -= fFat; xMyBox.MaxX += fFat;
	xMyBox.MinY -= fFat; xMyBox.MaxY += fFat;
	xMyBox.MinZ -= fFat; xMyBox.MaxZ += fFat;

	xOtherBox.MinX -= fFat; xOtherBox.MaxX += fFat;
	xOtherBox.MinY -= fFat; xOtherBox.MaxY += fFat;
	xOtherBox.MinZ -= fFat; xOtherBox.MaxZ += fFat;

	/*
		Grab the origins of the meshes, and compute the offset
		of the other relative to this. Vertex positions in a
		mesh are relative to the origin in the mesh.
	*/
	Asura_Vector_3 xMyPosition;
	Asura_Vector_3 xOtherPosition;

	Asura_Module_System::GetPositionOfModule(iMyId,xMyPosition);
	pxOtherModuleHandler->GetPositionOfModule(iOtherId,xOtherPosition);

	const Asura_Vector_3 xOffOtherFromMy = xOtherPosition-xMyPosition;

	/*
		If the (fattened) bounding boxes do not intersect at all, no
		adjacencies are possible, so give up.
	*/
	if (!xMyBox.Intersects(xOtherBox,xOffOtherFromMy))
	{
		TOOLS_ADJACENCY_TICKS_END(CAWM_CALL);
		TOOLS_ADJACENCY_TICKS_END(CAWM_MISC);
		TOOLS_ADJACENCY_STATS_INCR(CAWM_NOINTERSECT);

		return;
	}

	/*
		For each vertex in this module's mesh we have an initially empty
		_list_ of ''equivalent'' (very near to...) vertices in the other
		module. This means that multiple vertices in a module's mesh can
		be ''equivalent''.
	*/

	const int iMyVertexCount	= xMyMesh.GetNumberOfVertices();

	TOOLS_ADJACENCY_TICKS_END(CAWM_MISC);

	TOOLS_ADJACENCY_TICKS_BEG(CAWM_LIST);

	int iMyVertexListCount = 0;
	const int iMyVertexListSize = iMyVertexCount;
	Tools_Adjacency_VertexMatch::StartVertMatch(iMyVertexListSize);


	/*
		We might as well compute the AABB that is the intersection
		of both, and pass just that, but later...
	*/
	TOOLS_ADJACENCY_TICKS_END(CAWM_LIST);

	TOOLS_ADJACENCY_TICKS_BEG(CAWM_VV);
	Tools_Module_Adjacencies_VV(&iMyVertexListCount,
		xMyMesh,xMyBox,xOtherMesh,xOtherBox,
		/* note the '-' */ -xOffOtherFromMy);
	TOOLS_ADJACENCY_TICKS_END(CAWM_VV);


	if (iMyVertexListCount == 0)
	{
		TOOLS_ADJACENCY_TICKS_BEG(CAWM_LIST);
		Tools_Adjacency_VertexMatch::EndVertMatch();
		TOOLS_ADJACENCY_TICKS_END(CAWM_LIST);

		TOOLS_ADJACENCY_TICKS_END(CAWM_CALL);
		TOOLS_ADJACENCY_STATS_INCR(CAWM_VERT_NOSHARED);

		return;
	}
	TOOLS_ADJACENCY_TICKS_BEG(CAWM_MISC);

	/*
		At this point we know that this module and the other module have
		shared vertices, and that for every vertex in this module and
		entry in the array 'pxMyVertexList' points to a list of the
		vertices in the other modules that are the the ''equivalent''
		vertex.

		What we need now is to use this ''shared vertex'' info to build
		the adjacencies lists: for each vertex the list of all polygons
		sharing it in the other module and for each polygon the list of
		polygons in the other module that share a vertex with it.
	*/

	const int iMyPolyCount		= xMyMesh.GetNumberOfPolygons();
	const int iOtherPolyCount	= xOtherMesh.GetNumberOfPolygons();

	int iPolyAdjacentCount = 0;

	/*
		For each vertex in this mesh which has got at least one
		''equivalent'' vertex in the other module, check all the
		polygons in the other mesh, and for each other polygon check
		whether the vertex in this mesh is the same as the vertex in
		that polygon and if so add it to the list of polygons sharing
		this vertex.
	*/
	TOOLS_ADJACENCY_TICKS_END(CAWM_MISC);
	TOOLS_ADJACENCY_TICKS_BEG(CAWM_VERTPOLY);

#ifdef TOOLS_LOG_ADJACENCY_INFO
	u_int uNumberOfMatchedVertices = 0;
#endif
	for (int v = 0; v < iMyVertexCount; v++)
	{
		TOOLS_ADJACENCY_STATS_INCR(CAWM_MYVERTPOLY);

		if (Tools_Adjacency_VertexMatch::GetNumMatchedVerts(v) > 0)
		{
#ifdef TOOLS_LOG_ADJACENCY_INFO
			uNumberOfMatchedVertices+= Tools_Adjacency_VertexMatch::GetNumMatchedVerts(v);
#endif
			TOOLS_ADJACENCY_STATS_INCR(CAWM_MYVERTPOLY_HASADJ);

			for (int p = 0; p < iOtherPolyCount; p++)
			{
				const int iOtherPolyVertexCount	= xOtherMesh.GetNumberOfVertsInPoly(p);

				TOOLS_ADJACENCY_STATS_INCR(CAWM_MYVERTPOLY_OTHERPOLY);

				for (int w = 0; w < iOtherPolyVertexCount; w++)
				{
					const int iOtherPolyVertexId = xOtherMesh.GetVertexIndex(p,w);

					TOOLS_ADJACENCY_STATS_INCR(CAWM_MYVERTPOLY_OTHERPOLYVERT);

					/*
						This 'contains' on a list is probably a linear scan.
					*/
					if (Tools_Adjacency_VertexMatch::IsMatched(v,iOtherPolyVertexId))
					{
						TOOLS_ADJACENCY_STATS_INCR
							(CAWM_MYVERTPOLY_VERTCONTAINS);

						Asura_Assert(v < iMyVertexCount,"");
						this->Vertices[v].AddAdjacency(uOtherZoneHash,iOtherId,p);

						iPolyAdjacentCount++;
						break;
					}
				}
			}
		}
	}
	TOOLS_ADJACENCY_TICKS_END(CAWM_VERTPOLY);

	/*
		For each polygon in this mesh, and each polygon in the other
		mesh, check whether they have overlapping vertices, in that case
		they are adjacent, and then add the other polygon to the list of
		polygons adjacent to this polygon.
	*/
	TOOLS_ADJACENCY_TICKS_BEG(CAWM_POLYPOLY);

	for (int p = 0; p < iMyPolyCount; p++)
	{
		const int iMyPolyVertexCount = xMyMesh.GetNumberOfVertsInPoly(p);

		TOOLS_ADJACENCY_STATS_INCR(CAWM_MYPOLY);

		for (int v = 0; v < iMyPolyVertexCount; v++)
		{
			int iMyPolyVertexId = xMyMesh.GetVertexIndex(p,v);

			TOOLS_ADJACENCY_STATS_INCR(CAWM_MYPOLYVERT);

			/*
				We are only interested in checking vertices of this
				polygon that are ''shared'' with the other module.
			*/
			int iNumMatchedVerts = Tools_Adjacency_VertexMatch::GetNumMatchedVerts(iMyPolyVertexId);
			if (iNumMatchedVerts > 0)
			{
				TOOLS_ADJACENCY_STATS_INCR(CAWM_MYPOLYVERT_HASLIST);

				for (int iMatchIndex=0;iMatchIndex<iNumMatchedVerts;iMatchIndex++)
				{
					TOOLS_ADJACENCY_STATS_INCR(CAWM_MYPOLYVERT_LISTSZ);

					for (int q = 0; q < iOtherPolyCount; q++)
					{
						const int iOtherPolyVertexCount = xOtherMesh.GetNumberOfVertsInPoly(q);

						TOOLS_ADJACENCY_STATS_INCR(CAWM_OTHERPOLY);

						for (int w = 0; w < iOtherPolyVertexCount; w++)
						{
							/*
								If the current vertex in our mesh is
								''the same'' as the current vertex in
								the other mesh, then these two polygons
								in different modules are adjacent.
							*/

							TOOLS_ADJACENCY_STATS_INCR(CAWM_OTHERPOLY_VERT);

							if (Tools_Adjacency_VertexMatch::GetMatchedVert(iMyPolyVertexId,iMatchIndex)
								  == xOtherMesh.GetVertexIndex(q,w))
							{
								TOOLS_ADJACENCY_STATS_INCR
									(CAWM_OTHERPOLY_VERTCOMMON);

								Asura_Assert(p < iMyPolyCount,"");
								this->Polygons[p].AddAdjacency(uOtherZoneHash,iOtherId,q);

								iPolyAdjacentCount++;
								break;
							}
						}
					}
				}
			}
		}
	}
	TOOLS_ADJACENCY_TICKS_END(CAWM_POLYPOLY);


	TOOLS_ADJACENCY_TICKS_BEG(CAWM_LIST);
	Tools_Adjacency_VertexMatch::EndVertMatch();
	TOOLS_ADJACENCY_TICKS_END(CAWM_LIST);

	TOOLS_ADJACENCY_TICKS_BEG(CAWM_ADDLINK);
	if (iPolyAdjacentCount > 0)
	{
		this->AddLink(uOtherZoneHash,iOtherId);
		#ifdef ASURA_USE_STREAMING
		Tools_Adjacency_Handler* pxOtherAdjHandler = Tools_Adjacency::GetHandler(uOtherZoneHash);
		#else
		Tools_Adjacency_Handler* pxOtherAdjHandler = &Tools_Adjacency::GetCurrentHandler();
		#endif
		pxOtherAdjHandler->AddLink(iOtherId,m_uZoneHash,iMyId,m_bCollisionMesh);
	}
	TOOLS_ADJACENCY_TICKS_END(CAWM_ADDLINK);


	TOOLS_ADJACENCY_TICKS_END(CAWM_CALL);

#ifdef TOOLS_LOG_ADJACENCY_INFO
	Asura_Logfile_Retail(( TOOLS_ADJACENCY_LOGFILE, "Mods: %d:%d\t\tVerts:%d\t\tPolys:%d\n", iMyId, iOtherId, uNumberOfMatchedVertices, iPolyAdjacentCount ));
#endif
}
#endif

void Tools_Module_Adjacency::AddLink(const Asura_Hash_ID uZoneHash,const int iModuleId)
{
	TOOLS_ADJACENCY_STATS_INCR(AL_CALLS);

	/* Scan to ensure that the module is not already linked. */
	for (int i = 0; i < m_iLinkedModulesCount; i++)
	{
		if (m_pxLinkedModules[i].m_iModuleIndex == iModuleId && m_pxLinkedModules[i].m_uZoneHash == uZoneHash)
		{
			return;
		}
	}

	/* Enlarge the array if needed */
	if (m_iLinkedModulesCount == m_iLinkedModulesCapacity)
	{
		if (m_iLinkedModulesCapacity == 0)
		{
			m_iLinkedModulesCapacity = 8;
		}
		else
		{
			#if 1
				/* Increase capacity of linked modules array by 50% */
				m_iLinkedModulesCapacity *= 3;
				m_iLinkedModulesCapacity /= 2;
			#else
				m_iLinkedModulesCapacity += 4;
			#endif
		}

		Tools_Adjacency_LinkedModule* const pxNewArray = new Tools_Adjacency_LinkedModule[m_iLinkedModulesCapacity];

		Asura_Assert(pxNewArray != 0,
			"'new' failed: linked modules table");

		for (int i = 0; i < m_iLinkedModulesCount; i++)
		{
			pxNewArray[i] = m_pxLinkedModules[i];
		}

		if (m_pxLinkedModules != 0)
		{
			delete[] m_pxLinkedModules;
		}

		m_pxLinkedModules = pxNewArray;
	}

	/* Append the module to the list of linked modules */
	m_pxLinkedModules[m_iLinkedModulesCount].m_uZoneHash = uZoneHash;
	m_pxLinkedModules[m_iLinkedModulesCount].m_iModuleIndex = iModuleId;
	m_iLinkedModulesCount++;
}

void Tools_Module_Adjacency::DeleteLink(const Asura_Hash_ID uZoneHash,const int iModuleId)
{
	TOOLS_ADJACENCY_STATS_INCR(DL_CALLS);

	//Removal of a link will also result in this module's adjacencies being invalid.
	//RAR 08/06/2006
	Invalidate();

	for (int i = 0; i < m_iLinkedModulesCount; i++)
	{
		if (m_pxLinkedModules[i].m_iModuleIndex == iModuleId && m_pxLinkedModules[i].m_uZoneHash == uZoneHash)
		{
			m_pxLinkedModules[i] = m_pxLinkedModules[--m_iLinkedModulesCount];
			return;
		}
	}
}

void Tools_Module_Adjacency::InvalidateLinkedModules()
{
	TOOLS_ADJACENCY_STATS_INCR(ILM_CALLS);

//	Tools_Adjacency_Handler& xHandler = Tools_Adjacency::GetCurrentHandler();
	#ifndef ASURA_USE_STREAMING
	Tools_Adjacency_Handler* pxAdjHandler = &Tools_Adjacency::GetCurrentHandler();
	#endif

	
	Tools_Adjacency_LinkedModule* pxLinkedModule = m_pxLinkedModules;
	
	for (int i = 0; i < m_iLinkedModulesCount; i++,pxLinkedModule++)
	{
		#ifdef ASURA_USE_STREAMING
		Tools_Adjacency_Handler* pxAdjHandler = Tools_Adjacency::GetHandler(m_pxLinkedModules[i].m_uZoneHash);
		#endif
		
		if(pxAdjHandler)
		{
			pxAdjHandler->DeleteLink(m_pxLinkedModules[i].m_iModuleIndex,m_uZoneHash,m_iModuleId,m_bCollisionMesh);
		}
	}

	m_iLinkedModulesCount = 0;
}
