source-engine/public/disp_powerinfo.cpp

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

#include "disp_powerinfo.h"
#include "disp_common.h"
#include "commonmacros.h"

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

// ------------------------------------------------------------------------ //
// Internal classes.
// ------------------------------------------------------------------------ //

// These point at the vertices connecting to each of the [north,south,east,west] vertices.
class CVertCorners
{
public:
	short	m_Corner1[2];
	short	m_Corner2[2];
};


// ------------------------------------------------------------------------ //
// Globals.
// ------------------------------------------------------------------------ //

// This points at vertices to the side of a node (north, south, east, west).
static short g_SideVertMul[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

static CVertCorners g_SideVertCorners[4] =
{
	{ {1,-1},  {1,1} },
	{ {1,1},   {-1,1} },
	{ {-1,1},  {-1,-1} },
	{ {-1,-1}, {1,-1} }
};

// This is used in loops on child nodes. The indices point at the nodes:
// 0 = upper-right
// 1 = upper-left
// 2 = lower-left
// 3 = lower-right
static CVertIndex g_ChildNodeIndexMul[4] = 
{ 
	CVertIndex(1,1), 
	CVertIndex(-1,1), 
	CVertIndex(-1,-1), 
	CVertIndex(1,-1)
};

// These are multipliers on vertMul (not nodeMul).
static CVertIndex g_ChildNodeDependencies[4][2] =
{
	{ CVertIndex(1,0),  CVertIndex(0,1) },
	{ CVertIndex(0,1),  CVertIndex(-1,0) },
	{ CVertIndex(-1,0), CVertIndex(0,-1) },
	{ CVertIndex(0,-1), CVertIndex(1,0) }
};

// 2x2 rotation matrices for each orientation.
static int g_OrientationRotations[4][2][2] =
{
	{{1, 0},		// CCW_0
	{0, 1}},

	{{0, 1},		// CCW_90
	{-1,0}},

	{{-1,0},		// CCW_180
	{0,-1}},

	{{0, -1},		// CCW_270
	{1, 0}}
};	   


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

// Apply a 2D rotation to the specified CVertIndex around the specified centerpoint.
static CVertIndex Transform2D(
	int const mat[2][2],
	CVertIndex const &vert,
	CVertIndex const &centerPoint )
{
	CVertIndex translated = vert - centerPoint;
	
	CVertIndex transformed(
		translated.x*mat[0][0] + translated.y*mat[0][1],
		translated.x*mat[1][0] + translated.y*mat[1][1] );
	
	return transformed + centerPoint;
}


// Rotate a given CVertIndex with a specified orientation.
// Do this with a lookup table eventually!
static void GetEdgeVertIndex( int sideLength, int iEdge, int iVert, CVertIndex &out )
{
	if( iEdge == NEIGHBOREDGE_RIGHT )
	{
		out.x = sideLength - 1;
		out.y = iVert;
	}
	else if( iEdge == NEIGHBOREDGE_TOP )
	{
		out.x = iVert;
		out.y = sideLength - 1;
	}
	else if( iEdge == NEIGHBOREDGE_LEFT )
	{
		out.x = 0;
		out.y = iVert;
	}
	else
	{
		out.x = iVert;
		out.y = 0;
	}
}


// Generate an index given a CVertIndex and the size of the displacement it resides in.
static int VertIndex( CVertIndex const &vert, int iMaxPower )
{
	return vert.y * ((1 << iMaxPower) + 1) + vert.x;
}
 

static CVertIndex WrapVertIndex( CVertIndex const &in, int sideLength )
{
	int out[2];

	for( int i=0; i < 2; i++ )
	{
		if( in[i] < 0 )
			out[i] = sideLength - 1 - (-in[i] % sideLength);
		else if( in[i] >= sideLength )
			out[i] = in[i] % sideLength;
		else
			out[i] = in[i];
	}

	return CVertIndex( out[0], out[1] );
}


static int GetFreeDependency( CVertDependency *pDep, int nElements )
{
	for( int i=0; i < nElements; i++ )
	{
		if( !pDep[i].IsValid() ) 
			return i;
	}

	Assert( false );
	return 0;
}


static void AddDependency( 
	CVertInfo *dependencies, 
	int sideLength,
	CVertIndex const &nodeIndex,
	CVertIndex const &dependency,
	int iMaxPower,
	bool bCheckNeighborDependency,
	bool bAddReverseDependency )
{
	int iNodeIndex = VertIndex( nodeIndex, iMaxPower );
	CVertInfo *pNode = &dependencies[iNodeIndex];

	int iDep = GetFreeDependency( pNode->m_Dependencies, sizeof(pNode->m_Dependencies)/sizeof(pNode->m_Dependencies[0]) );
	pNode->m_Dependencies[iDep].m_iVert = dependency;
	pNode->m_Dependencies[iDep].m_iNeighbor = -1;

	if( bAddReverseDependency )
	{
		CVertInfo *pDep = &dependencies[VertIndex( dependency, iMaxPower )];
		iDep = GetFreeDependency( pDep->m_ReverseDependencies, CVertInfo::NUM_REVERSE_DEPENDENCIES );
		pDep->m_ReverseDependencies[iDep].m_iVert = nodeIndex;
		pDep->m_ReverseDependencies[iDep].m_iNeighbor = -1;
	}

	// Edge verts automatically add a dependency for the neighbor.
	// Internal verts wind up in here twice anyway so it doesn't need to 
	if( bCheckNeighborDependency )
	{
		int iConnection = GetEdgeIndexFromPoint( nodeIndex, iMaxPower );
		if( iConnection != -1 )
		{
			Assert( !pNode->m_Dependencies[1].IsValid() );

			CVertIndex delta( nodeIndex.x - dependency.x, nodeIndex.y - dependency.y );
			CVertIndex newIndex( nodeIndex.x + delta.x, nodeIndex.y + delta.y );
			
			int fullSideLength = (1 << iMaxPower) + 1;
			pNode->m_Dependencies[1].m_iVert = WrapVertIndex( CVertIndex( newIndex.x, newIndex.y ), fullSideLength );
			pNode->m_Dependencies[1].m_iNeighbor = iConnection;
		}
	}
}


// --------------------------------------------------------------------------------- //
// CTesselateWinding stuff.
// --------------------------------------------------------------------------------- //

CTesselateVert::CTesselateVert( CVertIndex const &index, int iNode )
	: m_Index( index )
{
	m_iNode = iNode;
}


CVertInfo::CVertInfo()
{
	int i;
	for( i=0; i < sizeof(m_Dependencies)/sizeof(m_Dependencies[0]); i++ )
	{
		m_Dependencies[i].m_iVert = CVertIndex( -1, -1 );
		m_Dependencies[i].m_iNeighbor = -1;
	}

	for( i=0; i < sizeof(m_ReverseDependencies)/sizeof(m_ReverseDependencies[0]); i++ )
	{
		m_ReverseDependencies[i].m_iVert = CVertIndex( -1, -1 );
		m_ReverseDependencies[i].m_iNeighbor = -1;
	}
	
	m_iParent.x = m_iParent.y = -1;
	m_iNodeLevel = -1;
}


CTesselateVert g_TesselateVerts[] =
{
	CTesselateVert( CVertIndex(1,-1),  CHILDNODE_LOWER_RIGHT),
	CTesselateVert( CVertIndex(0,-1),  -1),
	CTesselateVert( CVertIndex(-1,-1), CHILDNODE_LOWER_LEFT),
	CTesselateVert( CVertIndex(-1, 0), -1),
	CTesselateVert( CVertIndex(-1, 1), CHILDNODE_UPPER_LEFT),
	CTesselateVert( CVertIndex(0, 1),  -1),
	CTesselateVert( CVertIndex(1, 1),  CHILDNODE_UPPER_RIGHT),
	CTesselateVert( CVertIndex(1, 0),  -1),
	CTesselateVert( CVertIndex(1,-1),  CHILDNODE_LOWER_RIGHT)
};

CTesselateWinding g_TWinding =
{
	g_TesselateVerts,
	sizeof( g_TesselateVerts ) / sizeof( g_TesselateVerts[0] )
};



// --------------------------------------------------------------------------------- //
// CPowerInfo stuff.
// --------------------------------------------------------------------------------- //

// Precalculated info about each particular displacement size.
#define DECLARE_TABLES( size ) \
	static CVertInfo	g_VertInfo_##size##x##size[ size*size ];				\
	static CFourVerts	g_SideVerts_##size##x##size[ size*size ];				\
	static CFourVerts	g_ChildVerts_##size##x##size[ size*size ];			\
	static CFourVerts	g_SideVertCorners_##size##x##size[ size*size ];	\
	static CTwoUShorts	g_ErrorEdges_##size##x##size[ size*size ];			\
	static CTriInfo		g_TriInfos_##size##x##size[ (size-1)*(size-1)*2 ];	\
	static CPowerInfo	g_PowerInfo_##size##x##size(							\
		g_VertInfo_##size##x##size,		\
		g_SideVerts_##size##x##size,		\
		g_ChildVerts_##size##x##size,		\
		g_SideVertCorners_##size##x##size,\
		g_ErrorEdges_##size##x##size,		\
		g_TriInfos_##size##x##size		\
	)

