[an error occurred while processing this directive] 
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= //
//
//  Project:   Talina Gaming System (TgS) (∂)
//  File:      TgS Collision - Sphere-Triangle.cpp
//  Author:    Andrew Aye (EMail: andrew.aye@gmail.com, Web: http://www.andrewaye.com) 
//  Version:   3.11
//
// ------------------------------------------------------------------------------------------------------------------------------ //
//
//  Copyright: © 2002-2008, Andrew Aye.  All Rights Reserved.
//
//  This software is free for non-commercial use. Redistribution and use in source and binary forms, with or without modification,
//  are permitted provided that the following conditions are met: 
//    Redistributions of source code must retain this copyright notice, this list of conditions and the following disclaimers. 
//    Redistributions in binary form must reproduce this copyright notice, this list of conditions and the following
//      disclaimers in the documentation and other materials provided with the distribution. 
//
//  Neither the names of the copyright owner nor the names of its contributors may be used to endorse or promote products derived
//  from this software without specific prior written permission. 
//
//  The intellectual property rights of the algorithms used reside with Andrew Aye.  You may not use this software, in whole or
//  in part, in support of any commercial product without the express written consent of the author.
//
//  There is no warranty or other guarantee of fitness of this software for any purpose. It is provided solely "as is".
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= //




