wmlconvexhull3.cpp

3D Game Engine Design Source Code非常棒

        }

        // assert( iU != iL );  the theory
        if ( iU == iL )
        {
            // Numerical round-off error causes you to get here.  P is
            // inside the hull, so just return.
            return;
        }

        // construct the counterclockwise-ordered merged-hull vertices
        vector<int> kTmpHull;
        kTmpHull.push_back(iP);
        while ( true )
        {
            kTmpHull.push_back(m_kHullP[iU]);
            if ( iU == iL )
                break;

            if ( ++iU == iSize )
                iU = 0;
        }
        assert( kTmpHull.size() > 2 );

        m_kHullP = kTmpHull;
        return;
    }

    // Hull is about to become spatial.  The current planar hull is a convex
    // polygon that must be tri-fanned to initialize the triangle mesh that
    // represents the final hull.  The triangle order is required to be
    // counterclockwise when viewed from outside the hull.  If the current
    // planar hull has N vertices, the triangle fan has N-2 triangles and
    // P forms N triangles with the planar hull edges, a total of 2*N-2
    // triangles in the initial spatial hull.
    m_iHullType = HULL_SPATIAL;

    int iSize = (int)m_kHullP.size();
    int iQ0 = m_kHullP[0];
    int iQ1 = m_kHullP[1];
    int iQ2;

    if ( fOrder > Math<Real>::EPSILON )
    {
        // insert <P,Q[0],Q[1]>
        InsertTriangle(iP,iQ0,iQ1);

        for (i = 2; i < iSize; iQ1 = iQ2, i++)
        {
            // insert <Q[0],Q[i+1],Q[i]> and <P,Q[i],Q[i+1]>
            iQ2 = m_kHullP[i];
            InsertTriangle(iQ0,iQ2,iQ1);
            InsertTriangle(iP,iQ1,iQ2);
        }

        // insert <P,Q[n-1],Q[0]>
        InsertTriangle(iP,iQ1,iQ0);
    }
    else  // fOrder < -ms_fEpsilon
    {
        // insert <P,Q[1],Q[0]>
        InsertTriangle(iP,iQ1,iQ0);

        for (i = 2; i < iSize; iQ1 = iQ2, i++)
        {
            // insert <Q[0],Q[i],Q[i+1]> and <P,Q[i+1],Q[i]>
            iQ2 = m_kHullP[i];
            InsertTriangle(iQ0,iQ1,iQ2);
            InsertTriangle(iP,iQ2,iQ1);
        }

        // insert <P,Q[0],Q[n-1]>
        InsertTriangle(iP,iQ0,iQ1);
    }
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull3<Real>::MergeSpatial (int iP)
{
    // Find the triangle that is "most visible" to P.  Just finding the first
    // visible triangle is not sufficient when floating point round-off errors
    // are present.  The most visible triangle is used to start a
    // breadth-first for the connected mesh of triangles that are visible
    // to P.
    Vector3<Real> kDiff;
    Real fOrder, fMaxOrder = (Real)0.0;
    const Triangle* pkTri;
    const Triangle* pkMaxTri = NULL;
    const ETManifoldMesh::TMap& rkTMap = m_kHullS.GetTriangles();
    ETManifoldMesh::TMap::const_iterator pkTIter;
    for (pkTIter = rkTMap.begin(); pkTIter != rkTMap.end(); pkTIter++)
    {
        pkTri = (const Triangle*)pkTIter->second;
        kDiff = m_akVertex[iP] - m_akVertex[pkTri->V[0]];
        kDiff.Normalize();
        fOrder = pkTri->Normal.Dot(kDiff);
        if ( fOrder > fMaxOrder )
        {
            // triangle is visible to P
            fMaxOrder = fOrder;
            pkMaxTri = pkTri;
        }
    }

    if ( !pkMaxTri || fMaxOrder < Math<Real>::EPSILON )
    {
        // P is inside the current hull
        return;
    }

    // Triangle pkMinTri is visible to P.  Perform a breadth-first search to
    // locate all remaining visible triangles.
    set<const Triangle*> kInterior, kBoundary;
    kInterior.insert(pkMaxTri);
    const Triangle* pkAdj;
    int i;
    for (i = 0; i < 3; i++)
    {
        pkAdj = (const Triangle*)pkMaxTri->T[i];
        assert( pkAdj );
        kBoundary.insert(pkAdj);
    }

    typename set<const Triangle*>::iterator pkIter;
    while ( kBoundary.size() > 0 )
    {
        set<const Triangle*> kExterior;

        // process boundary triangles
        for (pkIter = kBoundary.begin(); pkIter != kBoundary.end(); pkIter++)
        {
            // current boundary triangle to process
            pkTri = (const Triangle*)*pkIter;
            kDiff = m_akVertex[iP] - m_akVertex[pkTri->V[0]];
            kDiff.Normalize();
            fOrder = pkTri->Normal.Dot(kDiff);
            if ( fOrder > (Real)0.0 )
            {
                // triangle is visible to P
                kInterior.insert(pkTri);

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

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

    // locate the terminator edges
    map<int,int> kTerminator;
    int iV0, iV1;
    for (pkIter = kInterior.begin(); pkIter != kInterior.end(); pkIter++)
    {
        // get a visible triangle
        pkTri = (const Triangle*)*pkIter;

        // If an adjacent triangle is not visible, then the shared edge is a
        // terminator edge.
        for (i = 0; i < 3; i++)
        {
            pkAdj = (const Triangle*)pkTri->T[i];
            assert( pkAdj );
            if ( kInterior.find(pkAdj) == kInterior.end() )
            {
                // adjacent triangle is not visible
                iV0 = pkTri->V[i];
                iV1 = pkTri->V[(i+1)%3];
                kTerminator[iV0] = iV1;
            }
        }
    }

    // remove the visible triangles
    for (pkIter = kInterior.begin(); pkIter != kInterior.end(); pkIter++)
    {
        pkTri = (const Triangle*)*pkIter;
        bool bRemoved = m_kHullS.RemoveTriangle(pkTri->V[0],pkTri->V[1],
            pkTri->V[2]);
        assert( bRemoved );
    }

    // add new triangles formed by P and terminator edges
    int iSize = (int)kTerminator.size();
    assert( iSize >= 3 );
    map<int,int>::iterator pkE = kTerminator.begin();
    int iVStart = pkE->first;
    iV0 = iVStart;
    for (i = 0; i < iSize; i++)
    {
        iV1 = pkE->second;

        // insert <P,V0,V1>
        InsertTriangle(iP,iV0,iV1);

        pkE = kTerminator.find(iV1);
        assert( pkE != kTerminator.end() );
        iV0 = iV1;
    }
    assert( iV0 == iVStart );
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull3<Real>::InsertTriangle (int iV0, int iV1, int iV2)
{
    Triangle* pkTri = (Triangle*) m_kHullS.InsertTriangle(iV0,iV1,iV2);
    assert( pkTri );

    const Vector3<Real>& rkV0 = m_akVertex[iV0];
    const Vector3<Real>& rkV1 = m_akVertex[iV1];
    const Vector3<Real>& rkV2 = m_akVertex[iV2];
    Vector3<Real> kE1 = rkV1 - rkV0, kE2 = rkV2 - rkV0;
    pkTri->Normal = kE1.UnitCross(kE2);
}
//----------------------------------------------------------------------------
template <class Real>
ETManifoldMesh::Triangle* ConvexHull3<Real>::CreateTriangle (int iV0, int iV1,
    int iV2)
{
    return new Triangle(iV0,iV1,iV2);
}
//----------------------------------------------------------------------------

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