intern/view_map/Silhouette.h

/*
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 */

#pragma once

/** \file
 * \ingroup freestyle
 * \brief Classes to define a silhouette structure
 */

#include <float.h>
#include <iostream>
#include <set>
#include <string>
#include <vector>

#include "Interface0D.h"
#include "Interface1D.h"

#include "../geometry/BBox.h"
#include "../geometry/Geom.h"
#include "../geometry/Polygon.h"

#include "../scene_graph/FrsMaterial.h"

#include "../system/Exception.h"
#include "../system/FreestyleConfig.h"

#include "../winged_edge/Curvature.h"

#ifdef WITH_CXX_GUARDEDALLOC
#  include "MEM_guardedalloc.h"
#endif

using namespace std;

namespace Freestyle {

using namespace Geometry;

class ViewShape;
typedef vector<ViewShape *> occluder_container;

/**********************************/
/*                                */
/*                                */
/*             SVertex            */
/*                                */
/*                                */
/**********************************/

class FEdge;
class ViewVertex;
class SShape;

/*! Class to define a vertex of the embedding. */
class SVertex : public Interface0D {
 public:  // Implementation of Interface0D
  /*! Returns the string "SVertex" .*/
  virtual string getExactTypeName() const
  {
    return "SVertex";
  }

  // Data access methods
  /*! Returns the 3D x coordinate of the vertex .*/
  virtual real getX() const
  {
    return _Point3D.x();
  }

  /*! Returns the 3D y coordinate of the vertex .*/
  virtual real getY() const
  {
    return _Point3D.y();
  }

  /*! Returns the 3D z coordinate of the vertex .*/
  virtual real getZ() const
  {
    return _Point3D.z();
  }

  /*!  Returns the 3D point. */
  virtual Vec3r getPoint3D() const
  {
    return _Point3D;
  }

  /*! Returns the projected 3D  x coordinate of the vertex .*/
  virtual real getProjectedX() const
  {
    return _Point2D.x();
  }

  /*! Returns the projected 3D  y coordinate of the vertex .*/
  virtual real getProjectedY() const
  {
    return _Point2D.y();
  }

  /*! Returns the projected 3D  z coordinate of the vertex .*/
  virtual real getProjectedZ() const
  {
    return _Point2D.z();
  }

  /*!  Returns the 2D point. */
  virtual Vec2r getPoint2D() const
  {
    return Vec2r(_Point2D.x(), _Point2D.y());
  }

  /*! Returns the FEdge that lies between this Svertex and the Interface0D given as argument. */
  virtual FEdge *getFEdge(Interface0D &);

  /*! Returns the Id of the vertex .*/
  virtual Id getId() const
  {
    return _Id;
  }

  /*! Returns the nature of the vertex .*/
  virtual Nature::VertexNature getNature() const;

  /*! Cast the Interface0D in SVertex if it can be. */
  virtual SVertex *castToSVertex();

  /*! Cast the Interface0D in ViewVertex if it can be. */
  virtual ViewVertex *castToViewVertex();

  /*! Cast the Interface0D in NonTVertex if it can be. */
  virtual NonTVertex *castToNonTVertex();

  /*! Cast the Interface0D in TVertex if it can be. */
  virtual TVertex *castToTVertex();

 public:
  typedef vector<FEdge *> fedges_container;

 private:
  Id _Id;
  Vec3r _Point3D;
  Vec3r _Point2D;
  set<Vec3r> _Normals;
  vector<FEdge *> _FEdges;   // the edges containing this vertex
  SShape *_Shape;            // the shape to which belongs the vertex
  ViewVertex *_pViewVertex;  // The associated viewvertex, in case there is one.
#if 0
  real _curvatureFredo;
  Vec2r _directionFredo;
#endif
  CurvatureInfo *_curvature_info;

 public:
  /*! A field that can be used by the user to store any data.
   *  This field must be reset afterwards using ResetUserData().
   */
  void *userdata;

  /*! Default constructor.*/
  inline SVertex()
  {
    _Id = 0;
    userdata = NULL;
    _Shape = NULL;
    _pViewVertex = 0;
    _curvature_info = 0;
  }

  /*! Builds a SVertex from 3D coordinates and an Id. */
  inline SVertex(const Vec3r &iPoint3D, const Id &id)
  {
    _Point3D = iPoint3D;
    _Id = id;
    userdata = NULL;
    _Shape = NULL;
    _pViewVertex = 0;
    _curvature_info = 0;
  }

  /*! Copy constructor. */
  inline SVertex(SVertex &iBrother)
  {
    _Id = iBrother._Id;
    _Point3D = iBrother.point3D();
    _Point2D = iBrother.point2D();
    _Normals = iBrother._Normals;
    _FEdges = iBrother.fedges();
    _Shape = iBrother.shape();
    _pViewVertex = iBrother._pViewVertex;
    if (!(iBrother._curvature_info)) {
      _curvature_info = 0;
    }
    else {
      _curvature_info = new CurvatureInfo(*(iBrother._curvature_info));
    }
    iBrother.userdata = this;
    userdata = 0;
  }

  /*! Destructor. */
  virtual ~SVertex()
  {
    if (_curvature_info) {
      delete _curvature_info;
    }
  }

  /*! Cloning method. */
  virtual SVertex *duplicate()
  {
    SVertex *clone = new SVertex(*this);
    return clone;
  }

  /*! operator == */
  virtual bool operator==(const SVertex &iBrother)
  {
    return ((_Point2D == iBrother._Point2D) && (_Point3D == iBrother._Point3D));
  }

  /* accessors */
  inline const Vec3r &point3D() const
  {
    return _Point3D;
  }

  inline const Vec3r &point2D() const
  {
    return _Point2D;
  }

  /*! Returns the set of normals for this Vertex.
   *  In a smooth surface, a vertex has exactly one normal.
   *  In a sharp surface, a vertex can have any number of normals.
   */
  inline set<Vec3r> normals()
  {
    return _Normals;
  }

  /*! Returns the number of different normals for this vertex. */
  inline unsigned normalsSize() const
  {
    return _Normals.size();
  }

  inline const vector<FEdge *> &fedges()
  {
    return _FEdges;
  }

  inline fedges_container::iterator fedges_begin()
  {
    return _FEdges.begin();
  }

  inline fedges_container::iterator fedges_end()
  {
    return _FEdges.end();
  }

  inline SShape *shape()
  {
    return _Shape;
  }

  inline real z() const
  {
    return _Point2D[2];
  }

  /*! If this SVertex is also a ViewVertex, this method returns a pointer onto this ViewVertex.
   *  0 is returned otherwise.
   */
  inline ViewVertex *viewvertex()
  {
    return _pViewVertex;
  }

