wmldelaunay2a.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 "WmlDelaunay2a.h"
using namespace Wml;

#include <algorithm>
#include <set>
using namespace std;

//----------------------------------------------------------------------------
template <class Real>
Delaunay2a<Real>::Delaunay2a (int iVQuantity, const Vector2<Real>* akVertex,
    int& riTQuantity, int*& raiTVertex, int*& raiTAdjacent)
    :
    m_kVertex(iVQuantity)
{
    // output values
    riTQuantity = 0;
    raiTVertex = NULL;
    raiTAdjacent = NULL;

    // transform the points to [-1,1]^2 for numerical preconditioning
    Real fMin = akVertex[0].X(), fMax = fMin;
    int i;
    for (i = 0; i < iVQuantity; i++)
    {
        if ( akVertex[i].X() < fMin )
            fMin = akVertex[i].X();
        else if ( akVertex[i].X() > fMax )
            fMax = akVertex[i].X();

        if ( akVertex[i].Y() < fMin )
            fMin = akVertex[i].Y();
        else if ( akVertex[i].Y() > fMax )
            fMax = akVertex[i].Y();
    }
    Real fHalfRange = ((Real)0.5)*(fMax - fMin);
    Real fInvHalfRange = ((Real)1.0)/fHalfRange;

    // sort by x-component to prepare to remove duplicate vertices
    for (i = 0; i < iVQuantity; i++)
    {
        m_kVertex[i].m_kV.X() = -(Real)1.0 + fInvHalfRange*(akVertex[i].X() -
            fMin);
        m_kVertex[i].m_kV.Y() = -(Real)1.0 + fInvHalfRange*(akVertex[i].Y() -
            fMin);
        m_kVertex[i].m_iIndex = i;
    }
    sort(m_kVertex.begin(),m_kVertex.end());

    // remove duplicate points
    typename SVArray::iterator pkEnd =
        unique(m_kVertex.begin(),m_kVertex.end());
    m_kVertex.erase(pkEnd,m_kVertex.end());

    // construct supertriangle and add to triangle mesh
    iVQuantity = (int)m_kVertex.size();
    m_aiSuperV[0] = iVQuantity;
    m_aiSuperV[1] = iVQuantity+1;
    m_aiSuperV[2] = iVQuantity+2;
    m_kVertex.push_back(SortedVertex(Vector2<Real>(-(Real)2.0,-(Real)2.0),
        m_aiSuperV[0]));
    m_kVertex.push_back(SortedVertex(Vector2<Real>(+(Real)5.0,-(Real)2.0),
        m_aiSuperV[1]));
    m_kVertex.push_back(SortedVertex(Vector2<Real>(-(Real)2.0,+(Real)5.0),
        m_aiSuperV[2]));

    Triangle* pkTri = new Triangle(m_aiSuperV[0],m_aiSuperV[1],
        m_aiSuperV[2],NULL,NULL,NULL);
    m_kTriangle.insert(pkTri);
    m_apkSuperT[0] = pkTri;
    m_apkSuperT[1] = pkTri;
    m_apkSuperT[2] = pkTri;

    // incrementally update the triangulation
    for (i = 0; i < iVQuantity; i++)
    {
        // construct the insertion polygon
        TSet kPolyTri;
        GetInsertionPolygon(m_kVertex[i].m_kV,kPolyTri);

        EArray kPoly;
        GetInsertionPolygonEdges(kPolyTri,kPoly);

        // add new triangles formed by the point and insertion polygon edges
        AddTriangles(i,kPoly);

        // remove insertion polygon
        RemoveInsertionPolygon(kPolyTri);
    }

    // remove triangles sharing a vertex of the supertriangle
    RemoveTriangles();

    // assign integer values to the triangles for use by the caller
    map<Triangle*,int> kPermute;
    TSetIterator pkTIter = m_kTriangle.begin();
    for (i = 0; pkTIter != m_kTriangle.end(); pkTIter++)
    {
        pkTri = *pkTIter;
        kPermute[pkTri] = i++;
    }
    kPermute[NULL] = -1;

    // put Delaunay triangles into an array (vertices and adjacency info)
    riTQuantity = (int)m_kTriangle.size();
    if ( riTQuantity > 0 )
    {
        raiTVertex = new int[3*riTQuantity];
        raiTAdjacent = new int[3*riTQuantity];
        i = 0;
        pkTIter = m_kTriangle.begin();
        for (/**/; pkTIter != m_kTriangle.end(); pkTIter++)
        {
            pkTri = *pkTIter;
            raiTVertex[i] = m_kVertex[pkTri->m_aiV[0]].m_iIndex;
            raiTAdjacent[i++] = kPermute[pkTri->m_apkAdj[0]];
            raiTVertex[i] = m_kVertex[pkTri->m_aiV[1]].m_iIndex;
            raiTAdjacent[i++] = kPermute[pkTri->m_apkAdj[1]];
            raiTVertex[i] = m_kVertex[pkTri->m_aiV[2]].m_iIndex;
            raiTAdjacent[i++] = kPermute[pkTri->m_apkAdj[2]];
        }
        assert( i == 3*riTQuantity );
    }
}
//----------------------------------------------------------------------------
template <class Real>
Delaunay2a<Real>::~Delaunay2a ()
{
    TSetIterator pkTIter = m_kTriangle.begin();
    for (/**/; pkTIter != m_kTriangle.end(); pkTIter++)
        delete *pkTIter;
}
//----------------------------------------------------------------------------
template <class Real>
typename Delaunay2a<Real>::Triangle*
Delaunay2a<Real>::GetContaining (const Vector2<Real>& rkP) const
{
    // start with supertriangle <S0,S1,V>
    Triangle* pkTri = m_apkSuperT[0];
    assert( pkTri->m_aiV[0] == m_aiSuperV[0]
        &&  pkTri->m_aiV[1] == m_aiSuperV[1] );

    const Vector2<Real>& rkS1 = m_kVertex[m_aiSuperV[1]].m_kV;
    Vector2<Real> kDiff = rkP - rkS1;
    int iSIndex = 1;
    int iVIndex = 2;  // local index following that of S1

    // The search should never iterate over more than all the triangles.  But
    // just to be safe...
    for (int i = 0; i < (int)m_kTriangle.size(); i++)
    {
        // test if P is inside the triangle
        Vector2<Real> kVmS1 = m_kVertex[pkTri->m_aiV[iVIndex]].m_kV - rkS1;
        Real fKross = kVmS1.X()*kDiff.Y() - kVmS1.Y()*kDiff.X();
        if ( fKross >= (Real)0.0 )
            return pkTri;

        pkTri = pkTri->m_apkAdj[iSIndex];
        assert( pkTri );
        if ( pkTri->m_aiV[0] == m_aiSuperV[1] )
        {
            iSIndex = 0;
            iVIndex = 1;
        }
        else if ( pkTri->m_aiV[1] == m_aiSuperV[1] )
        {
            iSIndex = 1;
            iVIndex = 2;
        }
        else if ( pkTri->m_aiV[2] == m_aiSuperV[1] )
        {
            iSIndex = 2;
            iVIndex = 0;
        }
        else
        {
            assert( false );
        }
    }

    // by construction, point must be in some triangle in the mesh
    assert( false );
    return pkTri;
}
//----------------------------------------------------------------------------
template <class Real>
bool Delaunay2a<Real>::IsInsertionComponent (const Vector2<Real>& rkV,
    Triangle* pkTri) const
{
    // determine the number of vertices in common with the supertriangle
    int iCommon = 0, j = -1;
    for (int i = 0; i < 3; i++)
    {
        int iV = pkTri->m_aiV[i];
        if ( iV == m_aiSuperV[0] )
        {
            iCommon++;
            j = i;
        }
        if ( iV == m_aiSuperV[1] )
        {
            iCommon++;
            j = i;
        }
        if ( iV == m_aiSuperV[2] )
        {
            iCommon++;
            j = i;
        }
    }

    if ( iCommon == 0 )
        return pkTri->PointInCircle(rkV,m_kVertex);

    if ( iCommon == 1 )
        return pkTri->PointLeftOfEdge(rkV,m_kVertex,(j+1)%3,(j+2)%3);

    return pkTri->PointInTriangle(rkV,m_kVertex);
}
//----------------------------------------------------------------------------
template <class Real>
void Delaunay2a<Real>::GetInsertionPolygon (const Vector2<Real>& rkV,
    TSet& rkPolyTri) const
{
    // locate triangle containing input point, add to insertion polygon
    Triangle* pkTri = GetContaining(rkV);
    //assert( IsInsertionComponent(rkV,pkTri) );
    rkPolyTri.insert(pkTri);

    // breadth-first search for other triangles in the insertion polygon
    TSet kInterior, kBoundary;