mgcclodmesh.cpp

来自「《3D游戏引擎设计》的源码」· C++ 代码 · 共 572 行 · 第 1/2 页

    unsigned int* auiNewIndex = new unsigned int[3*uiQuantity];
    unsigned int* puiMinNewIndex = auiNewIndex;
    unsigned int* puiMaxNewIndex = auiNewIndex + 3*(uiQuantity - 1);
    unsigned int* puiIndex = auiIndex;

    unsigned int* auiNewConnect = new unsigned int[3*uiQuantity];
    unsigned int* puiMinNewConnect = auiNewConnect;
    unsigned int* puiMaxNewConnect = auiNewConnect + 3*(uiQuantity - 1);
    unsigned int* puiConnect = m_auiConnect;

    unsigned int uiAtEnd = 0;
    unsigned int uiT;
    for (uiT = 0; uiT < uiQuantity; uiT++)
    {
        if ( TriangleContainsEdge(uiT,rkRecord.m_uiI0,rkRecord.m_uiI1) )
        {
            memcpy(puiMaxNewIndex,puiIndex,3*sizeof(unsigned int));
            puiMaxNewIndex -= 3;

            memcpy(puiMaxNewConnect,puiConnect,3*sizeof(unsigned int));
            puiMaxNewConnect -= 3;

            uiAtEnd++;
        }
        else
        {
            memcpy(puiMinNewIndex,puiIndex,3*sizeof(unsigned int));
            puiMinNewIndex += 3;

            memcpy(puiMinNewConnect,puiConnect,3*sizeof(unsigned int));
            puiMinNewConnect += 3;
        }

        puiIndex += 3;
        puiConnect += 3;
    }

    delete[] auiIndex;
    memcpy(m_auiConnect,auiNewConnect,3*uiQuantity*sizeof(unsigned int));
    delete[] auiNewConnect;
    m_akRecord[m_iCurrentRecord].m_uiTriangleQuantity = uiQuantity - uiAtEnd;

    // compute the inverse permutation of auiNewIndex
    unsigned int* auiPermute = new unsigned int[3*uiQuantity];
    for (uiI = 0; uiI < 3*uiQuantity; uiI++)
        auiPermute[auiNewIndex[uiI]] = uiI;
    delete[] auiNewIndex;

    // Previous records store connectivity indices.  Since the repacking
    // permutes the indices, the previous records must be adjusted to match
    // the current ordering.
    for (int iR = 0; iR < m_iCurrentRecord; iR++)
    {
        Record& rkRec = m_akRecord[iR];
        for (unsigned int uiV = 0; uiV < rkRec.m_uiVertexQuantity; uiV++)
        {
            uiI = rkRec.m_auiIndex[uiV];
            if ( uiI < 3*uiQuantity )
                rkRec.m_auiIndex[uiV] = auiPermute[uiI];
        }
    }

    delete[] auiPermute;
}
//----------------------------------------------------------------------------
void MgcCLodMesh::GetConnectivityIndices ()
{
    Record& rkRecord = m_akRecord[m_iCurrentRecord];
    unsigned int uiIMax = 3*rkRecord.m_uiTriangleQuantity;
    unsigned int* auiIndex = new unsigned int[uiIMax];

    unsigned int uiQuantity = 0;
    for (unsigned int uiI = 0; uiI < uiIMax; uiI++)
    {
        if ( m_auiConnect[uiI] == rkRecord.m_uiI1 )
        {
            m_auiConnect[uiI] = rkRecord.m_uiI0;
            auiIndex[uiQuantity++] = uiI;
        }
    }

    rkRecord.m_uiVertexQuantity = uiQuantity;
    if ( uiQuantity > 0 )
    {
        rkRecord.m_auiIndex = new unsigned int[uiQuantity];
        memcpy(rkRecord.m_auiIndex,auiIndex,uiQuantity*sizeof(unsigned int));
    }

    delete[] auiIndex;
}
//----------------------------------------------------------------------------
void MgcCLodMesh::RecalculateErrors (HeapType* pkHeap, ErrorMatrix* akQ,
    unsigned int uiKeep, unsigned int uiRemove)
{
    // Edges to be recalculated are removed from current heap and saved in
    // a temporary heap.  The number '16' is chosen with the expectation
    // that a vertex is shared by a small number of edges.  If this number
    // is exceeded, hash collisions will occur, but the algorithm still
    // works.
    HeapType* pkSaveHeap = new HeapType(16);

    // The implementation of MgcTClassMap prohibits a RemoveAt call in the
    // middle of a hash iteration using GetFirst/GetNext.  The hash items
    // to be updated must be removed after the traversal.  The keys for
    // those items are temporarily stored so that a sequence of RemoveAt
    // calls can be made.
    unsigned int uiSaveKeyQuantity = 0;
    KeyType* akSaveKey = new KeyType[pkHeap->GetQuantity()];

    unsigned int uiK;
    KeyType kKey;
    MgcReal fMetric;
    bool bFound = pkHeap->GetFirst(kKey,fMetric);
    while ( bFound )
    {
        ErrorMatrix kSum;

        if ( kKey.m_uiI0 == uiRemove )
        {
            akSaveKey[uiSaveKeyQuantity++] = kKey;

            kKey = KeyType(uiKeep,kKey.m_uiI1);

            for (uiK = 0; uiK < 10; uiK++)
                kSum[uiK] = akQ[kKey.m_uiI0][uiK] + akQ[kKey.m_uiI1][uiK];

            MgcVector3& rkV = m_akVertex[uiKeep];

            fMetric =
                rkV.x*(kSum[0]*rkV.x+kSum[1]*rkV.y+kSum[2]*rkV.z+kSum[3]) +
                rkV.y*(kSum[1]*rkV.x+kSum[4]*rkV.y+kSum[5]*rkV.z+kSum[6]) +
                rkV.z*(kSum[2]*rkV.x+kSum[5]*rkV.y+kSum[7]*rkV.z+kSum[8]) +
                      (kSum[3]*rkV.x+kSum[6]*rkV.y+kSum[8]*rkV.z+kSum[9]);

            pkSaveHeap->SetAt(kKey,fMetric);
        }
        else if ( kKey.m_uiI1 == uiRemove )
        {
            akSaveKey[uiSaveKeyQuantity++] = kKey;

            kKey = KeyType(uiKeep,kKey.m_uiI0);

            for (uiK = 0; uiK < 10; uiK++)
                kSum[uiK] = akQ[kKey.m_uiI0][uiK] + akQ[kKey.m_uiI1][uiK];

            MgcVector3& rkV = m_akVertex[uiKeep];

            fMetric =
                rkV.x*(kSum[0]*rkV.x+kSum[1]*rkV.y+kSum[2]*rkV.z+kSum[3]) +
                rkV.y*(kSum[1]*rkV.x+kSum[4]*rkV.y+kSum[5]*rkV.z+kSum[6]) +
                rkV.z*(kSum[2]*rkV.x+kSum[5]*rkV.y+kSum[7]*rkV.z+kSum[8]) +
                      (kSum[3]*rkV.x+kSum[6]*rkV.y+kSum[8]*rkV.z+kSum[9]);

            pkSaveHeap->SetAt(kKey,fMetric);
        }

        bFound = pkHeap->GetNext(kKey,fMetric);
    }

    // remove the old edges from the original heap
    for (uiK = 0; uiK < uiSaveKeyQuantity; uiK++)
        pkHeap->RemoveAt(akSaveKey[uiK]);

    // add the new edges to the original heap.
    bFound = pkSaveHeap->GetFirst(kKey,fMetric);
    while ( bFound )
    {
        pkHeap->SetAt(kKey,fMetric);
        bFound = pkSaveHeap->GetNext(kKey,fMetric);
    }

    delete[] akSaveKey;
    delete pkSaveHeap;
}
//----------------------------------------------------------------------------
void MgcCLodMesh::ComputeEdgeCollapses (HeapType* pkHeap, ErrorMatrix* akQ)
{
    m_iCurrentRecord = 0;
    m_akRecord = new Record[m_uiVertexQuantity - 1];

    while ( !pkHeap->IsEmpty() )
    {
        // find minimum error
        KeyType kMinKey, kKey;
        MgcReal fMinMetric, fMetric;
        pkHeap->GetFirst(kMinKey,fMinMetric);
        while ( pkHeap->GetNext(kKey,fMetric) )
        {
            if ( fMetric < fMinMetric )
            {
                kMinKey = kKey;
                fMinMetric = fMetric;
            }
        }

        // add vertex indices to record
        m_akRecord[m_iCurrentRecord].m_uiI0 = kMinKey.m_uiI0;
        m_akRecord[m_iCurrentRecord].m_uiI1 = kMinKey.m_uiI1;

        // move triangles sharing edge to end of connectivity array
        MoveTrianglesToEnd();

        // replace indices and save the locations
        GetConnectivityIndices();

        // remove edge and recalculate error metrics for new edges
        bool bOkay = pkHeap->RemoveAt(kMinKey);
        RecalculateErrors(pkHeap,akQ,kMinKey.m_uiI0,kMinKey.m_uiI1);

        m_iCurrentRecord++;
    }

    assert( m_iCurrentRecord == int(m_uiVertexQuantity - 1) );
    m_iCurrentRecord--;
}
//----------------------------------------------------------------------------
void MgcCLodMesh::ReorderVertices ()
{
    // TO DO.  The vertices are removed one-at-a-time during the edge
    // collapse calculations.  If these are kept track of, then the vertex
    // array itself can be reordered so that during an edge collapse, the
    // m_uiVertexQuantity can be decremented.  This allows the renderer to
    // only transform those vertices that actually do occur in the
    // simplification.
}
//----------------------------------------------------------------------------
void MgcCLodMesh::ComputeRecords ()
{
    ErrorMatrix* akQ = ComputeVertexErrorMatrices();
    HeapType* pkHeap = ComputeEdgeErrorMetrics(akQ);
    ComputeEdgeCollapses(pkHeap,akQ);
    ReorderVertices();

    // expand mesh to original
    while ( m_iCurrentRecord >= 0 )
    {
        // restore indices in connectivity array
        Record& rkRecord = m_akRecord[m_iCurrentRecord];
        for (unsigned int uiV = 0; uiV < rkRecord.m_uiVertexQuantity; uiV++)
        {
            unsigned int uiI = rkRecord.m_auiIndex[uiV];
            assert( m_auiConnect[uiI] == rkRecord.m_uiI0 );
            m_auiConnect[uiI] = rkRecord.m_uiI1;
        }

        m_iCurrentRecord--;
    }

    delete[] akQ;
    delete pkHeap;
}
//----------------------------------------------------------------------------

//---------------------------------------------------------------------------
// streaming
//---------------------------------------------------------------------------
MgcObject* MgcCLodMesh::Factory (MgcStream& rkStream)
{
    MgcCLodMesh* pkObject = new MgcCLodMesh;
    MgcStream::Link* pkLink = new MgcStream::Link(pkObject);
    pkObject->Load(rkStream,pkLink);
    return pkObject;
}
//---------------------------------------------------------------------------
void MgcCLodMesh::Load (MgcStream& rkStream, MgcStream::Link* pkLink)
{
    MgcTriMesh::Load(rkStream,pkLink);
}
//---------------------------------------------------------------------------
void MgcCLodMesh::Link (MgcStream& rkStream, MgcStream::Link* pkLink)
{
    MgcTriMesh::Link(rkStream,pkLink);
}
//---------------------------------------------------------------------------
bool MgcCLodMesh::Register (MgcStream& rkStream)
{
    return MgcTriMesh::Register(rkStream);
}
//---------------------------------------------------------------------------
void MgcCLodMesh::Save (MgcStream& rkStream)
{
    MgcTriMesh::Save(rkStream);
}
//---------------------------------------------------------------------------