// Wild Magic Source Code
// David Eberly
// http://www.geometrictools.com
// Copyright (c) 1998-2009
//
// This library is free software; you can redistribute it and/or modify it
// under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation; either version 2.1 of the License, or (at
// your option) any later version.  The license is available for reading at
// either of the locations:
//     http://www.gnu.org/copyleft/lgpl.html
//     http://www.geometrictools.com/License/WildMagicLicense.pdf
//
// Version: 4.0.0 (2006/06/28)

#include "VertexCollapse.h"
#include "Wm4DistVector3Segment3.h"

//----------------------------------------------------------------------------
VertexCollapse::VertexCollapse (int iVQuantity, Vector3f*& rakVertex,
    bool bClosed, int*& raiMap, int& riEQuantity, int*& raiEdge)
{
    raiMap = WM4_NEW int[iVQuantity];

    if (bClosed)
    {
        riEQuantity = iVQuantity;
        raiEdge = WM4_NEW int[2*riEQuantity];

        if (iVQuantity == 3)
        {
            raiMap[0] = 0;
            raiMap[1] = 1;
            raiMap[2] = 3;
            raiEdge[0] = 0;  raiEdge[1] = 1;
            raiEdge[2] = 1;  raiEdge[3] = 2;
            raiEdge[4] = 2;  raiEdge[5] = 0;
            return;
        }
    }
    else
    {
        riEQuantity = iVQuantity-1;
        raiEdge = WM4_NEW int[2*riEQuantity];

        if (iVQuantity == 2)
        {
            raiMap[0] = 0;
            raiMap[1] = 1;
            raiEdge[0] = 0;  raiEdge[1] = 1;
            return;
        }
    }

    // create the heap of records
    InitializeHeap(iVQuantity,rakVertex,bClosed);
    BuildHeap();
    assert( IsValid() );

    // create the level of detail information for the polyline
    int* aiCollapse = WM4_NEW int[iVQuantity];
    CollapseVertices(iVQuantity,rakVertex,aiCollapse);
    ComputeEdges(iVQuantity,bClosed,aiCollapse,raiMap,riEQuantity,raiEdge);
    ReorderVertices(iVQuantity,rakVertex,aiCollapse,riEQuantity,raiEdge);
    WM4_DELETE[] aiCollapse;
}
//----------------------------------------------------------------------------
VertexCollapse::~VertexCollapse ()
{
    WM4_DELETE[] m_akRecord;
    WM4_DELETE[] m_apkHeap;
}
//----------------------------------------------------------------------------
float VertexCollapse::GetWeight (int iM, int iZ, int iP, Vector3f* akVertex)
{
    Segment3f kSegment;
    kSegment.Origin = 0.5f*(akVertex[iM] + akVertex[iP]);
    kSegment.Direction = akVertex[iP] - akVertex[iM];
    float fLength = kSegment.Direction.Normalize();
    kSegment.Extent = 0.5f*fLength;
    float fDist = DistVector3Segment3f(akVertex[iZ],kSegment).Get();
    return (fLength > 0.0f ? fDist/fLength : Mathf::MAX_REAL);
}
//----------------------------------------------------------------------------
void VertexCollapse::InitializeHeap (int iVQuantity, Vector3f* akVertex,
    bool bClosed)
{
    // Build the initial heap of weights, a max heap.  The weights are set
    // to negative values so that we get a min heap.  TO DO:  Modify the
    // code to directly implement a min heap.
    m_iHQuantity = iVQuantity;
    m_akRecord = WM4_NEW Record[m_iHQuantity];
    m_apkHeap = WM4_NEW Record*[m_iHQuantity];

    int i;
    for (i = 0; i < m_iHQuantity; i++)
    {
        m_akRecord[i].m_iVIndex = i;
        m_akRecord[i].m_iHIndex = i;
        m_akRecord[i].m_pkLAdj = &m_akRecord[(m_iHQuantity+i-1)%m_iHQuantity];
        m_akRecord[i].m_pkRAdj = &m_akRecord[(i+1)%m_iHQuantity];
        m_apkHeap[i] = &m_akRecord[i];
    }

    int iQm1 = m_iHQuantity - 1;
    if (bClosed)
    {
        int iQm2 = m_iHQuantity - 2;
        m_akRecord[0].m_fWeight = GetWeight(iQm1,0,1,akVertex);
        m_akRecord[iQm1].m_fWeight = GetWeight(iQm2,iQm1,0,akVertex);
    }
    else
    {
        m_akRecord[0].m_fWeight = Mathf::MAX_REAL;
        m_akRecord[iQm1].m_fWeight = Mathf::MAX_REAL;
    }

    for (int iM = 0, iZ = 1, iP = 2; iZ < iQm1; iM++, iZ++, iP++)
    {
        m_akRecord[iZ].m_fWeight = GetWeight(iM,iZ,iP,akVertex);
    }
}
//----------------------------------------------------------------------------
void VertexCollapse::BuildHeap ()
{
    int iLast = m_iHQuantity - 1;
    for (int iLeft = iLast/2; iLeft >= 0; iLeft--)
    {
        Record* pkRecord = m_apkHeap[iLeft];
        int iPa = iLeft, iCh = 2*iLeft + 1;
        while (iCh <= iLast)
        {
            if (iCh < iLast)
            {
                if (m_apkHeap[iCh]->m_fWeight > m_apkHeap[iCh+1]->m_fWeight)
                {
                    iCh++;
                }
            }

            if (m_apkHeap[iCh]->m_fWeight >= pkRecord->m_fWeight)
            {
                break;
            }

            m_apkHeap[iCh]->m_iHIndex = iPa;
            m_apkHeap[iPa] = m_apkHeap[iCh];
            iPa = iCh;
            iCh = 2*iCh + 1;
        }

        pkRecord->m_iHIndex = iPa;
        m_apkHeap[iPa] = pkRecord;
    }
}
//----------------------------------------------------------------------------
int VertexCollapse::RemoveRoot (Vector3f* akVertex)
{
    Record* pkRoot = m_apkHeap[0];

    int iLast = m_iHQuantity - 1;
    Record* pkRecord = m_apkHeap[iLast];
    int iPa = 0, iCh = 1;
    while (iCh <= iLast)
    {
        if (iCh < iLast)
        {
            if (m_apkHeap[iCh]->m_fWeight > m_apkHeap[iCh+1]->m_fWeight)
            {
                iCh++;
            }
        }

        if (m_apkHeap[iCh]->m_fWeight >= pkRecord->m_fWeight)
        {
            break;
        }

        m_apkHeap[iCh]->m_iHIndex = iPa;
        m_apkHeap[iPa] = m_apkHeap[iCh];
        iPa = iCh;
        iCh = 2*iCh + 1;
    }

    pkRecord->m_iHIndex = iPa;
    m_apkHeap[iPa] = pkRecord;
    m_iHQuantity--;

    // remove root from the doubly-linked list
    Record* pkLAdj = pkRoot->m_pkLAdj;
    Record* pkRAdj = pkRoot->m_pkRAdj;
    pkLAdj->m_pkRAdj = pkRAdj;
    pkRAdj->m_pkLAdj = pkLAdj;

    // update the weights of the vertices affected by the removal
    int iM, iZ, iP;
    float fWeight;

    if (pkLAdj->m_fWeight != Mathf::MAX_REAL)
    {
        iZ = pkLAdj->m_iVIndex;
        iM = pkLAdj->m_pkLAdj->m_iVIndex;
        iP = pkLAdj->m_pkRAdj->m_iVIndex;
        fWeight = GetWeight(iM,iZ,iP,akVertex);

        Update(pkLAdj->m_iHIndex,fWeight);
        assert(IsValid());
    }

    if (pkRAdj->m_fWeight != Mathf::MAX_REAL)
    {
        iZ = pkRAdj->m_iVIndex;
        iM = pkRAdj->m_pkLAdj->m_iVIndex;
        iP = pkRAdj->m_pkRAdj->m_iVIndex;
        fWeight = GetWeight(iM,iZ,iP,akVertex);

        Update(pkRAdj->m_iHIndex,fWeight);
        assert(IsValid());
    }

    return pkRoot->m_iVIndex;
}
//----------------------------------------------------------------------------
void VertexCollapse::Update (int iHIndex, float fWeight)
{
    Record* pkRecord = m_apkHeap[iHIndex];
    int iPa, iCh, iChP, iMaxCh;

    if (fWeight > pkRecord->m_fWeight)
    {
        pkRecord->m_fWeight = fWeight;

        // new weight larger than old, propagate it towards the leaves
        iPa = iHIndex;
        iCh = 2*iPa+1;
        while (iCh < m_iHQuantity)
        {
            // at least one child exists
            if (iCh < m_iHQuantity-1)
            {
                // two children exist
                iChP = iCh+1;
                if (m_apkHeap[iCh]->m_fWeight <= m_apkHeap[iChP]->m_fWeight)
                {
                    iMaxCh = iCh;
                }
                else
                {
                    iMaxCh = iChP;
                }
            }
            else
            {
                // one child exists
                iMaxCh = iCh;
            }

            if (m_apkHeap[iMaxCh]->m_fWeight >= fWeight)
            {
                break;
            }

            m_apkHeap[iMaxCh]->m_iHIndex = iPa;
            m_apkHeap[iPa] = m_apkHeap[iMaxCh];
            pkRecord->m_iHIndex = iMaxCh;
            m_apkHeap[iMaxCh] = pkRecord;
            iPa = iMaxCh;
            iCh = 2*iPa+1;
        }
    }
    else if (fWeight < pkRecord->m_fWeight)
    {
        pkRecord->m_fWeight = fWeight;

        // new weight smaller than old, propagate it towards the root
        iCh = iHIndex;
        while (iCh > 0)
        {
            // a parent exists
            iPa = (iCh-1)/2;

            if (m_apkHeap[iPa]->m_fWeight <= fWeight)
            {
                break;
            }

            m_apkHeap[iPa]->m_iHIndex = iCh;
            m_apkHeap[iCh] = m_apkHeap[iPa];
            pkRecord->m_iHIndex = iPa;
            pkRecord->m_fWeight = fWeight;
            m_apkHeap[iPa] = pkRecord;
            iCh = iPa;
        }
    }
}
//----------------------------------------------------------------------------
void VertexCollapse::CollapseVertices (int iVQuantity, Vector3f* akVertex,
    int* aiCollapse)
{
    for (int i = iVQuantity-1; i >= 0; i--)
    {
        aiCollapse[i] = RemoveRoot(akVertex);
    }
}
//----------------------------------------------------------------------------
void VertexCollapse::ComputeEdges (int iVQuantity, bool bClosed,
    int* aiCollapse, int* aiMap, int iEQuantity, int* aiEdge)
{
    // Compute the edges (first to collapse is last in array).  Do not
    // collapse last line segment of open polyline.  Do not collapse last
    // triangle of closed polyline.
    int i, iVIndex, iEIndex = 2*iEQuantity-1;

    if (bClosed)
    {
        for (i = iVQuantity-1; i >= 0; i--)
        {
            iVIndex = aiCollapse[i];
            aiEdge[iEIndex--] = (iVIndex+1) % iVQuantity;
            aiEdge[iEIndex--] = iVIndex;
        }
    }
    else
    {
        for (i = iVQuantity-1; i >= 2; i--)
        {
            iVIndex = aiCollapse[i];
            aiEdge[iEIndex--] = iVIndex+1;
            aiEdge[iEIndex--] = iVIndex;
        }

        iVIndex = aiCollapse[0];
        aiEdge[0] = iVIndex;
        aiEdge[1] = iVIndex+1;
    }

    // In the given edge order, find the index in the edge array that
    // corresponds to a collapse vertex and save the index for the dynamic
    // change in level of detail.  This relies on the assumption that a
    // vertex is shared by at most two edges.
    iEIndex = 2*iEQuantity-1;
    for (i = iVQuantity-1; i >= 0; i--)
    {
        iVIndex = aiCollapse[i];
        for (int iE = 0; iE < 2*iEQuantity; iE++)
        {
            if (iVIndex == aiEdge[iE])
            {
                aiMap[i] = iE;
                aiEdge[iE] = aiEdge[iEIndex];
                break;
            }
        }
        iEIndex -= 2;

        if (bClosed)
        {
            if (iEIndex == 5)
            {
                break;
            }
        }
        else
        {
            if (iEIndex == 1)
            {
                break;
            }
        }
    }

    // restore the edge array to full level of detail
    if (bClosed)
    {
        for (i = 3; i < iVQuantity; i++)
        {
            iVIndex = aiCollapse[i];
            aiEdge[aiMap[i]] = iVIndex;
        }
    }
    else
    {
        for (i = 2; i < iVQuantity; i++)
        {
            iVIndex = aiCollapse[i];
            aiEdge[aiMap[i]] = iVIndex;
        }
    }
}
//----------------------------------------------------------------------------
void VertexCollapse::ReorderVertices (int iVQuantity, Vector3f*& rakVertex,
    int* aiCollapse, int iEQuantity, int* aiEdge)
{
    int* aiPermute = WM4_NEW int[iVQuantity];
    Vector3f* akPVertex = WM4_NEW Vector3f[iVQuantity];

    int i;
    for (i = 0; i < iVQuantity; i++)
    {
        int iVIndex = aiCollapse[i];
        aiPermute[iVIndex] = i;
        akPVertex[i] = rakVertex[iVIndex];
    }

    for (i = 0; i < 2*iEQuantity; i++)
    {
        aiEdge[i] = aiPermute[aiEdge[i]];
    }

    WM4_DELETE[] rakVertex;
    rakVertex = akPVertex;

    WM4_DELETE[] aiPermute;
}
//----------------------------------------------------------------------------
bool VertexCollapse::IsValid (int iStart, int iFinal)
{
    for (int iC = iStart; iC <= iFinal; iC++)
    {
        int iP = (iC-1)/2;
        if (iP > iStart)
        {
            if (m_apkHeap[iP]->m_fWeight > m_apkHeap[iC]->m_fWeight)
            {
                return false;
            }

            if (m_apkHeap[iP]->m_iHIndex != iP)
            {
                return false;
            }
        }
    }

    return true;
}
//----------------------------------------------------------------------------
bool VertexCollapse::IsValid ()
{
    return IsValid(0,m_iHQuantity-1);
}
//----------------------------------------------------------------------------
