// 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.

#ifndef WM3CONTCONVEXHULL3_H
#define WM3CONTCONVEXHULL3_H

#include "Wm3ContHullTriangle3.h"
#include "Wm3Query3.h"
#include <set>

namespace Wm3
{

template <class Real>
class WM3_ITEM ConvexHull3
{
public:
    // Construction and destruction.  The caller is responsible for deleting
    // the akVertex array.
    ConvexHull3 (int iVQuantity, const Vector3<Real>* akVertex);
    ~ConvexHull3 ();

    // Compute the hull using an incremental method. The Boolean return
    // value is 'true' if the construction was successful.  If the value is
    // 'false', then a release-build run failed and a bug report should be
    // filed.
    bool DoIncremental (Real fEpsilon = (Real)0.001);

    // The dimension of the hull is in {0,1,2}.  The index array has
    // GetQuantity() elements. The possibilities are
    //     dim = 0, quantity = 1, indices = {0}
    //     dim = 1, quantity = 2, indices = {i[0],i[1]}
    //     dim = 2, quantity >= 3, indices = {i[0],...,i[quantity-1]}
    //     dim = 3, quantity >= 3, The number of triangles is quantity/3.
    //              The array contains triples of vertex indices, one triple
    //              per triangle.
    int GetDimension () const;
    int GetQuantity () const;
    int* GetIndices (bool bTakeOwnership = false);

    // If the hull dimension is 1, the hull is linear and lives on the line
    // with these parameters.
    const Vector3<Real>& GetLineOrigin () const;
    const Vector3<Real>& GetLineDirection () const;

    // If the hull dimension is 2, the hull is planar and lives on the plane
    // with these parameters.
    const Vector3<Real>& GetPlaneOrigin () const;
    const Vector3<Real>& GetPlaneNormal () const;

private:
    bool Update (HullTriangle3<Real>*& rpkHull, int i);
    void ExtractIndices ();
    void DeleteHull ();

    // input points
    int m_iVQuantity;
    const Vector3<Real>* m_akVertex;
    Vector3<Real>* m_akSVertex;

    // support for robust calculations
    Query3<Real>* m_pkQuery;

    // for a linear hull only
    Vector3<Real> m_kLineOrigin, m_kLineDirection;

    // for a planar hull only
    Vector3<Real> m_kPlaneOrigin, m_kPlaneNormal;

    // the hull
    std::set<HullTriangle3<Real>*> m_kHull;
    int m_iHDim, m_iHQuantity;
    int* m_aiHIndex;

    class TerminatorData
    {
    public:
        TerminatorData (int iV0 = -1, int iV1 = -1, int iNullIndex = -1,
            HullTriangle3<Real>* pkTri = 0)
        {
            V[0] = iV0;
            V[1] = iV1;
            NullIndex = iNullIndex;
            Tri = pkTri;
        }

        int V[2];
        int NullIndex;
        HullTriangle3<Real>* Tri;
    };
};

typedef ConvexHull3<float> ConvexHull3f;
typedef ConvexHull3<double> ConvexHull3d;

}

#endif



