HL2Overcharged/public/disp_common.cpp

//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose: 
//
// $NoKeywords: $
//=============================================================================//

#include "disp_common.h"
#include "disp_powerinfo.h"
#include "builddisp.h"

// memdbgon must be the last include file in a .cpp file!!!
#include "tier0/memdbgon.h"

class CNodeVert
{
public:
	CNodeVert()					{}
	CNodeVert(int ix, int iy) { x = ix; y = iy; }

	inline int&			operator[](int i)			{ return ((int*)this)[i]; }
	inline int const&	operator[](int i) const	{ return ((int*)this)[i]; }

	int x, y;
};

static CNodeVert const g_NodeChildLookup[4][2] =
{
	{ CNodeVert(0, 0), CNodeVert(1, 1) },
	{ CNodeVert(1, 0), CNodeVert(2, 1) },
	{ CNodeVert(0, 1), CNodeVert(1, 2) },
	{ CNodeVert(1, 1), CNodeVert(2, 2) }
};

static CNodeVert const g_NodeTriWinding[9] =
{
	CNodeVert(0, 1),
	CNodeVert(0, 0),
	CNodeVert(1, 0),
	CNodeVert(2, 0),
	CNodeVert(2, 1),
	CNodeVert(2, 2),
	CNodeVert(1, 2),
	CNodeVert(0, 2),
	CNodeVert(0, 1)
};

// Indexed by CORNER_. These store NEIGHBOREDGE_ defines and tell which edges butt up against the corner.
static int g_CornerEdges[4][2] =
{
	{ NEIGHBOREDGE_BOTTOM, NEIGHBOREDGE_LEFT },	// CORNER_LOWER_LEFT
	{ NEIGHBOREDGE_TOP, NEIGHBOREDGE_LEFT },	// CORNER_UPPER_LEFT
	{ NEIGHBOREDGE_TOP, NEIGHBOREDGE_RIGHT },	// CORNER_UPPER_RIGHT
	{ NEIGHBOREDGE_BOTTOM, NEIGHBOREDGE_RIGHT }	// CORNER_LOWER_RIGHT
};

int g_EdgeDims[4] =
{
	0,		// NEIGHBOREDGE_LEFT   = X
	1,		// NEIGHBOREDGE_TOP    = Y
	0,		// NEIGHBOREDGE_RIGHT  = X
	1		// NEIGHBOREDGE_BOTTOM = Y
};

CShiftInfo g_ShiftInfos[3][3] =
{
	{
		{ 0, 0, true },		// CORNER_TO_CORNER -> CORNER_TO_CORNER
		{ 0, -1, true },		// CORNER_TO_CORNER -> CORNER_TO_MIDPOINT
		{ 2, -1, true }		// CORNER_TO_CORNER -> MIDPOINT_TO_CORNER
	},

	{
		{ 0, 1, true },		// CORNER_TO_MIDPOINT -> CORNER_TO_CORNER
		{ 0, 0, false },		// CORNER_TO_MIDPOINT -> CORNER_TO_MIDPOINT (invalid)
		{ 0, 0, false }		// CORNER_TO_MIDPOINT -> MIDPOINT_TO_CORNER (invalid)
	},

	{
		{ -1, 1, true },		// MIDPOINT_TO_CORNER -> CORNER_TO_CORNER
		{ 0, 0, false },		// MIDPOINT_TO_CORNER -> CORNER_TO_MIDPOINT (invalid)
		{ 0, 0, false }		// MIDPOINT_TO_CORNER -> MIDPOINT_TO_CORNER (invalid)
	}
};

int g_EdgeSideLenMul[4] =
{
	0,
	1,
	1,
	0
};


// --------------------------------------------------------------------------------- //
// Helper functions.
// --------------------------------------------------------------------------------- //

inline int SignedBitShift(int val, int shift)
{
	if (shift > 0)
		return val << shift;
	else
		return val >> -shift;
}

static inline void RotateVertIndex(
	NeighborOrientation neighor,
	int sideLengthMinus1,
	CVertIndex const &in,
	CVertIndex &out)
{
	if (neighor == ORIENTATION_CCW_0)
	{
		out = in;
	}
	else if (neighor == ORIENTATION_CCW_90)
	{
		out.x = in.y;
		out.y = sideLengthMinus1 - in.x;
	}
	else if (neighor == ORIENTATION_CCW_180)
	{
		out.x = sideLengthMinus1 - in.x;
		out.y = sideLengthMinus1 - in.y;
	}
	else
	{
		out.x = sideLengthMinus1 - in.y;
		out.y = in.x;
	}
}

static inline void RotateVertIncrement(
	NeighborOrientation neighor,
	CVertIndex const &in,
	CVertIndex &out)
{
	if (neighor == ORIENTATION_CCW_0)
	{
		out = in;
	}
	else if (neighor == ORIENTATION_CCW_90)
	{
		out.x = in.y;
		out.y = -in.x;
	}
	else if (neighor == ORIENTATION_CCW_180)
	{
		out.x = -in.x;
		out.y = -in.y;
	}
	else
	{
		out.x = -in.y;
		out.y = in.x;
	}
}


// --------------------------------------------------------------------------------- //
// CDispHelper functions.
// --------------------------------------------------------------------------------- //

int GetEdgeIndexFromPoint(CVertIndex const &index, int iMaxPower)
{
	int sideLengthMinus1 = 1 << iMaxPower;

	if (index.x == 0)
		return NEIGHBOREDGE_LEFT;
	else if (index.y == sideLengthMinus1)
		return NEIGHBOREDGE_TOP;
	else if (index.x == sideLengthMinus1)
		return NEIGHBOREDGE_RIGHT;
	else if (index.y == 0)
		return NEIGHBOREDGE_BOTTOM;
	else
		return -1;
}


