// EMERGENT GAME TECHNOLOGIES PROPRIETARY INFORMATION
//
// This software is supplied under the terms of a license agreement or
// nondisclosure agreement with Emergent Game Technologies and may not 
// be copied or disclosed except in accordance with the terms of that 
// agreement.
//
//      Copyright (c) 1996-2007 Emergent Game Technologies.
//      All Rights Reserved.
//
// Emergent Game Technologies, Chapel Hill, North Carolina 27517
// http://www.emergent.net

#ifndef HULLMANAGER_H
#define HULLMANAGER_H

#include <NiPoint3.h>
#include <NiPlane.h>
#include "EdgeMap.h"
#include <NiMemObject.h>

class HullManager : public NiMemObject
{
public:
    // Construction and destruction.  Initially, the axis-aligned bounding
    // box (AABB) of the points is used as an approximate hull.  Pairs of
    // hulls are later compared for intersection.  If two such AABBs
    // intersect, their full convex hulls are computed and used from that
    // time on.  HullManager takes responsibility for deleting akPoints.
    HullManager(int iNumPoints, NiPoint3* akPoints);
    ~HullManager();

    // The vertices and planes defining the hull.
    int GetNumVertices() const;
    const NiPoint3* GetVertices() const;
    int GetNumPlanes() const;
    const NiPlane* GetPlanes() const;
    const int* GetTriangles() const;

    // Returns 'true' iff the convex hull is used to define the room walls.
    bool UsesHull() const;

    // Test if the hulls are separated.  The function has side effects.  If
    // an object is using its AABB as the approximate hull, and if the AABB
    // intersects the other objects's AABB or hull (whichever it happens to
    // be using), then the object computes its actual hull and the test is
    // performed anew.  The return value is exactly 0.0f when the hulls are
    // separated.  Otherwise, the return value is an estimate of the
    // penetration depth.
    float AreSeparated(HullManager* pkHull);

private:
    // Prevent implicit copy construction or assignment.
    HullManager(const HullManager& kHull);
    HullManager& operator=(const HullManager& kHull);

    // For deferred calculation of the convex hull.
    bool ComputeConvexHull();

    // Preprocessing of the inputs for the convex hull construction.  Points
    // that are nearly duplicates are eliminated using fuzzy comparisons.
    void EliminateDuplicates(const float fEpsilon);

    // Postprocessing of the convex hull generated by ConvexHull3D.  Build
    // an array of the hull vertices.  Interior points are not needed for
    // further processing.
    void CompactifyHull();

    // Postprocessing of the convex hull.  Reorder the triangles' vertex
    // indices so that the triangles are clockwise when viewed from outside
    // the hull.  The planes of the triangles are computed and have inner
    // pointing normals.
    void ComputeConsistentPlanes();

    // Postprocessing of the convex hull.  The convex hull generation might
    // have needle-like triangles or other problems due to floating-point
    // round-off errors.  This function makes an attempt to reduce the plane
    // count for the hull.
    void GenerateUniquePlanes();

    // Postprocessing of the convex hull.  A set of unique edges for the hull
    // is built.  These are used in the hull intersection testing in the
    // AreSeparated functions.
    void GenerateUniqueEdges();

    // Test to determine if two axis-aligned boxes are disjoint.
    static bool AreSeparated(const NiPoint3& kMin0, const NiPoint3& kMax0,
        const NiPoint3& kMin1, const NiPoint3& kMax1);

    // Separating axis test to determine if two convex hulls are disjoint.
    // This function does not report an intersection if two hulls slightly
    // overlap, since two rooms that theoretically share a wall (and are
    // both tangent to the wall) might otherwise be reported as intersecting
    // because of floating-point round-off errors when representing the
    // rooms.
    static bool AreSeparated(const HullManager& kHull0,
        const HullManager& kHull1);

    // Determine if the input points are fully on one side of the input plane.
    // The return value is +1 if all points are on the side of the plane to
    // which the normal points, -1 if all points are on the other side of the
    // plane, or 0 if some points are on one side and some on the other side.
    static int OnSameSide(const NiPlane& kPlane, int iVQuantity,
        const NiPoint3* pkPoint);

    // For information purposes.  This function estimates the penetration
    // fraction for two intersecting hulls.  The quantity is the smallest
    // overlap on a potential separating axis of the intervals of projection
    // divided by the width of the union of the intervals of projection.
    static float EstimatePenetrationFraction(const HullManager& kHull0,
        const HullManager& kHull1);

    // Compute the interval of projection of the input points onto the
    // normal line for the input plane.  The interval is [lower,upper].
    static void ComputeProjection(const NiPlane& kPlane, int iVQuantity,
        const NiPoint3* pkPoint, float& fLower, float& fUpper);

    // Compute the intersection and union of the two intervals.  The return
    // value is the number of end points in the intersection (0, 1, or 2).
    static int GetIntervalInfo(float fMin0, float fMax0, float fMin1,
        float fMax1, float& fMinI, float& fMaxI, float& fMinU, float& fMaxU);

    // Keep a handle on the original point set so that the convex hull may
    // be computed when needed.
    int m_iNumPoints;
    NiPoint3* m_akPoints;

    // Axis-aligned bounding box and average point for the original points.
    NiPoint3 m_kMin, m_kMax, m_kAvg;

    // Either the convex hull of the vertices in the room subtree or the
    // AABB of the vertices.  These represent the hull whenever m_akPoints
    // is not null.
    int m_iNumVertices;
    NiPoint3* m_akVertices;
    int m_iNumPlanes;
    NiPlane* m_akPlanes;
    int* m_aiTriangles;
    EdgeMap m_kEdges;  // map used instead of set for hash capabilities
};

#endif