/**
 @file MeshAlg.h

 Indexed Mesh algorithms.

 @maintainer Morgan McGuire, matrix@graphics3d.com

 @created 2003-09-14
 @edited  2004-12-26
*/

#ifndef G3D_MESHALG_H
#define G3D_MESHALG_H

#include "G3D/platform.h"
#include "G3D/Array.h"
#include "G3D/Vector3.h"

namespace G3D {

/**
  Indexed <B>mesh alg</B>orithms.  You have to build your own mesh class.
  <P>
  No mesh class is provided with G3D because there isn't an "ideal" 
  mesh format-- one application needs keyframed animation, another
  skeletal animation, a third texture coordinates, a fourth
  cannot precompute information, etc.  Instead of compromising, this
  class implements the hard parts of mesh computation and you can write
  your own ideal mesh class on top of it.
  */ 
class MeshAlg {
public:

    enum Primitive {LINES, LINE_STRIP, TRIANGLES, TRIANGLE_STRIP,
                    TRIANGLE_FAN, QUADS, QUAD_STRIP, POINTS};


    /** Adjacency information for a vertex.
        Does not contain the vertex position or normal,
        which are stored in the MeshAlg::Geometry object.
        <CODE>Vertex</CODE>s must be stored in an array
        parallel to (indexed in the same way as) 
        MeshAlg::Geometry::vertexArray.
        */
    class Vertex {
    public:
        Vertex() {}

        /**
         Array of edges adjacent to this vertex.
         Let e = edgeIndex[i].  
         edge[(e >= 0) ? e : ~e].vertexIndex[0] == this
         vertex index.
         
         Edges may be listed multiple times if they are
         degenerate.
         */
        Array<int>              edgeIndex;

        /**
         Returns true if e or ~e is in the edgeIndex list.
         */
        inline bool inEdge(int e) const {
            return edgeIndex.contains(~e) || edgeIndex.contains(e);
        }

        /**
         Array of faces containing this vertex.  Faces
         may be listed multiple times if they are degenerate.
        */
        Array<int>              faceIndex;

        inline bool inFace(int f) const {
            debugAssert(f >= 0);
            return faceIndex.contains(f);
        }
    };


    /**
     Oriented, indexed triangle.
     */
    class Face {
    public:
        Face();

        /**
         Used by Edge::faceIndex to indicate a missing face.
         This is a large negative value.
         */
        static const int        NONE;


        /**
         Vertices in the face in counter-clockwise order.
         Degenerate faces may include the same vertex multiple times.
         */
        int                     vertexIndex[3];

        inline bool containsVertex(int v) const {
            return contains(vertexIndex, 3, v);
        }

        /**
         Edge indices in counter-clockwise order.  Edges are
         undirected, so it is important to know which way 
         each edge is pointing in a face.  This is encoded
         using negative indices.
         
         If <CODE>edgeIndex[i] >= 0</CODE> then this face
         contains the directed edge
         between vertex indices  
         <CODE>edgeArray[face.edgeIndex[i]].vertexIndex[0]</CODE>
         and
         <CODE>edgeArray[face.edgeIndex[i]].vertexIndex[1]</CODE>.
         
         If <CODE>edgeIndex[i] < 0</CODE> then 
         <CODE>~edgeIndex[i]</CODE> (i.e. the two's
         complement of) is used and this face contains the directed
         edge between vertex indices
         <CODE>edgeArray[~face.edgeIndex[i]].vertexIndex[0]</CODE>
         and
         <CODE>edgeArray[~face.edgeIndex[i]].vertexIndex[1]</CODE>.

         Degenerate faces may include the same edge multiple times.
         */
        // Temporarily takes on the value Face::NONE during adjacency
        // computation to indicate an edge that has not yet been assigned.
        int                     edgeIndex[3];

        inline bool containsEdge(int e) const {
            if (e < 0) {
                e = ~e;
            }
            return contains(edgeIndex, 3, e) || contains(edgeIndex, 3, ~e);
        }

        /** Contains the forward edge e if e >= 0 and the backward edge 
            ~e otherwise. */
        inline bool containsDirectedEdge(int e) const {
            return contains(edgeIndex, 3, e);
        }
    };