int GetCornerIndexFromPoint(CVertIndex const &index, int iPower)
{
	int sideLengthMinus1 = 1 << iPower;

	if (index.x == 0 && index.y == 0)
		return CORNER_LOWER_LEFT;

	else if (index.x == 0 && index.y == sideLengthMinus1)
		return CORNER_UPPER_LEFT;

	else if (index.x == sideLengthMinus1 && index.y == sideLengthMinus1)
		return CORNER_UPPER_RIGHT;

	else if (index.x == sideLengthMinus1 && index.y == 0)
		return CORNER_LOWER_RIGHT;

	else
		return -1;
}


int GetNeighborEdgePower(CDispUtilsHelper *pDisp, int iEdge, int iSub)
{
	CDispNeighbor *pEdge = pDisp->GetEdgeNeighbor(iEdge);
	CDispSubNeighbor *pSub = &pEdge->m_SubNeighbors[iSub];
	if (!pSub->IsValid())
		return -1;

	CDispUtilsHelper *pNeighbor = pDisp->GetDispUtilsByIndex(pSub->GetNeighborIndex());

	CShiftInfo *pInfo = &g_ShiftInfos[pSub->m_Span][pSub->m_NeighborSpan];
	Assert(pInfo->m_bValid);

	return pNeighbor->GetPower() + pInfo->m_PowerShiftAdd;
}


CDispUtilsHelper* SetupEdgeIncrements(
	CDispUtilsHelper *pDisp,
	int iEdge,
	int iSub,
	CVertIndex &myIndex,
	CVertIndex &myInc,
	CVertIndex &nbIndex,
	CVertIndex &nbInc,
	int &myEnd,
	int &iFreeDim)
{
	int iEdgeDim = g_EdgeDims[iEdge];
	iFreeDim = !iEdgeDim;

	CDispNeighbor *pSide = pDisp->GetEdgeNeighbor(iEdge);
	CDispSubNeighbor *pSub = &pSide->m_SubNeighbors[iSub];
	if (!pSub->IsValid())
		return NULL;

	CDispUtilsHelper *pNeighbor = pDisp->GetDispUtilsByIndex(pSub->m_iNeighbor);

	CShiftInfo *pShiftInfo = &g_ShiftInfos[pSub->m_Span][pSub->m_NeighborSpan];
	Assert(pShiftInfo->m_bValid);

	// Setup a start point and edge increment (NOTE: just precalculate these
	// and store them in the CDispSubNeighbors).
	CVertIndex tempInc;

	const CPowerInfo *pPowerInfo = pDisp->GetPowerInfo();
	myIndex[iEdgeDim] = g_EdgeSideLenMul[iEdge] * pPowerInfo->m_SideLengthM1;
	myIndex[iFreeDim] = pPowerInfo->m_MidPoint * iSub;
	TransformIntoSubNeighbor(pDisp, iEdge, iSub, myIndex, nbIndex);

	int myPower = pDisp->GetPowerInfo()->m_Power;
	int nbPower = pNeighbor->GetPowerInfo()->m_Power + pShiftInfo->m_PowerShiftAdd;

	myInc[iEdgeDim] = tempInc[iEdgeDim] = 0;
	if (nbPower > myPower)
	{
		myInc[iFreeDim] = 1;
		tempInc[iFreeDim] = 1 << (nbPower - myPower);
	}
	else
	{
		myInc[iFreeDim] = 1 << (myPower - nbPower);
		tempInc[iFreeDim] = 1;
	}
	RotateVertIncrement(pSub->GetNeighborOrientation(), tempInc, nbInc);

	// Walk along the edge.
	if (pSub->m_Span == CORNER_TO_MIDPOINT)
		myEnd = pDisp->GetPowerInfo()->m_SideLength >> 1;
	else
		myEnd = pDisp->GetPowerInfo()->m_SideLength - 1;

	return pNeighbor;
}


int GetSubNeighborIndex(
	CDispUtilsHelper *pDisp,
	int iEdge,
	CVertIndex const &nodeIndex)
{
	const CPowerInfo *pPowerInfo = pDisp->GetPowerInfo();
	const CDispNeighbor *pSide = pDisp->GetEdgeNeighbor(iEdge);

	// Figure out if this is a vertical or horizontal edge.
	int iEdgeDim = g_EdgeDims[iEdge];
	int iFreeDim = !iEdgeDim;

	int iFreeIndex = nodeIndex[iFreeDim];

	// Figure out which of the (up to two) neighbors it lies in.
	int iSub = 0;
	if (iFreeIndex == pPowerInfo->m_MidPoint)
	{
		// If it's in the middle, we only are interested if there's one neighbor
		// next to us (so we can enable its middle vert). If there are any neighbors
		// that touch the midpoint, then we have no need to return them because it would
		// touch their corner verts which are always active.
		if (pSide->m_SubNeighbors[0].m_Span != CORNER_TO_CORNER)
			return -1;
	}
	else if (iFreeIndex > pPowerInfo->m_MidPoint)
	{
		iSub = 1;
	}

	// Make sure we get a valid neighbor.
	if (!pSide->m_SubNeighbors[iSub].IsValid())
	{
		if (iSub == 1 &&
			pSide->m_SubNeighbors[0].IsValid() &&
			pSide->m_SubNeighbors[0].m_Span == CORNER_TO_CORNER)
		{
			iSub = 0;
		}
		else
		{
			return -1;
		}
	}

	return iSub;
}