  /*! modifiers */
  /*! Sets the 3D coordinates of the SVertex. */
  inline void setPoint3D(const Vec3r &iPoint3D)
  {
    _Point3D = iPoint3D;
  }

  /*! Sets the 3D projected coordinates of the SVertex. */
  inline void setPoint2D(const Vec3r &iPoint2D)
  {
    _Point2D = iPoint2D;
  }

  /*! Adds a normal to the Svertex's set of normals. If the same normal is already in the set,
   * nothing changes. */
  inline void AddNormal(const Vec3r &iNormal)
  {
    _Normals.insert(iNormal);  // if iNormal in the set already exists, nothing is done
  }

  void setCurvatureInfo(CurvatureInfo *ci)
  {
    if (_curvature_info) {  // Q. is this an error condition? (T.K. 02-May-2011)
      delete _curvature_info;
    }
    _curvature_info = ci;
  }

  const CurvatureInfo *getCurvatureInfo() const
  {
    return _curvature_info;
  }

#if 0
  /* Fredo's normal and curvature*/
  void setCurvatureFredo(real c)
  {
    _curvatureFredo = c;
  }

  void setDirectionFredo(Vec2r d)
  {
    _directionFredo = d;
  }

  real curvatureFredo()
  {
    return _curvatureFredo;
  }

  const Vec2r directionFredo()
  {
    return _directionFredo;
  }
#endif

  /*! Sets the Id */
  inline void setId(const Id &id)
  {
    _Id = id;
  }

  inline void setFEdges(const vector<FEdge *> &iFEdges)
  {
    _FEdges = iFEdges;
  }

  inline void setShape(SShape *iShape)
  {
    _Shape = iShape;
  }

  inline void setViewVertex(ViewVertex *iViewVertex)
  {
    _pViewVertex = iViewVertex;
  }

  /*! Add an FEdge to the list of edges emanating from this SVertex. */
  inline void AddFEdge(FEdge *iFEdge)
  {
    _FEdges.push_back(iFEdge);
  }

  /*! Remove an FEdge from the list of edges emanating from this SVertex. */
  inline void RemoveFEdge(FEdge *iFEdge)
  {
    for (vector<FEdge *>::iterator fe = _FEdges.begin(), fend = _FEdges.end(); fe != fend; fe++) {
      if (iFEdge == (*fe)) {
        _FEdges.erase(fe);
        break;
      }
    }
  }

  /* replaces edge 1 by edge 2 in the list of edges */
  inline void Replace(FEdge *e1, FEdge *e2)
  {
    vector<FEdge *>::iterator insertedfe;
    for (vector<FEdge *>::iterator fe = _FEdges.begin(), fend = _FEdges.end(); fe != fend; fe++) {
      if ((*fe) == e1) {
        insertedfe = _FEdges.insert(fe, e2);  // inserts e2 before fe.
        // returns an iterator pointing toward e2. fe is invalidated.
        // we want to remove e1, but we can't use fe anymore:
        ++insertedfe;  // insertedfe points now to e1
        _FEdges.erase(insertedfe);
        return;
      }
    }
  }

 public:
  /* Information access interface */
  FEdge *fedge();  // for non T vertex

  inline const Vec3r &point2d() const
  {
    return point2D();
  }

  inline const Vec3r &point3d() const
  {
    return point3D();
  }

  inline Vec3r normal() const
  {
    if (_Normals.size() == 1) {
      return (*(_Normals.begin()));
    }
    Exception::raiseException();
    return *(_Normals.begin());
  }

  // Material material() const ;
  Id shape_id() const;
  const SShape *shape() const;
  float shape_importance() const;

  int qi() const;
  occluder_container::const_iterator occluders_begin() const;
  occluder_container::const_iterator occluders_end() const;
  bool occluders_empty() const;
  int occluders_size() const;
  const Polygon3r &occludee() const;
  const SShape *occluded_shape() const;
  bool occludee_empty() const;
  real z_discontinuity() const;
#if 0
  inline float local_average_depth() const;
  inline float local_depth_variance() const;
  inline real local_average_density(float sigma = 2.3f) const;
  inline Vec3r shaded_color() const;
  inline Vec3r orientation2d() const;
  inline Vec3r orientation3d() const;
  inline Vec3r curvature2d_as_vector() const;
  /*! angle in radians */
  inline real curvature2d_as_angle() const;
#endif

#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SVertex")
#endif
};

/**********************************/
/*                                */
/*                                */
/*             FEdge              */
/*                                */
/*                                */
/**********************************/

class ViewEdge;

/*! Base Class for feature edges.
 *  This FEdge can represent a silhouette, a crease, a ridge/valley, a border or a suggestive
 * contour. For silhouettes,  the FEdge is oriented such as, the visible face lies on the left of
 * the edge. For borders, the FEdge is oriented such as, the face lies on the left of the edge. An
 * FEdge can represent an initial edge of the mesh or runs across a face of the initial mesh
 * depending on the smoothness or sharpness of the mesh. This class is specialized into a smooth
 * and a sharp version since their properties slightly vary from one to the other.
 */
class FEdge : public Interface1D {
 public:  // Implementation of Interface0D
  /*! Returns the string "FEdge". */
  virtual string getExactTypeName() const
  {
    return "FEdge";
  }

  // Data access methods

  /*! Returns the 2D length of the FEdge. */
  virtual real getLength2D() const
  {
    if (!_VertexA || !_VertexB) {
      return 0;
    }
    return (_VertexB->getPoint2D() - _VertexA->getPoint2D()).norm();
  }

  /*! Returns the Id of the FEdge. */
  virtual Id getId() const
  {
    return _Id;
  }

 public:
  // An edge can only be of one kind (SILHOUETTE or BORDER, etc...)
  // For an multi-nature edge there must be several different FEdge.
  //  DEBUG:
  //  Vec3r A;
  //  Vec3r u;
  //  vector<Polygon3r> _Occludees;
  //  Vec3r intersection;
  //  vector<Vec3i> _Cells;

 protected:
  SVertex *_VertexA;
  SVertex *_VertexB;
  Id _Id;
  Nature::EdgeNature _Nature;
  // vector<Polygon3r> _Occluders; // visibility // NOT HANDLED BY THE COPY CONSTRUCTOR!!

  FEdge *_NextEdge;  // next edge on the chain
  FEdge *_PreviousEdge;
  ViewEdge *_ViewEdge;
  // Sometimes we need to deport the visibility computation onto another edge. For example the
  // exact edges use edges of the mesh to compute their visibility

  Polygon3r _aFace;  // The occluded face which lies on the right of a silhouette edge
  Vec3r _occludeeIntersection;
  bool _occludeeEmpty;

