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