// triobject.hpp -- terrain object made of triangles
//
// Written by Frederic Bouvier, started June 2002.
//
// Copyright (C) 2002  Frederic Bouvier - fredb@users.sourceforge.net
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; either version 2 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
// $Id: triobject.hpp,v 1.11 2005/06/25 16:31:15 fredb2 Exp $

#ifndef _triobject_hpp_
#define _triobject_hpp_

#include "bobject.hpp"

#include <simgear/math/point3d.hxx>
#include <simgear/math/sg_types.hxx>

#ifdef ABSOLUTE
#undef ABSOLUTE
#endif

#ifdef RELATIVE
#undef RELATIVE
#endif

#include <CGAL/Cartesian.h>
#include <CGAL/Polyhedron_incremental_builder_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/Point_set_2.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Constrained_triangulation_plus_2.h>

#include <vector>
#include <set>
#include <map>

class SGBinObject;

class FGSD_TriangleObject : public FGSD_BaseObject {
   public:
      typedef std::map<std::string,size_t> MaterialMap;
      typedef std::vector<std::string> MaterialList;

      template <class Gt, class Vb = CGAL::Triangulation_vertex_base_2<Gt> >
      class TriVertex : public Vb {
         typedef Vb                              Base;
      public:
         typedef typename Vb::Vertex_handle      Vertex_handle;
         typedef typename Vb::Face_handle        Face_handle;
         typedef typename Vb::Point              Point;
         typedef typename Gt::FT                 FT;
         typedef typename Gt::Point_3            Point_3;

         template < typename TDS2 >
         struct Rebind_TDS {
            typedef typename Vb::template Rebind_TDS<TDS2>::Other Vb2;
            typedef TriVertex<Gt,Vb2> Other;
         };

         TriVertex()
            : Base()
            , interpolate_z( false )
            , elev( 0 ) {}
         TriVertex(Point p, void* f = 0)
            : Base(p,f)
            , interpolate_z( false )
            , elev( 0 ) {}

         bool interpolate_z;
         FT elev;
         Point_3 normal;
      };

      template <class Gt, class Fb = CGAL::Constrained_triangulation_face_base_2<Gt> >
      class TriFace : public Fb {
         typedef Fb Base;
      public:
         typedef typename Fb::Vertex_handle      Vertex_handle;
         typedef typename Fb::Face_handle        Face_handle;
         typedef typename Gt::Point_3            Point_3;

         template < typename TDS2 >
         struct Rebind_TDS {
            typedef typename Fb::template Rebind_TDS<TDS2>::Other Fb2;
            typedef TriFace<Gt,Fb2> Other;
         };

         TriFace()
            : Base()
            , material((size_t)-1)
            , object((size_t)-1) {}
         TriFace(Vertex_handle v0, Vertex_handle v1, Vertex_handle v2)
            : Base(v0,v1,v2)
            , material((size_t)-1)
            , object((size_t)-1) {}
         TriFace(Vertex_handle v0, Vertex_handle v1, Vertex_handle v2, Face_handle n0, Face_handle n1, Face_handle n2)
            : Base(v0,v1,v2,n0,n1,n2)
            , material((size_t)-1)
            , object((size_t)-1) {}
         TriFace(Vertex_handle v0, Vertex_handle v1, Vertex_handle v2, Face_handle n0, Face_handle n1, Face_handle n2, bool c0, bool c1, bool c2)
            : Base(v0,v1,v2,n0,n1,n2,c0,c1,c2)
            , material((size_t)-1)
            , object((size_t)-1) {}

         size_t material;
         size_t object;
         Point_3 normal;
         double tex_u[3];
         double tex_v[3];
      };

