D:/Zythum/DinoKod/Bsp/Bsp.cpp

//---------------------------------------------------------------------------------------------
//      This file is a part of "DinoKod".
//      Copyright © 2003 Dino Productions. All Rights Reserved.
//      
//      File                    : Bsp.cpp
//      Author                  : Sebastien LEIX        sebastien.leix@wanadoo.fr
//      Date                    : 07/09/2002
//      Modification    :
//
//---------------------------------------------------------------------------------------------
#include <conio.h>

#include "Common/Assert.h"
#include "Common/Error.h"
#include "Common/Console.h"
#include "Common/Directory.h"
#include "Common/Plane.h"
//#include "Common/Math3D.h"
#include "Common/Vertex.h"
#include "Physics/PhysicsCollision.h"

#include "Bsp/BezierPatch.h"

#include "Bsp/Bsp.h"

#define EPSILON 0.03125f        // 1/32 float

//---------------------------------------------------------------------------------------------------------------------
KBsp::KBsp()
: KBspLoader()
{
        m_pBezierPatches                = 0;
        m_pComputedVertices             = NULL;
}

//---------------------------------------------------------------------------------------------------------------------
KBsp::~KBsp()
{
}

//---------------------------------------------------------------------------------------------------------------------
s32 KBsp::LoadBSP( const char* pFileName )
{
        
        s32                     Result;
//      char            pFullName[1024];
//      const char*     pPath;

//      pPath = g_Directory.GetPath( "Datas" );

//      strcpy( pFullName, pPath );
//      strcat( pFullName, pFileName );

        // Charge le BSP
        g_Console << "Loading map [" << (char*)pFileName << "]...";

        Result = KBspLoader::LoadBSP( pFileName );

        switch( Result )
        {
        case BSP_OK:
                g_Console << "OK" << KENDL;
                g_Console << "Nb Vertices  : " << (int)m_nVertices << KENDL;
                g_Console << "Nb Faces     : " << (int)m_nFaces << KENDL;
                g_Console << "Nb Shaders   : " << (int)m_nShaders << KENDL;
                g_Console << "Nb Lightmaps : " << (int)m_nLightMaps << KENDL;
                break;
        case BSP_ERROR_OPENFILE:
                g_Console << "Cannot open file." << KENDL;
                return Result;
        case BSP_ERROR_BADVERSION:
                g_Console << "Bad version." << KENDL;
                return Result;
        }

        m_pBezierPatches        = new KBezierPatch[m_nFaces];
        m_pComputedVertices     = new KLVertex2[m_nVertices];

        ComputeVertices();
        ComputeBezier();

        return BSP_OK;
}

//---------------------------------------------------------------------------------------------------------------------
s32 KBsp::CloseBSP()
{
        if( m_pBezierPatches )
                Deletev( m_pBezierPatches );
        
        if( m_pComputedVertices )
                Deletev( m_pComputedVertices );

        return KBspLoader::CloseBSP();
}

//---------------------------------------------------------------------------------------------------------------------
u32 KBsp::FindLeaf( u32 NodeId, KVector& Position )
{
        if( KVector::DotProduct( m_pPlanes[m_pNodes[NodeId].m_PlaneId].m_Normal, Position ) -  m_pPlanes[m_pNodes[NodeId].m_PlaneId].m_Distance >= 0 )
        {
                // Devant
                if( m_pNodes[NodeId].m_Front & 0x8000 )
                {
                        // Leaf trouvé
                        return (u16)-( m_pNodes[NodeId].m_Front + 1);
                }
                else
                        return FindLeaf( m_pNodes[NodeId].m_Front, Position );
        }

        // Derriere
        if( m_pNodes[NodeId].m_Back & 0x8000 )
        {
                // Leaf trouvé
                return (u16)-( m_pNodes[NodeId].m_Back + 1);
        }
        else
                return FindLeaf( m_pNodes[NodeId].m_Back, Position );           
}