void SetupSpan(int iPower, int iEdge, NeighborSpan span, CVertIndex &viStart, CVertIndex &viEnd)
{
	int iFreeDim = !g_EdgeDims[iEdge];
	const CPowerInfo *pPowerInfo = GetPowerInfo(iPower);

	viStart = pPowerInfo->GetCornerPointIndex(iEdge);
	viEnd = pPowerInfo->GetCornerPointIndex((iEdge + 1) & 3);;

	if (iEdge == NEIGHBOREDGE_RIGHT || iEdge == NEIGHBOREDGE_BOTTOM)
	{
		// CORNER_TO_MIDPOINT and MIDPOINT_CORNER are defined where the edge moves up or right,
		// but pPowerInfo->GetCornerPointIndex walks around the edges clockwise, so on the
		// bottom and right edges (where GetCornerPointIndex has us moving down and left) we need to
		// reverse the sense here to make sure we return the right span.
		if (span == CORNER_TO_MIDPOINT)
			viStart[iFreeDim] = pPowerInfo->GetMidPoint();
		else if (span == MIDPOINT_TO_CORNER)
			viEnd[iFreeDim] = pPowerInfo->GetMidPoint();
	}
	else
	{
		if (span == CORNER_TO_MIDPOINT)
			viEnd[iFreeDim] = pPowerInfo->GetMidPoint();
		else if (span == MIDPOINT_TO_CORNER)
			viStart[iFreeDim] = pPowerInfo->GetMidPoint();
	}
}


CDispUtilsHelper* TransformIntoSubNeighbor(
	CDispUtilsHelper *pDisp,
	int iEdge,
	int iSub,
	CVertIndex const &nodeIndex,
	CVertIndex &out
	)
{
	const CDispSubNeighbor *pSub = &pDisp->GetEdgeNeighbor(iEdge)->m_SubNeighbors[iSub];

	// Find the part of pDisp's edge that this neighbor covers.
	CVertIndex viSrcStart, viSrcEnd;
	SetupSpan(pDisp->GetPower(), iEdge, pSub->GetSpan(), viSrcStart, viSrcEnd);

	// Find the corresponding parts on the neighbor.
	CDispUtilsHelper *pNeighbor = pDisp->GetDispUtilsByIndex(pSub->GetNeighborIndex());
	int iNBEdge = (iEdge + 2 + pSub->GetNeighborOrientation()) & 3;

	CVertIndex viDestStart, viDestEnd;
	SetupSpan(pNeighbor->GetPower(), iNBEdge, pSub->GetNeighborSpan(), viDestEnd, viDestStart);


	// Now map the one into the other.
	int iFreeDim = !g_EdgeDims[iEdge];
	int fixedPercent = ((nodeIndex[iFreeDim] - viSrcStart[iFreeDim]) * (1 << 16)) / (viSrcEnd[iFreeDim] - viSrcStart[iFreeDim]);
	Assert(fixedPercent >= 0 && fixedPercent <= (1 << 16));

	int nbDim = g_EdgeDims[iNBEdge];
	out[nbDim] = viDestStart[nbDim];
	out[!nbDim] = viDestStart[!nbDim] + ((viDestEnd[!nbDim] - viDestStart[!nbDim]) * fixedPercent) / (1 << 16);

	Assert(out.x >= 0 && out.x < pNeighbor->GetSideLength());
	Assert(out.y >= 0 && out.y < pNeighbor->GetSideLength());

	return pNeighbor;
}


CDispUtilsHelper* TransformIntoNeighbor(
	CDispUtilsHelper *pDisp,
	int iEdge,
	CVertIndex const &nodeIndex,
	CVertIndex &out
	)
{
	if (iEdge == -1)
		iEdge = GetEdgeIndexFromPoint(nodeIndex, pDisp->GetPower());

	int iSub = GetSubNeighborIndex(pDisp, iEdge, nodeIndex);
	if (iSub == -1)
		return NULL;

	CDispUtilsHelper *pRet = TransformIntoSubNeighbor(pDisp, iEdge, iSub, nodeIndex, out);

#if 0
	// Debug check.. make sure it comes back to the same point from the other side.
#if defined( _DEBUG )
	static bool bTesting = false;
	if (pRet && !bTesting)
	{
		bTesting = true;

		// We could let TransformIntoNeighbor figure out the index but if this is a corner vert, then
		// it may pick the wrong edge and we'd get a benign assert.
		int nbOrientation = pDisp->GetEdgeNeighbor(iEdge)->m_SubNeighbors[iSub].GetNeighborOrientation();
		int iNeighborEdge = (iEdge + 2 + nbOrientation) & 3;

		CVertIndex testIndex;
		CDispUtilsHelper *pTest = TransformIntoNeighbor(pRet, iNeighborEdge, out, testIndex);
		Assert(pTest == pDisp);
		Assert(testIndex == nodeIndex);

		bTesting = false;
	}
#endif
#endif

	return pRet;
}


bool DoesPointHaveAnyNeighbors(
	CDispUtilsHelper *pDisp,
	const CVertIndex &index)
{
	// See if it connects to a neighbor on the edge.
	CVertIndex dummy;
	if (TransformIntoNeighbor(pDisp, -1, index, dummy))
		return true;

	// See if it connects to a neighbor on a corner.
	int iCorner = GetCornerIndexFromPoint(index, pDisp->GetPower());
	if (iCorner == -1)
		return false;

	// If there are any neighbors on the specified corner, then the point has neighbors.
	if (pDisp->GetCornerNeighbors(iCorner)->m_nNeighbors > 0)
		return true;

	// Since points on corners touch two edges, we actually want to test two edges to see
	// if the point has a neighbor on either edge.
	for (int i = 0; i < 2; i++)
	{
		if (TransformIntoNeighbor(pDisp, g_CornerEdges[iCorner][i], index, dummy))
			return true;
	}

	return false;
}