namespace TGS { // START TGS ///////////////////////////////////////////////////////////////////////////////////////////////////////
namespace COL { // START COL ///////////////////////////////////////////////////////////////////////////////////////////////////////

// ============================================================================================================================== //

// ---- F_Internal_Penetrate ---------------------------------------------------------------------------------------------------- //
// Input:  tgPacket: The current series of contact points for this query-series, and contact generation parameters.
// Input:  tgCT0: Collision Triangle primitive
// Input:  tgSP0: Sphere primitive
// Output: tgPacket: Points of penetration between the two primitives are added to it
// Return: Result Code
// ------------------------------------------------------------------------------------------------------------------------------ //

template <typename TYPE, int DIM>
TgRESULT F_Internal_Penetrate( PC_(CONTACT_PACKET,DIM) ptgPacket, CR_(CTRI,DIM) tgCT0, CR_(SPHERE,DIM) tgSP0 )
{
    TgBLOCK_FCN_NOOBJ(ETgFAC_COLLISION, 0, ETgTEST_PENETRATE, (((TgUINT)ETgTRIANGLE<<16)|(TgUINT)ETgSPHERE));
    TgASSERT(!(0 == ptgPacket->m_niMaxContact || ptgPacket->m_niContact >= ptgPacket->m_niMaxContact));
    TgASSERT(!(0 == ptgPacket->m_ptgContact));

    TgFEBUG_COLLISION_TRIANGLE_CREATEID( iDBG_TriID, tgCT0, etgDEBUG_COLLISION_ENTERFCN );

    TYPE                                tyCT0, tyCT1;

    const TYPE                          tyDistSq = F_ClosestSq( &tyCT0,&tyCT1, tgCT0.Query_ET(), tgSP0.Query_Origin() );

    // Check to see if the proposed point of contact is on a reduced triangle feature.

    C_TgBOOL                            bCulled = Is_Point_Culled( tgCT0, tyCT0,tyCT1 );

    // Check to see if the reduced feature should be included for this case (only important if bCulled is true).

    C_TgBOOL                            bEdge = Is_Tri_Edge_Ignored( tgCT0.Query_ET(), tyCT0,tyCT1 );

    //  No penetration if the minimal distance between the sphere origin and the triangle is greater than the sphere's radius.
    // Also, if the point is on a reduced feature, the contact can be ignored.  The exception is for an edge, specifically for
    // a sphere ( limit of one contact point ) it is necessary to make sure that a contact on the edge is not ignored at least
    // once to prevent the system from culling out all contact points between a sphere and a triangle list.

    if (tyDistSq > tgSP0.Query_RadiusSq() || bCulled && bEdge)
    {
        return (TgE_NOINTERSECT);
    };

    TgFEBUG_COLLISION_TRIANGLE( iDBG_TriID, etgDEBUG_COLLISION_PASSED_REJECT );

    T_(VECTOR,DIM)                      tvCT0;
    
    tgCT0.Calc_Point( tvCT0, tyCT0,tyCT1 );

    const TYPE                          tyDist = P::SQRT( tyDistSq );
    const TYPE                          tyDepth = tyDist >= tgSP0.Query_Radius() ? TYPE(0.0) : tgSP0.Query_Radius() - tyDist;
    T_(VECTOR,DIM)                      tvNormal = MATH::F_SUB( tgSP0.Query_Origin(), tvCT0 );

    //  Check to see if the normal of intersection should be replaced by the triangle's normal.  This is done to reduce floating
    // point noise in the system where near-normal results are returned.  By forcing it to the triangle's normal, extraneous
    // rotations are minimized. The other possibility is that the sphere's origin lies on the triangle itself, thus, requiring
    // the selection of the triangle's normal for the intersection.

    TgBOOL                              bUseNormal = !Near_Zero( tyDist );

    if (bUseNormal)
    {
        MATH::F_NORM( tvNormal );

        //  Check to see if the resultant normal is near that of the triangle's.  If they are close then use the triangle's
        // normal to help further reduce floating point noise.

        bUseNormal = Near_One( MATH::F_DOT(tvNormal, tgCT0.Query_Normal()) );
    };

    if (bCulled && bUseNormal)
    {
        // If the point was marked to be culled (even if its on a valid edge), and the contact normal does not match the
        // triangle's normal, ignore this contact.  Its assumed that the matching triangle, attached to this one, will
        // create the required contact point.  Prevents duplicate points from being created.

        return (TgE_NOINTERSECT);
    };

    // Create contact point.

    P_(CONTACT,DIM)                     ptgContact;

    ptgContact = (P_(CONTACT,DIM))((PC_TgUINT08)ptgPacket->m_ptgContact + ptgPacket->m_niContact*ptgPacket->m_iStride);

    ptgContact->m_tvNormal = bUseNormal ? tvNormal : tgCT0.Query_Normal();
    ptgContact->m_tyT0 = TYPE(0.0);
    ptgContact->m_tyDepth = tyDepth;
    ptgContact->m_tvPos = MATH::F_SUB( tgSP0.Query_Origin(), MATH::F_MUL( tgSP0.Query_Radius(), ptgContact->m_tvNormal ) );

    ++ptgPacket->m_niContact;

    TgFEBUG_COLLISION_TRIANGLE( iDBG_TriID, etgDEBUG_COLLISION_CODE1 );

    return (TgS_OK);
};

template TgRESULT F_Internal_Penetrate( PC_TgF4CONTACT_PACKET, CR_TgF4CTRI, CR_TgF4SPHERE );


// ============================================================================================================================== //

// ---- F_Contact_Sweep --------------------------------------------------------------------------------------------------------- //
// Input:  tgPacket: The current series of contact points for this query-series, and contact generation parameters.
// Input:  tyPM: Current normalized time of first contact.
// Input:  bPenetrate: If the swept primitives are in penetration, if true the function will return points of penetration.
// Input:  tgST0: Space Triangle primitive
// Input:  tgSP0: Sphere primitive
// Input:  tgDT: A structure holding the swept primitive displacement for the entire duration of the test period
// Output: tgPacket: Contact points are added or replace the current set depending on the time comparison and given parameters
// Output: tyPM: New normalized time of first contact
// Return: Result Code
// ------------------------------------------------------------------------------------------------------------------------------ //

template <typename TYPE, int DIM>
TgRESULT F_Contact_Sweep( PC_(CONTACT_PACKET,DIM) ptgPacket, TYPE *ptyPM, CR_(STRI,DIM) tgST0, CR_(SPHERE,DIM) tgSP0, CR_(DELTA,DIM) tgDT )
{
    TgBLOCK_FCN_NOOBJ(ETgFAC_COLLISION, 0, ETgTEST_SWEEP, (((TgUINT)ETgTRIANGLE<<16)|(TgUINT)ETgSPHERE))

    TgASSERT((TgSIZE)ptgPacket->m_iStride >= sizeof( P_(CONTACT,DIM) ))
    TgASSERT(tgSP0.Is_Valid() && tgST0.Is_Valid())

    if (0 == ptgPacket->m_niMaxContact || ptgPacket->m_niContact >= ptgPacket->m_niMaxContact || NULL == ptgPacket->m_ptgContact)
    {
        return (TgE_FAIL);
    };

    TgFEBUG_COLLISION_TRIANGLE_CREATEID( iDBG_TriID, tgST0, etgDEBUG_COLLISION_ENTERFCN );

    // Check the displacement vector - if it is directed away from the triangle intersection is not possible.

    C_(VECTOR,DIM)                      tvX0 = MATH::F_SUB( tgSP0.Query_Origin(), tgST0.Query_Origin() );
    const TYPE                          tyX0_N = MATH::F_DOT( tvX0, tgST0.Query_Normal() );
    const TYPE                          tyDT_N = MATH::F_DOT( tgDT.m_tvDT, tgST0.Query_Normal() );

    if (tyX0_N > tgSP0.Query_Radius() && tyDT_N > LIMITS<TYPE>::EPSILON)
    {
        return (TgE_NOINTERSECT);
    };

    if (tyX0_N < -tgSP0.Query_Radius() && tyDT_N < -LIMITS<TYPE>::EPSILON)
    {
        return (TgE_NOINTERSECT);
    };

    // Calculate the extrapolation required to translate the distance from the origin to the triangle plane.

    C_TgBOOL                            bPenetrate = TgTRUE == ptgPacket->m_bReport_Penetration;
    const TYPE                          tyT = (tgSP0.Query_Radius() - tyX0_N) / tyDT_N;

    if (tyT > *ptyPM + ptgPacket->m_tySweepTol || tyT > TYPE(1.0))
    {
        if (bPenetrate)
        {
            goto SPHERE_PENETRATION;
        };

        return (TgE_NOINTERSECT);
    };

    // Examine the resulting point on the plane to see if it is contained by the triangle.

    if (tyT >= TYPE(0.0))
    {
        T_(VECTOR,DIM)                      tvIPT = MATH::F_ADD( tgSP0.Query_Origin(), MATH::F_MUL( tyT, tgDT.m_tvDT ) );

        for (int iEdge = 0; iEdge < 3; ++iEdge)
        {
            const TYPE                          tyLimit = LIMITS<TYPE>::EPSILON*MATH::F_LEN( tgST0.Query_Edge( iEdge ) );
            const TYPE                          tyDist = F_Dist( tgST0.Query_EdgePlane( iEdge ), tvIPT );

            if (tyDist < -tyLimit)
            {
                // The sphere origin is behind the triangle plane.  Check to see if the delta moves away from the plane.

                if (!tgST0.Test_Edge( iEdge ) && MATH::F_DOT( tgST0.Query_EdgePlane( iEdge ).Query_Normal(), tgDT.m_tvDT ) < TYPE(0.0))
                {
                    return (TgE_NOINTERSECT);
                };

                // The sphere does not intersect the triangle plane - check the edge/vertices for intersection.

                goto OutsideTriangle;
            }
            else if (tyDist <= tyLimit)
            {
                // The contact point is within tolerance of a specific triangle's edge.  Check to see if its been marked invalid.

                if (!tgST0.Test_Edge( iEdge ) && Is_Tri_Edge_Ignored( tgST0.Query_ET(), iEdge ))
                {
                    return (TgE_NOINTERSECT);
                };
            };
        };

        // Valid point of contact.

        if (tyT < *ptyPM - ptgPacket->m_tySweepTol)
        {
            ptgPacket->m_niContact = 0;
            *ptyPM = tyT;
        };

        P_(CONTACT,DIM)                     ptgContact;

        ptgContact = (P_(CONTACT,DIM))((PC_TgUINT08)ptgPacket->m_ptgContact + ptgPacket->m_niContact*ptgPacket->m_iStride);

        ptgContact->m_tvPos = MATH::F_SUB( tvIPT, MATH::F_MUL( tgSP0.Query_Radius(), tgST0.Query_Normal() ) );
        ptgContact->m_tvNormal = tgST0.Query_Normal();
        ptgContact->m_tyT0 = tyT;
        ptgContact->m_tyDepth = TYPE(0.0);

        ++ptgPacket->m_niContact;

        TgFEBUG_COLLISION_TRIANGLE( iDBG_TriID, etgDEBUG_COLLISION_CODE1 );

        return (TgS_OK);
    };

OutsideTriangle:

    {   // State Block for Edge Tests - Required because of the goto statement used for the penetration check

        C_(VECTOR,DIM)                      tvK0 = MATH::F_SUB( tgDT.m_tvDT, tgST0.Query_Origin() );
        C_(VECTOR,DIM)                      tvX1 = MATH::F_ADD( tgSP0.Query_Origin(), tvK0 );
        TgBOOL                              bHit = TgFALSE;

        // Check for collisions against the three edges

        for (int iEdge = 0; iEdge < 3; ++iEdge)
        {
            if (tgST0.Test_Edge( iEdge ) || !Is_Tri_Edge_Ignored( tgST0.Query_ET(), iEdge ))
            {
                const TYPE                          tyLimit = -tgSP0.Query_Radius()*MATH::F_LEN( tgST0.Query_Edge( iEdge ) );

                const TYPE                          tyT0 = MATH::F_DOT(tgST0.Query_EdgePlane( iEdge ).Query_Normal(),tvX0);
                const TYPE                          tyT1 = MATH::F_DOT(tgST0.Query_EdgePlane( iEdge ).Query_Normal(),tvX1);

                if (tyT0 < tyLimit && tyT1 < tyLimit)
                {
                    return (TgE_NOINTERSECT);
                };

                if (tyT0 < LIMITS<TYPE>::EPSILON || tyT1 < LIMITS<TYPE>::EPSILON)
                {
                    bHit |= 0 <= TTgSWP_SPLN<TYPE,DIM,1,1>::DO(
                        ptgPacket, ptyPM, tgST0.Query_Point( iEdge ), tgST0.Query_Edge( iEdge ), tgSP0, tgDT
                    );
                };
            };
        };

        // Check for collisions against the three vertices

        for (int iPoint = 0; iPoint < 3; ++iPoint)
        {
            if (tgST0.Test_Point( iPoint ))
            {
                bHit |= TgSUCCEEDED(F_Contact_Sweep( ptgPacket, ptyPM, tgST0.Query_Point( iPoint ), tgSP0,tgDT ));
            };
        };

        TgFEBUG_COLLISION_TRIANGLE( iDBG_TriID, etgDEBUG_COLLISION_CODE2 );

        if (bHit)
        {
            return (TgS_OK);
        };
    };

    // If pre-penetration information is not requested or the sphere's origin is behind the triangle report a non-intersection.

    if (!bPenetrate)
    {
        return (TgE_NOINTERSECT);
    };

SPHERE_PENETRATION:

    TgFEBUG_COLLISION_TRIANGLE( iDBG_TriID, etgDEBUG_COLLISION_PREPENETRATION );

    // Record the current number of contacts before potentially clearing the list in case pre-penetration is not found.

    C_TgINT                             niContact = ptgPacket->m_niContact;

    if (*ptyPM > ptgPacket->m_tySweepTol)
    {
        ptgPacket->m_niContact = 0;
    };

    C_TgRESULT tgResult = F_Internal_Penetrate( ptgPacket, tgST0.Query_CT(),tgSP0 );

    // Restore the original number of contacts if pre-penetration was not found.

    if (TgFAILED(tgResult))
    {
        ptgPacket->m_niContact = niContact;
        return (tgResult);
    };

    // Set the time parameter and return back the appropriate result code.

    *ptyPM = TYPE(0.0);

    return (TgS_MAXCONTACTS == tgResult ? TgE_PREPENETRATION_MAXCONTACTS : (TgS_OK == tgResult ? TgE_PREPENETRATION : tgResult));
};

template TgRESULT F_Contact_Sweep( PC_TgF4CONTACT_PACKET, P_TgFLOAT32, CR_TgF4STRI, CR_TgF4SPHERE, CR_TgF4DELTA );


// ============================================================================================================================== //

}; // END COL //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
}; // END TGS //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
[an error occurred while processing this directive]