wmlcontminsphere3.cpp

3D Game Engine Design Source Code非常棒

        rkSupp.Index[2] = i;
    }

    return kMinimal;
}
//----------------------------------------------------------------------------
template <class Real>
Sphere3<Real> MinSphere3<Real>::UpdateSupport3 (int i,
    Vector3<Real>** apkPerm, Support& rkSupp)
{
    const Vector3<Real>& rkP0 = *apkPerm[rkSupp.Index[0]];
    const Vector3<Real>& rkP1 = *apkPerm[rkSupp.Index[1]];
    const Vector3<Real>& rkP2 = *apkPerm[rkSupp.Index[2]];
    const Vector3<Real>& rkP3 = *apkPerm[i];

    Sphere3<Real> akS[6];
    Real fMinRSqr = Math<Real>::MAX_REAL;
    Real fDistDiff;
    int iIndex = -1;

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

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

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

    akS[3] = ExactSphere3(rkP0,rkP1,rkP3);
    if ( akS[3].Radius() < fMinRSqr && Contains(rkP2,akS[3],fDistDiff) )
    {
        fMinRSqr = akS[3].Radius();
        iIndex = 3;
    }

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

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

    Sphere3<Real> kMinimal;

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

    return kMinimal;
}
//----------------------------------------------------------------------------
template <class Real>
Sphere3<Real> MinSphere3<Real>::UpdateSupport4 (int i,
    Vector3<Real>** apkPerm, Support& rkSupp)
{
    const Vector3<Real>* apkPt[4] =
    {
        apkPerm[rkSupp.Index[0]],
        apkPerm[rkSupp.Index[1]],
        apkPerm[rkSupp.Index[2]],
        apkPerm[rkSupp.Index[3]]
    };

    const Vector3<Real>& rkP4 = *apkPerm[i];

    // permutations of type 1
    int aiT1[4][4] =
    {
        {0, /*4*/ 1,2,3},
        {1, /*4*/ 0,2,3},
        {2, /*4*/ 0,1,3},
        {3, /*4*/ 0,1,2}
    };

    // permutations of type 2
    int aiT2[6][4] =
    {
        {0,1, /*4*/ 2,3},
        {0,2, /*4*/ 1,3},
        {0,3, /*4*/ 1,2},
        {1,2, /*4*/ 0,3},
        {1,3, /*4*/ 0,2},
        {2,3, /*4*/ 0,1}
    };

    // permutations of type 3
    int aiT3[4][4] =
    {
        {0,1,2, /*4*/ 3},
        {0,1,3, /*4*/ 2},
        {0,2,3, /*4*/ 1},
        {1,2,3, /*4*/ 0}
    };

    Sphere3<Real> akS[14];
    Real fMinRSqr = Math<Real>::MAX_REAL;
    int iIndex = -1;
    Real fDistDiff, fMinDistDiff = Math<Real>::MAX_REAL;
    int iMinIndex = -1;
    int k = 0;  // sphere index

    // permutations of type 1
    int j;
    for (j = 0; j < 4; j++, k++)
    {
        akS[k] = ExactSphere2(*apkPt[aiT1[j][0]],rkP4);
        if ( akS[k].Radius() < fMinRSqr )
        {
            if ( Contains(*apkPt[aiT1[j][1]],akS[k],fDistDiff)
            &&   Contains(*apkPt[aiT1[j][2]],akS[k],fDistDiff)
            &&   Contains(*apkPt[aiT1[j][3]],akS[k],fDistDiff) )
            {
                fMinRSqr = akS[k].Radius();
                iIndex = k;
            }
            else if ( fDistDiff < fMinDistDiff )
            {
                fMinDistDiff = fDistDiff;
                iMinIndex = k;
            }
        }
    }

    // permutations of type 2
    for (j = 0; j < 6; j++, k++)
    {
        akS[k] = ExactSphere3(*apkPt[aiT2[j][0]],*apkPt[aiT2[j][1]],rkP4);
        if ( akS[k].Radius() < fMinRSqr )
        {
            if ( Contains(*apkPt[aiT2[j][2]],akS[k],fDistDiff)
            &&   Contains(*apkPt[aiT2[j][3]],akS[k],fDistDiff) )
            {
                fMinRSqr = akS[k].Radius();
                iIndex = k;
            }
            else if ( fDistDiff < fMinDistDiff )
            {
                fMinDistDiff = fDistDiff;
                iMinIndex = k;
            }
        }
    }

    // permutations of type 3
    for (j = 0; j < 4; j++, k++)
    {
        akS[k] = ExactSphere4(*apkPt[aiT3[j][0]],*apkPt[aiT3[j][1]],
            *apkPt[aiT3[j][2]],rkP4);
        if ( akS[k].Radius() < fMinRSqr )
        {
            if ( Contains(*apkPt[aiT3[j][3]],akS[k],fDistDiff) )
            {
                fMinRSqr = akS[k].Radius();
                iIndex = k;
            }
            else if ( fDistDiff < fMinDistDiff )
            {
                fMinDistDiff = fDistDiff;
                iMinIndex = k;
            }
        }
    }

    // Theoretically, iIndex >= 0 should happen, but floating point round-off
    // error can lead to this.  When this happens, the sphere is chosen that
    // has the minimum absolute errors between points (barely) outside the
    // sphere and the sphere.
    if ( iIndex == -1 )
        iIndex = iMinIndex;

    Sphere3<Real> kMinimal = akS[iIndex];

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

    return kMinimal;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// explicit instantiation
//----------------------------------------------------------------------------
namespace Wml
{
template class WML_ITEM MinSphere3<float>;
const float MinSphere3f::EPSILON = 1e-03f;
const float MinSphere3f::ONE_PLUS_EPSILON = 1.0f + 1e-03f;
MinSphere3f::UpdateFunction MinSphere3f::ms_aoUpdate[5] =
{
    NULL,
    MinSphere3f::UpdateSupport1,
    MinSphere3f::UpdateSupport2,
    MinSphere3f::UpdateSupport3,
    MinSphere3f::UpdateSupport4
};

template class WML_ITEM MinSphere3<double>;
const double MinSphere3d::EPSILON = 1e-03;
const double MinSphere3d::ONE_PLUS_EPSILON = 1.0 + 1e-03;
MinSphere3d::UpdateFunction MinSphere3d::ms_aoUpdate[5] =
{
    NULL,
    MinSphere3d::UpdateSupport1,
    MinSphere3d::UpdateSupport2,
    MinSphere3d::UpdateSupport3,
    MinSphere3d::UpdateSupport4
};
}
//----------------------------------------------------------------------------