wmlconvexpolygon2.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 "WmlConvexPolygon2.h"
using namespace Wml;

#include <fstream>
using namespace std;

//----------------------------------------------------------------------------
template <class Real>
ConvexPolygon2<Real>::ConvexPolygon2 ()
{
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolygon2<Real>::ConvexPolygon2 (const VArray& rakPoint)
{
    Create(rakPoint);
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolygon2<Real>::ConvexPolygon2 (const VArray& rakPoint,
    const LArray& rakLine)
{
    Create(rakPoint,rakLine);
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolygon2<Real>::ConvexPolygon2 (const ConvexPolygon2& rkPoly)
    :
    m_akPoint(rkPoly.m_akPoint),
    m_akLine(rkPoly.m_akLine)
{
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolygon2<Real>::Create (const VArray& rakPoint)
{
    assert( rakPoint.size() >= 3 );
    m_akPoint = rakPoint;
    UpdateLines();
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolygon2<Real>::Create (const VArray& rakPoint,
    const LArray& rakLine)
{
    assert( rakPoint.size() >= 3 );
    m_akPoint = rakPoint;
    m_akLine = rakLine;
    ComputeCentroid();
}
//----------------------------------------------------------------------------
template <class Real>
const typename ConvexPolygon2<Real>::VArray&
ConvexPolygon2<Real>::GetPoints () const
{
    return m_akPoint;
}
//----------------------------------------------------------------------------
template <class Real>
const Vector2<Real>& ConvexPolygon2<Real>::GetPoint (int iV) const
{
    assert( 0 <= iV && iV < (int)m_akPoint.size() );
    return m_akPoint[iV];
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexPolygon2<Real>::AddPoint (const Vector2<Real>& rkPoint)
{
    int iLocation = (int)m_akPoint.size();
    m_akPoint.push_back(rkPoint);
    return iLocation;
}
//----------------------------------------------------------------------------
template <class Real>
typename ConvexPolygon2<Real>::VArray& ConvexPolygon2<Real>::Points ()
{
    return m_akPoint;
}
//----------------------------------------------------------------------------
template <class Real>
Vector2<Real>& ConvexPolygon2<Real>::Point (int iV)
{
    assert( 0 <= iV && iV < (int)m_akPoint.size() );
    return m_akPoint[iV];
}
//----------------------------------------------------------------------------
template <class Real>
const typename ConvexPolygon2<Real>::LArray&
ConvexPolygon2<Real>::GetLines () const
{
    return m_akLine;
}
//----------------------------------------------------------------------------
template <class Real>
const Line2<Real>& ConvexPolygon2<Real>::GetLine (int iT) const
{
    assert( 0 <= iT && iT < (int)m_akLine.size() );
    return m_akLine[iT];
}
//----------------------------------------------------------------------------
template <class Real>
const Vector2<Real>& ConvexPolygon2<Real>::GetCentroid () const
{
    return m_kCentroid;
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolygon2<Real>& ConvexPolygon2<Real>::operator= (
    const ConvexPolygon2& rkPoly)
{
    m_akPoint = rkPoly.m_akPoint;
    m_akLine = rkPoly.m_akLine;
    m_kCentroid = rkPoly.m_kCentroid;
    return *this;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolygon2<Real>::UpdateLines ()
{
    m_akLine.resize(m_akPoint.size());
    ComputeCentroid();

    // compute lines with inner pointing normals
    int iQuantity = (int)m_akPoint.size();
    for (int i0 = iQuantity-1, i1 = 0; i1 < iQuantity; i0 = i1++)
    {
        Vector2<Real> kDiff = m_kCentroid - m_akPoint[i0];
        Vector2<Real> kDir = m_akPoint[i1] - m_akPoint[i0];

        Real fKross = kDir.Kross(kDiff);
        if ( fKross > (Real)0.0 )
            m_akLine[i1].Normal() = -kDir.Perp();
        else
            m_akLine[i1].Normal() = kDir.Perp();

        m_akLine[i1].Normal().Normalize();
        m_akLine[i1].Constant() = m_akPoint[i0].Dot(m_akLine[i1].Normal());
    }
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolygon2<Real>::ValidateHalfSpaceProperty (Real fThreshold) const
{
    Real fMax = -Math<Real>::MAX_REAL, fMin = Math<Real>::MAX_REAL;
    for (int j = 0; j < (int)m_akLine.size(); j++)
    {
        const Line2<Real>& rkLine = m_akLine[j];
        for (int i = 0; i < (int)m_akPoint.size(); i++)
        {
            Real fDistance = rkLine.GetPseudodistance(m_akPoint[i]);
            if ( fDistance < fMin )
                fMin = fDistance;
            if ( fDistance > fMax )
                fMax = fDistance;
            if ( fDistance < fThreshold )
                return false;
        }
    }

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolygon2<Real>::ComputeCentroid ()
{
    m_kCentroid = Vector2<Real>::ZERO;
    for (int i = 0; i < (int)m_akPoint.size(); i++)
        m_kCentroid += m_akPoint[i];
    m_kCentroid /= (Real)m_akPoint.size();
}
//----------------------------------------------------------------------------
template <class Real>
Real ConvexPolygon2<Real>::GetPerimeterLength () const
{
    Real fLength = (Real)0.0;
    int iQuantity = (int)m_akPoint.size();
    for (int i0 = iQuantity-1, i1 = 0; i1 < iQuantity; i0 = i1++)
    {
        Vector2<Real> kDir = m_akPoint[i1] - m_akPoint[i0];
        fLength += kDir.Length();
    }
    return fLength;
}
//----------------------------------------------------------------------------
template <class Real>
Real ConvexPolygon2<Real>::GetArea () const
{
    int iQuantity = (int)m_akPoint.size();
    int iQm1 = iQuantity-1;
    Real fArea = m_akPoint[iQm1].X()*(m_akPoint[0].Y() -
        m_akPoint[iQm1-1].Y());
    for (int i0 = iQm1, i1 = 0, i2 = 1; i1 < iQm1; i0 = i1, i1 = i2++)
        fArea += m_akPoint[i1].X()*(m_akPoint[i2].Y() - m_akPoint[i0].Y());
    fArea *= (Real)0.5;
    return fArea;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolygon2<Real>::ContainsPoint (const Vector2<Real>& rkP) const
{
    for (int i = 0; i < (int)m_akLine.size(); i++)
    {
        Real fDistance = m_akLine[i].GetPseudodistance(rkP);
        if ( fDistance < (Real)0.0 )
            return false;
    }
    return true;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolygon2<Real>::CreateEggShape (const Vector2<Real>& rkCenter,
    Real fX0, Real fX1, Real fY0, Real fY1, int iMaxSteps,
    ConvexPolygon2& rkEgg)
{
    assert( fX0 > (Real)0.0 && fX1 > (Real)0.0 );
    assert( fY0 > (Real)0.0 && fY1 > (Real)0.0 );
    assert( 0 <= iMaxSteps && iMaxSteps < 16 );

    // Start with a quadrilateral whose 4 vertices are (-x0,0), (x1,0),
    // (0,-y0), (0,y1).  The egg has 4*2^s vertices where s is the number of
    // steps.  Store the initial vertices at indices 0, 2^s, 2*s^2, 3*2^s to
    // allow subdivision in-place.
    int iStride = (1 << iMaxSteps);
    int iQuantity = 4*iStride;
    VArray akPoint(iQuantity);
    akPoint[0] = Vector2<Real>(fX1,(Real)0.0);
    akPoint[iStride] = Vector2<Real>((Real)0.0,fY1);
    akPoint[2*iStride] = Vector2<Real>(-fX0,(Real)0.0);
    akPoint[3*iStride] = Vector2<Real>((Real)0.0,-fY0);

    // subdivide the edges
    for (int iStep = 1; iStep <= iMaxSteps; iStep++, iStride >>= 1)
    {
        for (int i0 = 0, i1 = iStride; i0 < iQuantity; i0 = i1, i1 += iStride)
        {
            Vector2<Real>& rkSub = akPoint[(i0+i1)/2];
            if ( i1 < iQuantity )
                rkSub = akPoint[i0] + akPoint[i1];
            else
                rkSub = akPoint[i0] + akPoint[0];
            Real fXR = (rkSub.X() > (Real)0.0 ? rkSub.X()/fX1 :
                rkSub.X()/fX0);
            Real fYR = (rkSub.Y() > (Real)0.0 ? rkSub.Y()/fY1 :
                rkSub.Y()/fY0);
            rkSub *= Math<Real>::InvSqrt(fXR*fXR+fYR*fYR);
        }
    }

    // translate egg to the appropriate center
    for (int i = 0; i < (int)akPoint.size(); i++)
        akPoint[i] += rkCenter;

    rkEgg.Create(akPoint);
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolygon2<Real>::Print (ofstream& rkOStr) const
{
    int i;
    char acMsg[512];

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

    rkOStr << "lines:" << endl;
    for (i = 0; i < (int)m_akLine.size(); i++)
    {
        const Line2<Real>& rkL = m_akLine[i];
        sprintf(acMsg,"line<%d> = (%+8.6f,%+8.6f;%+8.4f)",i,rkL.Normal().X(),
            rkL.Normal().Y(),rkL.Constant());
        rkOStr << acMsg << endl;
    }
    rkOStr << endl;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolygon2<Real>::Print (const char* acFilename) const
{
    ofstream kOStr(acFilename);
    if ( !kOStr )
        return false;

    Print(kOStr);
    return true;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolygon2<Real>::Clip (const Line2<Real>& rkLine,
    ConvexPolygon2& rkIntr) const
{
    // compute signed distances from vertices to line
    const Real fEpsilon = (Real)1e-05;
    int iQuantity = (int)m_akPoint.size();
    Real* afDistance = new Real[iQuantity];
    int iPositive = 0, iNegative = 0, iPIndex = -1;
    for (int i = 0; i < iQuantity; i++)