wmlcreateclodmesh.cpp

3D Game Engine Design Source Code非常棒

// Magic Software, Inc.
// http://www.magic-software.com
// http://www.wild-magic.com
// Copyright (c) 2003.  All Rights Reserved
//
// The Wild Magic Library (WML) source code is supplied under the terms of
// the license agreement http://www.magic-software.com/License/WildMagic.pdf
// and may not be copied or disclosed except in accordance with the terms of
// that agreement.

#include "WmlCreateClodMesh.h"
using namespace Wml;

#include <fstream>
#include <stack>
using namespace std;

//----------------------------------------------------------------------------
CreateClodMesh::CreateClodMesh (int iVQuantity, Vector3f* akVertex,
    Vector3f* akNormal, ColorRGB* akColor, Vector2f* akTexture,
    int iTQuantity, int* aiConnect, int& riCQuantity,
    CollapseRecord*& rakCRecord)
{
    // Hang onto these to avoid having to pass them through member function
    // calls.
    m_iVQuantity = iVQuantity;
    m_akVertex = akVertex;
    m_akNormal = akNormal;
    m_akColor = akColor;
    m_akTexture = akTexture;
    m_iTQuantity = iTQuantity;
    m_aiConnect = aiConnect;

    // for reordering vertices and triangles
    m_iVCurrent = m_iVQuantity-1;
    m_iTCurrent = m_iTQuantity-1;
    m_aiVOrdered = new int[m_iVQuantity];
    m_aiVPermute = new int[m_iVQuantity];
    m_aiNewConnect = new int[3*m_iTQuantity];

    // Insert the triangles into the mesh.  The triangle indices are attached
    // as extra data.
    m_bCollapsing = false;
    for (int i = 0; i < m_iTQuantity; i++)
    {
        int iV0 = aiConnect[3*i];
        int iV1 = aiConnect[3*i+1];
        int iV2 = aiConnect[3*i+2];
        assert( iV0 != iV1 && iV0 != iV2 && iV1 != iV2 );
        Triangle kT(aiConnect[3*i],aiConnect[3*i+1],aiConnect[3*i+2]);
        InsertTriangle(kT);
        *(int*)GetData(kT) = i;
    }

    assert( (int)(m_kVMap.size()) == m_iVQuantity );
    assert( (int)(m_kTMap.size()) == m_iTQuantity );

    InitializeHeap();

    m_bCollapsing = true;
    while ( m_iHQuantity > 0 )
    {
        if ( m_apkHeap[0]->m_fMetric == FLT_MAX )
        {
            // all remaining heap elements have infinite weight
            FlushVertices();
            FlushTriangles();
            break;
        }

        DoCollapse();

        assert( (int)(m_kVMap.size()) == m_iVCurrent+1 );
        assert( (int)(m_kTMap.size()) == m_iTCurrent+1 );
    }
    m_bCollapsing = false;

    // Permute the vertices and triangle connectivity so that the last
    // vertex/triangle in the array is the first vertex/triangle to be
    // removed.
    Reorder();

    // The collapse records store the incremental changes that are used for
    // dynamic LOD changes in the caller of this constructor.
    ComputeRecords(riCQuantity,rakCRecord);
}
//----------------------------------------------------------------------------
CreateClodMesh::~CreateClodMesh ()
{
    RemoveAllTriangles();
    delete[] m_apkHeap;
    delete[] m_aiVOrdered;
    delete[] m_aiVPermute;
    delete[] m_aiNewConnect;
}
//----------------------------------------------------------------------------
void CreateClodMesh::DoCollapse ()
{
    // Define a 2-edge to be an edge that has exactly two triangles sharing
    // it.  An edge is collapsible if it is a 2-edge and has at least one end
    // point whose sharing edges are all 2-edges.  In this case, such an end
    // point will be the 'throw' vertex.  This keeps the boundary and junction
    // edges from changing geometry and helps preserve the shape of the mesh.
    // The topology is always guaranteed not to change.

    // When this function is called, the metric has already been calculated
    // and is finite (so exactly two triangles must be sharing this edge).
    assert( m_apkHeap[0]->m_fMetric < FLT_MAX );
    Edge kEdge = m_apkHeap[0]->m_kEdge;

    // test end points to see if either has only 2-edges sharing it
    int i;
    for (i = 0; i < 2; i++)
    {
        const SmallSet<Edge>* pkESet = GetEdges(kEdge.m_aiV[i]);
        int j;
        for (j = 0; j < pkESet->GetSize(); j++)
        {
            MECIter pkEM = m_kEMap.find((*pkESet)[j]);
            assert( pkEM != m_kEMap.end() );
            if ( pkEM->second.m_kTSet.GetSize() != 2 )
                break;
        }

        if ( j == pkESet->GetSize() )
        {
            // all edges sharing this end point are 2-edges
            break;
        }
    }

    if ( i < 2 )
    {
        int iVThrow = kEdge.m_aiV[i];
        int iVKeep = kEdge.m_aiV[1-i];
        if ( !CollapseCausesFolding(iVKeep,iVThrow) )
        {
            Remove();
            CollapseEdge(iVKeep,iVThrow);
            return;
        }
    }

    // edge not collapsible, assign it infinite weight and update the heap
    Update(0,FLT_MAX);
}
//----------------------------------------------------------------------------
bool CreateClodMesh::CollapseCausesFolding (int iVKeep, int iVThrow)
{
    MVIter pkVT = m_kVMap.find(iVThrow);
    assert( pkVT != m_kVMap.end() );

    Edge kCollapse(iVKeep,iVThrow);
    for (int j = 0; j < pkVT->second.m_kTSet.GetSize(); j++)
    {
        Triangle kT = pkVT->second.m_kTSet[j];
        if ( kCollapse == Edge(kT.m_aiV[0],kT.m_aiV[1])
        ||   kCollapse == Edge(kT.m_aiV[1],kT.m_aiV[2])
        ||   kCollapse == Edge(kT.m_aiV[2],kT.m_aiV[0]) )
        {
            // This triangle would be removed in a collapse, so it does not
            // contribute to any folding.
            continue;
        }

        for (int i = 0; i < 3; i++)
        {
            if ( kT.m_aiV[i] == iVThrow )
            {
                // Test if potential replacement triangle (either ordering)
                // is in the mesh.
                int iV0 = iVKeep;
                int iV1 = kT.m_aiV[(i+1)%3];
                int iV2 = kT.m_aiV[(i+2)%3];

                if ( m_kTMap.find(Triangle(iV0,iV1,iV2)) != m_kTMap.end()
                ||   m_kTMap.find(Triangle(iV0,iV2,iV1)) != m_kTMap.end() )
                {
                    return true;
                }
            }
        }
    }

    return false;
}
//----------------------------------------------------------------------------
float CreateClodMesh::GetMetric (MEIter pkE)
{
    const float fLengthWeight = 10.0f;
    const float fAngleWeight = 1.0f;

    // Compute the metric for the edge.  Only manifold edges (exactly two
    // triangles sharing the edge) are allowed to collapse.
    if ( pkE->second.m_kTSet.GetSize() == 2 )
    {
        // length contribution
        Vector3f& rkEnd0 = m_akVertex[pkE->first.m_aiV[0]];
        Vector3f& rkEnd1 = m_akVertex[pkE->first.m_aiV[1]];
        Vector3f kDiff = rkEnd1 - rkEnd0;
        float fMetric = fLengthWeight*kDiff.Length();

        // angle/area contribution
        Triangle kT = pkE->second.m_kTSet[0];
        Vector3f kV0 = m_akVertex[kT.m_aiV[0]];
        Vector3f kV1 = m_akVertex[kT.m_aiV[1]];
        Vector3f kV2 = m_akVertex[kT.m_aiV[2]];
        Vector3f kE0 = kV1 - kV0;
        Vector3f kE1 = kV2 - kV0;
        Vector3f kN0 = kE0.Cross(kE1);

        kT = pkE->second.m_kTSet[1];
        kV0 = m_akVertex[kT.m_aiV[0]];
        kV1 = m_akVertex[kT.m_aiV[1]];
        kV2 = m_akVertex[kT.m_aiV[2]];
        kE0 = kV1 - kV0;
        kE1 = kV2 - kV0;
        Vector3f kN1 = kE0.Cross(kE1);

        Vector3f kCross = kN0.Cross(kN1);
        fMetric += fAngleWeight*kCross.Length();

        return fMetric;
    }

    // Boundary edges (one triangle containing edge) and junction edges
    // (3 or more triangles sharing edge) are not allowed to collapse.
    return FLT_MAX;
}
//----------------------------------------------------------------------------
void CreateClodMesh::RemoveTriangle (const Triangle& rkT)
{
    // If the triangle is an original one, reorder the connectivity array so
    // that the triangle occurs at the end.
    int iTIndex = *(int*)GetData(rkT);
    if ( iTIndex >= 0 )
    {
        assert( m_iTCurrent >= 0 );
        m_aiNewConnect[3*m_iTCurrent] = m_aiConnect[3*iTIndex];
        m_aiNewConnect[3*m_iTCurrent+1] = m_aiConnect[3*iTIndex+1];
        m_aiNewConnect[3*m_iTCurrent+2] = m_aiConnect[3*iTIndex+2];
        m_iTCurrent--;
    }

    VETMesh::RemoveTriangle(rkT);
}
//----------------------------------------------------------------------------
void CreateClodMesh::ModifyTriangle (Triangle& rkT, int iVKeep, int iVThrow)
{
#ifdef _DEBUG
    int iTStart = (int)m_kTMap.size();
#endif

    // Get the index of the pre-modified triangle, then remove the triangle
    // from the mesh.
    int iTIndex = *(int*)GetData(rkT);
    VETMesh::RemoveTriangle(rkT);

    // replace 'throw' by 'keep'
    for (int i = 0; i < 3; i++)
    {
        if ( rkT.m_aiV[i] == iVThrow )
        {
            rkT.m_aiV[i] = iVKeep;
            break;
        }
    }

    // Indices on modified triangles are the same as the indices on the
    // pre-modified triangles.
    InsertTriangle(rkT);
    *(int*)GetData(rkT) = iTIndex;

#ifdef _DEBUG
    int iTFinal = (int)m_kTMap.size();
    assert( iTFinal == iTStart );
#endif
}
//----------------------------------------------------------------------------
void CreateClodMesh::CollapseEdge (int iVKeep, int iVThrow)
{
#ifdef _DEBUG
    int iVStart = (int)m_kVMap.size();
    int iTStart = (int)m_kTMap.size();
    assert( iVStart > 0 && iTStart > 0 );
#endif

    // find the edge to collapse
    Edge kCollapse(iVKeep,iVThrow);
    MEIter pkEM = m_kEMap.find(kCollapse);
    assert ( pkEM != m_kEMap.end() );

    // keep track of vertices that are deleted in the collapse
    m_kVDelete.clear();

    // Remove the collapse-edge-shared triangles.  Using a copy of the
    // triangle set from the collapse edge is required since removal of the
    // last triangle sharing the collapse edge will remove that edge from
    // the edge map, thereby invalidating any iterator that points to data
    // in the collapse edge.
    SmallSet<Triangle> kTSet = pkEM->second.m_kTSet;
    int iTDeletions = kTSet.GetSize();
    assert( iTDeletions > 0 );
    int j;
    for (j = 0; j < kTSet.GetSize(); j++)
        RemoveTriangle(kTSet[j]);

    // Replace 'throw' vertices by 'keep' vertices in the remaining triangles
    // at the 'throw' vertex.  The old triangles are removed and the modified
    // triangles are inserted.
    Triangle kT;
    MVIter pkVM = m_kVMap.find(iVThrow);
    if ( pkVM != m_kVMap.end() )
    {
        kTSet = pkVM->second.m_kTSet;
        for (j = 0; j < kTSet.GetSize(); j++)
        {
            // The explicit typecast is needed for version 2.96 of g++ that
            // ships with Red Hat Linux 7.0.  The compiler incorrectly
            // complains that *pkTS is 'const Wml::VETMesh::Triangle'
            // when in fact it is 'Wml::VETMesh::Triangle'.
            //
            // TO DO.  I removed the typecast.  Check g++ again.
            kT = kTSet[j];
            ModifyTriangle(kT,iVKeep,iVThrow);
        }
    }

    // The set of potentially modified edges consists of all those edges that
    // are shared by the triangles containing the 'keep' vertex.  Modify these
    // metrics and update the heap.
    set<Edge> kModified;
    const SmallSet<Triangle>* pkTSet = GetTriangles(iVKeep);
    if ( pkTSet )
    {
        kTSet = *pkTSet;
        for (j = 0; j < kTSet.GetSize(); j++)
        {
            kT = kTSet[j];
            kModified.insert(Edge(kT.m_aiV[0],kT.m_aiV[1]));
            kModified.insert(Edge(kT.m_aiV[1],kT.m_aiV[2]));
            kModified.insert(Edge(kT.m_aiV[2],kT.m_aiV[0]));
        }

        set<Edge>::iterator pkES;
        for (pkES = kModified.begin(); pkES != kModified.end(); pkES++)
        {
            MEIter pkEM = m_kEMap.find(*pkES);
            HeapRecord* pkRecord = (HeapRecord*)pkEM->second.m_pvData;
            float fMetric = GetMetric(pkEM);
            Update(pkRecord->m_iHIndex,fMetric);
        }
    }

#ifdef _DEBUG
    int iVFinal = (int)m_kVMap.size();
    int iVDiff = iVStart - iVFinal;
    int iTFinal = (int)m_kTMap.size();
    int iTDiff = iTStart - iTFinal;
    assert( iVDiff == (int)(m_kVDelete.size()) && iTDiff == iTDeletions );
#endif

    // save vertex reordering information
    set<int>::iterator pkVS;
    for (pkVS = m_kVDelete.begin(); pkVS != m_kVDelete.end(); pkVS++)
    {
        assert( 0 <= m_iVCurrent && m_iVCurrent < m_iVQuantity );

        int iV = *pkVS;
        assert( 0 <= iV && iV < m_iVQuantity );

        m_aiVOrdered[m_iVCurrent] = iV;
        m_aiVPermute[iV] = m_iVCurrent;
        m_iVCurrent--;
    }

    // Save the collapse information for use in constructing the final
    // collapse records for the caller of the constructor of this class.
    CollapseRecord kCR(iVKeep,iVThrow,(int)m_kVDelete.size(),iTDeletions);
    m_kEDelete.push_back(kCR);
}
//----------------------------------------------------------------------------
void CreateClodMesh::FlushVertices ()
{
    for (MVCIter pkV = m_kVMap.begin(); pkV != m_kVMap.end(); pkV++)
    {
        assert( 0 <= m_iVCurrent && m_iVCurrent < m_iVQuantity );

        int iV = pkV->first;
        assert( 0 <= iV && iV < m_iVQuantity );

        m_aiVOrdered[m_iVCurrent] = iV;
        m_aiVPermute[iV] = m_iVCurrent;
        m_iVCurrent--;
    }

    assert( m_iVCurrent == -1 );
}
//----------------------------------------------------------------------------
void CreateClodMesh::FlushTriangles ()
{
    for (MTCIter pkT = m_kTMap.begin(); pkT != m_kTMap.end(); pkT++)
    {
        assert( pkT->second.m_pvData != NULL );
        int iTIndex = *(int*)(pkT->second.m_pvData);
        if ( iTIndex >= 0 )
        {
            assert( m_iTCurrent >= 0 );
            m_aiNewConnect[3*m_iTCurrent] = m_aiConnect[3*iTIndex];
            m_aiNewConnect[3*m_iTCurrent+1] = m_aiConnect[3*iTIndex+1];
            m_aiNewConnect[3*m_iTCurrent+2] = m_aiConnect[3*iTIndex+2];
            m_iTCurrent--;
        }
    }

    assert( m_iTCurrent == -1 );
}
//----------------------------------------------------------------------------
void CreateClodMesh::Reorder ()
{
    // permute the vertices and copy to the original array
    Vector3f* akNewVertex = new Vector3f[m_iVQuantity];
    int i;
    for (i = 0; i < m_iVQuantity; i++)
        akNewVertex[i] = m_akVertex[m_aiVOrdered[i]];
    memcpy(m_akVertex,akNewVertex,m_iVQuantity*sizeof(Vector3f));
    delete[] akNewVertex;

    // permute the normal vectors (if any)