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.cpp | 3988 ++++++++++++++++++++++---------------------- 1 file changed, 1994 insertions(+), 1994 deletions(-) (limited to 'mp/src/public/dispcoll.cpp') diff --git a/mp/src/public/dispcoll.cpp b/mp/src/public/dispcoll.cpp index d8dd85bc..3583d4a2 100644 --- a/mp/src/public/dispcoll.cpp +++ b/mp/src/public/dispcoll.cpp @@ -1,1994 +1,1994 @@ -//========= Copyright Valve Corporation, All rights reserved. ============// -// -// Purpose: -// -// $NoKeywords: $ -//=============================================================================// - -#include "BuildDisp.h" -#include "DispColl.h" -#include "tier0/dbg.h" - -//============================================================================= - -const float CDispCollTree::COLLISION_EPSILON = 0.01f; -const float CDispCollTree::ONE_MINUS_COLLISION_EPSILON = 1.0f - COLLISION_EPSILON; - -//============================================================================= -// -// Displacement Collision Triangle Functions -// - - -//----------------------------------------------------------------------------- -// Purpose: initialize the displacement triangles -//----------------------------------------------------------------------------- -void CDispCollTri::Init( void ) -{ - for( int i = 0; i < 3; i++ ) - { - m_Points[i].x = 0.0f; m_Points[i].y = 0.0f; m_Points[i].z = 0.0f; - m_PointNormals[i].x = 0.0f; m_PointNormals[i].y = 0.0f; m_PointNormals[i].z = 0.0f; - } - - m_Normal.x = 0.0f; m_Normal.y = 0.0f; m_Normal.z = 0.0f; - m_Distance = 0.0f; - - m_ProjAxes[0] = -1; - m_ProjAxes[1] = -1; - - m_bIntersect = false; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline void CDispCollTri::SetPoint( int index, Vector const &vert ) -{ - Assert( index >= 0 ); - Assert( index < 3 ); - - m_Points[index].x = vert[0]; - m_Points[index].y = vert[1]; - m_Points[index].z = vert[2]; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline void CDispCollTri::SetPointNormal( int index, Vector const &normal ) -{ - Assert( index >= 0 ); - Assert( index < 3 ); - - m_PointNormals[index].x = normal[0]; - m_PointNormals[index].y = normal[1]; - m_PointNormals[index].z = normal[2]; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTri::CalcPlane( void ) -{ - // - // calculate the plane normal and distance - // - Vector segment1, segment2, cross; - - segment1 = m_Points[1] - m_Points[0]; - segment2 = m_Points[2] - m_Points[0]; - cross = segment1.Cross( segment2 ); - m_Normal = cross; - VectorNormalize(m_Normal); - - m_Distance = m_Normal.Dot( m_Points[0] ); - - // - // calculate the projection axes - // - if( FloatMakePositive( m_Normal[0] ) > FloatMakePositive( m_Normal[1] ) ) - { - if( FloatMakePositive( m_Normal[0] ) > FloatMakePositive( m_Normal[2] ) ) - { - m_ProjAxes[0] = 1; - m_ProjAxes[1] = 2; - } - else - { - m_ProjAxes[0] = 0; - m_ProjAxes[1] = 1; - } - } - else - { - if( FloatMakePositive( m_Normal[1] ) > FloatMakePositive( m_Normal[2] ) ) - { - m_ProjAxes[0] = 0; - m_ProjAxes[1] = 2; - } - else - { - m_ProjAxes[0] = 0; - m_ProjAxes[1] = 1; - } - } -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline void CDispCollTri::SetIntersect( bool bIntersect ) -{ - m_bIntersect = bIntersect; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline bool CDispCollTri::IsIntersect( void ) -{ - return m_bIntersect; -} - - -//============================================================================= -// -// Displacement Collision Node Functions -// - - -//----------------------------------------------------------------------------- -// Purpose: constructor -//----------------------------------------------------------------------------- -CDispCollNode::CDispCollNode() -{ - m_Bounds[0].x = m_Bounds[0].y = m_Bounds[0].z = 99999.9f; - m_Bounds[1].x = m_Bounds[1].y = m_Bounds[1].z = -99999.9f; - - m_Tris[0].Init(); - m_Tris[1].Init(); - - m_bIsLeaf = false; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline bool CDispCollNode::IsLeaf( void ) -{ - return m_bIsLeaf; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline void CDispCollNode::SetBounds( Vector const &bMin, Vector const &bMax ) -{ - m_Bounds[0] = bMin; - m_Bounds[1] = bMax; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline void CDispCollNode::GetBounds( Vector &bMin, Vector &bMax ) -{ - bMin = m_Bounds[0]; - bMax = m_Bounds[1]; -} - - -//============================================================================= -// -// Displacement Collision Tree Functions -// - -//----------------------------------------------------------------------------- -// Purpose: constructor -//----------------------------------------------------------------------------- -CDispCollTree::CDispCollTree() -{ - m_Power = 0; - - m_NodeCount = 0; - m_pNodes = NULL; - - InitAABBData(); -} - - -//----------------------------------------------------------------------------- -// Purpose: deconstructor -//----------------------------------------------------------------------------- -CDispCollTree::~CDispCollTree() -{ - FreeNodes(); -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::InitAABBData( void ) -{ - m_AABBNormals[0].x = -1.0f; m_AABBNormals[0].y = 0.0f; m_AABBNormals[0].z = 0.0f; - m_AABBNormals[1].x = 1.0f; m_AABBNormals[1].y = 0.0f; m_AABBNormals[1].z = 0.0f; - - m_AABBNormals[2].x = 0.0f; m_AABBNormals[2].y = -1.0f; m_AABBNormals[2].z = 0.0f; - m_AABBNormals[3].x = 0.0f; m_AABBNormals[3].y = 1.0f; m_AABBNormals[3].z = 0.0f; - - m_AABBNormals[4].x = 0.0f; m_AABBNormals[4].y = 0.0f; m_AABBNormals[4].z = -1.0f; - m_AABBNormals[5].x = 0.0f; m_AABBNormals[5].y = 0.0f; m_AABBNormals[5].z = 1.0f; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::CalcBounds( CDispCollNode *pNode, int nodeIndex ) -{ - Vector bounds[2]; - bounds[0].Init( 99999.9f, 99999.9f, 99999.9f ); - bounds[1].Init( -99999.9f, -99999.9f, -99999.9f ); - - // - // handle leaves differently -- bounding volume defined by triangles - // - if( pNode->IsLeaf() ) - { - for( int i = 0; i < 2; i++ ) - { - for( int j = 0; j < 3; j++ ) - { - // - // minimum - // - if( bounds[0].x > pNode->m_Tris[i].m_Points[j].x ) { bounds[0].x = pNode->m_Tris[i].m_Points[j].x; } - if( bounds[0].y > pNode->m_Tris[i].m_Points[j].y ) { bounds[0].y = pNode->m_Tris[i].m_Points[j].y; } - if( bounds[0].z > pNode->m_Tris[i].m_Points[j].z ) { bounds[0].z = pNode->m_Tris[i].m_Points[j].z; } - - // - // maximum - // - if( bounds[1].x < pNode->m_Tris[i].m_Points[j].x ) { bounds[1].x = pNode->m_Tris[i].m_Points[j].x; } - if( bounds[1].y < pNode->m_Tris[i].m_Points[j].y ) { bounds[1].y = pNode->m_Tris[i].m_Points[j].y; } - if( bounds[1].z < pNode->m_Tris[i].m_Points[j].z ) { bounds[1].z = pNode->m_Tris[i].m_Points[j].z; } - } - } - } - // - // bounding volume defined by maxima and minima of children volumes - // - else - { - for( int i = 0; i < 4; i++ ) - { - int childIndex = GetChildNode( nodeIndex, i ); - CDispCollNode *pChildNode = &m_pNodes[childIndex]; - - Vector childBounds[2]; - pChildNode->GetBounds( childBounds[0], childBounds[1] ); - - // - // minimum - // - if( bounds[0].x > childBounds[0].x ) { bounds[0].x = childBounds[0].x; } - if( bounds[0].y > childBounds[0].y ) { bounds[0].y = childBounds[0].y; } - if( bounds[0].z > childBounds[0].z ) { bounds[0].z = childBounds[0].z; } - - // - // maximum - // - if( bounds[1].x < childBounds[1].x ) { bounds[1].x = childBounds[1].x; } - if( bounds[1].y < childBounds[1].y ) { bounds[1].y = childBounds[1].y; } - if( bounds[1].z < childBounds[1].z ) { bounds[1].z = childBounds[1].z; } - } - } - - pNode->SetBounds( bounds[0], bounds[1] ); -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::CreateNodes_r( CCoreDispInfo *pDisp, int nodeIndex, int termLevel ) -{ - int nodeLevel = GetNodeLevel( nodeIndex ); - - // - // terminating condition -- set node info (leaf or otherwise) - // - if( nodeLevel == termLevel ) - { - CDispCollNode *pNode = &m_pNodes[nodeIndex]; - CalcBounds( pNode, nodeIndex ); - - return; - } - - // - // recurse into children - // - for( int i = 0; i < 4; i++ ) - { - CreateNodes_r( pDisp, GetChildNode( nodeIndex, i ), termLevel ); - } -} - - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::CreateNodes( CCoreDispInfo *pDisp ) -{ - // - // create all nodes in tree - // - int power = pDisp->GetPower() + 1; - for( int level = power; level > 0; level-- ) - { - CreateNodes_r( pDisp, 0 /* rootIndex */, level ); - } -} - - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -int CDispCollTree::GetNodeIndexFromComponents( int x, int y ) -{ - int index = 0; - - // Interleave bits from the x and y values to create the index: - - for( int shift = 0; x != 0; shift += 2, x >>= 1 ) - { - index |= ( x & 1 ) << shift; - } - - for( shift = 1; y != 0; shift += 2, y >>= 1 ) - { - index |= ( y & 1 ) << shift; - } - - return index; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::InitLeaves( CCoreDispInfo *pDisp ) -{ - // - // get power and width and displacement surface - // - int power = pDisp->GetPower(); - int width = pDisp->GetWidth(); - - // - // get leaf indices - // - int startIndex = CalcNodeCount( power - 1 ); - int endIndex = CalcNodeCount( power ); - - for( int index = startIndex; index < endIndex; index++ ) - { - // - // create triangles at leaves - // - int x = ( index - startIndex ) % ( width - 1 ); - int y = ( index - startIndex ) / ( width - 1 ); - - int nodeIndex = GetNodeIndexFromComponents( x, y ); - nodeIndex += startIndex; - - Vector vert; - Vector normal; - - // - // tri 1 - // - pDisp->GetVert( x + ( y * width ), vert ); - pDisp->GetNormal( x + ( y * width ), normal ); - m_pNodes[nodeIndex].m_Tris[0].SetPoint( 0, vert ); - m_pNodes[nodeIndex].m_Tris[0].SetPointNormal( 0, normal ); - - pDisp->GetVert( x + ( ( y + 1 ) * width ), vert ); - pDisp->GetNormal( x + ( ( y + 1 ) * width ), normal ); - m_pNodes[nodeIndex].m_Tris[0].SetPoint( 1, vert ); - m_pNodes[nodeIndex].m_Tris[0].SetPointNormal( 1, normal ); - - pDisp->GetVert( ( x + 1 ) + ( y * width ), vert ); - pDisp->GetNormal( ( x + 1 ) + ( y * width ), normal ); - m_pNodes[nodeIndex].m_Tris[0].SetPoint( 2, vert ); - m_pNodes[nodeIndex].m_Tris[0].SetPointNormal( 2, normal ); - - m_pNodes[nodeIndex].m_Tris[0].CalcPlane(); - - // - // tri 2 - // - pDisp->GetVert( ( x + 1 ) + ( y * width ), vert ); - pDisp->GetNormal( ( x + 1 ) + ( y * width ), normal ); - m_pNodes[nodeIndex].m_Tris[1].SetPoint( 0, vert ); - m_pNodes[nodeIndex].m_Tris[1].SetPointNormal( 0, normal ); - - pDisp->GetVert( x + ( ( y + 1 ) * width ), vert ); - pDisp->GetNormal( x + ( ( y + 1 ) * width ), normal ); - m_pNodes[nodeIndex].m_Tris[1].SetPoint( 1, vert ); - m_pNodes[nodeIndex].m_Tris[1].SetPointNormal( 1, normal ); - - pDisp->GetVert( ( x + 1 ) + ( ( y + 1 ) * width ), vert ); - pDisp->GetNormal( ( x + 1 ) + ( ( y + 1 ) * width ), normal ); - m_pNodes[nodeIndex].m_Tris[1].SetPoint( 2, vert ); - m_pNodes[nodeIndex].m_Tris[1].SetPointNormal( 2, normal ); - - m_pNodes[nodeIndex].m_Tris[1].CalcPlane(); - - // set node as leaf - m_pNodes[nodeIndex].m_bIsLeaf = true; - } -} - - -//----------------------------------------------------------------------------- -// Purpose: allocate and initialize the displacement collision tree -// Input: power - size of the displacement surface -// Output: bool - success? (true/false) -//----------------------------------------------------------------------------- -bool CDispCollTree::Create( CCoreDispInfo *pDisp ) -{ - // - // calculate the number of nodes needed given the size of the displacement - // - m_Power = pDisp->GetPower(); - m_NodeCount = CalcNodeCount( m_Power ); - - // - // allocate tree space - // - if( !AllocNodes( m_NodeCount ) ) - return false; - - // initialize leaves - InitLeaves( pDisp ); - - // create tree nodes - CreateNodes( pDisp ); - - // tree successfully created! - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: allocate memory for the displacement collision tree -// Input: nodeCount - number of nodes to allocate -// Output: bool - success? (true/false) -//----------------------------------------------------------------------------- -bool CDispCollTree::AllocNodes( int nodeCount ) -{ - // sanity check - Assert( nodeCount != 0 ); - - m_pNodes = new CDispCollNode[nodeCount]; - if( !m_pNodes ) - return false; - - // tree successfully allocated! - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: release allocated memory for displacement collision tree -//----------------------------------------------------------------------------- -void CDispCollTree::FreeNodes( void ) -{ - if( m_pNodes ) - { - delete [] m_pNodes; - m_pNodes = NULL; - } -} - - -//----------------------------------------------------------------------------- -// Purpose: calculate the number of tree nodes given the size of the -// displacement surface -// Input: power - size of the displacement surface -// Output: int - the number of tree nodes -//----------------------------------------------------------------------------- -inline int CDispCollTree::CalcNodeCount( int power ) -{ - // power range [2...4] - Assert( power > 0 ); - Assert( power < 5 ); - - return ( ( 1 << ( ( power + 1 ) << 1 ) ) / 3 ); -} - - -//----------------------------------------------------------------------------- -// Purpose: get the parent node index given the current node -// Input: nodeIndex - current node index -// Output: int - the index of the parent node -//----------------------------------------------------------------------------- -inline int CDispCollTree::GetParentNode( int nodeIndex ) -{ - // node range [0...m_NodeCount) - Assert( nodeIndex >= 0 ); - Assert( nodeIndex < m_NodeCount ); - - // ( nodeIndex - 1 ) / 4 - return ( ( nodeIndex - 1 ) >> 2 ); -} - - -//----------------------------------------------------------------------------- -// Purpose: get the child node index given the current node index and direction -// of the child (1 of 4) -// Input: nodeIndex - current node index -// direction - direction of the child ( [0...3] - SW, SE, NW, NE ) -// Output: int - the index of the child node -//----------------------------------------------------------------------------- -inline int CDispCollTree::GetChildNode( int nodeIndex, int direction ) -{ - // node range [0...m_NodeCount) - Assert( nodeIndex >= 0 ); - Assert( nodeIndex < m_NodeCount ); - - // ( nodeIndex * 4 ) + ( direction + 1 ) - return ( ( nodeIndex << 2 ) + ( direction + 1 ) ); -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -inline int CDispCollTree::GetNodeLevel( int nodeIndex ) -{ - // node range [0...m_NodeCount) - Assert( nodeIndex >= 0 ); - Assert( nodeIndex < m_NodeCount ); - - // level = 2^n + 1 - if( nodeIndex == 0 ) { return 1; } - if( nodeIndex < 5 ) { return 2; } - if( nodeIndex < 21 ) { return 3; } - if( nodeIndex < 85 ) { return 4; } - if( nodeIndex < 341 ) { return 5; } - - return -1; -} - - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -bool CDispCollTree::RayTriTest( Vector const &rayStart, Vector const &rayDir, float const rayLength, - CDispCollTri const *pTri, float *fraction ) -{ - const float DET_EPSILON = 0.001f; - const float DIST_EPSILON = 0.001f; - - // - // calculate the edges - // - Vector edge1 = pTri->m_Points[1] - pTri->m_Points[0]; - Vector edge2 = pTri->m_Points[2] - pTri->m_Points[0]; - -// Vector faceNormal = edge1.Cross( edge2 ); -// Vector normNormal = faceNormal.Normalize(); - - // - // calculate the triangle's determinant - // - Vector pVec = rayDir.Cross( edge2 ); - float det = pVec.Dot( edge1 ); - - // if determinant is zero -- ray lies in plane - if( ( det > -DET_EPSILON ) && ( det < DET_EPSILON ) ) - return false; - - // - // utility calculations - inverse determinant and distance from v0 to ray start - // - double invDet = 1.0f / det; - Vector tVec = rayStart - pTri->m_Points[0]; - - // - // calculate the U parameter and test bounds - // - double u = pVec.Dot( tVec ) * invDet; - if( ( u < 0.0f ) || ( u > 1.0f ) ) - return false; - - Vector qVec = tVec.Cross( edge1 ); - - // - // calculate the V parameter and test bounds - // - double v = qVec.Dot( rayDir ) * invDet; - if( ( v < 0.0f ) || ( ( u + v ) > 1.0f ) ) - return false; - - // calculate where ray intersects triangle - *fraction = qVec.Dot( edge2 ) * invDet; - *fraction /= rayLength; - - if( ( *fraction < DIST_EPSILON ) || ( *fraction > ( 1.0f - DIST_EPSILON ) ) ) - return false; - - return true; -} - - -//----------------------------------------------------------------------------- -//----------------------------------------------------------------------------- -bool CDispCollTree::RayTriListTest( CDispCollTreeTempData *pTemp, CDispCollData *pData ) -{ - // save starting fraction -- to test for collision - float startFraction = pData->m_Fraction; - - // - // calculate the ray - // - Vector seg = pData->m_EndPos - pData->m_StartPos; - Vector rayDir = seg; - float rayLength = VectorNormalize( rayDir ); - - // - // test ray against all triangles in list - // - for( int i = 0; i < pTemp->m_TriListCount; i++ ) - { - float fraction = 1.0f; - bool bResult = RayTriTest( pData->m_StartPos, rayDir, rayLength, pTemp->m_ppTriList[i], &fraction ); - if( !bResult ) - continue; - - if( pData->m_bOcclude ) - { - return true; - } - - if( fraction < pData->m_Fraction ) - { - pData->m_Fraction = fraction; - pData->m_Normal = pTemp->m_ppTriList[i]->m_Normal; - pData->m_Distance = pTemp->m_ppTriList[i]->m_Distance; - } - } - - // collision! - if( pData->m_Fraction < startFraction ) - return true; - - // no collision! - return false; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::RayAABBTest( CDispCollTreeTempData *pTemp, Vector &rayStart, Vector &rayEnd ) -{ - const float MY_DIST_EPSILON = 0.01f; - - for( int i = 0; i < 6; i++ ) - { - float dist1 = m_AABBNormals[i].Dot( rayStart ) - pTemp->m_AABBDistances[i]; - float dist2 = m_AABBNormals[i].Dot( rayEnd ) - pTemp->m_AABBDistances[i]; - - // - // entry intersection point - move ray start up to intersection - // - if( ( dist1 > MY_DIST_EPSILON ) && ( dist2 < -MY_DIST_EPSILON ) ) - { - float fraction = ( dist1 / ( dist1 - dist2 ) ); - - Vector segment, increment; - segment = ( rayEnd - rayStart ) * fraction; - increment = segment; - VectorNormalize(increment); - segment += increment; - rayStart += segment; - } - else if( ( dist1 > MY_DIST_EPSILON ) && ( dist2 > MY_DIST_EPSILON ) ) - { - return false; - } - } - - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::CreatePlanesFromBounds( CDispCollTreeTempData *pTemp, Vector const &bbMin, Vector const &bbMax ) -{ - // - // note -- these never change! - // -// m_AABBNormals[0].x = -1; -// m_AABBNormals[1].x = 1; - -// m_AABBNormals[2].y = -1; -// m_AABBNormals[3].y = 1; - -// m_AABBNormals[4].z = -1; -// m_AABBNormals[5].z = 1; - - pTemp->m_AABBDistances[0] = -bbMin.x; - pTemp->m_AABBDistances[1] = bbMax.x; - - pTemp->m_AABBDistances[2] = -bbMin.y; - pTemp->m_AABBDistances[3] = bbMax.y; - - pTemp->m_AABBDistances[4] = -bbMin.z; - pTemp->m_AABBDistances[5] = bbMax.z; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::RayNodeTest_r( CDispCollTreeTempData *pTemp, int nodeIndex, Vector rayStart, Vector rayEnd ) -{ - // get the current node - CDispCollNode *pNode = &m_pNodes[nodeIndex]; - - // - // get node bounding box and create collision planes - // - Vector bounds[2]; - pNode->GetBounds( bounds[0], bounds[1] ); - CreatePlanesFromBounds( pTemp, bounds[0], bounds[1] ); - - bool bIntersect = RayAABBTest( pTemp, rayStart, rayEnd ); - if( bIntersect ) - { - // done -- add triangles to triangle list - if( pNode->IsLeaf() ) - { - // Assert for now -- flush cache later!!!!! - Assert( pTemp->m_TriListCount >= 0 ); - Assert( pTemp->m_TriListCount < TRILIST_CACHE_SIZE ); - - pTemp->m_ppTriList[pTemp->m_TriListCount] = &pNode->m_Tris[0]; - pTemp->m_ppTriList[pTemp->m_TriListCount+1] = &pNode->m_Tris[1]; - pTemp->m_TriListCount += 2; - } - // continue recursion - else - { - for( int i = 0; i < 4; i++ ) - { - RayNodeTest_r( pTemp, GetChildNode( nodeIndex, i ), rayStart, rayEnd ); - } - } - } -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::RayTestAllTris( CDispCollData *pData, int power ) -{ - // - // get leaf indices - // - int startIndex = CalcNodeCount( power - 1 ); - int endIndex = CalcNodeCount( power ); - - // save incoming fraction - float startFraction = pData->m_Fraction; - float fraction = pData->m_Fraction; - - Vector ray = pData->m_EndPos - pData->m_StartPos; - Vector rayDir = ray; - float rayLength = VectorNormalize(rayDir); - - // - // test ray against all triangles in list - // - for( int index = startIndex; index < endIndex; index++ ) - { - for( int j = 0; j < 2; j++ ) - { - bool bResult = RayTriTest( pData->m_StartPos, rayDir, rayLength, &m_pNodes[index].m_Tris[j], &fraction ); - if( !bResult ) - continue; - - if( pData->m_bOcclude ) - { - return true; - } - - if( fraction < pData->m_Fraction ) - { - pData->m_Fraction = fraction; - pData->m_Normal = m_pNodes[index].m_Tris[j].m_Normal; - pData->m_Distance = m_pNodes[index].m_Tris[j].m_Distance; - } - } - } - - // collision! - if( pData->m_Fraction < startFraction ) - return true; - - // no collision! - return false; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::RayTest( CDispCollData *pData ) -{ - // reset the triangle list count - CDispCollTreeTempData tmp; - tmp.m_TriListCount = 0; - - // trace against nodes (copy start, end because they change) - RayNodeTest_r( &tmp, 0, pData->m_StartPos, pData->m_EndPos ); - - // - // trace against tris (if need be) - // - if( tmp.m_TriListCount != 0 ) - { - bool result = RayTriListTest( &tmp, pData ); - return result; - } - - return false; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::SweptAABBTriIntersect( Vector &rayStart, Vector &rayEnd, Vector &extents, - CDispCollTri const *pTri, Vector &plNormal, float *plDist, - float *fraction ) -{ - - // - // PUT A COPY HERE OF START AND END -- SINCE I CHANGE THEM!!!!!! - // - - - - - - int dir, ptIndex; - float closeValue; - float distStart, distEnd; - float t; - Vector rayPt; - - // get ray direction - Vector rayDir = rayEnd - rayStart; - - // initialize fraction - *fraction = 1.0f; - - // - // test for collision with axial planes (x, y, z) - // - for( dir = 0; dir < 3; dir++ ) - { - if( rayDir[dir] < 0.0f ) - { - closeValue = -99999.9f; - for( ptIndex = 0; ptIndex < 3; ptIndex++ ) - { - if( pTri->m_Points[ptIndex][dir] > closeValue ) - { - closeValue = pTri->m_Points[ptIndex][dir]; - } - } - - closeValue += extents[dir]; - - distStart = rayStart[dir] - closeValue; - distEnd = rayEnd[dir] - closeValue; - } - else - { - closeValue = 99999.9f; - for( ptIndex = 0; ptIndex < 3; ptIndex++ ) - { - if( pTri->m_Points[ptIndex][dir] < closeValue ) - { - closeValue = pTri->m_Points[ptIndex][dir]; - } - } - - closeValue -= extents[dir]; - - distStart = -( rayStart[dir] - closeValue ); - distEnd = -( rayEnd[dir] - closeValue ); - } - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal.Init(); - plNormal[dir] = 1.0f; - *plDist = closeValue; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - } - - // - // check for an early out - // - if( ( pTri->m_Normal[0] > ONE_MINUS_COLLISION_EPSILON ) || - ( pTri->m_Normal[1] > ONE_MINUS_COLLISION_EPSILON ) || - ( pTri->m_Normal[2] > ONE_MINUS_COLLISION_EPSILON ) ) - { - if( *fraction == 1.0f ) - return false; - - return true; - } - - // - // handle 9 edge tests - // - Vector normal; - Vector edge; - float dist; - - // find the closest box point - Vector boxPt( 0.0f, 0.0f, 0.0f ); - for( dir = 0; dir < 3; dir++ ) - { - if( rayDir[dir] < 0.0f ) - { - boxPt[dir] = extents[dir]; - } - else - { - boxPt[dir] = -extents[dir]; - } - } - - // - // edge 0 - // - edge = pTri->m_Points[1] - pTri->m_Points[0]; - - // cross x-edge - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - - // extents adjusted dist - dist = ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); - - // find distances from plane (start, end) - distStart = ( normal.y * rayStart.y ) + ( normal.z * rayStart.z ) - dist; - distEnd = ( normal.y * rayEnd.y ) + ( normal.z * rayEnd.z ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // cross y-edge - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - - // extents adjusted dist - dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); - - // find distances from plane (start, end) - distStart = ( normal.x * rayStart.x ) + ( normal.z * rayStart.z ) - dist; - distEnd = ( normal.x * rayEnd.x ) + ( normal.z * rayEnd.z ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // cross z-edge - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - - // extents adjusted dist - dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ); - - // find distances from plane (start, end) - distStart = ( normal.x * rayStart.x ) + ( normal.y * rayStart.y ) - dist; - distEnd = ( normal.x * rayEnd.x ) + ( normal.y * rayEnd.y ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // - // edge 1 - // - edge = pTri->m_Points[2] - pTri->m_Points[1]; - - // cross x-edge - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - - // extents adjusted dist - dist = ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); - - // find distances from plane (start, end) - distStart = ( normal.y * rayStart.y ) + ( normal.z * rayStart.z ) - dist; - distEnd = ( normal.y * rayEnd.y ) + ( normal.z * rayEnd.z ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // cross y-edge - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - - // extents adjusted dist - dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); - - // find distances from plane (start, end) - distStart = ( normal.x * rayStart.x ) + ( normal.z * rayStart.z ) - dist; - distEnd = ( normal.x * rayEnd.x ) + ( normal.z * rayEnd.z ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // cross z-edge - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - - // extents adjusted dist - dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ); - - // find distances from plane (start, end) - distStart = ( normal.x * rayStart.x ) + ( normal.y * rayStart.y ) - dist; - distEnd = ( normal.x * rayEnd.x ) + ( normal.y * rayEnd.y ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // - // edge 2 - // - edge = pTri->m_Points[0] - pTri->m_Points[2]; - - // cross x-edge - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - - // extents adjusted dist - dist = ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); - - // find distances from plane (start, end) - distStart = ( normal.y * rayStart.y ) + ( normal.z * rayStart.z ) - dist; - distEnd = ( normal.y * rayEnd.y ) + ( normal.z * rayEnd.z ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // cross y-edge - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - - // extents adjusted dist - dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); - - // find distances from plane (start, end) - distStart = ( normal.x * rayStart.x ) + ( normal.z * rayStart.z ) - dist; - distEnd = ( normal.x * rayEnd.x ) + ( normal.z * rayEnd.z ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // cross z-edge - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - - // extents adjusted dist - dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ); - - // find distances from plane (start, end) - distStart = ( normal.x * rayStart.x ) + ( normal.y * rayStart.y ) - dist; - distEnd = ( normal.x * rayEnd.x ) + ( normal.y * rayEnd.y ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // - // test face plane - // - dist = ( pTri->m_Normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + - ( pTri->m_Normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + - ( pTri->m_Normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); - - distStart = pTri->m_Normal.Dot( rayStart ) - dist; - distEnd = pTri->m_Normal.Dot( rayEnd ) - dist; - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); - if( t > *fraction ) - { - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayStart ); - *fraction = t; - plNormal = normal; - *plDist = dist; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); - VectorScale( rayDir, t, rayPt ); - VectorAdd( rayStart, rayPt, rayEnd ); - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - if( *fraction == 1.0f ) - return false; - - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBTriIntersect( CDispCollTreeTempData *pTemp, CDispCollData *pData ) -{ - bool bResult = false; - - Vector normal; - float fraction, dist; - - // - // sweep ABB against all triangles in list - // - for( int i = 0; i < pTemp->m_TriListCount; i++ ) - { - if( pTemp->m_ppTriList[i]->IsIntersect() ) - { - bResult = SweptAABBTriIntersect( pData->m_StartPos, pData->m_EndPos, pData->m_Extents, - pTemp->m_ppTriList[i], normal, &dist, &fraction ); - if( bResult ) - { - if( fraction < pData->m_Fraction ) - { - pData->m_Fraction = fraction; - pData->m_Normal = normal; - pData->m_Distance = dist; - } - } - } - } - - return bResult; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::IntersectAABBTriTest( Vector &rayStart, Vector &extents, - CDispCollTri const *pTri ) -{ - int dir, ptIndex; - float dist; - - // - // test axail planes (x, y, z) - // - - for( dir = 0; dir < 3; dir++ ) - { - // - // negative axial plane, component = dir - // - dist = rayStart[dir] - extents[dir]; - for( ptIndex = 0; ptIndex < 3; ptIndex++ ) - { - if( pTri->m_Points[ptIndex][dir] > dist ) - break; - } - - if( ptIndex == 3 ) - return false; - - // - // positive axial plane, component = dir - // - dist = rayStart[dir] + extents[dir]; - for( ptIndex = 0; ptIndex < 3; ptIndex++ ) - { - if( pTri->m_Points[ptIndex][dir] < dist ) - break; - } - - if( ptIndex == 3 ) - return false; - } - - // - // add a test here to see if triangle face normal is close to axial -- done if so!!! - // - if( ( pTri->m_Normal[0] > ONE_MINUS_COLLISION_EPSILON ) || - ( pTri->m_Normal[1] > ONE_MINUS_COLLISION_EPSILON ) || - ( pTri->m_Normal[2] > ONE_MINUS_COLLISION_EPSILON ) ) - return true; - - // find the closest point on the box (use negated tri face noraml) - Vector boxPt( 0.0f, 0.0f, 0.0f ); - for( dir = 0; dir < 3; dir++ ) - { - if( pTri->m_Normal[dir] < 0.0f ) - { - boxPt[dir] = extents[dir]; - } - else - { - boxPt[dir] = -extents[dir]; - } - } - - // - // triangle plane test - // - // do the opposite because the ray has been negated - if( ( ( pTri->m_Normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + - ( pTri->m_Normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + - ( pTri->m_Normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) - return false; - - // - // test edge planes - 9 of them - // - Vector normal; - Vector edge; - - // - // edge 0 - // - edge = pTri->m_Points[1] - pTri->m_Points[0]; - - // cross x - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - if( ( ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) - return false; - - // cross y - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) - return false; - - // cross z - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) ) > 0.0f ) - return false; - - // - // edge 1 - // - edge = pTri->m_Points[2] - pTri->m_Points[1]; - - // cross x - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - if( ( ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) - return false; - - // cross y - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) - return false; - - // cross z - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) ) > 0.0f ) - return false; - - // - // edge 2 - // - edge = pTri->m_Points[0] - pTri->m_Points[2]; - - // cross x - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - if( ( ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) - return false; - - // cross y - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) - return false; - - // cross z - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) ) > 0.0f ) - return false; - - return true; -} - - - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::SweptAABBTriTest( Vector &rayStart, Vector &rayEnd, Vector &extents, - CDispCollTri const *pTri ) -{ - // get ray direction - Vector rayDir = rayEnd - rayStart; - - // - // quick and dirty test -- test to see if the object is traveling away from triangle surface??? - // - if( pTri->m_Normal.Dot( rayDir ) > 0.0f ) - return false; - - // - // calc the swept triangle face (negate the ray -- opposite direction of box travel) - // - rayDir.Negate(); - - Vector points[3]; - points[0] = pTri->m_Points[0] + rayDir; - points[1] = pTri->m_Points[1] + rayDir; - points[2] = pTri->m_Points[2] + rayDir; - - // - // handle 4 faces tests (3 axial planes and triangle face) - // - int dir; - float dist; - - // - // axial planes tests (x, y, z) - // - for( dir = 0; dir < 3; dir++ ) - { - bool bOutside = true; - - if( rayDir[dir] < 0.0f ) - { - dist = rayStart[dir] - extents[dir]; - for( int ptIndex = 0; ptIndex < 3; ptIndex ) - { - if( points[ptIndex][dir] > dist ) - { - bOutside = false; - break; - } - } - } - else - { - dist = rayStart[dir] + extents[dir]; - for( int ptIndex = 0; ptIndex < 3; ptIndex ) - { - if( pTri->m_Points[ptIndex][dir] < dist ) - { - bOutside = false; - break; - } - } - } - - if( bOutside ) - return false; - } - - // - // add a test here to see if triangle face normal is close to axial -- done if so!!! - // - if( ( pTri->m_Normal[0] > ONE_MINUS_COLLISION_EPSILON ) || - ( pTri->m_Normal[1] > ONE_MINUS_COLLISION_EPSILON ) || - ( pTri->m_Normal[2] > ONE_MINUS_COLLISION_EPSILON ) ) - return true; - - // - // handle 9 edge tests - always use the newly swept face for this - // - Vector normal; - Vector edge; - - // find the closest box point - (is written opposite to normal due to negating ray) - Vector boxPt( 0.0f, 0.0f, 0.0f ); - for( dir = 0; dir < 3; dir++ ) - { - if( rayDir[dir] < 0.0f ) - { - boxPt[dir] = rayStart[dir] - extents[dir]; - } - else - { - boxPt[dir] = rayStart[dir] + extents[dir]; - } - } - - // - // edge 0 - // - edge = points[1] - points[0]; - - // cross x-edge - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - if( ( ( normal.y * ( boxPt.y - points[0].y ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) - return false; - - // cross, y-edge - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) - return false; - - // cross z-edge - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.y * ( boxPt.y - points[0].y ) ) ) > 0.0f ) - return false; - - // - // edge 1 - // - edge = points[2] - points[1]; - - // cross x-edge - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - if( ( ( normal.y * ( boxPt.y - points[0].y ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) - return false; - - // cross, y-edge - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) - return false; - - // cross z-edge - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.y * ( boxPt.y - points[0].y ) ) ) > 0.0f ) - return false; - - // - // edge 2 - // - edge = points[0] - points[2]; - - // cross x-edge - normal.x = 0.0f; - normal.y = -edge.z; - normal.z = edge.y; - if( ( ( normal.y * ( boxPt.y - points[0].y ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) - return false; - - // cross, y-edge - normal.x = edge.z; - normal.y = 0.0f; - normal.z = edge.y; - if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) - return false; - - // cross z-edge - normal.x = -edge.y; - normal.y = edge.x; - normal.z = 0.0f; - if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.y * ( boxPt.y - points[0].y ) ) ) > 0.0f ) - return false; - - // - // triangle plane test - // - // do the opposite because the ray has been negated - if( ( ( pTri->m_Normal.x * ( boxPt.x - points[0].x ) ) + - ( pTri->m_Normal.y * ( boxPt.y - points[0].y ) ) + - ( pTri->m_Normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) - return false; - - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::CullTriList( CDispCollTreeTempData *pTemp, Vector &rayStart, Vector &rayEnd, Vector &extents, bool bIntersect ) -{ - // - // intersect AABB with all triangles in list - // - if( bIntersect ) - { - for( int i = 0; i < pTemp->m_TriListCount; i++ ) - { - if( IntersectAABBTriTest( rayStart, extents, pTemp->m_ppTriList[i] ) ) - return true; - } - - return false; - } - // - // sweep AABB against all triangles in list - // - else - { - bool bResult = false; - - for( int i = 0; i < pTemp->m_TriListCount; i++ ) - { - if( SweptAABBTriTest( rayStart, rayEnd, extents, pTemp->m_ppTriList[i] ) ) - { - pTemp->m_ppTriList[i]->SetIntersect( true ); - bResult = true; - } - } - - return bResult; - } -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::IntersectAABBAABBTest( CDispCollTreeTempData *pTemp, const Vector &pos, const Vector &extents ) -{ - float dist; - - for( int dir = 0; dir < 3; dir++ ) - { - // negative direction - dist = -( pos[dir] - ( pTemp->m_AABBDistances[(dir>>1)] - extents[dir] ) ); - if( dist > COLLISION_EPSILON ) - return false; - - // positive direction - dist = pos[dir] - ( pTemp->m_AABBDistances[(dir>>1)+1] + extents[dir] ); - if( dist > COLLISION_EPSILON ) - return false; - } - - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::SweptAABBAABBTest( CDispCollTreeTempData *pTemp, const Vector &rayStart, const Vector &rayEnd, const Vector &extents ) -{ - int dir; - float distStart, distEnd; - float fraction; - float deltas[3]; - float scalers[3]; - - // - // enter and exit fractions - // - float enterFraction = 0.0f; - float exitFraction = 0.0f; - - // - // de-normalize the paramter space so that we don't have to divide - // to find the fractional amount later (clamped for precision) - // - deltas[0] = rayEnd.x - rayStart.x; - deltas[1] = rayEnd.y - rayStart.y; - deltas[2] = rayEnd.z - rayStart.z; - if( ( deltas[0] < COLLISION_EPSILON ) && ( deltas[0] > -COLLISION_EPSILON ) ) { deltas[0] = 1.0f; } - if( ( deltas[1] < COLLISION_EPSILON ) && ( deltas[1] > -COLLISION_EPSILON ) ) { deltas[0] = 1.0f; } - if( ( deltas[2] < COLLISION_EPSILON ) && ( deltas[2] > -COLLISION_EPSILON ) ) { deltas[0] = 1.0f; } - scalers[0] = deltas[1] * deltas[2]; - scalers[1] = deltas[0] * deltas[2]; - scalers[2] = deltas[0] * deltas[1]; - - for( dir = 0; dir < 3; dir++ ) - { - // - // negative direction - // - distStart = -( rayStart[dir] - ( pTemp->m_AABBDistances[(dir>>1)] - extents[dir] ) ); - distEnd = -( rayEnd[dir] - ( pTemp->m_AABBDistances[(dir>>1)] - extents[dir] ) ); - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - fraction = distStart * scalers[dir]; - if( fraction > enterFraction ) - { - enterFraction = fraction; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - fraction = distStart * scalers[dir]; - if( fraction < exitFraction ) - { - exitFraction = fraction; - } - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - - // - // positive direction - // - distStart = rayStart[dir] - ( pTemp->m_AABBDistances[(dir>>1)+1] + extents[dir] ); - distEnd = rayEnd[dir] - ( pTemp->m_AABBDistances[(dir>>1)+1] + extents[dir] ); - - if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) - { - fraction = distStart * scalers[dir]; - if( fraction > enterFraction ) - { - enterFraction = fraction; - } - } - else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - fraction = distStart * scalers[dir]; - if( fraction < exitFraction ) - { - exitFraction = fraction; - } - } - else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) - { - return false; - } - } - - if( exitFraction < enterFraction ) - return false; - - return true; -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -void CDispCollTree::BuildTriList_r( CDispCollTreeTempData *pTemp, int nodeIndex, Vector &rayStart, Vector &rayEnd, Vector &extents, - bool bIntersect ) -{ - // - // get the current nodes bounds and create collision test planes - // (saved in the in class cache m_AABBNormals, m_AABBDistances) - // - Vector bounds[2]; - CDispCollNode *pNode = &m_pNodes[nodeIndex]; - pNode->GetBounds( bounds[0], bounds[1] ); - CreatePlanesFromBounds( pTemp, bounds[0], bounds[1] ); - - // - // interesect/sweep test - // - bool bResult; - if( bIntersect ) - { - bResult = IntersectAABBAABBTest( pTemp, rayStart, extents ); - } - else - { - bResult = SweptAABBAABBTest( pTemp, rayStart, rayEnd, extents ); - } - - if( bResult ) - { - // if leaf node -- add triangles to interstection test list - if( pNode->IsLeaf() ) - { - // Assert for now -- flush cache later!!!!! - Assert( pTemp->m_TriListCount >= 0 ); - Assert( pTemp->m_TriListCount < TRILIST_CACHE_SIZE ); - - pTemp->m_ppTriList[pTemp->m_TriListCount] = &pNode->m_Tris[0]; - pTemp->m_ppTriList[pTemp->m_TriListCount+1] = &pNode->m_Tris[1]; - pTemp->m_TriListCount += 2; - } - // continue recursion - else - { - BuildTriList_r( pTemp, GetChildNode( nodeIndex, 0 ), rayStart, rayEnd, extents, bIntersect ); - BuildTriList_r( pTemp, GetChildNode( nodeIndex, 1 ), rayStart, rayEnd, extents, bIntersect ); - BuildTriList_r( pTemp, GetChildNode( nodeIndex, 2 ), rayStart, rayEnd, extents, bIntersect ); - BuildTriList_r( pTemp, GetChildNode( nodeIndex, 3 ), rayStart, rayEnd, extents, bIntersect ); - } - } -} - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBSweep( CDispCollData *pData ) -{ - // reset the triangle lists counts - CDispCollTreeTempData tmp; - tmp.m_TriListCount = 0; - - // sweep the AABB against the tree - BuildTriList_r( &tmp, 0, pData->m_StartPos, pData->m_EndPos, pData->m_Extents, false ); - - // find collision triangles - if( CullTriList( &tmp, pData->m_StartPos, pData->m_EndPos, pData->m_Extents, false ) ) - { - // find closest intersection - return AABBTriIntersect( &tmp, pData ); - } - - return false; -} - - - -//----------------------------------------------------------------------------- -// Purpose: -//----------------------------------------------------------------------------- -bool CDispCollTree::AABBIntersect( CDispCollData *pData ) -{ - // reset the triangle lists counts - CDispCollTreeTempData tmp; - tmp.m_TriListCount = 0; - - // sweep the AABB against the tree - BuildTriList_r( &tmp, 0, pData->m_StartPos, pData->m_StartPos, pData->m_Extents, true ); - - // find collision triangles - return CullTriList( &tmp, pData->m_StartPos, pData->m_StartPos, pData->m_Extents, true ); -} +//========= Copyright Valve Corporation, All rights reserved. ============// +// +// Purpose: +// +// $NoKeywords: $ +//=============================================================================// + +#include "BuildDisp.h" +#include "DispColl.h" +#include "tier0/dbg.h" + +//============================================================================= + +const float CDispCollTree::COLLISION_EPSILON = 0.01f; +const float CDispCollTree::ONE_MINUS_COLLISION_EPSILON = 1.0f - COLLISION_EPSILON; + +//============================================================================= +// +// Displacement Collision Triangle Functions +// + + +//----------------------------------------------------------------------------- +// Purpose: initialize the displacement triangles +//----------------------------------------------------------------------------- +void CDispCollTri::Init( void ) +{ + for( int i = 0; i < 3; i++ ) + { + m_Points[i].x = 0.0f; m_Points[i].y = 0.0f; m_Points[i].z = 0.0f; + m_PointNormals[i].x = 0.0f; m_PointNormals[i].y = 0.0f; m_PointNormals[i].z = 0.0f; + } + + m_Normal.x = 0.0f; m_Normal.y = 0.0f; m_Normal.z = 0.0f; + m_Distance = 0.0f; + + m_ProjAxes[0] = -1; + m_ProjAxes[1] = -1; + + m_bIntersect = false; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline void CDispCollTri::SetPoint( int index, Vector const &vert ) +{ + Assert( index >= 0 ); + Assert( index < 3 ); + + m_Points[index].x = vert[0]; + m_Points[index].y = vert[1]; + m_Points[index].z = vert[2]; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline void CDispCollTri::SetPointNormal( int index, Vector const &normal ) +{ + Assert( index >= 0 ); + Assert( index < 3 ); + + m_PointNormals[index].x = normal[0]; + m_PointNormals[index].y = normal[1]; + m_PointNormals[index].z = normal[2]; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTri::CalcPlane( void ) +{ + // + // calculate the plane normal and distance + // + Vector segment1, segment2, cross; + + segment1 = m_Points[1] - m_Points[0]; + segment2 = m_Points[2] - m_Points[0]; + cross = segment1.Cross( segment2 ); + m_Normal = cross; + VectorNormalize(m_Normal); + + m_Distance = m_Normal.Dot( m_Points[0] ); + + // + // calculate the projection axes + // + if( FloatMakePositive( m_Normal[0] ) > FloatMakePositive( m_Normal[1] ) ) + { + if( FloatMakePositive( m_Normal[0] ) > FloatMakePositive( m_Normal[2] ) ) + { + m_ProjAxes[0] = 1; + m_ProjAxes[1] = 2; + } + else + { + m_ProjAxes[0] = 0; + m_ProjAxes[1] = 1; + } + } + else + { + if( FloatMakePositive( m_Normal[1] ) > FloatMakePositive( m_Normal[2] ) ) + { + m_ProjAxes[0] = 0; + m_ProjAxes[1] = 2; + } + else + { + m_ProjAxes[0] = 0; + m_ProjAxes[1] = 1; + } + } +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline void CDispCollTri::SetIntersect( bool bIntersect ) +{ + m_bIntersect = bIntersect; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline bool CDispCollTri::IsIntersect( void ) +{ + return m_bIntersect; +} + + +//============================================================================= +// +// Displacement Collision Node Functions +// + + +//----------------------------------------------------------------------------- +// Purpose: constructor +//----------------------------------------------------------------------------- +CDispCollNode::CDispCollNode() +{ + m_Bounds[0].x = m_Bounds[0].y = m_Bounds[0].z = 99999.9f; + m_Bounds[1].x = m_Bounds[1].y = m_Bounds[1].z = -99999.9f; + + m_Tris[0].Init(); + m_Tris[1].Init(); + + m_bIsLeaf = false; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline bool CDispCollNode::IsLeaf( void ) +{ + return m_bIsLeaf; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline void CDispCollNode::SetBounds( Vector const &bMin, Vector const &bMax ) +{ + m_Bounds[0] = bMin; + m_Bounds[1] = bMax; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline void CDispCollNode::GetBounds( Vector &bMin, Vector &bMax ) +{ + bMin = m_Bounds[0]; + bMax = m_Bounds[1]; +} + + +//============================================================================= +// +// Displacement Collision Tree Functions +// + +//----------------------------------------------------------------------------- +// Purpose: constructor +//----------------------------------------------------------------------------- +CDispCollTree::CDispCollTree() +{ + m_Power = 0; + + m_NodeCount = 0; + m_pNodes = NULL; + + InitAABBData(); +} + + +//----------------------------------------------------------------------------- +// Purpose: deconstructor +//----------------------------------------------------------------------------- +CDispCollTree::~CDispCollTree() +{ + FreeNodes(); +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::InitAABBData( void ) +{ + m_AABBNormals[0].x = -1.0f; m_AABBNormals[0].y = 0.0f; m_AABBNormals[0].z = 0.0f; + m_AABBNormals[1].x = 1.0f; m_AABBNormals[1].y = 0.0f; m_AABBNormals[1].z = 0.0f; + + m_AABBNormals[2].x = 0.0f; m_AABBNormals[2].y = -1.0f; m_AABBNormals[2].z = 0.0f; + m_AABBNormals[3].x = 0.0f; m_AABBNormals[3].y = 1.0f; m_AABBNormals[3].z = 0.0f; + + m_AABBNormals[4].x = 0.0f; m_AABBNormals[4].y = 0.0f; m_AABBNormals[4].z = -1.0f; + m_AABBNormals[5].x = 0.0f; m_AABBNormals[5].y = 0.0f; m_AABBNormals[5].z = 1.0f; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::CalcBounds( CDispCollNode *pNode, int nodeIndex ) +{ + Vector bounds[2]; + bounds[0].Init( 99999.9f, 99999.9f, 99999.9f ); + bounds[1].Init( -99999.9f, -99999.9f, -99999.9f ); + + // + // handle leaves differently -- bounding volume defined by triangles + // + if( pNode->IsLeaf() ) + { + for( int i = 0; i < 2; i++ ) + { + for( int j = 0; j < 3; j++ ) + { + // + // minimum + // + if( bounds[0].x > pNode->m_Tris[i].m_Points[j].x ) { bounds[0].x = pNode->m_Tris[i].m_Points[j].x; } + if( bounds[0].y > pNode->m_Tris[i].m_Points[j].y ) { bounds[0].y = pNode->m_Tris[i].m_Points[j].y; } + if( bounds[0].z > pNode->m_Tris[i].m_Points[j].z ) { bounds[0].z = pNode->m_Tris[i].m_Points[j].z; } + + // + // maximum + // + if( bounds[1].x < pNode->m_Tris[i].m_Points[j].x ) { bounds[1].x = pNode->m_Tris[i].m_Points[j].x; } + if( bounds[1].y < pNode->m_Tris[i].m_Points[j].y ) { bounds[1].y = pNode->m_Tris[i].m_Points[j].y; } + if( bounds[1].z < pNode->m_Tris[i].m_Points[j].z ) { bounds[1].z = pNode->m_Tris[i].m_Points[j].z; } + } + } + } + // + // bounding volume defined by maxima and minima of children volumes + // + else + { + for( int i = 0; i < 4; i++ ) + { + int childIndex = GetChildNode( nodeIndex, i ); + CDispCollNode *pChildNode = &m_pNodes[childIndex]; + + Vector childBounds[2]; + pChildNode->GetBounds( childBounds[0], childBounds[1] ); + + // + // minimum + // + if( bounds[0].x > childBounds[0].x ) { bounds[0].x = childBounds[0].x; } + if( bounds[0].y > childBounds[0].y ) { bounds[0].y = childBounds[0].y; } + if( bounds[0].z > childBounds[0].z ) { bounds[0].z = childBounds[0].z; } + + // + // maximum + // + if( bounds[1].x < childBounds[1].x ) { bounds[1].x = childBounds[1].x; } + if( bounds[1].y < childBounds[1].y ) { bounds[1].y = childBounds[1].y; } + if( bounds[1].z < childBounds[1].z ) { bounds[1].z = childBounds[1].z; } + } + } + + pNode->SetBounds( bounds[0], bounds[1] ); +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::CreateNodes_r( CCoreDispInfo *pDisp, int nodeIndex, int termLevel ) +{ + int nodeLevel = GetNodeLevel( nodeIndex ); + + // + // terminating condition -- set node info (leaf or otherwise) + // + if( nodeLevel == termLevel ) + { + CDispCollNode *pNode = &m_pNodes[nodeIndex]; + CalcBounds( pNode, nodeIndex ); + + return; + } + + // + // recurse into children + // + for( int i = 0; i < 4; i++ ) + { + CreateNodes_r( pDisp, GetChildNode( nodeIndex, i ), termLevel ); + } +} + + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::CreateNodes( CCoreDispInfo *pDisp ) +{ + // + // create all nodes in tree + // + int power = pDisp->GetPower() + 1; + for( int level = power; level > 0; level-- ) + { + CreateNodes_r( pDisp, 0 /* rootIndex */, level ); + } +} + + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +int CDispCollTree::GetNodeIndexFromComponents( int x, int y ) +{ + int index = 0; + + // Interleave bits from the x and y values to create the index: + + for( int shift = 0; x != 0; shift += 2, x >>= 1 ) + { + index |= ( x & 1 ) << shift; + } + + for( shift = 1; y != 0; shift += 2, y >>= 1 ) + { + index |= ( y & 1 ) << shift; + } + + return index; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::InitLeaves( CCoreDispInfo *pDisp ) +{ + // + // get power and width and displacement surface + // + int power = pDisp->GetPower(); + int width = pDisp->GetWidth(); + + // + // get leaf indices + // + int startIndex = CalcNodeCount( power - 1 ); + int endIndex = CalcNodeCount( power ); + + for( int index = startIndex; index < endIndex; index++ ) + { + // + // create triangles at leaves + // + int x = ( index - startIndex ) % ( width - 1 ); + int y = ( index - startIndex ) / ( width - 1 ); + + int nodeIndex = GetNodeIndexFromComponents( x, y ); + nodeIndex += startIndex; + + Vector vert; + Vector normal; + + // + // tri 1 + // + pDisp->GetVert( x + ( y * width ), vert ); + pDisp->GetNormal( x + ( y * width ), normal ); + m_pNodes[nodeIndex].m_Tris[0].SetPoint( 0, vert ); + m_pNodes[nodeIndex].m_Tris[0].SetPointNormal( 0, normal ); + + pDisp->GetVert( x + ( ( y + 1 ) * width ), vert ); + pDisp->GetNormal( x + ( ( y + 1 ) * width ), normal ); + m_pNodes[nodeIndex].m_Tris[0].SetPoint( 1, vert ); + m_pNodes[nodeIndex].m_Tris[0].SetPointNormal( 1, normal ); + + pDisp->GetVert( ( x + 1 ) + ( y * width ), vert ); + pDisp->GetNormal( ( x + 1 ) + ( y * width ), normal ); + m_pNodes[nodeIndex].m_Tris[0].SetPoint( 2, vert ); + m_pNodes[nodeIndex].m_Tris[0].SetPointNormal( 2, normal ); + + m_pNodes[nodeIndex].m_Tris[0].CalcPlane(); + + // + // tri 2 + // + pDisp->GetVert( ( x + 1 ) + ( y * width ), vert ); + pDisp->GetNormal( ( x + 1 ) + ( y * width ), normal ); + m_pNodes[nodeIndex].m_Tris[1].SetPoint( 0, vert ); + m_pNodes[nodeIndex].m_Tris[1].SetPointNormal( 0, normal ); + + pDisp->GetVert( x + ( ( y + 1 ) * width ), vert ); + pDisp->GetNormal( x + ( ( y + 1 ) * width ), normal ); + m_pNodes[nodeIndex].m_Tris[1].SetPoint( 1, vert ); + m_pNodes[nodeIndex].m_Tris[1].SetPointNormal( 1, normal ); + + pDisp->GetVert( ( x + 1 ) + ( ( y + 1 ) * width ), vert ); + pDisp->GetNormal( ( x + 1 ) + ( ( y + 1 ) * width ), normal ); + m_pNodes[nodeIndex].m_Tris[1].SetPoint( 2, vert ); + m_pNodes[nodeIndex].m_Tris[1].SetPointNormal( 2, normal ); + + m_pNodes[nodeIndex].m_Tris[1].CalcPlane(); + + // set node as leaf + m_pNodes[nodeIndex].m_bIsLeaf = true; + } +} + + +//----------------------------------------------------------------------------- +// Purpose: allocate and initialize the displacement collision tree +// Input: power - size of the displacement surface +// Output: bool - success? (true/false) +//----------------------------------------------------------------------------- +bool CDispCollTree::Create( CCoreDispInfo *pDisp ) +{ + // + // calculate the number of nodes needed given the size of the displacement + // + m_Power = pDisp->GetPower(); + m_NodeCount = CalcNodeCount( m_Power ); + + // + // allocate tree space + // + if( !AllocNodes( m_NodeCount ) ) + return false; + + // initialize leaves + InitLeaves( pDisp ); + + // create tree nodes + CreateNodes( pDisp ); + + // tree successfully created! + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: allocate memory for the displacement collision tree +// Input: nodeCount - number of nodes to allocate +// Output: bool - success? (true/false) +//----------------------------------------------------------------------------- +bool CDispCollTree::AllocNodes( int nodeCount ) +{ + // sanity check + Assert( nodeCount != 0 ); + + m_pNodes = new CDispCollNode[nodeCount]; + if( !m_pNodes ) + return false; + + // tree successfully allocated! + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: release allocated memory for displacement collision tree +//----------------------------------------------------------------------------- +void CDispCollTree::FreeNodes( void ) +{ + if( m_pNodes ) + { + delete [] m_pNodes; + m_pNodes = NULL; + } +} + + +//----------------------------------------------------------------------------- +// Purpose: calculate the number of tree nodes given the size of the +// displacement surface +// Input: power - size of the displacement surface +// Output: int - the number of tree nodes +//----------------------------------------------------------------------------- +inline int CDispCollTree::CalcNodeCount( int power ) +{ + // power range [2...4] + Assert( power > 0 ); + Assert( power < 5 ); + + return ( ( 1 << ( ( power + 1 ) << 1 ) ) / 3 ); +} + + +//----------------------------------------------------------------------------- +// Purpose: get the parent node index given the current node +// Input: nodeIndex - current node index +// Output: int - the index of the parent node +//----------------------------------------------------------------------------- +inline int CDispCollTree::GetParentNode( int nodeIndex ) +{ + // node range [0...m_NodeCount) + Assert( nodeIndex >= 0 ); + Assert( nodeIndex < m_NodeCount ); + + // ( nodeIndex - 1 ) / 4 + return ( ( nodeIndex - 1 ) >> 2 ); +} + + +//----------------------------------------------------------------------------- +// Purpose: get the child node index given the current node index and direction +// of the child (1 of 4) +// Input: nodeIndex - current node index +// direction - direction of the child ( [0...3] - SW, SE, NW, NE ) +// Output: int - the index of the child node +//----------------------------------------------------------------------------- +inline int CDispCollTree::GetChildNode( int nodeIndex, int direction ) +{ + // node range [0...m_NodeCount) + Assert( nodeIndex >= 0 ); + Assert( nodeIndex < m_NodeCount ); + + // ( nodeIndex * 4 ) + ( direction + 1 ) + return ( ( nodeIndex << 2 ) + ( direction + 1 ) ); +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +inline int CDispCollTree::GetNodeLevel( int nodeIndex ) +{ + // node range [0...m_NodeCount) + Assert( nodeIndex >= 0 ); + Assert( nodeIndex < m_NodeCount ); + + // level = 2^n + 1 + if( nodeIndex == 0 ) { return 1; } + if( nodeIndex < 5 ) { return 2; } + if( nodeIndex < 21 ) { return 3; } + if( nodeIndex < 85 ) { return 4; } + if( nodeIndex < 341 ) { return 5; } + + return -1; +} + + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +bool CDispCollTree::RayTriTest( Vector const &rayStart, Vector const &rayDir, float const rayLength, + CDispCollTri const *pTri, float *fraction ) +{ + const float DET_EPSILON = 0.001f; + const float DIST_EPSILON = 0.001f; + + // + // calculate the edges + // + Vector edge1 = pTri->m_Points[1] - pTri->m_Points[0]; + Vector edge2 = pTri->m_Points[2] - pTri->m_Points[0]; + +// Vector faceNormal = edge1.Cross( edge2 ); +// Vector normNormal = faceNormal.Normalize(); + + // + // calculate the triangle's determinant + // + Vector pVec = rayDir.Cross( edge2 ); + float det = pVec.Dot( edge1 ); + + // if determinant is zero -- ray lies in plane + if( ( det > -DET_EPSILON ) && ( det < DET_EPSILON ) ) + return false; + + // + // utility calculations - inverse determinant and distance from v0 to ray start + // + double invDet = 1.0f / det; + Vector tVec = rayStart - pTri->m_Points[0]; + + // + // calculate the U parameter and test bounds + // + double u = pVec.Dot( tVec ) * invDet; + if( ( u < 0.0f ) || ( u > 1.0f ) ) + return false; + + Vector qVec = tVec.Cross( edge1 ); + + // + // calculate the V parameter and test bounds + // + double v = qVec.Dot( rayDir ) * invDet; + if( ( v < 0.0f ) || ( ( u + v ) > 1.0f ) ) + return false; + + // calculate where ray intersects triangle + *fraction = qVec.Dot( edge2 ) * invDet; + *fraction /= rayLength; + + if( ( *fraction < DIST_EPSILON ) || ( *fraction > ( 1.0f - DIST_EPSILON ) ) ) + return false; + + return true; +} + + +//----------------------------------------------------------------------------- +//----------------------------------------------------------------------------- +bool CDispCollTree::RayTriListTest( CDispCollTreeTempData *pTemp, CDispCollData *pData ) +{ + // save starting fraction -- to test for collision + float startFraction = pData->m_Fraction; + + // + // calculate the ray + // + Vector seg = pData->m_EndPos - pData->m_StartPos; + Vector rayDir = seg; + float rayLength = VectorNormalize( rayDir ); + + // + // test ray against all triangles in list + // + for( int i = 0; i < pTemp->m_TriListCount; i++ ) + { + float fraction = 1.0f; + bool bResult = RayTriTest( pData->m_StartPos, rayDir, rayLength, pTemp->m_ppTriList[i], &fraction ); + if( !bResult ) + continue; + + if( pData->m_bOcclude ) + { + return true; + } + + if( fraction < pData->m_Fraction ) + { + pData->m_Fraction = fraction; + pData->m_Normal = pTemp->m_ppTriList[i]->m_Normal; + pData->m_Distance = pTemp->m_ppTriList[i]->m_Distance; + } + } + + // collision! + if( pData->m_Fraction < startFraction ) + return true; + + // no collision! + return false; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::RayAABBTest( CDispCollTreeTempData *pTemp, Vector &rayStart, Vector &rayEnd ) +{ + const float MY_DIST_EPSILON = 0.01f; + + for( int i = 0; i < 6; i++ ) + { + float dist1 = m_AABBNormals[i].Dot( rayStart ) - pTemp->m_AABBDistances[i]; + float dist2 = m_AABBNormals[i].Dot( rayEnd ) - pTemp->m_AABBDistances[i]; + + // + // entry intersection point - move ray start up to intersection + // + if( ( dist1 > MY_DIST_EPSILON ) && ( dist2 < -MY_DIST_EPSILON ) ) + { + float fraction = ( dist1 / ( dist1 - dist2 ) ); + + Vector segment, increment; + segment = ( rayEnd - rayStart ) * fraction; + increment = segment; + VectorNormalize(increment); + segment += increment; + rayStart += segment; + } + else if( ( dist1 > MY_DIST_EPSILON ) && ( dist2 > MY_DIST_EPSILON ) ) + { + return false; + } + } + + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::CreatePlanesFromBounds( CDispCollTreeTempData *pTemp, Vector const &bbMin, Vector const &bbMax ) +{ + // + // note -- these never change! + // +// m_AABBNormals[0].x = -1; +// m_AABBNormals[1].x = 1; + +// m_AABBNormals[2].y = -1; +// m_AABBNormals[3].y = 1; + +// m_AABBNormals[4].z = -1; +// m_AABBNormals[5].z = 1; + + pTemp->m_AABBDistances[0] = -bbMin.x; + pTemp->m_AABBDistances[1] = bbMax.x; + + pTemp->m_AABBDistances[2] = -bbMin.y; + pTemp->m_AABBDistances[3] = bbMax.y; + + pTemp->m_AABBDistances[4] = -bbMin.z; + pTemp->m_AABBDistances[5] = bbMax.z; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::RayNodeTest_r( CDispCollTreeTempData *pTemp, int nodeIndex, Vector rayStart, Vector rayEnd ) +{ + // get the current node + CDispCollNode *pNode = &m_pNodes[nodeIndex]; + + // + // get node bounding box and create collision planes + // + Vector bounds[2]; + pNode->GetBounds( bounds[0], bounds[1] ); + CreatePlanesFromBounds( pTemp, bounds[0], bounds[1] ); + + bool bIntersect = RayAABBTest( pTemp, rayStart, rayEnd ); + if( bIntersect ) + { + // done -- add triangles to triangle list + if( pNode->IsLeaf() ) + { + // Assert for now -- flush cache later!!!!! + Assert( pTemp->m_TriListCount >= 0 ); + Assert( pTemp->m_TriListCount < TRILIST_CACHE_SIZE ); + + pTemp->m_ppTriList[pTemp->m_TriListCount] = &pNode->m_Tris[0]; + pTemp->m_ppTriList[pTemp->m_TriListCount+1] = &pNode->m_Tris[1]; + pTemp->m_TriListCount += 2; + } + // continue recursion + else + { + for( int i = 0; i < 4; i++ ) + { + RayNodeTest_r( pTemp, GetChildNode( nodeIndex, i ), rayStart, rayEnd ); + } + } + } +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::RayTestAllTris( CDispCollData *pData, int power ) +{ + // + // get leaf indices + // + int startIndex = CalcNodeCount( power - 1 ); + int endIndex = CalcNodeCount( power ); + + // save incoming fraction + float startFraction = pData->m_Fraction; + float fraction = pData->m_Fraction; + + Vector ray = pData->m_EndPos - pData->m_StartPos; + Vector rayDir = ray; + float rayLength = VectorNormalize(rayDir); + + // + // test ray against all triangles in list + // + for( int index = startIndex; index < endIndex; index++ ) + { + for( int j = 0; j < 2; j++ ) + { + bool bResult = RayTriTest( pData->m_StartPos, rayDir, rayLength, &m_pNodes[index].m_Tris[j], &fraction ); + if( !bResult ) + continue; + + if( pData->m_bOcclude ) + { + return true; + } + + if( fraction < pData->m_Fraction ) + { + pData->m_Fraction = fraction; + pData->m_Normal = m_pNodes[index].m_Tris[j].m_Normal; + pData->m_Distance = m_pNodes[index].m_Tris[j].m_Distance; + } + } + } + + // collision! + if( pData->m_Fraction < startFraction ) + return true; + + // no collision! + return false; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::RayTest( CDispCollData *pData ) +{ + // reset the triangle list count + CDispCollTreeTempData tmp; + tmp.m_TriListCount = 0; + + // trace against nodes (copy start, end because they change) + RayNodeTest_r( &tmp, 0, pData->m_StartPos, pData->m_EndPos ); + + // + // trace against tris (if need be) + // + if( tmp.m_TriListCount != 0 ) + { + bool result = RayTriListTest( &tmp, pData ); + return result; + } + + return false; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::SweptAABBTriIntersect( Vector &rayStart, Vector &rayEnd, Vector &extents, + CDispCollTri const *pTri, Vector &plNormal, float *plDist, + float *fraction ) +{ + + // + // PUT A COPY HERE OF START AND END -- SINCE I CHANGE THEM!!!!!! + // + + + + + + int dir, ptIndex; + float closeValue; + float distStart, distEnd; + float t; + Vector rayPt; + + // get ray direction + Vector rayDir = rayEnd - rayStart; + + // initialize fraction + *fraction = 1.0f; + + // + // test for collision with axial planes (x, y, z) + // + for( dir = 0; dir < 3; dir++ ) + { + if( rayDir[dir] < 0.0f ) + { + closeValue = -99999.9f; + for( ptIndex = 0; ptIndex < 3; ptIndex++ ) + { + if( pTri->m_Points[ptIndex][dir] > closeValue ) + { + closeValue = pTri->m_Points[ptIndex][dir]; + } + } + + closeValue += extents[dir]; + + distStart = rayStart[dir] - closeValue; + distEnd = rayEnd[dir] - closeValue; + } + else + { + closeValue = 99999.9f; + for( ptIndex = 0; ptIndex < 3; ptIndex++ ) + { + if( pTri->m_Points[ptIndex][dir] < closeValue ) + { + closeValue = pTri->m_Points[ptIndex][dir]; + } + } + + closeValue -= extents[dir]; + + distStart = -( rayStart[dir] - closeValue ); + distEnd = -( rayEnd[dir] - closeValue ); + } + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal.Init(); + plNormal[dir] = 1.0f; + *plDist = closeValue; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + } + + // + // check for an early out + // + if( ( pTri->m_Normal[0] > ONE_MINUS_COLLISION_EPSILON ) || + ( pTri->m_Normal[1] > ONE_MINUS_COLLISION_EPSILON ) || + ( pTri->m_Normal[2] > ONE_MINUS_COLLISION_EPSILON ) ) + { + if( *fraction == 1.0f ) + return false; + + return true; + } + + // + // handle 9 edge tests + // + Vector normal; + Vector edge; + float dist; + + // find the closest box point + Vector boxPt( 0.0f, 0.0f, 0.0f ); + for( dir = 0; dir < 3; dir++ ) + { + if( rayDir[dir] < 0.0f ) + { + boxPt[dir] = extents[dir]; + } + else + { + boxPt[dir] = -extents[dir]; + } + } + + // + // edge 0 + // + edge = pTri->m_Points[1] - pTri->m_Points[0]; + + // cross x-edge + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + + // extents adjusted dist + dist = ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); + + // find distances from plane (start, end) + distStart = ( normal.y * rayStart.y ) + ( normal.z * rayStart.z ) - dist; + distEnd = ( normal.y * rayEnd.y ) + ( normal.z * rayEnd.z ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // cross y-edge + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + + // extents adjusted dist + dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); + + // find distances from plane (start, end) + distStart = ( normal.x * rayStart.x ) + ( normal.z * rayStart.z ) - dist; + distEnd = ( normal.x * rayEnd.x ) + ( normal.z * rayEnd.z ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // cross z-edge + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + + // extents adjusted dist + dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ); + + // find distances from plane (start, end) + distStart = ( normal.x * rayStart.x ) + ( normal.y * rayStart.y ) - dist; + distEnd = ( normal.x * rayEnd.x ) + ( normal.y * rayEnd.y ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // + // edge 1 + // + edge = pTri->m_Points[2] - pTri->m_Points[1]; + + // cross x-edge + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + + // extents adjusted dist + dist = ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); + + // find distances from plane (start, end) + distStart = ( normal.y * rayStart.y ) + ( normal.z * rayStart.z ) - dist; + distEnd = ( normal.y * rayEnd.y ) + ( normal.z * rayEnd.z ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // cross y-edge + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + + // extents adjusted dist + dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); + + // find distances from plane (start, end) + distStart = ( normal.x * rayStart.x ) + ( normal.z * rayStart.z ) - dist; + distEnd = ( normal.x * rayEnd.x ) + ( normal.z * rayEnd.z ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // cross z-edge + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + + // extents adjusted dist + dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ); + + // find distances from plane (start, end) + distStart = ( normal.x * rayStart.x ) + ( normal.y * rayStart.y ) - dist; + distEnd = ( normal.x * rayEnd.x ) + ( normal.y * rayEnd.y ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // + // edge 2 + // + edge = pTri->m_Points[0] - pTri->m_Points[2]; + + // cross x-edge + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + + // extents adjusted dist + dist = ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); + + // find distances from plane (start, end) + distStart = ( normal.y * rayStart.y ) + ( normal.z * rayStart.z ) - dist; + distEnd = ( normal.y * rayEnd.y ) + ( normal.z * rayEnd.z ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // cross y-edge + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + + // extents adjusted dist + dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); + + // find distances from plane (start, end) + distStart = ( normal.x * rayStart.x ) + ( normal.z * rayStart.z ) - dist; + distEnd = ( normal.x * rayEnd.x ) + ( normal.z * rayEnd.z ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // cross z-edge + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + + // extents adjusted dist + dist = ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ); + + // find distances from plane (start, end) + distStart = ( normal.x * rayStart.x ) + ( normal.y * rayStart.y ) - dist; + distEnd = ( normal.x * rayEnd.x ) + ( normal.y * rayEnd.y ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // + // test face plane + // + dist = ( pTri->m_Normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + + ( pTri->m_Normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + + ( pTri->m_Normal.z * ( boxPt.z - pTri->m_Points[0].z ) ); + + distStart = pTri->m_Normal.Dot( rayStart ) - dist; + distEnd = pTri->m_Normal.Dot( rayEnd ) - dist; + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + t = ( distStart - COLLISION_EPSILON ) / ( distStart - distEnd ); + if( t > *fraction ) + { + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayStart ); + *fraction = t; + plNormal = normal; + *plDist = dist; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + t = ( distStart + COLLISION_EPSILON ) / ( distStart - distEnd ); + VectorScale( rayDir, t, rayPt ); + VectorAdd( rayStart, rayPt, rayEnd ); + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + if( *fraction == 1.0f ) + return false; + + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBTriIntersect( CDispCollTreeTempData *pTemp, CDispCollData *pData ) +{ + bool bResult = false; + + Vector normal; + float fraction, dist; + + // + // sweep ABB against all triangles in list + // + for( int i = 0; i < pTemp->m_TriListCount; i++ ) + { + if( pTemp->m_ppTriList[i]->IsIntersect() ) + { + bResult = SweptAABBTriIntersect( pData->m_StartPos, pData->m_EndPos, pData->m_Extents, + pTemp->m_ppTriList[i], normal, &dist, &fraction ); + if( bResult ) + { + if( fraction < pData->m_Fraction ) + { + pData->m_Fraction = fraction; + pData->m_Normal = normal; + pData->m_Distance = dist; + } + } + } + } + + return bResult; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::IntersectAABBTriTest( Vector &rayStart, Vector &extents, + CDispCollTri const *pTri ) +{ + int dir, ptIndex; + float dist; + + // + // test axail planes (x, y, z) + // + + for( dir = 0; dir < 3; dir++ ) + { + // + // negative axial plane, component = dir + // + dist = rayStart[dir] - extents[dir]; + for( ptIndex = 0; ptIndex < 3; ptIndex++ ) + { + if( pTri->m_Points[ptIndex][dir] > dist ) + break; + } + + if( ptIndex == 3 ) + return false; + + // + // positive axial plane, component = dir + // + dist = rayStart[dir] + extents[dir]; + for( ptIndex = 0; ptIndex < 3; ptIndex++ ) + { + if( pTri->m_Points[ptIndex][dir] < dist ) + break; + } + + if( ptIndex == 3 ) + return false; + } + + // + // add a test here to see if triangle face normal is close to axial -- done if so!!! + // + if( ( pTri->m_Normal[0] > ONE_MINUS_COLLISION_EPSILON ) || + ( pTri->m_Normal[1] > ONE_MINUS_COLLISION_EPSILON ) || + ( pTri->m_Normal[2] > ONE_MINUS_COLLISION_EPSILON ) ) + return true; + + // find the closest point on the box (use negated tri face noraml) + Vector boxPt( 0.0f, 0.0f, 0.0f ); + for( dir = 0; dir < 3; dir++ ) + { + if( pTri->m_Normal[dir] < 0.0f ) + { + boxPt[dir] = extents[dir]; + } + else + { + boxPt[dir] = -extents[dir]; + } + } + + // + // triangle plane test + // + // do the opposite because the ray has been negated + if( ( ( pTri->m_Normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + + ( pTri->m_Normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + + ( pTri->m_Normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) + return false; + + // + // test edge planes - 9 of them + // + Vector normal; + Vector edge; + + // + // edge 0 + // + edge = pTri->m_Points[1] - pTri->m_Points[0]; + + // cross x + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + if( ( ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) + return false; + + // cross y + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) + return false; + + // cross z + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) ) > 0.0f ) + return false; + + // + // edge 1 + // + edge = pTri->m_Points[2] - pTri->m_Points[1]; + + // cross x + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + if( ( ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) + return false; + + // cross y + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) + return false; + + // cross z + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) ) > 0.0f ) + return false; + + // + // edge 2 + // + edge = pTri->m_Points[0] - pTri->m_Points[2]; + + // cross x + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + if( ( ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) + return false; + + // cross y + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.z * ( boxPt.z - pTri->m_Points[0].z ) ) ) > 0.0f ) + return false; + + // cross z + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + if( ( ( normal.x * ( boxPt.x - pTri->m_Points[0].x ) ) + ( normal.y * ( boxPt.y - pTri->m_Points[0].y ) ) ) > 0.0f ) + return false; + + return true; +} + + + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::SweptAABBTriTest( Vector &rayStart, Vector &rayEnd, Vector &extents, + CDispCollTri const *pTri ) +{ + // get ray direction + Vector rayDir = rayEnd - rayStart; + + // + // quick and dirty test -- test to see if the object is traveling away from triangle surface??? + // + if( pTri->m_Normal.Dot( rayDir ) > 0.0f ) + return false; + + // + // calc the swept triangle face (negate the ray -- opposite direction of box travel) + // + rayDir.Negate(); + + Vector points[3]; + points[0] = pTri->m_Points[0] + rayDir; + points[1] = pTri->m_Points[1] + rayDir; + points[2] = pTri->m_Points[2] + rayDir; + + // + // handle 4 faces tests (3 axial planes and triangle face) + // + int dir; + float dist; + + // + // axial planes tests (x, y, z) + // + for( dir = 0; dir < 3; dir++ ) + { + bool bOutside = true; + + if( rayDir[dir] < 0.0f ) + { + dist = rayStart[dir] - extents[dir]; + for( int ptIndex = 0; ptIndex < 3; ptIndex ) + { + if( points[ptIndex][dir] > dist ) + { + bOutside = false; + break; + } + } + } + else + { + dist = rayStart[dir] + extents[dir]; + for( int ptIndex = 0; ptIndex < 3; ptIndex ) + { + if( pTri->m_Points[ptIndex][dir] < dist ) + { + bOutside = false; + break; + } + } + } + + if( bOutside ) + return false; + } + + // + // add a test here to see if triangle face normal is close to axial -- done if so!!! + // + if( ( pTri->m_Normal[0] > ONE_MINUS_COLLISION_EPSILON ) || + ( pTri->m_Normal[1] > ONE_MINUS_COLLISION_EPSILON ) || + ( pTri->m_Normal[2] > ONE_MINUS_COLLISION_EPSILON ) ) + return true; + + // + // handle 9 edge tests - always use the newly swept face for this + // + Vector normal; + Vector edge; + + // find the closest box point - (is written opposite to normal due to negating ray) + Vector boxPt( 0.0f, 0.0f, 0.0f ); + for( dir = 0; dir < 3; dir++ ) + { + if( rayDir[dir] < 0.0f ) + { + boxPt[dir] = rayStart[dir] - extents[dir]; + } + else + { + boxPt[dir] = rayStart[dir] + extents[dir]; + } + } + + // + // edge 0 + // + edge = points[1] - points[0]; + + // cross x-edge + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + if( ( ( normal.y * ( boxPt.y - points[0].y ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) + return false; + + // cross, y-edge + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) + return false; + + // cross z-edge + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.y * ( boxPt.y - points[0].y ) ) ) > 0.0f ) + return false; + + // + // edge 1 + // + edge = points[2] - points[1]; + + // cross x-edge + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + if( ( ( normal.y * ( boxPt.y - points[0].y ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) + return false; + + // cross, y-edge + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) + return false; + + // cross z-edge + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.y * ( boxPt.y - points[0].y ) ) ) > 0.0f ) + return false; + + // + // edge 2 + // + edge = points[0] - points[2]; + + // cross x-edge + normal.x = 0.0f; + normal.y = -edge.z; + normal.z = edge.y; + if( ( ( normal.y * ( boxPt.y - points[0].y ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) + return false; + + // cross, y-edge + normal.x = edge.z; + normal.y = 0.0f; + normal.z = edge.y; + if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) + return false; + + // cross z-edge + normal.x = -edge.y; + normal.y = edge.x; + normal.z = 0.0f; + if( ( ( normal.x * ( boxPt.x - points[0].x ) ) + ( normal.y * ( boxPt.y - points[0].y ) ) ) > 0.0f ) + return false; + + // + // triangle plane test + // + // do the opposite because the ray has been negated + if( ( ( pTri->m_Normal.x * ( boxPt.x - points[0].x ) ) + + ( pTri->m_Normal.y * ( boxPt.y - points[0].y ) ) + + ( pTri->m_Normal.z * ( boxPt.z - points[0].z ) ) ) > 0.0f ) + return false; + + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::CullTriList( CDispCollTreeTempData *pTemp, Vector &rayStart, Vector &rayEnd, Vector &extents, bool bIntersect ) +{ + // + // intersect AABB with all triangles in list + // + if( bIntersect ) + { + for( int i = 0; i < pTemp->m_TriListCount; i++ ) + { + if( IntersectAABBTriTest( rayStart, extents, pTemp->m_ppTriList[i] ) ) + return true; + } + + return false; + } + // + // sweep AABB against all triangles in list + // + else + { + bool bResult = false; + + for( int i = 0; i < pTemp->m_TriListCount; i++ ) + { + if( SweptAABBTriTest( rayStart, rayEnd, extents, pTemp->m_ppTriList[i] ) ) + { + pTemp->m_ppTriList[i]->SetIntersect( true ); + bResult = true; + } + } + + return bResult; + } +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::IntersectAABBAABBTest( CDispCollTreeTempData *pTemp, const Vector &pos, const Vector &extents ) +{ + float dist; + + for( int dir = 0; dir < 3; dir++ ) + { + // negative direction + dist = -( pos[dir] - ( pTemp->m_AABBDistances[(dir>>1)] - extents[dir] ) ); + if( dist > COLLISION_EPSILON ) + return false; + + // positive direction + dist = pos[dir] - ( pTemp->m_AABBDistances[(dir>>1)+1] + extents[dir] ); + if( dist > COLLISION_EPSILON ) + return false; + } + + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::SweptAABBAABBTest( CDispCollTreeTempData *pTemp, const Vector &rayStart, const Vector &rayEnd, const Vector &extents ) +{ + int dir; + float distStart, distEnd; + float fraction; + float deltas[3]; + float scalers[3]; + + // + // enter and exit fractions + // + float enterFraction = 0.0f; + float exitFraction = 0.0f; + + // + // de-normalize the paramter space so that we don't have to divide + // to find the fractional amount later (clamped for precision) + // + deltas[0] = rayEnd.x - rayStart.x; + deltas[1] = rayEnd.y - rayStart.y; + deltas[2] = rayEnd.z - rayStart.z; + if( ( deltas[0] < COLLISION_EPSILON ) && ( deltas[0] > -COLLISION_EPSILON ) ) { deltas[0] = 1.0f; } + if( ( deltas[1] < COLLISION_EPSILON ) && ( deltas[1] > -COLLISION_EPSILON ) ) { deltas[0] = 1.0f; } + if( ( deltas[2] < COLLISION_EPSILON ) && ( deltas[2] > -COLLISION_EPSILON ) ) { deltas[0] = 1.0f; } + scalers[0] = deltas[1] * deltas[2]; + scalers[1] = deltas[0] * deltas[2]; + scalers[2] = deltas[0] * deltas[1]; + + for( dir = 0; dir < 3; dir++ ) + { + // + // negative direction + // + distStart = -( rayStart[dir] - ( pTemp->m_AABBDistances[(dir>>1)] - extents[dir] ) ); + distEnd = -( rayEnd[dir] - ( pTemp->m_AABBDistances[(dir>>1)] - extents[dir] ) ); + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + fraction = distStart * scalers[dir]; + if( fraction > enterFraction ) + { + enterFraction = fraction; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + fraction = distStart * scalers[dir]; + if( fraction < exitFraction ) + { + exitFraction = fraction; + } + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + + // + // positive direction + // + distStart = rayStart[dir] - ( pTemp->m_AABBDistances[(dir>>1)+1] + extents[dir] ); + distEnd = rayEnd[dir] - ( pTemp->m_AABBDistances[(dir>>1)+1] + extents[dir] ); + + if( ( distStart > COLLISION_EPSILON ) && ( distEnd < -COLLISION_EPSILON ) ) + { + fraction = distStart * scalers[dir]; + if( fraction > enterFraction ) + { + enterFraction = fraction; + } + } + else if( ( distStart < -COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + fraction = distStart * scalers[dir]; + if( fraction < exitFraction ) + { + exitFraction = fraction; + } + } + else if( ( distStart > COLLISION_EPSILON ) && ( distEnd > COLLISION_EPSILON ) ) + { + return false; + } + } + + if( exitFraction < enterFraction ) + return false; + + return true; +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +void CDispCollTree::BuildTriList_r( CDispCollTreeTempData *pTemp, int nodeIndex, Vector &rayStart, Vector &rayEnd, Vector &extents, + bool bIntersect ) +{ + // + // get the current nodes bounds and create collision test planes + // (saved in the in class cache m_AABBNormals, m_AABBDistances) + // + Vector bounds[2]; + CDispCollNode *pNode = &m_pNodes[nodeIndex]; + pNode->GetBounds( bounds[0], bounds[1] ); + CreatePlanesFromBounds( pTemp, bounds[0], bounds[1] ); + + // + // interesect/sweep test + // + bool bResult; + if( bIntersect ) + { + bResult = IntersectAABBAABBTest( pTemp, rayStart, extents ); + } + else + { + bResult = SweptAABBAABBTest( pTemp, rayStart, rayEnd, extents ); + } + + if( bResult ) + { + // if leaf node -- add triangles to interstection test list + if( pNode->IsLeaf() ) + { + // Assert for now -- flush cache later!!!!! + Assert( pTemp->m_TriListCount >= 0 ); + Assert( pTemp->m_TriListCount < TRILIST_CACHE_SIZE ); + + pTemp->m_ppTriList[pTemp->m_TriListCount] = &pNode->m_Tris[0]; + pTemp->m_ppTriList[pTemp->m_TriListCount+1] = &pNode->m_Tris[1]; + pTemp->m_TriListCount += 2; + } + // continue recursion + else + { + BuildTriList_r( pTemp, GetChildNode( nodeIndex, 0 ), rayStart, rayEnd, extents, bIntersect ); + BuildTriList_r( pTemp, GetChildNode( nodeIndex, 1 ), rayStart, rayEnd, extents, bIntersect ); + BuildTriList_r( pTemp, GetChildNode( nodeIndex, 2 ), rayStart, rayEnd, extents, bIntersect ); + BuildTriList_r( pTemp, GetChildNode( nodeIndex, 3 ), rayStart, rayEnd, extents, bIntersect ); + } + } +} + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBSweep( CDispCollData *pData ) +{ + // reset the triangle lists counts + CDispCollTreeTempData tmp; + tmp.m_TriListCount = 0; + + // sweep the AABB against the tree + BuildTriList_r( &tmp, 0, pData->m_StartPos, pData->m_EndPos, pData->m_Extents, false ); + + // find collision triangles + if( CullTriList( &tmp, pData->m_StartPos, pData->m_EndPos, pData->m_Extents, false ) ) + { + // find closest intersection + return AABBTriIntersect( &tmp, pData ); + } + + return false; +} + + + +//----------------------------------------------------------------------------- +// Purpose: +//----------------------------------------------------------------------------- +bool CDispCollTree::AABBIntersect( CDispCollData *pData ) +{ + // reset the triangle lists counts + CDispCollTreeTempData tmp; + tmp.m_TriListCount = 0; + + // sweep the AABB against the tree + BuildTriList_r( &tmp, 0, pData->m_StartPos, pData->m_StartPos, pData->m_Extents, true ); + + // find collision triangles + return CullTriList( &tmp, pData->m_StartPos, pData->m_StartPos, pData->m_Extents, true ); +} -- cgit v1.2.3