      template <class Vb,class Fb>
      class TriDS : public CGAL::Triangulation_data_structure_2<Vb,Fb> {
      public:
         typedef CGAL::Triangulation_data_structure_2<Vb,Fb> Parent;
         typedef typename Parent::Vertex_handle      Vertex_handle;
         typedef typename Parent::Face_handle        Face_handle;
         Vertex_handle insert_in_face(Face_handle f) {
            Vertex_handle v = Parent::insert_in_face(f);
            Face_handle f1 = f->neighbor( 1 );
            if ( f1 != Face_handle() ) {
               f1->material = f->material;
               f1->object = f->object;
            }
            Face_handle f2 = f->neighbor( 2 );
            if ( f2 != Face_handle() ) {
               f2->material = f->material;
               f2->object = f->object;
            }
            return v;
         }
         Vertex_handle insert_in_edge(Face_handle f, int i) {
            Face_handle n = f->neighbor( i );
            int in = f->mirror_index( i );
            size_t m1 = f->material,
                   o1 = f->object,
                   m2 = n->material,
                   o2 = n->object;
            Vertex_handle v = Parent::insert_in_edge(f,i);
            Face_handle n1 = n->neighbor( CDTplus::cw( in ) );
            n1->material = m2;
            n1->object = o2;
            Face_handle n2 = n->neighbor( in );
            n2->material = m1;
            n2->object = m1;
            int in2 = n->mirror_index( in );
            Face_handle n3 = n2->neighbor( CDTplus::ccw( in2 ) );
            n3->material = m1;
            n3->object = o1;
            return v;
         }
         void flip(Face_handle f, int i) {
            Face_handle n = f->neighbor( i );
            int j = f->mirror_index( i );

            bool trc = f->is_constrained( CDTplus::ccw( i ) ),
               fc = f->is_constrained( i ),
               blc = n->is_constrained( CDTplus::ccw( j ) ),
               nc = n->is_constrained( j );
            Parent::flip( f, i );
            f->set_constraint( i, blc );
            f->set_constraint( CDTplus::ccw( i ), fc );
            n->set_constraint( j, trc );
            n->set_constraint( CDTplus::ccw( j ), nc );


            Face_handle n0 = f->neighbor(0),
                        n1 = f->neighbor(1),
                        n2 = f->neighbor(2);
            CGAL_triangulation_assertion( n0 != n1 && n1 != n2 && n2 != n0 );
            Vertex_handle v0 = f->vertex(0),
                        v1 = f->vertex(1),
                        v2 = f->vertex(2);
            CGAL_triangulation_assertion( v0 != v1 && v1 != v2 && v2 != v0 );

            n0 = n->neighbor(0),
            n1 = n->neighbor(1),
            n2 = n->neighbor(2);
            CGAL_triangulation_assertion( n0 != n1 && n1 != n2 && n2 != n0 );
            v0 = n->vertex(0),
            v1 = n->vertex(1),
            v2 = n->vertex(2);
            CGAL_triangulation_assertion( v0 != v1 && v1 != v2 && v2 != v0 );
         }
         void collapse_edge( Face_handle f, int i ) {
            Face_handle n0 = f->neighbor(0),
                        n1 = f->neighbor(1),
                        n2 = f->neighbor(2);
            CGAL_triangulation_assertion( n0 != n1 && n1 != n2 && n2 != n0 );
            Vertex_handle v0 = f->vertex(0),
                        v1 = f->vertex(1),
                        v2 = f->vertex(2);
            CGAL_triangulation_assertion( v0 != v1 && v1 != v2 && v2 != v0 );

            join_vertices( f, i );
         }
      };

      typedef CGAL::Cartesian<double>                 K;
      typedef TriVertex<K>                            _Vb;
      typedef TriFace<K>                              _Fb;
      typedef CGAL::Exact_predicates_tag              Itag;
      typedef CGAL::Constrained_Delaunay_triangulation_2<K,TriDS<_Vb,_Fb>,Itag>  CDT;
      class CDTplus : public CGAL::Constrained_triangulation_plus_2<CDT> {
         public:
            bool is_constrained_edge(CDT::Vertex_handle va, CDT::Vertex_handle vb) const {
               return hierarchy.is_constrained_edge( va, vb );
            }
      };

