//========= 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<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 &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 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 &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 ); }