//---------------------------------------------------------------------------------------------------------------------
void KBsp::ComputeVertices()
{
        u32     v;

        for( v = 0; v < m_nVertices; v ++ )
        {
                KRgba   Color = KRgba( 255, 255, 255, 255 );
                
/*              if( !m_bUseLightMaps )
                {
                        Color = m_pVertices[v].m_Color;
                        if( m_bSwapRgb )
                                Color.Swap();
                }
*/
                m_pComputedVertices[v].Position         = m_pVertices[v].m_Position;
                m_pComputedVertices[v].Color            = KRGBA2INT( Color );
                m_pComputedVertices[v].tu1                      = m_pVertices[v].m_UV[0].x;
                m_pComputedVertices[v].tv1                      = m_pVertices[v].m_UV[0].y;
                m_pComputedVertices[v].tu2                      = m_pVertices[v].m_UV[1].x;
                m_pComputedVertices[v].tv2                      = m_pVertices[v].m_UV[1].y;
        }
}

//---------------------------------------------------------------------------------------------------------------------
void KBsp::ComputeBezier()
{
        KASSERT( m_pBezierPatches );

        for( u32 i = 0; i < m_nFaces; i ++ )
        {
                if( m_pFaces[i].m_Type == KBFT_PATCH )
                {
                        m_pBezierPatches[i].GenerateVertices( &m_pComputedVertices[m_pFaces[i].m_FirstVertexId], KPt( m_pFaces[i].m_Size ) );
                }
        }
}

//---------------------------------------------------------------------------------------------------------------------
//-- COLLISION
//---------------------------------------------------------------------------------------------------------------------
void KBsp::CheckSphereCollision( u32 NodeId, KPhysicsCollisionData* pData )
{
        float   Radius;

        Radius = MAX( MAX( pData->m_eRadius.x, pData->m_eRadius.y ), pData->m_eRadius.z );
        Radius += pData->m_R3Velocity.Magnitude();

        float   fDist   = KVector::DotProduct( m_pPlanes[m_pNodes[NodeId].m_PlaneId].m_Normal, pData->m_R3Position ) - m_pPlanes[m_pNodes[NodeId].m_PlaneId].m_Distance;

        if( fDist >= -Radius )
        {
                // Devant
                if( m_pNodes[NodeId].m_Front & 0x8000 )
                {
                        // Leaf trouvé
                        CheckLeafSphereCollision( (u16)-( m_pNodes[NodeId].m_Front + 1), pData );
                }
                else
                        CheckSphereCollision( m_pNodes[NodeId].m_Front, pData );
        }

        if( fDist <= Radius )
        {
                // Derriere
                if( m_pNodes[NodeId].m_Back & 0x8000 )
                {
                        // Leaf trouvé
                        CheckLeafSphereCollision( (u16)-( m_pNodes[NodeId].m_Back + 1), pData );
                }
                else
                        CheckSphereCollision( m_pNodes[NodeId].m_Back, pData );
        }
}