// ------------------------------------------------------------------------------------ //
// CDispSubEdgeIterator.
// ------------------------------------------------------------------------------------ //

CDispSubEdgeIterator::CDispSubEdgeIterator()
{
	m_pNeighbor = 0;
	m_FreeDim = m_Index.x = m_Inc.x = m_End = 0;	// Setup so Next returns false.
}


void CDispSubEdgeIterator::Start(CDispUtilsHelper *pDisp, int iEdge, int iSub, bool bTouchCorners)
{
	m_pNeighbor = SetupEdgeIncrements(pDisp, iEdge, iSub, m_Index, m_Inc, m_NBIndex, m_NBInc, m_End, m_FreeDim);
	if (m_pNeighbor)
	{
		if (bTouchCorners)
		{
			// Back up our current position by 1 so we hit the corner first, and extend the endpoint
			// so we hit the other corner too.
			m_Index -= m_Inc;
			m_NBIndex -= m_NBInc;

			m_End += m_Inc[m_FreeDim];
		}
	}
	else
	{
		m_FreeDim = m_Index.x = m_Inc.x = m_End = 0;	// Setup so Next returns false.
	}
}


bool CDispSubEdgeIterator::Next()
{
	m_Index += m_Inc;
	m_NBIndex += m_NBInc;

	// Were we just at the last point on the edge?
	return m_Index[m_FreeDim] < m_End;
}


bool CDispSubEdgeIterator::IsLastVert() const
{
	return (m_Index[m_FreeDim] + m_Inc[m_FreeDim]) >= m_End;
}


// ------------------------------------------------------------------------------------ //
// CDispEdgeIterator.
// ------------------------------------------------------------------------------------ //

CDispEdgeIterator::CDispEdgeIterator(CDispUtilsHelper *pDisp, int iEdge)
{
	m_pDisp = pDisp;
	m_iEdge = iEdge;
	m_iCurSub = -1;
}


bool CDispEdgeIterator::Next()
{
	while (!m_It.Next())
	{
		// Ok, move up to the next sub.
		if (m_iCurSub == 1)
			return false;

		++m_iCurSub;
		m_It.Start(m_pDisp, m_iEdge, m_iCurSub);
	}
	return true;
}


// ------------------------------------------------------------------------------------ //
// CDispCircumferenceIterator.
// ------------------------------------------------------------------------------------ //

CDispCircumferenceIterator::CDispCircumferenceIterator(int sideLength)
{
	m_iCurEdge = -1;
	m_SideLengthM1 = sideLength - 1;
}


bool CDispCircumferenceIterator::Next()
{
	switch (m_iCurEdge)
	{
	case -1:
	{
		m_iCurEdge = NEIGHBOREDGE_LEFT;
		m_VertIndex.Init(0, 0);
	}
	break;

	case NEIGHBOREDGE_LEFT:
	{
		++m_VertIndex.y;
		if (m_VertIndex.y == m_SideLengthM1)
			m_iCurEdge = NEIGHBOREDGE_TOP;
	}
	break;

	case NEIGHBOREDGE_TOP:
	{
		++m_VertIndex.x;
		if (m_VertIndex.x == m_SideLengthM1)
			m_iCurEdge = NEIGHBOREDGE_RIGHT;
	}
	break;

	case NEIGHBOREDGE_RIGHT:
	{
		--m_VertIndex.y;
		if (m_VertIndex.y == 0)
			m_iCurEdge = NEIGHBOREDGE_BOTTOM;
	}
	break;

	case NEIGHBOREDGE_BOTTOM:
	{
		--m_VertIndex.x;
		if (m_VertIndex.x == 0)
			return false; // Done!
	}
	break;
	}

	return true;
}



// Helper function to setup an index either on the edges or the center
// of the box defined by [bottomleft,topRight].
static inline void SetupCoordXY(CNodeVert &out, CNodeVert const &bottomLeft, CNodeVert const &topRight, CNodeVert const &info)
{
	for (int i = 0; i < 2; i++)
	{
		if (info[i] == 0)
			out[i] = bottomLeft[i];
		else if (info[i] == 1)
			out[i] = (bottomLeft[i] + topRight[i]) >> 1;
		else
			out[i] = topRight[i];
	}
}


static unsigned short* DispCommon_GenerateTriIndices_R(
	CNodeVert const &bottomLeft,
	CNodeVert const &topRight,
	unsigned short *indices,
	int power,
	int sideLength)
{
	if (power == 1)
	{
		// Ok, add triangles. All we do here is follow a list of verts (g_NodeTriWinding)
		// around the center vert of this node and make triangles.
		int iCurTri = 0;
		CNodeVert verts[3];

		// verts[0] is always the center vert.
		SetupCoordXY(verts[0], bottomLeft, topRight, CNodeVert(1, 1));
		int iCurVert = 1;

		for (int i = 0; i < 9; i++)
		{
			SetupCoordXY(verts[iCurVert], bottomLeft, topRight, g_NodeTriWinding[i]);
			++iCurVert;

			if (iCurVert == 3)
			{
				for (int iTriVert = 2; iTriVert >= 0; iTriVert--)
				{
					int index = verts[iTriVert].y * sideLength + verts[iTriVert].x;
					*indices = index;
					++indices;
				}

				// Setup for the next triangle.
				verts[1] = verts[2];
				iCurVert = 2;
				iCurTri++;
			}
		}
	}
	else
	{
		// Recurse into the children.
		for (int i = 0; i < 4; i++)
		{
			CNodeVert childBottomLeft, childTopRight;
			SetupCoordXY(childBottomLeft, bottomLeft, topRight, g_NodeChildLookup[i][0]);
			SetupCoordXY(childTopRight, bottomLeft, topRight, g_NodeChildLookup[i][1]);

			indices = DispCommon_GenerateTriIndices_R(childBottomLeft, childTopRight, indices, power - 1, sideLength);
		}
	}

	return indices;
}


