wmldelaunay2.cpp

3D Game Engine Design Source Code非常棒

        }
        else
        {
            m_iExtraTriangleQuantity++;
        }
    }
    delete[] akIndex;

    // set up extra triangle data
    m_akExtraTriangle = new Triangle[m_iExtraTriangleQuantity];
    for (i = 0, iE = 0; i < m_iTriangleQuantity; i++)
    {
        Triangle& rkTri = m_akTriangle[i];
        for (int j = 0; j < 3; j++)
        {
            if ( rkTri.m_aiAdjacent[j] == -1 )
            {
                Triangle& rkETri = m_akExtraTriangle[iE];
                int j1 = (j+1) % 3, j2 = (j+2) % 3;
                int iS0 = rkTri.m_aiVertex[j];
                int iS1 = rkTri.m_aiVertex[j1];
                rkETri.m_aiVertex[j] = iS0;
                rkETri.m_aiVertex[j1] = iS1;
                rkETri.m_aiVertex[j2] = -1;
                rkTri.m_aiAdjacent[j] = iE + m_iTriangleQuantity;
                iE++;
            }
        }
    }

ExitDelaunay:;
    delete[] aaiTmp[0];
    delete[] aaiTmp;
    delete[] aiID;
    delete[] aaiA3S[0];
    delete[] aaiA3S;
    delete[] aafCCR[0];
    delete[] aafCCR;
    delete[] akPoint;
}
//----------------------------------------------------------------------------
template <class Real>
Delaunay2<Real>::Delaunay2 (Delaunay2& rkNet)
{
    m_bOwner = false;

    m_iVertexQuantity = rkNet.m_iVertexQuantity;
    m_akVertex = rkNet.m_akVertex;
    m_fXMin = rkNet.m_fXMin;
    m_fXMax = rkNet.m_fXMax;
    m_fXRange = rkNet.m_fXRange;
    m_fYMin = rkNet.m_fYMin;
    m_fYMax = rkNet.m_fYMax;
    m_fYRange = rkNet.m_fYRange;
    m_iEdgeQuantity = rkNet.m_iEdgeQuantity;
    m_akEdge = rkNet.m_akEdge;
    m_iTriangleQuantity = rkNet.m_iTriangleQuantity;
    m_akTriangle = rkNet.m_akTriangle;
    m_iExtraTriangleQuantity = rkNet.m_iExtraTriangleQuantity;
    m_akExtraTriangle = rkNet.m_akExtraTriangle;
}
//----------------------------------------------------------------------------
template <class Real>
Delaunay2<Real>::~Delaunay2 ()
{
    if ( m_bOwner )
    {
        delete[] m_akVertex;
        delete[] m_akEdge;
        delete[] m_akTriangle;
        delete[] m_akExtraTriangle;
    }
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay2<Real>::IsOwner () const
{
    return m_bOwner;
}
//----------------------------------------------------------------------------
template <class Real>
int Delaunay2<Real>::GetVertexQuantity () const
{
    return m_iVertexQuantity;
}
//----------------------------------------------------------------------------
template <class Real>
const Vector2<Real>& Delaunay2<Real>::GetVertex (int i) const
{
    assert( 0 <= i && i < m_iVertexQuantity );
    return m_akVertex[i];
}
//----------------------------------------------------------------------------
template <class Real>
const Vector2<Real>* Delaunay2<Real>::GetVertices () const
{
    return m_akVertex;
}
//----------------------------------------------------------------------------
template <class Real>
Real Delaunay2<Real>::GetXMin () const
{
    return m_fXMin;
}
//----------------------------------------------------------------------------
template <class Real>
Real Delaunay2<Real>::GetXMax () const
{
    return m_fXMax;
}
//----------------------------------------------------------------------------
template <class Real>
Real Delaunay2<Real>::GetXRange () const
{
    return m_fXRange;
}
//----------------------------------------------------------------------------
template <class Real>
Real Delaunay2<Real>::GetYMin () const
{
    return m_fYMin;
}
//----------------------------------------------------------------------------
template <class Real>
Real Delaunay2<Real>::GetYMax () const
{
    return m_fYMax;
}
//----------------------------------------------------------------------------
template <class Real>
Real Delaunay2<Real>::GetYRange () const
{
    return m_fYRange;
}
//----------------------------------------------------------------------------
template <class Real>
int Delaunay2<Real>::GetEdgeQuantity () const
{
    return m_iEdgeQuantity;
}
//----------------------------------------------------------------------------
template <class Real>
const typename Delaunay2<Real>::Edge& Delaunay2<Real>::GetEdge (int i) const
{
    assert( 0 <= i && i < m_iEdgeQuantity );
    return m_akEdge[i];
}
//----------------------------------------------------------------------------
template <class Real>
const typename Delaunay2<Real>::Edge* Delaunay2<Real>::GetEdges () const
{
    return m_akEdge;
}
//----------------------------------------------------------------------------
template <class Real>
int Delaunay2<Real>::GetTriangleQuantity () const
{
    return m_iTriangleQuantity;
}
//----------------------------------------------------------------------------
template <class Real>
typename Delaunay2<Real>::Triangle& Delaunay2<Real>::GetTriangle (int i)
{
    assert( 0 <= i && i < m_iTriangleQuantity );
    return m_akTriangle[i];
}
//----------------------------------------------------------------------------
template <class Real>
const typename Delaunay2<Real>::Triangle&
Delaunay2<Real>::GetTriangle (int i) const
{
    assert( 0 <= i && i < m_iTriangleQuantity );
    return m_akTriangle[i];
}
//----------------------------------------------------------------------------
template <class Real>
typename Delaunay2<Real>::Triangle* Delaunay2<Real>::GetTriangles ()
{
    return m_akTriangle;
}
//----------------------------------------------------------------------------
template <class Real>
const typename Delaunay2<Real>::Triangle*
Delaunay2<Real>::GetTriangles () const
{
    return m_akTriangle;
}
//----------------------------------------------------------------------------
template <class Real>
int Delaunay2<Real>::GetExtraTriangleQuantity () const
{
    return m_iExtraTriangleQuantity;
}
//----------------------------------------------------------------------------
template <class Real>
typename Delaunay2<Real>::Triangle& Delaunay2<Real>::GetExtraTriangle (int i)
{
    assert( 0 <= i && i < m_iExtraTriangleQuantity );
    return m_akExtraTriangle[i];
}
//----------------------------------------------------------------------------
template <class Real>
const typename Delaunay2<Real>::Triangle&
Delaunay2<Real>::GetExtraTriangle (int i) const
{
    assert( 0 <= i && i < m_iExtraTriangleQuantity );
    return m_akExtraTriangle[i];
}
//----------------------------------------------------------------------------
template <class Real>
typename Delaunay2<Real>::Triangle* Delaunay2<Real>::GetExtraTriangles ()
{
    return m_akExtraTriangle;
}
//----------------------------------------------------------------------------
template <class Real>
const typename Delaunay2<Real>::Triangle*
Delaunay2<Real>::GetExtraTriangles () const
{
    return m_akExtraTriangle;
}
//----------------------------------------------------------------------------
template <class Real>
Real& Delaunay2<Real>::Epsilon ()
{
    return ms_fEpsilon;
}
//----------------------------------------------------------------------------
template <class Real>
Real& Delaunay2<Real>::Range ()
{
    return ms_fRange;
}
//----------------------------------------------------------------------------
template <class Real>
int& Delaunay2<Real>::TSize ()
{
    return ms_iTSize;
}
//----------------------------------------------------------------------------
template <class Real>
void Delaunay2<Real>::ComputeBarycenter (const Vector2<Real>& rkV0,
    const Vector2<Real>& rkV1, const Vector2<Real>& rkV2,
    const Vector2<Real>& rkP, Real afBary[3])
{
    Vector2<Real> kV02 = rkV0 - rkV2;
    Vector2<Real> kV12 = rkV1 - rkV2;
    Vector2<Real> kPV2 = rkP - rkV2;

    Real fM00 = kV02.Dot(kV02);
    Real fM01 = kV02.Dot(kV12);
    Real fM11 = kV12.Dot(kV12);
    Real fR0 = kV02.Dot(kPV2);
    Real fR1 = kV12.Dot(kPV2);
    Real fDet = fM00*fM11 - fM01*fM01;
    assert( Math<Real>::FAbs(fDet) > (Real)0.0 );
    Real fInvDet = ((Real)1.0)/fDet;

    afBary[0] = (fM11*fR0 - fM01*fR1)*fInvDet;
    afBary[1] = (fM00*fR1 - fM01*fR0)*fInvDet;
    afBary[2] = (Real)1.0 - afBary[0] - afBary[1];
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay2<Real>::InTriangle (const Vector2<Real>& rkV0,
    const Vector2<Real>& rkV1, const Vector2<Real>& rkV2,
    const Vector2<Real>& rkTest)
{
    // test against normal to first edge
    Vector2<Real> kDir = rkTest - rkV0;
    Vector2<Real> kNor(rkV0.Y() - rkV1.Y(), rkV1.X() - rkV0.X());
    if ( kDir.Dot(kNor) < -Math<Real>::EPSILON )
        return false;

    // test against normal to second edge
    kDir = rkTest - rkV1;
    kNor = Vector2<Real>(rkV1.Y() - rkV2.Y(), rkV2.X() - rkV1.X());
    if ( kDir.Dot(kNor) < -Math<Real>::EPSILON )
        return false;

    // test against normal to third edge
    kDir = rkTest - rkV2;
    kNor = Vector2<Real>(rkV2.Y() - rkV0.Y(), rkV0.X() - rkV2.X());
    if ( kDir.Dot(kNor) < -Math<Real>::EPSILON )
        return false;

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
void Delaunay2<Real>::ComputeInscribedCenter (const Vector2<Real>& rkV0,
    const Vector2<Real>& rkV1, const Vector2<Real>& rkV2,
    Vector2<Real>& rkCenter)
{
    Vector2<Real> kD10 = rkV1 - rkV0, kD20 = rkV2 - rkV0, kD21 = rkV2 - rkV1;
    Real fL10 = kD10.Length(), fL20 = kD20.Length(), fL21 = kD21.Length();
    Real fPerimeter = fL10 + fL20 + fL21;
    if ( fPerimeter > (Real)0.0 )
    {
        Real fInv = ((Real)1.0)/fPerimeter;
        fL10 *= fInv;
        fL20 *= fInv;
        fL21 *= fInv;
    }

    rkCenter = fL21*rkV0 + fL20*rkV1 + fL10*rkV2;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// explicit instantiation
//----------------------------------------------------------------------------
namespace Wml
{
template class WML_ITEM Delaunay2<float>;
float Delaunay2f::ms_fEpsilon = 0.00001f;
float Delaunay2f::ms_fRange = 10.0f;
int Delaunay2f::ms_iTSize = 75;

template class WML_ITEM Delaunay2<double>;
double Delaunay2d::ms_fEpsilon = 0.00001;
double Delaunay2d::ms_fRange = 10.0;
int Delaunay2d::ms_iTSize = 75;
}
//----------------------------------------------------------------------------