    /** Oriented, indexed edge */
    class Edge {
    public:
        Edge();

        /** Degenerate edges may include the same vertex times. */
        int                     vertexIndex[2];
        
        inline bool containsVertex(int v) const {
            return contains(vertexIndex, 3, v);
        }

        /**
         The edge is directed <B>forward</B> in face 0
         <B>backward</B> in face 1. Face index of MeshAlg::Face::NONE
         indicates a boundary (a.k.a. crack, broken) edge.
         */
        int                     faceIndex[2];
        
        /** Returns true if f is contained in the faceIndex array in either slot.
            To see if it is forward in that face, just check edge.faceIndex[0] == f.*/
        inline bool inFace(int f) const {
            return contains(faceIndex, 2, f);
        }

        /**
         Returns true if either faceIndex is NONE.
         */
        inline bool boundary() const {
            return (faceIndex[0] == Face::NONE) ||
                   (faceIndex[1] == Face::NONE);
        }

        /** @deprecated Use Edge::boundary */
        inline bool broken() const {
            return boundary();
        }

        /**
         Returns the reversed edge.
         */
        inline Edge reverse() const {
            Edge e;
            e.vertexIndex[0] = vertexIndex[1];
            e.vertexIndex[1] = vertexIndex[0];
            e.faceIndex[0]   = faceIndex[1];
            e.faceIndex[1]   = faceIndex[0];
            return e;
        }
    };
    

    /**
     Convenient for passing around the data that changes under
     animation. The faces and edges are needed to interpret 
     these values.
     */
    class Geometry {
    public:        
        Array<Vector3>          vertexArray;
        Array<Vector3>          normalArray;

        /**
         Assignment is optimized using SSE.
         */
        Geometry& operator=(const Geometry& src);

        void clear() {
            vertexArray.clear();
            normalArray.clear();
        }
    };

    /**
     Given a set of vertices and a set of indices for traversing them
     to create triangles, computes other mesh properties.  

     <B>Colocated vertices are treated as separate.</B>  To have
     colocated vertices collapsed (necessary for many algorithms,
     like shadowing), weld the mesh before computing adjacency.
     
     <I>Recent change: In version 6.00, colocated vertices were automatically
     welded by this routine and degenerate faces and edges were removed.  That
     is no longer the case.</I>

     Where two faces meet, there are two opposite directed edges.  These
     are collapsed into a single bidirectional edge in the edgeArray.
     If four faces meet exactly at the same edge, that edge will appear
     twice in the array, and so on.  If an edge is a boundary of the mesh 
     (i.e. if the edge has only one adjacent face) it will appear in the 
     array with one  face index set to MeshAlg::Face::NONE.

     @param vertexArray Vertex positions to use when deciding colocation.
     @param indexArray  Order to traverse vertices to make triangles
     @param faceArray   <I>Output</I>
     @param edgeArray   <I>Output</I>.  Sorted so that boundary edges are at the end of the array. 
     @param vertexArray <I>Output</I> 
     */
    static void computeAdjacency(
        const Array<Vector3>&   vertexGeometry,
        const Array<int>&       indexArray,
        Array<Face>&            faceArray,
        Array<Edge>&            edgeArray,
        Array<Vertex>&          vertexArray);

    /**
     @deprecated Use the other version of computeAdjacency, which takes Array<Vertex>.
     @param facesAdjacentToVertex <I>Output</I> adjacentFaceArray[v] is an array of
                        indices for faces touching vertex index v
     */
    static void computeAdjacency(
        const Array<Vector3>&   vertexArray,
        const Array<int>&       indexArray,
        Array<Face>&            faceArray,
        Array<Edge>&            edgeArray,
        Array< Array<int> >&    facesAdjacentToVertex);



    static void computeAreaStatistics(
        const Array<Vector3>&   vertexArray,
        const Array<int>&       indexArray,
        double&                 minEdgeLength,
        double&                 meanEdgeLength,
        double&                 medianEdgeLength,
        double&                 maxEdgeLength,
        double&                 minFaceArea,
        double&                 meanFaceArea,
        double&                 medianFaceArea,
        double&                 maxFaceArea);

private:
    /**
     Computes the tangent space basis vectors for
     a counter-clockwise oriented face.

     @cite Max McGuire
     */
    static void computeTangentVectors(
        const Vector3&  normal,
        const Vector3   position[3],
        const Vector2   texCoord[3],
        Vector3&        tangent, 
        Vector3&        binormal);

