wmlconvexpolygon2.cpp

3D Game Engine Design Source Code非常棒

    {
        afDistance[i] = rkLine.GetPseudodistance(m_akPoint[i]);
        if ( afDistance[i] >= fEpsilon )
        {
            iPositive++;
            if ( iPIndex < 0 )
                iPIndex = i;
        }
        else if ( afDistance[i] <= -fEpsilon )
        {
            iNegative++;
        }
        else
        {
            // The point is on the line (within floating point tolerance).
            afDistance[i] = (Real)0.0;
        }
    }

    if ( iPositive == 0 )
    {
        // polygon is in negative half-space, fully clipped
        delete[] afDistance;
        return false;
    }

    if ( iNegative == 0 )
    {
        // polygon is in positive half-space, fully visible
        rkIntr = *this;
        delete[] afDistance;
        return true;
    }

    // line transversely intersects polygon
    VArray kCV;
    int iCur, iPrv;
    Real fT;

    if ( iPIndex > 0 )
    {
        // first clip vertex on line
        iCur = iPIndex;
        iPrv = iCur-1;
        fT = afDistance[iCur]/(afDistance[iCur]-afDistance[iPrv]);
        kCV.push_back(m_akPoint[iCur]+fT*(m_akPoint[iPrv]-m_akPoint[iCur]));

        // vertices on positive side of line
        while ( iCur < iQuantity && afDistance[iCur] > (Real)0.0 )
            kCV.push_back(m_akPoint[iCur++]);

        // last clip vertex on line
        if ( iCur < iQuantity )
        {
            iPrv = iCur-1;
        }
        else
        {
            iCur = 0;
            iPrv = iQuantity - 1;
        }
        fT = afDistance[iCur]/(afDistance[iCur]-afDistance[iPrv]);
        kCV.push_back(m_akPoint[iCur]+fT*(m_akPoint[iPrv]-m_akPoint[iCur]));
    }
    else  // iPIndex is 0
    {
        // vertices on positive side of line
        iCur = 0;
        while ( iCur < iQuantity && afDistance[iCur] > (Real)0.0 )
            kCV.push_back(m_akPoint[iCur++]);

        // last clip vertex on line
        iPrv = iCur-1;
        fT = afDistance[iCur]/(afDistance[iCur]-afDistance[iPrv]);
        kCV.push_back(m_akPoint[iCur]+fT*(m_akPoint[iPrv]-m_akPoint[iCur]));

        // skip vertices on negative side
        while ( iCur < iQuantity && afDistance[iCur] <= (Real)0.0 )
            iCur++;

        // first clip vertex on line
        if ( iCur < iQuantity )
        {
            iPrv = iCur-1;
            fT = afDistance[iCur]/(afDistance[iCur]-afDistance[iPrv]);
            kCV.push_back(m_akPoint[iCur]+fT*(m_akPoint[iPrv] -
                m_akPoint[iCur]));

            // vertices on positive side of line
            while ( iCur < iQuantity && afDistance[iCur] > (Real)0.0 )
                kCV.push_back(m_akPoint[iCur++]);
        }
        else
        {
            // iCur = 0
            iPrv = iQuantity - 1;
            fT = afDistance[0]/(afDistance[0]-afDistance[iPrv]);
            kCV.push_back(m_akPoint[0]+fT*(m_akPoint[iPrv]-m_akPoint[0]));
        }
    }

    delete[] afDistance;
    rkIntr.Create(kCV);
    return true;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolygon2<Real>::FindIntersection (const ConvexPolygon2& rkPoly,
    ConvexPolygon2& rkIntr) const
{
    rkIntr = *this;

    const LArray& rakLine = rkPoly.GetLines();
    for (int i = 0; i < (int)rakLine.size(); i++)
    {
        if ( !rkIntr.Clip(rakLine[i],rkIntr) )
            return false;
    }

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolygon2<Real>* ConvexPolygon2<Real>::FindSolidIntersection (
    const ConvexPolygon2& rkPoly0, const ConvexPolygon2& rkPoly1)
{
    ConvexPolygon2* pkIntr = new ConvexPolygon2;
    if ( rkPoly0.FindIntersection(rkPoly1,*pkIntr) )
        return pkIntr;
    
    // As curves, the polygons do not intersect.  However, as solids, one
    // polygon might be fully contained in the other.
    if ( rkPoly0.ContainsPoint(rkPoly1.GetCentroid()) )
    {
        *pkIntr = rkPoly1;
        return pkIntr;
    }
        
    if ( rkPoly1.ContainsPoint(rkPoly0.GetCentroid()) )
    {
        *pkIntr = rkPoly0;
        return pkIntr;
    }

    delete pkIntr;
    return NULL;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolygon2<Real>::FindAllIntersections (int iQuantity,
    ConvexPolygon2* akPoly, int& riCombos, ConvexPolygon2**& rapkIntr)
{
    // Only 2^16 possible combinations for intersections are currently
    // supported.  If you need more, then GetHighBit(int) must be modified
    // to handle more than 16-bit inputs.
    if ( iQuantity <= 0 || iQuantity > 16 )
    {
        riCombos = 0;
        rapkIntr = NULL;
        return;
    }

    riCombos = (1 << iQuantity);
    bool* abNeedsTesting = new bool[riCombos];
    rapkIntr = new ConvexPolygon2*[riCombos];
    int i;
    for (i = 0; i < riCombos; i++)
    {
        abNeedsTesting[i] = true;
        rapkIntr[i] = NULL;
    }

    // trivial cases, zero or one polyhedron--already the intersection
    abNeedsTesting[0] = false;
    for (i = 0; i < iQuantity; i++)
    {
        int j = (1 << i);
        abNeedsTesting[j] = false;
        rapkIntr[j] = new ConvexPolygon2(akPoly[i]);
    }
    
    for (i = 3; i < riCombos; i++)
    {
        if ( abNeedsTesting[i] )
        {
            // In binary, i = b[m]...b[0] where b[m] is not zero (the
            // high-order bit.  Also, i1 = b[m-1]...b[0] is not zero
            // since, if it were, we would have ruled out the combination
            // by the j-loop below.  Therefore, i0 = b[m]0...0 and
            // i1 correspond to already existing polyhedra.  The
            // intersection finding just needs to look at the intersection
            // of the two polyhedra.
            int i0 = GetHighBit(i);
            int i1 = i & ~i0;
            rapkIntr[i] = FindSolidIntersection(*rapkIntr[i0],*rapkIntr[i1]);
            if ( !rapkIntr[i] )
            {
                // No intersection for this combination.  No need to test
                // other combinations that include this one.
                for (int j = 0; j < riCombos; j++)
                {
                    if ( (i & j) == i )
                        abNeedsTesting[j] = false;
                }
            }
#ifdef _DEBUG
            else  // test if well-formed convex polyhedron
            {
                Vector2<Real> kCentroid = rapkIntr[i]->GetCentroid();
                bool bContains = rapkIntr[i]->ContainsPoint(kCentroid);
                assert( bContains );
            }
#endif
        }
    }

    delete[] abNeedsTesting;
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexPolygon2<Real>::GetHighBit (int i)
{
    // assert: i in [1,2^16].  That is, (i>0) && (0xFFFF0000&i)==0.
    // This is a binary search for the high-order bit of i.
    if ( (i & 0xFF00) != 0 )
    {
        if ( (i & 0xF000) != 0 )
        {
            if ( (i & 0xC000) != 0 )
            {
                if ( (i & 0x8000) != 0 )
                    return 0x8000;
                else // (i & 0x4000) != 0
                    return 0x4000;
            }
            else  // (i & 0x3000) != 0
            {
                if ( (i & 0x2000) != 0 )
                    return 0x2000;
                else  // (i & 0x1000) != 0
                    return 0x1000;
            }
        }
        else  // (i & 0x0F00) != 0
        {
            if ( (i & 0x0C00) != 0 )
            {
                if ( (i & 0x0800) != 0 )
                    return 0x0800;
                else  // (i & 0x0400) != 0
                    return 0x0400;
            }
            else  // (i & 0x0300) != 0
            {
                if ( (i & 0x0200) != 0 )
                    return 0x0200;
                else  // (i & 0x0100) != 0
                    return 0x0100;
            }
        }
    }
    else  // (i & 0x00FF)
    {
        if ( (i & 0x00F0) != 0 )
        {
            if ( (i & 0x00C0) != 0 )
            {
                if ( (i & 0x0080) != 0 )
                    return 0x0080;
                else  // (i & 0x0040) != 0
                    return 0x0040;
            }
            else  // (i & 0x0030) != 0
            {
                if ( (i & 0x0020) != 0 )
                    return 0x0020;
                else  // (i & 0x0010) != 0
                    return 0x0010;
            }
        }
        else  // (i & 0x000F) != 0
        {
            if ( (i & 0x000C) != 0 )
            {
                if ( (i & 0x0008) != 0 )
                    return 0x0008;
                else  // (i & 0x0004) != 0
                    return 0x0004;
            }
            else  // (i & 0x0003) != 0
            {
                if ( (i & 0x0002) != 0 )
                    return 0x0002;
                else  // (i & 0x0001) != 0
                    return 0x0001;
            }
        }
    }
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// explicit instantiation
//----------------------------------------------------------------------------
namespace Wml
{
template class WML_ITEM ConvexPolygon2<float>;
template class WML_ITEM ConvexPolygon2<double>;
}
//----------------------------------------------------------------------------