//---------------------------------------------------------------------------------------------------------------------
bool KBsp::CheckLeafSphereCollision( u32 LeafId, KPhysicsCollisionData* pData )
{
        s32             FaceId;
        u32             Face;
        s32             MeshVertId;
        KVector pVertex[3];

        if( !LeafId )
                return false;

//      DrawLeaf( LeafId );

        for(    FaceId = m_pLeaves[LeafId].m_FirstFaceId;
                        FaceId < m_pLeaves[LeafId].m_FirstFaceId + m_pLeaves[LeafId].m_NumFaces;
                        FaceId ++ )

        {
                Face = m_pFaceList[FaceId].m_Face;
                
                //
                //      POLYGON
                //
                if( m_pFaces[Face].m_Type == KBFT_POLYGON )
                {
                        for(    MeshVertId = m_pFaces[Face].m_FirstMeshVert;
                                        MeshVertId < m_pFaces[Face].m_FirstMeshVert + m_pFaces[Face].m_NumMeshVerts;
                                        MeshVertId += 3 )
                        {
                                pVertex[0] = m_pVertices[m_pFaces[Face].m_FirstVertexId + m_pMeshVerts[MeshVertId + 0].m_FirstVertexId].m_Position;
                                pVertex[1] = m_pVertices[m_pFaces[Face].m_FirstVertexId + m_pMeshVerts[MeshVertId + 2].m_FirstVertexId].m_Position;
                                pVertex[2] = m_pVertices[m_pFaces[Face].m_FirstVertexId + m_pMeshVerts[MeshVertId + 1].m_FirstVertexId].m_Position;

#if _DEBUG
        m_DebugCollFace ++;
#endif _DEBUG
                                KPhysicsCollision::CheckSphereCollision( pData, pVertex[0], pVertex[1], pVertex[2] );
                        }
                }

                
                //
                //      MESH
                //
                if( m_pFaces[Face].m_Type == KBFT_MESH )
                {
                        for(    MeshVertId = m_pFaces[Face].m_FirstMeshVert;
                                        MeshVertId < m_pFaces[Face].m_FirstMeshVert + m_pFaces[Face].m_NumMeshVerts;
                                        MeshVertId += 3 )
                        {
                                pVertex[0] = m_pVertices[m_pFaces[Face].m_FirstVertexId + m_pMeshVerts[MeshVertId + 0].m_FirstVertexId].m_Position;
                                pVertex[1] = m_pVertices[m_pFaces[Face].m_FirstVertexId + m_pMeshVerts[MeshVertId + 2].m_FirstVertexId].m_Position;
                                pVertex[2] = m_pVertices[m_pFaces[Face].m_FirstVertexId + m_pMeshVerts[MeshVertId + 1].m_FirstVertexId].m_Position;

#if _DEBUG
        m_DebugCollFace ++;
#endif _DEBUG
                                KPhysicsCollision::CheckSphereCollision( pData, pVertex[0], pVertex[1], pVertex[2] );
                        }
                }

                //
                //      PATCH
                //
                if( m_pFaces[Face].m_Type == KBFT_PATCH )
                {
                        for(    MeshVertId = 0;
                                        MeshVertId < m_pBezierPatches[Face].GetnIndices();
                                        MeshVertId += 3 )
                        {
                                pVertex[0] = m_pBezierPatches[Face].GetpVertices()[m_pBezierPatches[Face].GetpIndices()[MeshVertId + 0]].Position;
                                pVertex[1] = m_pBezierPatches[Face].GetpVertices()[m_pBezierPatches[Face].GetpIndices()[MeshVertId + 2]].Position;
                                pVertex[2] = m_pBezierPatches[Face].GetpVertices()[m_pBezierPatches[Face].GetpIndices()[MeshVertId + 1]].Position;

#if _DEBUG
        m_DebugCollFace ++;
#endif _DEBUG
                                KPhysicsCollision::CheckSphereCollision( pData, pVertex[0], pVertex[1], pVertex[2] );
                        }
                }
        }

        return true;
}

// Here comes the Hard Stuff. First read the Collision.html to get a fully 
// explanation of how this work
// This function take an Star location and a target and see if the ray collide with 
// something. All the information need to handle the collision is returned in the
// sMoveData.
//---------------------------------------------------------------------------------------------------------------------
KBspCollisionData KBsp::CheckRayMove( KVector& vStart, KVector& vEnd )
{
        KBspCollisionData       CollisionData;

        // Initializations, This will change if the traversal detect it was wrong
        CollisionData.m_StartOut        = true;    
        CollisionData.m_AllSolid        = false;
        CollisionData.m_Fraction        = 1.0f;
        // Necessary info to collide with brushes
        CollisionData.m_Start           = vStart;
        CollisionData.m_End                     = vEnd;
        CollisionData.m_ObjectType      = BSP_COLL_RAY;
        CollisionData.m_MoveOffset      = 0.0f;

        // walk through the BSP tree
        CheckMoveByNode( 0, 0.0f, 1.0f, vStart, vEnd, CollisionData );

        if( CollisionData.m_Fraction == 1.0f)
        {       // nothing blocked the trace
                CollisionData.m_EndPoint = vEnd;
        }
        else
        {       // collided with something 
                CollisionData.m_EndPoint = vStart + ( vEnd - vStart ) * CollisionData.m_Fraction;
        }
        return CollisionData;
}