#define POWERINFO_ENTRY( size )	\
	(&g_PowerInfo_##size##x##size)

DECLARE_TABLES( 5 );	
DECLARE_TABLES( 9 );	
DECLARE_TABLES( 17 );	


// Index by m_Power.
CPowerInfo *g_PowerInfos[NUM_POWERINFOS] =
{
	NULL,
	NULL,
	POWERINFO_ENTRY(5),
	POWERINFO_ENTRY(9),
	POWERINFO_ENTRY(17)
};


CPowerInfo::CPowerInfo( 
	CVertInfo *pVertInfo, 
	CFourVerts *pSideVerts,
	CFourVerts *pChildVerts,
	CFourVerts *pSideVertCorners,
	CTwoUShorts *pErrorEdges,
	CTriInfo *pTriInfos )
{
	m_pVertInfo = pVertInfo;
	m_pSideVerts = pSideVerts;
	m_pChildVerts = pChildVerts;
	m_pSideVertCorners = pSideVertCorners;
	m_pErrorEdges = pErrorEdges;
	m_pTriInfos = pTriInfos;
}

static void InitPowerInfoTriInfos_R( 
	CPowerInfo *pInfo,
	CVertIndex const &nodeIndex,
	CTriInfo* &pTriInfo,
	int iMaxPower,
	int iLevel )
{
	int iNodeIndex = VertIndex( nodeIndex, iMaxPower );

	if( iLevel+1 < iMaxPower )
	{
		// Recurse into children.
		for( int iChild=0; iChild < 4; iChild++ )
		{
			InitPowerInfoTriInfos_R(
				pInfo,
				pInfo->m_pChildVerts[iNodeIndex].m_Verts[iChild],
				pTriInfo,
				iMaxPower,
				iLevel+1 );
		}
	}
	else
	{
		unsigned short indices[3];
		
		int vertInc = 1 << ((iMaxPower - iLevel) - 1);

		// We're at a leaf, generate the tris.
		CTesselateWinding *pWinding = &g_TWinding;

		// Starting at the bottom-left, wind clockwise picking up vertices and
		// generating triangles.
		int iCurTriVert = 0;
		for( int iVert=0; iVert < pWinding->m_nVerts; iVert++ )
		{
			CVertIndex sideVert  = BuildOffsetVertIndex( nodeIndex, pWinding->m_Verts[iVert].m_Index, vertInc );
			
			if( iCurTriVert == 1 )
			{
				// Add this vert and finish the tri.
				pTriInfo->m_Indices[0] = indices[0];
				pTriInfo->m_Indices[1] = VertIndex( sideVert, iMaxPower );
				pTriInfo->m_Indices[2] = iNodeIndex;
				++pTriInfo;
			}

			indices[0] = VertIndex( sideVert, iMaxPower );
			iCurTriVert = 1;
		}
	}
}	


static void InitPowerInfo_R( 
	CPowerInfo *pPowerInfo, 
	int iMaxPower, 
	CVertIndex const &nodeIndex,
	CVertIndex const &dependency1,
	CVertIndex const &dependency2,
	CVertIndex const &nodeEdge1, 
	CVertIndex const &nodeEdge2, 
	CVertIndex const &iParent,
	int iLevel )
{
	int sideLength = ((1 << iMaxPower) + 1);
	int iNodeIndex = VertIndex( nodeIndex, iMaxPower );
	
	pPowerInfo->m_pVertInfo[iNodeIndex].m_iParent = iParent;
	pPowerInfo->m_pVertInfo[iNodeIndex].m_iNodeLevel = iLevel + 1;

	pPowerInfo->m_pErrorEdges[iNodeIndex].m_Values[0] = (unsigned short)(VertIndex( nodeEdge1, iMaxPower ));
	pPowerInfo->m_pErrorEdges[iNodeIndex].m_Values[1] = (unsigned short)(VertIndex( nodeEdge2, iMaxPower ));
	
	// Add this node's dependencies.
	AddDependency( pPowerInfo->m_pVertInfo, sideLength, nodeIndex, dependency1, iMaxPower, false, true );
	AddDependency( pPowerInfo->m_pVertInfo, sideLength, nodeIndex, dependency2, iMaxPower, false, true );

	// The 4 side vertices depend on this node.
	int iPower = iMaxPower - iLevel;
	int vertInc = 1 << (iPower - 1);

	for( int iSide=0; iSide < 4; iSide++ )
	{
		// Store the side vert index.
		CVertIndex sideVert( nodeIndex.x + g_SideVertMul[iSide][0]*vertInc, nodeIndex.y + g_SideVertMul[iSide][1]*vertInc );
		int iSideVert = VertIndex( sideVert, iMaxPower );

		pPowerInfo->m_pSideVerts[iNodeIndex].m_Verts[iSide] = sideVert;

		// Store the side vert corners.		
		CVertIndex sideVertCorner0 = CVertIndex( nodeIndex.x + g_SideVertCorners[iSide].m_Corner1[0]*vertInc, nodeIndex.y + g_SideVertCorners[iSide].m_Corner1[1]*vertInc );
		CVertIndex sideVertCorner1 = CVertIndex( nodeIndex.x + g_SideVertCorners[iSide].m_Corner2[0]*vertInc, nodeIndex.y + g_SideVertCorners[iSide].m_Corner2[1]*vertInc );

		pPowerInfo->m_pSideVertCorners[iNodeIndex].m_Verts[iSide] = sideVertCorner0;

		// Write the side vert corners into the error-edges list.
		pPowerInfo->m_pErrorEdges[iSideVert].m_Values[0] = (unsigned short)VertIndex( sideVertCorner0, iMaxPower );
		pPowerInfo->m_pErrorEdges[iSideVert].m_Values[1] = (unsigned short)VertIndex( sideVertCorner1, iMaxPower );

		AddDependency( 
			pPowerInfo->m_pVertInfo, 
			sideLength, 
			sideVert, 
			nodeIndex, 
			iMaxPower, 
			true, 
			true );
	}

	// Recurse into the children.
	int nodeInc = vertInc >> 1;
	if( nodeInc )
	{
		for( int iChild=0; iChild < 4; iChild++ )
		{
			CVertIndex childVert( nodeIndex.x + g_ChildNodeIndexMul[iChild].x * nodeInc, nodeIndex.y + g_ChildNodeIndexMul[iChild].y * nodeInc );

			pPowerInfo->m_pChildVerts[iNodeIndex].m_Verts[iChild] = childVert;

			InitPowerInfo_R( pPowerInfo, 
				iMaxPower,
				childVert,
				
				CVertIndex(nodeIndex.x + g_ChildNodeDependencies[iChild][0].x*vertInc, nodeIndex.y + g_ChildNodeDependencies[iChild][0].y*vertInc),
				CVertIndex(nodeIndex.x + g_ChildNodeDependencies[iChild][1].x*vertInc, nodeIndex.y + g_ChildNodeDependencies[iChild][1].y*vertInc),
				
				nodeIndex,
				CVertIndex( nodeIndex.x + g_ChildNodeIndexMul[iChild].x * vertInc, nodeIndex.y + g_ChildNodeIndexMul[iChild].y * vertInc ),
				
				nodeIndex,
				iLevel + 1 );
		}
	}
}


void InitPowerInfo( CPowerInfo *pInfo, int iMaxPower )
{
	int sideLength = (1 << iMaxPower) + 1;

	// Precalculate the dependency graph.
	CVertIndex nodeDependency1( sideLength-1, sideLength-1 );
	CVertIndex nodeDependency2( 0, 0 );

	pInfo->m_RootNode = CVertIndex( sideLength/2, sideLength/2 );
	pInfo->m_SideLength = sideLength;
	pInfo->m_SideLengthM1 = sideLength - 1;
	pInfo->m_MidPoint = sideLength / 2;
	pInfo->m_MaxVerts = sideLength * sideLength;

	// Setup the corner indices.
	pInfo->m_CornerPointIndices[CORNER_LOWER_LEFT].Init( 0, 0 );
	pInfo->m_CornerPointIndices[CORNER_UPPER_LEFT].Init( 0, sideLength-1 );
	pInfo->m_CornerPointIndices[CORNER_UPPER_RIGHT].Init( sideLength-1, sideLength-1 );
	pInfo->m_CornerPointIndices[CORNER_LOWER_RIGHT].Init( sideLength-1, 0 );
	
	InitPowerInfo_R( 
		pInfo, 
		iMaxPower, 
		pInfo->m_RootNode, 
		
		nodeDependency1,							// dependencies
		nodeDependency2, 
		
		CVertIndex(0,0),							// error edge
		CVertIndex(sideLength-1, sideLength-1),		
		
		CVertIndex(-1,-1),							// parent
		0 );

	pInfo->m_Power = iMaxPower;
	
	CTriInfo *pTriInfo = pInfo->m_pTriInfos;
	InitPowerInfoTriInfos_R( pInfo, pInfo->m_RootNode, pTriInfo, iMaxPower, 0 );

	for( int iEdge=0; iEdge < 4; iEdge++ )
	{
		// Figure out the start vert and increment.
		CVertIndex nextVert;
		GetEdgeVertIndex( sideLength, iEdge, 0, pInfo->m_EdgeStartVerts[iEdge] );
		GetEdgeVertIndex( sideLength, iEdge, 1, nextVert );
		pInfo->m_EdgeIncrements[iEdge] = nextVert - pInfo->m_EdgeStartVerts[iEdge];

		// Now get the neighbor's start vert and increment.
		CVertIndex nbStartVert, nbNextVert, nbDelta;
		GetEdgeVertIndex( sideLength, (iEdge+2)&3, 0, nbStartVert );
		GetEdgeVertIndex( sideLength, (iEdge+2)&3, 1, nbNextVert );
		nbDelta = nbNextVert - nbStartVert;

		// Rotate it for each orientation.
		for( int orient=0; orient < 4; orient++ )
		{
			pInfo->m_NeighborStartVerts[iEdge][orient] = Transform2D( 
				g_OrientationRotations[orient], 
				nbStartVert, 
				CVertIndex( sideLength/2, sideLength/2 ) );

			pInfo->m_NeighborIncrements[iEdge][orient] = Transform2D( 
				g_OrientationRotations[orient],
				nbDelta,
				CVertIndex(0,0) );				 
		}
	}


	// Init the node index increments.
	int curPowerOf4 = 1;
	int curTotal = 0;
	for( int i=0; i < iMaxPower-1; i++ )
	{
		curTotal += curPowerOf4;

		pInfo->m_NodeIndexIncrements[iMaxPower-i-2] = curTotal;

		curPowerOf4 *= 4;		
	}

	// Store off the total node count
	pInfo->m_NodeCount = curTotal + curPowerOf4;

	pInfo->m_nTriInfos = Square( 1 << iMaxPower ) * 2;
}

class CPowerInfoInitializer
{
public:
	CPowerInfoInitializer()
	{
		Assert( MAX_MAP_DISP_POWER+1 == NUM_POWERINFOS );

		for( int i=0; i <= MAX_MAP_DISP_POWER; i++ )
		{
			if( g_PowerInfos[i] )
			{
				InitPowerInfo( g_PowerInfos[i], i );
			}
		}
	}
};

static CPowerInfoInitializer g_PowerInfoInitializer;


const CPowerInfo* GetPowerInfo( int iPower )
{
	Assert( iPower >= 0 && iPower < ARRAYSIZE( g_PowerInfos ) );
	Assert( g_PowerInfos[iPower] );
	return g_PowerInfos[iPower];
}


// ------------------------------------------------------------------------------------------------ //
// CPowerInfo member function initialization.
// ------------------------------------------------------------------------------------------------ //

const CVertIndex& CPowerInfo::GetCornerPointIndex( int iCorner ) const
{
	Assert( iCorner >= 0 && iCorner < 4 );
	return m_CornerPointIndices[iCorner];
}