  bool _isSmooth;

  bool _isInImage;

  bool _isTemporary;

 public:
  /*! A field that can be used by the user to store any data.
   *  This field must be reset afterwards using ResetUserData().
   */
  void *userdata;

  /*! Default constructor */
  inline FEdge()
  {
    userdata = NULL;
    _VertexA = NULL;
    _VertexB = NULL;
    _Nature = Nature::NO_FEATURE;
    _NextEdge = NULL;
    _PreviousEdge = NULL;
    _ViewEdge = NULL;
    //_hasVisibilityPoint = false;
    _occludeeEmpty = true;
    _isSmooth = false;
    _isInImage = true;
    _isTemporary = false;
  }

  /*! Builds an FEdge going from vA to vB. */
  inline FEdge(SVertex *vA, SVertex *vB)
  {
    userdata = NULL;
    _VertexA = vA;
    _VertexB = vB;
    _Nature = Nature::NO_FEATURE;
    _NextEdge = NULL;
    _PreviousEdge = NULL;
    _ViewEdge = NULL;
    //_hasVisibilityPoint = false;
    _occludeeEmpty = true;
    _isSmooth = false;
    _isInImage = true;
    _isTemporary = false;
  }

  /*! Copy constructor */
  inline FEdge(FEdge &iBrother)
  {
    _VertexA = iBrother.vertexA();
    _VertexB = iBrother.vertexB();
    _NextEdge = iBrother.nextEdge();
    _PreviousEdge = iBrother._PreviousEdge;
    _Nature = iBrother.getNature();
    _Id = iBrother._Id;
    _ViewEdge = iBrother._ViewEdge;
    //_hasVisibilityPoint = iBrother._hasVisibilityPoint;
    //_VisibilityPointA = iBrother._VisibilityPointA;
    //_VisibilityPointB = iBrother._VisibilityPointB;
    _aFace = iBrother._aFace;
    _occludeeEmpty = iBrother._occludeeEmpty;
    _isSmooth = iBrother._isSmooth;
    _isInImage = iBrother._isInImage;
    _isTemporary = iBrother._isTemporary;
    iBrother.userdata = this;
    userdata = 0;
  }

  /*! Destructor */
  virtual ~FEdge()
  {
  }

  /*! Cloning method. */
  virtual FEdge *duplicate()
  {
    FEdge *clone = new FEdge(*this);
    return clone;
  }

  /* accessors */
  /*! Returns the first SVertex. */
  inline SVertex *vertexA()
  {
    return _VertexA;
  }

  /*! Returns the second SVertex. */
  inline SVertex *vertexB()
  {
    return _VertexB;
  }

  /*! Returns the first SVertex if i=0, the second SVertex if i=1. */
  inline SVertex *operator[](const unsigned short int &i) const
  {
    return (i % 2 == 0) ? _VertexA : _VertexB;
  }

  /*! Returns the nature of the FEdge. */
  inline Nature::EdgeNature getNature() const
  {
    return _Nature;
  }

  /*! Returns the FEdge following this one in the ViewEdge.
   *  If this FEdge is the last of the ViewEdge, 0 is returned.
   */
  inline FEdge *nextEdge()
  {
    return _NextEdge;
  }

  /*! Returns the Edge preceding this one in the ViewEdge.
   *  If this FEdge is the first one of the ViewEdge, 0 is returned.
   */
  inline FEdge *previousEdge()
  {
    return _PreviousEdge;
  }

  inline SShape *shape()
  {
    return _VertexA->shape();
  }

#if 0
  inline int invisibility() const
  {
    return _Occluders.size();
  }
#endif

  int invisibility() const;

#if 0
  inline const vector<Polygon3r> &occluders() const
  {
    return _Occluders;
  }
#endif

  /*! Returns a pointer to the ViewEdge to which this FEdge belongs to. */
  inline ViewEdge *viewedge() const
  {
    return _ViewEdge;
  }

  inline Vec3r center3d()
  {
    return Vec3r((_VertexA->point3D() + _VertexB->point3D()) / 2.0);
  }

  inline Vec3r center2d()
  {
    return Vec3r((_VertexA->point2D() + _VertexB->point2D()) / 2.0);
  }

#if 0
  inline bool hasVisibilityPoint() const
  {
    return _hasVisibilityPoint;
  }

  inline Vec3r visibilityPointA() const
  {
    return _VisibilityPointA;
  }

  inline Vec3r visibilityPointB() const
  {
    return _VisibilityPointB;
  }
#endif

  inline const Polygon3r &aFace() const
  {
    return _aFace;
  }

  inline const Vec3r &getOccludeeIntersection()
  {
    return _occludeeIntersection;
  }

  inline bool getOccludeeEmpty()
  {
    return _occludeeEmpty;
  }

  /*! Returns true if this FEdge is a smooth FEdge. */
  inline bool isSmooth() const
  {
    return _isSmooth;
  }

  inline bool isInImage() const
  {
    return _isInImage;
  }

  inline bool isTemporary() const
  {
    return _isTemporary;
  }

  /* modifiers */
  /*! Sets the first SVertex. */
  inline void setVertexA(SVertex *vA)
  {
    _VertexA = vA;
  }

  /*! Sets the second SVertex. */
  inline void setVertexB(SVertex *vB)
  {
    _VertexB = vB;
  }

  /*! Sets the FEdge Id . */
  inline void setId(const Id &id)
  {
    _Id = id;
  }

  /*! Sets the pointer to the next FEdge. */
  inline void setNextEdge(FEdge *iEdge)
  {
    _NextEdge = iEdge;
  }

  /*! Sets the pointer to the previous FEdge. */
  inline void setPreviousEdge(FEdge *iEdge)
  {
    _PreviousEdge = iEdge;
  }

  /*! Sets the nature of this FEdge. */
  inline void setNature(Nature::EdgeNature iNature)
  {
    _Nature = iNature;
  }

#if 0
  inline void AddOccluder(Polygon3r &iPolygon)
  {
    _Occluders.push_back(iPolygon);
  }
#endif

  /*! Sets the ViewEdge to which this FEdge belongs to. */
  inline void setViewEdge(ViewEdge *iViewEdge)
  {
    _ViewEdge = iViewEdge;
  }

#if 0
  inline void setHasVisibilityPoint(bool iBool)
  {
    _hasVisibilityPoint = iBool;
  }

  inline void setVisibilityPointA(const Vec3r &iPoint)
  {
    _VisibilityPointA = iPoint;
  }

  inline void setVisibilityPointB(const Vec3r &iPoint)
  {
    _VisibilityPointB = iPoint;
  }
#endif

  inline void setaFace(Polygon3r &iFace)
  {
    _aFace = iFace;
  }