    /** Helper for weldAdjacency */
    static void weldBoundaryEdges(
        Array<Face>&       faceArray,
        Array<Edge>&       edgeArray,
        Array<Vertex>&     vertexArray);

public:

    /**
     Computes tangent and binormal vectors,
     which provide a (mostly) consistent
     parameterization over the surface for
     effects like bump mapping.  In the resulting coordinate frame, 
     T = x (varies with texture s coordinate), B = y (varies with negative texture t coordinate), 
     and N = z for a right-handed coordinate frame.  If a billboard is vertical on the screen
     in view of the camera, the tangent space matches the camera's coordinate frame.

     The vertex, texCoord, tangent, and binormal
     arrays are parallel arrays.

     The resulting tangent and binormal might not be exactly
     perpendicular to each other.  They are guaranteed to
     be perpendicular to the normal.

     @cite Max McGuire
    */
    static void computeTangentSpaceBasis(
        const Array<Vector3>&       vertexArray,
        const Array<Vector2>&       texCoordArray,
        const Array<Vector3>&       vertexNormalArray,
        const Array<Face>&          faceArray,
        Array<Vector3>&             tangent,
        Array<Vector3>&             binormal);

    /** @deprecated */
    static void computeNormals(
        const Array<Vector3>&   vertexArray,
        const Array<Face>&      faceArray,
        const Array< Array<int> >& adjacentFaceArray,
        Array<Vector3>&         vertexNormalArray,
        Array<Vector3>&         faceNormalArray);

    /**
     Vertex normals are weighted by the area of adjacent faces.
     Nelson Max showed this is superior to uniform weighting for
     general meshes in jgt.

     @param vertexNormalArray Output. Unit length
     @param faceNormalArray Output.   Degenerate faces produce zero magnitude normals. Unit length
    */
    static void computeNormals(
        const Array<Vector3>&   vertexGeometry,
        const Array<Face>&      faceArray,
        const Array<Vertex>&    vertexArray,
        Array<Vector3>&         vertexNormalArray,
        Array<Vector3>&         faceNormalArray);

    /** Computes unit length normals in place using the other computeNormals methods.
    If you already have a face array use another method; it will be faster. */
    static void computeNormals(
        Geometry&               geometry,
        const Array<int>&       indexArray);


    /**
     Computes face normals only.  Significantly faster (especially if
     normalize is false) than computeNormals.
     */
    static void computeFaceNormals(
        const Array<Vector3>&           vertexArray,
        const Array<Face>&              faceArray,
        Array<Vector3>&                 faceNormals,
        bool                            normalize = true);

    /**
     Classifies each face as a backface or a front face relative
     to the observer point P (which is at infinity when P.w = 0).
     A face with normal exactly perpendicular to the observer vector
     may be classified as either a front or a back face arbitrarily.
     */
    static void identifyBackfaces(
        const Array<Vector3>&           vertexArray,
        const Array<Face>&              faceArray,
        const Vector4&                  P,
        Array<bool>&                    backface);

    /** A faster version of identifyBackfaces for the case where
        face normals have already been computed */
    static void identifyBackfaces(
        const Array<Vector3>&           vertexArray,
        const Array<Face>&              faceArray,
        const Vector4&                  P,
        Array<bool>&                    backface,
        const Array<Vector3>&           faceNormals);

