mgctrianglenetwork.cpp

《3D游戏引擎设计》的源码

                }
            }

            fTmp = aafWork[0][0]*aafWork[1][1] - aafWork[0][1]*aafWork[1][0];
            if ( MgcMath::Abs(fTmp) > ms_fEpsilon*fMaxRangeSqr )
                m_iTriangleQuantity++;
        }
    }

    // create the triangles
    m_akTriangle = new Triangle[m_iTriangleQuantity];
    m_iTriangleQuantity = 0;
    i0 = -1;
    for (i11 = 0; i11 < iTriangleQuantity; i11++)
    {  
        i0++;
        while ( aaiA3S[i0][0] < 0 ) 
            i0++;
        if ( aaiA3S[i0][0] < m_iVertexQuantity )
        {  
            for (i1 = 0; i1 < 2; i1++)
            {
                for (i2 = 0; i2 < 2; i2++)
                {
                    aafWork[i2][i1] = akPoint[aaiA3S[i0][i1]][i2] -
                        akPoint[aaiA3S[i0][2]][i2];
                }
            }

            fTmp = aafWork[0][0]*aafWork[1][1] - aafWork[0][1]*aafWork[1][0];
            if ( fabs(fTmp) > ms_fEpsilon*fMaxRangeSqr )
            {  
                int iDelta = fTmp < 0 ? 1 : 0;
                Triangle& rkTri = m_akTriangle[m_iTriangleQuantity];
                rkTri.m_aiVertex[0] = aaiA3S[i0][0];
                rkTri.m_aiVertex[1] = aaiA3S[i0][1+iDelta];
                rkTri.m_aiVertex[2] = aaiA3S[i0][2-iDelta];
                rkTri.m_aiAdjacent[0] = -1;
                rkTri.m_aiAdjacent[1] = -1;
                rkTri.m_aiAdjacent[2] = -1;
                m_iTriangleQuantity++;
            }
        }
    }

    // build edge table
    m_iEdgeQuantity = 0;
    m_akEdge = new Edge[3*m_iTriangleQuantity];
    akIndex = new _Index[3*m_iTriangleQuantity];

    int j, j0, j1;
    for (i = 0; i < m_iTriangleQuantity; i++)
    {
        Triangle& rkTri = m_akTriangle[i];

        for (j0 = 0, j1 = 1; j0 < 3; j0++, j1 = (j1+1)%3)
        {
            for (j = 0; j < m_iEdgeQuantity; j++)
            {
                Edge& rkEdge = m_akEdge[j];
                if ( (rkTri.m_aiVertex[j0] == rkEdge.m_aiVertex[0] 
                   && rkTri.m_aiVertex[j1] == rkEdge.m_aiVertex[1])
                ||   (rkTri.m_aiVertex[j0] == rkEdge.m_aiVertex[1] 
                   && rkTri.m_aiVertex[j1] == rkEdge.m_aiVertex[0]) )
                {
                    break;
                }
            }
            if ( j == m_iEdgeQuantity )  // add edge to table
            {
                m_akEdge[j].m_aiVertex[0] = rkTri.m_aiVertex[j0];
                m_akEdge[j].m_aiVertex[1] = rkTri.m_aiVertex[j1];
                m_akEdge[j].m_aiTriangle[0] = i;
                akIndex[j][0] = j0;
                m_akEdge[j].m_aiTriangle[1] = -1;
                m_iEdgeQuantity++;
            }
            else  // edge already exists, add triangle to table
            {
                m_akEdge[j].m_aiTriangle[1] = i;
                akIndex[j][1] = j0;
            }
        }
    }

    // count boundary edges (the convex hull of the points)
    // and establish links between adjacent triangles
    m_iExtraTriangleQuantity = 0;
    for (i = 0; i < m_iEdgeQuantity; i++)
    {
        if ( m_akEdge[i].m_aiTriangle[1] != -1 )
        {
            j0 = m_akEdge[i].m_aiTriangle[0];
            j1 = m_akEdge[i].m_aiTriangle[1];
            m_akTriangle[j0].m_aiAdjacent[akIndex[i][0]] = j1;
            m_akTriangle[j1].m_aiAdjacent[akIndex[i][1]] = j0;
        }
        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;
}
//----------------------------------------------------------------------------
MgcTriangleNetwork::MgcTriangleNetwork (MgcTriangleNetwork& 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;
}
//----------------------------------------------------------------------------
MgcTriangleNetwork::~MgcTriangleNetwork ()
{
    if ( m_bOwner )
    {
        delete[] m_akVertex;
        delete[] m_akEdge;
        delete[] m_akTriangle;
        delete[] m_akExtraTriangle;
    }
}
//----------------------------------------------------------------------------
void MgcTriangleNetwork::ComputeBarycenter (const MgcVector2& rkV0,
    const MgcVector2& rkV1, const MgcVector2& rkV2, const MgcVector2& rkP,
    MgcReal afBary[3])
{
    MgcVector2 kV02 = rkV0 - rkV2;
    MgcVector2 kV12 = rkV1 - rkV2;
    MgcVector2 kPV2 = rkP - rkV2;

    MgcReal fM00 = kV02.Dot(kV02);
    MgcReal fM01 = kV02.Dot(kV12);
    MgcReal fM11 = kV12.Dot(kV12);
    MgcReal fR0 = kV02.Dot(kPV2);
    MgcReal fR1 = kV12.Dot(kPV2);
    MgcReal fDet = fM00*fM11 - fM01*fM01;
    assert( MgcMath::Abs(fDet) > 0.0 );
    MgcReal fInvDet = 1.0/fDet;

    afBary[0] = (fM11*fR0 - fM01*fR1)*fInvDet;
    afBary[1] = (fM00*fR1 - fM01*fR0)*fInvDet;
    afBary[2] = 1.0 - afBary[0] - afBary[1];
}
//----------------------------------------------------------------------------
bool MgcTriangleNetwork::InTriangle (const MgcVector2& rkV0,
    const MgcVector2& rkV1, const MgcVector2& rkV2, const MgcVector2& rkTest)
{
    const MgcReal fEpsilon = 1e-06;

    // test against normal to first edge
    MgcVector2 kDir = rkTest - rkV0;
    MgcVector2 kNor(rkV0.y - rkV1.y, rkV1.x - rkV0.x);
    if ( kDir.Dot(kNor) < -fEpsilon )
        return false;

    // test against normal to second edge
    kDir = rkTest - rkV1;
    kNor = MgcVector2(rkV1.y - rkV2.y, rkV2.x - rkV1.x);
    if ( kDir.Dot(kNor) < -fEpsilon )
        return false;

    // test against normal to third edge
    kDir = rkTest - rkV2;
    kNor = MgcVector2(rkV2.y - rkV0.y, rkV0.x - rkV2.x);
    if ( kDir.Dot(kNor) < -fEpsilon )
        return false;

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

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