  inline void setOccludeeIntersection(const Vec3r &iPoint)
  {
    _occludeeIntersection = iPoint;
  }

  inline void setOccludeeEmpty(bool iempty)
  {
    _occludeeEmpty = iempty;
  }

  /*! Sets the flag telling whether this FEdge is smooth or sharp.
   *  true for Smooth, false for Sharp.
   */
  inline void setSmooth(bool iFlag)
  {
    _isSmooth = iFlag;
  }

  inline void setIsInImage(bool iFlag)
  {
    _isInImage = iFlag;
  }

  inline void setTemporary(bool iFlag)
  {
    _isTemporary = iFlag;
  }

  /* checks whether two FEdge have a common vertex.
   *  Returns a pointer on the common vertex if it exists, NULL otherwise.
   */
  static inline SVertex *CommonVertex(FEdge *iEdge1, FEdge *iEdge2)
  {
    if ((NULL == iEdge1) || (NULL == iEdge2)) {
      return NULL;
    }

    SVertex *sv1 = iEdge1->vertexA();
    SVertex *sv2 = iEdge1->vertexB();
    SVertex *sv3 = iEdge2->vertexA();
    SVertex *sv4 = iEdge2->vertexB();

    if ((sv1 == sv3) || (sv1 == sv4)) {
      return sv1;
    }
    else if ((sv2 == sv3) || (sv2 == sv4)) {
      return sv2;
    }

    return NULL;
  }

  inline const SVertex *min2d() const
  {
    if (_VertexA->point2D() < _VertexB->point2D()) {
      return _VertexA;
    }
    else {
      return _VertexB;
    }
  }

  inline const SVertex *max2d() const
  {
    if (_VertexA->point2D() < _VertexB->point2D()) {
      return _VertexB;
    }
    else {
      return _VertexA;
    }
  }

  /* Information access interface */

  // Material material() const;
  Id shape_id() const;
  const SShape *shape() const;
  float shape_importance() const;

  inline const int qi() const
  {
    return invisibility();
  }

  occluder_container::const_iterator occluders_begin() const;
  occluder_container::const_iterator occluders_end() const;
  bool occluders_empty() const;
  int occluders_size() const;

  inline const Polygon3r &occludee() const
  {
    return aFace();
  }

  const SShape *occluded_shape() const;

#if 0
  inline const bool occludee_empty() const
  {
    return _occludeeEmpty;
  }
#endif

  bool occludee_empty() const;
  real z_discontinuity() const;

#if 0
  inline float local_average_depth(int iCombination = 0) const;
  inline float local_depth_variance(int iCombination = 0) const;
  inline real local_average_density(float sigma = 2.3f, int iCombination = 0) const;
  inline Vec3r shaded_color(int iCombination = 0) const
  {
  }
#endif

  int viewedge_nature() const;

  // float viewedge_length() const;

  inline Vec3r orientation2d() const
  {
    return Vec3r(_VertexB->point2d() - _VertexA->point2d());
  }

  inline Vec3r orientation3d() const
  {
    return Vec3r(_VertexB->point3d() - _VertexA->point3d());
  }

#if 0
  inline real curvature2d() const
  {
    return viewedge()->curvature2d((_VertexA->point2d() + _VertexB->point2d()) / 2.0);
  }

  inline Vec3r curvature2d_as_vector(int iCombination = 0) const;

  /* angle in degrees*/
  inline real curvature2d_as_angle(int iCombination = 0) const;
#endif

  // Iterator access (Interface1D)
  /*! Returns an iterator over the 2 (!) SVertex pointing to the first SVertex. */
  virtual inline Interface0DIterator verticesBegin();

  /*! Returns an iterator over the 2 (!) SVertex pointing after the last SVertex. */
  virtual inline Interface0DIterator verticesEnd();

  /*! Returns an iterator over the FEdge points, pointing to the first point. The difference with
   * verticesBegin() is that here we can iterate over points of the FEdge at a any given sampling.
   *  Indeed, for each iteration, a virtual point is created.
   *  \param t:
   *    The sampling with which we want to iterate over points of this FEdge.
   */
  virtual inline Interface0DIterator pointsBegin(float t = 0.0f);

  /*! Returns an iterator over the FEdge points, pointing after the last point. The difference with
   * verticesEnd() is that here we can iterate over points of the FEdge at a any given sampling.
   *  Indeed, for each iteration, a virtual point is created.
   *  \param t:
   *    The sampling with which we want to iterate over points of this FEdge.
   */
  virtual inline Interface0DIterator pointsEnd(float t = 0.0f);

#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:FEdge")
#endif
};

//
// SVertexIterator
//
/////////////////////////////////////////////////

namespace FEdgeInternal {

class SVertexIterator : public Interface0DIteratorNested {
 public:
  SVertexIterator()
  {
    _vertex = NULL;
    _edge = NULL;
  }

  SVertexIterator(const SVertexIterator &vi)
  {
    _vertex = vi._vertex;
    _edge = vi._edge;
  }

  SVertexIterator(SVertex *v, FEdge *edge)
  {
    _vertex = v;
    _edge = edge;
  }

  SVertexIterator &operator=(const SVertexIterator &vi)
  {
    _vertex = vi._vertex;
    _edge = vi._edge;
    return *this;
  }

  virtual string getExactTypeName() const
  {
    return "SVertexIterator";
  }

  virtual SVertex &operator*()
  {
    return *_vertex;
  }

  virtual SVertex *operator->()
  {
    return &(operator*());
  }

  virtual SVertexIterator &operator++()
  {
    increment();
    return *this;
  }

  virtual SVertexIterator operator++(int)
  {
    SVertexIterator ret(*this);
    increment();
    return ret;
  }

  virtual SVertexIterator &operator--()
  {
    decrement();
    return *this;
  }

  virtual SVertexIterator operator--(int)
  {
    SVertexIterator ret(*this);
    decrement();
    return ret;
  }

  virtual int increment()
  {
    if (_vertex == _edge->vertexB()) {
      _vertex = 0;
      return 0;
    }
    _vertex = _edge->vertexB();
    return 0;
  }

  virtual int decrement()
  {
    if (_vertex == _edge->vertexA()) {
      _vertex = 0;
      return 0;
    }
    _vertex = _edge->vertexA();
    return 0;
  }

  virtual bool isBegin() const
  {
    return _vertex == _edge->vertexA();
  }

  virtual bool isEnd() const
  {
    return _vertex == _edge->vertexB();
  }

  virtual bool operator==(const Interface0DIteratorNested &it) const
  {
    const SVertexIterator *it_exact = dynamic_cast<const SVertexIterator *>(&it);
    if (!it_exact) {
      return false;
    }
    return ((_vertex == it_exact->_vertex) && (_edge == it_exact->_edge));
  }

