wmlconvexclipper.cpp

3D Game Engine Design Source Code非常棒

        int iV1 = rkE.m_aiVertex[1];
        m_akVertex[iV1].m_iOccurs++;
        if ( m_akVertex[iV1].m_iOccurs > 2 )
            bOkay = false;
    }

    if ( !bOkay )
    {
#ifdef _DEBUG
        // If you reach this block, there is a good chance that floating
        // point round-off error had caused this face to be needle-like and
        // what was theoretically a narrow V-shaped portion (a vertex shared
        // by two edges forming a small angle) has collapsed into a single
        // line segment.
        //
        // NOTE.  Once I added PostProcess, I have not gotten to this block.
        ofstream kOStr("error.txt");
        pkIter = rkF.m_akEdge.begin();
        while ( pkIter != rkF.m_akEdge.end() )
        {
            int iE = *pkIter++;
            Edge& rkE = m_akEdge[iE];
            kOStr << "e<" << iE << "> = <" << rkE.m_aiVertex[0] << ","
                  << rkE.m_aiVertex[1] << "|" << rkE.m_aiFace[0] << ","
                  << rkE.m_aiFace[1] << "> ";
            if ( rkE.m_bVisible )
                kOStr << "T" << endl;
            else
                kOStr << "F" << endl;
        }
        kOStr.close();

        assert( false );
#else
        return false;
#endif
    }

    // determine if the polyline is open
    pkIter = rkF.m_akEdge.begin();
    riVStart = -1;
    riVFinal = -1;
    while ( pkIter != rkF.m_akEdge.end() )
    {
        int iE = *pkIter++;
        Edge& rkE = m_akEdge[iE];

        int iV0 = rkE.m_aiVertex[0];
        if ( m_akVertex[iV0].m_iOccurs == 1 )
        {
            if ( riVStart == -1 )
            {
                riVStart = iV0;
            }
            else if ( riVFinal == -1 )
            {
                riVFinal = iV0;
            }
            else
            {
                // If you reach this assert, there is a good chance that the
                // polyhedron is not convex.  To check this, use the function
                // ValidateHalfSpaceProperty() on your polyhedron right after
                // you construct it.
                assert( false );
            }
        }

        int iV1 = rkE.m_aiVertex[1];
        if ( m_akVertex[iV1].m_iOccurs == 1 )
        {
            if ( riVStart == -1 )
            {
                riVStart = iV1;
            }
            else if ( riVFinal == -1 )
            {
                riVFinal = iV1;
            }
            else
            {
                // If you reach this assert, there is a good chance that the
                // polyhedron is not convex.  To check this, use the function
                // ValidateHalfSpaceProperty() on your polyhedron right after
                // you construct it.
                assert( false );
            }
        }
    }

    assert( (riVStart == -1 && riVFinal == -1)
        ||  (riVStart != -1 && riVFinal != -1) );

    return riVStart != -1;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexClipper<Real>::OrderVertices (Face& rkF, vector<int>& aiVOrdered)
{
    // copy edge indices into contiguous memory
    int i = 0, iQuantity = (int)rkF.m_akEdge.size();
    vector<int> aiEOrdered(iQuantity);
    set<int>::iterator pkIter = rkF.m_akEdge.begin();
    while ( pkIter != rkF.m_akEdge.end() )
        aiEOrdered[i++] = *pkIter++;

    // bubble sort (yes, it is...)
    for (int i0 = 0, i1 = 1, iChoice = 1; i1 < iQuantity-1; i0 = i1, i1++)
    {
        Edge& rkECurr = m_akEdge[aiEOrdered[i0]];
        int j, iCurr = rkECurr.m_aiVertex[iChoice];
        for (j = i1; j < iQuantity; j++)
        {
            Edge& rkETemp = m_akEdge[aiEOrdered[j]];
            int iSave;
            if ( rkETemp.m_aiVertex[0] == iCurr )
            {
                iSave = aiEOrdered[i1];
                aiEOrdered[i1] = aiEOrdered[j];
                aiEOrdered[j] = iSave;
                iChoice = 1;
                break;
            }
            if ( rkETemp.m_aiVertex[1] == iCurr )
            {
                iSave = aiEOrdered[i1];
                aiEOrdered[i1] = aiEOrdered[j];
                aiEOrdered[j] = iSave;
                iChoice = 0;
                break;
            }
        }
        assert( j < iQuantity );
    }

    aiVOrdered[0] = m_akEdge[aiEOrdered[0]].m_aiVertex[0];
    aiVOrdered[1] = m_akEdge[aiEOrdered[0]].m_aiVertex[1];
    for (i = 1; i < iQuantity; i++)
    {
        Edge& rkE = m_akEdge[aiEOrdered[i]];
        if ( rkE.m_aiVertex[0] == aiVOrdered[i] )
            aiVOrdered[i+1] = rkE.m_aiVertex[1];
        else
            aiVOrdered[i+1] = rkE.m_aiVertex[0];
    }
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexClipper<Real>::GetTriangles (vector<int>& raiConnect,
    vector<Plane3<Real> >& rakPlane)
{
    for (int iF = 0; iF < (int)m_akFace.size(); iF++)
    {
        Face& rkF = m_akFace[iF];
        if ( rkF.m_bVisible )
        {
            int iQuantity = (int)rkF.m_akEdge.size();
            assert( iQuantity >= 3 );
            vector<int> aiOrdered(iQuantity+1);
            OrderVertices(rkF,aiOrdered);

            int iV0 = aiOrdered[0], iV2 = aiOrdered[iQuantity-1];
            int iV1 = aiOrdered[(iQuantity-1) >> 1];
            Vector3<Real> kD1 = m_akVertex[iV1].m_kPoint -
                m_akVertex[iV0].m_kPoint;
            Vector3<Real> kD2 = m_akVertex[iV2].m_kPoint -
                m_akVertex[iV0].m_kPoint;
            Real fTSP = rkF.m_kPlane.GetNormal().Dot(kD1.Cross(kD2));
            if ( fTSP > (Real)0.0 )
            {
                // clockwise, need to swap
                for (int i = 1; i+1 < iQuantity; i++)
                {
                    raiConnect.push_back(iV0);
                    raiConnect.push_back(aiOrdered[i+1]);
                    raiConnect.push_back(aiOrdered[i]);
                    rakPlane.push_back(rkF.m_kPlane);
                }
            }
            else
            {
                // counterclockwise
                for (int i = 1; i+1 < iQuantity; i++)
                {
                    raiConnect.push_back(iV0);
                    raiConnect.push_back(aiOrdered[i]);
                    raiConnect.push_back(aiOrdered[i+1]);
                    rakPlane.push_back(rkF.m_kPlane);
                }
            }
        }
    }
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexClipper<Real>::Convert (ConvexPolyhedron3<Real>& rkPoly)
{
    // get visible vertices
    int iVQuantity = (int)m_akVertex.size();
    vector<Vector3<Real> > akPoint;
    int* aiVMap = new int[iVQuantity];
    memset(aiVMap,0xFF,iVQuantity*sizeof(int));
    for (int iV = 0; iV < iVQuantity; iV++)
    {
        const Vertex& rkV = m_akVertex[iV];
        if ( rkV.m_bVisible )
        {
            aiVMap[iV] = (int)akPoint.size();
            akPoint.push_back(rkV.m_kPoint);
        }
    }

    vector<int> aiConnect;
    vector<Plane3<Real> > akPlane;
    GetTriangles(aiConnect,akPlane);

    // re-order
    int iNewVQuantity = (int)akPoint.size();
    for (int iC = 0; iC < (int)aiConnect.size(); iC++)
    {
        int iOldC = aiConnect[iC];
        assert( 0 <= iOldC && iOldC < iVQuantity );
        int iNewC = aiVMap[iOldC];
        assert( 0 <= iNewC && iNewC < iNewVQuantity );
        aiConnect[iC] = iNewC;
    }

    delete[] aiVMap;

    rkPoly.Create(akPoint,aiConnect,akPlane);
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexClipper<Real>::Print (const char* acFilename) const
{
    ofstream kOStr(acFilename);
    if ( !kOStr )
        return false;

    int iVQuantity = (int)m_akVertex.size();
    int iEQuantity = (int)m_akEdge.size();
    int iFQuantity = (int)m_akFace.size();
    int iVDigits = (int)(ceil(log10((double)iVQuantity)));
    int iEDigits = (int)(ceil(log10((double)iEQuantity)));
    int iFDigits = (int)(ceil(log10((double)iFQuantity)));
    char acMsg[1024];

    kOStr << iVQuantity << " vertices" << endl;
    for (int iV = 0; iV < iVQuantity; iV++)
    {
        const Vertex& rkV = m_akVertex[iV];
        sprintf(acMsg,"v<%*d> %c: (%f,%f,%f)",
            iVDigits,iV,(rkV.m_bVisible ? 'T' : 'F'),
            rkV.m_kPoint.X(),
            rkV.m_kPoint.Y(),
            rkV.m_kPoint.Z());
        kOStr << acMsg << endl;
    }
    kOStr << endl;

    kOStr << iEQuantity << " edges" << endl;
    for (int iE = 0; iE < iEQuantity; iE++)
    {
        const Edge& rkE = m_akEdge[iE];
        sprintf(acMsg,"e<%*d> %c: v[%*d,%*d], t[%*d,%*d]",
            iEDigits,iE,(rkE.m_bVisible ? 'T' : 'F'),
            iVDigits,rkE.m_aiVertex[0],
            iVDigits,rkE.m_aiVertex[1],
            iFDigits,rkE.m_aiFace[0],
            iFDigits,rkE.m_aiFace[1]);
        kOStr << acMsg << endl;
    }
    kOStr << endl;

    kOStr << iFQuantity << " faces" << endl;
    for (int iF = 0; iF < iFQuantity; iF++)
    {
        const Face& rkF = m_akFace[iF];
        sprintf(acMsg,"t<%*d> %d: e = ",
            iFDigits,iF,(rkF.m_bVisible ? 'T' : 'F'));
        kOStr << acMsg;

        set<int>::const_iterator pkIter = rkF.m_akEdge.begin();
        while ( pkIter != rkF.m_akEdge.end() )
        {
            kOStr << *pkIter << ' ';
            pkIter++;
        }
        kOStr << endl;
    }

    return true;
}
//----------------------------------------------------------------------------

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