    /**
     Welds nearby and colocated elements of the <I>oldVertexArray</I> together so that
     <I>newVertexArray</I> contains no vertices within <I>radius</I> of one another.
     Every vertex in newVertexPositions also appears in oldVertexPositions.
     This is useful for downsampling meshes and welding cracks created by artist errors
     or numerical imprecision.  

     The two integer arrays map indices back and forth between the arrays according to:
     <PRE>
     oldVertexArray[toOld[ni]] == newVertexArray[ni]
     oldVertexArray[oi] == newVertexArray[toNew[ni]]
     </PRE>

     Note that newVertexPositions is never longer than oldVertexPositions
     and is shorter when vertices are welded.

     Welding with a large radius will effectively compute a lower level of detail for
     the mesh.

     The welding method runs in roughly linear time in the length of oldVertexArray--
     a uniform spatial grid is used to achieve nearly constant time vertex collapses
     for uniformly distributed vertices.

     It is sometimes desirable to keep the original vertex ordering but 
     identify the unique vertices.  The following code computes 
     array canonical s.t. canonical[v] = first occurance of 
     a vertex near oldVertexPositions[v] in oldVertexPositions.

     <PRE>
        Array<int> canonical(oldVertexPositions.size()), toNew, toOld;
        computeWeld(oldVertexPositions, Array<Vector3>(), toNew, toOld, radius);
        for (int v = 0; v < canonical.size(); ++v) {
            canonical[v] = toOld[toNew[v]];
        }
     </PRE>

     See also G3D::MeshAlg::weldAdjacency.

     @cite The method is that described as the 'Grouper' in Baum, Mann, Smith, and Winget, 
     Making Radiosity Usable: Automatic Preprocessing and Meshing Techniques for
     the Generation of Accurate Radiosity Solutions, Computer Graphics vol 25, no 4, July 1991.
     */
    static void computeWeld(
        const Array<Vector3>& oldVertexPositions,
        Array<Vector3>&       newVertexPositions,
        Array<int>&           toNew,
        Array<int>&           toOld,
        double                radius = G3D::fuzzyEpsilon);

    /**
     Modifies the face, edge, and vertex arrays in place so that
     colocated (within radius) vertices are treated as identical.
     Note that the vertexArray and corresponding geometry will
     contain elements that are no longer used.  In the vertexArray,
     these elements are initialized to MeshAlg::Vertex() but not 
     removed (because removal would change the indexing).
     
     This is a good preprocessing step for algorithms that are only
     concerned with the shape of a mesh (e.g. cartoon rendering, fur, shadows)
     and not the indexing of the vertices.

     Use this method when you have already computed adjacency information
     and want to collapse colocated vertices within that data without
     disturbing the actual mesh vertices or indexing scheme.  
     
     If you have not computed adjacency already, use MeshAlg::computeWeld
     instead and compute adjacency information after welding.

     @param faceArray Mutated in place.  Size is maintained (degenerate
            faces are <b>not</B> removed).
     @param edgeArray Mutated in place.  May shrink if boundary edges
            are welded together.
     @param vertexArray Mutated in place.  Size is maintained (duplicate
            vertices contain no adjacency info).
    */
    static void weldAdjacency(
        const Array<Vector3>& originalGeometry,
        Array<Face>&          faceArray,
        Array<Edge>&          edgeArray,
        Array<Vertex>&        vertexArray,
        double                radius = G3D::fuzzyEpsilon);


    /**
     Counts the number of edges (in an edge array returned from 
     MeshAlg::computeAdjacency) that have only one adjacent face.
     */
    static int countBoundaryEdges(const Array<Edge>& edgeArray);

    /** @deprecated Use countBoundaryEdges */
    inline static int countBrokenEdges(const Array<Edge>& edgeArray) {
        return countBoundaryEdges(edgeArray);
    }


    /**
     Generates an array of integers from start to start + n - 1 that have run numbers
     in series then omit the next skip before the next run.  Useful for turning
     a triangle list into an indexed face set.

     Example: 
     <PRE>
       createIndexArray(10, x);
       // x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 

       createIndexArray(5, x, 2);
       // x = [2, 3, 4, 5, 6, 7] 

       createIndexArray(6, x, 0, 2, 1);
       // x = [0, 1, 3, 4, 6, 7]
     </PRE>
     */
    static void createIndexArray(
        int                 n, 
        Array<int>&         array,
        int                 start   = 0,
        int                 run     = 1,
        int                 skip    = 0);

    /**
     Computes a conservative, near-optimal axis aligned bounding box and sphere. 

      @cite The bounding sphere uses the method from J. Ritter. An effcient bounding sphere. In Andrew S. Glassner, editor, Graphics Gems. Academic Press, Boston, MA, 1990.

    */
    static void computeBounds(const Array<Vector3>& vertex, class Box& box, class Sphere& sphere);