  virtual float t() const
  {
    if (_vertex == _edge->vertexA()) {
      return 0.0f;
    }
    return ((float)_edge->getLength2D());
  }
  virtual float u() const
  {
    if (_vertex == _edge->vertexA()) {
      return 0.0f;
    }
    return 1.0f;
  }

  virtual SVertexIterator *copy() const
  {
    return new SVertexIterator(*this);
  }

 private:
  SVertex *_vertex;
  FEdge *_edge;
};

}  // end of namespace FEdgeInternal

// Iterator access (implementation)

Interface0DIterator FEdge::verticesBegin()
{
  Interface0DIterator ret(new FEdgeInternal::SVertexIterator(_VertexA, this));
  return ret;
}

Interface0DIterator FEdge::verticesEnd()
{
  Interface0DIterator ret(new FEdgeInternal::SVertexIterator(0, this));
  return ret;
}

Interface0DIterator FEdge::pointsBegin(float /*t*/)
{
  return verticesBegin();
}

Interface0DIterator FEdge::pointsEnd(float /*t*/)
{
  return verticesEnd();
}

/*! Class defining a sharp FEdge. A Sharp FEdge corresponds to an initial edge of the input mesh.
 *  It can be a silhouette, a crease or a border. If it is a crease edge, then it is bordered
 *  by two faces of the mesh. Face a lies on its right whereas Face b lies on its left.
 *  If it is a border edge, then it doesn't have any face on its right, and thus Face a = 0.
 */
class FEdgeSharp : public FEdge {
 protected:
  Vec3r _aNormal;  // When following the edge, normal of the right face
  Vec3r _bNormal;  // When following the edge, normal of the left face
  unsigned _aFrsMaterialIndex;
  unsigned _bFrsMaterialIndex;
  bool _aFaceMark;
  bool _bFaceMark;

 public:
  /*! Returns the string "FEdgeSharp" . */
  virtual string getExactTypeName() const
  {
    return "FEdgeSharp";
  }

  /*! Default constructor. */
  inline FEdgeSharp() : FEdge()
  {
    _aFrsMaterialIndex = _bFrsMaterialIndex = 0;
    _aFaceMark = _bFaceMark = false;
  }

  /*! Builds an FEdgeSharp going from vA to vB. */
  inline FEdgeSharp(SVertex *vA, SVertex *vB) : FEdge(vA, vB)
  {
    _aFrsMaterialIndex = _bFrsMaterialIndex = 0;
    _aFaceMark = _bFaceMark = false;
  }

  /*! Copy constructor. */
  inline FEdgeSharp(FEdgeSharp &iBrother) : FEdge(iBrother)
  {
    _aNormal = iBrother._aNormal;
    _bNormal = iBrother._bNormal;
    _aFrsMaterialIndex = iBrother._aFrsMaterialIndex;
    _bFrsMaterialIndex = iBrother._bFrsMaterialIndex;
    _aFaceMark = iBrother._aFaceMark;
    _bFaceMark = iBrother._bFaceMark;
  }

  /*! Destructor. */
  virtual ~FEdgeSharp()
  {
  }

  /*! Cloning method. */
  virtual FEdge *duplicate()
  {
    FEdge *clone = new FEdgeSharp(*this);
    return clone;
  }

  /*! Returns the normal to the face lying on the right of the FEdge. If this FEdge is a border,
   *  it has no Face on its right and therefore, no normal.
   */
  inline const Vec3r &normalA()
  {
    return _aNormal;
  }

  /*! Returns the normal to the face lying on the left of the FEdge. */
  inline const Vec3r &normalB()
  {
    return _bNormal;
  }

  /*! Returns the index of the material of the face lying on the
   *  right of the FEdge. If this FEdge is a border,
   *  it has no Face on its right and therefore, no material.
   */
  inline unsigned aFrsMaterialIndex() const
  {
    return _aFrsMaterialIndex;
  }

  /*! Returns the material of the face lying on the right of the FEdge. If this FEdge is a border,
   *  it has no Face on its right and therefore, no material.
   */
  const FrsMaterial &aFrsMaterial() const;

  /*! Returns the index of the material of the face lying on the left of the FEdge. */
  inline unsigned bFrsMaterialIndex() const
  {
    return _bFrsMaterialIndex;
  }

  /*! Returns the  material of the face lying on the left of the FEdge. */
  const FrsMaterial &bFrsMaterial() const;

  /*! Returns the face mark of the face lying on the right of the FEdge.
   *  If this FEdge is a border, it has no Face on its right and thus false is returned.
   */
  inline bool aFaceMark() const
  {
    return _aFaceMark;
  }

  /*! Returns the face mark of the face lying on the left of the FEdge. */
  inline bool bFaceMark() const
  {
    return _bFaceMark;
  }

  /*! Sets the normal to the face lying on the right of the FEdge. */
  inline void setNormalA(const Vec3r &iNormal)
  {
    _aNormal = iNormal;
  }

  /*! Sets the normal to the face lying on the left of the FEdge. */
  inline void setNormalB(const Vec3r &iNormal)
  {
    _bNormal = iNormal;
  }

  /*! Sets the index of the material lying on the right of the FEdge.*/
  inline void setaFrsMaterialIndex(unsigned i)
  {
    _aFrsMaterialIndex = i;
  }

  /*! Sets the index of the material lying on the left of the FEdge.*/
  inline void setbFrsMaterialIndex(unsigned i)
  {
    _bFrsMaterialIndex = i;
  }

  /*! Sets the face mark of the face lying on the right of the FEdge. */
  inline void setaFaceMark(bool iFaceMark)
  {
    _aFaceMark = iFaceMark;
  }

  /*! Sets the face mark of the face lying on the left of the FEdge. */
  inline void setbFaceMark(bool iFaceMark)
  {
    _bFaceMark = iFaceMark;
  }

#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:FEdgeSharp")
#endif
};

/*! Class defining a smooth edge. This kind of edge typically runs across a face of the input mesh.
 * It can be a silhouette, a ridge or valley, a suggestive contour.
 */
class FEdgeSmooth : public FEdge {
 protected:
  Vec3r _Normal;
  unsigned _FrsMaterialIndex;
#if 0
  bool _hasVisibilityPoint;
  Vec3r _VisibilityPointA;  // The edge on which the visibility will be computed represented
  Vec3r _VisibilityPointB;  // using its 2 extremity points A and B
#endif
  void *_Face;  // In case of exact silhouette, Face is the WFace crossed by Fedge
                // NOT HANDLED BY THE COPY CONSTRUCTEUR
  bool _FaceMark;

