wmlcreateclodmesh.cpp

3D Game Engine Design Source Code非常棒

    if ( m_akNormal )
    {
        Vector3f* akNewNormal = new Vector3f[m_iVQuantity];
        for (i = 0; i < m_iVQuantity; i++)
            akNewNormal[i] = m_akNormal[m_aiVOrdered[i]];
        memcpy(m_akNormal,akNewNormal,m_iVQuantity*sizeof(Vector3f));
        delete[] akNewNormal;
    }

    // permute the colors (if any)
    if ( m_akColor )
    {
        ColorRGB* akNewColor = new ColorRGB[m_iVQuantity];
        for (i = 0; i < m_iVQuantity; i++)
            akNewColor[i] = m_akColor[m_aiVOrdered[i]];
        memcpy(m_akColor,akNewColor,m_iVQuantity*sizeof(ColorRGB));
        delete[] akNewColor;
    }

    // permute the texture coordinates (if any)
    if ( m_akTexture )
    {
        Vector2f* akNewTexture = new Vector2f[m_iVQuantity];
        for (i = 0; i < m_iVQuantity; i++)
            akNewTexture[i] = m_akTexture[m_aiVOrdered[i]];
        memcpy(m_akTexture,akNewTexture,m_iVQuantity*sizeof(Vector2f));
        delete[] akNewTexture;
    }

    // permute the connectivity array and copy to the original array
    for (i = 0; i < 3*m_iTQuantity; i++)
        m_aiConnect[i] = m_aiVPermute[m_aiNewConnect[i]];

    // permute the keep/throw pairs
    for (i = 0; i < (int)m_kEDelete.size(); i++)
    {
        CollapseRecord& rkCR = m_kEDelete[i];
        rkCR.m_iVKeep = m_aiVPermute[rkCR.m_iVKeep];
        rkCR.m_iVThrow = m_aiVPermute[rkCR.m_iVThrow];
    }
}
//----------------------------------------------------------------------------
void CreateClodMesh::ComputeRecords (int& riCQuantity,
    CollapseRecord*& rakCRecord)
{
    // build the collapse records for the caller
    riCQuantity = (int)m_kEDelete.size() + 1;
    rakCRecord = new CollapseRecord[riCQuantity];

    // initial record only stores the initial vertex and triangle quantities
    rakCRecord[0].m_iVQuantity = m_iVQuantity;
    rakCRecord[0].m_iTQuantity = m_iTQuantity;

    // construct the replacement arrays
    int iVQuantity = m_iVQuantity, iTQuantity = m_iTQuantity;
    int iR, i;
    for (iR = 0; iR < (int)m_kEDelete.size(); iR++)
    {
        CollapseRecord& rkERecord = m_kEDelete[iR];
        CollapseRecord& rkRecord = rakCRecord[iR+1];

        iVQuantity -= rkERecord.m_iVQuantity;
        iTQuantity -= rkERecord.m_iTQuantity;

        rkRecord.m_iVKeep = rkERecord.m_iVKeep;
        rkRecord.m_iVThrow = rkERecord.m_iVThrow;
        rkRecord.m_iVQuantity = iVQuantity;
        rkRecord.m_iTQuantity = iTQuantity;
        rkRecord.m_iIQuantity = 0;

        if ( iTQuantity > 0 )
        {
            int iIMax = 3*iTQuantity;
            int* aiIndex = new int[iIMax];
            for (i = 0; i < iIMax; i++)
            {
                if ( m_aiConnect[i] == rkRecord.m_iVThrow )
                {
                    m_aiConnect[i] = rkRecord.m_iVKeep;
                    aiIndex[rkRecord.m_iIQuantity++] = i;
                }
            }

            if ( rkRecord.m_iIQuantity > 0 )
            {
                rkRecord.m_aiIndex = new int[rkRecord.m_iIQuantity];
                memcpy(rkRecord.m_aiIndex,aiIndex,
                    rkRecord.m_iIQuantity*sizeof(int));
            }

            delete[] aiIndex;
        }
        else
        {
            rkRecord.m_aiIndex = NULL;
        }
    }

    // expand mesh back to original
    for (iR = riCQuantity - 1; iR > 0; iR--)
    {
        // restore indices in connectivity array
        CollapseRecord& rkRecord = rakCRecord[iR];
        for (i = 0; i < rkRecord.m_iIQuantity; i++)
        {
            int iC = rkRecord.m_aiIndex[i];
            assert( m_aiConnect[iC] == rkRecord.m_iVKeep );
            m_aiConnect[iC] = rkRecord.m_iVThrow;
        }
    }
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// heap operations
//----------------------------------------------------------------------------
void CreateClodMesh::InitializeHeap ()
{
    // It is possible that during an edge collapse, the number of *temporary*
    // edges is larger than the original number of edges in the mesh.  To
    // make sure there is enough heap space, allocate two times the number of
    // original edges.
    m_iHQuantity = (int)m_kEMap.size();
    m_apkHeap = new HeapRecord*[2*m_iHQuantity];

    int iHIndex = 0;
    for (MEIter pkE = m_kEMap.begin(); pkE != m_kEMap.end(); pkE++, iHIndex++)
    {
        m_apkHeap[iHIndex] = (HeapRecord*)pkE->second.m_pvData;
        m_apkHeap[iHIndex]->m_kEdge = pkE->first;
        m_apkHeap[iHIndex]->m_iHIndex = iHIndex;
        m_apkHeap[iHIndex]->m_fMetric = GetMetric(pkE);
    }

    Sort();
}
//----------------------------------------------------------------------------
void CreateClodMesh::Sort ()
{
    int iLast = m_iHQuantity - 1;
    for (int iLeft = iLast/2; iLeft >= 0; iLeft--)
    {
        HeapRecord* pkRecord = m_apkHeap[iLeft];
        int iPa = iLeft, iCh = 2*iLeft + 1;
        while ( iCh <= iLast )
        {
            if ( iCh < iLast )
            {
                int iChP = iCh+1;
                if ( m_apkHeap[iCh]->m_fMetric > m_apkHeap[iChP]->m_fMetric )
                    iCh = iChP;
            }

            if ( m_apkHeap[iCh]->m_fMetric >= pkRecord->m_fMetric )
                break;

            m_apkHeap[iCh]->m_iHIndex = iPa;
            m_apkHeap[iPa] = m_apkHeap[iCh];
            iPa = iCh;
            iCh = 2*iCh + 1;
        }

        pkRecord->m_iHIndex = iPa;
        m_apkHeap[iPa] = pkRecord;
    }
}
//----------------------------------------------------------------------------
void CreateClodMesh::Add (float fMetric)
{
    // Under normal heap operations, you would have to make sure that the
    // heap storage grows if necessary.  Increased storage demand will not
    // happen in this application.  The creation of the heap record itself is
    // done in OnEdgeCreate.
    m_iHQuantity++;

    int iCh = m_iHQuantity - 1;
    HeapRecord* pkRecord = m_apkHeap[iCh];
    pkRecord->m_fMetric = fMetric;
    while ( iCh > 0 )
    {
        int iPa = (iCh-1)/2;
        if ( m_apkHeap[iPa]->m_fMetric <= fMetric )
            break;

        m_apkHeap[iPa]->m_iHIndex = iCh;
        m_apkHeap[iCh] = m_apkHeap[iPa];
        pkRecord->m_iHIndex = iPa;
        pkRecord->m_fMetric = fMetric;
        m_apkHeap[iPa] = pkRecord;
        iCh = iPa;
    }

    m_apkHeap[iCh]->m_fMetric = fMetric;
}
//----------------------------------------------------------------------------
void CreateClodMesh::Remove ()
{
    HeapRecord* pkRoot = m_apkHeap[0];

    int iLast = m_iHQuantity - 1;
    HeapRecord* pkRecord = m_apkHeap[iLast];
    int iPa = 0, iCh = 1;
    while ( iCh <= iLast )
    {
        if ( iCh < iLast )
        {
            int iChP = iCh+1;
            if ( m_apkHeap[iCh]->m_fMetric > m_apkHeap[iChP]->m_fMetric )
                iCh = iChP;
        }

        if ( m_apkHeap[iCh]->m_fMetric >= pkRecord->m_fMetric )
            break;

        m_apkHeap[iCh]->m_iHIndex = iPa;
        m_apkHeap[iPa] = m_apkHeap[iCh];
        iPa = iCh;
        iCh = 2*iCh + 1;
    }

    pkRecord->m_iHIndex = iPa;
    m_apkHeap[iPa] = pkRecord;
    m_iHQuantity--;

    // To notify OnEdgeDestroy that this edge was already removed from the
    // heap, but the object must be deleted by that callback.
    pkRoot->m_iHIndex = -1;
}
//----------------------------------------------------------------------------
void CreateClodMesh::Update (int iHIndex, float fMetric)
{
    HeapRecord* pkRecord = m_apkHeap[iHIndex];
    int iPa, iCh, iChP, iMaxCh;

    if ( fMetric > pkRecord->m_fMetric )
    {
        pkRecord->m_fMetric = fMetric;

        // new weight larger than old, propagate it towards the leaves
        iPa = iHIndex;
        iCh = 2*iPa+1;
        while ( iCh < m_iHQuantity )
        {
            // at least one child exists
            if ( iCh < m_iHQuantity-1 )
            {
                // two children exist
                iChP = iCh+1;
                if ( m_apkHeap[iCh]->m_fMetric <= m_apkHeap[iChP]->m_fMetric )
                    iMaxCh = iCh;
                else
                    iMaxCh = iChP;
            }
            else
            {
                // one child exists
                iMaxCh = iCh;
            }

            if ( m_apkHeap[iMaxCh]->m_fMetric >= fMetric )
                break;

            m_apkHeap[iMaxCh]->m_iHIndex = iPa;
            m_apkHeap[iPa] = m_apkHeap[iMaxCh];
            pkRecord->m_iHIndex = iMaxCh;
            m_apkHeap[iMaxCh] = pkRecord;
            iPa = iMaxCh;
            iCh = 2*iPa+1;
        }
    }
    else if ( fMetric < pkRecord->m_fMetric )
    {
        pkRecord->m_fMetric = fMetric;

        // new weight smaller than old, propagate it towards the root
        iCh = iHIndex;
        while ( iCh > 0 )
        {
            // a parent exists
            iPa = (iCh-1)/2;

            if ( m_apkHeap[iPa]->m_fMetric <= fMetric )
                break;

            m_apkHeap[iPa]->m_iHIndex = iCh;
            m_apkHeap[iCh] = m_apkHeap[iPa];
            pkRecord->m_iHIndex = iPa;
            pkRecord->m_fMetric = fMetric;
            m_apkHeap[iPa] = pkRecord;
            iCh = iPa;
        }
    }
}
//----------------------------------------------------------------------------
bool CreateClodMesh::IsValidHeap (int iStart, int iFinal)
{
    for (int iC = iStart; iC <= iFinal; iC++)
    {
        int iP = (iC-1)/2;
        if ( iP > iStart )
        {
            if ( m_apkHeap[iP]->m_fMetric > m_apkHeap[iC]->m_fMetric )
                return false;

            if ( m_apkHeap[iP]->m_iHIndex != iP )
                return false;
        }
    }

    return true;
}
//----------------------------------------------------------------------------
bool CreateClodMesh::IsValidHeap ()
{
    return IsValidHeap(0,m_iHQuantity-1);
}
//----------------------------------------------------------------------------
void CreateClodMesh::PrintHeap (const char* acFilename)
{
    ofstream kOStr(acFilename);
    for (int i = 0; i < m_iHQuantity; i++)
    {
        HeapRecord* pkRecord = m_apkHeap[i];
        kOStr << pkRecord->m_iHIndex << "= <" << pkRecord->m_kEdge.m_aiV[0]
              << ',' << pkRecord->m_kEdge.m_aiV[1] << "> "
              << pkRecord->m_fMetric << endl;

        int iValue = i+2;
        int iBits = 0;
        while ( iValue != 0 )
        {
            if ( iValue & 1 )
                iBits++;
            iValue >>= 1;
        }
        if ( iBits == 1 )
            kOStr << endl;
    }
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// mesh insert/remove callbacks
//----------------------------------------------------------------------------
void CreateClodMesh::OnVertexInsert (int iV, bool bCreate, void*&)
{
    // It is possible that a 'keep' vertex was removed because the triangles
    // sharing the collapse edge were removed first, but then the insertion
    // of a modified triangle reinserts the 'keep' vertex.
    if ( bCreate && m_bCollapsing )
        m_kVDelete.erase(iV);
}
//----------------------------------------------------------------------------
void CreateClodMesh::OnVertexRemove (int iV, bool bDestroy, void*)
{
    // Keep track of vertices removed during the edge collapse.
    if ( bDestroy && m_bCollapsing )
        m_kVDelete.insert(iV);
}
//----------------------------------------------------------------------------
void CreateClodMesh::OnEdgeInsert (const Edge& rkE, bool bCreate,
    void*& rpvData)
{
    if ( bCreate )
    {
        rpvData = new HeapRecord;
        if ( m_bCollapsing )
        {
            m_apkHeap[m_iHQuantity] = (HeapRecord*)rpvData;
            m_apkHeap[m_iHQuantity]->m_kEdge = rkE;
            m_apkHeap[m_iHQuantity]->m_iHIndex = m_iHQuantity;
            Add(GetMetric(m_kEMap.find(rkE)));
        }
    }
    else
    {
        if ( m_bCollapsing )
        {
            HeapRecord* pkRecord = (HeapRecord*)rpvData;
            assert( pkRecord->m_kEdge == rkE );
            if ( pkRecord->m_iHIndex >= 0 )
            {
                Update(pkRecord->m_iHIndex,GetMetric(m_kEMap.find(rkE)));
            }
            else
            {
                assert( pkRecord->m_iHIndex == -1 );
                pkRecord->m_iHIndex = m_iHQuantity;
                Add(GetMetric(m_kEMap.find(rkE)));
            }
        }
    }
}
//----------------------------------------------------------------------------
void CreateClodMesh::OnEdgeRemove (const Edge&, bool bDestroy, void* pvData)
{
    // Remove the edge from the heap.  The metric of the edge is set to
    // -INFINITY so that it has the minimum value of all edges.  The update
    // call bubbles the edge to the root of the heap.  The edge is then
    // removed from the root.

    if ( bDestroy )
    {
        HeapRecord* pkRecord = (HeapRecord*)pvData;
        if ( pkRecord->m_iHIndex >= 0 )
        {
            Update(pkRecord->m_iHIndex,-FLT_MAX);
            Remove();
        }
        delete pkRecord;
    }
}
//----------------------------------------------------------------------------
void CreateClodMesh::OnTriangleInsert (const Triangle&, bool bCreate,
    void*& rpvData)
{
    if ( bCreate )
        rpvData = new int(-1);
}
//----------------------------------------------------------------------------
void CreateClodMesh::OnTriangleRemove (const Triangle&, bool bDestroy,
    void* pvData)
{
    if ( bDestroy )
        delete (int*)pvData;
}
//----------------------------------------------------------------------------