// Geometric Tools, Inc.
// http://www.geometrictools.com
// Copyright (c) 1998-2005.  All Rights Reserved
//
// The Wild Magic Library (WM3) source code is supplied under the terms of
// the license agreement
//     http://www.geometrictools.com/License/WildMagic3License.pdf
// and may not be copied or disclosed except in accordance with the terms
// of that agreement.

#include "Wm3ContConvexHull3.h"
#include "Wm3ContConvexHull2.h"
#include "Wm3Mapper3.h"

// The fastest choice is Query3Int64.  The others may be swapped in for
// testing by enabling exactly one of the following defines.
#define USE_QUERY3INT64
//#define USE_QUERY3TINTEGER
//#define USE_QUERY3TRATIONAL

#ifdef USE_QUERY3INT64
#include "Wm3Query3Int64.h"
#endif

#ifdef USE_QUERY3TINTEGER
#include "Wm3Query3TInteger.h"
#endif

#ifdef USE_QUERY3TRATIONAL
#include "Wm3Query3TRational.h"
#endif

#include <map>
#include <stack>

namespace Wm3
{

//----------------------------------------------------------------------------
template <class Real>
ConvexHull3<Real>::ConvexHull3 (int iVQuantity, const Vector3<Real>* akVertex)
    :
    m_kLineOrigin(Vector3<Real>::ZERO),
    m_kLineDirection(Vector3<Real>::ZERO),
    m_kPlaneOrigin(Vector3<Real>::ZERO),
    m_kPlaneNormal(Vector3<Real>::ZERO)
{
    assert( iVQuantity > 0 && akVertex );
    m_iVQuantity = iVQuantity;
    m_akVertex = akVertex;
    m_akSVertex = 0;
    m_pkQuery = 0;
    m_iHDim = 0;
    m_iHQuantity = 0;
    m_aiHIndex = 0;
}
//----------------------------------------------------------------------------
template <class Real>
ConvexHull3<Real>::~ConvexHull3 ()
{
    assert( m_pkQuery == 0 );
    delete[] m_aiHIndex;

#ifndef USE_QUERY3TRATIONAL
    delete[] m_akSVertex;
#endif
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexHull3<Real>::DoIncremental (Real fEpsilon)
{
    if ( fEpsilon < (Real)0.0 )
        fEpsilon = (Real)0.0;

    // Clear out the index array in case this function is called more than
    // one time (for different dimThreshold or uncertainty parameters).
    delete[] m_aiHIndex;
    m_aiHIndex = 0;

    // Clear out the line and plane parameters in case the hull turns out not
    // to be linear or planar.
    m_kLineOrigin = Vector3<Real>::ZERO;
    m_kLineDirection = Vector3<Real>::ZERO;
    m_kPlaneOrigin = Vector3<Real>::ZERO;
    m_kPlaneNormal = Vector3<Real>::ZERO;

    // Determine the dimension of the point set.
    Mapper3<Real> kMapper(m_iVQuantity,m_akVertex,fEpsilon);

    if ( kMapper.GetDimension() == 0 )
    {
        // The hull is (nearly) a point.
        m_iHDim = 0;
        m_iHQuantity = 1;
        m_aiHIndex = new int[1];
        m_aiHIndex[0] = 0;
        return true;
    }

    int i0 = kMapper.GetExtremeIndex(0);
    int i1 = kMapper.GetExtremeIndex(1);
    if ( kMapper.GetDimension() == 1 )
    {
        // The hull is (nearly) a line segment.
        m_iHDim = 1;
        m_iHQuantity = 2;
        m_aiHIndex = new int[2];
        m_aiHIndex[0] = i0;
        m_aiHIndex[1] = i1;
        m_kLineOrigin = kMapper.GetOrigin();
        m_kLineDirection = kMapper.GetDirection(0);
        return true;
    }

    int i2 = kMapper.GetExtremeIndex(2);
    if ( kMapper.GetDimension() == 2 )
    {
        // The hull is (nearly) a convex polygon.  Project points into the
        // common plane of the points.
        Vector2<Real>* akPVertex = new Vector2<Real>[m_iVQuantity];
        const Vector3<Real>& rkU0 = kMapper.GetDirection(0);
        const Vector3<Real>& rkU1 = kMapper.GetDirection(1);
        for (int i = 0; i < m_iVQuantity; i++)
        {
            Vector3<Real> kDiff = m_akVertex[i] - kMapper.GetOrigin();
            akPVertex[i][0] = rkU0.Dot(kDiff);
            akPVertex[i][1] = rkU1.Dot(kDiff);
        }

        m_kPlaneOrigin = kMapper.GetOrigin();
        m_kPlaneNormal = kMapper.GetDirection(2);

        ConvexHull2<Real> kHull2(m_iVQuantity,akPVertex);
        bool bSuccess = kHull2.DoIncremental();
        assert( bSuccess );
        m_iHDim = kHull2.GetDimension();
        m_iHQuantity = kHull2.GetQuantity();
        m_aiHIndex = kHull2.GetIndices(true);
        delete[] akPVertex;
        return bSuccess;
    }

    int i3 = kMapper.GetExtremeIndex(3);
    m_iHDim = 3;

    int i;

#ifndef USE_QUERY3TRATIONAL
    // Transform the vertices to the cube [-2^{20},2^{20}]^3 to allow use of
    // 64-bit integers for hull construction.
    if ( !m_akSVertex )
        m_akSVertex = new Vector3<Real>[m_iVQuantity];

    Real fScale = ((Real)(1 << 20))/kMapper.GetMaxRange();
    for (i = 0; i < m_iVQuantity; i++)
        m_akSVertex[i] = (m_akVertex[i] - kMapper.GetMin())*fScale;

#ifdef USE_QUERY3INT64
    m_pkQuery = new Query3Int64<Real>(m_iVQuantity,m_akSVertex);
#else
    m_pkQuery = new Query3TInteger<Real>(m_iVQuantity,m_akSVertex);
#endif
#else
    m_akSVertex = (Vector3<Real>*)m_akVertex;
    m_pkQuery = new Query3TRational<Real>(m_iVQuantity,m_akSVertex);
#endif

    HullTriangle3<Real>* pkT0;
    HullTriangle3<Real>* pkT1;
    HullTriangle3<Real>* pkT2;
    HullTriangle3<Real>* pkT3;

    if ( kMapper.GetExtremeCCW() )
    {
        pkT0 = new HullTriangle3<Real>(i0,i1,i3);
        pkT1 = new HullTriangle3<Real>(i0,i2,i1);
        pkT2 = new HullTriangle3<Real>(i0,i3,i2);
        pkT3 = new HullTriangle3<Real>(i1,i2,i3);
        pkT0->AttachTo(pkT1,pkT3,pkT2);
        pkT1->AttachTo(pkT2,pkT3,pkT0);
        pkT2->AttachTo(pkT0,pkT3,pkT1);
        pkT3->AttachTo(pkT1,pkT2,pkT0);
    }
    else
    {
        pkT0 = new HullTriangle3<Real>(i0,i3,i1);
        pkT1 = new HullTriangle3<Real>(i0,i1,i2);
        pkT2 = new HullTriangle3<Real>(i0,i2,i3);
        pkT3 = new HullTriangle3<Real>(i1,i3,i2);
        pkT0->AttachTo(pkT2,pkT3,pkT1);
        pkT1->AttachTo(pkT0,pkT3,pkT2);
        pkT2->AttachTo(pkT1,pkT3,pkT0);
        pkT3->AttachTo(pkT0,pkT2,pkT1);
    }

    m_kHull.clear();
    m_kHull.insert(pkT0);
    m_kHull.insert(pkT1);
    m_kHull.insert(pkT2);
    m_kHull.insert(pkT3);

    HullTriangle3<Real>* pkHull = pkT0;
    for (i = 0; i < m_iVQuantity; i++)
    {
        if ( !Update(pkHull,i) )
        {
            DeleteHull();
            return false;
        }
    }

    ExtractIndices();

    delete m_pkQuery;
    m_pkQuery = 0;
    return true;
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexHull3<Real>::GetDimension () const
{
    return m_iHDim;
}
//----------------------------------------------------------------------------
template <class Real>
int ConvexHull3<Real>::GetQuantity () const
{
    return m_iHQuantity;
}
//----------------------------------------------------------------------------
template <class Real>
int* ConvexHull3<Real>::GetIndices (bool bTakeOwnership)
{
    int* aiIndices = m_aiHIndex;
    if ( bTakeOwnership )
        m_aiHIndex = 0;

    return aiIndices;
}
//----------------------------------------------------------------------------
template <class Real>
const Vector3<Real>& ConvexHull3<Real>::GetLineOrigin () const
{
    return m_kLineOrigin;
}
//----------------------------------------------------------------------------
template <class Real>
const Vector3<Real>& ConvexHull3<Real>::GetLineDirection () const
{
    return m_kLineDirection;
}
//----------------------------------------------------------------------------
template <class Real>
const Vector3<Real>& ConvexHull3<Real>::GetPlaneOrigin () const
{
    return m_kPlaneOrigin;
}
//----------------------------------------------------------------------------
template <class Real>
const Vector3<Real>& ConvexHull3<Real>::GetPlaneNormal () const
{
    return m_kPlaneNormal;
}
//----------------------------------------------------------------------------
template <class Real>
bool ConvexHull3<Real>::Update (HullTriangle3<Real>*& rpkHull, int i)
{
    // Locate a triangle visible to the input point (if possible).
    HullTriangle3<Real>* pkVisible = 0;
    HullTriangle3<Real>* pkTri;
    typename std::set<HullTriangle3<Real>*>::iterator pkIter;
    for (pkIter = m_kHull.begin(); pkIter != m_kHull.end(); pkIter++)
    {
        pkTri = *pkIter;
        if ( pkTri->GetSign(i,m_pkQuery) > 0 )
        {
            pkVisible = pkTri;
            break;
        }
    }

    if ( !pkVisible )
    {
        // The point is inside the current hull; nothing to do.
        return true;
    }

    // Locate and remove the visible triangles.
    std::stack<HullTriangle3<Real>*> kVisible;
    std::map<int,TerminatorData> kTerminator;
    kVisible.push(pkVisible);
    pkVisible->OnStack = true;
    int j, iV0, iV1;
    while ( !kVisible.empty() )
    {
        pkTri = kVisible.top();
        kVisible.pop();
        pkTri->OnStack = false;
        for (j = 0; j < 3; j++)
        {
            HullTriangle3<Real>* pkAdj = pkTri->A[j];
            if ( pkAdj )
            {
                // Detach triangle and adjacent triangle from each other.
                int iNullIndex = pkTri->DetachFrom(j,pkAdj);

                if ( pkAdj->GetSign(i,m_pkQuery) > 0 )
                {
                    if ( !pkAdj->OnStack )
                    {
                        // Adjacent triangle is visible.
                        kVisible.push(pkAdj);
                        pkAdj->OnStack = true;
                    }
                }
                else
                {
                    // Adjacent triangle is invisible.
                    iV0 = pkTri->V[j];
                    iV1 = pkTri->V[(j+1)%3];
                    kTerminator[iV0] = TerminatorData(iV0,iV1,iNullIndex,
                        pkAdj);
                }
            }
        }
        m_kHull.erase(pkTri);
        delete pkTri;
    }

    // Insert the new edges formed by the input point and the terminator
    // between visible and invisible triangles.
    int iSize = (int)kTerminator.size();
    assert( iSize >= 3 );
    typename std::map<int,TerminatorData>::iterator pkEdge =
        kTerminator.begin();
    iV0 = pkEdge->second.V[0];
    iV1 = pkEdge->second.V[1];
    pkTri = new HullTriangle3<Real>(i,iV0,iV1);
    m_kHull.insert(pkTri);

    // save information for linking first/last inserted new triangles
    int iSaveV0 = pkEdge->second.V[0];
    HullTriangle3<Real>* pkSaveTri = pkTri;

    // establish adjacency links across terminator edge
    pkTri->A[1] = pkEdge->second.Tri;
    pkEdge->second.Tri->A[pkEdge->second.NullIndex] = pkTri;
    for (j = 1; j < iSize; j++)
    {
        pkEdge = kTerminator.find(iV1);
        assert( pkEdge != kTerminator.end() );
        iV0 = iV1;
        iV1 = pkEdge->second.V[1];
        HullTriangle3<Real>* pkNext = new HullTriangle3<Real>(i,iV0,iV1);
        m_kHull.insert(pkNext);

        // establish adjacency links across terminator edge
        pkNext->A[1] = pkEdge->second.Tri;
        pkEdge->second.Tri->A[pkEdge->second.NullIndex] = pkNext;

        // establish adjacency links with previously inserted triangle
        pkNext->A[0] = pkTri;
        pkTri->A[2] = pkNext;

        pkTri = pkNext;
    }
    assert( iV1 == iSaveV0 );
    (void)iSaveV0;  // avoid warning in Release build

    // establish adjacency links between first/last triangles
    pkSaveTri->A[0] = pkTri;
    pkTri->A[2] = pkSaveTri;

    return true;
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull3<Real>::ExtractIndices ()
{
    int iTQuantity = (int)m_kHull.size();
    m_iHQuantity = 3*iTQuantity;
    m_aiHIndex = new int[m_iHQuantity];

    typename std::set<HullTriangle3<Real>*>::iterator pkIter;
    int i = 0;
    for (pkIter = m_kHull.begin(); pkIter != m_kHull.end(); pkIter++)
    {
        HullTriangle3<Real>* pkTri = *pkIter;
        for (int j = 0; j < 3; j++)
            m_aiHIndex[i++] = pkTri->V[j];
        delete pkTri;
    }
    m_kHull.clear();
}
//----------------------------------------------------------------------------
template <class Real>
void ConvexHull3<Real>::DeleteHull ()
{
    typename std::set<HullTriangle3<Real>*>::iterator pkIter;
    for (pkIter = m_kHull.begin(); pkIter != m_kHull.end(); pkIter++)
    {
        HullTriangle3<Real>* pkTri = *pkIter;
        delete pkTri;
    }
    m_kHull.clear();
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// explicit instantiation
//----------------------------------------------------------------------------
// float
template WM3_ITEM
class ConvexHull3<float>;

// double
template WM3_ITEM
class ConvexHull3<double>;
//----------------------------------------------------------------------------
}