 public:
  /*! Returns the string "FEdgeSmooth" . */
  virtual string getExactTypeName() const
  {
    return "FEdgeSmooth";
  }

  /*! Default constructor. */
  inline FEdgeSmooth() : FEdge()
  {
    _Face = NULL;
    _FaceMark = false;
    _FrsMaterialIndex = 0;
    _isSmooth = true;
  }

  /*! Builds an FEdgeSmooth going from vA to vB. */
  inline FEdgeSmooth(SVertex *vA, SVertex *vB) : FEdge(vA, vB)
  {
    _Face = NULL;
    _FaceMark = false;
    _FrsMaterialIndex = 0;
    _isSmooth = true;
  }

  /*! Copy constructor. */
  inline FEdgeSmooth(FEdgeSmooth &iBrother) : FEdge(iBrother)
  {
    _Normal = iBrother._Normal;
    _Face = iBrother._Face;
    _FaceMark = iBrother._FaceMark;
    _FrsMaterialIndex = iBrother._FrsMaterialIndex;
    _isSmooth = true;
  }

  /*! Destructor. */
  virtual ~FEdgeSmooth()
  {
  }

  /*! Cloning method. */
  virtual FEdge *duplicate()
  {
    FEdge *clone = new FEdgeSmooth(*this);
    return clone;
  }

  inline void *face() const
  {
    return _Face;
  }

  /*! Returns the face mark of the face it is running across. */
  inline bool faceMark() const
  {
    return _FaceMark;
  }

  /*! Returns the normal to the Face it is running across. */
  inline const Vec3r &normal()
  {
    return _Normal;
  }

  /*! Returns the index of the material of the face it is running across. */
  inline unsigned frs_materialIndex() const
  {
    return _FrsMaterialIndex;
  }

  /*! Returns the material of the face it is running across. */
  const FrsMaterial &frs_material() const;

  inline void setFace(void *iFace)
  {
    _Face = iFace;
  }

  /*! Sets the face mark of the face it is running across. */
  inline void setFaceMark(bool iFaceMark)
  {
    _FaceMark = iFaceMark;
  }

  /*! Sets the normal to the Face it is running across. */
  inline void setNormal(const Vec3r &iNormal)
  {
    _Normal = iNormal;
  }

  /*! Sets the index of the material of the face it is running across. */
  inline void setFrsMaterialIndex(unsigned i)
  {
    _FrsMaterialIndex = i;
  }

#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:FEdgeSmooth")
#endif
};

/**********************************/
/*                                */
/*                                */
/*             SShape             */
/*                                */
/*                                */
/**********************************/

/*! Class to define a feature shape. It is the gathering of feature elements from an identified
 * input shape */
class SShape {
 private:
  vector<FEdge *> _chains;          // list of fedges that are chains starting points.
  vector<SVertex *> _verticesList;  // list of all vertices
  vector<FEdge *> _edgesList;       // list of all edges
  Id _Id;
  string _Name;
  string _LibraryPath;
  BBox<Vec3r> _BBox;
  vector<FrsMaterial> _FrsMaterials;

  float _importance;

  ViewShape *_ViewShape;

 public:
  /*! A field that can be used by the user to store any data.
   *  This field must be reset afterwards using ResetUserData().
   */
  void *userdata;  // added by E.T.

  /*! Default constructor */
  inline SShape()
  {
    userdata = NULL;
    _importance = 0.0f;
    _ViewShape = NULL;
  }

  /*! Copy constructor */
  inline SShape(SShape &iBrother)
  {
    userdata = NULL;
    _Id = iBrother._Id;
    _Name = iBrother._Name;
    _LibraryPath = iBrother._LibraryPath;
    _BBox = iBrother.bbox();
    _FrsMaterials = iBrother._FrsMaterials;
    _importance = iBrother._importance;
    _ViewShape = iBrother._ViewShape;

    //---------
    // vertices
    //---------
    vector<SVertex *>::iterator sv, svend;
    vector<SVertex *> &verticesList = iBrother.getVertexList();
    for (sv = verticesList.begin(), svend = verticesList.end(); sv != svend; sv++) {
      SVertex *newv = new SVertex(*(*sv));
      newv->setShape(this);
      _verticesList.push_back(newv);
    }

    //------
    // edges
    //------
    vector<FEdge *>::iterator e, eend;
    vector<FEdge *> &edgesList = iBrother.getEdgeList();
    for (e = edgesList.begin(), eend = edgesList.end(); e != eend; e++) {
      FEdge *newe = (*e)->duplicate();
      _edgesList.push_back(newe);
    }

    //-------------------------
    // starting chain edges
    //-------------------------
    vector<FEdge *>::iterator fe, fend;
    vector<FEdge *> &fedges = iBrother.getChains();
    for (fe = fedges.begin(), fend = fedges.end(); fe != fend; fe++) {
      _chains.push_back((FEdge *)((*fe)->userdata));
    }

    //-------------------------
    // remap edges in vertices:
    //-------------------------
    for (sv = _verticesList.begin(), svend = _verticesList.end(); sv != svend; sv++) {
      const vector<FEdge *> &fedgeList = (*sv)->fedges();
      vector<FEdge *> newfedgelist;
      for (vector<FEdge *>::const_iterator fed = fedgeList.begin(), fedend = fedgeList.end();
           fed != fedend;
           fed++) {
        FEdge *current = *fed;
        newfedgelist.push_back((FEdge *)current->userdata);
      }
      (*sv)->setFEdges(newfedgelist);
    }

    //-------------------------------------
    // remap vertices and nextedge in edges:
    //-------------------------------------
    for (e = _edgesList.begin(), eend = _edgesList.end(); e != eend; e++) {
      (*e)->setVertexA((SVertex *)((*e)->vertexA()->userdata));
      (*e)->setVertexB((SVertex *)((*e)->vertexB()->userdata));
      (*e)->setNextEdge((FEdge *)((*e)->nextEdge()->userdata));
      (*e)->setPreviousEdge((FEdge *)((*e)->previousEdge()->userdata));
    }

    // reset all brothers userdata to NULL:
    //-------------------------------------
    //---------
    // vertices
    //---------
    for (sv = _verticesList.begin(), svend = _verticesList.end(); sv != svend; sv++) {
      (*sv)->userdata = NULL;
    }

    //------
    // edges
    //------
    for (e = _edgesList.begin(), eend = _edgesList.end(); e != eend; e++) {
      (*e)->userdata = NULL;
    }
  }

  /*! Cloning method. */
  virtual SShape *duplicate()
  {
    SShape *clone = new SShape(*this);
    return clone;
  }