// Here comes the Hard Stuff. First read the Collision.html to get a fully 
// explanation of how this work
//---------------------------------------------------------------------------------------------------------------------
KBspCollisionData KBsp::CheckSphereMove( KVector& vStart, KVector& vEnd, float Radius )
{
        KBspCollisionData       CollisionData;

        // Initializations, This will change if the traversal detect it was wrong
        CollisionData.m_StartOut                = true;    
        CollisionData.m_AllSolid                = false;
        CollisionData.m_Fraction                = 1.0f;
        // Necessary info to collide with brushes
        CollisionData.m_Start                   = vStart;
        CollisionData.m_End                             = vEnd;
        CollisionData.m_ObjectType              = BSP_COLL_SPHERE;
        CollisionData.m_MoveOffset              = Radius;

        // walk through the BSP tree
        CheckMoveByNode( 0, 0.0f, 1.0f, vStart, vEnd, CollisionData );

        if( CollisionData.m_Fraction == 1.0f )
        {       // nothing blocked the trace
                CollisionData.m_EndPoint = vEnd;
        }
        else
        {       // collided with something 
                CollisionData.m_EndPoint = vStart + ( vEnd - vStart ) * CollisionData.m_Fraction;
        }
        return CollisionData;
}

// Check if we collide with something of this node ( including children and leafs
//---------------------------------------------------------------------------------------------------------------------
void KBsp::CheckMoveByNode( s32 NodeId, float StartFraction, float EndFraction, KVector& vStart, KVector vEnd, KBspCollisionData& CollisionData )
{
        // If the path was blocked by a nearer obstacle, don't bother checking
        if( CollisionData.m_Fraction <= StartFraction) 
                return;

        if( NodeId < 0 )
        {       // this is a leaf
                KBspLeaf* pLeaf = &m_pLeaves[~NodeId];  // Get a pointer from the m_pLeafs Array. 
                                                                                                // Remember that NodeIndex is negative so the corresponding leafs is
                                                                                                // ~nodeIndex which is same of saying -(NodeIndex+1) but faster!
                                                                                                // Loop by all the brushes 
                for( s32 i = 0; i < pLeaf->m_NumBrushes; i++ )
                {
                        //Take a point to the i-th brush in the leaf
                        KBspBrush* pBrush = &m_pBrushes[m_pBrushList[pLeaf->m_FirstBrushId + i].m_Brush];

                        // If the brush has sides (is a convex volume) and is SOLID then check it out!
                        if( pBrush->m_NumBrushSides > 0 && ( m_pShaders[pBrush->m_TextureId].m_Contents & 1 ) )
                        {
                                CheckTouchBrush( pBrush, CollisionData );
                        }
                }
        
                // don't have to do anything else for leaves
                return;
        }

        // this is a node.
        // Get pointer to the Node it self and to the splitter plane
        KBspNode*       pNode   = &m_pNodes[NodeId];
        KBspPlane*      pPlane  = &m_pPlanes[pNode->m_PlaneId];

        // Get the distance from the start and end point to the plane. This is done with the Plane formula:
        float StartDistance =   pPlane->m_Normal.x * vStart.x + 
                                                        pPlane->m_Normal.y * vStart.y + 
                                                        pPlane->m_Normal.z * vStart.z - 
                                                        pPlane->m_Distance;
        float EndDistance   =   pPlane->m_Normal.x * vEnd.x + 
                                                        pPlane->m_Normal.y * vEnd.y + 
                                                        pPlane->m_Normal.z * vEnd.z - 
                                                        pPlane->m_Distance;

        // If both points are in front of the plane (the positive side) pass the ray to the front 
        // child as the ray comes.
        
        if( ( StartDistance >= CollisionData.m_MoveOffset ) && ( EndDistance >= CollisionData.m_MoveOffset ) )
        {       
                CheckMoveByNode( pNode->m_Front, StartFraction, EndFraction, vStart, vEnd, CollisionData );
        }

        // If both points are in behind the plane (the negative side) pass the ray to the back 
        // child as the ray comes.

        else if( ( StartDistance < -CollisionData.m_MoveOffset ) && ( EndDistance < -CollisionData.m_MoveOffset ) )
        {
                CheckMoveByNode( pNode->m_Back, StartFraction, EndFraction, vStart, vEnd, CollisionData );
        }

        else
        {       // the line spans the splitting plane
                s32                     Side1, Side2;                           // Variables to hold which side to traverse first and which second
                float           Fraction1, Fraction2;           // Used to know compute the Smiddle and Emiddle. 
                KVector         vMiddle;                                        // middle point (Smiddle and Emiddle)

                // split the segment into two

                // If we know that one is positive and the other is negative, and startDistance < endDistance, so 
                // startDistance is negative and endDistance is positive (front and back correspondingly)
                if( StartDistance < EndDistance )
                {
                        Side1 = pNode->m_Back;    // the back side contains the start point so the back will be the first
                        Side2 = pNode->m_Front;    
                        float InverseDistance = 1.0f / ( StartDistance - EndDistance ); // optimization
                        Fraction1 = ( StartDistance - EPSILON - CollisionData.m_MoveOffset ) * InverseDistance;   // compute fraction for the start-middle
                        Fraction2 = ( StartDistance + EPSILON + CollisionData.m_MoveOffset ) * InverseDistance;   // compute fraction for the middle-end
                }
                // On the other hand if endDistance is negative and startDistance is positive
                else if ( EndDistance < StartDistance )
                {
                        Side1 = pNode->m_Front;   // the front side contains the start point so the front will be the first
                        Side2 = pNode->m_Back;
                        float InverseDistance = 1.0f / ( StartDistance - EndDistance );
                        Fraction1 = ( StartDistance + EPSILON + CollisionData.m_MoveOffset ) * InverseDistance;
                        Fraction2 = ( StartDistance - EPSILON - CollisionData.m_MoveOffset ) * InverseDistance;
                }
                else
                {
                        Side1 = pNode->m_Front;
                        Side2 = pNode->m_Back;
                        Fraction1 = 1.0f;
                        Fraction2 = 0.0f;
                }

                // make sure the numbers are valid
                if( Fraction1 < 0.0f ) Fraction1 = 0.0f;
                else if ( Fraction1 > 1.0f ) Fraction1 = 1.0f;
                if ( Fraction2 < 0.0f ) Fraction2 = 0.0f;
                else if ( Fraction2 > 1.0f ) Fraction2 = 1.0f;

                // calculate the middle point for the first side
                vMiddle            = vStart + ( vEnd - vStart ) * Fraction1;

                // get the Smiddle fraction (not just the point)
                float MiddleFraction = StartFraction + ( EndFraction - StartFraction) * Fraction1;

                // check the first side
                CheckMoveByNode( Side1, StartFraction, MiddleFraction, vStart, vMiddle, CollisionData );

                // calculate the middle point for the second side
                vMiddle = vStart + ( vEnd - vStart ) * Fraction2;

                // get the Emiddle fraction (not just the point)
                MiddleFraction = StartFraction + ( EndFraction - StartFraction ) * Fraction2;

                // check the second side
                CheckMoveByNode( Side2, MiddleFraction, EndFraction, vMiddle, vEnd, CollisionData );
        }
}

