wmldelaunay2a.cpp

3D Game Engine Design Source Code非常棒

    kInterior.insert(pkTri);
    Triangle* pkAdj;
    int i;
    for (i = 0; i < 3; i++)
    {
        pkAdj = pkTri->m_apkAdj[i];
        if ( pkAdj )
            kBoundary.insert(pkAdj);
    }

    while ( kBoundary.size() > 0 )
    {
        TSet kExterior;

        // process boundary triangles
        TSetIterator pkIter;
        for (pkIter = kBoundary.begin(); pkIter != kBoundary.end(); pkIter++)
        {
            // current boundary triangle to process
            pkTri = *pkIter;
            if ( IsInsertionComponent(rkV,pkTri) )
            {
                // triangle is an insertion component
                rkPolyTri.insert(pkTri);

                // locate adjacent, exterior triangles for later processing
                for (i = 0; i < 3; i++)
                {
                    pkAdj = pkTri->m_apkAdj[i];
                    if ( pkAdj
                    &&   kInterior.find(pkAdj) == kInterior.end()
                    &&   kBoundary.find(pkAdj) == kBoundary.end() )
                    {
                        kExterior.insert(pkAdj);
                    }
                }
            }
        }

        // boundary triangles processed, move them to interior
        for (pkIter = kBoundary.begin(); pkIter != kBoundary.end(); pkIter++)
            kInterior.insert(*pkIter);

        // exterior triangles are next in line to be processed
        kBoundary = kExterior;
    }

    // If the input point is outside the current convex hull, triangles
    // sharing a supertriangle edge have to be added to the insertion polygon
    // if the non-supertriangle vertex is shared by two edges that are visible
    // to the input point.
    for (i = 0; i < 3; i++)
    {
        pkTri = m_apkSuperT[i];
        if ( rkPolyTri.find(pkTri->m_apkAdj[1]) != rkPolyTri.end()
        &&   rkPolyTri.find(pkTri->m_apkAdj[2]) != rkPolyTri.end() )
        {
            rkPolyTri.insert(pkTri);
        }
    }
}
//----------------------------------------------------------------------------
template <class Real>
void Delaunay2a<Real>::GetInsertionPolygonEdges (TSet& rkPolyTri,
    EArray& rkPoly) const
{
    // locate edges of the insertion polygon
    EMap kIPolygon;
    int iV0, iV1;
    Triangle* pkTri;
    Triangle* pkAdj;
    TSetIterator pkTIter;
    for (pkTIter = rkPolyTri.begin(); pkTIter != rkPolyTri.end(); pkTIter++)
    {
        // get an insertion polygon triangle
        pkTri = *pkTIter;

        // If an adjacent triangle is not an insertion polygon triangle, then
        // the shared edge is a boundary edge of the insertion polygon.  Use
        // this edge to create a new Delaunay triangle from the input vertex
        // and the shared edge.
        for (int j = 0; j < 3; j++)
        {
            pkAdj = pkTri->m_apkAdj[j];
            if ( pkAdj )
            {
                if ( rkPolyTri.find(pkAdj) == rkPolyTri.end() )
                {
                    // adjacent triangle is not part of insertion polygon
                    iV0 = pkTri->m_aiV[j];
                    iV1 = pkTri->m_aiV[(j+1)%3];
                    kIPolygon[iV0] = Edge(iV0,iV1,pkTri,pkAdj);
                }
            }
            else
            {
                // no adjacent triangle, edge is part of insertion polygon
                iV0 = pkTri->m_aiV[j];
                iV1 = pkTri->m_aiV[(j+1)%3];
                kIPolygon[iV0] = Edge(iV0,iV1,pkTri,pkAdj);
            }
        }
    }

    // insertion polygon should be at least a triangle
    int iSize = (int)kIPolygon.size();
    assert( iSize >= 3 );

    // sort the edges
    typename EMap::iterator pkE = kIPolygon.begin();
    iV0 = pkE->second.m_iV0;
    for (int i = 0; i < iSize; i++)
    {
        iV1 = pkE->second.m_iV1;
        rkPoly.push_back(pkE->second);
        pkE = kIPolygon.find(iV1);
        assert( pkE != kIPolygon.end() );
    }
    assert( iV1 == iV0 );
}
//----------------------------------------------------------------------------
template <class Real>
void Delaunay2a<Real>::AddTriangles (int iV2, const EArray& rkPoly)
{
    // create new triangles
    int iSize = (int)rkPoly.size();
    TArray kTriangle(iSize);
    Triangle* pkTri;
    Triangle* pkAdj;
    int i, j;
    for (i = 0; i < iSize; i++)
    {
        const Edge& rkE = rkPoly[i];

        // construct new triangle
        pkTri = new Triangle(rkE.m_iV0,rkE.m_iV1,iV2,rkE.m_pkA,NULL,NULL);
        kTriangle[i] = pkTri;
        if ( rkE.m_iV0 == m_aiSuperV[0] && rkE.m_iV1 == m_aiSuperV[1] )
            m_apkSuperT[0] = pkTri;
        else if ( rkE.m_iV0 == m_aiSuperV[1] && rkE.m_iV1 == m_aiSuperV[2] )
            m_apkSuperT[1] = pkTri;
        else if ( rkE.m_iV0 == m_aiSuperV[2] && rkE.m_iV1 == m_aiSuperV[0] )
            m_apkSuperT[2] = pkTri;

        // update information of triangle adjacent to insertion polygon
        pkAdj = rkE.m_pkA;
        if ( pkAdj )
        {
            for (j = 0; j < 3; j++)
            {
                if ( pkAdj->m_apkAdj[j] == rkE.m_pkT )
                {
                    pkAdj->m_apkAdj[j] = pkTri;
                    break;
                }
            }
        }
    }

    // Insertion polygon is a star polygon with center vertex V2.  Finalize
    // the triangles by setting the adjacency information.
    for (i = 0; i < iSize; i++)
    {
        // current triangle
        pkTri = kTriangle[i];

        // connect to next new triangle
        int iNext = i+1;
        if ( iNext == iSize )
            iNext = 0;
        pkTri->m_apkAdj[1] = kTriangle[iNext];

        // connect to previous new triangle
        int iPrev = i-1;
        if ( iPrev == -1 )
            iPrev = iSize-1;
        pkTri->m_apkAdj[2] = kTriangle[iPrev];
    }

    // add the triangles to the mesh
    for (i = 0; i < iSize; i++)
        m_kTriangle.insert(kTriangle[i]);
}
//----------------------------------------------------------------------------
template <class Real>
void Delaunay2a<Real>::RemoveInsertionPolygon (TSet& rkPolyTri)
{
    TSetIterator pkTIter;
    for (pkTIter = rkPolyTri.begin(); pkTIter != rkPolyTri.end(); pkTIter++)
    {
        Triangle* pkTri = *pkTIter;
        m_kTriangle.erase(pkTri);
        delete pkTri;
    }
}
//----------------------------------------------------------------------------
template <class Real>
void Delaunay2a<Real>::RemoveTriangles ()
{
    // identify those triangles sharing a vertex of the supertriangle
    TSet kRemoveTri;
    Triangle* pkTri;
    TSetIterator pkTIter = m_kTriangle.begin();
    for (/**/; pkTIter != m_kTriangle.end(); pkTIter++)
    {
        pkTri = *pkTIter;
        for (int j = 0; j < 3; j++)
        {
            int iV = pkTri->m_aiV[j];
            if ( iV == m_aiSuperV[0]
            ||   iV == m_aiSuperV[1]
            ||   iV == m_aiSuperV[2] )
            {
                kRemoveTri.insert(pkTri);
                break;
            }
        }
    }

    // remove the triangles from the mesh
    pkTIter = kRemoveTri.begin();
    for (/**/; pkTIter != kRemoveTri.end(); pkTIter++)
    {
        pkTri = *pkTIter;
        m_kTriangle.erase(pkTri);
        delete pkTri;
    }
}
//----------------------------------------------------------------------------

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