      struct CData {
         CData(CDTplus::Vertex_handle _v,size_t _m,size_t _o):v(_v),m(_m),o(_o){}
         CDTplus::Vertex_handle v;
         size_t m;
         size_t o;
         };
      typedef std::list<CData> CDataList;

      template <class Gt, class Vb = CGAL::Triangulation_vertex_base_2<Gt> >
      class PsVertex : public Vb {
         typedef Vb                              Base;
      public:
         typedef typename Vb::Vertex_handle      Vertex_handle;
         typedef typename Vb::Face_handle        Face_handle;
         typedef typename Vb::Point              Point;

         template < typename TDS2 >
         struct Rebind_TDS {
            typedef typename Vb::template Rebind_TDS<TDS2>::Other Vb2;
            typedef PsVertex<Gt,Vb2> Other;
         };

         PsVertex()
            : Base() {}
         PsVertex(Point p, void* f = 0)
            : Base(p,f) {}
         CDTplus::Vertex_handle v;
      };

      typedef CGAL::Triangulation_face_base_2<K>      PsFb;
      typedef CGAL::Triangulation_data_structure_2<PsVertex<K>,PsFb> PsTds;
      typedef CGAL::Point_set_2<K,PsTds>              Point_set;

      template <class Refs, class Traits>
      struct PolyVertex : public CGAL::HalfedgeDS_vertex_base<Refs,CGAL::Tag_true,typename Traits::Point_3> {
         typedef CGAL::HalfedgeDS_vertex_base<Refs,CGAL::Tag_true,typename Traits::Point_3> Parent;
         PolyVertex() {}
         PolyVertex( const PolyVertex &v )
            : Parent( v ) {}
         PolyVertex( const typename Traits::Point_3 &p )
            : Parent( p ) {}
         PolyVertex( const typename Traits::FT &x, const typename Traits::FT &y, const typename Traits::FT &z )
            : Parent( x, y, z ) {}
         typename Traits::Point_3 normal;
         CDT::Vertex_handle v;
      };

      template <class Refs, class Traits>
      struct PolyFace : public CGAL::HalfedgeDS_face_base<Refs> {
         PolyFace() {
            material = (size_t)-1;
            object = (size_t)-1;
         }
         size_t material;
         size_t object;
         typename Traits::Point_3 normal;
         double tex_u[3];
         double tex_v[3];
      };

      struct PolyItems : public CGAL::Polyhedron_items_3 {
         template <class Refs, class Traits>
         struct Vertex_wrapper {
            typedef typename Traits::Point_3 Point;
            typedef PolyVertex<Refs,Traits> Vertex;
         };
         template <class Refs, class Traits>
         struct Face_wrapper {
            typedef PolyFace<Refs,Traits> Face;
         };
      };

      typedef CGAL::Polyhedron_3<K,PolyItems>         Polyhedron;
      typedef Polyhedron::HalfedgeDS                  HalfedgeDS;

      //
      template <class T>
      class CompareHandle {
      public:
         int operator()( const T &left, const T &right ) const {
            return left.node < right.node;
         }
      };
      // .
      class SplitPolyhedron : public CGAL::Modifier_base<HalfedgeDS> {
      public:
         SplitPolyhedron( Polyhedron &o, double v, bool h, bool g )
            : orig( o ), value( v ), horizontal( h ), greater( g ) {}
         void operator()( HalfedgeDS& hds );
      private:
         Polyhedron &orig;
         double value;
         bool horizontal;
         bool greater;
      };
      // .
      class LoadObject : public CGAL::Modifier_base<HalfedgeDS> {
      public:
         struct ErrorCondition {
            enum { Tris, Strips, Fans } type;
            size_t i1;
            size_t i2;
         };
         LoadObject( FGSD_TriangleObject &t, SGBinObject &o, size_t i ) : object( o ), tri( t ), iObj( i ) {}
         void operator()( HalfedgeDS& hds );
      private:
         SGBinObject &object;
         FGSD_TriangleObject &tri;
         size_t iObj;
      };

