mgcminsphere.cpp

3D Game Engine Design Source Code非常棒

        kMinimal = akS[1];
        rkSupp.m_iQuantity = 2;
        rkSupp.m_aiIndex[0] = i;
        break;
    case 2:
        kMinimal = akS[2];
        rkSupp.m_iQuantity = 2;
        rkSupp.m_aiIndex[0] = rkSupp.m_aiIndex[2];
        rkSupp.m_aiIndex[1] = i;
        break;
    case 3:
        kMinimal = akS[3];
        rkSupp.m_aiIndex[2] = i;
        break;
    case 4:
        kMinimal = akS[4];
        rkSupp.m_aiIndex[1] = i;
        break;
    case 5:
        kMinimal = akS[5];
        rkSupp.m_aiIndex[0] = i;
        break;
    default:
        kMinimal = ExactSphere4(rkP0,rkP1,rkP2,rkP3);
        assert( kMinimal.Radius() <= fMinRSqr );
        rkSupp.m_iQuantity = 4;
        rkSupp.m_aiIndex[3] = i;
        break;
    }

    return kMinimal;
}
//----------------------------------------------------------------------------
static MgcSphere UpdateSupport4 (int i, MgcVector3** apkPerm, Support& rkSupp)
{
    const MgcVector3& rkP0 = *apkPerm[rkSupp.m_aiIndex[0]];
    const MgcVector3& rkP1 = *apkPerm[rkSupp.m_aiIndex[1]];
    const MgcVector3& rkP2 = *apkPerm[rkSupp.m_aiIndex[2]];
    const MgcVector3& rkP3 = *apkPerm[rkSupp.m_aiIndex[3]];
    const MgcVector3& rkP4 = *apkPerm[i];

    MgcSphere akS[14];
    MgcReal fMinRSqr = MgcMath::INFINITY;
    int iIndex = -1;

    akS[0] = ExactSphere2(rkP0,rkP4);
    if ( PointInsideSphere(rkP1,akS[0])
    &&   PointInsideSphere(rkP2,akS[0])
    &&   PointInsideSphere(rkP3,akS[0]) )
    {
        fMinRSqr = akS[0].Radius();
        iIndex = 0;
    }

    akS[1] = ExactSphere2(rkP1,rkP4);
    if ( PointInsideSphere(rkP0,akS[1])
    &&   PointInsideSphere(rkP2,akS[1])
    &&   PointInsideSphere(rkP3,akS[1]) )
    {
        if ( akS[1].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[1].Radius();
            iIndex = 1;
        }
    }

    akS[2] = ExactSphere2(rkP2,rkP4);
    if ( PointInsideSphere(rkP0,akS[2])
    &&   PointInsideSphere(rkP1,akS[2])
    &&   PointInsideSphere(rkP3,akS[2]) )
    {
        if ( akS[2].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[2].Radius();
            iIndex = 2;
        }
    }

    akS[3] = ExactSphere2(rkP3,rkP4);
    if ( PointInsideSphere(rkP0,akS[3])
    &&   PointInsideSphere(rkP1,akS[3])
    &&   PointInsideSphere(rkP2,akS[3]) )
    {
        if ( akS[3].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[3].Radius();
            iIndex = 3;
        }
    }

    akS[4] = ExactSphere3(rkP0,rkP1,rkP4);
    if ( PointInsideSphere(rkP2,akS[4])
    &&   PointInsideSphere(rkP3,akS[4]) )
    {
        if ( akS[4].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[4].Radius();
            iIndex = 4;
        }
    }

    akS[5] = ExactSphere3(rkP0,rkP2,rkP4);
    if ( PointInsideSphere(rkP1,akS[5])
    &&   PointInsideSphere(rkP3,akS[5]) )
    {
        if ( akS[5].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[5].Radius();
            iIndex = 5;
        }
    }

    akS[6] = ExactSphere3(rkP0,rkP3,rkP4);
    if ( PointInsideSphere(rkP1,akS[6])
    &&   PointInsideSphere(rkP2,akS[6]) )
    {
        if ( akS[6].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[6].Radius();
            iIndex = 6;
        }
    }

    akS[7] = ExactSphere3(rkP1,rkP2,rkP4);
    if ( PointInsideSphere(rkP0,akS[7])
    &&   PointInsideSphere(rkP3,akS[7]) )
    {
        if ( akS[7].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[7].Radius();
            iIndex = 7;
        }
    }

    akS[8] = ExactSphere3(rkP1,rkP3,rkP4);
    if ( PointInsideSphere(rkP0,akS[8])
    &&   PointInsideSphere(rkP2,akS[8]) )
    {
        if ( akS[8].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[8].Radius();
            iIndex = 8;
        }
    }

    akS[9] = ExactSphere3(rkP2,rkP3,rkP4);
    if ( PointInsideSphere(rkP0,akS[9])
    &&   PointInsideSphere(rkP1,akS[9]) )
    {
        if ( akS[9].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[9].Radius();
            iIndex = 9;
        }
    }

    akS[10] = ExactSphere4(rkP0,rkP1,rkP2,rkP4);
    if ( PointInsideSphere(rkP3,akS[10]) )
    {
        if ( akS[10].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[10].Radius();
            iIndex = 10;
        }
    }

    akS[11] = ExactSphere4(rkP0,rkP1,rkP3,rkP4);
    if ( PointInsideSphere(rkP2,akS[11]) )
    {
        if ( akS[11].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[11].Radius();
            iIndex = 11;
        }
    }

    akS[12] = ExactSphere4(rkP0,rkP2,rkP3,rkP4);
    if ( PointInsideSphere(rkP1,akS[12]) )
    {
        if ( akS[12].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[12].Radius();
            iIndex = 12;
        }
    }

    akS[13] = ExactSphere4(rkP1,rkP2,rkP3,rkP4);
    if ( PointInsideSphere(rkP0,akS[13]) )
    {
        if ( akS[13].Radius() < fMinRSqr )
        {
            fMinRSqr = akS[13].Radius();
            iIndex = 13;
        }
    }

    assert( iIndex != -1 );

    MgcSphere kMinimal = akS[iIndex];

    switch ( iIndex )
    {
    case 0:
        rkSupp.m_iQuantity = 2;
        rkSupp.m_aiIndex[1] = i;
        break;
    case 1:
        rkSupp.m_iQuantity = 2;
        rkSupp.m_aiIndex[0] = i;
        break;
    case 2:
        rkSupp.m_iQuantity = 2;
        rkSupp.m_aiIndex[0] = rkSupp.m_aiIndex[2];
        rkSupp.m_aiIndex[1] = i;
        break;
    case 3:
        rkSupp.m_iQuantity = 2;
        rkSupp.m_aiIndex[0] = rkSupp.m_aiIndex[3];
        rkSupp.m_aiIndex[1] = i;
        break;
    case 4:
        rkSupp.m_iQuantity = 3;
        rkSupp.m_aiIndex[2] = i;
        break;
    case 5:
        rkSupp.m_iQuantity = 3;
        rkSupp.m_aiIndex[1] = i;
        break;
    case 6:
        rkSupp.m_iQuantity = 3;
        rkSupp.m_aiIndex[1] = rkSupp.m_aiIndex[3];
        rkSupp.m_aiIndex[2] = i;
        break;
    case 7:
        rkSupp.m_iQuantity = 3;
        rkSupp.m_aiIndex[0] = i;
        break;
    case 8:
        rkSupp.m_iQuantity = 3;
        rkSupp.m_aiIndex[0] = rkSupp.m_aiIndex[3];
        rkSupp.m_aiIndex[2] = i;
        break;
    case 9:
        rkSupp.m_iQuantity = 3;
        rkSupp.m_aiIndex[0] = rkSupp.m_aiIndex[3];
        rkSupp.m_aiIndex[1] = i;
        break;
    case 10:
        rkSupp.m_aiIndex[3] = i;
        break;
    case 11:
        rkSupp.m_aiIndex[2] = i;
        break;
    case 12:
        rkSupp.m_aiIndex[1] = i;
        break;
    case 13:
        rkSupp.m_aiIndex[0] = i;
        break;
    }

    return kMinimal;
}
//----------------------------------------------------------------------------
typedef MgcSphere (*UpdateFunction)(int,MgcVector3**,Support&);
static UpdateFunction Update[5] =
{
    0,
    UpdateSupport1,
    UpdateSupport2,
    UpdateSupport3,
    UpdateSupport4
};
//----------------------------------------------------------------------------
MgcSphere MgcMinSphere (int iQuantity, const MgcVector3* akPoint)
{
    // initialize random number generator
    static bool s_bFirstTime = true;
    if ( s_bFirstTime )
    {
        srand(367);
        s_bFirstTime = false;
    }

    MgcSphere kMinimal;
    Support kSupp;

    if ( iQuantity >= 1 )
    {
        // create identity permutation (0,1,...,iQuantity-1)
        MgcVector3** apkPerm = new MgcVector3*[iQuantity];
        int i;
        for (i = 0; i < iQuantity; i++)
            apkPerm[i] = (MgcVector3*)&akPoint[i];

        // generate random permutation
        for (i = iQuantity-1; i > 0; i--)
        {
            int j = rand() % (i+1);
            if ( j != i )
            {
                MgcVector3* pSave = apkPerm[i];
                apkPerm[i] = apkPerm[j];
                apkPerm[j] = pSave;
            }
        }

        kMinimal = ExactSphere1(*apkPerm[0]);
        kSupp.m_iQuantity = 1;
        kSupp.m_aiIndex[0] = 0;
        i = 1;
        while ( i < iQuantity )
        {
            if ( !kSupp.Contains(i) )
            {
                if ( !PointInsideSphere(*apkPerm[i],kMinimal) )
                {
                    kMinimal = Update[kSupp.m_iQuantity](i,apkPerm,kSupp);
                    i = 0;
                    continue;
                }
            }
            i++;
        }

        delete[] apkPerm;
    }
    else
    {
        assert( false );
    }

    kMinimal.Radius() = MgcMath::Sqrt(kMinimal.Radius());
    return kMinimal;
}
//----------------------------------------------------------------------------