Shinya Kitaoka 810553
#pragma once
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef T_CENTERLINE_VECTORIZER_PRIVATE
Toshihiro Shimizu 890ddd
#define T_CENTERLINE_VECTORIZER_PRIVATE
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "toonz/tcenterlinevectorizer.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// TnzCore includes
Toshihiro Shimizu 890ddd
#include "tpalette.h"
Toshihiro Shimizu 890ddd
#include "tcolorstyles.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "trastercm.h"
Toshihiro Shimizu 890ddd
#include "ttoonzimage.h"
Toshihiro Shimizu 890ddd
#include "trasterimage.h"
Toshihiro Shimizu 890ddd
#include "tvectorimage.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "tgeometry.h"
Toshihiro Shimizu 890ddd
#include "tstroke.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// STD includes
Toshihiro Shimizu 890ddd
#include <vector></vector>
Toshihiro Shimizu 890ddd
#include <list></list>
Toshihiro Shimizu 890ddd
#include <queue></queue>
Toshihiro Shimizu 890ddd
#include <map></map>
Toshihiro Shimizu 890ddd
#include <functional></functional>
Toshihiro Shimizu 890ddd
#include <algorithm></algorithm>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include <math.h></math.h>
Toshihiro Shimizu 890ddd
#include <assert.h></assert.h>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------
Toshihiro Shimizu 890ddd
//    Preliminary geometric helpers
Toshihiro Shimizu 890ddd
//--------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline TPointD planeProjection(const T3DPointD &p) { return TPointD(p.x, p.y); }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//! Returns distance of \p P from line of direction \p v that touches \p B
Shinya Kitaoka 120a6e
inline double tdistance2(const T3DPointD &P, const T3DPointD &v,
Shinya Kitaoka 120a6e
                         const T3DPointD &B) {
Shinya Kitaoka 120a6e
  double t    = P * v - B * v;
Shinya Kitaoka 120a6e
  T3DPointD Q = B + t * v - P;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return Q * Q;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline double tdistance(TPointD P, TPointD v, TPointD B) {
Shinya Kitaoka 120a6e
  return fabs(cross(P - B, normalize(v)));
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline double tdistance(T3DPointD P, T3DPointD v, T3DPointD B) {
Shinya Kitaoka 120a6e
  double vv = norm2(v);
Shinya Kitaoka 120a6e
  if (vv < 0.01) return -1;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double t    = (P * v - B * v) / vv;
Shinya Kitaoka 120a6e
  T3DPointD Q = B + t * v - P;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return norm(Q);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline double planeDistance(const T3DPointD &P, const T3DPointD &Q) {
Shinya Kitaoka 120a6e
  return sqrt((P.x - Q.x) * (P.x - Q.x) + (P.y - Q.y) * (P.y - Q.y));
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline double crossZ(const T3DPointD &p, const T3DPointD &q) {
Shinya Kitaoka 120a6e
  return p.x * q.y - p.y * q.x;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// a, b assumed normalized
Shinya Kitaoka 120a6e
inline bool angleLess(const TPointD &a, const TPointD &b) {
Shinya Kitaoka 120a6e
  return a.y >= 0 ? b.y >= 0 ? a.x > b.x : 1 : b.y < 0 ? a.x < b.x : 0;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// a, b, ref assumed normalized
Shinya Kitaoka 120a6e
inline bool angleLess(const TPointD &a, const TPointD &b, const TPointD &ref) {
Shinya Kitaoka 120a6e
  return angleLess(a, ref) ? angleLess(b, ref) ? angleLess(a, b) : 0
Shinya Kitaoka 120a6e
                           : angleLess(b, ref) ? 1 : angleLess(a, b);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------
Toshihiro Shimizu 890ddd
//    STL auxiliaries
Toshihiro Shimizu 890ddd
//------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Container append (needs reverse iterators)
Toshihiro Shimizu 890ddd
// NOTE: Merge could be used... but it requires operator< and we don't...
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
//! warning: must be I == T::Reverse_iterator; explicited because on Mac it was
Shinya Kitaoka 120a6e
//! not compiling!
Toshihiro Shimizu 890ddd
template <class class="" i="" t,=""></class>
Shinya Kitaoka 120a6e
void append(T &cont1, T &cont2) {
Shinya Kitaoka 120a6e
  I i, j;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  cont1.resize(cont1.size() + cont2.size());
Shinya Kitaoka 120a6e
  for (i = cont2.rbegin(), j = cont1.rbegin(); i != cont2.rend(); ++i, ++j)
Shinya Kitaoka 120a6e
    *j = *i;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//*********************************
Toshihiro Shimizu 890ddd
//       Traversable Graphs
Toshihiro Shimizu 890ddd
//*********************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef unsigned int UINT;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*!
Toshihiro Shimizu 890ddd
  \brief    Graph class used by the centerline vectorization process.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  \details  Introducing a directed graph structure that allows local access:
Shinya Kitaoka 120a6e
  main feature is that a graph edge
Shinya Kitaoka 120a6e
            physically belongs to the node that emitted it, by storing it in a
Shinya Kitaoka 120a6e
  'link vector' inside the node.
Shinya Kitaoka 120a6e
            No full-scale edge search method is therefore needed to find node
Shinya Kitaoka 120a6e
  neighbours.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
            No specific iterator class is needed, just use unsigned ints to
Shinya Kitaoka 120a6e
  perform random access to nodes and
Toshihiro Shimizu 890ddd
            links vectors.
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
template <typename arctype="" nodecontenttype,="" typename=""></typename>
Shinya Kitaoka 120a6e
class Graph {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  class Link {
Shinya Kitaoka 120a6e
    UINT m_next;    //!< Index of the node pointed by this link.
Shinya Kitaoka 120a6e
    ArcType m_arc;  //!< Edge data associated to this link.
Shinya Kitaoka 120a6e
    int m_access;   //!< Whether access to a node is allowed
Shinya Kitaoka 120a6e
                    //!  through this link.
Shinya Kitaoka 120a6e
  public:
Shinya Kitaoka 120a6e
    Link() : m_access(1) {}
Shinya Kitaoka 120a6e
    Link(UINT _next) : m_next(_next), m_access(1) {}
Shinya Kitaoka 120a6e
    Link(UINT _next, ArcType _arc) : m_next(_next), m_arc(_arc), m_access(1) {}
Shinya Kitaoka 120a6e
    ~Link() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    ArcType &operator*() { return m_arc; }
Shinya Kitaoka 120a6e
    const ArcType &operator*() const { return m_arc; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    ArcType *operator->() { return &m_arc; }
Shinya Kitaoka 120a6e
    const ArcType *operator->() const { return &m_arc; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    UINT getNext() const { return m_next; }
Shinya Kitaoka 120a6e
    void setNext(UINT _next) { m_next = _next; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    int getAccess() const { return m_access; }
Shinya Kitaoka 120a6e
    void setAccess(int acc) { m_access = acc; }
Shinya Kitaoka 120a6e
  };
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  //--------------------------------------------------------------------------
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  class Node {
Shinya Kitaoka 120a6e
    friend class Graph;  // Grant Graph access to m_links
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    std::vector<link> m_links;  //!< Links to neighbouring nodes.
Shinya Kitaoka 120a6e
    NodeContentType m_content;  //!< The node's content.
Shinya Kitaoka 120a6e
    int m_attributes;           //!< Node attributes.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  public:
Shinya Kitaoka 120a6e
    Node() : m_attributes(0) {}
Shinya Kitaoka 120a6e
    Node(const NodeContentType &_cont) : m_content(_cont), m_attributes(0) {}
Shinya Kitaoka 120a6e
    ~Node() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    Link &link(UINT i) { return m_links[i]; }
Shinya Kitaoka 120a6e
    const Link &getLink(UINT i) const { return m_links[i]; }
Shinya Kitaoka 120a6e
    UINT getLinksCount() const { return m_links.size(); }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    NodeContentType &operator*() { return m_content; }
Shinya Kitaoka 120a6e
    const NodeContentType &operator*() const { return m_content; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    NodeContentType *operator->() { return &m_content; }
Shinya Kitaoka 120a6e
    const NodeContentType *operator->() const { return &m_content; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Attributes
Shinya Kitaoka 120a6e
    int hasAttribute(int attr) const { return m_attributes & attr; }
Shinya Kitaoka 120a6e
    void setAttribute(int attr) { m_attributes |= attr; }
Shinya Kitaoka 120a6e
    void clearAttribute(int attr) { m_attributes &= ~attr; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Others
Shinya Kitaoka 120a6e
    int degree() const { return int(m_links.size()); }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    /*!
Shinya Kitaoka 120a6e
\warning    If more links can be set between the same nodes, the
Shinya Kitaoka 120a6e
      returned link index will be ambiguous.
Shinya Kitaoka 120a6e
*/
Shinya Kitaoka 120a6e
    UINT linkOfNode(UINT next) const {
Shinya Kitaoka 120a6e
      UINT i = 0;
Shinya Kitaoka 120a6e
      for (; i < m_links.size() && m_links[i].getNext() != next; ++i)
Shinya Kitaoka 120a6e
        ;
Shinya Kitaoka 120a6e
      return i;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  };
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  std::vector<node> m_nodes;  //!< Nodes container.</node>
Shinya Kitaoka 120a6e
  UINT m_linksCount;          //!< Links counter.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  Graph() : m_linksCount(0) {}
Shinya Kitaoka 120a6e
  virtual ~Graph() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  Node &node(UINT i) { return m_nodes[i]; }
Shinya Kitaoka 120a6e
  const Node &getNode(UINT i) const { return m_nodes[i]; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  UINT getNodesCount() const { return m_nodes.size(); }
Shinya Kitaoka 120a6e
  UINT getLinksCount() const { return m_linksCount; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Nodes/Links insertions
Shinya Kitaoka 120a6e
  UINT newNode() {
Shinya Kitaoka 120a6e
    m_nodes.push_back(Node());
Shinya Kitaoka 120a6e
    return m_nodes.size() - 1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  UINT newNode(const NodeContentType &content) {
Shinya Kitaoka 120a6e
    m_nodes.push_back(Node(content));
Shinya Kitaoka 120a6e
    return m_nodes.size() - 1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  UINT newLink(UINT first, UINT last) {
Shinya Kitaoka 120a6e
    assert(first < m_nodes.size() && last < m_nodes.size());
Shinya Kitaoka 120a6e
    m_nodes[first].m_links.push_back(Link(last));
Shinya Kitaoka 120a6e
    ++m_linksCount;
Shinya Kitaoka 120a6e
    return m_nodes[first].m_links.size() - 1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  UINT newLink(UINT first, UINT last, const ArcType &arc) {
Shinya Kitaoka 120a6e
    assert(first < m_nodes.size() && last < m_nodes.size());
Shinya Kitaoka 120a6e
    m_nodes[first].m_links.push_back(Link(last, arc));
Shinya Kitaoka 120a6e
    ++m_linksCount;
Shinya Kitaoka 120a6e
    return m_nodes[first].m_links.size() - 1;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void insert(UINT inserted, UINT afterNode, UINT onLink) {
Shinya Kitaoka 120a6e
    newLink(inserted, getNode(afterNode).getLink(onLink).getNext());
Shinya Kitaoka 120a6e
    node(afterNode).link(onLink).setNext(inserted);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//********************************
Toshihiro Shimizu 890ddd
//*    Polygonization classes    *
Toshihiro Shimizu 890ddd
//********************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Of course we don't want RawBorders to be entirely copied whenever STL
Toshihiro Shimizu 890ddd
// requires to resize a BorderFamily...
Toshihiro Shimizu 890ddd
class RawBorder;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef std::vector<rawborder *=""> BorderFamily;</rawborder>
Toshihiro Shimizu 890ddd
typedef std::vector<borderfamily> BorderList;</borderfamily>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------
Toshihiro Shimizu 890ddd
//    Output Polygon Classes
Toshihiro Shimizu 890ddd
//--------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
class ContourEdge;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// NOTE: The following class is mainly used in the later 'straight skeleton
Shinya Kitaoka 120a6e
// computation'
Toshihiro Shimizu 890ddd
//       - for polygonization purposes, consider it like a TPointD class.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class ContourNode {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  enum Attributes           //! Node attributes
Shinya Kitaoka 120a6e
  { HEAD            = 0x1,  //!< Node is the 'first' of a nodes ring.
Shinya Kitaoka 120a6e
    ELIMINATED      = 0x4,  //!< Node was eliminated by the SS process.
Shinya Kitaoka 120a6e
    SK_NODE_DROPPED = 0x8,
Shinya Kitaoka 120a6e
    AMBIGUOUS_LEFT  = 0x10,  //!< Node represents an ambiguous \a left turn in
Shinya Kitaoka 120a6e
                             //!  the original image.
Shinya Kitaoka 120a6e
    AMBIGUOUS_RIGHT = 0x20,  //!< Node represents an ambiguous \a right turn in
Shinya Kitaoka 120a6e
                             //!  the original image.
Shinya Kitaoka 120a6e
    JR_RESERVED  = 0x40,     //!< Reserved for joints recovery.
Shinya Kitaoka 120a6e
    LINEAR_ADDED = 0x80  //!< Node was added by the linear skeleton technique.
Shinya Kitaoka 120a6e
  };
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  // Node kinematics infos
Shinya Kitaoka 120a6e
  T3DPointD m_position,      //!< Node's position.
Shinya Kitaoka 120a6e
      m_direction,           //!< Node's direction.
Shinya Kitaoka 120a6e
      m_AngularMomentum,     //!< Angular momentum with the next node's edge.
Shinya Kitaoka 120a6e
      m_AuxiliaryMomentum1,  // Used only when this vertex is convex
Shinya Kitaoka 120a6e
      m_AuxiliaryMomentum2;  // Used only when this vertex is convex
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Further node properties
Shinya Kitaoka 120a6e
  bool m_concave;             //!< Whether the node represents a concave angle.
Shinya Kitaoka 120a6e
  unsigned int m_attributes,  //!< Bitwise signatures of this node
Shinya Kitaoka 120a6e
      m_updateTime,  //!< \a Algoritmic time in which the node was updated.
Shinya Kitaoka 120a6e
      m_ancestor,  //!< Index of the original node from which this one evolved.
Shinya Kitaoka 120a6e
      m_ancestorContour;  //!< Contour index of the original node from which
Shinya Kitaoka 38fd86
                          //! this one evolved.
Shinya Kitaoka 120a6e
  std::vector<contouredge *=""> m_notOpposites;  //!< List of edges \a not to be</contouredge>
Shinya Kitaoka 38fd86
                                              //! used as possible opposites.
Shinya Kitaoka 120a6e
  int m_outputNode;  //!< Skeleton node produced by this ContourNode.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Connective data
Shinya Kitaoka 120a6e
  ContourEdge *m_edge;  //!< Edge departing from this, keeping adjacent black
Shinya Kitaoka 120a6e
                        //!  region on the right
Shinya Kitaoka 120a6e
  // Node neighbours
Shinya Kitaoka 120a6e
  ContourNode *m_next;  //!< Next node on the contour.
Shinya Kitaoka 120a6e
  ContourNode *m_prev;  //!< Previous node on the contour.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  ContourNode() : m_attributes(0) {}
Shinya Kitaoka 120a6e
  ContourNode(double x, double y) : m_position(x, y, 0), m_attributes(0) {}
Shinya Kitaoka 120a6e
  ContourNode(const TPointD &P) : m_position(P.x, P.y, 0), m_attributes(0) {}
Shinya Kitaoka 120a6e
  ContourNode(double x, double y, unsigned short attrib)
Shinya Kitaoka 120a6e
      : m_position(x, y, 0), m_attributes(attrib) {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  int hasAttribute(int attr) const { return m_attributes & attr; }
Shinya Kitaoka 120a6e
  void setAttribute(int attr) { m_attributes |= attr; }
Shinya Kitaoka 120a6e
  void clearAttribute(int attr) { m_attributes &= ~attr; }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  // Private Node Methods
Shinya Kitaoka 120a6e
  inline void buildNodeInfos(bool forceConvex = false);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef std::vector<contournode> Contour;</contournode>
Toshihiro Shimizu 890ddd
typedef std::vector<contour> ContourFamily;</contour>
Toshihiro Shimizu 890ddd
typedef std::vector<contourfamily> Contours;</contourfamily>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-----------------------------------
Toshihiro Shimizu 890ddd
//    Straight Skeleton Classes
Toshihiro Shimizu 890ddd
//-----------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class SkeletonArc {
Shinya Kitaoka 120a6e
  double m_slope;
Shinya Kitaoka 120a6e
  unsigned int m_leftGeneratingNode, m_leftContour, m_rightGeneratingNode,
Shinya Kitaoka 120a6e
      m_rightContour;
Shinya Kitaoka 120a6e
  int m_attributes;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // NOTE:  Typically an arc is generated by a couple of *edges* of the original
Shinya Kitaoka 120a6e
  //        contours; but we store instead the *nodes* which address those
Shinya Kitaoka 120a6e
  //        edges.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  SkeletonArc() : m_attributes(0) {}
Shinya Kitaoka 120a6e
  SkeletonArc(ContourNode *node)
Shinya Kitaoka 120a6e
      : m_slope(node->m_direction.z)
Shinya Kitaoka 120a6e
      , m_leftGeneratingNode(node->m_ancestor)
Shinya Kitaoka 120a6e
      , m_leftContour(node->m_ancestorContour)
Shinya Kitaoka 120a6e
      , m_rightGeneratingNode(node->m_prev->m_ancestor)
Shinya Kitaoka 120a6e
      , m_rightContour(node->m_prev->m_ancestorContour)
Shinya Kitaoka 120a6e
      , m_attributes(0) {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  enum { ROAD = 0x1 };
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double getSlope() const { return m_slope; }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  unsigned int getLeftGenerator() const { return m_leftGeneratingNode; }
Shinya Kitaoka 120a6e
  unsigned int getRightGenerator() const { return m_rightGeneratingNode; }
Shinya Kitaoka 120a6e
  unsigned int getLeftContour() const { return m_leftContour; }
Shinya Kitaoka 120a6e
  unsigned int getRightContour() const { return m_rightContour; }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  enum { SS_OUTLINE = 0x10, SS_OUTLINE_REVERSED = 0x20 };
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  int hasAttribute(int attr) const { return m_attributes & attr; }
Shinya Kitaoka 120a6e
  void setAttribute(int attr) { m_attributes |= attr; }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void turn() {
Shinya Kitaoka 120a6e
    m_slope = -m_slope;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    std::swap(m_leftGeneratingNode, m_rightGeneratingNode);
Shinya Kitaoka 120a6e
    std::swap(m_leftContour, m_rightContour);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef Graph<t3dpointd, skeletonarc=""> SkeletonGraph;</t3dpointd,>
Toshihiro Shimizu 890ddd
typedef std::vector<skeletongraph *=""> SkeletonList;</skeletongraph>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//----------------------------------------
Toshihiro Shimizu 890ddd
//    Joints and Sequences definition
Toshihiro Shimizu 890ddd
//----------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class Sequence {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  UINT m_head;
Shinya Kitaoka 120a6e
  UINT m_headLink;
Shinya Kitaoka 120a6e
  UINT m_tail;
Shinya Kitaoka 120a6e
  UINT m_tailLink;
Shinya Kitaoka 120a6e
  SkeletonGraph *m_graphHolder;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Stroke color-sensible data
Shinya Kitaoka 120a6e
  int m_color;
Shinya Kitaoka 120a6e
  int m_strokeIndex;
Shinya Kitaoka 120a6e
  int m_strokeHeight;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  Sequence() : m_graphHolder(0) {}
Shinya Kitaoka 120a6e
  ~Sequence() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Impose a property dependant only on the extremity we consider first
Shinya Kitaoka 120a6e
  // - so that the same sequence is not considered twice when head and tail
Shinya Kitaoka 120a6e
  // are exchanged
Shinya Kitaoka 120a6e
  bool isForward() const {
Shinya Kitaoka 120a6e
    return (m_head < m_tail) || (m_head == m_tail && m_headLink < m_tailLink);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Advances a couple (old, current) of sequence nodes
Shinya Kitaoka 120a6e
  void advance(UINT &old, UINT ¤t) const {
Shinya Kitaoka 120a6e
    UINT temp = current;
Shinya Kitaoka 120a6e
    current   = m_graphHolder->getNode(current).getLink(0).getNext() == old
Shinya Kitaoka 120a6e
                  ? m_graphHolder->getNode(current).getLink(1).getNext()
Shinya Kitaoka 120a6e
                  : m_graphHolder->getNode(current).getLink(0).getNext();
Shinya Kitaoka 120a6e
    old = temp;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Advances a couple (current, link) of a sequence node plus its link
Shinya Kitaoka 120a6e
  // direction
Shinya Kitaoka 120a6e
  void next(UINT ¤t, UINT &link) const {
Shinya Kitaoka 120a6e
    UINT temp = current;
Shinya Kitaoka 120a6e
    current   = m_graphHolder->getNode(current).getLink(link).getNext();
Shinya Kitaoka 120a6e
    link = m_graphHolder->getNode(current).getLink(0).getNext() == temp ? 1 : 0;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka d1f6c4
class JointSequenceGraph final : public Graph<uint, sequence=""> {</uint,>
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  JointSequenceGraph() {}
Shinya Kitaoka 120a6e
  ~JointSequenceGraph() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  enum { REACHED = 0x1, ELIMINATED = 0x2 };
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Extracts JSG tail link of input node-link
Shinya Kitaoka 120a6e
  inline UINT tailLinkOf(UINT node, UINT link) {
Shinya Kitaoka 120a6e
    UINT i, next = getNode(node).getLink(link).getNext();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    for (i = 0; getNode(next).getLink(i)->m_tail !=
Shinya Kitaoka 120a6e
                    getNode(node).getLink(link)->m_head ||
Shinya Kitaoka 120a6e
                getNode(next).getLink(i)->m_tailLink !=
Shinya Kitaoka 120a6e
                    getNode(node).getLink(link)->m_headLink;
Shinya Kitaoka 120a6e
         ++i)
Shinya Kitaoka 120a6e
      ;
Shinya Kitaoka 120a6e
    return i;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef std::vector<jointsequencegraph> JointSequenceGraphList;</jointsequencegraph>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
typedef std::vector<sequence> SequenceList;</sequence>
Toshihiro Shimizu 890ddd
typedef std::vector<t3dpointd> PointList;</t3dpointd>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//----------------
Toshihiro Shimizu 890ddd
//    Globals
Toshihiro Shimizu 890ddd
//----------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//!\b FOR \b INTERNAL \b USE \b ONLY!
Shinya Kitaoka 120a6e
//! EXPLANATION: Some variables are used widely used and shared by all the
Shinya Kitaoka 120a6e
//! "tcenterline*.cpp"
Shinya Kitaoka 120a6e
// sources. Instead than passing each variable repeatedly, it is easier to
Shinya Kitaoka 120a6e
// define a Global
Shinya Kitaoka 120a6e
// class passed to each file, which gets immediatly pointed in an anonymous
Shinya Kitaoka 120a6e
// namespace.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
class VectorizerCoreGlobals {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  const CenterlineConfiguration *currConfig;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  JointSequenceGraphList organizedGraphs;
Shinya Kitaoka 120a6e
  SequenceList singleSequences;
Shinya Kitaoka 120a6e
  PointList singlePoints;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  VectorizerCoreGlobals() {}
Shinya Kitaoka 120a6e
  ~VectorizerCoreGlobals() {}
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace {
Shinya Kitaoka 120a6e
// SkeletonGraph nodes global signatures - used for various purposes
Shinya Kitaoka 120a6e
enum {
Shinya Kitaoka 120a6e
  ORGANIZEGRAPHS_SIGN = 0x10,
Shinya Kitaoka 120a6e
  SAMPLECOLOR_SIGN    = 0x20,
Shinya Kitaoka 120a6e
  COLORORDERING_SIGN  = 0x40
Shinya Kitaoka 120a6e
};
Shinya Kitaoka 120a6e
const int infinity = 1000000;  // just a great enough number
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//===============================
Toshihiro Shimizu 890ddd
//    Function prototypes
Toshihiro Shimizu 890ddd
//===============================
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void polygonize(const TRasterP &ras, Contours &polygons,
Shinya Kitaoka 120a6e
                VectorizerCoreGlobals &g);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
SkeletonList *skeletonize(Contours &contours, VectorizerCore *thisVectorizer,
Shinya Kitaoka 120a6e
                          VectorizerCoreGlobals &g);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
void organizeGraphs(SkeletonList *skeleton, VectorizerCoreGlobals &g);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
void junctionRecovery(Contours *polygons, VectorizerCoreGlobals &g);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void conversionToStrokes(std::vector<tstroke *=""> &strokes,</tstroke>
Shinya Kitaoka 120a6e
                         VectorizerCoreGlobals &g);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
void calculateSequenceColors(const TRasterP &ras, VectorizerCoreGlobals &g);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void applyStrokeColors(std::vector<tstroke *=""> &strokes, const TRasterP &ras,</tstroke>
Shinya Kitaoka 120a6e
                       TPalette *palette, VectorizerCoreGlobals &g);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
#endif  // T_CENTERLINE_VECTORIZER_PRIVATE