From 39ed87570bdb2f86969d4be821c94b722dc71179 Mon Sep 17 00:00:00 2001 From: Joe Ludwig Date: Wed, 26 Jun 2013 15:22:04 -0700 Subject: First version of the SOurce SDK 2013 --- mp/src/public/dispcoll.cpp | 1994 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1994 insertions(+) create mode 100644 mp/src/public/dispcoll.cpp (limited to 'mp/src/public/dispcoll.cpp') diff --git a/mp/src/public/dispcoll.cpp b/mp/src/public/dispcoll.cpp new file mode 100644 index 00000000..d8dd85bc --- /dev/null +++ b/mp/src/public/dispcoll.cpp @@ -0,0 +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 ); +} -- cgit v1.2.3