wmlconvexpolyhedron3.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 "WmlConvexPolyhedron3.h"
#include "WmlConvexClipper.h"
#include <fstream>
#include <map>
#include <set>
using namespace Wml;
using namespace std;

//----------------------------------------------------------------------------
template <class Real>
ConvexPolyhedron3<Real>::ConvexPolyhedron3 ()
{
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolyhedron3<Real>::ConvexPolyhedron3 (const V3Array& rakPoint,
    const IArray& raiConnect)
{
    Create(rakPoint,raiConnect);
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolyhedron3<Real>::ConvexPolyhedron3 (const V3Array& rakPoint,
    const IArray& raiConnect, const PArray& rakPlane)
{
    Create(rakPoint,raiConnect,rakPlane);
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolyhedron3<Real>::ConvexPolyhedron3 (const ConvexPolyhedron3& rkPoly)
    :
    MTMesh(rkPoly),
    m_akPoint(rkPoly.m_akPoint),
    m_akPlane(rkPoly.m_akPlane)
{
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::Create (const V3Array& rakPoint,
    const IArray& raiConnect)
{
    assert( rakPoint.size() >= 4 && raiConnect.size() >= 4 );

    int iVQuantity = (int)rakPoint.size();
    int iTQuantity = (int)raiConnect.size()/3;
    int iEQuantity = iVQuantity + iTQuantity - 2;
    Reset(iVQuantity,iEQuantity,iTQuantity);
    m_akPoint = rakPoint;

    // Copy polyhedron points into vertex array.  Compute centroid for use in
    // making sure the triangles are counterclockwise oriented when viewed
    // from the outside.
    ComputeCentroid();

    // get polyhedron edge and triangle information
    for (int iT = 0, iIndex = 0; iT < iTQuantity; iT++)
    {
        // get vertex indices for triangle
        int iV0 = raiConnect[iIndex++];
        int iV1 = raiConnect[iIndex++];
        int iV2 = raiConnect[iIndex++];

        // make sure triangle is counterclockwise
        Vector3<Real>& rkV0 = m_akPoint[iV0];
        Vector3<Real>& rkV1 = m_akPoint[iV1];
        Vector3<Real>& rkV2 = m_akPoint[iV2];

        Vector3<Real> kDiff = m_kCentroid - rkV0;
        Vector3<Real> kE1 = rkV1 - rkV0;
        Vector3<Real> kE2 = rkV2 - rkV0;
        Vector3<Real> kNormal = kE1.Cross(kE2);
        Real fLength = kNormal.Length();
        if ( fLength > Math<Real>::EPSILON )
        {
            kNormal /= fLength;
        }
        else
        {
            kNormal = kDiff;
            kNormal.Normalize();
        }

        Real fDistance = kNormal.Dot(kDiff);

        if ( fDistance < (Real)0.0 )
        {
            // triangle is counterclockwise
            Insert(iV0,iV1,iV2);
        }
        else
        {
            // triangle is clockwise
            Insert(iV0,iV2,iV1);
        }
    }

    UpdatePlanes();
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::Create (const V3Array& rakPoint,
    const IArray& raiConnect, const PArray& rakPlane)
{
    assert( rakPoint.size() >= 4 && raiConnect.size() >= 4 );

    int iVQuantity = (int)rakPoint.size();
    int iTQuantity = (int)raiConnect.size()/3;
    int iEQuantity = iVQuantity + iTQuantity - 2;
    Reset(iVQuantity,iEQuantity,iTQuantity);
    m_akPoint = rakPoint;
    m_akPlane = rakPlane;

    // Copy polyhedron points into vertex array.  Compute centroid for use in
    // making sure the triangles are counterclockwise oriented when viewed
    // from the outside.
    ComputeCentroid();

    // get polyhedron edge and triangle information
    for (int iT = 0, iIndex = 0; iT < iTQuantity; iT++)
    {
        // get vertex indices for triangle
        int iV0 = raiConnect[iIndex++];
        int iV1 = raiConnect[iIndex++];
        int iV2 = raiConnect[iIndex++];

        Real fDistance = m_akPlane[iT].DistanceTo(m_kCentroid);
        if ( fDistance > (Real)0.0 )
        {
            // triangle is counterclockwise
            Insert(iV0,iV1,iV2);
        }
        else
        {
            // triangle is clockwise
            Insert(iV0,iV2,iV1);
        }
    }
}
//----------------------------------------------------------------------------
template <class Real>
const typename ConvexPolyhedron3<Real>::V3Array&
ConvexPolyhedron3<Real>::GetPoints () const
{
    return m_akPoint;
}
//----------------------------------------------------------------------------
template <class Real>
const Vector3<Real>& ConvexPolyhedron3<Real>::GetPoint (int iV) const
{
    assert( 0 <= iV && iV < (int)m_akPoint.size() );
    return m_akPoint[iV];
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexPolyhedron3<Real>::AddPoint (const Vector3<Real>& rkPoint)
{
    int iLocation = (int)m_akPoint.size();
    m_akPoint.push_back(rkPoint);
    return iLocation;
}
//----------------------------------------------------------------------------
template <class Real>
typename ConvexPolyhedron3<Real>::V3Array& ConvexPolyhedron3<Real>::Points ()
{
    return m_akPoint;
}
//----------------------------------------------------------------------------
template <class Real>
Vector3<Real>& ConvexPolyhedron3<Real>::Point (int iV)
{
    assert( 0 <= iV && iV < (int)m_akPoint.size() );
    return m_akPoint[iV];
}
//----------------------------------------------------------------------------
template <class Real>
const typename ConvexPolyhedron3<Real>::PArray&
ConvexPolyhedron3<Real>::GetPlanes () const
{
    return m_akPlane;
}
//----------------------------------------------------------------------------
template <class Real>
const Plane3<Real>& ConvexPolyhedron3<Real>::GetPlane (int iT) const
{
    assert( 0 <= iT && iT < (int)m_akPlane.size() );
    return m_akPlane[iT];
}
//----------------------------------------------------------------------------
template <class Real>
const Vector3<Real>& ConvexPolyhedron3<Real>::GetCentroid () const
{
    return m_kCentroid;
}
//----------------------------------------------------------------------------
template <class Real>
ConvexPolyhedron3<Real>& ConvexPolyhedron3<Real>::operator= (
    const ConvexPolyhedron3& rkPoly)
{
    MTMesh::operator=(rkPoly);
    m_akPoint = rkPoly.m_akPoint;
    m_akPlane = rkPoly.m_akPlane;
    return *this;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::UpdatePlanes ()
{
    // The planes are constructed to have *inner pointing* normals.  This
    // supports my Wild Magic software clipping code that was based on a view
    // frustum having inner pointing normals.
    ComputeCentroid();
    int iTQuantity = m_akTriangle.GetQuantity();
    m_akPlane.resize(iTQuantity);
    for (int iT = 0; iT < iTQuantity; iT++)
    {
        MTTriangle& rkT = m_akTriangle[iT];
        int iV0 = GetVLabel(rkT.Vertex(0));
        int iV1 = GetVLabel(rkT.Vertex(1));
        int iV2 = GetVLabel(rkT.Vertex(2));
        Vector3<Real>& rkV0 = m_akPoint[iV0];
        Vector3<Real>& rkV1 = m_akPoint[iV1];
        Vector3<Real>& rkV2 = m_akPoint[iV2];

        Vector3<Real> kDiff = m_kCentroid - rkV0;
        Vector3<Real> kE1 = rkV1 - rkV0;
        Vector3<Real> kE2 = rkV2 - rkV0;
        Vector3<Real> kNormal = kE2.Cross(kE1);
        Real fLength = kNormal.Length();
        if ( fLength > Math<Real>::EPSILON )
        {
            kNormal /= fLength;
            Real fDot = kNormal.Dot(kDiff);
            if ( fDot < (Real)0.0 )
                kNormal = -kNormal;
        }
        else
        {
            // triangle is degenerate, use "normal" that points towards
            // centroid
            kNormal = kDiff;
            kNormal.Normalize();
        }

        // inner pointing normal
        m_akPlane[iT] = Plane3<Real>(kNormal,kNormal.Dot(rkV0));
    }
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::ValidateHalfSpaceProperty (Real fThreshold)
    const
{
    Real fMax = -Math<Real>::MAX_REAL, fMin = Math<Real>::MAX_REAL;
    for (int iT = 0; iT < m_akTriangle.GetQuantity(); iT++)
    {
        const Plane3<Real>& rkPlane = m_akPlane[iT];
        for (int i = 0; i < (int)m_akPoint.size(); i++)
        {
            Real fDistance = rkPlane.DistanceTo(m_akPoint[i]);
            if ( fDistance < fMin )
                fMin = fDistance;
            if ( fDistance > fMax )
                fMax = fDistance;
            if ( fDistance < fThreshold )
                return false;
        }
    }

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexPolyhedron3<Real>::ComputeCentroid ()
{
    m_kCentroid = Vector3<Real>::ZERO;
    for (int iV = 0; iV < (int)m_akPoint.size(); iV++)
        m_kCentroid += m_akPoint[iV];
    m_kCentroid /= (Real)m_akPoint.size();
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::Clip (const Plane3<Real>& rkPlane,
    ConvexPolyhedron3& rkIntr) const
{
    ConvexClipper<Real> kClipper(*this);
    int iSide = kClipper.Clip(rkPlane);

    if ( iSide == Plane3<Real>::POSITIVE_SIDE )
    {
        rkIntr = *this;
        return true;
    }

    if ( iSide == Plane3<Real>::NEGATIVE_SIDE )
        return false;

    kClipper.Convert(rkIntr);
    return true;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexPolyhedron3<Real>::FindIntersection (
    const ConvexPolyhedron3& rkPoly, ConvexPolyhedron3& rkIntr) const