Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
581 lines (468 sloc) 15.7 KB
//========= 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];
}