//---------------------------------------------------------------------------------------------------------------------
void KBsp::CheckTouchBrush( KBspBrush* pBrush, KBspCollisionData& CollisionData )
{
        float   StartFraction   = -1.0f;        // The S in the pictures
        float   EndFraction             = 1.0f;         // The E in the pictures
        bool    StartsOut               = false;        // If not plane change this value then the ray start IN
        bool    EndsOut                 = false;        // If not plane change this value then the ray end IN

        KVector         CandidateToHitNormal;

        // Go for every brush side 
        for( s32 i = 0; i < pBrush->m_NumBrushSides; i ++ )
        {
                // take a pointer to the brush side and the plane it represent
                KBspBrushSide*  pBrushSide      = &m_pBrushSides[pBrush->m_FirstBrushSideId + i];
                KBspPlane*              pPlane          = &m_pPlanes[pBrushSide->m_PlaneId];

                // Compute distances from the plane to the MStart and MEnd (the values enter at the begging of the trace
                float StartDistance =   pPlane->m_Normal.x * CollisionData.m_Start.x + 
                                                                pPlane->m_Normal.y * CollisionData.m_Start.y + 
                                                                pPlane->m_Normal.z * CollisionData.m_Start.z - 
                                                                pPlane->m_Distance - CollisionData.m_MoveOffset;
                float EndDistance   =   pPlane->m_Normal.x * CollisionData.m_End.x + 
                                                                pPlane->m_Normal.y * CollisionData.m_End.y + 
                                                                pPlane->m_Normal.z * CollisionData.m_End.z - 
                                                                pPlane->m_Distance - CollisionData.m_MoveOffset;

                // if the start point is in front this plane, then it can be IN the brush so it’s OUT
                if( StartDistance > 0 )
                        StartsOut = true;

                // if the end point is in front this plane, then it can be IN the brush so it’s OUT
                if( EndDistance > 0 )
                        EndsOut = true;

                // make sure the trace isn't completely on one side of the brush
                if( StartDistance > 0 && EndDistance > 0 )
                {   // both are in front of the plane, its outside of this brush
                        return;
                }

                if( StartDistance <= 0 && EndDistance <= 0 )
                {   // both are behind this plane, it will get clipped by another one
                        continue;
                }


                // The line is Red so is entering the brush. 
                // Compute the new S   (fraction)
                // if (the new S) > S    move S  and update CandidateToHitNormal                
                                
                if( StartDistance > EndDistance )
                {  
                        float Fraction = ( StartDistance - EPSILON ) / ( StartDistance - EndDistance );
                        if( Fraction > StartFraction)
                        {
                                StartFraction = Fraction;
                                CandidateToHitNormal = pPlane->m_Normal;
                        }
                }
                else
                        // The line is Black so is leaving the brush. 
                        // Compute the new E   (fraction)
                        // if (the new E) < E    move E
                {   
                        float Fraction = ( StartDistance + EPSILON ) / ( StartDistance - EndDistance );
                        if( Fraction < EndFraction )
                                EndFraction = Fraction;
                }
        }

        // After checking all sides if startOut remain false, then the Start Point is complete in the brush
                
        if( StartsOut == false )
        {
                CollisionData.m_StartOut = false;

        // if also the EndPoint is in this brush, then the ray is complete in this brush
                if( EndsOut == false )
                        CollisionData.m_AllSolid = true;
                return;
        }

        // if there was collision against the brush (S < E)
        if( StartFraction < EndFraction )
        {
                // And of course if we move S (if we don’t then we don’t enter the brush 
                // and we don’t collide with some nearest brush
                if( StartFraction > -1 && StartFraction < CollisionData.m_Fraction )
                {
                        // UpDate OutPut values

                        if( StartFraction < 0 )
                                StartFraction = 0;

                        CollisionData.m_Fraction                = StartFraction;
                        CollisionData.m_CollisionNormal = CandidateToHitNormal; // The candidate gets postulate!
                }
        }
}

---