wmlconvexpolyhedron3.cpp

3D Game Engine Design Source Code非常棒

    if ( rafDistance[iT] == Math<Real>::MAX_REAL )
    {
        rafDistance[iT] = -m_akPlane[iT].DistanceTo(rkEye);

        if ( Math<Real>::FAbs(rafDistance[iT]) < Math<Real>::EPSILON )
            rafDistance[iT] = (Real)0.0;
    }

    return rafDistance[iT];
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::IsNegativeProduct (Real fDist0, Real fDist1)
{
    return (fDist0 != (Real)0.0 ? (fDist0*fDist1 <= (Real)0.0) :
        (fDist1 != (Real)0.0));
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::ComputeTerminator (const Vector3<Real>& rkEye,
    V3Array& rkTerminator)
{
    // temporary storage for signed distances from eye to triangles
    int iTQuantity = m_akTriangle.GetQuantity();
    vector<Real> afDistance(iTQuantity);
    int i, j;
    for (i = 0; i < iTQuantity; i++)
        afDistance[i] = Math<Real>::MAX_REAL;

    // Start a search for a front-facing triangle that has an adjacent
    // back-facing triangle or for a back-facing triangle that has an
    // adjacent front-facing triangle.
    int iTCurrent = 0;
    MTTriangle* pkTCurrent = &m_akTriangle[iTCurrent];
    Real fTriDist = GetDistance(rkEye,iTCurrent,afDistance);
    int iEFirst = -1;
    for (i = 0; i < iTQuantity; i++)
    {
        // Check adjacent neighbors for edge of terminator.  Such an
        // edge occurs if the signed distance changes sign.
        int iMinIndex = -1;
        Real fMinAbsDist = Math<Real>::MAX_REAL;
        Real afAdjDist[3];
        for (j = 0; j < 3; j++)
        {
            afAdjDist[j] = GetDistance(rkEye,pkTCurrent->Adjacent(j),
                afDistance);
            if ( IsNegativeProduct(fTriDist,afAdjDist[j]) )
            {
                iEFirst = pkTCurrent->Edge(j);
                break;
            }

            Real fAbsDist = Math<Real>::FAbs(afAdjDist[j]);
            if ( fAbsDist < fMinAbsDist )
            {
                fMinAbsDist = fAbsDist;
                iMinIndex = j;
            }
        }
        if ( j < 3 )
            break;

        // First edge not found during this iteration.  Move to adjacent
        // triangle whose distance is smallest of all adjacent triangles.
        iTCurrent = pkTCurrent->Adjacent(iMinIndex);
        pkTCurrent = &m_akTriangle[iTCurrent];
        fTriDist = afAdjDist[iMinIndex];
    }
    assert( i < iTQuantity );

    MTEdge& rkEFirst = m_akEdge[iEFirst];
    rkTerminator.push_back(m_akPoint[GetVLabel(rkEFirst.Vertex(0))]);
    rkTerminator.push_back(m_akPoint[GetVLabel(rkEFirst.Vertex(1))]);

    // walk along the terminator
    int iVFirst = rkEFirst.Vertex(0);
    int iV = rkEFirst.Vertex(1);
    int iE = iEFirst;
    int iEQuantity = m_akEdge.GetQuantity();
    for (i = 0; i < iEQuantity; i++)
    {
        // search all edges sharing the vertex for another terminator edge
        int j, jMax = m_akVertex[iV].GetEdgeQuantity();
        for (j = 0; j < m_akVertex[iV].GetEdgeQuantity(); j++)
        {
            int iENext = m_akVertex[iV].GetEdge(j);
            if ( iENext == iE )
                continue;

            Real fDist0 = GetDistance(rkEye,m_akEdge[iENext].GetTriangle(0),
                afDistance);
            Real fDist1 = GetDistance(rkEye,m_akEdge[iENext].GetTriangle(1),
                afDistance);
            if ( IsNegativeProduct(fDist0,fDist1) )
            {
                if ( m_akEdge[iENext].GetVertex(0) == iV )
                {
                    iV = m_akEdge[iENext].GetVertex(1);
                    rkTerminator.push_back(m_akPoint[GetVLabel(iV)]);
                    if ( iV == iVFirst )
                        return;
                }
                else
                {
                    iV = m_akEdge[iENext].GetVertex(0);
                    rkTerminator.push_back(m_akPoint[GetVLabel(iV)]);
                    if ( iV == iVFirst )
                        return;
                }

                iE = iENext;
                break;
            }
        }
        assert( j < jMax );
    }
    assert( i < iEQuantity );
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::ComputeSilhouette (const Vector3<Real>& rkEye,
    const Plane3<Real>& rkPlane, const Vector3<Real>& rkU,
    const Vector3<Real>& rkV, V2Array& rkSilhouette)
{
    V3Array kTerminator;
    ComputeTerminator(rkEye,kTerminator);
    return ComputeSilhouette(kTerminator,rkEye,rkPlane,rkU,rkV,rkSilhouette);
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::ComputeSilhouette (V3Array& rkTerminator,
    const Vector3<Real>& rkEye, const Plane3<Real>& rkPlane,
    const Vector3<Real>& rkU, const Vector3<Real>& rkV,
    V2Array& rkSilhouette)
{
    Real fEDist = rkPlane.DistanceTo(rkEye);  // assert:  fEDist > 0

    // closest planar point to E is K = E-dist*N
    Vector3<Real> kClosest = rkEye - fEDist*rkPlane.GetNormal();

    // project polyhedron points onto plane
    for (int i = 0; i < (int)rkTerminator.size(); i++)
    {
        Vector3<Real>& rkPoint = rkTerminator[i];

        Real fVDist = rkPlane.DistanceTo(rkPoint);
        if ( fVDist >= fEDist )
        {
            // cannot project vertex onto plane
            return false;
        }

        // compute projected point Q
        Real fRatio = fEDist/(fEDist-fVDist);
        Vector3<Real> kProjected = rkEye + fRatio*(rkPoint - rkEye);

        // compute (x,y) so that Q = K+x*U+y*V+z*N
        Vector3<Real> kDiff = kProjected - kClosest;
        rkSilhouette.push_back(Vector2<Real>(rkU.Dot(kDiff),rkV.Dot(kDiff)));
    }

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::CreateEggShape (const Vector3<Real>& rkCenter,
    Real fX0, Real fX1, Real fY0, Real fY1, Real fZ0, Real fZ1,
    int iMaxSteps, ConvexPolyhedron3& rkEgg)
{
    assert( fX0 > (Real)0.0 && fX1 > (Real)0.0 );
    assert( fY0 > (Real)0.0 && fY1 > (Real)0.0 );
    assert( fZ0 > (Real)0.0 && fZ1 > (Real)0.0 );
    assert( iMaxSteps >= 0 );

    // Start with an octahedron whose 6 vertices are (-x0,0,0), (x1,0,0),
    // (0,-y0,0), (0,y1,0), (0,0,-z0), (0,0,z1).  The center point will be
    // added later.
    V3Array akPoint(6);
    akPoint[0] = Vector3<Real>(-fX0,(Real)0.0,(Real)0.0);
    akPoint[1] = Vector3<Real>(fX1,(Real)0.0,(Real)0.0);
    akPoint[2] = Vector3<Real>((Real)0.0,-fY0,(Real)0.0);
    akPoint[3] = Vector3<Real>((Real)0.0,fY1,(Real)0.0);
    akPoint[4] = Vector3<Real>((Real)0.0,(Real)0.0,-fZ0);
    akPoint[5] = Vector3<Real>((Real)0.0,(Real)0.0,fZ1);

    IArray aiConnect(24);
    aiConnect[ 0] = 1;  aiConnect[ 1] = 3;  aiConnect[ 2] = 5;
    aiConnect[ 3] = 3;  aiConnect[ 4] = 0;  aiConnect[ 5] = 5;
    aiConnect[ 6] = 0;  aiConnect[ 7] = 2;  aiConnect[ 8] = 5;
    aiConnect[ 9] = 2;  aiConnect[10] = 1;  aiConnect[11] = 5;
    aiConnect[12] = 3;  aiConnect[13] = 1;  aiConnect[14] = 4;
    aiConnect[15] = 0;  aiConnect[16] = 3;  aiConnect[17] = 4;
    aiConnect[18] = 2;  aiConnect[19] = 0;  aiConnect[20] = 4;
    aiConnect[21] = 1;  aiConnect[22] = 2;  aiConnect[23] = 4;

    rkEgg.InitialELabel() = 0;
    rkEgg.Create(akPoint,aiConnect);

    // Subdivide the triangles.  The midpoints of the edges are computed.
    // The triangle is replaced by four sub triangles using the original 3
    // vertices and the 3 new edge midpoints.

    int i;
    for (int iStep = 1; iStep <= iMaxSteps; iStep++)
    {
        int iVQuantity = rkEgg.GetVQuantity();
        int iEQuantity = rkEgg.GetEQuantity();
        int iTQuantity = rkEgg.GetTQuantity();

        // compute lifted edge midpoints
        for (i = 0; i < iEQuantity; i++)
        {
            // get edge
            const MTEdge& rkE = rkEgg.GetEdge(i);
            int iV0 = rkEgg.GetVLabel(rkE.GetVertex(0));
            int iV1 = rkEgg.GetVLabel(rkE.GetVertex(1));

            // compute "lifted" centroid to points
            Vector3<Real> kCen = rkEgg.Point(iV0)+rkEgg.Point(iV1);
            Real fXR = (kCen.X() > (Real)0.0 ? kCen.X()/fX1 : kCen.X()/fX0);
            Real fYR = (kCen.Y() > (Real)0.0 ? kCen.Y()/fY1 : kCen.Y()/fY0);
            Real fZR = (kCen.Z() > (Real)0.0 ? kCen.Z()/fZ1 : kCen.Z()/fZ0);
            kCen *= Math<Real>::InvSqrt(fXR*fXR+fYR*fYR+fZR*fZR);

            // Add the point to the array.  Store the point index in the edge
            // label for support in adding new triangles.
            rkEgg.ELabel(i) = iVQuantity++;
            rkEgg.AddPoint(kCen);
        }

        // Add the new triangles and remove the old triangle.  The removal
        // in slot i will cause the last added triangle to be moved to that
        // slot.  This side effect will not interfere with the iteration
        // and removal of the triangles.
        for (i = 0; i < iTQuantity; i++)
        {
            const MTTriangle& rkT = rkEgg.GetTriangle(i);
            int iV0 = rkEgg.GetVLabel(rkT.GetVertex(0));
            int iV1 = rkEgg.GetVLabel(rkT.GetVertex(1));
            int iV2 = rkEgg.GetVLabel(rkT.GetVertex(2));
            int iV01 = rkEgg.GetELabel(rkT.GetEdge(0));
            int iV12 = rkEgg.GetELabel(rkT.GetEdge(1));
            int iV20 = rkEgg.GetELabel(rkT.GetEdge(2));
            rkEgg.Insert(iV0,iV01,iV20);
            rkEgg.Insert(iV01,iV1,iV12);
            rkEgg.Insert(iV20,iV12,iV2);
            rkEgg.Insert(iV01,iV12,iV20);
            rkEgg.Remove(iV0,iV1,iV2);
        }
    }

    // add center
    for (i = 0; i < (int)rkEgg.m_akPoint.size(); i++)
        rkEgg.m_akPoint[i] += rkCenter;

    rkEgg.UpdatePlanes();
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::Print (ofstream& rkOStr) const
{
    MTMesh::Print(rkOStr);

    int i;
    char acMsg[512];

    rkOStr << "points:" << endl;
    for (i = 0; i < (int)m_akPoint.size(); i++)
    {
        const Vector3<Real>& rkV = m_akPoint[i];
        sprintf(acMsg,"point<%d> = (%+8.4f,%+8.4f,%+8.4f)",i,rkV.X(),rkV.Y(),
            rkV.Z());
        rkOStr << acMsg << endl;
    }
    rkOStr << endl;

    rkOStr << "planes:" << endl;
    for (i = 0; i < (int)m_akPlane.size(); i++)
    {
        const Plane3<Real>& rkP = m_akPlane[i];
        sprintf(acMsg,"plane<%d> = (%+8.6f,%+8.6f,%+8.6f;%+8.4f)",i,
            rkP.GetNormal().X(),rkP.GetNormal().Y(),rkP.GetNormal().Z(),
            rkP.GetConstant());
        rkOStr << acMsg << endl;
    }
    rkOStr << endl;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::Print (const char* acFilename) const
{
    ofstream kOStr(acFilename);
    if ( !kOStr )
        return false;

    Print(kOStr);
    return true;
}
//----------------------------------------------------------------------------

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