      enum ConstraintType { C_MATERIAL, C_HYPSO };
      struct Constraint {
         std::list<CDTplus::Vertex_handle> _vertices;
         ConstraintType _type;
      };

      struct PointFeature {
         std::string material;
         point_list points;
         point_list normals;
      };
      typedef std::vector<PointFeature> PointFeatureList;
      typedef std::map<int, PointFeatureList> PointsByObjectsMap;

   public:
      FGSD_TriangleObject( FGSD_Tile *__tile );
      ~FGSD_TriangleObject();

      bool load( const char *path, bool isTerrain );
      bool save( const std::string &path, bool objectBase, bool object );
      bool saveAscii( const std::string &path, bool objectBase, bool object );
      bool saveObject( const std::string &path, const char *name, size_t iObj );
      bool saveObjectAscii( const std::string &path, const char *name, size_t iObj );
      void draw( double alpha, bool lines, DrawType drawType, double minx, double maxx, double miny, double maxy, double zLevel );
      bool propertiesUnderMouse( double lon, double lat, double &height, std::string &material, std::string &airportID ) const;
      bool objectUnderMouse( double lon, double lat, double zLevel );
      bool visible( double minx, double maxx, double miny, double maxy ) const;
      bool visible( double lon, double lat ) const;
      std::string getName() const;
      void *convertTo( FGSD_BaseObject::ObjectType __type );
      bool changeMaterial( const std::string &mat, double lon, double lat );

      void getAirportList( std::vector<std::string> &__aptList ) const;

      void changeCurrentPointPosition( double __lon, double __lat );
      bool xlock( bool &__min );
      bool ylock( bool &__min );
      bool interior() const;
      void changeCurrentPointHeight( double __height );
      bool getPointPosition( size_t __index, double &__lon, double &__lat ) const;

      Point3D current() const;
      void setCurrent( const Point3D &p );

      void postLoad();

      size_t nbObjects() const;
      std::string objectName( size_t i ) const;

      bool addPolyhedron( Polyhedron &p, bool terrain, size_t o, double minx, double maxx, double miny, double maxy );

      CDTplus::Vertex_handle embedPoint( const Point3D &p );
      void embedEdge( CDTplus::Vertex_handle va, CDTplus::Vertex_handle vb );

      void recoverFaceData();

   public:
      static std::vector<std::vector<FGSD_TriangleObject *> > _objectSpan;
      static Point_set _pointSet;
      static std::vector<Polyhedron *> _outSurfaceList;
      static std::vector<size_t> _outObjectList;

   private:
      size_t findMaterial( const std::string &mat );
      double calc_gbs( const point_list &nodes, Point3D &gbs_center );
      bool setMaterialThruEdge( CDTplus::Face_handle f, int i );
      void cutPolyhedron( Polyhedron &p, double value, bool horizontally );
      bool pointInsideBoundingPoly( Point3D p0 ) const;
      void replaceVertex( CDTplus::Vertex_handle va, CDTplus::Vertex_handle vb );
      CDTplus::Vertex_handle replaceVertex( CDTplus::Vertex_handle va, const CDTplus::Point &p );

   private:
      std::string _name;
      std::vector<size_t> _objects;

      static MaterialMap _materialMap;
      static MaterialList _materialList;
      static std::vector<std::string> _objectName;
      static std::map<std::string,size_t> _objectNameMap;

      double _minx;
      double _maxx;
      double _miny;
      double _maxy;

      double _vminx;
      double _vmaxx;
      double _vminy;
      double _vmaxy;

      bool _xlock;
      bool _ylock;

      CDTplus::Vertex_handle _curPt;

      CDTplus _surface;
      CDTplus::Face_handle _lastLocate;

      PointsByObjectsMap _ptsFeatures;
};

inline
size_t FGSD_TriangleObject::nbObjects() const
{
   return _objects.size();
}

inline
std::string FGSD_TriangleObject::objectName( size_t i ) const
{
   return i < _objects.size() ? _objectName[ _objects[i] ] : std::string();
}

#endif