// ------------------------------------------------------------------------------------------- //
// CDispUtilsHelper functions.
// ------------------------------------------------------------------------------------------- //

int CDispUtilsHelper::GetPower() const
{
	return GetPowerInfo()->GetPower();
}

int CDispUtilsHelper::GetSideLength() const
{
	return GetPowerInfo()->GetSideLength();
}

const CVertIndex& CDispUtilsHelper::GetCornerPointIndex(int iCorner) const
{
	return GetPowerInfo()->GetCornerPointIndex(iCorner);
}

int CDispUtilsHelper::VertIndexToInt(const CVertIndex &i) const
{
	Assert(i.x >= 0 && i.x < GetSideLength() && i.y >= 0 && i.y < GetSideLength());
	return i.y * GetSideLength() + i.x;
}

CVertIndex CDispUtilsHelper::GetEdgeMidPoint(int iEdge) const
{
	int end = GetSideLength() - 1;
	int mid = GetPowerInfo()->GetMidPoint();

	if (iEdge == NEIGHBOREDGE_LEFT)
		return CVertIndex(0, mid);

	else if (iEdge == NEIGHBOREDGE_TOP)
		return CVertIndex(mid, end);

	else if (iEdge == NEIGHBOREDGE_RIGHT)
		return CVertIndex(end, mid);

	else if (iEdge == NEIGHBOREDGE_BOTTOM)
		return CVertIndex(mid, 0);

	Assert(false);
	return CVertIndex(0, 0);
}

int DispCommon_GetNumTriIndices(int power)
{
	return (1 << power) * (1 << power) * 2 * 3;
}


void DispCommon_GenerateTriIndices(int power, unsigned short *indices)
{
	int sideLength = 1 << power;
	DispCommon_GenerateTriIndices_R(
		CNodeVert(0, 0),
		CNodeVert(sideLength, sideLength),
		indices,
		power,
		sideLength + 1);
}

//=============================================================================
//
// Finding neighbors.
//

// This table swaps MIDPOINT_TO_CORNER and CORNER_TO_MIDPOINT.
static NeighborSpan g_SpanFlip[3] = { CORNER_TO_CORNER, MIDPOINT_TO_CORNER, CORNER_TO_MIDPOINT };
static bool			g_bEdgeNeighborFlip[4] = { false, false, true, true };

