From f56bb35301836e56582a575a75864392a0177875 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B8rgen=20P=2E=20Tjern=C3=B8?= Date: Mon, 2 Dec 2013 19:31:46 -0800 Subject: Fix line endings. WHAMMY. --- mp/src/public/dispcoll_common.cpp | 3078 ++++++++++++++++++------------------- 1 file changed, 1539 insertions(+), 1539 deletions(-) (limited to 'mp/src/public/dispcoll_common.cpp') diff --git a/mp/src/public/dispcoll_common.cpp b/mp/src/public/dispcoll_common.cpp index d3ecbd7c..9131d4c1 100644 --- a/mp/src/public/dispcoll_common.cpp +++ b/mp/src/public/dispcoll_common.cpp @@ -1,1539 +1,1539 @@ -//========= Copyright Valve Corporation, All rights reserved. ============// -// -// Purpose: -// -// $NoKeywords: $ -//=============================================================================// - -#include "cmodel.h" -#include "dispcoll_common.h" -#include "collisionutils.h" -#include "tier1/strtools.h" -#include "tier0/vprof.h" -#include "tier1/fmtstr.h" -#include "tier1/utlhash.h" -#include "tier1/generichash.h" -#include "tier0/fasttimer.h" -#include "vphysics/virtualmesh.h" -#include "tier1/datamanager.h" -// memdbgon must be the last include file in a .cpp file!!! -#include "tier0/memdbgon.h" - -//============================================================================= -// Cache - -#ifdef ENGINE_DLL -CDataManager g_DispCollTriCache( 2048*1024 ); -#endif - - -struct DispCollPlaneIndex_t -{ - Vector vecPlane; - int index; -}; - -class CPlaneIndexHashFuncs -{ -public: - CPlaneIndexHashFuncs( int ) {} - - // Compare - bool operator()( const DispCollPlaneIndex_t &lhs, const DispCollPlaneIndex_t &rhs ) const - { - return ( lhs.vecPlane == rhs.vecPlane || lhs.vecPlane == -rhs.vecPlane ); - } - - // Hash - unsigned int operator()( const DispCollPlaneIndex_t &item ) const - { - return HashItem( item.vecPlane ) ^ HashItem( -item.vecPlane ); - } -}; - -CUtlHash g_DispCollPlaneIndexHash( 512 ); - - -//============================================================================= -// Displacement Collision Triangle - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -CDispCollTri::CDispCollTri() -{ - Init(); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTri::Init( void ) -{ - m_vecNormal.Init(); - m_flDist = 0.0f; - m_TriData[0].m_IndexDummy = m_TriData[1].m_IndexDummy = m_TriData[2].m_IndexDummy = 0; -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTri::CalcPlane( CDispVector &m_aVerts ) -{ - Vector vecEdges[2]; - vecEdges[0] = m_aVerts[GetVert( 1 )] - m_aVerts[GetVert( 0 )]; - vecEdges[1] = m_aVerts[GetVert( 2 )] - m_aVerts[GetVert( 0 )]; - - m_vecNormal = vecEdges[1].Cross( vecEdges[0] ); - VectorNormalize( m_vecNormal ); - m_flDist = m_vecNormal.Dot( m_aVerts[GetVert( 0 )] ); - - // Calculate the signbits for the plane - fast test. - m_ucSignBits = 0; - m_ucPlaneType = PLANE_ANYZ; - for ( int iAxis = 0; iAxis < 3 ; ++iAxis ) - { - if ( m_vecNormal[iAxis] < 0.0f ) - { - m_ucSignBits |= 1 << iAxis; - } - - if ( m_vecNormal[iAxis] == 1.0f ) - { - m_ucPlaneType = iAxis; - } - } -} - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -inline void FindMin( float v1, float v2, float v3, int &iMin ) -{ - float flMin = v1; - iMin = 0; - if( v2 < flMin ) { flMin = v2; iMin = 1; } - if( v3 < flMin ) { flMin = v3; iMin = 2; } -} - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -inline void FindMax( float v1, float v2, float v3, int &iMax ) -{ - float flMax = v1; - iMax = 0; - if( v2 > flMax ) { flMax = v2; iMax = 1; } - if( v3 > flMax ) { flMax = v3; iMax = 2; } -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTri::FindMinMax( CDispVector &m_aVerts ) -{ - int iMin, iMax; - FindMin( m_aVerts[GetVert(0)].x, m_aVerts[GetVert(1)].x, m_aVerts[GetVert(2)].x, iMin ); - FindMax( m_aVerts[GetVert(0)].x, m_aVerts[GetVert(1)].x, m_aVerts[GetVert(2)].x, iMax ); - SetMin( 0, iMin ); - SetMax( 0, iMax ); - - FindMin( m_aVerts[GetVert(0)].y, m_aVerts[GetVert(1)].y, m_aVerts[GetVert(2)].y, iMin ); - FindMax( m_aVerts[GetVert(0)].y, m_aVerts[GetVert(1)].y, m_aVerts[GetVert(2)].y, iMax ); - SetMin( 1, iMin ); - SetMax( 1, iMax ); - - FindMin( m_aVerts[GetVert(0)].z, m_aVerts[GetVert(1)].z, m_aVerts[GetVert(2)].z, iMin ); - FindMax( m_aVerts[GetVert(0)].z, m_aVerts[GetVert(1)].z, m_aVerts[GetVert(2)].z, iMax ); - SetMin( 2, iMin ); - SetMax( 2, iMax ); -} - - -// SIMD Routines for intersecting with the quad tree -FORCEINLINE int IntersectRayWithFourBoxes( const FourVectors &rayStart, const FourVectors &invDelta, const FourVectors &rayExtents, const FourVectors &boxMins, const FourVectors &boxMaxs ) -{ - // SIMD Test ray against all four boxes at once - // each node stores the bboxes of its four children - FourVectors hitMins = boxMins; - hitMins -= rayStart; - FourVectors hitMaxs = boxMaxs; - hitMaxs -= rayStart; - - // adjust for swept box by enlarging the child bounds to shrink the sweep down to a point - hitMins -= rayExtents; - hitMaxs += rayExtents; - - // compute the parametric distance along the ray of intersection in each dimension - hitMins *= invDelta; - hitMaxs *= invDelta; - - // Find the exit parametric intersection distance in each dimesion, for each box - FourVectors exitT = maximum(hitMins,hitMaxs); - // Find the entry parametric intersection distance in each dimesion, for each box - FourVectors entryT = minimum(hitMins,hitMaxs); - - // now find the max overall entry distance across all dimensions for each box - fltx4 minTemp = MaxSIMD(entryT.x, entryT.y); - fltx4 boxEntryT = MaxSIMD(minTemp, entryT.z); - - // now find the min overall exit distance across all dimensions for each box - fltx4 maxTemp = MinSIMD(exitT.x, exitT.y); - fltx4 boxExitT = MinSIMD(maxTemp, exitT.z); - - boxEntryT = MaxSIMD(boxEntryT,Four_Zeros); - boxExitT = MinSIMD(boxExitT,Four_Ones); - - // if entry<=exit for the box, we've got a hit - fltx4 active = CmpLeSIMD(boxEntryT,boxExitT); // mask of which boxes are active - - // hit at least one box? - return TestSignSIMD(active); -} - -// This does 4 simultaneous box intersections -// NOTE: This can be used as a 1 vs 4 test by replicating a single box into the one side -FORCEINLINE int IntersectFourBoxPairs( const FourVectors &mins0, const FourVectors &maxs0, const FourVectors &mins1, const FourVectors &maxs1 ) -{ - // find the max mins and min maxs in each dimension - FourVectors intersectMins = maximum(mins0,mins1); - FourVectors intersectMaxs = minimum(maxs0,maxs1); - - // if intersectMins <= intersectMaxs then the boxes overlap in this dimension - fltx4 overlapX = CmpLeSIMD(intersectMins.x,intersectMaxs.x); - fltx4 overlapY = CmpLeSIMD(intersectMins.y,intersectMaxs.y); - fltx4 overlapZ = CmpLeSIMD(intersectMins.z,intersectMaxs.z); - - // if the boxes overlap in all three dimensions, they intersect - fltx4 tmp = AndSIMD( overlapX, overlapY ); - fltx4 active = AndSIMD( tmp, overlapZ ); - - // hit at least one box? - return TestSignSIMD(active); -} - -// This does 4 simultaneous box vs. sphere intersections -// NOTE: This can be used as a 1 vs 4 test by replicating a single sphere/box into one side -FORCEINLINE int IntersectFourBoxSpherePairs( const FourVectors ¢er, const fltx4 &radiusSq, const FourVectors &mins, const FourVectors &maxs ) -{ - // for each dimension of each box, compute the clamped distance from the mins side to the center (must be >= 0) - FourVectors minDist = mins; - minDist -= center; - FourVectors dist; - dist.x = MaxSIMD(Four_Zeros, minDist.x); - dist.y = MaxSIMD(Four_Zeros, minDist.y); - dist.z = MaxSIMD(Four_Zeros, minDist.z); - - // now compute the distance from the maxs side to the center - FourVectors maxDist = center; - maxDist -= maxs; - // NOTE: Don't need to clamp here because we clamp against the minDist which must be >= 0, so the two clamps - // get folded together - FourVectors totalDist; - totalDist.x = MaxSIMD(dist.x, maxDist.x); - totalDist.y = MaxSIMD(dist.y, maxDist.y); - totalDist.z = MaxSIMD(dist.z, maxDist.z); - // get the total squred distance between each box & sphere center by summing the squares of each - // component/dimension - fltx4 distSq = totalDist * totalDist; - - // if squared distance between each sphere center & box is less than the radiusSquared for that sphere - // we have an intersection - fltx4 active = CmpLeSIMD(distSq,radiusSq); - - // at least one intersection? - return TestSignSIMD(active); -} - - -int FORCEINLINE CDispCollTree::BuildRayLeafList( int iNode, rayleaflist_t &list ) -{ - list.nodeList[0] = iNode; - int listIndex = 0; - list.maxIndex = 0; - while ( listIndex <= list.maxIndex ) - { - iNode = list.nodeList[listIndex]; - // the rest are all leaves - if ( IsLeafNode(iNode) ) - return listIndex; - listIndex++; - const CDispCollNode &node = m_nodes[iNode]; - int mask = IntersectRayWithFourBoxes( list.rayStart, list.invDelta, list.rayExtents, node.m_mins, node.m_maxs ); - if ( mask ) - { - int child = Nodes_GetChild( iNode, 0 ); - if ( mask & 1 ) - { - ++list.maxIndex; - list.nodeList[list.maxIndex] = child; - } - if ( mask & 2 ) - { - ++list.maxIndex; - list.nodeList[list.maxIndex] = child+1; - } - if ( mask & 4 ) - { - ++list.maxIndex; - list.nodeList[list.maxIndex] = child+2; - } - if ( mask & 8 ) - { - ++list.maxIndex; - list.nodeList[list.maxIndex] = child+3; - } - Assert(list.maxIndex < MAX_AABB_LIST); - } - } - - return listIndex; -} - - -//----------------------------------------------------------------------------- -// Purpose: Create the AABB tree. -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBTree_Create( CCoreDispInfo *pDisp ) -{ - // Copy the flags. - m_nFlags = pDisp->GetSurface()->GetFlags(); - - // Copy necessary displacement data. - AABBTree_CopyDispData( pDisp ); - - // Setup/create the leaf nodes first so the recusion can use this data to stop. - AABBTree_CreateLeafs(); - - // Create the bounding box of the displacement surface + the base face. - AABBTree_CalcBounds(); - - // Successful. - return true; -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::AABBTree_CopyDispData( CCoreDispInfo *pDisp ) -{ - // Displacement size. - m_nPower = pDisp->GetPower(); - - // Displacement base surface data. - CCoreDispSurface *pSurf = pDisp->GetSurface(); - m_nContents = pSurf->GetContents(); - pSurf->GetNormal( m_vecStabDir ); - for ( int iPoint = 0; iPoint < 4; iPoint++ ) - { - pSurf->GetPoint( iPoint, m_vecSurfPoints[iPoint] ); - } - - // Allocate collision tree data. - { - MEM_ALLOC_CREDIT(); - m_aVerts.SetSize( GetSize() ); - } - - { - MEM_ALLOC_CREDIT(); - m_aTris.SetSize( GetTriSize() ); - } - - { - MEM_ALLOC_CREDIT(); - int numLeaves = (GetWidth()-1) * (GetHeight()-1); - m_leaves.SetCount(numLeaves); - int numNodes = Nodes_CalcCount( m_nPower ); - numNodes -= numLeaves; - m_nodes.SetCount(numNodes); - } - - - // Setup size. - m_nSize = sizeof( this ); - m_nSize += sizeof( Vector ) * GetSize(); - m_nSize += sizeof( CDispCollTri ) * GetTriSize(); -#if OLD_DISP_AABB - m_nSize += sizeof( CDispCollAABBNode ) * Nodes_CalcCount( m_nPower ); -#endif - m_nSize += sizeof(m_nodes[0]) * m_nodes.Count(); - m_nSize += sizeof(m_leaves[0]) * m_leaves.Count(); - m_nSize += sizeof( CDispCollTri* ) * DISPCOLL_TREETRI_SIZE; - - // Copy vertex data. - for ( int iVert = 0; iVert < m_aVerts.Count(); iVert++ ) - { - pDisp->GetVert( iVert, m_aVerts[iVert] ); - } - - // Copy and setup triangle data. - unsigned short iVerts[3]; - for ( int iTri = 0; iTri < m_aTris.Count(); ++iTri ) - { - pDisp->GetTriIndices( iTri, iVerts[0], iVerts[1], iVerts[2] ); - m_aTris[iTri].SetVert( 0, iVerts[0] ); - m_aTris[iTri].SetVert( 1, iVerts[1] ); - m_aTris[iTri].SetVert( 2, iVerts[2] ); - m_aTris[iTri].m_uiFlags = pDisp->GetTriTagValue( iTri ); - - // Calculate the surface props and set flags. - float flTotalAlpha = 0.0f; - for ( int iVert = 0; iVert < 3; ++iVert ) - { - flTotalAlpha += pDisp->GetAlpha( m_aTris[iTri].GetVert( iVert ) ); - } - - if ( flTotalAlpha > DISP_ALPHA_PROP_DELTA ) - { - m_aTris[iTri].m_uiFlags |= DISPSURF_FLAG_SURFPROP2; - } - else - { - m_aTris[iTri].m_uiFlags |= DISPSURF_FLAG_SURFPROP1; - } - - // Add the displacement surface flag. - m_aTris[iTri].m_uiFlags |= DISPSURF_FLAG_SURFACE; - - // Calculate the plane normal and the min max. - m_aTris[iTri].CalcPlane( m_aVerts ); - m_aTris[iTri].FindMinMax( m_aVerts ); - } -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::AABBTree_CreateLeafs( void ) -{ - int numLeaves = (GetWidth()-1) * (GetHeight()-1); - m_leaves.SetCount(numLeaves); - int numNodes = Nodes_CalcCount( m_nPower ); - numNodes -= numLeaves; - m_nodes.SetCount(numNodes); - - // Get the width and height of the displacement. - int nWidth = GetWidth() - 1; - int nHeight = GetHeight() - 1; - - for ( int iHgt = 0; iHgt < nHeight; ++iHgt ) - { - for ( int iWid = 0; iWid < nWidth; ++iWid ) - { - int iLeaf = Nodes_GetIndexFromComponents( iWid, iHgt ); - int iIndex = iHgt * nWidth + iWid; - int iTri = iIndex * 2; - - m_leaves[iLeaf].m_tris[0] = iTri; - m_leaves[iLeaf].m_tris[1] = iTri + 1; - } - } -} - -void CDispCollTree::AABBTree_GenerateBoxes_r( int nodeIndex, Vector *pMins, Vector *pMaxs ) -{ - // leaf - ClearBounds( *pMins, *pMaxs ); - if ( nodeIndex >= m_nodes.Count() ) - { - int iLeaf = nodeIndex - m_nodes.Count(); - - for ( int iTri = 0; iTri < 2; ++iTri ) - { - int triIndex = m_leaves[iLeaf].m_tris[iTri]; - const CDispCollTri &tri = m_aTris[triIndex]; - AddPointToBounds( m_aVerts[tri.GetVert( 0 )], *pMins, *pMaxs ); - AddPointToBounds( m_aVerts[tri.GetVert( 1 )], *pMins, *pMaxs ); - AddPointToBounds( m_aVerts[tri.GetVert( 2 )], *pMins, *pMaxs ); - } - } - else // node - { - Vector childMins[4], childMaxs[4]; - for ( int i = 0; i < 4; i++ ) - { - int child = Nodes_GetChild( nodeIndex, i ); - AABBTree_GenerateBoxes_r( child, &childMins[i], &childMaxs[i] ); - AddPointToBounds( childMins[i], *pMins, *pMaxs ); - AddPointToBounds( childMaxs[i], *pMins, *pMaxs ); - } - m_nodes[nodeIndex].m_mins.LoadAndSwizzle( childMins[0], childMins[1], childMins[2], childMins[3] ); - m_nodes[nodeIndex].m_maxs.LoadAndSwizzle( childMaxs[0], childMaxs[1], childMaxs[2], childMaxs[3] ); - } -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::AABBTree_CalcBounds( void ) -{ - // Check data. - if ( ( m_aVerts.Count() == 0 ) || ( m_nodes.Count() == 0 ) ) - return; - - AABBTree_GenerateBoxes_r( 0, &m_mins, &m_maxs ); - -#if INCLUDE_SURFACE_IN_BOUNDS - // Add surface points to bounds. - for ( int iPoint = 0; iPoint < 4; ++iPoint ) - { - VectorMin( m_vecSurfPoints[iPoint], m_mins, m_mins ); - VectorMax( m_vecSurfPoints[iPoint], m_maxs, m_maxs ); - } -#endif - - // Bloat a little. - for ( int iAxis = 0; iAxis < 3; ++iAxis ) - { - m_mins[iAxis] -= 1.0f; - m_maxs[iAxis] += 1.0f; - } -} - -static CThreadFastMutex s_CacheMutex; -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline void CDispCollTree::LockCache() -{ -#ifdef ENGINE_DLL - if ( !g_DispCollTriCache.LockResource( m_hCache ) ) - { - AUTO_LOCK_FM( s_CacheMutex ); - - // Cache may have just been created, so check once more - if ( !g_DispCollTriCache.LockResource( m_hCache ) ) - { - Cache(); - m_hCache = g_DispCollTriCache.CreateResource( this ); - g_DispCollTriCache.LockResource( m_hCache ); - //Msg( "Adding 0x%x to cache (actual %d) [%d, %d --> %.2f] %d total, %d unique\n", this, GetCacheMemorySize(), GetTriSize(), m_aEdgePlanes.Count(), (float)m_aEdgePlanes.Count()/(float)GetTriSize(), totals, uniques ); - } - } -#else - Cache(); -#endif -} - -inline void CDispCollTree::UnlockCache() -{ -#ifdef ENGINE_DLL - g_DispCollTriCache.UnlockResource( m_hCache ); -#endif -} -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::Cache( void ) -{ - if ( m_aTrisCache.Count() == GetTriSize() ) - { - return; - } - - VPROF( "CDispCollTree::Cache" ); - - // Alloc. -// int nSize = sizeof( CDispCollTriCache ) * GetTriSize(); - int nTriCount = GetTriSize(); - { - MEM_ALLOC_CREDIT(); - m_aTrisCache.SetSize( nTriCount ); - } - - for ( int iTri = 0; iTri < nTriCount; ++iTri ) - { - Cache_Create( &m_aTris[iTri], iTri ); - } - - g_DispCollPlaneIndexHash.Purge(); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBTree_Ray( const Ray_t &ray, RayDispOutput_t &output ) -{ - if ( IsBoxIntersectingRay( m_mins, m_maxs, ray.m_Start, ray.m_Delta, DISPCOLL_DIST_EPSILON ) ) - { - return AABBTree_Ray( ray, ray.InvDelta(), output ); - } - return false; -} - -bool CDispCollTree::AABBTree_Ray( const Ray_t &ray, const Vector &vecInvDelta, RayDispOutput_t &output ) -{ - VPROF( "DispRayTest" ); - - // Check for ray test. - if ( CheckFlags( CCoreDispInfo::SURF_NORAY_COLL ) ) - return false; - - // Check for opacity. - if ( !( m_nContents & MASK_OPAQUE ) ) - return false; - - // Pre-calc the inverse delta for perf. - CDispCollTri *pImpactTri = NULL; - - AABBTree_TreeTrisRayBarycentricTest( ray, vecInvDelta, DISPCOLL_ROOTNODE_INDEX, output, &pImpactTri ); - - if ( pImpactTri ) - { - // Collision. - output.ndxVerts[0] = pImpactTri->GetVert( 0 ); - output.ndxVerts[1] = pImpactTri->GetVert( 2 ); - output.ndxVerts[2] = pImpactTri->GetVert( 1 ); - - Assert( (output.u <= 1.0f ) && ( output.v <= 1.0f ) ); - Assert( (output.u >= 0.0f ) && ( output.v >= 0.0f ) ); - - return true; - } - - // No collision. - return false; -} - -void CDispCollTree::AABBTree_TreeTrisRayBarycentricTest( const Ray_t &ray, const Vector &vecInvDelta, int iNode, RayDispOutput_t &output, CDispCollTri **pImpactTri ) -{ - rayleaflist_t list; - // NOTE: This part is loop invariant - should be hoisted up as far as possible - list.invDelta.DuplicateVector(vecInvDelta); - list.rayStart.DuplicateVector(ray.m_Start); - Vector ext = ray.m_Extents + Vector(DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON); - list.rayExtents.DuplicateVector(ext); - int listIndex = BuildRayLeafList( iNode, list ); - - float flU, flV, flT; - for ( ; listIndex <= list.maxIndex; listIndex++ ) - { - int leafIndex = list.nodeList[listIndex] - m_nodes.Count(); - CDispCollTri *pTri0 = &m_aTris[m_leaves[leafIndex].m_tris[0]]; - CDispCollTri *pTri1 = &m_aTris[m_leaves[leafIndex].m_tris[1]]; - - if ( ComputeIntersectionBarycentricCoordinates( ray, m_aVerts[pTri0->GetVert( 0 )], m_aVerts[pTri0->GetVert( 2 )], m_aVerts[pTri0->GetVert( 1 )], flU, flV, &flT ) ) - { - // Make sure it's inside the range - if ( ( flU >= 0.0f ) && ( flV >= 0.0f ) && ( ( flU + flV ) <= 1.0f ) ) - { - if( ( flT > 0.0f ) && ( flT < output.dist ) ) - { - (*pImpactTri) = pTri0; - output.u = flU; - output.v = flV; - output.dist = flT; - } - } - } - if ( ComputeIntersectionBarycentricCoordinates( ray, m_aVerts[pTri1->GetVert( 0 )], m_aVerts[pTri1->GetVert( 2 )], m_aVerts[pTri1->GetVert( 1 )], flU, flV, &flT ) ) - { - // Make sure it's inside the range - if ( ( flU >= 0.0f ) && ( flV >= 0.0f ) && ( ( flU + flV ) <= 1.0f ) ) - { - if( ( flT > 0.0f ) && ( flT < output.dist ) ) - { - (*pImpactTri) = pTri1; - output.u = flU; - output.v = flV; - output.dist = flT; - } - } - } - } -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBTree_Ray( const Ray_t &ray, const Vector &vecInvDelta, CBaseTrace *pTrace, bool bSide ) -{ - VPROF("AABBTree_Ray"); - -// VPROF_BUDGET( "DispRayTraces", VPROF_BUDGETGROUP_DISP_RAYTRACES ); - - // Check for ray test. - if ( CheckFlags( CCoreDispInfo::SURF_NORAY_COLL ) ) - return false; - - // Check for opacity. - if ( !( m_nContents & MASK_OPAQUE ) ) - return false; - - // Pre-calc the inverse delta for perf. - CDispCollTri *pImpactTri = NULL; - - AABBTree_TreeTrisRayTest( ray, vecInvDelta, DISPCOLL_ROOTNODE_INDEX, pTrace, bSide, &pImpactTri ); - - if ( pImpactTri ) - { - // Collision. - VectorCopy( pImpactTri->m_vecNormal, pTrace->plane.normal ); - pTrace->plane.dist = pImpactTri->m_flDist; - pTrace->dispFlags = pImpactTri->m_uiFlags; - return true; - } - - // No collision. - return false; -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::AABBTree_TreeTrisRayTest( const Ray_t &ray, const Vector &vecInvDelta, int iNode, CBaseTrace *pTrace, bool bSide, CDispCollTri **pImpactTri ) -{ - rayleaflist_t list; - // NOTE: This part is loop invariant - should be hoisted up as far as possible - list.invDelta.DuplicateVector(vecInvDelta); - list.rayStart.DuplicateVector(ray.m_Start); - Vector ext = ray.m_Extents + Vector(DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON); - list.rayExtents.DuplicateVector(ext); - int listIndex = BuildRayLeafList( iNode, list ); - - for ( ;listIndex <= list.maxIndex; listIndex++ ) - { - int leafIndex = list.nodeList[listIndex] - m_nodes.Count(); - CDispCollTri *pTri0 = &m_aTris[m_leaves[leafIndex].m_tris[0]]; - CDispCollTri *pTri1 = &m_aTris[m_leaves[leafIndex].m_tris[1]]; - float flFrac = IntersectRayWithTriangle( ray, m_aVerts[pTri0->GetVert( 0 )], m_aVerts[pTri0->GetVert( 2 )], m_aVerts[pTri0->GetVert( 1 )], bSide ); - if( ( flFrac >= 0.0f ) && ( flFrac < pTrace->fraction ) ) - { - pTrace->fraction = flFrac; - (*pImpactTri) = pTri0; - } - - flFrac = IntersectRayWithTriangle( ray, m_aVerts[pTri1->GetVert( 0 )], m_aVerts[pTri1->GetVert( 2 )], m_aVerts[pTri1->GetVert( 1 )], bSide ); - if( ( flFrac >= 0.0f ) && ( flFrac < pTrace->fraction ) ) - { - pTrace->fraction = flFrac; - (*pImpactTri) = pTri1; - } - } -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -int CDispCollTree::AABBTree_GetTrisInSphere( const Vector ¢er, float radius, unsigned short *pIndexOut, int indexMax ) -{ - return AABBTree_BuildTreeTrisInSphere_r( center, radius, DISPCOLL_ROOTNODE_INDEX, pIndexOut, indexMax ); -} - -int CDispCollTree::AABBTree_BuildTreeTrisInSphere_r( const Vector ¢er, float radius, int iNode, unsigned short *pIndexOut, unsigned short indexMax ) -{ - int nodeList[MAX_AABB_LIST]; - nodeList[0] = iNode; - int nTriCount = 0; - int listIndex = 0; - int maxIndex = 0; - // NOTE: This part is loop invariant - should be hoisted up as far as possible - FourVectors sphereCenters; - sphereCenters.DuplicateVector(center); - float radiusSq = radius * radius; - fltx4 sphereRadSq = ReplicateX4(radiusSq); - while ( listIndex <= maxIndex ) - { - iNode = nodeList[listIndex]; - listIndex++; - // the rest are all leaves - if ( IsLeafNode(iNode) ) - { - VPROF("Tris"); - for ( --listIndex; listIndex <= maxIndex; listIndex++ ) - { - if ( (nTriCount+2) <= indexMax ) - { - int leafIndex = nodeList[listIndex] - m_nodes.Count(); - pIndexOut[nTriCount] = m_leaves[leafIndex].m_tris[0]; - pIndexOut[nTriCount+1] = m_leaves[leafIndex].m_tris[1]; - nTriCount += 2; - } - } - break; - } - else - { - const CDispCollNode &node = m_nodes[iNode]; - int mask = IntersectFourBoxSpherePairs( sphereCenters, sphereRadSq, node.m_mins, node.m_maxs ); - if ( mask ) - { - int child = Nodes_GetChild( iNode, 0 ); - if ( mask & 1 ) - { - ++maxIndex; - nodeList[maxIndex] = child; - } - if ( mask & 2 ) - { - ++maxIndex; - nodeList[maxIndex] = child+1; - } - if ( mask & 4 ) - { - ++maxIndex; - nodeList[maxIndex] = child+2; - } - if ( mask & 8 ) - { - ++maxIndex; - nodeList[maxIndex] = child+3; - } - Assert(maxIndex < MAX_AABB_LIST); - } - } - } - return nTriCount; -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBTree_IntersectAABB( const Vector &absMins, const Vector &absMaxs ) -{ - // Check for hull test. - if ( CheckFlags( CCoreDispInfo::SURF_NOHULL_COLL ) ) - return false; - - cplane_t plane; - Vector center = 0.5f *(absMins + absMaxs); - Vector extents = absMaxs - center; - - int nodeList[MAX_AABB_LIST]; - nodeList[0] = 0; - int listIndex = 0; - int maxIndex = 0; - - // NOTE: This part is loop invariant - should be hoisted up as far as possible - FourVectors mins0; - mins0.DuplicateVector(absMins); - FourVectors maxs0; - maxs0.DuplicateVector(absMaxs); - FourVectors rayExtents; - while ( listIndex <= maxIndex ) - { - int iNode = nodeList[listIndex]; - listIndex++; - // the rest are all leaves - if ( IsLeafNode(iNode) ) - { - VPROF("Tris"); - for ( --listIndex; listIndex <= maxIndex; listIndex++ ) - { - int leafIndex = nodeList[listIndex] - m_nodes.Count(); - CDispCollTri *pTri0 = &m_aTris[m_leaves[leafIndex].m_tris[0]]; - CDispCollTri *pTri1 = &m_aTris[m_leaves[leafIndex].m_tris[1]]; - - VectorCopy( pTri0->m_vecNormal, plane.normal ); - plane.dist = pTri0->m_flDist; - plane.signbits = pTri0->m_ucSignBits; - plane.type = pTri0->m_ucPlaneType; - - if ( IsBoxIntersectingTriangle( center, extents, - m_aVerts[pTri0->GetVert( 0 )], - m_aVerts[pTri0->GetVert( 2 )], - m_aVerts[pTri0->GetVert( 1 )], - plane, 0.0f ) ) - return true; - VectorCopy( pTri1->m_vecNormal, plane.normal ); - plane.dist = pTri1->m_flDist; - plane.signbits = pTri1->m_ucSignBits; - plane.type = pTri1->m_ucPlaneType; - - if ( IsBoxIntersectingTriangle( center, extents, - m_aVerts[pTri1->GetVert( 0 )], - m_aVerts[pTri1->GetVert( 2 )], - m_aVerts[pTri1->GetVert( 1 )], - plane, 0.0f ) ) - return true; - } - break; - } - else - { - const CDispCollNode &node = m_nodes[iNode]; - int mask = IntersectFourBoxPairs( mins0, maxs0, node.m_mins, node.m_maxs ); - if ( mask ) - { - int child = Nodes_GetChild( iNode, 0 ); - if ( mask & 1 ) - { - ++maxIndex; - nodeList[maxIndex] = child; - } - if ( mask & 2 ) - { - ++maxIndex; - nodeList[maxIndex] = child+1; - } - if ( mask & 4 ) - { - ++maxIndex; - nodeList[maxIndex] = child+2; - } - if ( mask & 8 ) - { - ++maxIndex; - nodeList[maxIndex] = child+3; - } - Assert(maxIndex < MAX_AABB_LIST); - } - } - } - - // no collision - return false; -} - -static const Vector g_Vec3DispCollEpsilons(DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON); -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBTree_SweepAABB( const Ray_t &ray, const Vector &vecInvDelta, CBaseTrace *pTrace ) -{ - VPROF( "DispHullTest" ); - // VPROF_BUDGET( "DispHullTraces", VPROF_BUDGETGROUP_DISP_HULLTRACES ); - // Check for hull test. - if ( CheckFlags( CCoreDispInfo::SURF_NOHULL_COLL ) ) - return false; - - // Test ray against the triangles in the list. - Vector rayDir; - VectorCopy( ray.m_Delta, rayDir ); - VectorNormalize( rayDir ); - // Save fraction. - float flFrac = pTrace->fraction; - - rayleaflist_t list; - // NOTE: This part is loop invariant - should be hoisted up as far as possible - list.invDelta.DuplicateVector(vecInvDelta); - list.rayStart.DuplicateVector(ray.m_Start); - Vector ext = ray.m_Extents + g_Vec3DispCollEpsilons; - list.rayExtents.DuplicateVector(ext); - int listIndex = BuildRayLeafList( 0, list ); - - if ( listIndex <= list.maxIndex ) - { - LockCache(); - for ( ; listIndex <= list.maxIndex; listIndex++ ) - { - int leafIndex = list.nodeList[listIndex] - m_nodes.Count(); - int iTri0 = m_leaves[leafIndex].m_tris[0]; - int iTri1 = m_leaves[leafIndex].m_tris[1]; - CDispCollTri *pTri0 = &m_aTris[iTri0]; - CDispCollTri *pTri1 = &m_aTris[iTri1]; - - SweepAABBTriIntersect( ray, rayDir, iTri0, pTri0, pTrace ); - SweepAABBTriIntersect( ray, rayDir, iTri1, pTri1, pTrace ); - } - UnlockCache(); - } - - // Collision. - if ( pTrace->fraction < flFrac ) - return true; - - // No collision. - return false; -} - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -bool CDispCollTree::ResolveRayPlaneIntersect( float flStart, float flEnd, const Vector &vecNormal, float flDist, CDispCollHelper *pHelper ) -{ - if( ( flStart > 0.0f ) && ( flEnd > 0.0f ) ) - return false; - - if( ( flStart < 0.0f ) && ( flEnd < 0.0f ) ) - return true; - - float flDenom = flStart - flEnd; - bool bDenomIsZero = ( flDenom == 0.0f ); - if( ( flStart >= 0.0f ) && ( flEnd <= 0.0f ) ) - { - // Find t - the parametric distance along the trace line. - float t = ( !bDenomIsZero ) ? ( flStart - DISPCOLL_DIST_EPSILON ) / flDenom : 0.0f; - if( t > pHelper->m_flStartFrac ) - { - pHelper->m_flStartFrac = t; - VectorCopy( vecNormal, pHelper->m_vecImpactNormal ); - pHelper->m_flImpactDist = flDist; - } - } - else - { - // Find t - the parametric distance along the trace line. - float t = ( !bDenomIsZero ) ? ( flStart + DISPCOLL_DIST_EPSILON ) / flDenom : 0.0f; - if( t < pHelper->m_flEndFrac ) - { - pHelper->m_flEndFrac = t; - } - } - - return true; -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline bool CDispCollTree::FacePlane( const Ray_t &ray, const Vector &rayDir, CDispCollTri *pTri, CDispCollHelper *pHelper ) -{ - // Calculate the closest point on box to plane (get extents in that direction). - Vector vecExtent; - CalcClosestExtents( pTri->m_vecNormal, ray.m_Extents, vecExtent ); - - float flExpandDist = pTri->m_flDist - pTri->m_vecNormal.Dot( vecExtent ); - - float flStart = pTri->m_vecNormal.Dot( ray.m_Start ) - flExpandDist; - float flEnd = pTri->m_vecNormal.Dot( ( ray.m_Start + ray.m_Delta ) ) - flExpandDist; - - return ResolveRayPlaneIntersect( flStart, flEnd, pTri->m_vecNormal, pTri->m_flDist, pHelper ); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool FORCEINLINE CDispCollTree::AxisPlanesXYZ( const Ray_t &ray, CDispCollTri *pTri, CDispCollHelper *pHelper ) -{ - static const TableVector g_ImpactNormalVecs[2][3] = - { - { - { -1, 0, 0 }, - { 0, -1, 0 }, - { 0, 0, -1 }, - }, - - { - { 1, 0, 0 }, - { 0, 1, 0 }, - { 0, 0, 1 }, - } - }; - - Vector vecImpactNormal; - float flDist, flExpDist, flStart, flEnd; - - int iAxis; - for ( iAxis = 2; iAxis >= 0; --iAxis ) - { - const float rayStart = ray.m_Start[iAxis]; - const float rayExtent = ray.m_Extents[iAxis]; - const float rayDelta = ray.m_Delta[iAxis]; - - // Min - flDist = m_aVerts[pTri->GetVert(pTri->GetMin(iAxis))][iAxis]; - flExpDist = flDist - rayExtent; - flStart = flExpDist - rayStart; - flEnd = flStart - rayDelta; - - if ( !ResolveRayPlaneIntersect( flStart, flEnd, g_ImpactNormalVecs[0][iAxis], flDist, pHelper ) ) - return false; - - // Max - flDist = m_aVerts[pTri->GetVert(pTri->GetMax(iAxis))][iAxis]; - flExpDist = flDist + rayExtent; - flStart = rayStart - flExpDist; - flEnd = flStart + rayDelta; - - if ( !ResolveRayPlaneIntersect( flStart, flEnd, g_ImpactNormalVecs[1][iAxis], flDist, pHelper ) ) - return false; - } - - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: Testing! -//----------------------------------------------------------------------------- -void CDispCollTree::Cache_Create( CDispCollTri *pTri, int iTri ) -{ - MEM_ALLOC_CREDIT(); - Vector *pVerts[3]; - pVerts[0] = &m_aVerts[pTri->GetVert( 0 )]; - pVerts[1] = &m_aVerts[pTri->GetVert( 1 )]; - pVerts[2] = &m_aVerts[pTri->GetVert( 2 )]; - - CDispCollTriCache *pCache = &m_aTrisCache[iTri]; - - Vector vecEdge; - - // Edge 1 - VectorSubtract( *pVerts[1], *pVerts[0], vecEdge ); - Cache_EdgeCrossAxisX( vecEdge, *pVerts[0], *pVerts[2], pTri, pCache->m_iCrossX[0] ); - Cache_EdgeCrossAxisY( vecEdge, *pVerts[0], *pVerts[2], pTri, pCache->m_iCrossY[0] ); - Cache_EdgeCrossAxisZ( vecEdge, *pVerts[0], *pVerts[2], pTri, pCache->m_iCrossZ[0] ); - - // Edge 2 - VectorSubtract( *pVerts[2], *pVerts[1], vecEdge ); - Cache_EdgeCrossAxisX( vecEdge, *pVerts[1], *pVerts[0], pTri, pCache->m_iCrossX[1] ); - Cache_EdgeCrossAxisY( vecEdge, *pVerts[1], *pVerts[0], pTri, pCache->m_iCrossY[1] ); - Cache_EdgeCrossAxisZ( vecEdge, *pVerts[1], *pVerts[0], pTri, pCache->m_iCrossZ[1] ); - - // Edge 3 - VectorSubtract( *pVerts[0], *pVerts[2], vecEdge ); - Cache_EdgeCrossAxisX( vecEdge, *pVerts[2], *pVerts[1], pTri, pCache->m_iCrossX[2] ); - Cache_EdgeCrossAxisY( vecEdge, *pVerts[2], *pVerts[1], pTri, pCache->m_iCrossY[2] ); - Cache_EdgeCrossAxisZ( vecEdge, *pVerts[2], *pVerts[1], pTri, pCache->m_iCrossZ[2] ); -} - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -int CDispCollTree::AddPlane( const Vector &vecNormal ) -{ - UtlHashHandle_t handle; - DispCollPlaneIndex_t planeIndex; - bool bDidInsert; - - planeIndex.vecPlane = vecNormal; - planeIndex.index = m_aEdgePlanes.Count(); - - handle = g_DispCollPlaneIndexHash.Insert( planeIndex, &bDidInsert ); - - if ( !bDidInsert ) - { - DispCollPlaneIndex_t &existingEntry = g_DispCollPlaneIndexHash[handle]; - if ( existingEntry.vecPlane == vecNormal ) - { - return existingEntry.index; - } - else - { - return ( existingEntry.index | 0x8000 ); - } - } - - return m_aEdgePlanes.AddToTail( vecNormal ); -} - -//----------------------------------------------------------------------------- -// Purpose: -// NOTE: The plane distance get stored in the normal x position since it isn't -// used. -//----------------------------------------------------------------------------- -bool CDispCollTree::Cache_EdgeCrossAxisX( const Vector &vecEdge, const Vector &vecOnEdge, - const Vector &vecOffEdge, CDispCollTri *pTri, - unsigned short &iPlane ) -{ - // Calculate the normal - edge x axisX = ( 0.0, edgeZ, -edgeY ) - Vector vecNormal( 0.0f, vecEdge.z, -vecEdge.y ); - VectorNormalize( vecNormal ); - - // Check for zero length normals. - if( ( vecNormal.y == 0.0f ) || ( vecNormal.z == 0.0f ) ) - { - iPlane = DISPCOLL_NORMAL_UNDEF; - return false; - } - -// if ( pTri->m_vecNormal.Dot( vecNormal ) ) -// { -// iPlane = DISPCOLL_NORMAL_UNDEF; -// return false; -// } - - // Finish the plane definition - get distance. - float flDist = ( vecNormal.y * vecOnEdge.y ) + ( vecNormal.z * vecOnEdge.z ); - - // Special case the point off edge in plane - float flOffDist = ( vecNormal.y * vecOffEdge.y ) + ( vecNormal.z * vecOffEdge.z ); - if ( !( FloatMakePositive( flOffDist - flDist ) < DISPCOLL_DIST_EPSILON ) && ( flOffDist > flDist ) ) - { - // Adjust plane facing - triangle should be behind the plane. - vecNormal.x = -flDist; - vecNormal.y = -vecNormal.y; - vecNormal.z = -vecNormal.z; - } - else - { - vecNormal.x = flDist; - } - - // Add edge plane to edge plane list. - iPlane = static_cast( AddPlane( vecNormal ) ); - - // Created the cached edge. - return true; -} - -//----------------------------------------------------------------------------- -// Purpose: -// NOTE: The plane distance get stored in the normal y position since it isn't -// used. -//----------------------------------------------------------------------------- -bool CDispCollTree::Cache_EdgeCrossAxisY( const Vector &vecEdge, const Vector &vecOnEdge, - const Vector &vecOffEdge, CDispCollTri *pTri, - unsigned short &iPlane ) -{ - // Calculate the normal - edge x axisY = ( -edgeZ, 0.0, edgeX ) - Vector vecNormal( -vecEdge.z, 0.0f, vecEdge.x ); - VectorNormalize( vecNormal ); - - // Check for zero length normals - if( ( vecNormal.x == 0.0f ) || ( vecNormal.z == 0.0f ) ) - { - iPlane = DISPCOLL_NORMAL_UNDEF; - return false; - } - -// if ( pTri->m_vecNormal.Dot( vecNormal ) ) -// { -// iPlane = DISPCOLL_NORMAL_UNDEF; -// return false; -// } - - // Finish the plane definition - get distance. - float flDist = ( vecNormal.x * vecOnEdge.x ) + ( vecNormal.z * vecOnEdge.z ); - - // Special case the point off edge in plane - float flOffDist = ( vecNormal.x * vecOffEdge.x ) + ( vecNormal.z * vecOffEdge.z ); - if ( !( FloatMakePositive( flOffDist - flDist ) < DISPCOLL_DIST_EPSILON ) && ( flOffDist > flDist ) ) - { - // Adjust plane facing if necessay - triangle should be behind the plane. - vecNormal.x = -vecNormal.x; - vecNormal.y = -flDist; - vecNormal.z = -vecNormal.z; - } - else - { - vecNormal.y = flDist; - } - - // Add edge plane to edge plane list. - iPlane = static_cast( AddPlane( vecNormal ) ); - - // Created the cached edge. - return true; -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::Cache_EdgeCrossAxisZ( const Vector &vecEdge, const Vector &vecOnEdge, - const Vector &vecOffEdge, CDispCollTri *pTri, - unsigned short &iPlane ) -{ - // Calculate the normal - edge x axisY = ( edgeY, -edgeX, 0.0 ) - Vector vecNormal( vecEdge.y, -vecEdge.x, 0.0f ); - VectorNormalize( vecNormal ); - - // Check for zero length normals - if( ( vecNormal.x == 0.0f ) || ( vecNormal.y == 0.0f ) ) - { - iPlane = DISPCOLL_NORMAL_UNDEF; - return false; - } - -// if ( pTri->m_vecNormal.Dot( vecNormal ) ) -// { -// iPlane = DISPCOLL_NORMAL_UNDEF; -// return false; -// } - - // Finish the plane definition - get distance. - float flDist = ( vecNormal.x * vecOnEdge.x ) + ( vecNormal.y * vecOnEdge.y ); - - // Special case the point off edge in plane - float flOffDist = ( vecNormal.x * vecOffEdge.x ) + ( vecNormal.y * vecOffEdge.y ); - if ( !( FloatMakePositive( flOffDist - flDist ) < DISPCOLL_DIST_EPSILON ) && ( flOffDist > flDist ) ) - { - // Adjust plane facing if necessay - triangle should be behind the plane. - vecNormal.x = -vecNormal.x; - vecNormal.y = -vecNormal.y; - vecNormal.z = -flDist; - } - else - { - vecNormal.z = flDist; - } - - // Add edge plane to edge plane list. - iPlane = static_cast( AddPlane( vecNormal ) ); - - // Created the cached edge. - return true; -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -template -bool CDispCollTree::EdgeCrossAxis( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) -{ - if ( iPlane == DISPCOLL_NORMAL_UNDEF ) - return true; - - // Get the edge plane. - Vector vecNormal; - if ( ( iPlane & 0x8000 ) != 0 ) - { - VectorCopy( m_aEdgePlanes[(iPlane&0x7fff)], vecNormal ); - vecNormal.Negate(); - } - else - { - VectorCopy( m_aEdgePlanes[iPlane], vecNormal ); - } - - const int OTHER_AXIS1 = ( AXIS + 1 ) % 3; - const int OTHER_AXIS2 = ( AXIS + 2 ) % 3; - - // Get the pland distance are "fix" the normal. - float flDist = vecNormal[AXIS]; - vecNormal[AXIS] = 0.0f; - - // Calculate the closest point on box to plane (get extents in that direction). - Vector vecExtent; - //vecExtent[AXIS] = 0.0f; - vecExtent[OTHER_AXIS1] = ( vecNormal[OTHER_AXIS1] < 0.0f ) ? ray.m_Extents[OTHER_AXIS1] : -ray.m_Extents[OTHER_AXIS1]; - vecExtent[OTHER_AXIS2] = ( vecNormal[OTHER_AXIS2] < 0.0f ) ? ray.m_Extents[OTHER_AXIS2] : -ray.m_Extents[OTHER_AXIS2]; - - // Expand the plane by the extents of the box to reduce the swept box/triangle - // test to a ray/extruded triangle test (one of the triangles extruded planes - // was just calculated above). - Vector vecEnd; - vecEnd[AXIS] = 0; - vecEnd[OTHER_AXIS1] = ray.m_Start[OTHER_AXIS1] + ray.m_Delta[OTHER_AXIS1]; - vecEnd[OTHER_AXIS2] = ray.m_Start[OTHER_AXIS2] + ray.m_Delta[OTHER_AXIS2]; - - float flExpandDist = flDist - ( ( vecNormal[OTHER_AXIS1] * vecExtent[OTHER_AXIS1] ) + ( vecNormal[OTHER_AXIS2] * vecExtent[OTHER_AXIS2] ) ); - float flStart = ( vecNormal[OTHER_AXIS1] * ray.m_Start[OTHER_AXIS1] ) + ( vecNormal[OTHER_AXIS2] * ray.m_Start[OTHER_AXIS2] ) - flExpandDist; - float flEnd = ( vecNormal[OTHER_AXIS1] * vecEnd[OTHER_AXIS1] ) + ( vecNormal[OTHER_AXIS2] * vecEnd[OTHER_AXIS2] ) - flExpandDist; - - return ResolveRayPlaneIntersect( flStart, flEnd, vecNormal, flDist, pHelper ); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline bool CDispCollTree::EdgeCrossAxisX( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) -{ - return EdgeCrossAxis<0>( ray, iPlane, pHelper ); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline bool CDispCollTree::EdgeCrossAxisY( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) -{ - return EdgeCrossAxis<1>( ray, iPlane, pHelper ); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline bool CDispCollTree::EdgeCrossAxisZ( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) -{ - return EdgeCrossAxis<2>( ray, iPlane, pHelper ); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::SweepAABBTriIntersect( const Ray_t &ray, const Vector &rayDir, int iTri, CDispCollTri *pTri, CBaseTrace *pTrace ) -{ - // Init test data. - CDispCollHelper helper; - helper.m_flEndFrac = 1.0f; - helper.m_flStartFrac = DISPCOLL_INVALID_FRAC; - - // Make sure objects are traveling toward one another. - float flDistAlongNormal = pTri->m_vecNormal.Dot( ray.m_Delta ); - if( flDistAlongNormal > DISPCOLL_DIST_EPSILON ) - return; - - // Test against the axis planes. - if ( !AxisPlanesXYZ( ray, pTri, &helper ) ) - { - return; - } - - // - // There are 9 edge tests - edges 1, 2, 3 cross with the box edges (symmetry) 1, 2, 3. However, the box - // is axis-aligned resulting in axially directional edges -- thus each test is edges 1, 2, and 3 vs. - // axial planes x, y, and z - // - // There are potentially 9 more tests with edges, the edge's edges and the direction of motion! - // NOTE: I don't think these tests are necessary for a manifold surface. - // - - CDispCollTriCache *pCache = &m_aTrisCache[iTri]; - - // Edges 1-3, interleaved - axis tests are 2d tests - if ( !EdgeCrossAxisX( ray, pCache->m_iCrossX[0], &helper ) ) { return; } - if ( !EdgeCrossAxisX( ray, pCache->m_iCrossX[1], &helper ) ) { return; } - if ( !EdgeCrossAxisX( ray, pCache->m_iCrossX[2], &helper ) ) { return; } - - if ( !EdgeCrossAxisY( ray, pCache->m_iCrossY[0], &helper ) ) { return; } - if ( !EdgeCrossAxisY( ray, pCache->m_iCrossY[1], &helper ) ) { return; } - if ( !EdgeCrossAxisY( ray, pCache->m_iCrossY[2], &helper ) ) { return; } - - if ( !EdgeCrossAxisZ( ray, pCache->m_iCrossZ[0], &helper ) ) { return; } - if ( !EdgeCrossAxisZ( ray, pCache->m_iCrossZ[1], &helper ) ) { return; } - if ( !EdgeCrossAxisZ( ray, pCache->m_iCrossZ[2], &helper ) ) { return; } - - // Test against the triangle face plane. - if ( !FacePlane( ray, rayDir, pTri, &helper ) ) - return; - - if ( ( helper.m_flStartFrac < helper.m_flEndFrac ) || ( FloatMakePositive( helper.m_flStartFrac - helper.m_flEndFrac ) < 0.001f ) ) - { - if ( ( helper.m_flStartFrac != DISPCOLL_INVALID_FRAC ) && ( helper.m_flStartFrac < pTrace->fraction ) ) - { - // Clamp -- shouldn't really ever be here!??? - if ( helper.m_flStartFrac < 0.0f ) - { - helper.m_flStartFrac = 0.0f; - } - - pTrace->fraction = helper.m_flStartFrac; - VectorCopy( helper.m_vecImpactNormal, pTrace->plane.normal ); - pTrace->plane.dist = helper.m_flImpactDist; - pTrace->dispFlags = pTri->m_uiFlags; - } - } -} - -//----------------------------------------------------------------------------- -// Purpose: constructor -//----------------------------------------------------------------------------- -CDispCollTree::CDispCollTree() -{ - m_nPower = 0; - m_nFlags = 0; - - for ( int iPoint = 0; iPoint < 4; ++iPoint ) - { - m_vecSurfPoints[iPoint].Init(); - } - m_nContents = -1; - m_nSurfaceProps[0] = 0; - m_nSurfaceProps[1] = 0; - - m_vecStabDir.Init(); - m_mins.Init( FLT_MAX, FLT_MAX, FLT_MAX ); - m_maxs.Init( -FLT_MAX, -FLT_MAX, -FLT_MAX ); - - m_iCounter = 0; - - m_aVerts.Purge(); - m_aTris.Purge(); - m_aEdgePlanes.Purge(); -#ifdef ENGINE_DLL - m_hCache = INVALID_MEMHANDLE; -#endif -} - -//----------------------------------------------------------------------------- -// Purpose: deconstructor -//----------------------------------------------------------------------------- -CDispCollTree::~CDispCollTree() -{ -#ifdef ENGINE_DLL - if ( m_hCache != INVALID_MEMHANDLE ) - g_DispCollTriCache.DestroyResource( m_hCache ); -#endif - m_aVerts.Purge(); - m_aTris.Purge(); - m_aEdgePlanes.Purge(); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::Create( CCoreDispInfo *pDisp ) -{ - // Create the AABB Tree. - return AABBTree_Create( pDisp ); -} - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::PointInBounds( const Vector &vecBoxCenter, const Vector &vecBoxMin, - const Vector &vecBoxMax, bool bPoint ) -{ - // Point test inside bounds. - if( bPoint ) - { - return IsPointInBox( vecBoxCenter, m_mins, m_maxs ); - } - - // Box test inside bounds - Vector vecExtents; - VectorSubtract( vecBoxMax, vecBoxMin, vecExtents ); - vecExtents *= 0.5f; - - Vector vecExpandBounds[2]; - vecExpandBounds[0] = m_mins - vecExtents; - vecExpandBounds[1] = m_maxs + vecExtents; - - return IsPointInBox( vecBoxCenter, vecExpandBounds[0], vecExpandBounds[1] ); -} - -void CDispCollTree::GetVirtualMeshList( virtualmeshlist_t *pList ) -{ - int i; - int triangleCount = GetTriSize(); - pList->indexCount = triangleCount * 3; - pList->triangleCount = triangleCount; - pList->vertexCount = m_aVerts.Count(); - pList->pVerts = m_aVerts.Base(); - pList->pHull = NULL; - pList->surfacePropsIndex = GetSurfaceProps(0); - int index = 0; - for ( i = 0 ; i < triangleCount; i++ ) - { - pList->indices[index+0] = m_aTris[i].GetVert(0); - pList->indices[index+1] = m_aTris[i].GetVert(1); - pList->indices[index+2] = m_aTris[i].GetVert(2); - index += 3; - } -} - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -#ifdef ENGINE_DLL -static int g_nTrees; -#endif -CDispCollTree *DispCollTrees_Alloc( int count ) -{ - CDispCollTree *pTrees = NULL; -#ifdef ENGINE_DLL - pTrees = (CDispCollTree *)Hunk_Alloc( count * sizeof(CDispCollTree), false ); - g_nTrees = count; - for ( int i = 0; i < g_nTrees; i++ ) - { - Construct( pTrees + i ); - } -#else - pTrees = new CDispCollTree[count]; -#endif - if( !pTrees ) - return NULL; - - for ( int i = 0; i < count; i++ ) - { - pTrees[i].m_iCounter = i; - } - return pTrees; -} - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -void DispCollTrees_Free( CDispCollTree *pTrees ) -{ -#ifdef ENGINE_DLL - for ( int i = 0; i < g_nTrees; i++ ) - { - Destruct( pTrees + i ); - } - g_nTrees = 0; -#else - if( pTrees ) - { - delete [] pTrees; - pTrees = NULL; - } -#endif -} +//========= Copyright Valve Corporation, All rights reserved. ============// +// +// Purpose: +// +// $NoKeywords: $ +//=============================================================================// + +#include "cmodel.h" +#include "dispcoll_common.h" +#include "collisionutils.h" +#include "tier1/strtools.h" +#include "tier0/vprof.h" +#include "tier1/fmtstr.h" +#include "tier1/utlhash.h" +#include "tier1/generichash.h" +#include "tier0/fasttimer.h" +#include "vphysics/virtualmesh.h" +#include "tier1/datamanager.h" +// memdbgon must be the last include file in a .cpp file!!! +#include "tier0/memdbgon.h" + +//============================================================================= +// Cache + +#ifdef ENGINE_DLL +CDataManager g_DispCollTriCache( 2048*1024 ); +#endif + + +struct DispCollPlaneIndex_t +{ + Vector vecPlane; + int index; +}; + +class CPlaneIndexHashFuncs +{ +public: + CPlaneIndexHashFuncs( int ) {} + + // Compare + bool operator()( const DispCollPlaneIndex_t &lhs, const DispCollPlaneIndex_t &rhs ) const + { + return ( lhs.vecPlane == rhs.vecPlane || lhs.vecPlane == -rhs.vecPlane ); + } + + // Hash + unsigned int operator()( const DispCollPlaneIndex_t &item ) const + { + return HashItem( item.vecPlane ) ^ HashItem( -item.vecPlane ); + } +}; + +CUtlHash g_DispCollPlaneIndexHash( 512 ); + + +//============================================================================= +// Displacement Collision Triangle + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +CDispCollTri::CDispCollTri() +{ + Init(); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTri::Init( void ) +{ + m_vecNormal.Init(); + m_flDist = 0.0f; + m_TriData[0].m_IndexDummy = m_TriData[1].m_IndexDummy = m_TriData[2].m_IndexDummy = 0; +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTri::CalcPlane( CDispVector &m_aVerts ) +{ + Vector vecEdges[2]; + vecEdges[0] = m_aVerts[GetVert( 1 )] - m_aVerts[GetVert( 0 )]; + vecEdges[1] = m_aVerts[GetVert( 2 )] - m_aVerts[GetVert( 0 )]; + + m_vecNormal = vecEdges[1].Cross( vecEdges[0] ); + VectorNormalize( m_vecNormal ); + m_flDist = m_vecNormal.Dot( m_aVerts[GetVert( 0 )] ); + + // Calculate the signbits for the plane - fast test. + m_ucSignBits = 0; + m_ucPlaneType = PLANE_ANYZ; + for ( int iAxis = 0; iAxis < 3 ; ++iAxis ) + { + if ( m_vecNormal[iAxis] < 0.0f ) + { + m_ucSignBits |= 1 << iAxis; + } + + if ( m_vecNormal[iAxis] == 1.0f ) + { + m_ucPlaneType = iAxis; + } + } +} + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +inline void FindMin( float v1, float v2, float v3, int &iMin ) +{ + float flMin = v1; + iMin = 0; + if( v2 < flMin ) { flMin = v2; iMin = 1; } + if( v3 < flMin ) { flMin = v3; iMin = 2; } +} + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +inline void FindMax( float v1, float v2, float v3, int &iMax ) +{ + float flMax = v1; + iMax = 0; + if( v2 > flMax ) { flMax = v2; iMax = 1; } + if( v3 > flMax ) { flMax = v3; iMax = 2; } +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTri::FindMinMax( CDispVector &m_aVerts ) +{ + int iMin, iMax; + FindMin( m_aVerts[GetVert(0)].x, m_aVerts[GetVert(1)].x, m_aVerts[GetVert(2)].x, iMin ); + FindMax( m_aVerts[GetVert(0)].x, m_aVerts[GetVert(1)].x, m_aVerts[GetVert(2)].x, iMax ); + SetMin( 0, iMin ); + SetMax( 0, iMax ); + + FindMin( m_aVerts[GetVert(0)].y, m_aVerts[GetVert(1)].y, m_aVerts[GetVert(2)].y, iMin ); + FindMax( m_aVerts[GetVert(0)].y, m_aVerts[GetVert(1)].y, m_aVerts[GetVert(2)].y, iMax ); + SetMin( 1, iMin ); + SetMax( 1, iMax ); + + FindMin( m_aVerts[GetVert(0)].z, m_aVerts[GetVert(1)].z, m_aVerts[GetVert(2)].z, iMin ); + FindMax( m_aVerts[GetVert(0)].z, m_aVerts[GetVert(1)].z, m_aVerts[GetVert(2)].z, iMax ); + SetMin( 2, iMin ); + SetMax( 2, iMax ); +} + + +// SIMD Routines for intersecting with the quad tree +FORCEINLINE int IntersectRayWithFourBoxes( const FourVectors &rayStart, const FourVectors &invDelta, const FourVectors &rayExtents, const FourVectors &boxMins, const FourVectors &boxMaxs ) +{ + // SIMD Test ray against all four boxes at once + // each node stores the bboxes of its four children + FourVectors hitMins = boxMins; + hitMins -= rayStart; + FourVectors hitMaxs = boxMaxs; + hitMaxs -= rayStart; + + // adjust for swept box by enlarging the child bounds to shrink the sweep down to a point + hitMins -= rayExtents; + hitMaxs += rayExtents; + + // compute the parametric distance along the ray of intersection in each dimension + hitMins *= invDelta; + hitMaxs *= invDelta; + + // Find the exit parametric intersection distance in each dimesion, for each box + FourVectors exitT = maximum(hitMins,hitMaxs); + // Find the entry parametric intersection distance in each dimesion, for each box + FourVectors entryT = minimum(hitMins,hitMaxs); + + // now find the max overall entry distance across all dimensions for each box + fltx4 minTemp = MaxSIMD(entryT.x, entryT.y); + fltx4 boxEntryT = MaxSIMD(minTemp, entryT.z); + + // now find the min overall exit distance across all dimensions for each box + fltx4 maxTemp = MinSIMD(exitT.x, exitT.y); + fltx4 boxExitT = MinSIMD(maxTemp, exitT.z); + + boxEntryT = MaxSIMD(boxEntryT,Four_Zeros); + boxExitT = MinSIMD(boxExitT,Four_Ones); + + // if entry<=exit for the box, we've got a hit + fltx4 active = CmpLeSIMD(boxEntryT,boxExitT); // mask of which boxes are active + + // hit at least one box? + return TestSignSIMD(active); +} + +// This does 4 simultaneous box intersections +// NOTE: This can be used as a 1 vs 4 test by replicating a single box into the one side +FORCEINLINE int IntersectFourBoxPairs( const FourVectors &mins0, const FourVectors &maxs0, const FourVectors &mins1, const FourVectors &maxs1 ) +{ + // find the max mins and min maxs in each dimension + FourVectors intersectMins = maximum(mins0,mins1); + FourVectors intersectMaxs = minimum(maxs0,maxs1); + + // if intersectMins <= intersectMaxs then the boxes overlap in this dimension + fltx4 overlapX = CmpLeSIMD(intersectMins.x,intersectMaxs.x); + fltx4 overlapY = CmpLeSIMD(intersectMins.y,intersectMaxs.y); + fltx4 overlapZ = CmpLeSIMD(intersectMins.z,intersectMaxs.z); + + // if the boxes overlap in all three dimensions, they intersect + fltx4 tmp = AndSIMD( overlapX, overlapY ); + fltx4 active = AndSIMD( tmp, overlapZ ); + + // hit at least one box? + return TestSignSIMD(active); +} + +// This does 4 simultaneous box vs. sphere intersections +// NOTE: This can be used as a 1 vs 4 test by replicating a single sphere/box into one side +FORCEINLINE int IntersectFourBoxSpherePairs( const FourVectors ¢er, const fltx4 &radiusSq, const FourVectors &mins, const FourVectors &maxs ) +{ + // for each dimension of each box, compute the clamped distance from the mins side to the center (must be >= 0) + FourVectors minDist = mins; + minDist -= center; + FourVectors dist; + dist.x = MaxSIMD(Four_Zeros, minDist.x); + dist.y = MaxSIMD(Four_Zeros, minDist.y); + dist.z = MaxSIMD(Four_Zeros, minDist.z); + + // now compute the distance from the maxs side to the center + FourVectors maxDist = center; + maxDist -= maxs; + // NOTE: Don't need to clamp here because we clamp against the minDist which must be >= 0, so the two clamps + // get folded together + FourVectors totalDist; + totalDist.x = MaxSIMD(dist.x, maxDist.x); + totalDist.y = MaxSIMD(dist.y, maxDist.y); + totalDist.z = MaxSIMD(dist.z, maxDist.z); + // get the total squred distance between each box & sphere center by summing the squares of each + // component/dimension + fltx4 distSq = totalDist * totalDist; + + // if squared distance between each sphere center & box is less than the radiusSquared for that sphere + // we have an intersection + fltx4 active = CmpLeSIMD(distSq,radiusSq); + + // at least one intersection? + return TestSignSIMD(active); +} + + +int FORCEINLINE CDispCollTree::BuildRayLeafList( int iNode, rayleaflist_t &list ) +{ + list.nodeList[0] = iNode; + int listIndex = 0; + list.maxIndex = 0; + while ( listIndex <= list.maxIndex ) + { + iNode = list.nodeList[listIndex]; + // the rest are all leaves + if ( IsLeafNode(iNode) ) + return listIndex; + listIndex++; + const CDispCollNode &node = m_nodes[iNode]; + int mask = IntersectRayWithFourBoxes( list.rayStart, list.invDelta, list.rayExtents, node.m_mins, node.m_maxs ); + if ( mask ) + { + int child = Nodes_GetChild( iNode, 0 ); + if ( mask & 1 ) + { + ++list.maxIndex; + list.nodeList[list.maxIndex] = child; + } + if ( mask & 2 ) + { + ++list.maxIndex; + list.nodeList[list.maxIndex] = child+1; + } + if ( mask & 4 ) + { + ++list.maxIndex; + list.nodeList[list.maxIndex] = child+2; + } + if ( mask & 8 ) + { + ++list.maxIndex; + list.nodeList[list.maxIndex] = child+3; + } + Assert(list.maxIndex < MAX_AABB_LIST); + } + } + + return listIndex; +} + + +//----------------------------------------------------------------------------- +// Purpose: Create the AABB tree. +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBTree_Create( CCoreDispInfo *pDisp ) +{ + // Copy the flags. + m_nFlags = pDisp->GetSurface()->GetFlags(); + + // Copy necessary displacement data. + AABBTree_CopyDispData( pDisp ); + + // Setup/create the leaf nodes first so the recusion can use this data to stop. + AABBTree_CreateLeafs(); + + // Create the bounding box of the displacement surface + the base face. + AABBTree_CalcBounds(); + + // Successful. + return true; +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::AABBTree_CopyDispData( CCoreDispInfo *pDisp ) +{ + // Displacement size. + m_nPower = pDisp->GetPower(); + + // Displacement base surface data. + CCoreDispSurface *pSurf = pDisp->GetSurface(); + m_nContents = pSurf->GetContents(); + pSurf->GetNormal( m_vecStabDir ); + for ( int iPoint = 0; iPoint < 4; iPoint++ ) + { + pSurf->GetPoint( iPoint, m_vecSurfPoints[iPoint] ); + } + + // Allocate collision tree data. + { + MEM_ALLOC_CREDIT(); + m_aVerts.SetSize( GetSize() ); + } + + { + MEM_ALLOC_CREDIT(); + m_aTris.SetSize( GetTriSize() ); + } + + { + MEM_ALLOC_CREDIT(); + int numLeaves = (GetWidth()-1) * (GetHeight()-1); + m_leaves.SetCount(numLeaves); + int numNodes = Nodes_CalcCount( m_nPower ); + numNodes -= numLeaves; + m_nodes.SetCount(numNodes); + } + + + // Setup size. + m_nSize = sizeof( this ); + m_nSize += sizeof( Vector ) * GetSize(); + m_nSize += sizeof( CDispCollTri ) * GetTriSize(); +#if OLD_DISP_AABB + m_nSize += sizeof( CDispCollAABBNode ) * Nodes_CalcCount( m_nPower ); +#endif + m_nSize += sizeof(m_nodes[0]) * m_nodes.Count(); + m_nSize += sizeof(m_leaves[0]) * m_leaves.Count(); + m_nSize += sizeof( CDispCollTri* ) * DISPCOLL_TREETRI_SIZE; + + // Copy vertex data. + for ( int iVert = 0; iVert < m_aVerts.Count(); iVert++ ) + { + pDisp->GetVert( iVert, m_aVerts[iVert] ); + } + + // Copy and setup triangle data. + unsigned short iVerts[3]; + for ( int iTri = 0; iTri < m_aTris.Count(); ++iTri ) + { + pDisp->GetTriIndices( iTri, iVerts[0], iVerts[1], iVerts[2] ); + m_aTris[iTri].SetVert( 0, iVerts[0] ); + m_aTris[iTri].SetVert( 1, iVerts[1] ); + m_aTris[iTri].SetVert( 2, iVerts[2] ); + m_aTris[iTri].m_uiFlags = pDisp->GetTriTagValue( iTri ); + + // Calculate the surface props and set flags. + float flTotalAlpha = 0.0f; + for ( int iVert = 0; iVert < 3; ++iVert ) + { + flTotalAlpha += pDisp->GetAlpha( m_aTris[iTri].GetVert( iVert ) ); + } + + if ( flTotalAlpha > DISP_ALPHA_PROP_DELTA ) + { + m_aTris[iTri].m_uiFlags |= DISPSURF_FLAG_SURFPROP2; + } + else + { + m_aTris[iTri].m_uiFlags |= DISPSURF_FLAG_SURFPROP1; + } + + // Add the displacement surface flag. + m_aTris[iTri].m_uiFlags |= DISPSURF_FLAG_SURFACE; + + // Calculate the plane normal and the min max. + m_aTris[iTri].CalcPlane( m_aVerts ); + m_aTris[iTri].FindMinMax( m_aVerts ); + } +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::AABBTree_CreateLeafs( void ) +{ + int numLeaves = (GetWidth()-1) * (GetHeight()-1); + m_leaves.SetCount(numLeaves); + int numNodes = Nodes_CalcCount( m_nPower ); + numNodes -= numLeaves; + m_nodes.SetCount(numNodes); + + // Get the width and height of the displacement. + int nWidth = GetWidth() - 1; + int nHeight = GetHeight() - 1; + + for ( int iHgt = 0; iHgt < nHeight; ++iHgt ) + { + for ( int iWid = 0; iWid < nWidth; ++iWid ) + { + int iLeaf = Nodes_GetIndexFromComponents( iWid, iHgt ); + int iIndex = iHgt * nWidth + iWid; + int iTri = iIndex * 2; + + m_leaves[iLeaf].m_tris[0] = iTri; + m_leaves[iLeaf].m_tris[1] = iTri + 1; + } + } +} + +void CDispCollTree::AABBTree_GenerateBoxes_r( int nodeIndex, Vector *pMins, Vector *pMaxs ) +{ + // leaf + ClearBounds( *pMins, *pMaxs ); + if ( nodeIndex >= m_nodes.Count() ) + { + int iLeaf = nodeIndex - m_nodes.Count(); + + for ( int iTri = 0; iTri < 2; ++iTri ) + { + int triIndex = m_leaves[iLeaf].m_tris[iTri]; + const CDispCollTri &tri = m_aTris[triIndex]; + AddPointToBounds( m_aVerts[tri.GetVert( 0 )], *pMins, *pMaxs ); + AddPointToBounds( m_aVerts[tri.GetVert( 1 )], *pMins, *pMaxs ); + AddPointToBounds( m_aVerts[tri.GetVert( 2 )], *pMins, *pMaxs ); + } + } + else // node + { + Vector childMins[4], childMaxs[4]; + for ( int i = 0; i < 4; i++ ) + { + int child = Nodes_GetChild( nodeIndex, i ); + AABBTree_GenerateBoxes_r( child, &childMins[i], &childMaxs[i] ); + AddPointToBounds( childMins[i], *pMins, *pMaxs ); + AddPointToBounds( childMaxs[i], *pMins, *pMaxs ); + } + m_nodes[nodeIndex].m_mins.LoadAndSwizzle( childMins[0], childMins[1], childMins[2], childMins[3] ); + m_nodes[nodeIndex].m_maxs.LoadAndSwizzle( childMaxs[0], childMaxs[1], childMaxs[2], childMaxs[3] ); + } +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::AABBTree_CalcBounds( void ) +{ + // Check data. + if ( ( m_aVerts.Count() == 0 ) || ( m_nodes.Count() == 0 ) ) + return; + + AABBTree_GenerateBoxes_r( 0, &m_mins, &m_maxs ); + +#if INCLUDE_SURFACE_IN_BOUNDS + // Add surface points to bounds. + for ( int iPoint = 0; iPoint < 4; ++iPoint ) + { + VectorMin( m_vecSurfPoints[iPoint], m_mins, m_mins ); + VectorMax( m_vecSurfPoints[iPoint], m_maxs, m_maxs ); + } +#endif + + // Bloat a little. + for ( int iAxis = 0; iAxis < 3; ++iAxis ) + { + m_mins[iAxis] -= 1.0f; + m_maxs[iAxis] += 1.0f; + } +} + +static CThreadFastMutex s_CacheMutex; +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline void CDispCollTree::LockCache() +{ +#ifdef ENGINE_DLL + if ( !g_DispCollTriCache.LockResource( m_hCache ) ) + { + AUTO_LOCK_FM( s_CacheMutex ); + + // Cache may have just been created, so check once more + if ( !g_DispCollTriCache.LockResource( m_hCache ) ) + { + Cache(); + m_hCache = g_DispCollTriCache.CreateResource( this ); + g_DispCollTriCache.LockResource( m_hCache ); + //Msg( "Adding 0x%x to cache (actual %d) [%d, %d --> %.2f] %d total, %d unique\n", this, GetCacheMemorySize(), GetTriSize(), m_aEdgePlanes.Count(), (float)m_aEdgePlanes.Count()/(float)GetTriSize(), totals, uniques ); + } + } +#else + Cache(); +#endif +} + +inline void CDispCollTree::UnlockCache() +{ +#ifdef ENGINE_DLL + g_DispCollTriCache.UnlockResource( m_hCache ); +#endif +} +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::Cache( void ) +{ + if ( m_aTrisCache.Count() == GetTriSize() ) + { + return; + } + + VPROF( "CDispCollTree::Cache" ); + + // Alloc. +// int nSize = sizeof( CDispCollTriCache ) * GetTriSize(); + int nTriCount = GetTriSize(); + { + MEM_ALLOC_CREDIT(); + m_aTrisCache.SetSize( nTriCount ); + } + + for ( int iTri = 0; iTri < nTriCount; ++iTri ) + { + Cache_Create( &m_aTris[iTri], iTri ); + } + + g_DispCollPlaneIndexHash.Purge(); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBTree_Ray( const Ray_t &ray, RayDispOutput_t &output ) +{ + if ( IsBoxIntersectingRay( m_mins, m_maxs, ray.m_Start, ray.m_Delta, DISPCOLL_DIST_EPSILON ) ) + { + return AABBTree_Ray( ray, ray.InvDelta(), output ); + } + return false; +} + +bool CDispCollTree::AABBTree_Ray( const Ray_t &ray, const Vector &vecInvDelta, RayDispOutput_t &output ) +{ + VPROF( "DispRayTest" ); + + // Check for ray test. + if ( CheckFlags( CCoreDispInfo::SURF_NORAY_COLL ) ) + return false; + + // Check for opacity. + if ( !( m_nContents & MASK_OPAQUE ) ) + return false; + + // Pre-calc the inverse delta for perf. + CDispCollTri *pImpactTri = NULL; + + AABBTree_TreeTrisRayBarycentricTest( ray, vecInvDelta, DISPCOLL_ROOTNODE_INDEX, output, &pImpactTri ); + + if ( pImpactTri ) + { + // Collision. + output.ndxVerts[0] = pImpactTri->GetVert( 0 ); + output.ndxVerts[1] = pImpactTri->GetVert( 2 ); + output.ndxVerts[2] = pImpactTri->GetVert( 1 ); + + Assert( (output.u <= 1.0f ) && ( output.v <= 1.0f ) ); + Assert( (output.u >= 0.0f ) && ( output.v >= 0.0f ) ); + + return true; + } + + // No collision. + return false; +} + +void CDispCollTree::AABBTree_TreeTrisRayBarycentricTest( const Ray_t &ray, const Vector &vecInvDelta, int iNode, RayDispOutput_t &output, CDispCollTri **pImpactTri ) +{ + rayleaflist_t list; + // NOTE: This part is loop invariant - should be hoisted up as far as possible + list.invDelta.DuplicateVector(vecInvDelta); + list.rayStart.DuplicateVector(ray.m_Start); + Vector ext = ray.m_Extents + Vector(DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON); + list.rayExtents.DuplicateVector(ext); + int listIndex = BuildRayLeafList( iNode, list ); + + float flU, flV, flT; + for ( ; listIndex <= list.maxIndex; listIndex++ ) + { + int leafIndex = list.nodeList[listIndex] - m_nodes.Count(); + CDispCollTri *pTri0 = &m_aTris[m_leaves[leafIndex].m_tris[0]]; + CDispCollTri *pTri1 = &m_aTris[m_leaves[leafIndex].m_tris[1]]; + + if ( ComputeIntersectionBarycentricCoordinates( ray, m_aVerts[pTri0->GetVert( 0 )], m_aVerts[pTri0->GetVert( 2 )], m_aVerts[pTri0->GetVert( 1 )], flU, flV, &flT ) ) + { + // Make sure it's inside the range + if ( ( flU >= 0.0f ) && ( flV >= 0.0f ) && ( ( flU + flV ) <= 1.0f ) ) + { + if( ( flT > 0.0f ) && ( flT < output.dist ) ) + { + (*pImpactTri) = pTri0; + output.u = flU; + output.v = flV; + output.dist = flT; + } + } + } + if ( ComputeIntersectionBarycentricCoordinates( ray, m_aVerts[pTri1->GetVert( 0 )], m_aVerts[pTri1->GetVert( 2 )], m_aVerts[pTri1->GetVert( 1 )], flU, flV, &flT ) ) + { + // Make sure it's inside the range + if ( ( flU >= 0.0f ) && ( flV >= 0.0f ) && ( ( flU + flV ) <= 1.0f ) ) + { + if( ( flT > 0.0f ) && ( flT < output.dist ) ) + { + (*pImpactTri) = pTri1; + output.u = flU; + output.v = flV; + output.dist = flT; + } + } + } + } +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBTree_Ray( const Ray_t &ray, const Vector &vecInvDelta, CBaseTrace *pTrace, bool bSide ) +{ + VPROF("AABBTree_Ray"); + +// VPROF_BUDGET( "DispRayTraces", VPROF_BUDGETGROUP_DISP_RAYTRACES ); + + // Check for ray test. + if ( CheckFlags( CCoreDispInfo::SURF_NORAY_COLL ) ) + return false; + + // Check for opacity. + if ( !( m_nContents & MASK_OPAQUE ) ) + return false; + + // Pre-calc the inverse delta for perf. + CDispCollTri *pImpactTri = NULL; + + AABBTree_TreeTrisRayTest( ray, vecInvDelta, DISPCOLL_ROOTNODE_INDEX, pTrace, bSide, &pImpactTri ); + + if ( pImpactTri ) + { + // Collision. + VectorCopy( pImpactTri->m_vecNormal, pTrace->plane.normal ); + pTrace->plane.dist = pImpactTri->m_flDist; + pTrace->dispFlags = pImpactTri->m_uiFlags; + return true; + } + + // No collision. + return false; +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::AABBTree_TreeTrisRayTest( const Ray_t &ray, const Vector &vecInvDelta, int iNode, CBaseTrace *pTrace, bool bSide, CDispCollTri **pImpactTri ) +{ + rayleaflist_t list; + // NOTE: This part is loop invariant - should be hoisted up as far as possible + list.invDelta.DuplicateVector(vecInvDelta); + list.rayStart.DuplicateVector(ray.m_Start); + Vector ext = ray.m_Extents + Vector(DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON); + list.rayExtents.DuplicateVector(ext); + int listIndex = BuildRayLeafList( iNode, list ); + + for ( ;listIndex <= list.maxIndex; listIndex++ ) + { + int leafIndex = list.nodeList[listIndex] - m_nodes.Count(); + CDispCollTri *pTri0 = &m_aTris[m_leaves[leafIndex].m_tris[0]]; + CDispCollTri *pTri1 = &m_aTris[m_leaves[leafIndex].m_tris[1]]; + float flFrac = IntersectRayWithTriangle( ray, m_aVerts[pTri0->GetVert( 0 )], m_aVerts[pTri0->GetVert( 2 )], m_aVerts[pTri0->GetVert( 1 )], bSide ); + if( ( flFrac >= 0.0f ) && ( flFrac < pTrace->fraction ) ) + { + pTrace->fraction = flFrac; + (*pImpactTri) = pTri0; + } + + flFrac = IntersectRayWithTriangle( ray, m_aVerts[pTri1->GetVert( 0 )], m_aVerts[pTri1->GetVert( 2 )], m_aVerts[pTri1->GetVert( 1 )], bSide ); + if( ( flFrac >= 0.0f ) && ( flFrac < pTrace->fraction ) ) + { + pTrace->fraction = flFrac; + (*pImpactTri) = pTri1; + } + } +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +int CDispCollTree::AABBTree_GetTrisInSphere( const Vector ¢er, float radius, unsigned short *pIndexOut, int indexMax ) +{ + return AABBTree_BuildTreeTrisInSphere_r( center, radius, DISPCOLL_ROOTNODE_INDEX, pIndexOut, indexMax ); +} + +int CDispCollTree::AABBTree_BuildTreeTrisInSphere_r( const Vector ¢er, float radius, int iNode, unsigned short *pIndexOut, unsigned short indexMax ) +{ + int nodeList[MAX_AABB_LIST]; + nodeList[0] = iNode; + int nTriCount = 0; + int listIndex = 0; + int maxIndex = 0; + // NOTE: This part is loop invariant - should be hoisted up as far as possible + FourVectors sphereCenters; + sphereCenters.DuplicateVector(center); + float radiusSq = radius * radius; + fltx4 sphereRadSq = ReplicateX4(radiusSq); + while ( listIndex <= maxIndex ) + { + iNode = nodeList[listIndex]; + listIndex++; + // the rest are all leaves + if ( IsLeafNode(iNode) ) + { + VPROF("Tris"); + for ( --listIndex; listIndex <= maxIndex; listIndex++ ) + { + if ( (nTriCount+2) <= indexMax ) + { + int leafIndex = nodeList[listIndex] - m_nodes.Count(); + pIndexOut[nTriCount] = m_leaves[leafIndex].m_tris[0]; + pIndexOut[nTriCount+1] = m_leaves[leafIndex].m_tris[1]; + nTriCount += 2; + } + } + break; + } + else + { + const CDispCollNode &node = m_nodes[iNode]; + int mask = IntersectFourBoxSpherePairs( sphereCenters, sphereRadSq, node.m_mins, node.m_maxs ); + if ( mask ) + { + int child = Nodes_GetChild( iNode, 0 ); + if ( mask & 1 ) + { + ++maxIndex; + nodeList[maxIndex] = child; + } + if ( mask & 2 ) + { + ++maxIndex; + nodeList[maxIndex] = child+1; + } + if ( mask & 4 ) + { + ++maxIndex; + nodeList[maxIndex] = child+2; + } + if ( mask & 8 ) + { + ++maxIndex; + nodeList[maxIndex] = child+3; + } + Assert(maxIndex < MAX_AABB_LIST); + } + } + } + return nTriCount; +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBTree_IntersectAABB( const Vector &absMins, const Vector &absMaxs ) +{ + // Check for hull test. + if ( CheckFlags( CCoreDispInfo::SURF_NOHULL_COLL ) ) + return false; + + cplane_t plane; + Vector center = 0.5f *(absMins + absMaxs); + Vector extents = absMaxs - center; + + int nodeList[MAX_AABB_LIST]; + nodeList[0] = 0; + int listIndex = 0; + int maxIndex = 0; + + // NOTE: This part is loop invariant - should be hoisted up as far as possible + FourVectors mins0; + mins0.DuplicateVector(absMins); + FourVectors maxs0; + maxs0.DuplicateVector(absMaxs); + FourVectors rayExtents; + while ( listIndex <= maxIndex ) + { + int iNode = nodeList[listIndex]; + listIndex++; + // the rest are all leaves + if ( IsLeafNode(iNode) ) + { + VPROF("Tris"); + for ( --listIndex; listIndex <= maxIndex; listIndex++ ) + { + int leafIndex = nodeList[listIndex] - m_nodes.Count(); + CDispCollTri *pTri0 = &m_aTris[m_leaves[leafIndex].m_tris[0]]; + CDispCollTri *pTri1 = &m_aTris[m_leaves[leafIndex].m_tris[1]]; + + VectorCopy( pTri0->m_vecNormal, plane.normal ); + plane.dist = pTri0->m_flDist; + plane.signbits = pTri0->m_ucSignBits; + plane.type = pTri0->m_ucPlaneType; + + if ( IsBoxIntersectingTriangle( center, extents, + m_aVerts[pTri0->GetVert( 0 )], + m_aVerts[pTri0->GetVert( 2 )], + m_aVerts[pTri0->GetVert( 1 )], + plane, 0.0f ) ) + return true; + VectorCopy( pTri1->m_vecNormal, plane.normal ); + plane.dist = pTri1->m_flDist; + plane.signbits = pTri1->m_ucSignBits; + plane.type = pTri1->m_ucPlaneType; + + if ( IsBoxIntersectingTriangle( center, extents, + m_aVerts[pTri1->GetVert( 0 )], + m_aVerts[pTri1->GetVert( 2 )], + m_aVerts[pTri1->GetVert( 1 )], + plane, 0.0f ) ) + return true; + } + break; + } + else + { + const CDispCollNode &node = m_nodes[iNode]; + int mask = IntersectFourBoxPairs( mins0, maxs0, node.m_mins, node.m_maxs ); + if ( mask ) + { + int child = Nodes_GetChild( iNode, 0 ); + if ( mask & 1 ) + { + ++maxIndex; + nodeList[maxIndex] = child; + } + if ( mask & 2 ) + { + ++maxIndex; + nodeList[maxIndex] = child+1; + } + if ( mask & 4 ) + { + ++maxIndex; + nodeList[maxIndex] = child+2; + } + if ( mask & 8 ) + { + ++maxIndex; + nodeList[maxIndex] = child+3; + } + Assert(maxIndex < MAX_AABB_LIST); + } + } + } + + // no collision + return false; +} + +static const Vector g_Vec3DispCollEpsilons(DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON,DISPCOLL_DIST_EPSILON); +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBTree_SweepAABB( const Ray_t &ray, const Vector &vecInvDelta, CBaseTrace *pTrace ) +{ + VPROF( "DispHullTest" ); + // VPROF_BUDGET( "DispHullTraces", VPROF_BUDGETGROUP_DISP_HULLTRACES ); + // Check for hull test. + if ( CheckFlags( CCoreDispInfo::SURF_NOHULL_COLL ) ) + return false; + + // Test ray against the triangles in the list. + Vector rayDir; + VectorCopy( ray.m_Delta, rayDir ); + VectorNormalize( rayDir ); + // Save fraction. + float flFrac = pTrace->fraction; + + rayleaflist_t list; + // NOTE: This part is loop invariant - should be hoisted up as far as possible + list.invDelta.DuplicateVector(vecInvDelta); + list.rayStart.DuplicateVector(ray.m_Start); + Vector ext = ray.m_Extents + g_Vec3DispCollEpsilons; + list.rayExtents.DuplicateVector(ext); + int listIndex = BuildRayLeafList( 0, list ); + + if ( listIndex <= list.maxIndex ) + { + LockCache(); + for ( ; listIndex <= list.maxIndex; listIndex++ ) + { + int leafIndex = list.nodeList[listIndex] - m_nodes.Count(); + int iTri0 = m_leaves[leafIndex].m_tris[0]; + int iTri1 = m_leaves[leafIndex].m_tris[1]; + CDispCollTri *pTri0 = &m_aTris[iTri0]; + CDispCollTri *pTri1 = &m_aTris[iTri1]; + + SweepAABBTriIntersect( ray, rayDir, iTri0, pTri0, pTrace ); + SweepAABBTriIntersect( ray, rayDir, iTri1, pTri1, pTrace ); + } + UnlockCache(); + } + + // Collision. + if ( pTrace->fraction < flFrac ) + return true; + + // No collision. + return false; +} + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +bool CDispCollTree::ResolveRayPlaneIntersect( float flStart, float flEnd, const Vector &vecNormal, float flDist, CDispCollHelper *pHelper ) +{ + if( ( flStart > 0.0f ) && ( flEnd > 0.0f ) ) + return false; + + if( ( flStart < 0.0f ) && ( flEnd < 0.0f ) ) + return true; + + float flDenom = flStart - flEnd; + bool bDenomIsZero = ( flDenom == 0.0f ); + if( ( flStart >= 0.0f ) && ( flEnd <= 0.0f ) ) + { + // Find t - the parametric distance along the trace line. + float t = ( !bDenomIsZero ) ? ( flStart - DISPCOLL_DIST_EPSILON ) / flDenom : 0.0f; + if( t > pHelper->m_flStartFrac ) + { + pHelper->m_flStartFrac = t; + VectorCopy( vecNormal, pHelper->m_vecImpactNormal ); + pHelper->m_flImpactDist = flDist; + } + } + else + { + // Find t - the parametric distance along the trace line. + float t = ( !bDenomIsZero ) ? ( flStart + DISPCOLL_DIST_EPSILON ) / flDenom : 0.0f; + if( t < pHelper->m_flEndFrac ) + { + pHelper->m_flEndFrac = t; + } + } + + return true; +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline bool CDispCollTree::FacePlane( const Ray_t &ray, const Vector &rayDir, CDispCollTri *pTri, CDispCollHelper *pHelper ) +{ + // Calculate the closest point on box to plane (get extents in that direction). + Vector vecExtent; + CalcClosestExtents( pTri->m_vecNormal, ray.m_Extents, vecExtent ); + + float flExpandDist = pTri->m_flDist - pTri->m_vecNormal.Dot( vecExtent ); + + float flStart = pTri->m_vecNormal.Dot( ray.m_Start ) - flExpandDist; + float flEnd = pTri->m_vecNormal.Dot( ( ray.m_Start + ray.m_Delta ) ) - flExpandDist; + + return ResolveRayPlaneIntersect( flStart, flEnd, pTri->m_vecNormal, pTri->m_flDist, pHelper ); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool FORCEINLINE CDispCollTree::AxisPlanesXYZ( const Ray_t &ray, CDispCollTri *pTri, CDispCollHelper *pHelper ) +{ + static const TableVector g_ImpactNormalVecs[2][3] = + { + { + { -1, 0, 0 }, + { 0, -1, 0 }, + { 0, 0, -1 }, + }, + + { + { 1, 0, 0 }, + { 0, 1, 0 }, + { 0, 0, 1 }, + } + }; + + Vector vecImpactNormal; + float flDist, flExpDist, flStart, flEnd; + + int iAxis; + for ( iAxis = 2; iAxis >= 0; --iAxis ) + { + const float rayStart = ray.m_Start[iAxis]; + const float rayExtent = ray.m_Extents[iAxis]; + const float rayDelta = ray.m_Delta[iAxis]; + + // Min + flDist = m_aVerts[pTri->GetVert(pTri->GetMin(iAxis))][iAxis]; + flExpDist = flDist - rayExtent; + flStart = flExpDist - rayStart; + flEnd = flStart - rayDelta; + + if ( !ResolveRayPlaneIntersect( flStart, flEnd, g_ImpactNormalVecs[0][iAxis], flDist, pHelper ) ) + return false; + + // Max + flDist = m_aVerts[pTri->GetVert(pTri->GetMax(iAxis))][iAxis]; + flExpDist = flDist + rayExtent; + flStart = rayStart - flExpDist; + flEnd = flStart + rayDelta; + + if ( !ResolveRayPlaneIntersect( flStart, flEnd, g_ImpactNormalVecs[1][iAxis], flDist, pHelper ) ) + return false; + } + + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: Testing! +//----------------------------------------------------------------------------- +void CDispCollTree::Cache_Create( CDispCollTri *pTri, int iTri ) +{ + MEM_ALLOC_CREDIT(); + Vector *pVerts[3]; + pVerts[0] = &m_aVerts[pTri->GetVert( 0 )]; + pVerts[1] = &m_aVerts[pTri->GetVert( 1 )]; + pVerts[2] = &m_aVerts[pTri->GetVert( 2 )]; + + CDispCollTriCache *pCache = &m_aTrisCache[iTri]; + + Vector vecEdge; + + // Edge 1 + VectorSubtract( *pVerts[1], *pVerts[0], vecEdge ); + Cache_EdgeCrossAxisX( vecEdge, *pVerts[0], *pVerts[2], pTri, pCache->m_iCrossX[0] ); + Cache_EdgeCrossAxisY( vecEdge, *pVerts[0], *pVerts[2], pTri, pCache->m_iCrossY[0] ); + Cache_EdgeCrossAxisZ( vecEdge, *pVerts[0], *pVerts[2], pTri, pCache->m_iCrossZ[0] ); + + // Edge 2 + VectorSubtract( *pVerts[2], *pVerts[1], vecEdge ); + Cache_EdgeCrossAxisX( vecEdge, *pVerts[1], *pVerts[0], pTri, pCache->m_iCrossX[1] ); + Cache_EdgeCrossAxisY( vecEdge, *pVerts[1], *pVerts[0], pTri, pCache->m_iCrossY[1] ); + Cache_EdgeCrossAxisZ( vecEdge, *pVerts[1], *pVerts[0], pTri, pCache->m_iCrossZ[1] ); + + // Edge 3 + VectorSubtract( *pVerts[0], *pVerts[2], vecEdge ); + Cache_EdgeCrossAxisX( vecEdge, *pVerts[2], *pVerts[1], pTri, pCache->m_iCrossX[2] ); + Cache_EdgeCrossAxisY( vecEdge, *pVerts[2], *pVerts[1], pTri, pCache->m_iCrossY[2] ); + Cache_EdgeCrossAxisZ( vecEdge, *pVerts[2], *pVerts[1], pTri, pCache->m_iCrossZ[2] ); +} + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +int CDispCollTree::AddPlane( const Vector &vecNormal ) +{ + UtlHashHandle_t handle; + DispCollPlaneIndex_t planeIndex; + bool bDidInsert; + + planeIndex.vecPlane = vecNormal; + planeIndex.index = m_aEdgePlanes.Count(); + + handle = g_DispCollPlaneIndexHash.Insert( planeIndex, &bDidInsert ); + + if ( !bDidInsert ) + { + DispCollPlaneIndex_t &existingEntry = g_DispCollPlaneIndexHash[handle]; + if ( existingEntry.vecPlane == vecNormal ) + { + return existingEntry.index; + } + else + { + return ( existingEntry.index | 0x8000 ); + } + } + + return m_aEdgePlanes.AddToTail( vecNormal ); +} + +//----------------------------------------------------------------------------- +// Purpose: +// NOTE: The plane distance get stored in the normal x position since it isn't +// used. +//----------------------------------------------------------------------------- +bool CDispCollTree::Cache_EdgeCrossAxisX( const Vector &vecEdge, const Vector &vecOnEdge, + const Vector &vecOffEdge, CDispCollTri *pTri, + unsigned short &iPlane ) +{ + // Calculate the normal - edge x axisX = ( 0.0, edgeZ, -edgeY ) + Vector vecNormal( 0.0f, vecEdge.z, -vecEdge.y ); + VectorNormalize( vecNormal ); + + // Check for zero length normals. + if( ( vecNormal.y == 0.0f ) || ( vecNormal.z == 0.0f ) ) + { + iPlane = DISPCOLL_NORMAL_UNDEF; + return false; + } + +// if ( pTri->m_vecNormal.Dot( vecNormal ) ) +// { +// iPlane = DISPCOLL_NORMAL_UNDEF; +// return false; +// } + + // Finish the plane definition - get distance. + float flDist = ( vecNormal.y * vecOnEdge.y ) + ( vecNormal.z * vecOnEdge.z ); + + // Special case the point off edge in plane + float flOffDist = ( vecNormal.y * vecOffEdge.y ) + ( vecNormal.z * vecOffEdge.z ); + if ( !( FloatMakePositive( flOffDist - flDist ) < DISPCOLL_DIST_EPSILON ) && ( flOffDist > flDist ) ) + { + // Adjust plane facing - triangle should be behind the plane. + vecNormal.x = -flDist; + vecNormal.y = -vecNormal.y; + vecNormal.z = -vecNormal.z; + } + else + { + vecNormal.x = flDist; + } + + // Add edge plane to edge plane list. + iPlane = static_cast( AddPlane( vecNormal ) ); + + // Created the cached edge. + return true; +} + +//----------------------------------------------------------------------------- +// Purpose: +// NOTE: The plane distance get stored in the normal y position since it isn't +// used. +//----------------------------------------------------------------------------- +bool CDispCollTree::Cache_EdgeCrossAxisY( const Vector &vecEdge, const Vector &vecOnEdge, + const Vector &vecOffEdge, CDispCollTri *pTri, + unsigned short &iPlane ) +{ + // Calculate the normal - edge x axisY = ( -edgeZ, 0.0, edgeX ) + Vector vecNormal( -vecEdge.z, 0.0f, vecEdge.x ); + VectorNormalize( vecNormal ); + + // Check for zero length normals + if( ( vecNormal.x == 0.0f ) || ( vecNormal.z == 0.0f ) ) + { + iPlane = DISPCOLL_NORMAL_UNDEF; + return false; + } + +// if ( pTri->m_vecNormal.Dot( vecNormal ) ) +// { +// iPlane = DISPCOLL_NORMAL_UNDEF; +// return false; +// } + + // Finish the plane definition - get distance. + float flDist = ( vecNormal.x * vecOnEdge.x ) + ( vecNormal.z * vecOnEdge.z ); + + // Special case the point off edge in plane + float flOffDist = ( vecNormal.x * vecOffEdge.x ) + ( vecNormal.z * vecOffEdge.z ); + if ( !( FloatMakePositive( flOffDist - flDist ) < DISPCOLL_DIST_EPSILON ) && ( flOffDist > flDist ) ) + { + // Adjust plane facing if necessay - triangle should be behind the plane. + vecNormal.x = -vecNormal.x; + vecNormal.y = -flDist; + vecNormal.z = -vecNormal.z; + } + else + { + vecNormal.y = flDist; + } + + // Add edge plane to edge plane list. + iPlane = static_cast( AddPlane( vecNormal ) ); + + // Created the cached edge. + return true; +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::Cache_EdgeCrossAxisZ( const Vector &vecEdge, const Vector &vecOnEdge, + const Vector &vecOffEdge, CDispCollTri *pTri, + unsigned short &iPlane ) +{ + // Calculate the normal - edge x axisY = ( edgeY, -edgeX, 0.0 ) + Vector vecNormal( vecEdge.y, -vecEdge.x, 0.0f ); + VectorNormalize( vecNormal ); + + // Check for zero length normals + if( ( vecNormal.x == 0.0f ) || ( vecNormal.y == 0.0f ) ) + { + iPlane = DISPCOLL_NORMAL_UNDEF; + return false; + } + +// if ( pTri->m_vecNormal.Dot( vecNormal ) ) +// { +// iPlane = DISPCOLL_NORMAL_UNDEF; +// return false; +// } + + // Finish the plane definition - get distance. + float flDist = ( vecNormal.x * vecOnEdge.x ) + ( vecNormal.y * vecOnEdge.y ); + + // Special case the point off edge in plane + float flOffDist = ( vecNormal.x * vecOffEdge.x ) + ( vecNormal.y * vecOffEdge.y ); + if ( !( FloatMakePositive( flOffDist - flDist ) < DISPCOLL_DIST_EPSILON ) && ( flOffDist > flDist ) ) + { + // Adjust plane facing if necessay - triangle should be behind the plane. + vecNormal.x = -vecNormal.x; + vecNormal.y = -vecNormal.y; + vecNormal.z = -flDist; + } + else + { + vecNormal.z = flDist; + } + + // Add edge plane to edge plane list. + iPlane = static_cast( AddPlane( vecNormal ) ); + + // Created the cached edge. + return true; +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +template +bool CDispCollTree::EdgeCrossAxis( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) +{ + if ( iPlane == DISPCOLL_NORMAL_UNDEF ) + return true; + + // Get the edge plane. + Vector vecNormal; + if ( ( iPlane & 0x8000 ) != 0 ) + { + VectorCopy( m_aEdgePlanes[(iPlane&0x7fff)], vecNormal ); + vecNormal.Negate(); + } + else + { + VectorCopy( m_aEdgePlanes[iPlane], vecNormal ); + } + + const int OTHER_AXIS1 = ( AXIS + 1 ) % 3; + const int OTHER_AXIS2 = ( AXIS + 2 ) % 3; + + // Get the pland distance are "fix" the normal. + float flDist = vecNormal[AXIS]; + vecNormal[AXIS] = 0.0f; + + // Calculate the closest point on box to plane (get extents in that direction). + Vector vecExtent; + //vecExtent[AXIS] = 0.0f; + vecExtent[OTHER_AXIS1] = ( vecNormal[OTHER_AXIS1] < 0.0f ) ? ray.m_Extents[OTHER_AXIS1] : -ray.m_Extents[OTHER_AXIS1]; + vecExtent[OTHER_AXIS2] = ( vecNormal[OTHER_AXIS2] < 0.0f ) ? ray.m_Extents[OTHER_AXIS2] : -ray.m_Extents[OTHER_AXIS2]; + + // Expand the plane by the extents of the box to reduce the swept box/triangle + // test to a ray/extruded triangle test (one of the triangles extruded planes + // was just calculated above). + Vector vecEnd; + vecEnd[AXIS] = 0; + vecEnd[OTHER_AXIS1] = ray.m_Start[OTHER_AXIS1] + ray.m_Delta[OTHER_AXIS1]; + vecEnd[OTHER_AXIS2] = ray.m_Start[OTHER_AXIS2] + ray.m_Delta[OTHER_AXIS2]; + + float flExpandDist = flDist - ( ( vecNormal[OTHER_AXIS1] * vecExtent[OTHER_AXIS1] ) + ( vecNormal[OTHER_AXIS2] * vecExtent[OTHER_AXIS2] ) ); + float flStart = ( vecNormal[OTHER_AXIS1] * ray.m_Start[OTHER_AXIS1] ) + ( vecNormal[OTHER_AXIS2] * ray.m_Start[OTHER_AXIS2] ) - flExpandDist; + float flEnd = ( vecNormal[OTHER_AXIS1] * vecEnd[OTHER_AXIS1] ) + ( vecNormal[OTHER_AXIS2] * vecEnd[OTHER_AXIS2] ) - flExpandDist; + + return ResolveRayPlaneIntersect( flStart, flEnd, vecNormal, flDist, pHelper ); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline bool CDispCollTree::EdgeCrossAxisX( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) +{ + return EdgeCrossAxis<0>( ray, iPlane, pHelper ); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline bool CDispCollTree::EdgeCrossAxisY( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) +{ + return EdgeCrossAxis<1>( ray, iPlane, pHelper ); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline bool CDispCollTree::EdgeCrossAxisZ( const Ray_t &ray, unsigned short iPlane, CDispCollHelper *pHelper ) +{ + return EdgeCrossAxis<2>( ray, iPlane, pHelper ); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::SweepAABBTriIntersect( const Ray_t &ray, const Vector &rayDir, int iTri, CDispCollTri *pTri, CBaseTrace *pTrace ) +{ + // Init test data. + CDispCollHelper helper; + helper.m_flEndFrac = 1.0f; + helper.m_flStartFrac = DISPCOLL_INVALID_FRAC; + + // Make sure objects are traveling toward one another. + float flDistAlongNormal = pTri->m_vecNormal.Dot( ray.m_Delta ); + if( flDistAlongNormal > DISPCOLL_DIST_EPSILON ) + return; + + // Test against the axis planes. + if ( !AxisPlanesXYZ( ray, pTri, &helper ) ) + { + return; + } + + // + // There are 9 edge tests - edges 1, 2, 3 cross with the box edges (symmetry) 1, 2, 3. However, the box + // is axis-aligned resulting in axially directional edges -- thus each test is edges 1, 2, and 3 vs. + // axial planes x, y, and z + // + // There are potentially 9 more tests with edges, the edge's edges and the direction of motion! + // NOTE: I don't think these tests are necessary for a manifold surface. + // + + CDispCollTriCache *pCache = &m_aTrisCache[iTri]; + + // Edges 1-3, interleaved - axis tests are 2d tests + if ( !EdgeCrossAxisX( ray, pCache->m_iCrossX[0], &helper ) ) { return; } + if ( !EdgeCrossAxisX( ray, pCache->m_iCrossX[1], &helper ) ) { return; } + if ( !EdgeCrossAxisX( ray, pCache->m_iCrossX[2], &helper ) ) { return; } + + if ( !EdgeCrossAxisY( ray, pCache->m_iCrossY[0], &helper ) ) { return; } + if ( !EdgeCrossAxisY( ray, pCache->m_iCrossY[1], &helper ) ) { return; } + if ( !EdgeCrossAxisY( ray, pCache->m_iCrossY[2], &helper ) ) { return; } + + if ( !EdgeCrossAxisZ( ray, pCache->m_iCrossZ[0], &helper ) ) { return; } + if ( !EdgeCrossAxisZ( ray, pCache->m_iCrossZ[1], &helper ) ) { return; } + if ( !EdgeCrossAxisZ( ray, pCache->m_iCrossZ[2], &helper ) ) { return; } + + // Test against the triangle face plane. + if ( !FacePlane( ray, rayDir, pTri, &helper ) ) + return; + + if ( ( helper.m_flStartFrac < helper.m_flEndFrac ) || ( FloatMakePositive( helper.m_flStartFrac - helper.m_flEndFrac ) < 0.001f ) ) + { + if ( ( helper.m_flStartFrac != DISPCOLL_INVALID_FRAC ) && ( helper.m_flStartFrac < pTrace->fraction ) ) + { + // Clamp -- shouldn't really ever be here!??? + if ( helper.m_flStartFrac < 0.0f ) + { + helper.m_flStartFrac = 0.0f; + } + + pTrace->fraction = helper.m_flStartFrac; + VectorCopy( helper.m_vecImpactNormal, pTrace->plane.normal ); + pTrace->plane.dist = helper.m_flImpactDist; + pTrace->dispFlags = pTri->m_uiFlags; + } + } +} + +//----------------------------------------------------------------------------- +// Purpose: constructor +//----------------------------------------------------------------------------- +CDispCollTree::CDispCollTree() +{ + m_nPower = 0; + m_nFlags = 0; + + for ( int iPoint = 0; iPoint < 4; ++iPoint ) + { + m_vecSurfPoints[iPoint].Init(); + } + m_nContents = -1; + m_nSurfaceProps[0] = 0; + m_nSurfaceProps[1] = 0; + + m_vecStabDir.Init(); + m_mins.Init( FLT_MAX, FLT_MAX, FLT_MAX ); + m_maxs.Init( -FLT_MAX, -FLT_MAX, -FLT_MAX ); + + m_iCounter = 0; + + m_aVerts.Purge(); + m_aTris.Purge(); + m_aEdgePlanes.Purge(); +#ifdef ENGINE_DLL + m_hCache = INVALID_MEMHANDLE; +#endif +} + +//----------------------------------------------------------------------------- +// Purpose: deconstructor +//----------------------------------------------------------------------------- +CDispCollTree::~CDispCollTree() +{ +#ifdef ENGINE_DLL + if ( m_hCache != INVALID_MEMHANDLE ) + g_DispCollTriCache.DestroyResource( m_hCache ); +#endif + m_aVerts.Purge(); + m_aTris.Purge(); + m_aEdgePlanes.Purge(); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::Create( CCoreDispInfo *pDisp ) +{ + // Create the AABB Tree. + return AABBTree_Create( pDisp ); +} + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::PointInBounds( const Vector &vecBoxCenter, const Vector &vecBoxMin, + const Vector &vecBoxMax, bool bPoint ) +{ + // Point test inside bounds. + if( bPoint ) + { + return IsPointInBox( vecBoxCenter, m_mins, m_maxs ); + } + + // Box test inside bounds + Vector vecExtents; + VectorSubtract( vecBoxMax, vecBoxMin, vecExtents ); + vecExtents *= 0.5f; + + Vector vecExpandBounds[2]; + vecExpandBounds[0] = m_mins - vecExtents; + vecExpandBounds[1] = m_maxs + vecExtents; + + return IsPointInBox( vecBoxCenter, vecExpandBounds[0], vecExpandBounds[1] ); +} + +void CDispCollTree::GetVirtualMeshList( virtualmeshlist_t *pList ) +{ + int i; + int triangleCount = GetTriSize(); + pList->indexCount = triangleCount * 3; + pList->triangleCount = triangleCount; + pList->vertexCount = m_aVerts.Count(); + pList->pVerts = m_aVerts.Base(); + pList->pHull = NULL; + pList->surfacePropsIndex = GetSurfaceProps(0); + int index = 0; + for ( i = 0 ; i < triangleCount; i++ ) + { + pList->indices[index+0] = m_aTris[i].GetVert(0); + pList->indices[index+1] = m_aTris[i].GetVert(1); + pList->indices[index+2] = m_aTris[i].GetVert(2); + index += 3; + } +} + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +#ifdef ENGINE_DLL +static int g_nTrees; +#endif +CDispCollTree *DispCollTrees_Alloc( int count ) +{ + CDispCollTree *pTrees = NULL; +#ifdef ENGINE_DLL + pTrees = (CDispCollTree *)Hunk_Alloc( count * sizeof(CDispCollTree), false ); + g_nTrees = count; + for ( int i = 0; i < g_nTrees; i++ ) + { + Construct( pTrees + i ); + } +#else + pTrees = new CDispCollTree[count]; +#endif + if( !pTrees ) + return NULL; + + for ( int i = 0; i < count; i++ ) + { + pTrees[i].m_iCounter = i; + } + return pTrees; +} + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +void DispCollTrees_Free( CDispCollTree *pTrees ) +{ +#ifdef ENGINE_DLL + for ( int i = 0; i < g_nTrees; i++ ) + { + Destruct( pTrees + i ); + } + g_nTrees = 0; +#else + if( pTrees ) + { + delete [] pTrees; + pTrees = NULL; + } +#endif +} -- cgit v1.2.3