  /*! Destructor. */
  virtual inline ~SShape()
  {
    vector<SVertex *>::iterator sv, svend;
    vector<FEdge *>::iterator e, eend;
    if (0 != _verticesList.size()) {
      for (sv = _verticesList.begin(), svend = _verticesList.end(); sv != svend; sv++) {
        delete (*sv);
      }
      _verticesList.clear();
    }

    if (0 != _edgesList.size()) {
      for (e = _edgesList.begin(), eend = _edgesList.end(); e != eend; e++) {
        delete (*e);
      }
      _edgesList.clear();
    }

    //! Clear the chains list
    //-----------------------
    if (0 != _chains.size()) {
      _chains.clear();
    }
  }

  /*! Adds a FEdge to the list of FEdges. */
  inline void AddEdge(FEdge *iEdge)
  {
    _edgesList.push_back(iEdge);
  }

  /*! Adds a SVertex to the list of SVertex of this Shape.
   * The SShape attribute of the SVertex is also set to 'this'.
   */
  inline void AddNewVertex(SVertex *iv)
  {
    iv->setShape(this);
    _verticesList.push_back(iv);
  }

  inline void AddChain(FEdge *iEdge)
  {
    _chains.push_back(iEdge);
  }

  inline SVertex *CreateSVertex(const Vec3r &P3D, const Vec3r &P2D, const Id &id)
  {
    SVertex *Ia = new SVertex(P3D, id);
    Ia->setPoint2D(P2D);
    AddNewVertex(Ia);
    return Ia;
  }

  /*! Splits an edge into several edges.
   *  The edge's vertices are passed rather than the edge itself. This way, all feature edges
   * (SILHOUETTE, CREASE, BORDER) are split in the same time. The processed edges are flagged as
   * done (using the user-data flag).One single new vertex is created whereas several split edges
   * might created for the different kinds of edges. These new elements are added to the lists
   *  maintained by the shape.
   *  New chains are also created.
   *    ioA
   *      The first vertex for the edge that gets split.
   *    ioB
   *      The second vertex for the edge that gets split.
   *    iParameters
   *      A vector containing 2D real vectors indicating the parameters giving the intersections
   * coordinates in 3D and in 2D. These intersections points must be sorted from B to A. Each
   * parameter defines the intersection point I as I=A+T*AB. T<0 and T>1 are then incorrect insofar
   * as they give intersections points that lie outside the segment. ioNewEdges The edges that are
   * newly created (the initial edges are not included) are added to this list.
   */
  inline void SplitEdge(FEdge *fe, const vector<Vec2r> &iParameters, vector<FEdge *> &ioNewEdges)
  {
    SVertex *ioA = fe->vertexA();
    SVertex *ioB = fe->vertexB();
    Vec3r A = ioA->point3D();
    Vec3r B = ioB->point3D();
    Vec3r a = ioA->point2D();
    Vec3r b = ioB->point2D();

    Vec3r newpoint3d, newpoint2d;
    vector<SVertex *> intersections;
    real t, T;
    for (vector<Vec2r>::const_iterator p = iParameters.begin(), pend = iParameters.end();
         p != pend;
         p++) {
      T = (*p)[0];
      t = (*p)[1];

      if ((t < 0) || (t > 1)) {
        cerr << "Warning: Intersection out of range for edge " << ioA->getId() << " - "
             << ioB->getId() << endl;
      }

      // compute the 3D and 2D coordinates for the intersections points:
      newpoint3d = Vec3r(A + T * (B - A));
      newpoint2d = Vec3r(a + t * (b - a));

      // create new SVertex:
      // (we keep B's id)
      SVertex *newVertex = new SVertex(newpoint3d, ioB->getId());
      newVertex->setPoint2D(newpoint2d);

      // Add this vertex to the intersections list:
      intersections.push_back(newVertex);

      // Add this vertex to this sshape:
      AddNewVertex(newVertex);
    }

    for (vector<SVertex *>::iterator sv = intersections.begin(), svend = intersections.end();
         sv != svend;
         sv++) {
      // SVertex *svA = fe->vertexA();
      SVertex *svB = fe->vertexB();

      // We split edge AB into AA' and A'B. A' and A'B are created.
      // AB becomes (address speaking) AA'. B is updated.
      //--------------------------------------------------
      // The edge AB becomes edge AA'.
      (fe)->setVertexB((*sv));
      // a new edge, A'B is created.
      FEdge *newEdge;
      if (fe->isSmooth()) {
        newEdge = new FEdgeSmooth((*sv), svB);
        FEdgeSmooth *se = dynamic_cast<FEdgeSmooth *>(newEdge);
        FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(fe);
        se->setFrsMaterialIndex(fes->frs_materialIndex());
      }
      else {
        newEdge = new FEdgeSharp((*sv), svB);
        FEdgeSharp *se = dynamic_cast<FEdgeSharp *>(newEdge);
        FEdgeSharp *fes = dynamic_cast<FEdgeSharp *>(fe);
        se->setaFrsMaterialIndex(fes->aFrsMaterialIndex());
        se->setbFrsMaterialIndex(fes->bFrsMaterialIndex());
      }

      newEdge->setNature((fe)->getNature());

      // to build a new chain:
      AddChain(newEdge);
      // add the new edge to the sshape edges list.
      AddEdge(newEdge);
      // add new edge to the list of new edges passed as argument:
      ioNewEdges.push_back(newEdge);

      // update edge A'B for the next pointing edge
      newEdge->setNextEdge((fe)->nextEdge());
      fe->nextEdge()->setPreviousEdge(newEdge);
      Id id(fe->getId().getFirst(), fe->getId().getSecond() + 1);
      newEdge->setId(fe->getId());
      fe->setId(id);

      // update edge AA' for the next pointing edge
      // ioEdge->setNextEdge(newEdge);
      (fe)->setNextEdge(NULL);

      // update vertex pointing edges list:
      // -- vertex B --
      svB->Replace((fe), newEdge);
      // -- vertex A' --
      (*sv)->AddFEdge((fe));
      (*sv)->AddFEdge(newEdge);
    }
  }