// These map CCoreDispSurface neighbor orientations (which are actually edge indices)
// into our 'degrees of rotation' representation.
static int g_CoreDispNeighborOrientationMap[4][4] =
{
	{ ORIENTATION_CCW_180, ORIENTATION_CCW_270, ORIENTATION_CCW_0, ORIENTATION_CCW_90 },
	{ ORIENTATION_CCW_90, ORIENTATION_CCW_180, ORIENTATION_CCW_270, ORIENTATION_CCW_0 },
	{ ORIENTATION_CCW_0, ORIENTATION_CCW_90, ORIENTATION_CCW_180, ORIENTATION_CCW_270 },
	{ ORIENTATION_CCW_270, ORIENTATION_CCW_0, ORIENTATION_CCW_90, ORIENTATION_CCW_180 }
};

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void ClearNeighborData(CCoreDispInfo *pDisp)
{
	for (int i = 0; i < 4; i++)
	{
		pDisp->GetEdgeNeighbor(i)->SetInvalid();
		pDisp->GetCornerNeighbors(i)->SetInvalid();
	}
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void GetDispBox(CCoreDispInfo *pDisp, CDispBox &box)
{
	// Calculate the bbox for this displacement.
	Vector vMin(1e24, 1e24, 1e24);
	Vector vMax(-1e24, -1e24, -1e24);

	for (int iVert = 0; iVert < 4; ++iVert)
	{
		const Vector &vTest = pDisp->GetSurface()->GetPoint(iVert);
		VectorMin(vTest, vMin, vMin);
		VectorMax(vTest, vMax, vMax);
	}

	// Puff the box out a little.
	static float flPuff = 0.1f;
	vMin -= Vector(flPuff, flPuff, flPuff);
	vMax += Vector(flPuff, flPuff, flPuff);

	box.m_Min = vMin;
	box.m_Max = vMax;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void SetupDispBoxes(CCoreDispInfo **ppListBase, int nListSize, CUtlVector<CDispBox> &out)
{
	out.SetSize(nListSize);
	for (int iDisp = 0; iDisp < nListSize; ++iDisp)
	{
		CCoreDispInfo *pDisp = ppListBase[iDisp];
		GetDispBox(pDisp, out[iDisp]);
	}
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
inline bool DoBBoxesTouch(const CDispBox &a, const CDispBox &b)
{
	for (int i = 0; i < 3; i++)
	{
		if (a.m_Max[i] < b.m_Min[i])
			return false;

		if (a.m_Min[i] > b.m_Max[i])
			return false;
	}

	return true;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
bool FindEdge(CCoreDispInfo *pInfo, Vector const &vPoint1, Vector const &vPoint2, int &iEdge)
{
	CCoreDispSurface *pSurface = pInfo->GetSurface();

	for (iEdge = 0; iEdge < 4; iEdge++)
	{
		if (VectorsAreEqual(vPoint1, pSurface->GetPoint(iEdge), 0.01f) &&
			VectorsAreEqual(vPoint2, pSurface->GetPoint((iEdge + 1) & 3), 0.01f))
		{
			return true;
		}
	}

	return false;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
NeighborSpan NeighborSpanFlip(int iEdge, NeighborSpan span)
{
	if (g_bEdgeNeighborFlip[iEdge])
		return g_SpanFlip[span];
	else
		return span;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void AddNeighbor(CCoreDispInfo *pMain,
	int iEdge,				// Which of pMain's sides this is on.
	int iSub,				// Which sub neighbor this takes up in pSide.
	NeighborSpan span,		// What span this fills in pMain.
	CCoreDispInfo *pOther, int iNeighborEdge, NeighborSpan nbSpan)
{
	// The edge iteration before coming in here goes 0-1, 1-2, 2-3, 3-4.
	// This flips the sense of CORNER_TO_MIDPOINT/MIDPOINT_TO_CORNER on the right and 
	// bottom edges and is undone here.
	span = NeighborSpanFlip(iEdge, span);
	nbSpan = NeighborSpanFlip(iNeighborEdge, nbSpan);

	// Get the subspan this fills on our displacement.
	CDispSubNeighbor *pSub = &pMain->GetEdgeNeighbor(iEdge)->m_SubNeighbors[iSub];

	// Which subspan does this use in the neighbor?
	CDispSubNeighbor *pNeighborSub;
	if (nbSpan == MIDPOINT_TO_CORNER)
	{
		pNeighborSub = &pOther->GetEdgeNeighbor(iNeighborEdge)->m_SubNeighbors[1];
	}
	else
	{
		pNeighborSub = &pOther->GetEdgeNeighbor(iNeighborEdge)->m_SubNeighbors[0];
	}

	// Make sure this slot isn't used on either displacement.
	if (pSub->IsValid() || pNeighborSub->IsValid())
	{
		ExecuteOnce(Warning("Found a displacement edge abutting multiple other edges.\n"));
		return;
	}

	// Now just copy the data into each displacement.	
	pSub->m_iNeighbor = pOther->GetListIndex();
	pSub->m_NeighborOrientation = g_CoreDispNeighborOrientationMap[iEdge][iNeighborEdge];
	pSub->m_Span = span;
	pSub->m_NeighborSpan = nbSpan;

	pNeighborSub->m_iNeighbor = pMain->GetListIndex();
	pNeighborSub->m_NeighborOrientation = g_CoreDispNeighborOrientationMap[iNeighborEdge][iEdge];
	pNeighborSub->m_Span = nbSpan;
	pNeighborSub->m_NeighborSpan = span;

#if defined( _DEBUG )
	// Walk an iterator over the new connection to make sure it works.
	CDispSubEdgeIterator it;
	it.Start(pMain, iEdge, iSub);
	while (it.Next())
	{
		CVertIndex nbIndex;
		TransformIntoNeighbor(pMain, iEdge, it.GetVertIndex(), nbIndex);
	}
#endif
}

//-----------------------------------------------------------------------------
// This function is symmetric wrt pMain and pOther. It sets up valid neighboring data for
// the relationship between both of them.
//-----------------------------------------------------------------------------
void SetupEdgeNeighbors(CCoreDispInfo *pMain, CCoreDispInfo *pOther)
{
	// Initialize..
	for (int iEdge = 0; iEdge < 4; iEdge++)
	{
		// Setup the edge points and the midpoint.
		Vector pt[2], mid;
		pMain->GetSurface()->GetPoint(iEdge, pt[0]);
		pMain->GetSurface()->GetPoint((iEdge + 1) & 3, pt[1]);
		mid = (pt[0] + pt[1]) * 0.5f;

		// Find neighbors.
		int iNBEdge;
		if (FindEdge(pOther, pt[1], pt[0], iNBEdge))
		{
			AddNeighbor(pMain, iEdge, 0, CORNER_TO_CORNER, pOther, iNBEdge, CORNER_TO_CORNER);
		}
		else
		{
			// Look for one that takes up our whole side.
			if (FindEdge(pOther, pt[1], pt[0] * 2 - pt[1], iNBEdge))
			{
				AddNeighbor(pMain, iEdge, 0, CORNER_TO_CORNER, pOther, iNBEdge, CORNER_TO_MIDPOINT);
			}
			else if (FindEdge(pOther, pt[1] * 2 - pt[0], pt[0], iNBEdge))
			{
				AddNeighbor(pMain, iEdge, 0, CORNER_TO_CORNER, pOther, iNBEdge, MIDPOINT_TO_CORNER);
			}
			else
			{
				// Ok, look for 1 or two that abut this side.
				if (FindEdge(pOther, mid, pt[0], iNBEdge))
				{
					AddNeighbor(pMain, iEdge, g_bEdgeNeighborFlip[iEdge], CORNER_TO_MIDPOINT, pOther, iNBEdge, CORNER_TO_CORNER);
				}

				if (FindEdge(pOther, pt[1], mid, iNBEdge))
				{
					AddNeighbor(pMain, iEdge, !g_bEdgeNeighborFlip[iEdge], MIDPOINT_TO_CORNER, pOther, iNBEdge, CORNER_TO_CORNER);
				}
			}
		}
	}
}

//-----------------------------------------------------------------------------
// Returns true if the displacement has an edge neighbor with the given index.
//-----------------------------------------------------------------------------
bool HasEdgeNeighbor(const CCoreDispInfo *pMain, int iNeighbor)
{
	for (int i = 0; i < 4; i++)
	{
		const CDispCornerNeighbors *pCorner = pMain->GetCornerNeighbors(i);
		for (int iNB = 0; iNB < pCorner->m_nNeighbors; iNB++)
			if (pCorner->m_Neighbors[iNB] == iNeighbor)
				return true;

		const CDispNeighbor *pEdge = pMain->GetEdgeNeighbor(i);
		if (pEdge->m_SubNeighbors[0].GetNeighborIndex() == iNeighbor ||
			pEdge->m_SubNeighbors[1].GetNeighborIndex() == iNeighbor)
		{
			return true;
		}
	}
	return false;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void SetupCornerNeighbors(CCoreDispInfo *pMain, CCoreDispInfo *pOther, int *nOverflows)
{
	if (HasEdgeNeighbor(pMain, pOther->GetListIndex()))
		return;

	// Do these two share a vertex?
	int nShared = 0;
	int iMainSharedCorner = -1;
	int iOtherSharedCorner = -1;

	for (int iMainCorner = 0; iMainCorner < 4; iMainCorner++)
	{
		Vector const &vMainCorner = pMain->GetCornerPoint(iMainCorner);

		for (int iOtherCorner = 0; iOtherCorner < 4; iOtherCorner++)
		{
			Vector const &vOtherCorner = pOther->GetCornerPoint(iOtherCorner);

			if (VectorsAreEqual(vMainCorner, vOtherCorner, 0.001f))
			{
				iMainSharedCorner = iMainCorner;
				iOtherSharedCorner = iOtherCorner;
				++nShared;
			}
		}
	}

	if (nShared == 1)
	{
		CDispCornerNeighbors *pMainCorner = pMain->GetCornerNeighbors(iMainSharedCorner);
		CDispCornerNeighbors *pOtherCorner = pOther->GetCornerNeighbors(iOtherSharedCorner);

		if (pMainCorner->m_nNeighbors < MAX_DISP_CORNER_NEIGHBORS &&
			pOtherCorner->m_nNeighbors < MAX_DISP_CORNER_NEIGHBORS)
		{
			pMainCorner->m_Neighbors[pMainCorner->m_nNeighbors++] = pOther->GetListIndex();
			pOtherCorner->m_Neighbors[pOtherCorner->m_nNeighbors++] = pMain->GetListIndex();
		}
		else
		{
			++(*nOverflows);
		}
	}
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
bool VerifyNeighborVertConnection(CDispUtilsHelper *pDisp, const CVertIndex &nodeIndex,
	const CDispUtilsHelper *pTestNeighbor, const CVertIndex &testNeighborIndex,
	int mySide)
{
	CVertIndex nbIndex(-1, -1);
	CDispUtilsHelper *pNeighbor = NULL;
	if ((pNeighbor = TransformIntoNeighbor(pDisp, mySide, nodeIndex, nbIndex)) != NULL)
	{
		if (pTestNeighbor != pNeighbor || nbIndex != testNeighborIndex)
			return false;

		CVertIndex testIndex(-1, -1);
		int iSide = GetEdgeIndexFromPoint(nbIndex, pNeighbor->GetPowerInfo()->m_Power);
		if (iSide == -1)
		{
			return false;
		}

		CDispUtilsHelper *pTest = TransformIntoNeighbor(pNeighbor, iSide, nbIndex, testIndex);

		if (pTest != pDisp || nodeIndex != testIndex)
		{
			return false;
		}
	}

	return true;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void VerifyNeighborConnections(CCoreDispInfo **ppListBase, int nDisps)
{
	while (1)
	{
		bool bHappy = true;

		int iDisp;
		for (iDisp = 0; iDisp < nDisps; ++iDisp)
		{
			CCoreDispInfo *pDisp = ppListBase[iDisp];
			CDispUtilsHelper *pHelper = pDisp;

			for (int iEdge = 0; iEdge < 4; iEdge++)
			{
				CDispEdgeIterator it(pHelper, iEdge);
				while (it.Next())
				{
					if (!VerifyNeighborVertConnection(pHelper, it.GetVertIndex(), it.GetCurrentNeighbor(), it.GetNBVertIndex(), iEdge))
					{
						pDisp->GetEdgeNeighbor(iEdge)->SetInvalid();
						Warning("Warning: invalid neighbor connection on displacement near (%.2f %.2f %.2f)\n", VectorExpand(pDisp->GetCornerPoint(0)));
						bHappy = false;
					}
				}
			}
		}

		if (bHappy)
			break;
	}
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void FindNeighboringDispSurfs(CCoreDispInfo **ppListBase, int nListSize)
{
	// First, clear all neighboring data.
	int iDisp;
	for (iDisp = 0; iDisp < nListSize; ++iDisp)
	{
		ClearNeighborData(ppListBase[iDisp]);
	}

	CUtlVector<CDispBox> boxes;
	SetupDispBoxes(ppListBase, nListSize, boxes);

	int nCornerOverflows = 0;

	// Now test all pairs of displacements and setup neighboring relations between them.
	for (iDisp = 0; iDisp < nListSize; ++iDisp)
	{
		CCoreDispInfo *pMain = ppListBase[iDisp];

		for (int iDisp2 = iDisp + 1; iDisp2 < nListSize; ++iDisp2)
		{
			CCoreDispInfo *pOther = ppListBase[iDisp2];

			// Trivial reject.
			if (!DoBBoxesTouch(boxes[iDisp], boxes[iDisp2]))
				continue;

			SetupEdgeNeighbors(pMain, pOther);

			// NOTE: this must come after SetupEdgeNeighbors because it makes sure not to add
			// corner neighbors for disps that are already edge neighbors.
			SetupCornerNeighbors(pMain, pOther, &nCornerOverflows);
		}
	}

	if (nCornerOverflows)
	{
		Warning("Warning: overflowed %d displacement corner-neighbor lists.", nCornerOverflows);
	}

	// Debug check.. make sure the neighbor connections are intact (make sure that any
	// edge vert that gets mapped into a neighbor gets mapped back the same way).
	VerifyNeighborConnections(ppListBase, nListSize);
}

//=============================================================================
//
// Allowable verts.
//

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
int IsCorner(CVertIndex const &index, int sideLength)
{
	if (index.x == 0)
	{
		if (index.y == 0)
			return true;
		else if (index.y == sideLength - 1)
			return true;
	}
	else if (index.x == sideLength - 1)
	{
		if (index.y == 0)
			return true;
		else if (index.y == sideLength - 1)
			return true;
	}

	return false;
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
bool IsVertAllowed(CDispUtilsHelper *pDisp, CVertIndex const &sideVert, int iLevel)
{
	if (IsCorner(sideVert, pDisp->GetPowerInfo()->GetSideLength()))
		return true;

	int iSide = GetEdgeIndexFromPoint(sideVert, pDisp->GetPowerInfo()->GetPower());
	if (iSide == -1)
		return true;

	int iSub = GetSubNeighborIndex(pDisp, iSide, sideVert);
	if (iSub == -1)
		return true;

	CDispSubNeighbor *pSub = &pDisp->GetEdgeNeighbor(iSide)->m_SubNeighbors[iSub];
	CDispUtilsHelper *pNeighbor = pDisp->GetDispUtilsByIndex(pSub->m_iNeighbor);
	Assert(pNeighbor);

	// Ok, there is a neighbor.. see if this vertex exists in the neighbor.
	CShiftInfo *pShiftInfo = &g_ShiftInfos[pSub->m_Span][pSub->m_NeighborSpan];
	Assert(pShiftInfo->m_bValid);

	if ((pNeighbor->GetPowerInfo()->GetPower() + pShiftInfo->m_PowerShiftAdd) < (iLevel + 1))
	{
		return false;
	}

	// Ok, it exists. Make sure the neighbor hasn't disallowed it.
	CVertIndex nbIndex;
	TransformIntoSubNeighbor(pDisp, iSide, iSub, sideVert, nbIndex);

	CBitVec<MAX_DISPVERTS> &allowedVerts = CCoreDispInfo::FromDispUtils(pNeighbor)->GetAllowedVerts();
	return !!allowedVerts.Get(pNeighbor->VertIndexToInt(nbIndex));
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void UnallowVerts_R(CDispUtilsHelper *pDisp, CVertIndex const &nodeIndex, int &nUnallowed)
{
	int iNodeIndex = pDisp->VertIndexToInt(nodeIndex);

	CCoreDispInfo *pCoreDisp = CCoreDispInfo::FromDispUtils(pDisp);
	if (!pCoreDisp->GetAllowedVerts().Get(iNodeIndex))
		return;

	nUnallowed++;
	pCoreDisp->GetAllowedVerts().Clear(iNodeIndex);

	for (int iDep = 0; iDep < CVertInfo::NUM_REVERSE_DEPENDENCIES; iDep++)
	{
		CVertDependency &dep = pDisp->GetPowerInfo()->m_pVertInfo[iNodeIndex].m_ReverseDependencies[iDep];

		if (dep.m_iVert.x != -1 && dep.m_iNeighbor == -1)
		{
			UnallowVerts_R(pDisp, dep.m_iVert, nUnallowed);
		}
	}
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void DisableUnallowedVerts_R(CDispUtilsHelper *pDisp, CVertIndex const &nodeIndex, int iLevel, int &nUnallowed)
{
	int iNodeIndex = pDisp->VertIndexToInt(nodeIndex);

	// This vertex is not allowed if it is on an edge with a neighbor
	// that does not have this vertex.

	// Test side verts.
	for (int iSide = 0; iSide < 4; iSide++)
	{
		CVertIndex const &sideVert = pDisp->GetPowerInfo()->m_pSideVerts[iNodeIndex].m_Verts[iSide];

		if (!IsVertAllowed(pDisp, sideVert, iLevel))
		{
			// This vert (and its dependencies) can't exist.
			UnallowVerts_R(pDisp, sideVert, nUnallowed);
		}
	}

#if 0
	// Test dependencies.
	for (int iDep = 0; iDep < 2; iDep++)
	{
		CVertDependency const &dep = pDisp->GetPowerInfo()->m_pVertInfo[iNodeIndex].m_Dependencies[iDep];

		if (dep.m_iNeighbor == -1 && !IsVertAllowed(pDisp, dep.m_iVert, iLevel))
		{
			UnallowVerts_R(pDisp, nodeIndex, nUnallowed);
		}
	}
#endif

	// Recurse.
	if (iLevel + 1 < pDisp->GetPower())
	{
		for (int iChild = 0; iChild < 4; iChild++)
		{
			DisableUnallowedVerts_R(pDisp, pDisp->GetPowerInfo()->m_pChildVerts[iNodeIndex].m_Verts[iChild], iLevel + 1, nUnallowed);
		}
	}
}

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
void SetupAllowedVerts(CCoreDispInfo **ppListBase, int nListSize)
{
	// Set all verts to allowed to start with.
	int iDisp;
	for (iDisp = 0; iDisp < nListSize; ++iDisp)
	{
		ppListBase[iDisp]->GetAllowedVerts().SetAll();
	}

	// Disable verts that need to be disabled so higher-powered displacements remove
	// the necessary triangles when bordering lower-powered displacements.	
	// It is necessary to loop around here because disabling verts can accumulate into 
	// neighbors.
	bool bContinue;
	do
	{
		bContinue = false;
		for (iDisp = 0; iDisp < nListSize; ++iDisp)
		{
			CDispUtilsHelper *pDisp = ppListBase[iDisp];

			int nUnallowed = 0;
			DisableUnallowedVerts_R(pDisp, pDisp->GetPowerInfo()->m_RootNode, 0, nUnallowed);
			if (nUnallowed)
				bContinue = true;
		}
	} while (bContinue);
}