    /** Computes bounds for a subset of the vertices.  It is ok if vertices appear more than once in the index array. */
    static void computeBounds(const Array<Vector3>& vertex, const Array<int>& index, class Box& box, class Sphere& sphere);

    /**
     In debug mode, asserts that the adjacency references between the
     face, edge, and vertex array are consistent.
     */
    static void debugCheckConsistency(
        const Array<Face>&      faceArray,
        const Array<Edge>&      edgeArray,
        const Array<Vertex>&    vertexArray);

    /** Converts quadlist (QUADS), tristrip(TRIANGLE_STRIP), and quadstrip (QUAD_STRIP)indices into triangle list (TRIANGLES)  indices. */
    template<class IndexType>
    static void toIndexedTriList(
        const Array<IndexType>& inIndices, 
        MeshAlg::Primitive      inType, 
        Array<IndexType>&       outIndices) {

        debugAssert(
            inType == MeshAlg::TRIANGLE_STRIP ||
            inType == MeshAlg::QUADS ||
            inType == MeshAlg::QUAD_STRIP);

        const int inSize = inIndices.size();

        switch(inType) {
        case MeshAlg::TRIANGLE_STRIP:
            {
            debugAssert(inSize >= 3);

            outIndices.resize((inSize - 2) * 3);

            bool atEven = false;
            for (IndexType i = 0, outIndex = 0; i <= (inSize - 2); ++i, outIndex += 3) {
                if (atEven) {
                    outIndices[outIndex] = inIndices[i + 1];
                    outIndices[outIndex + 1] = inIndices[i];
                    outIndices[outIndex + 2] = inIndices[i + 2];
                    atEven = false;
                } else {
                    outIndices[outIndex] = inIndices[i];
                    outIndices[outIndex + 1] = inIndices[i + 1];
                    outIndices[outIndex + 2] = inIndices[i + 2];
                    atEven = true;
                }
            }

            break;
            }
        case MeshAlg::QUADS:
            {
            debugAssert(inIndices.size() >= 4);

            outIndices.resize(inSize * 1.5);

            for (IndexType i = 0, outIndex = 0; i <= (inSize - 4); i += 4, outIndex += 6) {
                outIndices[outIndex] = inIndices[i];
                outIndices[outIndex + 1] = inIndices[i + 1];
                outIndices[outIndex + 2] = inIndices[i + 3];
                outIndices[outIndex + 3] = inIndices[i + 1];
                outIndices[outIndex + 4] = inIndices[i + 2];
                outIndices[outIndex + 5] = inIndices[i + 3];
            }

            break;
            }
        case MeshAlg::QUAD_STRIP:
            {
            debugAssert(inIndices.size() >= 4);

            outIndices.resize((inSize - 2) * 3);

            for (IndexType i = 0, outIndex = 0; i <= (inSize - 2); i += 2, outIndex += 6) {
                outIndices[outIndex] = inIndices[i];
                outIndices[outIndex + 1] = inIndices[i + 1];
                outIndices[outIndex + 2] = inIndices[i + 2];
                outIndices[outIndex + 3] = inIndices[i + 2];
                outIndices[outIndex + 4] = inIndices[i + 1];
                outIndices[outIndex + 5] = inIndices[i + 3];
            }
            break;
            }
        }
    }

protected:

    /**
     Helper for computeAdjacency.  If a directed edge with index e already
     exists from i0 to i1 then e is returned.  If a directed edge with index e
     already exists from i1 to i0, ~e is returned (the complement) and
     edgeArray[e] is set to f.  Otherwise, a new edge is created from i0 to i1
     with first face index f and its index is returned.
    
     @param vertexArray Vertex positions to use when deciding colocation.
     
     @param area Area of face f.  When multiple edges of the same direction 
       are found between the same vertices (usually because of degenerate edges)
       the face with larger area is kept in the edge table.
     */
    static int findEdgeIndex(
        const Array<Vector3>&   vertexArray,
        Array<Edge>&            geometricEdgeArray,
        int i0, int i1, int f, double area);
};
}
#endif