  /* splits an edge into 2 edges. The new vertex and edge are added to the sshape list of vertices
   * and edges a new chain is also created. returns the new edge. ioEdge The edge that gets
   * splitted newpoint x,y,z coordinates of the new point.
   */
  inline FEdge *SplitEdgeIn2(FEdge *ioEdge, SVertex *ioNewVertex)
  {
    // soc unused - SVertex *A = ioEdge->vertexA();
    SVertex *B = ioEdge->vertexB();

    // We split edge AB into AA' and A'B. A' and A'B are created.
    // AB becomes (address speaking) AA'. B is updated.
    //--------------------------------------------------
    // a new edge, A'B is created.
    FEdge *newEdge;
    if (ioEdge->isSmooth()) {
      newEdge = new FEdgeSmooth(ioNewVertex, B);
      FEdgeSmooth *se = dynamic_cast<FEdgeSmooth *>(newEdge);
      FEdgeSmooth *fes = dynamic_cast<FEdgeSmooth *>(ioEdge);
      se->setNormal(fes->normal());
      se->setFrsMaterialIndex(fes->frs_materialIndex());
      se->setFaceMark(fes->faceMark());
    }
    else {
      newEdge = new FEdgeSharp(ioNewVertex, B);
      FEdgeSharp *se = dynamic_cast<FEdgeSharp *>(newEdge);
      FEdgeSharp *fes = dynamic_cast<FEdgeSharp *>(ioEdge);
      se->setNormalA(fes->normalA());
      se->setNormalB(fes->normalB());
      se->setaFrsMaterialIndex(fes->aFrsMaterialIndex());
      se->setbFrsMaterialIndex(fes->bFrsMaterialIndex());
      se->setaFaceMark(fes->aFaceMark());
      se->setbFaceMark(fes->bFaceMark());
    }
    newEdge->setNature(ioEdge->getNature());

    if (ioEdge->nextEdge() != 0) {
      ioEdge->nextEdge()->setPreviousEdge(newEdge);
    }

    // update edge A'B for the next pointing edge
    newEdge->setNextEdge(ioEdge->nextEdge());
    // update edge A'B for the previous pointing edge
    newEdge->setPreviousEdge(0);  // because it is now a TVertex
    Id id(ioEdge->getId().getFirst(), ioEdge->getId().getSecond() + 1);
    newEdge->setId(ioEdge->getId());
    ioEdge->setId(id);

    // update edge AA' for the next pointing edge
    ioEdge->setNextEdge(0);  // because it is now a TVertex

    // update vertex pointing edges list:
    // -- vertex B --
    B->Replace(ioEdge, newEdge);
    // -- vertex A' --
    ioNewVertex->AddFEdge(ioEdge);
    ioNewVertex->AddFEdge(newEdge);

    // to build a new chain:
    AddChain(newEdge);
    AddEdge(newEdge);  // FIXME ??

    // The edge AB becomes edge AA'.
    ioEdge->setVertexB(ioNewVertex);

    if (ioEdge->isSmooth()) {
      ((FEdgeSmooth *)newEdge)->setFace(((FEdgeSmooth *)ioEdge)->face());
    }

    return newEdge;
  }

  /*! Sets the Bounding Box of the Shape */
  inline void setBBox(const BBox<Vec3r> &iBBox)
  {
    _BBox = iBBox;
  }

  /*! Compute the bbox of the sshape */
  inline void ComputeBBox()
  {
    if (0 == _verticesList.size()) {
      return;
    }

    Vec3r firstVertex = _verticesList[0]->point3D();
    real XMax = firstVertex[0];
    real YMax = firstVertex[1];
    real ZMax = firstVertex[2];

    real XMin = firstVertex[0];
    real YMin = firstVertex[1];
    real ZMin = firstVertex[2];

    vector<SVertex *>::iterator v, vend;
    // parse all the coordinates to find the Xmax, YMax, ZMax
    for (v = _verticesList.begin(), vend = _verticesList.end(); v != vend; v++) {
      Vec3r vertex = (*v)->point3D();
      // X
      real x = vertex[0];
      if (x > XMax) {
        XMax = x;
      }
      else if (x < XMin) {
        XMin = x;
      }

      // Y
      real y = vertex[1];
      if (y > YMax) {
        YMax = y;
      }
      else if (y < YMin) {
        YMin = y;
      }

      // Z
      real z = vertex[2];
      if (z > ZMax) {
        ZMax = z;
      }
      else if (z < ZMin) {
        ZMin = z;
      }
    }

    setBBox(BBox<Vec3r>(Vec3r(XMin, YMin, ZMin), Vec3r(XMax, YMax, ZMax)));
  }

  inline void RemoveEdgeFromChain(FEdge *iEdge)
  {
    for (vector<FEdge *>::iterator fe = _chains.begin(), feend = _chains.end(); fe != feend;
         fe++) {
      if (iEdge == (*fe)) {
        _chains.erase(fe);
        break;
      }
    }
  }

  inline void RemoveEdge(FEdge *iEdge)
  {
    for (vector<FEdge *>::iterator fe = _edgesList.begin(), feend = _edgesList.end(); fe != feend;
         fe++) {
      if (iEdge == (*fe)) {
        _edgesList.erase(fe);
        break;
      }
    }
  }

  /* accessors */
  /*! Returns the list of SVertex of the Shape. */
  inline vector<SVertex *> &getVertexList()
  {
    return _verticesList;
  }

  /*! Returns the list of FEdges of the Shape. */
  inline vector<FEdge *> &getEdgeList()
  {
    return _edgesList;
  }

  inline vector<FEdge *> &getChains()
  {
    return _chains;
  }

  /*! Returns the bounding box of the shape. */
  inline const BBox<Vec3r> &bbox()
  {
    return _BBox;
  }

  /*! Returns the ith material of the shape. */
  inline const FrsMaterial &frs_material(unsigned i) const
  {
    return _FrsMaterials[i];
  }

  /*! Returns the list of materials of the Shape. */
  inline const vector<FrsMaterial> &frs_materials() const
  {
    return _FrsMaterials;
  }

  inline ViewShape *viewShape()
  {
    return _ViewShape;
  }

  inline float importance() const
  {
    return _importance;
  }

  /*! Returns the Id of the Shape. */
  inline Id getId() const
  {
    return _Id;
  }

  /*! Returns the name of the Shape. */
  inline const string &getName() const
  {
    return _Name;
  }

  /*! Returns the library path of the Shape. */
  inline const string &getLibraryPath() const
  {
    return _LibraryPath;
  }

  /* Modififers */
  /*! Sets the Id of the shape.*/
  inline void setId(Id id)
  {
    _Id = id;
  }

  /*! Sets the name of the shape.*/
  inline void setName(const string &name)
  {
    _Name = name;
  }

  /*! Sets the library path of the shape.*/
  inline void setLibraryPath(const string &path)
  {
    _LibraryPath = path;
  }

  /*! Sets the list of materials for the shape */
  inline void setFrsMaterials(const vector<FrsMaterial> &iMaterials)
  {
    _FrsMaterials = iMaterials;
  }

  inline void setViewShape(ViewShape *iShape)
  {
    _ViewShape = iShape;
  }

  inline void setImportance(float importance)
  {
    _importance = importance;
  }

#ifdef WITH_CXX_GUARDEDALLOC
  MEM_CXX_CLASS_ALLOC_FUNCS("Freestyle:SShape")
#endif
};

} /* namespace Freestyle */