wmlconvexclipper.cpp

3D Game Engine Design Source Code非常棒

// Magic Software, Inc.
// http://www.magic-software.com
// http://www.wild-magic.com
// Copyright (c) 2003.  All Rights Reserved
//
// The Wild Magic Library (WML) source code is supplied under the terms of
// the license agreement http://www.magic-software.com/License/WildMagic.pdf
// and may not be copied or disclosed except in accordance with the terms of
// that agreement.

#include "WmlConvexClipper.h"
#include "WmlConvexPolyhedron3.h"
using namespace Wml;

#include <algorithm>
#include <fstream>
#include <map>
using namespace std;

//----------------------------------------------------------------------------
template <class Real>
ConvexClipper<Real>::ConvexClipper (const ConvexPolyhedron3<Real>& rkPoly,
    Real fEpsilon)
{
    m_fEpsilon = fEpsilon;

    const vector<Vector3<Real> >& rakPoint = rkPoly.GetPoints();
    int iVQuantity = rkPoly.GetVQuantity();
    m_akVertex.resize(iVQuantity);
    for (int iV = 0; iV < iVQuantity; iV++)
        m_akVertex[iV].m_kPoint = rakPoint[iV];

    int iEQuantity = rkPoly.GetEQuantity();
    m_akEdge.resize(iEQuantity);
    for (int iE = 0; iE < iEQuantity; iE++)
    {
        const MTEdge& rkE = rkPoly.GetEdge(iE);
        for (int i = 0; i < 2; i++)
        {
            m_akEdge[iE].m_aiVertex[i] = rkPoly.GetVLabel(rkE.GetVertex(i));
            m_akEdge[iE].m_aiFace[i] = rkE.GetTriangle(i);
        }
    }

    int iTQuantity = rkPoly.GetTQuantity();
    m_akFace.resize(iTQuantity);
    for (int iT = 0; iT < iTQuantity; iT++)
    {
        m_akFace[iT].m_kPlane = rkPoly.GetPlane(iT);

        const MTTriangle& rkT = rkPoly.GetTriangle(iT);
        for (int i = 0; i < 3; i++)
            m_akFace[iT].m_akEdge.insert(rkT.GetEdge(i));
    }
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexClipper<Real>::Clip (const Plane3<Real>& rkPlane)
{
    // compute signed distances from vertices to plane
    int iPositive = 0, iNegative = 0;
    for (int iV = 0; iV < (int)m_akVertex.size(); iV++)
    {
        Vertex& rkV = m_akVertex[iV];
        if ( rkV.m_bVisible )
        {
            rkV.m_fDistance = rkPlane.DistanceTo(rkV.m_kPoint);
            if ( rkV.m_fDistance >= m_fEpsilon )
            {
                iPositive++;
            }
            else if ( rkV.m_fDistance <= -m_fEpsilon )
            {
                iNegative++;
                rkV.m_bVisible = false;
            }
            else
            {
                // The point is on the plane (within floating point
                // tolerance).
                rkV.m_fDistance = (Real)0.0;
            }
        }
    }

    if ( iPositive == 0 )
    {
        // mesh is in negative half-space, fully clipped
        return Plane3<Real>::NEGATIVE_SIDE;
    }

    if ( iNegative == 0 )
    {
        // mesh is in positive half-space, fully visible
        return Plane3<Real>::POSITIVE_SIDE;
    }

    // clip the visible edges
    for (int iE = 0; iE < (int)m_akEdge.size(); iE++)
    {
        Edge& rkE = m_akEdge[iE];
        if ( rkE.m_bVisible )
        {
            int iV0 = rkE.m_aiVertex[0], iV1 = rkE.m_aiVertex[1];
            int iF0 = rkE.m_aiFace[0], iF1 = rkE.m_aiFace[1];
            Face& rkF0 = m_akFace[iF0];
            Face& rkF1 = m_akFace[iF1];
            Real fD0 = m_akVertex[iV0].m_fDistance;
            Real fD1 = m_akVertex[iV1].m_fDistance;

            if ( fD0 <= (Real)0.0 && fD1 <= (Real)0.0 )
            {
                // The edge is culled.  If the edge is exactly on the clip
                // plane, it is possible that a visible triangle shares it.
                // The edge will be re-added during the face loop.
                rkF0.m_akEdge.erase(iE);
                if ( rkF0.m_akEdge.empty() )
                    rkF0.m_bVisible = false;

                rkF1.m_akEdge.erase(iE);
                if ( rkF1.m_akEdge.empty() )
                    rkF1.m_bVisible = false;

                rkE.m_bVisible = false;
                continue;
            }

            if ( fD0 >= (Real)0.0 && fD1 >= (Real)0.0 )
            {
                // face retains the edge
                continue;
            }

            // The edge is split by the plane.  Compute the point of
            // intersection.  If the old edge is <V0,V1> and I is the
            // intersection point, the new edge is <V0,I> when d0 > 0 or
            // <I,V1> when d1 > 0.
            int iNV = (int)m_akVertex.size();
            m_akVertex.push_back(Vertex());
            Vertex& rkNV = m_akVertex[iNV];

            Vector3<Real>& rkP0 = m_akVertex[iV0].m_kPoint;
            Vector3<Real>& rkP1 = m_akVertex[iV1].m_kPoint;
            rkNV.m_kPoint = rkP0+(fD0/(fD0-fD1))*(rkP1-rkP0);

            if ( fD0 > (Real)0.0 )
                rkE.m_aiVertex[1] = iNV;
            else
                rkE.m_aiVertex[0] = iNV;
        }
    }

    // The mesh straddles the plane.  A new convex polygonal face will be
    // generated.  Add it now and insert edges when they are visited.
    int iNF = (int)m_akFace.size();
    m_akFace.push_back(Face());
    Face& rkNF = m_akFace[iNF];
    rkNF.m_kPlane = rkPlane;

    // process the faces
    for (int iF = 0; iF < iNF; iF++)
    {
        Face& rkF = m_akFace[iF];
        if ( rkF.m_bVisible )
        {
            // Determine if the face is on the negative side, the positive
            // side, or split by the clipping plane.  The m_iOccurs members
            // are set to zero to help find the end points of the polyline
            // that results from clipping a face.
            assert( rkF.m_akEdge.size() >= 2 );
            set<int>::iterator pkIter = rkF.m_akEdge.begin();
            while ( pkIter != rkF.m_akEdge.end() )
            {
                int iE = *pkIter++;
                Edge& rkE = m_akEdge[iE];
                assert( rkE.m_bVisible );
                m_akVertex[rkE.m_aiVertex[0]].m_iOccurs = 0;
                m_akVertex[rkE.m_aiVertex[1]].m_iOccurs = 0;
            }

            int iVStart, iVFinal;
            if ( GetOpenPolyline(rkF,iVStart,iVFinal) )
            {
                // polyline is open, close it up
                int iNE = (int)m_akEdge.size();
                m_akEdge.push_back(Edge());
                Edge& rkNE = m_akEdge[iNE];

                rkNE.m_aiVertex[0] = iVStart;
                rkNE.m_aiVertex[1] = iVFinal;
                rkNE.m_aiFace[0] = iF;
                rkNE.m_aiFace[1] = iNF;

                // add new edge to polygons
                rkF.m_akEdge.insert(iNE);
                rkNF.m_akEdge.insert(iNE);
            }
        }
    }

    // Process face rkNF to make sure it is a simple polygon (theoretically
    // convex, but numerically may be slightly not convex).  Floating point
    // round-off errors can cause the new face from the last loop to be
    // needle-like with a collapse of two edges into a single edge.  This
    // block guarantees the invariant "face always a simple polygon".
    PostProcess(iNF,rkNF);
    int iESize = (int)rkNF.m_akEdge.size();
    if ( iESize < 3 )
    {
        // face is completely degenerate, remove it from mesh
        m_akFace.pop_back();
    }

    return Plane3<Real>::NO_SIDE;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexClipper<Real>::PostProcess (int iNF, Face& rkNF)
{
    int i = 0, iEQuantity = (int)rkNF.m_akEdge.size();
    vector<EdgePlus> kEdges(iEQuantity);
    set<int>::iterator pkIter = rkNF.m_akEdge.begin();
    while ( pkIter != rkNF.m_akEdge.end() )
    {
        int iE = *pkIter++;
        kEdges[i++] = EdgePlus(iE,m_akEdge[iE]);
    }
    assert( i == iEQuantity );

    sort(kEdges.begin(),kEdges.end());

    // process duplicate edges
    for (int i0 = 0, i1 = 1; i1 < iEQuantity; i0 = i1++)
    {
        if ( kEdges[i0] == kEdges[i1] )
        {
            // found two equivalent edges (same vertex end points)
#ifdef _DEBUG
            int i2 = i1+1;
            if ( i2 < iEQuantity )
            {
                // Make sure an edge occurs at most twice.  If not, then
                // algorithm needs to be modified to handle it.
                assert( kEdges[i1] != kEdges[i2] );
            }
#endif
            // Edge E0 has vertices V0, V1 and faces F0, NF.  Edge E1 has
            // vertices V0, V1 and faces F1, NF.
            int iE0 = kEdges[i0].m_iE;
            int iE1 = kEdges[i1].m_iE;
            Edge& rkE0 = m_akEdge[iE0];
            Edge& rkE1 = m_akEdge[iE1];

            // remove E0 and E1 from NF
            rkNF.m_akEdge.erase(iE0);
            rkNF.m_akEdge.erase(iE1);

            // remove NF from E0
            if ( rkE0.m_aiFace[0] == iNF )
            {
                rkE0.m_aiFace[0] = rkE0.m_aiFace[1];
            }
            else
            {
                assert( rkE0.m_aiFace[1] == iNF );
            }
            rkE0.m_aiFace[1] = -1;

            // remove NF from E1
            if ( rkE1.m_aiFace[0] == iNF )
            {
                rkE1.m_aiFace[0] = rkE1.m_aiFace[1];
            }
            else
            {
                assert( rkE1.m_aiFace[1] == iNF );
            }
            rkE1.m_aiFace[1] = -1;

            // E2 is being booted from the system.  Update the face F1 that
            // shares it.  Update E1 to share F1.
            int iF1 = rkE1.m_aiFace[0];
            Face& rkF1 = m_akFace[iF1];
            rkF1.m_akEdge.erase(iE1);
            rkF1.m_akEdge.insert(iE0);
            rkE0.m_aiFace[1] = iF1;
            rkE1.m_bVisible = false;
        }
    }
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexClipper<Real>::GetOpenPolyline (Face& rkF, int& riVStart,
    int& riVFinal)
{
    // count the number of occurrences of each vertex in the polyline
    bool bOkay = true;
    set<int>::iterator pkIter = rkF.m_akEdge.begin();
    while ( pkIter != rkF.m_akEdge.end() )
    {
        int iE = *pkIter++;
        Edge& rkE = m_akEdge[iE];

        int iV0 = rkE.m_aiVertex[0];
        m_akVertex[iV0].m_iOccurs++;
        if ( m_akVertex[iV0].m_iOccurs > 2 )
            bOkay = false;