wmlvetmesh.cpp

3D Game Engine Design Source Code非常棒

            const SmallSet<Triangle>& rkTSet = pkE->second.m_kTSet;
            for (int j = 0; j < rkTSet.GetSize(); j++)
            {
                const Triangle& rkTAdj = rkTSet[j];
                pkVI = kVisitedMap.find(rkTAdj);
                assert( pkVI != kVisitedMap.end() );
                if ( pkVI->second == false )
                {
                    // this adjacent triangle not yet visited
                    kStack.push(rkTAdj);
                    pkVI->second = true;
                    iTSize--;
                }
            }
        }
    }

    return iTSize == 0;
}
//----------------------------------------------------------------------------
void VETMesh::GetComponents (vector<VETMesh*>& rkComponents)
{
    // Do a depth-first search of the mesh to find connected components.
    int iTSize = (int)m_kTMap.size();
    if ( iTSize == 0 )
        return;

    // for marking visited triangles during the traversal
    map<Triangle,bool> kVisitedMap;
    MTCIter pkT;
    for (pkT = m_kTMap.begin(); pkT != m_kTMap.end(); pkT++)
        kVisitedMap.insert(make_pair(pkT->first,false));

    while ( iTSize > 0 )
    {
        // find an unvisited triangle in the mesh
        stack<Triangle> kStack;
        map<Triangle,bool>::iterator pkVI = kVisitedMap.begin();
        while ( pkVI != kVisitedMap.end() )
        {
            if ( pkVI->second == false )
            {
                kStack.push(pkVI->first);
                pkVI->second = true;
                iTSize--;
                break;
            }
            pkVI++;
        }

        // traverse the connected component of the starting triangle
        VETMesh* pkComponent = Create();
        while ( !kStack.empty() )
        {
            // start at the current triangle
            Triangle kT = kStack.top();
            kStack.pop();
            pkComponent->InsertTriangle(kT);

            for (int i = 0; i < 3; i++)
            {
                // get an edge of the current triangle
                Edge kE(kT.m_aiV[i],kT.m_aiV[(i+1)%3]);
                MECIter pkE = m_kEMap.find(kE);

                // visit each adjacent triangle
                const SmallSet<Triangle>& rkTSet = pkE->second.m_kTSet;
                for (int j = 0; j < rkTSet.GetSize(); j++)
                {
                    const Triangle& rkTAdj = rkTSet[i];
                    pkVI = kVisitedMap.find(rkTAdj);
                    assert( pkVI != kVisitedMap.end() );
                    if ( pkVI->second == false )
                    {
                        // this adjacent triangle not yet visited
                        kStack.push(rkTAdj);
                        pkVI->second = true;
                        iTSize--;
                    }
                }
            }
        }
        rkComponents.push_back(pkComponent);
    }
}
//----------------------------------------------------------------------------
void VETMesh::GetComponents (vector<int>& rkIndex, int*& raiConnect)
{
    rkIndex.clear();

    // Do a depth-first search of the mesh to find connected components.
    int iTSize = (int)m_kTMap.size();
    if ( iTSize == 0 )
    {
        raiConnect = NULL;
        return;
    }

    int iIQuantity = 3*iTSize;
    int iIndex = 0;
    raiConnect = new int[iIQuantity];

    // for marking visited triangles during the traversal
    map<Triangle,bool> kVisitedMap;
    MTCIter pkT;
    for (pkT = m_kTMap.begin(); pkT != m_kTMap.end(); pkT++)
        kVisitedMap.insert(make_pair(pkT->first,false));

    while ( iTSize > 0 )
    {
        // find an unvisited triangle in the mesh
        stack<Triangle> kStack;
        map<Triangle,bool>::iterator pkVI = kVisitedMap.begin();
        while ( pkVI != kVisitedMap.end() )
        {
            if ( pkVI->second == false )
            {
                kStack.push(pkVI->first);
                pkVI->second = true;
                iTSize--;
                break;
            }
            pkVI++;
        }

        // traverse the connected component of the starting triangle
        VETMesh* pkComponent = Create();
        while ( !kStack.empty() )
        {
            // start at the current triangle
            Triangle kT = kStack.top();
            kStack.pop();
            pkComponent->InsertTriangle(kT);

            for (int i = 0; i < 3; i++)
            {
                // get an edge of the current triangle
                Edge kE(kT.m_aiV[i],kT.m_aiV[(i+1)%3]);
                MECIter pkE = m_kEMap.find(kE);

                // visit each adjacent triangle
                const SmallSet<Triangle>& rkTSet = pkE->second.m_kTSet;
                for (int j = 0; j < rkTSet.GetSize(); j++)
                {
                    const Triangle& rkTAdj = rkTSet[i];
                    pkVI = kVisitedMap.find(rkTAdj);
                    assert( pkVI != kVisitedMap.end() );
                    if ( pkVI->second == false )
                    {
                        // this adjacent triangle not yet visited
                        kStack.push(rkTAdj);
                        pkVI->second = true;
                        iTSize--;
                    }
                }
            }
        }

        // store the connectivity information for this component
        set<Triangle> kTSet;
        pkComponent->GetTriangles(kTSet);
        delete pkComponent;

        rkIndex.push_back(iIndex);
        set<Triangle>::iterator pkTIter;
        for (pkTIter = kTSet.begin(); pkTIter != kTSet.end(); pkTIter++)
        {
            assert( iIndex+3 <= iIQuantity );
            const Triangle& rkT = *pkTIter;
            raiConnect[iIndex++] = rkT.m_aiV[0];
            raiConnect[iIndex++] = rkT.m_aiV[1];
            raiConnect[iIndex++] = rkT.m_aiV[2];
        }

    }
    
    rkIndex.push_back(iIQuantity);
}
//----------------------------------------------------------------------------
void VETMesh::RemoveComponent (int& riIQuantity, int* aiConnect)
{
    // Do a depth-first search of the mesh to find connected components.  The
    // input array is assumed to be large enough to hold the component (see
    // the comments in WmlTriangleMesh.h for RemoveComponent).
    riIQuantity = 0;

    int iTSize = (int)m_kTMap.size();
    if ( iTSize == 0 )
        return;

    // Find the connected component containing the first triangle in the mesh.
    // A set is used instead of a stack to avoid having a large-memory
    // 'visited' map.
    set<Triangle> kVisited;
    kVisited.insert(m_kTMap.begin()->first);

    // traverse the connected component
    while ( !kVisited.empty() )
    {
        // start at the current triangle
        Triangle kT = *kVisited.begin();

        // add adjacent triangles to the set for recursive processing
        for (int i = 0; i < 3; i++)
        {
            // get an edge of the current triangle
            Edge kE(kT.m_aiV[i],kT.m_aiV[(i+1)%3]);
            MECIter pkE = m_kEMap.find(kE);
            assert( pkE != m_kEMap.end() );

            // visit each adjacent triangle
            const SmallSet<Triangle>& rkTSet = pkE->second.m_kTSet;
            for (int j = 0; j < rkTSet.GetSize(); j++)
            {
                Triangle kTAdj = rkTSet[j];
                if ( kTAdj != kT )
                    kVisited.insert(kTAdj);
            }
        }

        // add triangle to connectivity array
        aiConnect[riIQuantity++] = kT.m_aiV[0];
        aiConnect[riIQuantity++] = kT.m_aiV[1];
        aiConnect[riIQuantity++] = kT.m_aiV[2];

        // remove the current triangle (visited, no longer needed)
        kVisited.erase(kT);
        RemoveTriangle(kT);
    }
}
//----------------------------------------------------------------------------
bool VETMesh::GetConsistentComponents (vector<VETMesh*>& rkComponents)
{
    if ( !IsManifold() )
        return false;

    // Do a depth-first search of the mesh to find connected components.
    int iTSize = (int)m_kTMap.size();
    if ( iTSize == 0 )
        return true;

    // for marking visited triangles during the traversal
    map<Triangle,bool> kVisitedMap;
    MTCIter pkT;
    for (pkT = m_kTMap.begin(); pkT != m_kTMap.end(); pkT++)
        kVisitedMap.insert(make_pair(pkT->first,false));

    while ( iTSize > 0 )
    {
        // Find an unvisited triangle in the mesh.  Any triangle pushed onto
        // the stack is considered to have a consistent ordering.
        stack<Triangle> kStack;
        map<Triangle,bool>::iterator pkVI = kVisitedMap.begin();
        while ( pkVI != kVisitedMap.end() )
        {
            if ( pkVI->second == false )
            {
                kStack.push(pkVI->first);
                pkVI->second = true;
                iTSize--;
                break;
            }
            pkVI++;
        }

        // traverse the connected component of the starting triangle
        VETMesh* pkComponent = Create();
        while ( !kStack.empty() )
        {
            // start at the current triangle
            Triangle kT = kStack.top();
            kStack.pop();
            pkComponent->InsertTriangle(kT);

            for (int i = 0; i < 3; i++)
            {
                // get an edge of the current triangle
                int iV0 = kT.m_aiV[i], iV1 = kT.m_aiV[(i+1)%3], iV2;
                Edge kE(iV0,iV1);
                MECIter pkE = m_kEMap.find(kE);

                int iSize = pkE->second.m_kTSet.GetSize();
                assert( iSize == 1 || iSize == 2 );  // mesh is manifold
                const Triangle* pkTAdj = &pkE->second.m_kTSet[0];
                if ( iSize == 2 )
                {
                    // get the adjacent triangle to the current one
                    if ( *pkTAdj == kT )
                        pkTAdj = &pkE->second.m_kTSet[1];

                    pkVI = kVisitedMap.find(*pkTAdj);
                    assert( pkVI != kVisitedMap.end() );
                    if ( pkVI->second == false )
                    {
                        // adjacent triangle not yet visited
                        if ((pkTAdj->m_aiV[0]==iV0 && pkTAdj->m_aiV[1]==iV1)
                        ||  (pkTAdj->m_aiV[1]==iV0 && pkTAdj->m_aiV[2]==iV1)
                        ||  (pkTAdj->m_aiV[2]==iV0 && pkTAdj->m_aiV[0]==iV1))
                        {
                            // adjacent triangle must be reordered
                            iV0 = pkTAdj->m_aiV[0];
                            iV1 = pkTAdj->m_aiV[1];
                            iV2 = pkTAdj->m_aiV[2];
                            kVisitedMap.erase(*pkTAdj);
                            RemoveTriangle(iV0,iV1,iV2);
                            InsertTriangle(iV1,iV0,iV2);
                            kVisitedMap.insert(make_pair(Triangle(iV1,iV0,
                                iV2),false));

                            // refresh the iterators since maps changed
                            pkE = m_kEMap.find(kE);
                            pkTAdj = &pkE->second.m_kTSet[0];
                            if ( *pkTAdj == kT )
                                pkTAdj = &pkE->second.m_kTSet[1];
                            pkVI = kVisitedMap.find(*pkTAdj);
                            assert( pkVI != kVisitedMap.end() );
                        }

                        kStack.push(*pkTAdj);
                        pkVI->second = true;
                        iTSize--;
                    }
                }
            }
        }
        rkComponents.push_back(pkComponent);
    }

    return true;
}
//----------------------------------------------------------------------------
VETMesh* VETMesh::GetReversedOrderMesh () const
{
    VETMesh* pkReversed = Create();

    for (MTCIter pkT = m_kTMap.begin(); pkT != m_kTMap.end(); pkT++)
    {
        pkReversed->InsertTriangle(pkT->first.m_aiV[0],pkT->first.m_aiV[2],
            pkT->first.m_aiV[1]);
    }

    return pkReversed;
}
//----------------------------------------------------------------------------
void VETMesh::GetStatistics (int& riVQuantity, int& riEQuantity,
    int& riTQuantity, float& rfAverageEdgesPerVertex,
    float& rfAverageTrianglesPerVertex, float& rfAverageTrianglesPerEdge,
    int& riMaximumEdgesPerVertex, int& riMaximumTrianglesPerVertex,
    int& riMaximumTrianglesPerEdge)
{
    riVQuantity = (int)m_kVMap.size();
    riEQuantity = (int)m_kEMap.size();
    riTQuantity = (int)m_kTMap.size();

    int iESumForV = 0;
    int iTSumForV = 0;
    riMaximumEdgesPerVertex = 0;
    riMaximumTrianglesPerVertex = 0;

    int iESize, iTSize;
    
    for (MVCIter pkV = m_kVMap.begin(); pkV != m_kVMap.end(); pkV++)
    {
        iESize = pkV->second.m_kESet.GetSize();
        iTSize = pkV->second.m_kTSet.GetSize();
        iESumForV += iESize;
        iTSumForV += iTSize;
        if ( iESize > riMaximumEdgesPerVertex )
            riMaximumEdgesPerVertex = iESize;
        if ( iTSize > riMaximumTrianglesPerVertex )
            riMaximumTrianglesPerVertex = iTSize;
    }
    
    int iTSumForE = 0;
    riMaximumTrianglesPerEdge = 0;
    for (MECIter pkE = m_kEMap.begin(); pkE != m_kEMap.end(); pkE++)
    {
        iTSize = pkE->second.m_kTSet.GetSize();
        iTSumForE += iTSize;
        if ( iTSize > riMaximumTrianglesPerEdge )
            riMaximumTrianglesPerEdge = iTSize;
    }
    
    rfAverageEdgesPerVertex = ((float)iESumForV)/riVQuantity;
    rfAverageTrianglesPerVertex = ((float)iTSumForV)/riVQuantity;
    rfAverageTrianglesPerEdge = ((float)iTSumForE)/riEQuantity;
}
//----------------------------------------------------------------------------