Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "tcenterlinevectP.h"
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
//#define _SSDEBUG                                              // Uncomment to
Shinya Kitaoka 38fd86
// enable the debug viewer
Shinya Kitaoka 120a6e
//#define _UPDATE                                               // Shows borders
Shinya Kitaoka 38fd86
// updated to current time
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//====================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Forward declarations
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
struct VectorizationContext;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//====================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//**************************************************************
Toshihiro Shimizu 890ddd
//      Rationale
Toshihiro Shimizu 890ddd
//**************************************************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*
Toshihiro Shimizu 890ddd
  NOTE: Input is a vector of Contours, representing the borders of a
Toshihiro Shimizu 890ddd
        polygonal region. First border is the outer one, followed by internal
Toshihiro Shimizu 890ddd
        counter-borders; each Contour is itself a vector of "ContourNode"s,
Toshihiro Shimizu 890ddd
        ordered so that the region to be thinned is at the RIGHT of segments
Toshihiro Shimizu 890ddd
        formed by successive nodes.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
        Output is a Graph structure representing the straight skeleton of the
Toshihiro Shimizu 890ddd
        thinned region. Original contours survive the thinning procedure.
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//**************************************************************
Toshihiro Shimizu 890ddd
//      Straight Skeleton Debugger
Toshihiro Shimizu 890ddd
//**************************************************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef _SSDEBUG
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include <qwidget></qwidget>
Toshihiro Shimizu 890ddd
#include <qtransform></qtransform>
Toshihiro Shimizu 890ddd
#include <qeventloop></qeventloop>
Toshihiro Shimizu 890ddd
#include <qpainter></qpainter>
Toshihiro Shimizu 890ddd
#include <qmouseevent></qmouseevent>
Toshihiro Shimizu 890ddd
#include <qwheelevent></qwheelevent>
Toshihiro Shimizu 890ddd
Shinya Kitaoka d1f6c4
class SSDebugger final : public QWidget {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  VectorizationContext &m_context;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  QPoint m_pos, m_pressPos;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double m_scale;
Shinya Kitaoka 120a6e
  QTransform m_transform;
Shinya Kitaoka 120a6e
  QEventLoop m_loop;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  double m_height;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  SSDebugger(VectorizationContext &context);
Shinya Kitaoka 120a6e
  ~SSDebugger() {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void loop() { m_loop.exec(); }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void paintEvent(QPaintEvent *event);
Shinya Kitaoka 120a6e
  void keyPressEvent(QKeyEvent *event);
Shinya Kitaoka 120a6e
  void mouseMoveEvent(QMouseEvent *event);
Shinya Kitaoka 120a6e
  void mousePressEvent(QMouseEvent *event);
Shinya Kitaoka 120a6e
  void mouseReleaseEvent(QMouseEvent *event);
Shinya Kitaoka 120a6e
  void wheelEvent(QWheelEvent *event);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline QPoint winToWorld(int x, int y);
Shinya Kitaoka 120a6e
  inline QPoint worldToWin(double x, double y);
Shinya Kitaoka 120a6e
  inline QPointF winToWorldF(int x, int y);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline bool isOnScreen(ContourNode *node);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Node Updates
Shinya Kitaoka 120a6e
  TPointD updated(ContourNode *input);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
#endif  // _SSDEBUG
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//**************************************************************
Toshihiro Shimizu 890ddd
//      Classes
Toshihiro Shimizu 890ddd
//**************************************************************
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class ContourEdge {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  enum { NOT_OPPOSITE = 0x1 };
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  TPointD m_direction;
Shinya Kitaoka 120a6e
  unsigned short m_attributes;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  ContourEdge() : m_attributes(0) {}
Shinya Kitaoka 120a6e
  ContourEdge(TPointD dir) : m_direction(dir), m_attributes(0) {}
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
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class IndexTable {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  typedef std::list<contournode *=""> IndexColumn;</contournode>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  std::vector<indexcolumn></indexcolumn>
luzpaz 27707d
      m_columns;  //!< Contours set by 'column identifier'.
Shinya Kitaoka 120a6e
  std::vector<int></int>
Shinya Kitaoka 120a6e
      m_identifiers;  //!< Column identifiers by original contour index.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // NOTE: Contours are stored in 'comb' structure (vector of lists) since
Shinya Kitaoka 120a6e
  // contours may both
Shinya Kitaoka 120a6e
  // be SPLIT (new entry in a list) and MERGED (two lists merge).
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  IndexTable() {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  IndexColumn *operator[](int i) { return &m_columns[i]; }
Shinya Kitaoka 120a6e
  IndexColumn &columnOfId(int id) { return m_columns[m_identifiers[id]]; }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Initialization
Shinya Kitaoka 120a6e
  void build(ContourFamily &family);
Shinya Kitaoka 120a6e
  void clear();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Specific handlers
Shinya Kitaoka 120a6e
  IndexColumn::iterator find(ContourNode *index);
Shinya Kitaoka 120a6e
  void merge(IndexColumn::iterator index1, IndexColumn::iterator index2);
Shinya Kitaoka 120a6e
  void remove(IndexColumn::iterator index);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class Event {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  /*! \remark  Values are sorted by preference at simultaneous events.    */
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  enum Type            //! An event's possible types.
Shinya Kitaoka 120a6e
  { special,           //!< A vertex event that is also an edge event (V case).
Shinya Kitaoka 120a6e
    edge,              //!< An edge shrinks to 0 length.
Shinya Kitaoka 120a6e
    vertex,            //!< Two contour nodes clash.
Shinya Kitaoka 120a6e
    split_regenerate,  //!< Placeholder type for split events that must be
Shinya Kitaoka 38fd86
                       //! regenerated.
Shinya Kitaoka 120a6e
    split,             //!< An edge is split by a clashing contour node.
Shinya Kitaoka 120a6e
    failure };
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  double m_height;
Shinya Kitaoka 120a6e
  double m_displacement;
Shinya Kitaoka 120a6e
  ContourNode *m_generator;
Shinya Kitaoka 120a6e
  ContourNode *m_coGenerator;
Shinya Kitaoka 120a6e
  Type m_type;
Shinya Kitaoka 120a6e
  unsigned int m_algoritmicTime;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  VectorizationContext *m_context;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  // In-builder event constructor
Shinya Kitaoka 120a6e
  Event(ContourNode *generator, VectorizationContext *context);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Event calculators
Shinya Kitaoka 120a6e
  inline void calculateEdgeEvent();
Shinya Kitaoka 120a6e
  inline void calculateSplitEvent();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Auxiliary event calculators
Shinya Kitaoka 120a6e
  inline double splitDisplacementWith(ContourNode *plane);
Shinya Kitaoka 120a6e
  inline bool tryRayEdgeCollisionWith(ContourNode *edge);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Event handlers
Shinya Kitaoka 120a6e
  inline bool process();
Shinya Kitaoka 120a6e
  inline void processEdgeEvent();
Shinya Kitaoka 120a6e
  inline void processMaxEvent();
Shinya Kitaoka 120a6e
  inline void processSplitEvent();
Shinya Kitaoka 120a6e
  inline void processVertexEvent();
Shinya Kitaoka 120a6e
  inline void processSpecialEvent();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
private:
Shinya Kitaoka 120a6e
  inline bool testRayEdgeCollision(ContourNode *opposite, double &displacement,
Shinya Kitaoka 120a6e
                                   double &height, double &side1,
Shinya Kitaoka 120a6e
                                   double &side2);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
struct EventGreater {
Shinya Kitaoka 120a6e
  bool operator()(const Event &event1, const Event &event2) const {
Shinya Kitaoka 120a6e
    return event1.m_height > event2.m_height ||
Shinya Kitaoka 120a6e
           (event1.m_height == event2.m_height &&
Shinya Kitaoka 120a6e
            event1.m_type > event2.m_type);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Shinya Kitaoka d1f6c4
class Timeline final
Shinya Kitaoka 120a6e
    : public std::priority_queue<event, std::vector<event="">, EventGreater> {</event,>
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  Timeline() {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // NOTE: Timeline construction contains the most complex part of
Shinya Kitaoka 120a6e
  // vectorization;
Shinya Kitaoka 120a6e
  // progress bar partial notification happens there, so thisVectorizer's signal
Shinya Kitaoka 120a6e
  // emission methods must be passed and used.
Shinya Kitaoka 120a6e
  void build(ContourFamily &polygons, VectorizationContext &context,
Shinya Kitaoka 120a6e
             VectorizerCore *thisVectorizer);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------
Toshihiro Shimizu 890ddd
//    Preliminary methods/functions
Toshihiro Shimizu 890ddd
//--------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// IndexTable methods
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void IndexTable::build(ContourFamily &family) {
Shinya Kitaoka 120a6e
  unsigned int i;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_columns.resize(family.size());
Shinya Kitaoka 120a6e
  m_identifiers.resize(family.size());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // NOTE: At the beginning, m_identifiers= 1, .. , m_columns.size() - 1;
Shinya Kitaoka 120a6e
  for (i = 0; i < m_columns.size(); ++i) {
Shinya Kitaoka 120a6e
    m_identifiers[i] = i;
Shinya Kitaoka 120a6e
    m_columns[i].push_back(&family[i][0]);
Shinya Kitaoka 120a6e
    // Each node referenced in the Table is signed as 'head' of the cirular
Shinya Kitaoka 120a6e
    // list.
Shinya Kitaoka 120a6e
    family[i][0].setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Explanation: during the skeletonization process, ContourNodes and calculated
Shinya Kitaoka 120a6e
// Events are unaware of global index-changes generated by other events, so
Shinya Kitaoka 120a6e
// the position of index stored in one Event has to be retrieved in the
Shinya Kitaoka 120a6e
// IndexTable before event processing begins.
Shinya Kitaoka 120a6e
// NOTE: Can this be done in a more efficient way?...
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline IndexTable::IndexColumn::iterator IndexTable::find(ContourNode *sought) {
Shinya Kitaoka 120a6e
  int indexId = m_identifiers[sought->m_ancestorContour];
Shinya Kitaoka 120a6e
  IndexColumn::iterator res;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Search for the HEAD attribute in index's Contour
Shinya Kitaoka 120a6e
  for (; !sought->hasAttribute(ContourNode::HEAD); sought = sought->m_next)
Shinya Kitaoka 120a6e
    ;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Finally, find index through our column
Shinya Kitaoka 120a6e
  for (res = m_columns[indexId].begin(); (*res) != sought; ++res)
Shinya Kitaoka 120a6e
    ;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return res;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Handles active contour merging due to split/vertex events
Shinya Kitaoka 120a6e
void IndexTable::merge(IndexColumn::iterator index1,
Shinya Kitaoka 120a6e
                       IndexColumn::iterator index2) {
Shinya Kitaoka 120a6e
  IndexColumn::iterator current;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  int identifier1 = m_identifiers[(*index1)->m_ancestorContour],
Shinya Kitaoka 120a6e
      identifier2 = m_identifiers[(*index2)->m_ancestorContour];
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  remove(index2);  // We maintain only one index of the merged contour
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, append columns
Shinya Kitaoka 120a6e
  if (!m_columns[identifier2].empty()) {
Shinya Kitaoka 120a6e
    append<indextable::indexcolumn, indextable::indexcolumn::reverse_iterator="">(</indextable::indexcolumn,>
Shinya Kitaoka 120a6e
        m_columns[identifier1], m_columns[identifier2]);
Shinya Kitaoka 120a6e
    m_columns[identifier2].clear();
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Then, update stored identifiers
Shinya Kitaoka 120a6e
  for (unsigned int k = 0; k < m_columns.size(); ++k) {
Shinya Kitaoka 120a6e
    if (m_identifiers[k] == identifier2) m_identifiers[k] = identifier1;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Removes given index in Table
Shinya Kitaoka 120a6e
inline void IndexTable::remove(IndexColumn::iterator index) {
Shinya Kitaoka 120a6e
  m_columns[m_identifiers[(*index)->m_ancestorContour]].erase(index);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void IndexTable::clear() { m_columns.clear(), m_identifiers.clear(); }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
//                    Straight Skeleton Algorithm
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
//      Global Variables
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
struct VectorizationContext {
Shinya Kitaoka 120a6e
  VectorizerCoreGlobals *m_globals;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Globals
Shinya Kitaoka 120a6e
  unsigned int m_totalNodes;      // Number of original contour nodes
Shinya Kitaoka 120a6e
  unsigned int m_contoursCount;   // Number of contours in input region
Shinya Kitaoka 120a6e
  IndexTable m_activeTable;       // Index table of active contours
Shinya Kitaoka 120a6e
  SkeletonGraph *m_output;        // Output skeleton of input region
Shinya Kitaoka 120a6e
  double m_currentHeight;         // Height of our 'roof-flooding' process
Shinya Kitaoka 120a6e
  Timeline m_timeline;            // Ordered queue of all possible events
Shinya Kitaoka 120a6e
  unsigned int m_algoritmicTime;  // Number of events precessed up to now
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Containers
Shinya Kitaoka 120a6e
  std::vector<contouredge> m_edgesHeap;</contouredge>
Shinya Kitaoka 120a6e
  std::vector<contournode> m_nodesHeap;  // of *non-original* nodes only</contournode>
Shinya Kitaoka 120a6e
  unsigned int m_nodesHeapCount;         // number of nodes used in nodesHeap
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  //'Linear Axis-added' *pseudo-original* nodes and edges
Shinya Kitaoka 120a6e
  std::vector<contournode> m_linearNodesHeap;</contournode>
Shinya Kitaoka 120a6e
  std::vector<contouredge> m_linearEdgesHeap;</contouredge>
Shinya Kitaoka 120a6e
  unsigned int m_linearNodesHeapCount;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  VectorizationContext(VectorizerCoreGlobals *globals) : m_globals(globals) {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  ContourNode *getNode() { return &m_nodesHeap[m_nodesHeapCount++]; }
Shinya Kitaoka 120a6e
  ContourNode *getLinearNode() {
Shinya Kitaoka 120a6e
    return &m_linearNodesHeap[m_linearNodesHeapCount];
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  ContourEdge *getLinearEdge() {
Shinya Kitaoka 120a6e
    return &m_linearEdgesHeap[m_linearNodesHeapCount++];
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline void addLinearNodeBefore(ContourNode *node);
Shinya Kitaoka 120a6e
  inline void repairDegenerations(
Shinya Kitaoka 120a6e
      const std::vector<contournode *=""> °enerates);</contournode>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline void prepareGlobals();
Shinya Kitaoka 120a6e
  inline void prepareContours(ContourFamily &family);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline void newSkeletonLink(unsigned int cur, ContourNode *node);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// WARNING: To be launched only *after* prepareContours - node countings happen
Shinya Kitaoka 120a6e
// there
Shinya Kitaoka 120a6e
inline void VectorizationContext::prepareGlobals() {
Shinya Kitaoka 120a6e
  // NOTE: Let n be the total number of nodes in the family, k the number of
Shinya Kitaoka 120a6e
  // split events
Shinya Kitaoka 120a6e
  //      effectively happening in the process, m the number of original
Shinya Kitaoka 120a6e
  //      contours of the family.
Shinya Kitaoka 120a6e
  //      Now:
Shinya Kitaoka 120a6e
  //        * Each split event eliminates its generating reflex node and
Shinya Kitaoka 120a6e
  //        introduces
Shinya Kitaoka 120a6e
  //          two convex nodes
Shinya Kitaoka 120a6e
  //        * Each edge event eliminates its couple of generating nodes and
Shinya Kitaoka 120a6e
  //          introduces one new convex node
Shinya Kitaoka 120a6e
  //        * Each max event eliminates 3 generating nodes without introducing
Shinya Kitaoka 120a6e
  //        new ones
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // So, split events introduce 2k non-original nodes, and (k-m+2) is the number
Shinya Kitaoka 120a6e
  // of max events
Shinya Kitaoka 120a6e
  // necessarily happening, since (m-1) are the *merging* split events.
Shinya Kitaoka 120a6e
  // On the n+k-3(k-m+2) nodes remaining for pure edge events, as many
Shinya Kitaoka 120a6e
  // non-original nodes are inserted.
Shinya Kitaoka 120a6e
  //=> This yields 2k + n-2k+3m-6= n+3m-6 non-original nodes. Contemporaneous
Shinya Kitaoka 38fd86
  // events such as
Shinya Kitaoka 120a6e
  // vertex and special events can only decrease the number of non-original
Shinya Kitaoka 120a6e
  // nodes requested.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Initialize non-original nodes container
Shinya Kitaoka 120a6e
  m_nodesHeap.resize(m_totalNodes + 3 * m_contoursCount - 6);
Shinya Kitaoka 120a6e
  m_nodesHeapCount = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Reset time/height variables
Shinya Kitaoka 120a6e
  m_currentHeight  = 0;
Shinya Kitaoka 120a6e
  m_algoritmicTime = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Clean IndexTable
Shinya Kitaoka 120a6e
  m_activeTable.clear();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void VectorizationContext::newSkeletonLink(unsigned int cur,
Shinya Kitaoka 120a6e
                                                  ContourNode *node) {
Shinya Kitaoka 120a6e
  if (node->hasAttribute(ContourNode::SK_NODE_DROPPED)) {
Shinya Kitaoka 120a6e
    SkeletonArc arcCopy(node);
Shinya Kitaoka 120a6e
    m_output->newLink(node->m_outputNode, cur, arcCopy);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    arcCopy.turn();
Shinya Kitaoka 120a6e
    m_output->newLink(cur, node->m_outputNode, arcCopy);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//===================================
Toshihiro Shimizu 890ddd
//    Thinning Functions/Methods
Toshihiro Shimizu 890ddd
//===================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//----------------------------------------
Toshihiro Shimizu 890ddd
//      Repair Polygon Degenerations
Toshihiro Shimizu 890ddd
//----------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION: After "Polygonizer", there may be simpleness degenerations
Shinya Kitaoka 120a6e
// about polygons which are dangerous to deal in the thinning process.
Shinya Kitaoka 120a6e
// Typically, these correspond to cases in which node->m_direction.z ~ 0
Toshihiro Shimizu 890ddd
//(too fast), and are concave.
Shinya Kitaoka 120a6e
// We then deal with them *before* the process begins, by splitting one
Shinya Kitaoka 120a6e
// such node in two slower ones (known as 'Linear Axis' method).
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
inline void VectorizationContext::addLinearNodeBefore(ContourNode *node) {
Shinya Kitaoka 120a6e
  ContourNode *newNode = getLinearNode();
Shinya Kitaoka 120a6e
  ContourEdge *newEdge = getLinearEdge();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newNode->m_position = node->m_position;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build new edge
Shinya Kitaoka 120a6e
  if (node->m_direction.z < 0.1)
Shinya Kitaoka 120a6e
    newEdge->m_direction = rotate270(node->m_edge->m_direction);
Shinya Kitaoka 120a6e
  else
Shinya Kitaoka 120a6e
    newEdge->m_direction = normalize(node->m_edge->m_direction +
Shinya Kitaoka 120a6e
                                     node->m_prev->m_edge->m_direction);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newNode->m_edge = newEdge;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Link newNode
Shinya Kitaoka 120a6e
  newNode->m_prev      = node->m_prev;
Shinya Kitaoka 120a6e
  newNode->m_next      = node;
Shinya Kitaoka 120a6e
  node->m_prev->m_next = newNode;
Shinya Kitaoka 120a6e
  node->m_prev         = newNode;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build remaining infos
Shinya Kitaoka 120a6e
  node->buildNodeInfos();  // Rebuild
Shinya Kitaoka 120a6e
  newNode->buildNodeInfos();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newNode->m_updateTime      = 0;
Shinya Kitaoka 120a6e
  newNode->m_ancestor        = node->m_ancestor;
Shinya Kitaoka 120a6e
  newNode->m_ancestorContour = node->m_ancestorContour;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Set node and newNode's edges not to be recognized as possible
Shinya Kitaoka 120a6e
  // opposites by the other (could happen in *future* instants)
Shinya Kitaoka 120a6e
  //                *DO NOT REMOVE!*
Shinya Kitaoka 120a6e
  node->m_notOpposites.push_back(newNode->m_edge);
Shinya Kitaoka 120a6e
  node->m_notOpposites.push_back(newNode->m_prev->m_edge);
Shinya Kitaoka 120a6e
  newNode->m_notOpposites.push_back(node->m_edge);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Further sign newly added node
Shinya Kitaoka 120a6e
  newNode->setAttribute(ContourNode::LINEAR_ADDED);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void VectorizationContext::repairDegenerations(
Shinya Kitaoka 120a6e
    const std::vector<contournode *=""> °enerates) {</contournode>
Shinya Kitaoka 120a6e
  unsigned int i;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_linearNodesHeap.resize(degenerates.size());
Shinya Kitaoka 120a6e
  m_linearEdgesHeap.resize(degenerates.size());
Shinya Kitaoka 120a6e
  m_linearNodesHeapCount = 0;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  for (i = 0; i < degenerates.size(); ++i) {
Shinya Kitaoka 120a6e
    if (!degenerates[i]->hasAttribute(ContourNode::AMBIGUOUS_LEFT)) {
Shinya Kitaoka 120a6e
      addLinearNodeBefore(degenerates[i]);
Shinya Kitaoka 120a6e
      m_totalNodes++;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------
Toshihiro Shimizu 890ddd
//    Node Infos Construction
Toshihiro Shimizu 890ddd
//--------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void VectorizationContext::prepareContours(ContourFamily &family) {
Shinya Kitaoka 120a6e
  std::vector<contournode *=""> degenerateNodes;</contournode>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build circular links
Shinya Kitaoka 120a6e
  unsigned int i, j, k;
Shinya Kitaoka 120a6e
  unsigned int current;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  m_contoursCount = family.size();
Shinya Kitaoka 120a6e
  m_totalNodes    = 0;
Shinya Kitaoka 120a6e
  for (i = 0; i < family.size(); ++i) {
Shinya Kitaoka 120a6e
    for (j = 0, k = family[i].size() - 1; j < family[i].size(); k = j, ++j) {
Shinya Kitaoka 120a6e
      family[i][k].m_next = &family[i][j];
Shinya Kitaoka 120a6e
      family[i][j].m_prev = &family[i][k];
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    m_totalNodes += family[i].size();
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build node edges
Shinya Kitaoka 120a6e
  m_edgesHeap.resize(m_totalNodes);
Shinya Kitaoka 120a6e
  current = 0;
Shinya Kitaoka 120a6e
  for (i = 0; i < family.size(); ++i) {
Shinya Kitaoka 120a6e
    for (j = 0, k = family[i].size() - 1; j < family[i].size(); k = j, ++j) {
Shinya Kitaoka 120a6e
      m_edgesHeap[current].m_direction = normalize(
Shinya Kitaoka 120a6e
          planeProjection(family[i][j].m_position - family[i][k].m_position));
Shinya Kitaoka 120a6e
      family[i][k].m_edge = &m_edgesHeap[current];
Shinya Kitaoka 120a6e
      current++;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bool maxThicknessNotZero = m_globals->currConfig->m_maxThickness > 0.0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now build remaining infos
Shinya Kitaoka 120a6e
  for (i = 0; i < family.size(); ++i) {
Shinya Kitaoka 120a6e
    for (j = 0; j < family[i].size(); ++j) {
Shinya Kitaoka 120a6e
      family[i][j].buildNodeInfos();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      family[i][j].m_updateTime = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      family[i][j].m_ancestor        = j;
Shinya Kitaoka 120a6e
      family[i][j].m_ancestorContour = i;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Check the following degeneration
Shinya Kitaoka 120a6e
      if (family[i][j].m_concave && family[i][j].m_direction.z < 0.3) {
Shinya Kitaoka 120a6e
        // Push this node among degenerate ones
Shinya Kitaoka 120a6e
        degenerateNodes.push_back(&family[i][j]);
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Insert output node in sharp angles
Shinya Kitaoka 120a6e
      if (!family[i][j].m_concave && family[i][j].m_direction.z < 0.6 &&
Shinya Kitaoka 120a6e
          maxThicknessNotZero) {
Shinya Kitaoka 120a6e
        family[i][j].setAttribute(ContourNode::SK_NODE_DROPPED);
Shinya Kitaoka 120a6e
        family[i][j].m_outputNode = m_output->newNode(family[i][j].m_position);
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Push on nodes having AMBIGUOUS_RIGHT attribute
Shinya Kitaoka 120a6e
      if (family[i][j].hasAttribute(ContourNode::AMBIGUOUS_RIGHT))
Shinya Kitaoka 120a6e
        family[i][j].m_position += 0.02 * family[i][j].m_direction;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, ensure polygon degenerations found are solved
Shinya Kitaoka 120a6e
  if (maxThicknessNotZero) repairDegenerations(degenerateNodes);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// WARNING: m_edge field of *this* and *previous* node must already be defined.
Shinya Kitaoka 120a6e
inline void ContourNode::buildNodeInfos(bool forceConvex) {
Shinya Kitaoka 120a6e
  TPointD direction;
Shinya Kitaoka 120a6e
  double parameter;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Calculate node convexity
Shinya Kitaoka 120a6e
  if (forceConvex)
Shinya Kitaoka 120a6e
    m_concave = 0;
Shinya Kitaoka 120a6e
  else if (cross(m_edge->m_direction, m_prev->m_edge->m_direction) < 0) {
Shinya Kitaoka 120a6e
    m_concave = 1;
Shinya Kitaoka 120a6e
  } else
Shinya Kitaoka 120a6e
    m_concave = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Build node direction
Shinya Kitaoka 120a6e
  direction = m_edge->m_direction - m_prev->m_edge->m_direction;
Shinya Kitaoka 120a6e
  parameter = norm(direction);
Shinya Kitaoka 120a6e
  if (parameter > 0.01) {
Shinya Kitaoka 120a6e
    direction                = direction * (1 / parameter);
Shinya Kitaoka 120a6e
    if (m_concave) direction = -direction;
Shinya Kitaoka 120a6e
  } else
Shinya Kitaoka 120a6e
    direction = rotate270(m_edge->m_direction);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  m_direction.x = direction.x;
Shinya Kitaoka 120a6e
  m_direction.y = direction.y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Calculate node speed
Shinya Kitaoka 120a6e
  m_direction.z = cross(planeProjection(m_direction), m_edge->m_direction);
Shinya Kitaoka 120a6e
  if (m_direction.z < 0) m_direction.z = 0;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Calculate angular momentum
Shinya Kitaoka 120a6e
  m_AngularMomentum = cross(m_position, m_direction);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (m_concave) {
Shinya Kitaoka 120a6e
    m_AuxiliaryMomentum1 = m_AuxiliaryMomentum2 = m_AngularMomentum;
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    m_AuxiliaryMomentum1 =
Shinya Kitaoka 120a6e
        cross(m_position,
Shinya Kitaoka 120a6e
              T3DPointD(m_edge->m_direction.y, -m_edge->m_direction.x, 1));
Shinya Kitaoka 120a6e
    m_AuxiliaryMomentum2 =
Shinya Kitaoka 120a6e
        cross(m_position, T3DPointD(m_prev->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                                    -m_prev->m_edge->m_direction.x, 1));
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//---------------------------------
Toshihiro Shimizu 890ddd
//      Timeline Construction
Toshihiro Shimizu 890ddd
//---------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// NOTE: In the following, we achieve these results:
Toshihiro Shimizu 890ddd
//        * Build the timeline - events priority queue
Toshihiro Shimizu 890ddd
//        * Process those split events which *necessarily* happen
Shinya Kitaoka 120a6e
// Pre-processing of split events is useful in order to lower execution times.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Each node is first associated to a random integer; then a referencing
Shinya Kitaoka 120a6e
// vector is ordered according to those integers - events are calculated
Shinya Kitaoka 120a6e
// following this order. Split events are therefore calculated sparsely
Shinya Kitaoka 120a6e
// along the polygons, allowing a significant time reduction effect.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class RandomizedNode {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  ContourNode *m_node;
Shinya Kitaoka 120a6e
  int m_number;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  RandomizedNode() {}
Shinya Kitaoka 120a6e
  RandomizedNode(ContourNode *node) : m_node(node), m_number(rand()) {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline ContourNode *operator->(void) { return m_node; }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
class RandomizedNodeLess {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  RandomizedNodeLess() {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  inline bool operator()(RandomizedNode a, RandomizedNode b) {
Shinya Kitaoka 120a6e
    return (a.m_number < b.m_number);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
void Timeline::build(ContourFamily &polygons, VectorizationContext &context,
Shinya Kitaoka 120a6e
                     VectorizerCore *thisVectorizer) {
Shinya Kitaoka 120a6e
  unsigned int i, j, current;
Shinya Kitaoka 120a6e
  std::vector<randomizednode> nodesToBeTreated(context.m_totalNodes);</randomizednode>
Shinya Kitaoka 120a6e
  T3DPointD momentum, ray;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Build casual ordered node-array
Shinya Kitaoka 120a6e
  for (i = 0, current = 0; i < polygons.size(); ++i)
Shinya Kitaoka 120a6e
    for (j                        = 0; j < polygons[i].size(); ++j)
Shinya Kitaoka 120a6e
      nodesToBeTreated[current++] = RandomizedNode(&polygons[i][j]);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Same for linear-added nodes
Shinya Kitaoka 120a6e
  for (i                        = 0; i < context.m_linearNodesHeapCount; ++i)
Shinya Kitaoka 120a6e
    nodesToBeTreated[current++] = RandomizedNode(&context.m_linearNodesHeap[i]);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double maxThickness = context.m_globals->currConfig->m_maxThickness;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Compute events generated by nodes
Shinya Kitaoka 120a6e
  // NOTE: are edge events to be computed BEFORE split ones?
Shinya Kitaoka 120a6e
  for (i = 0; i < nodesToBeTreated.size(); ++i) {
Shinya Kitaoka 120a6e
    // Break calculation at user cancel press
Shinya Kitaoka 120a6e
    if (thisVectorizer->isCanceled()) break;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    Event currentEvent(nodesToBeTreated[i].m_node, &context);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Notify event calculation
Shinya Kitaoka 120a6e
    if (!nodesToBeTreated[i].m_node->hasAttribute(ContourNode::LINEAR_ADDED))
Shinya Kitaoka 120a6e
      thisVectorizer->emitPartialDone();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    if (currentEvent.m_type != Event::failure &&
Shinya Kitaoka 120a6e
        currentEvent.m_height < maxThickness)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef _PREPROCESS
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      if (currentEvent.m_type == Event::split) {
Shinya Kitaoka 120a6e
        if (currentEvent.m_coGenerator->m_concave) {
Shinya Kitaoka 120a6e
          ray =
Shinya Kitaoka 120a6e
              T3DPointD(currentEvent.m_coGenerator->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                        -currentEvent.m_coGenerator->m_edge->m_direction.x, 1);
Shinya Kitaoka 120a6e
          momentum = cross(currentEvent.m_coGenerator->m_position, ray);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          if (currentEvent.m_generator->m_direction * momentum +
Shinya Kitaoka 120a6e
                  ray * currentEvent.m_generator->m_AngularMomentum <
Shinya Kitaoka 120a6e
              0) {
Shinya Kitaoka 120a6e
            timeline.push(currentEvent);
Shinya Kitaoka 120a6e
            continue;
Shinya Kitaoka 120a6e
          }
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (currentEvent.m_coGenerator->m_next->m_concave) {
Shinya Kitaoka 120a6e
          ray =
Shinya Kitaoka 120a6e
              T3DPointD(currentEvent.m_coGenerator->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                        -currentEvent.m_coGenerator->m_edge->m_direction.x, 1);
Shinya Kitaoka 120a6e
          momentum = cross(currentEvent.m_coGenerator->m_next->m_position, ray);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
          if (currentEvent.m_generator->m_direction * momentum +
Shinya Kitaoka 120a6e
                  ray * currentEvent.m_generator->m_AngularMomentum >
Shinya Kitaoka 120a6e
              0) {
Shinya Kitaoka 120a6e
            timeline.push(currentEvent);
Shinya Kitaoka 120a6e
            continue;
Shinya Kitaoka 120a6e
          }
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
        if (cross(currentEvent.m_generator->m_edge->m_direction,
Shinya Kitaoka 120a6e
                  currentEvent.m_coGenerator->m_edge->m_direction) > 0.02 &&
Shinya Kitaoka 120a6e
            cross(currentEvent.m_coGenerator->m_edge->m_direction,
Shinya Kitaoka 120a6e
                  currentEvent.m_generator->m_prev->m_edge->m_direction) >
Shinya Kitaoka 120a6e
                0.02)  // 0.02 in comparison with 'parameter' in buildNodeInfos
Shinya Kitaoka 120a6e
        {
Shinya Kitaoka 120a6e
          // Pre-processing succeeded
Shinya Kitaoka 120a6e
          currentEvent.process();
Shinya Kitaoka 120a6e
          continue;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
      }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    push(currentEvent);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
//      Event Calculation
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Calculates event generated by input node
Toshihiro Shimizu 890ddd
Event::Event(ContourNode *generator, VectorizationContext *context)
Shinya Kitaoka 120a6e
    : m_height(infinity)
Shinya Kitaoka 120a6e
    , m_displacement(infinity)
Shinya Kitaoka 120a6e
    , m_generator(generator)
Shinya Kitaoka 120a6e
    , m_type(failure)
Shinya Kitaoka 120a6e
    , m_algoritmicTime(context->m_algoritmicTime)
Shinya Kitaoka 120a6e
    , m_context(context) {
Shinya Kitaoka 120a6e
  if (generator->m_concave)
Shinya Kitaoka 120a6e
    calculateSplitEvent();
Shinya Kitaoka 120a6e
  else
Shinya Kitaoka 120a6e
    calculateEdgeEvent();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// The edge event *generated by a node* is defined as the earliest edge event
Toshihiro Shimizu 890ddd
// generated by its adjacent edges. Remember that 'edge events' correspond to
Toshihiro Shimizu 890ddd
// those in which one edge gets 0 length.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void Event::calculateEdgeEvent() {
Shinya Kitaoka 120a6e
  struct locals {
Shinya Kitaoka 120a6e
    static inline void buildDisplacements(ContourNode *edgeFirst, double &d1,
Shinya Kitaoka 120a6e
                                          double &d2) {
Shinya Kitaoka 120a6e
      ContourNode *edgeSecond = edgeFirst->m_next;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // If bisectors are almost opposite, avoid: there must be another bisector
Shinya Kitaoka 120a6e
      // colliding with m_generator *before* coGenerator - allowing a positive
Shinya Kitaoka 120a6e
      // result here may interfere with it.
Shinya Kitaoka 120a6e
      if ((edgeFirst->m_concave && edgeSecond->m_concave) ||
Shinya Kitaoka 120a6e
          edgeFirst->m_direction * edgeSecond->m_direction < -0.9) {
Shinya Kitaoka 120a6e
        d1 = d2 = -1.0;
Shinya Kitaoka 120a6e
        return;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      double det = edgeFirst->m_direction.y * edgeSecond->m_direction.x -
Shinya Kitaoka 120a6e
                   edgeFirst->m_direction.x * edgeSecond->m_direction.y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      double cx = edgeSecond->m_position.x - edgeFirst->m_position.x,
Shinya Kitaoka 120a6e
             cy = edgeSecond->m_position.y - edgeFirst->m_position.y;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      d1 = (edgeSecond->m_direction.x * cy - edgeSecond->m_direction.y * cx) /
Shinya Kitaoka 120a6e
           det;
Shinya Kitaoka 120a6e
      d2 =
Shinya Kitaoka 120a6e
          (edgeFirst->m_direction.x * cy - edgeFirst->m_direction.y * cx) / det;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    static inline double height(ContourNode *node, double displacement) {
Shinya Kitaoka 120a6e
      return node->m_position.z + displacement * node->m_direction.z;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  };  // locals
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double minHeight, minDisplacement;
Shinya Kitaoka 120a6e
  bool positiveEdgeDispl;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  m_type = edge;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Calculate the two possible displacement parameters
Shinya Kitaoka 120a6e
  double firstDisplacement, prevDisplacement, nextDisplacement,
Shinya Kitaoka 120a6e
      lastDisplacement;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // right == prev
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  locals::buildDisplacements(m_generator, nextDisplacement, lastDisplacement);
Shinya Kitaoka 120a6e
  locals::buildDisplacements(m_generator->m_prev, firstDisplacement,
Shinya Kitaoka 120a6e
                             prevDisplacement);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Take the smallest positive between them and assign the co-generator
Shinya Kitaoka 120a6e
  // NOTE: In a missed vertex event, the threshold value is to compare with the
Shinya Kitaoka 120a6e
  // possible pushes at the end of processSplit
Shinya Kitaoka 120a6e
  // However, admitting slightly negative displacements should be ok: due to the
Shinya Kitaoka 120a6e
  // weak linear axis imposed for concave
Shinya Kitaoka 120a6e
  // vertices, it is impossible to have little negative displacements apart from
Shinya Kitaoka 120a6e
  // the above mentioned pushed case.
Shinya Kitaoka 120a6e
  //   ..currently almost true..
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  static const double minusTol = -0.03;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bool prevDispPositive = (prevDisplacement > minusTol);
Shinya Kitaoka 120a6e
  bool nextDispPositive = (nextDisplacement > minusTol);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (nextDispPositive) {
Shinya Kitaoka 120a6e
    if (!prevDispPositive || nextDisplacement < prevDisplacement) {
Shinya Kitaoka 120a6e
      m_coGenerator     = m_generator;
Shinya Kitaoka 120a6e
      minDisplacement   = nextDisplacement;
Shinya Kitaoka 120a6e
      minHeight         = locals::height(m_coGenerator, nextDisplacement);
Shinya Kitaoka 120a6e
      positiveEdgeDispl = (nextDispPositive && lastDisplacement > minusTol);
Shinya Kitaoka 120a6e
    } else {
Shinya Kitaoka 120a6e
      m_coGenerator   = m_generator->m_prev;
Shinya Kitaoka 120a6e
      minDisplacement = prevDisplacement;
Shinya Kitaoka 120a6e
      minHeight       = locals::height(
Shinya Kitaoka 120a6e
          m_coGenerator,
Shinya Kitaoka 120a6e
          firstDisplacement);  // Height is built on the edge's first
Shinya Kitaoka 120a6e
      positiveEdgeDispl =
Shinya Kitaoka 120a6e
          (prevDispPositive &&
Shinya Kitaoka 120a6e
           firstDisplacement >
Shinya Kitaoka 120a6e
               minusTol);  // endpoint to have the same values on adjacent
Shinya Kitaoka 120a6e
    }                      // generators. It's important for SPECIAL events.
Shinya Kitaoka 120a6e
  } else if (prevDispPositive) {
Shinya Kitaoka 120a6e
    m_coGenerator   = m_generator->m_prev;
Shinya Kitaoka 120a6e
    minDisplacement = prevDisplacement;
Shinya Kitaoka 120a6e
    minHeight = locals::height(m_coGenerator, firstDisplacement);  // Same here
Shinya Kitaoka 120a6e
    positiveEdgeDispl = (prevDispPositive && firstDisplacement > minusTol);
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    m_type = failure;
Shinya Kitaoka 120a6e
    return;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // NOTA: Le const di tolleranza sono da confrontare tra:
Shinya Kitaoka 120a6e
  // a) i push alla fine di processSplit per evitare rogne coi vertex multipli
Shinya Kitaoka 120a6e
  // b) Le condizioni di esclusione su side1 e side2 in trySplit che evitano a)
Shinya Kitaoka 120a6e
  // c) Le condizioni di riconoscimento di vertex e special events - perche' se
Shinya Kitaoka 120a6e
  // mancano...
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Special cases: (forse da raffinare le condizioni - comunque ora sono
Shinya Kitaoka 120a6e
  // efficaci)
Shinya Kitaoka 120a6e
  if (nextDispPositive && !m_generator->m_concave) {
Shinya Kitaoka 120a6e
    if (m_generator->m_prev->m_concave && m_generator->m_next->m_concave &&
Shinya Kitaoka 120a6e
        fabs(nextDisplacement - prevDisplacement) <
Shinya Kitaoka 120a6e
            0.1)  // condizione debole per escludere subito i casi evidentemente
Shinya Kitaoka 120a6e
                  // innocenti
Shinya Kitaoka 120a6e
    {
Shinya Kitaoka 120a6e
      // Check 'V' (special) event - can generate a new concave vertex
Shinya Kitaoka 120a6e
      ContourNode *prevRay = m_generator->m_prev,
Shinya Kitaoka 120a6e
                  *nextRay = m_generator->m_next;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      double side = prevRay->m_direction * nextRay->m_AngularMomentum +
Shinya Kitaoka 120a6e
                    nextRay->m_direction * prevRay->m_AngularMomentum;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // NOTE: fabs(side) / || prevRay->dir x nextRay->dir ||  is the distance
Shinya Kitaoka 120a6e
      // between the two rays.
Shinya Kitaoka 120a6e
      if (fabs(side) <
Shinya Kitaoka 120a6e
          0.03 * norm(cross(prevRay->m_direction, nextRay->m_direction)))
Shinya Kitaoka 120a6e
        m_type = special, m_coGenerator = m_generator;
Shinya Kitaoka 120a6e
    } else if (fabs(nextDisplacement - prevDisplacement) < 0.01) {
Shinya Kitaoka 120a6e
      // Then choose to make the event with a concave vertex (to resemble the
Shinya Kitaoka 120a6e
      // 'LL' case)
Shinya Kitaoka 120a6e
      m_coGenerator =
Shinya Kitaoka 120a6e
          m_generator->m_next->m_concave ? m_generator : m_generator->m_prev;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, if calculated height is coherent, this Event is valid.
Shinya Kitaoka 120a6e
  if (positiveEdgeDispl  // Edges shrinking to a point after a FORWARD
Shinya Kitaoka 120a6e
      ||
Shinya Kitaoka 120a6e
      minHeight > m_context->m_currentHeight -
Shinya Kitaoka 120a6e
                      0.01)  // displacement are processable - this dominates
Shinya Kitaoka 120a6e
    m_height = minHeight,
Shinya Kitaoka 120a6e
    m_displacement =
Shinya Kitaoka 120a6e
        minDisplacement;  // height considerations which may be affected by
Shinya Kitaoka 120a6e
  else                    // numerical errors
Shinya Kitaoka 120a6e
    m_type = failure;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void Event::calculateSplitEvent() {
Shinya Kitaoka 120a6e
  unsigned int i;
Shinya Kitaoka 120a6e
  bool forceFirst;
Shinya Kitaoka 120a6e
  ContourNode *opposite, *first, *last;
Shinya Kitaoka 120a6e
  std::list<contournode *="">::iterator currentContour;</contournode>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Sign *edges* not to be taken as possible opposites
Shinya Kitaoka 120a6e
  for (i = 0; i < m_generator->m_notOpposites.size(); ++i)
Shinya Kitaoka 120a6e
    m_generator->m_notOpposites[i]->setAttribute(ContourEdge::NOT_OPPOSITE);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Check adjacent edge events
Shinya Kitaoka 120a6e
  calculateEdgeEvent();  // DO NOT REMOVE - adjacent convexes may have
Shinya Kitaoka 120a6e
                         // been calculated too earlier
Shinya Kitaoka 120a6e
  // First check opposites in the m_generator active contour
Shinya Kitaoka 120a6e
  first =
Shinya Kitaoka 120a6e
      m_generator->m_next->m_next;     // Adjacent edges were already considered
Shinya Kitaoka 120a6e
  last = m_generator->m_prev->m_prev;  // by calculateEdgeEvents()
Shinya Kitaoka 120a6e
  for (opposite = first; opposite != last; opposite = opposite->m_next) {
Shinya Kitaoka 120a6e
    if (!opposite->m_edge->hasAttribute(ContourEdge::NOT_OPPOSITE))
Shinya Kitaoka 120a6e
      tryRayEdgeCollisionWith(opposite);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  IndexTable &activeTable = m_context->m_activeTable;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Then, try in the remaining active contours whose identifier is != our
Shinya Kitaoka 120a6e
  for (i = 0; i < activeTable.m_columns.size(); ++i) {
Shinya Kitaoka 120a6e
    for (currentContour = activeTable[i]->begin();
Shinya Kitaoka 120a6e
         currentContour != activeTable[i]->end(); currentContour++) {
Shinya Kitaoka 120a6e
      // Da spostare sopra il 2o for
Shinya Kitaoka 120a6e
      if (activeTable.m_identifiers[(*currentContour)->m_ancestorContour] !=
Shinya Kitaoka 120a6e
          activeTable.m_identifiers[m_generator->m_ancestorContour]) {
Shinya Kitaoka 120a6e
        first = *currentContour;
Shinya Kitaoka 120a6e
        for (opposite = first, forceFirst = 1;
Shinya Kitaoka 120a6e
             // Better the first next cond. - in case of thinning errors, at
Shinya Kitaoka 120a6e
             // least it does not get loop'd.
Shinya Kitaoka 120a6e
             !opposite->hasAttribute(ContourNode::HEAD)  // opposite!=first
Shinya Kitaoka 120a6e
             || (forceFirst ? forceFirst = 0, 1 : 0);
Shinya Kitaoka 120a6e
             opposite = opposite->m_next) {
Shinya Kitaoka 120a6e
          if (!opposite->m_edge->hasAttribute(ContourEdge::NOT_OPPOSITE))
Shinya Kitaoka 120a6e
            tryRayEdgeCollisionWith(opposite);
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Restore edge attributes
Shinya Kitaoka 120a6e
  for (i = 0; i < m_generator->m_notOpposites.size(); ++i)
Shinya Kitaoka 120a6e
    m_generator->m_notOpposites[i]->clearAttribute(ContourEdge::NOT_OPPOSITE);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline bool Event::testRayEdgeCollision(ContourNode *opposite,
Shinya Kitaoka 120a6e
                                        double &displacement, double &height,
Shinya Kitaoka 120a6e
                                        double &side1, double &side2) {
Shinya Kitaoka 120a6e
  // Initialize test vectors
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // NOTE: In the convex case, slab guards MUST be orthogonal to the edge, due
Shinya Kitaoka 120a6e
  // to this case:
Shinya Kitaoka 120a6e
  //
Shinya Kitaoka 120a6e
  //    ______/|                the ray would not hit the edge - AND THUS FOREGO
Shinya Kitaoka 120a6e
  //    INTERACTION
Shinya Kitaoka 120a6e
  //           |                WITH IT COMPLETELY
Shinya Kitaoka 120a6e
  //     ->    |
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  T3DPointD firstSlabGuard =
Shinya Kitaoka 120a6e
      opposite->m_concave ? opposite->m_direction
Shinya Kitaoka 120a6e
                          : T3DPointD(opposite->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                                      -opposite->m_edge->m_direction.x, 1);
Shinya Kitaoka 120a6e
  T3DPointD lastSlabGuard =
Shinya Kitaoka 120a6e
      opposite->m_next->m_concave
Shinya Kitaoka 120a6e
          ? opposite->m_next->m_direction
Shinya Kitaoka 120a6e
          : T3DPointD(opposite->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                      -opposite->m_edge->m_direction.x, 1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  T3DPointD roofSlabOrthogonal(-opposite->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                               opposite->m_edge->m_direction.x, 1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (roofSlabOrthogonal * (opposite->m_position - m_generator->m_position) >
Shinya Kitaoka 120a6e
          -0.01  // Ray's vertex generator is below the roof slab
Shinya Kitaoka 120a6e
      //&& roofSlabOrthogonal * m_generator->m_direction > 0
Shinya Kitaoka 120a6e
      //// Ray must go 'against' the roof slab
Shinya Kitaoka 120a6e
      &&
Shinya Kitaoka 120a6e
      planeProjection(roofSlabOrthogonal) *
Shinya Kitaoka 120a6e
              planeProjection(m_generator->m_direction) >
Shinya Kitaoka 120a6e
          0  // Ray must go against the opposing edge
Shinya Kitaoka 120a6e
      &&
Shinya Kitaoka 120a6e
      (side1 = m_generator->m_direction *
Shinya Kitaoka 120a6e
                   opposite->m_AuxiliaryMomentum1 +  // Ray must pass inside the
Shinya Kitaoka 120a6e
                                                     // first slab guard
Shinya Kitaoka 120a6e
               firstSlabGuard * m_generator->m_AngularMomentum) > -0.01  //
Shinya Kitaoka 120a6e
      &&
Shinya Kitaoka 120a6e
      (side2 = m_generator->m_direction *
Shinya Kitaoka 120a6e
                   opposite->m_next->m_AuxiliaryMomentum2 +  // Ray must pass
Shinya Kitaoka 120a6e
                                                             // inside the
Shinya Kitaoka 120a6e
                                                             // second slab
Shinya Kitaoka 120a6e
                                                             // guard
Shinya Kitaoka 120a6e
               lastSlabGuard * m_generator->m_AngularMomentum) < 0.01  //
Shinya Kitaoka 120a6e
      &&
Shinya Kitaoka 120a6e
      (m_generator->m_ancestorContour !=
Shinya Kitaoka 120a6e
           opposite->m_ancestorContour  // Helps with immediate splits from
Shinya Kitaoka 120a6e
                                        // coincident
Shinya Kitaoka 120a6e
       || m_generator->m_ancestor != opposite->m_ancestor))  // linear vertexes
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    displacement = splitDisplacementWith(opposite);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Possible Security checks for almost complanarity cases
Shinya Kitaoka 120a6e
    //----------------------------------------
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (displacement > -0.01 && displacement < 0.01) {
Shinya Kitaoka 120a6e
      T3DPointD slabLeftOrthogonal(-opposite->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                                   opposite->m_edge->m_direction.x, 1);
Shinya Kitaoka 120a6e
      double check1 =
Shinya Kitaoka 120a6e
          (m_generator->m_position - opposite->m_position) *
Shinya Kitaoka 120a6e
          normalize(cross(opposite->m_direction, slabLeftOrthogonal));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      double check2 =
Shinya Kitaoka 120a6e
          (m_generator->m_position - opposite->m_next->m_position) *
Shinya Kitaoka 120a6e
          normalize(cross(opposite->m_next->m_direction, slabLeftOrthogonal));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (check1 > 0.02 || check2 < -0.02) return false;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    //----------------------------------------
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Check height/displacement conditions
Shinya Kitaoka 120a6e
    if (displacement > -0.01 &&
Shinya Kitaoka 120a6e
        displacement < m_displacement + 0.01  // admitting concurrent events
Shinya Kitaoka 120a6e
        &&
Shinya Kitaoka 120a6e
        (height = m_generator->m_position.z +
Shinya Kitaoka 120a6e
                  displacement * m_generator->m_direction.z) >
Shinya Kitaoka 120a6e
            m_context->m_currentHeight - 0.01)
Shinya Kitaoka 120a6e
      return true;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return false;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline bool Event::tryRayEdgeCollisionWith(ContourNode *opposite) {
Shinya Kitaoka 120a6e
  ContourNode *newCoGenerator;
Shinya Kitaoka 120a6e
  Type type;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  double displacement, height, side1, side2;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (testRayEdgeCollision(opposite, displacement, height, side1, side2)) {
Shinya Kitaoka 120a6e
    type           = split_regenerate;
Shinya Kitaoka 120a6e
    newCoGenerator = opposite;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Check against the REAL slab guards for type deduction
Shinya Kitaoka 120a6e
    double firstSide =
Shinya Kitaoka 120a6e
               opposite->m_concave
Shinya Kitaoka 120a6e
                   ? side1
Shinya Kitaoka 120a6e
                   : m_generator->m_direction * opposite->m_AngularMomentum +
Shinya Kitaoka 120a6e
                         opposite->m_direction * m_generator->m_AngularMomentum,
Shinya Kitaoka 120a6e
           secondSide = opposite->m_next->m_concave
Shinya Kitaoka 120a6e
                            ? side2
Shinya Kitaoka 120a6e
                            : m_generator->m_direction *
Shinya Kitaoka 120a6e
                                      opposite->m_next->m_AngularMomentum +
Shinya Kitaoka 120a6e
                                  opposite->m_next->m_direction *
Shinya Kitaoka 120a6e
                                      m_generator->m_AngularMomentum;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (firstSide > -0.01 && secondSide < 0.01) {
Shinya Kitaoka 120a6e
      double displacement_, height_;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (firstSide < 0.01) {
Shinya Kitaoka 120a6e
        // Ray hits first extremity of edge
Shinya Kitaoka 120a6e
        if (opposite->m_concave ||
Shinya Kitaoka 120a6e
            testRayEdgeCollision(opposite->m_prev, displacement_, height_,
Shinya Kitaoka 120a6e
                                 side1, side2))
Shinya Kitaoka 120a6e
          type = vertex;
Shinya Kitaoka 120a6e
      } else if (secondSide > -0.01) {
Shinya Kitaoka 120a6e
        // Ray hits second extremity of edge
Shinya Kitaoka 120a6e
        if (opposite->m_next->m_concave ||
Shinya Kitaoka 120a6e
            testRayEdgeCollision(opposite->m_next, displacement_, height_,
Shinya Kitaoka 120a6e
                                 side1, side2)) {
Shinya Kitaoka 120a6e
          type           = vertex;
Shinya Kitaoka 120a6e
          newCoGenerator = opposite->m_next;
Shinya Kitaoka 120a6e
        }
Shinya Kitaoka 120a6e
      } else
Shinya Kitaoka 120a6e
        type = split;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    if (type == split_regenerate &&
Shinya Kitaoka 120a6e
        height <=
Shinya Kitaoka 120a6e
            m_context
Shinya Kitaoka 120a6e
                ->m_currentHeight)  // Split regeneration is allowed only at
Shinya Kitaoka 120a6e
      return false;                 // future times
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // If competing with another event split/vertex, approve replacement only if
Shinya Kitaoka 120a6e
    // the angle
Shinya Kitaoka 120a6e
    // between m_generator and newCoGenerator is < than with current
Shinya Kitaoka 120a6e
    // m_coGenerator.
Shinya Kitaoka 120a6e
    if (m_type != edge && fabs(displacement - m_displacement) < 0.01 &&
Shinya Kitaoka 120a6e
        angleLess(m_coGenerator->m_edge->m_direction,
Shinya Kitaoka 120a6e
                  newCoGenerator->m_edge->m_direction,
Shinya Kitaoka 120a6e
                  m_generator->m_edge->m_direction))
Shinya Kitaoka 120a6e
      return false;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Pero' nel caso di quasi contemporaneo con un convesso, puo' permettere di
Shinya Kitaoka 120a6e
    // scegliere quello con Displacement > !! ...
Shinya Kitaoka 120a6e
    // Da rivedere... (cmq succede raramente che crei grossi problemi)
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    m_type = type, m_coGenerator = newCoGenerator;
Shinya Kitaoka 120a6e
    m_displacement = displacement, m_height = height;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    return true;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return false;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline double Event::splitDisplacementWith(ContourNode *slab) {
Shinya Kitaoka 120a6e
  TPointD slabLeftOrthogonal(-slab->m_edge->m_direction.y,
Shinya Kitaoka 120a6e
                             slab->m_edge->m_direction.x);
Shinya Kitaoka 120a6e
  double denom = m_generator->m_direction.z +
Shinya Kitaoka 120a6e
                 slabLeftOrthogonal * TPointD(m_generator->m_direction.x,
Shinya Kitaoka 120a6e
                                              m_generator->m_direction.y);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (denom < 0.01)
Shinya Kitaoka 120a6e
    return -1;  // generator-emitted ray is almost parallel to slab
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  TPointD difference =
Shinya Kitaoka 120a6e
      planeProjection(slab->m_position - m_generator->m_position);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return (slabLeftOrthogonal * difference + slab->m_position.z -
Shinya Kitaoka 120a6e
          m_generator->m_position.z) /
Shinya Kitaoka 120a6e
         denom;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
//      Event Processing
Toshihiro Shimizu 890ddd
//------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Event::Process discriminates event types and calls their specific handlers
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
inline bool Event::process() {
Shinya Kitaoka 120a6e
  Timeline &timeline           = m_context->m_timeline;
Shinya Kitaoka 120a6e
  unsigned int &algoritmicTime = m_context->m_algoritmicTime;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (!m_generator->hasAttribute(ContourNode::ELIMINATED)) {
Shinya Kitaoka 120a6e
    switch (m_type) {
Shinya Kitaoka 120a6e
    case special:
Shinya Kitaoka 120a6e
      assert(!m_coGenerator->hasAttribute(ContourNode::ELIMINATED));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (m_coGenerator->m_prev->hasAttribute(
Shinya Kitaoka 120a6e
              ContourNode::ELIMINATED) ||  // These two are most probably
Shinya Kitaoka 120a6e
                                           // useless - could
Shinya Kitaoka 120a6e
          m_coGenerator->m_next->hasAttribute(
Shinya Kitaoka 120a6e
              ContourNode::ELIMINATED) ||  // try to remove them once I'm in for
Shinya Kitaoka 120a6e
                                           // some testing...
Shinya Kitaoka 120a6e
          m_algoritmicTime < m_coGenerator->m_prev->m_updateTime ||
Shinya Kitaoka 120a6e
          m_algoritmicTime < m_coGenerator->m_next->m_updateTime) {
Shinya Kitaoka 120a6e
        // recalculate event
Shinya Kitaoka 120a6e
        Event newEvent(m_generator, m_context);
Shinya Kitaoka 120a6e
        if (newEvent.m_type != failure) timeline.push(newEvent);
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // else allow processing
Shinya Kitaoka 120a6e
      algoritmicTime++;
Shinya Kitaoka 120a6e
      processSpecialEvent();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    case edge:
Shinya Kitaoka 120a6e
      if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) ||
Shinya Kitaoka 120a6e
          m_algoritmicTime < m_coGenerator->m_next->m_updateTime) {
Shinya Kitaoka 120a6e
        // recalculate event
Shinya Kitaoka 120a6e
        Event newEvent(m_generator, m_context);
Shinya Kitaoka 120a6e
        if (newEvent.m_type != failure) timeline.push(newEvent);
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Deal with edge superposition cases *only* when m_generator has the
Shinya Kitaoka 120a6e
      // m_direction.z == 0.0
Shinya Kitaoka 120a6e
      if ((m_coGenerator->m_direction.z == 0.0 &&
Shinya Kitaoka 120a6e
           m_coGenerator != m_generator) ||
Shinya Kitaoka 120a6e
          (m_coGenerator->m_next->m_direction.z == 0.0 &&
Shinya Kitaoka 120a6e
           m_coGenerator == m_generator))
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // else allow processing
Shinya Kitaoka 120a6e
      algoritmicTime++;  // global
Shinya Kitaoka 120a6e
      if (m_generator->m_next->m_next == m_generator->m_prev)
Shinya Kitaoka 120a6e
        processMaxEvent();
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        processEdgeEvent();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    case vertex:
Shinya Kitaoka 120a6e
      if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED)) {
Shinya Kitaoka 120a6e
        // recalculate event
Shinya Kitaoka 120a6e
        Event newEvent(m_generator, m_context);
Shinya Kitaoka 120a6e
        if (newEvent.m_type != failure) timeline.push(newEvent);
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Unlike the split case, we don't need to rebuild if
Shinya Kitaoka 120a6e
      // the event is not up to date with m_coGenerator - since
Shinya Kitaoka 120a6e
      // the event is not about splitting an edge
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      if (m_coGenerator ==
Shinya Kitaoka 120a6e
              m_generator->m_next
Shinya Kitaoka 120a6e
                  ->m_next  // CAN devolve to a special event - which should
Shinya Kitaoka 120a6e
          ||
Shinya Kitaoka 120a6e
          m_coGenerator ==
Shinya Kitaoka 120a6e
              m_generator->m_prev
Shinya Kitaoka 120a6e
                  ->m_prev)  // already be present in the timeline
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // then, process it
Shinya Kitaoka 120a6e
      algoritmicTime++;
Shinya Kitaoka 120a6e
      processVertexEvent();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      break;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    case split_regenerate:
Shinya Kitaoka 120a6e
      if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) ||
Shinya Kitaoka 120a6e
          (m_algoritmicTime < m_coGenerator->m_next->m_updateTime)) {
Shinya Kitaoka 120a6e
        // recalculate event
Shinya Kitaoka 120a6e
        Event newEvent(m_generator, m_context);
Shinya Kitaoka 120a6e
        if (newEvent.m_type != failure) timeline.push(newEvent);
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // This may actually happen on current implementation, due to quirky event
Shinya Kitaoka 120a6e
    // generation and preferential events rejection. See function tryRay..()
Shinya Kitaoka 120a6e
    // around the end. Historically resolved to a split event, so we maintain
Shinya Kitaoka 120a6e
    // that.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // assert(false);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    /* fallthrough */
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    case split:  // No break is intended
Shinya Kitaoka 120a6e
      if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) ||
Shinya Kitaoka 120a6e
          (m_algoritmicTime < m_coGenerator->m_next->m_updateTime)) {
Shinya Kitaoka 120a6e
        // recalculate event
Shinya Kitaoka 120a6e
        Event newEvent(m_generator, m_context);
Shinya Kitaoka 120a6e
        if (newEvent.m_type != failure) timeline.push(newEvent);
Shinya Kitaoka 120a6e
        return false;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // else allow processing (but check these conditions)
Shinya Kitaoka 120a6e
      if (m_coGenerator != m_generator->m_next &&
Shinya Kitaoka 120a6e
          m_coGenerator !=
Shinya Kitaoka 120a6e
              m_generator->m_prev
Shinya Kitaoka 120a6e
                  ->m_prev)  // Because another edge already occurs at his place
Shinya Kitaoka 120a6e
      {
Shinya Kitaoka 120a6e
        algoritmicTime++;
Shinya Kitaoka 120a6e
        processSplitEvent();
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      break;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return true;  // Processing succeeded
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION:  Here is the typical case:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//        \       /
Toshihiro Shimizu 890ddd
//         \  x  /
Toshihiro Shimizu 890ddd
//          2---1 = m_coGenerator
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// m_coGenerator's edge reduces to 0. Then, nodes 1 and 2 gets ELIMINATED from
Shinya Kitaoka 120a6e
// the active contour and a new node at position "x" is placed instead.
Shinya Kitaoka 120a6e
// Observe also that nodes 1 or 2 may be concave (but not both)...
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
inline void Event::processEdgeEvent() {
Shinya Kitaoka 120a6e
  ContourNode *newNode;
Shinya Kitaoka 120a6e
  T3DPointD position(m_generator->m_position +
Shinya Kitaoka 120a6e
                     m_displacement * m_generator->m_direction);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Eliminate and unlink extremities of m_coGenerator's edge
Shinya Kitaoka 120a6e
  m_coGenerator->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
  m_coGenerator->m_next->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Then, take a node from heap and insert it at their place.
Shinya Kitaoka 120a6e
  newNode             = m_context->getNode();
Shinya Kitaoka 120a6e
  newNode->m_position = position;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newNode->m_next                       = m_coGenerator->m_next->m_next;
Shinya Kitaoka 120a6e
  m_coGenerator->m_next->m_next->m_prev = newNode;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newNode->m_prev               = m_coGenerator->m_prev;
Shinya Kitaoka 120a6e
  m_coGenerator->m_prev->m_next = newNode;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Then, initialize new node (however, 3rd component is m_height...)
Shinya Kitaoka 120a6e
  newNode->m_position =
Shinya Kitaoka 120a6e
      m_generator->m_position + m_displacement * m_generator->m_direction;
Shinya Kitaoka 120a6e
  newNode->m_edge = m_coGenerator->m_next->m_edge;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newNode->buildNodeInfos(1);  // 1 => Force convex node
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newNode->m_ancestor        = m_coGenerator->m_next->m_ancestor;
Shinya Kitaoka 120a6e
  newNode->m_ancestorContour = m_coGenerator->m_next->m_ancestorContour;
Shinya Kitaoka 120a6e
  newNode->m_updateTime      = m_context->m_algoritmicTime;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // We allocate an output vertex on newNode's position under these conditions
Shinya Kitaoka 120a6e
  // NOTE: Update once graph_old is replaced
Shinya Kitaoka 120a6e
  if (newNode->m_direction.z < 0.7 ||
Shinya Kitaoka 120a6e
      m_coGenerator->hasAttribute(ContourNode::SK_NODE_DROPPED) ||
Shinya Kitaoka 120a6e
      m_coGenerator->m_next->hasAttribute(ContourNode::SK_NODE_DROPPED)) {
Shinya Kitaoka 120a6e
    newNode->setAttribute(ContourNode::SK_NODE_DROPPED);
Shinya Kitaoka 120a6e
    newNode->m_outputNode = m_context->m_output->newNode(position);
Shinya Kitaoka 120a6e
    m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator);
Shinya Kitaoka 120a6e
    m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_next);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // If m_coGenerator or its m_next is HEAD of this contour, then
Shinya Kitaoka 120a6e
  // redefine newNode as the new head.
Shinya Kitaoka 120a6e
  if (m_coGenerator->hasAttribute(ContourNode::HEAD) ||
Shinya Kitaoka 120a6e
      m_coGenerator->m_next->hasAttribute(ContourNode::HEAD)) {
Shinya Kitaoka 120a6e
    std::list<contournode *="">::iterator it;</contournode>
Shinya Kitaoka 120a6e
    std::list<contournode *=""> &column =</contournode>
Shinya Kitaoka 120a6e
        m_context->m_activeTable.columnOfId(m_generator->m_ancestorContour);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    for (it = column.begin(); !(*it)->hasAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
         ++it)
Shinya Kitaoka 120a6e
      ;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // assert(*it == m_coGenerator || *it == m_coGenerator->m_next);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    *it = newNode, newNode->setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, calculate the Event raising by newNode
Shinya Kitaoka 120a6e
  Event newEvent(newNode, m_context);
Shinya Kitaoka 120a6e
  if (newEvent.m_type != Event::failure) m_context->m_timeline.push(newEvent);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Typical triangle case
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void Event::processMaxEvent() {
Shinya Kitaoka 120a6e
  T3DPointD position(m_generator->m_position +
Shinya Kitaoka 120a6e
                     m_displacement * m_generator->m_direction);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  unsigned int outputNode = m_context->m_output->newNode(position);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(outputNode, m_generator);
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(outputNode, m_generator->m_prev);
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(outputNode, m_generator->m_next);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Then remove active contour and eliminate nodes
Shinya Kitaoka 120a6e
  std::list<contournode *="">::iterator eventVertexIndex =</contournode>
Shinya Kitaoka 120a6e
      m_context->m_activeTable.find(m_generator);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_context->m_activeTable.remove(eventVertexIndex);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_generator->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
  m_generator->m_prev->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
  m_generator->m_next->setAttribute(ContourNode::ELIMINATED);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION: Ordinary split event:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//   m_coGenerator = a'---------b'
Toshihiro Shimizu 890ddd
//                         x
Toshihiro Shimizu 890ddd
//                         b = m_generator
Toshihiro Shimizu 890ddd
//                        / \
Toshihiro Shimizu 890ddd
//                       c   a
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// We eliminate b and split/merge the border/s represented in the scheme.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
inline void Event::processSplitEvent() {
Shinya Kitaoka 120a6e
  ContourNode *newLeftNode,
Shinya Kitaoka 120a6e
      *newRightNode;  // left-right in the sense of the picture
Shinya Kitaoka 120a6e
  T3DPointD position(m_generator->m_position +
Shinya Kitaoka 120a6e
                     m_displacement * m_generator->m_direction);
Shinya Kitaoka 120a6e
  IndexTable &activeTable      = m_context->m_activeTable;
Shinya Kitaoka 120a6e
  unsigned int &algoritmicTime = m_context->m_algoritmicTime;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // First, we find in the Index Table the contours involved
Shinya Kitaoka 120a6e
  std::list<contournode *="">::iterator genContour, coGenContour;</contournode>
Shinya Kitaoka 120a6e
  genContour = activeTable.find(m_generator);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
Shinya Kitaoka 120a6e
      activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) {
Shinya Kitaoka 120a6e
    // We have two different contours, that merge in one
Shinya Kitaoka 120a6e
    coGenContour = activeTable.find(m_coGenerator);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, update known nodes
Shinya Kitaoka 120a6e
  m_generator->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Allocate 2 new nodes and link the following way:
Shinya Kitaoka 120a6e
  newLeftNode             = m_context->getNode();
Shinya Kitaoka 120a6e
  newRightNode            = m_context->getNode();
Shinya Kitaoka 120a6e
  newLeftNode->m_position = newRightNode->m_position = position;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // On the right side
Shinya Kitaoka 120a6e
  m_coGenerator->m_next->m_prev = newRightNode;
Shinya Kitaoka 120a6e
  newRightNode->m_next          = m_coGenerator->m_next;
Shinya Kitaoka 120a6e
  m_generator->m_prev->m_next   = newRightNode;
Shinya Kitaoka 120a6e
  newRightNode->m_prev          = m_generator->m_prev;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // On the left side
Shinya Kitaoka 120a6e
  m_coGenerator->m_next       = newLeftNode;
Shinya Kitaoka 120a6e
  newLeftNode->m_prev         = m_coGenerator;
Shinya Kitaoka 120a6e
  m_generator->m_next->m_prev = newLeftNode;
Shinya Kitaoka 120a6e
  newLeftNode->m_next         = m_generator->m_next;
Shinya Kitaoka 120a6e
luzpaz 27707d
  // Assign and calculate the new nodes' information
Shinya Kitaoka 120a6e
  newLeftNode->m_edge  = m_generator->m_edge;
Shinya Kitaoka 120a6e
  newRightNode->m_edge = m_coGenerator->m_edge;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newLeftNode->m_ancestor         = m_generator->m_ancestor;
Shinya Kitaoka 120a6e
  newLeftNode->m_ancestorContour  = m_generator->m_ancestorContour;
Shinya Kitaoka 120a6e
  newRightNode->m_ancestor        = m_coGenerator->m_ancestor;
Shinya Kitaoka 120a6e
  newRightNode->m_ancestorContour = m_coGenerator->m_ancestorContour;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // We can force the new nodes to be convex
Shinya Kitaoka 120a6e
  newLeftNode->buildNodeInfos(1);
Shinya Kitaoka 120a6e
  newRightNode->buildNodeInfos(1);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newLeftNode->m_updateTime = newRightNode->m_updateTime = algoritmicTime;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, output the found interaction
Shinya Kitaoka 120a6e
  newLeftNode->setAttribute(ContourNode::SK_NODE_DROPPED);
Shinya Kitaoka 120a6e
  newRightNode->setAttribute(ContourNode::SK_NODE_DROPPED);
Shinya Kitaoka 120a6e
  newLeftNode->m_outputNode  = m_context->m_output->newNode(position);
Shinya Kitaoka 120a6e
  newRightNode->m_outputNode = newLeftNode->m_outputNode;
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(newLeftNode->m_outputNode, m_generator);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Update the active Index Table:
Shinya Kitaoka 120a6e
  if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
Shinya Kitaoka 120a6e
      activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) {
Shinya Kitaoka 120a6e
    // If we have two different contours, they merge in one
Shinya Kitaoka 120a6e
    // We keep coGenContour and remove genContour
Shinya Kitaoka 120a6e
    (*genContour)->clearAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
    activeTable.merge(coGenContour, genContour);
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    // Else we have only one contour, which splits in two
Shinya Kitaoka 120a6e
    (*genContour)->clearAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
    *genContour = newLeftNode;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    newLeftNode->setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
    newRightNode->setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    activeTable.columnOfId(m_generator->m_ancestorContour)
Shinya Kitaoka 120a6e
        .push_back(newRightNode);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // (Vertex compatibility): Moving newRightNode a bit on
Shinya Kitaoka 120a6e
  newRightNode->m_position += 0.02 * newRightNode->m_direction;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, calculate the new left and right Events
Shinya Kitaoka 120a6e
  Event newLeftEvent(newLeftNode, m_context);
Shinya Kitaoka 120a6e
  if (newLeftEvent.m_type != Event::failure)
Shinya Kitaoka 120a6e
    m_context->m_timeline.push(newLeftEvent);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  Event newRightEvent(newRightNode, m_context);
Shinya Kitaoka 120a6e
  if (newRightEvent.m_type != Event::failure)
Shinya Kitaoka 120a6e
    m_context->m_timeline.push(newRightEvent);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//               c     L     a'
Toshihiro Shimizu 890ddd
//                \         /
Toshihiro Shimizu 890ddd
//  m_generator =  b   x   b' = m_coGenerator
Toshihiro Shimizu 890ddd
//                /         \
Toshihiro Shimizu 890ddd
//               a     R     c'
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Reflex vertices b and b' collide. Observe that a new reflex vertex may rise
Shinya Kitaoka 120a6e
// here.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
inline void Event::processVertexEvent() {
Shinya Kitaoka 120a6e
  ContourNode *newLeftNode,
Shinya Kitaoka 120a6e
      *newRightNode;  // left-right in the sense of the picture
Shinya Kitaoka 120a6e
  T3DPointD position(m_generator->m_position +
Shinya Kitaoka 120a6e
                     m_displacement * m_generator->m_direction);
Shinya Kitaoka 120a6e
  IndexTable &activeTable      = m_context->m_activeTable;
Shinya Kitaoka 120a6e
  unsigned int &algoritmicTime = m_context->m_algoritmicTime;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // First, we find in the Index Table the contours involved
Shinya Kitaoka 120a6e
  std::list<contournode *="">::iterator genContour, coGenContour;</contournode>
Shinya Kitaoka 120a6e
  genContour = activeTable.find(m_generator);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
Shinya Kitaoka 120a6e
      activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) {
Shinya Kitaoka 120a6e
    // We have two different contours, that merge in one
Shinya Kitaoka 120a6e
    coGenContour = activeTable.find(m_coGenerator);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, update known nodes
Shinya Kitaoka 120a6e
  m_generator->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
  m_coGenerator->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Allocate 2 new nodes and link the following way:
Shinya Kitaoka 120a6e
  newLeftNode             = m_context->getNode();
Shinya Kitaoka 120a6e
  newRightNode            = m_context->getNode();
Shinya Kitaoka 120a6e
  newLeftNode->m_position = newRightNode->m_position = position;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // On the right side
Shinya Kitaoka 120a6e
  m_coGenerator->m_next->m_prev = newRightNode;
Shinya Kitaoka 120a6e
  newRightNode->m_next          = m_coGenerator->m_next;
Shinya Kitaoka 120a6e
  m_generator->m_prev->m_next   = newRightNode;
Shinya Kitaoka 120a6e
  newRightNode->m_prev          = m_generator->m_prev;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // On the left side
Shinya Kitaoka 120a6e
  m_coGenerator->m_prev->m_next = newLeftNode;
Shinya Kitaoka 120a6e
  newLeftNode->m_prev           = m_coGenerator->m_prev;
Shinya Kitaoka 120a6e
  m_generator->m_next->m_prev   = newLeftNode;
Shinya Kitaoka 120a6e
  newLeftNode->m_next           = m_generator->m_next;
Shinya Kitaoka 120a6e
luzpaz 27707d
  // Assign and calculate the new nodes' information
Shinya Kitaoka 120a6e
  newLeftNode->m_edge  = m_generator->m_edge;
Shinya Kitaoka 120a6e
  newRightNode->m_edge = m_coGenerator->m_edge;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newLeftNode->m_ancestor         = m_generator->m_ancestor;
Shinya Kitaoka 120a6e
  newLeftNode->m_ancestorContour  = m_generator->m_ancestorContour;
Shinya Kitaoka 120a6e
  newRightNode->m_ancestor        = m_coGenerator->m_ancestor;
Shinya Kitaoka 120a6e
  newRightNode->m_ancestorContour = m_coGenerator->m_ancestorContour;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // We *CAN'T* force the new nodes to be convex here
Shinya Kitaoka 120a6e
  newLeftNode->buildNodeInfos();
Shinya Kitaoka 120a6e
  newRightNode->buildNodeInfos();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  newLeftNode->m_updateTime = newRightNode->m_updateTime = algoritmicTime;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Now, output the found interaction
Shinya Kitaoka 120a6e
  newLeftNode->setAttribute(ContourNode::SK_NODE_DROPPED);
Shinya Kitaoka 120a6e
  newRightNode->setAttribute(ContourNode::SK_NODE_DROPPED);
Shinya Kitaoka 120a6e
  newLeftNode->m_outputNode  = m_context->m_output->newNode(position);
Shinya Kitaoka 120a6e
  newRightNode->m_outputNode = newLeftNode->m_outputNode;
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(newLeftNode->m_outputNode, m_generator);
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(newLeftNode->m_outputNode, m_coGenerator);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Update the active Index Table
Shinya Kitaoka 120a6e
  if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
Shinya Kitaoka 120a6e
      activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) {
Shinya Kitaoka 120a6e
    // If we have two different contours, they merge in one
Shinya Kitaoka 120a6e
    (*coGenContour)->clearAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
    activeTable.merge(genContour, coGenContour);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // Check if the generator is head, if so update.
Shinya Kitaoka 120a6e
    if (m_generator->hasAttribute(ContourNode::HEAD)) {
Shinya Kitaoka 120a6e
      newLeftNode->setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
      *genContour = newLeftNode;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  } else {
Shinya Kitaoka 120a6e
    // Else we have only one contour, which splits in two
Shinya Kitaoka 120a6e
    (*genContour)->clearAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
    *genContour = newLeftNode;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    newLeftNode->setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
    newRightNode->setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    activeTable.columnOfId(m_generator->m_ancestorContour)
Shinya Kitaoka 120a6e
        .push_back(newRightNode);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Before calculating the new interactions, to each new node we assign
Shinya Kitaoka 120a6e
  // as impossible opposite edges the adjacent of the other node.
Shinya Kitaoka 120a6e
  if (newLeftNode->m_concave) {
Shinya Kitaoka 120a6e
    newLeftNode->m_notOpposites = m_generator->m_notOpposites;
Shinya Kitaoka 120a6e
    append<std::vector<contouredge *="">,</std::vector<contouredge>
Shinya Kitaoka 120a6e
           std::vector<contouredge *="">::reverse_iterator>(</contouredge>
Shinya Kitaoka 120a6e
        newLeftNode->m_notOpposites, m_coGenerator->m_notOpposites);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    newLeftNode->m_notOpposites.push_back(newRightNode->m_edge);
Shinya Kitaoka 120a6e
    newLeftNode->m_notOpposites.push_back(newRightNode->m_prev->m_edge);
Campbell Barton d89022
  } else if (newRightNode->m_concave) {
Shinya Kitaoka 120a6e
    newRightNode->m_notOpposites = m_generator->m_notOpposites;
Shinya Kitaoka 120a6e
    append<std::vector<contouredge *="">,</std::vector<contouredge>
Shinya Kitaoka 120a6e
           std::vector<contouredge *="">::reverse_iterator>(</contouredge>
Shinya Kitaoka 120a6e
        newRightNode->m_notOpposites, m_coGenerator->m_notOpposites);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    newRightNode->m_notOpposites.push_back(newLeftNode->m_edge);
Shinya Kitaoka 120a6e
    newRightNode->m_notOpposites.push_back(newLeftNode->m_prev->m_edge);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // We also forbid newRightNode to be involved in events at the same location
Shinya Kitaoka 120a6e
  // of this one.
Shinya Kitaoka 120a6e
  // We just push its position in the m_direction by 0.02.
Shinya Kitaoka 120a6e
  newRightNode->m_position += 0.02 * newRightNode->m_direction;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, calculate the new left and right Events
Shinya Kitaoka 120a6e
  Event newLeftEvent(newLeftNode, m_context);
Shinya Kitaoka 120a6e
  if (newLeftEvent.m_type != Event::failure)
Shinya Kitaoka 120a6e
    m_context->m_timeline.push(newLeftEvent);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  Event newRightEvent(newRightNode, m_context);
Shinya Kitaoka 120a6e
  if (newRightEvent.m_type != Event::failure)
Shinya Kitaoka 120a6e
    m_context->m_timeline.push(newRightEvent);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// EXPLANATION:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//             x
Toshihiro Shimizu 890ddd
//        ---c   a---
Toshihiro Shimizu 890ddd
//            \ /
Toshihiro Shimizu 890ddd
//             b = m_coGenerator
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Typical "V" event in which rays emitted from a, b and c collide.
Shinya Kitaoka 120a6e
// This events have to be recognized different from vertex events, and
Shinya Kitaoka 120a6e
// better treated as a whole event, rather than two simultaneous edge events.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline void Event::processSpecialEvent() {
Shinya Kitaoka 120a6e
  ContourNode *newNode;
Shinya Kitaoka 120a6e
  T3DPointD position(m_generator->m_position +
Shinya Kitaoka 120a6e
                     m_displacement * m_generator->m_direction);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_coGenerator->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
  m_coGenerator->m_prev->setAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
  m_coGenerator->m_next->setAttribute(ContourNode::ELIMINATED);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Get and link newNode to the rest of this contour
Shinya Kitaoka 120a6e
  newNode             = m_context->getNode();
Shinya Kitaoka 120a6e
  newNode->m_position = position;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_coGenerator->m_prev->m_prev->m_next = newNode;
Shinya Kitaoka 120a6e
  newNode->m_prev                       = m_coGenerator->m_prev->m_prev;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_coGenerator->m_next->m_next->m_prev = newNode;
Shinya Kitaoka 120a6e
  newNode->m_next                       = m_coGenerator->m_next->m_next;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Then, initialize newNode infos
Shinya Kitaoka 120a6e
  newNode->m_edge = m_coGenerator->m_next->m_edge;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  newNode->m_ancestor        = m_coGenerator->m_next->m_ancestor;
Shinya Kitaoka 120a6e
  newNode->m_ancestorContour = m_coGenerator->m_next->m_ancestorContour;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Neither this case can be forced convex
Shinya Kitaoka 120a6e
  newNode->buildNodeInfos();
Shinya Kitaoka 120a6e
  newNode->m_updateTime = m_context->m_algoritmicTime;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Now build output
Shinya Kitaoka 120a6e
  newNode->setAttribute(ContourNode::SK_NODE_DROPPED);
Shinya Kitaoka 120a6e
  newNode->m_outputNode = m_context->m_output->newNode(position);
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_prev);
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator);
Shinya Kitaoka 120a6e
  m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_next);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // If m_coGenerator or one of his adjacents is HEAD of this contour, then
Shinya Kitaoka 120a6e
  // redefine newNode as the new head.
Shinya Kitaoka 120a6e
  if (m_coGenerator->hasAttribute(ContourNode::HEAD) ||
Shinya Kitaoka 120a6e
      m_coGenerator->m_next->hasAttribute(ContourNode::HEAD) ||
Shinya Kitaoka 120a6e
      m_coGenerator->m_prev->hasAttribute(ContourNode::HEAD)) {
Shinya Kitaoka 120a6e
    std::list<contournode *="">::iterator it;</contournode>
Shinya Kitaoka 120a6e
    std::list<contournode *=""> &column =</contournode>
Shinya Kitaoka 120a6e
        m_context->m_activeTable.columnOfId(m_generator->m_ancestorContour);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    for (it = column.begin(); !(*it)->hasAttribute(ContourNode::ELIMINATED);
Shinya Kitaoka 120a6e
         ++it)
Shinya Kitaoka 120a6e
      ;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // assert(*it == m_coGenerator || *it == m_coGenerator->m_next || *it ==
Shinya Kitaoka 120a6e
    // m_coGenerator->m_prev);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    *it = newNode, newNode->setAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Finally, calculate the Event raising by newNode
Shinya Kitaoka 120a6e
  Event newEvent(newNode, m_context);
Shinya Kitaoka 120a6e
  if (newEvent.m_type != Event::failure) m_context->m_timeline.push(newEvent);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
//    Straight Skeleton mains
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
Campbell Barton b3bd84
static SkeletonGraph *skeletonize(ContourFamily ®ionContours,
Campbell Barton b3bd84
                                  VectorizationContext &context,
Campbell Barton b3bd84
                                  VectorizerCore *thisVectorizer) {
Shinya Kitaoka 120a6e
  SkeletonGraph *output = context.m_output = new SkeletonGraph;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  context.prepareContours(regionContours);
Shinya Kitaoka 120a6e
  context.prepareGlobals();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  IndexTable &activeTable = context.m_activeTable;
Shinya Kitaoka 120a6e
  activeTable.build(regionContours);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  double maxThickness = context.m_globals->currConfig->m_maxThickness;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (maxThickness > 0.0)  // if(!currConfig->m_outline)
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    Timeline &timeline = context.m_timeline;
Shinya Kitaoka 120a6e
    timeline.build(regionContours, context, thisVectorizer);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef _SSDEBUG
Shinya Kitaoka 120a6e
    SSDebugger debugger(context);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    bool spawnDebugger = false;
Shinya Kitaoka 120a6e
    if (timeline.size() > 1000) {
Shinya Kitaoka 120a6e
      debugger.m_height = context.m_currentHeight;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      debugger.show();
Shinya Kitaoka 120a6e
      debugger.raise();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      debugger.repaint();
Shinya Kitaoka 120a6e
      debugger.loop();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      spawnDebugger = true;
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    if (thisVectorizer->isCanceled()) {
Shinya Kitaoka 120a6e
      // Bailing out
Shinya Kitaoka 120a6e
      while (!timeline.empty()) timeline.pop();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      context.m_nodesHeap.clear();
Shinya Kitaoka 120a6e
      context.m_edgesHeap.clear();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      context.m_linearNodesHeap.clear();
Shinya Kitaoka 120a6e
      context.m_linearEdgesHeap.clear();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      return output;
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Process timeline
Shinya Kitaoka 120a6e
    while (!timeline.empty()) {
Shinya Kitaoka 120a6e
      Event currentEvent = timeline.top();
Shinya Kitaoka 120a6e
      timeline.pop();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      // If maxThickness hit, stop before processing
Shinya Kitaoka 120a6e
      if (currentEvent.m_height >= maxThickness) break;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Redraw debugger window
Toshihiro Shimizu 890ddd
#ifdef _SSDEBUG
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      if (spawnDebugger && debugger.isOnScreen(currentEvent.m_generator)) {
Shinya Kitaoka 120a6e
        debugger.m_height = currentEvent.m_height;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
        debugger.repaint();
Shinya Kitaoka 120a6e
        debugger.loop();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
        if (currentEvent.m_type == Event::split ||
Shinya Kitaoka 120a6e
            currentEvent.m_type == Event::vertex)
Shinya Kitaoka 120a6e
          currentEvent.tryRayEdgeCollisionWith(currentEvent.m_coGenerator);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
        if (currentEvent.m_type == Event::edge)
Shinya Kitaoka 120a6e
          currentEvent.calculateEdgeEvent();
Shinya Kitaoka 120a6e
      }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
#endif  // _SSDEBUG
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      // Process event
Shinya Kitaoka 120a6e
      currentEvent.process();
Shinya Kitaoka 120a6e
      context.m_currentHeight = currentEvent.m_height;
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // The thinning process terminates: deleting non-original nodes and edges.
Shinya Kitaoka 120a6e
    while (!timeline.empty()) timeline.pop();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef _SSDEBUG
Shinya Kitaoka 120a6e
    if (spawnDebugger) {
Shinya Kitaoka 120a6e
      debugger.m_height = context.m_currentHeight;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      debugger.repaint();
Shinya Kitaoka 120a6e
      debugger.loop();
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
#endif  // _SSDEBUG
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, update remaining nodes not processed due to maxThickness and
Shinya Kitaoka 120a6e
  // connect them to output skeleton
Shinya Kitaoka 120a6e
  unsigned int i, l, n;
Shinya Kitaoka 120a6e
  IndexTable::IndexColumn::iterator j;
Shinya Kitaoka 120a6e
  ContourNode *k;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (i = 0; i < regionContours.size(); ++i)
Shinya Kitaoka 120a6e
    for (j = activeTable[i]->begin(); j != activeTable[i]->end(); ++j) {
Shinya Kitaoka 120a6e
      unsigned int count = 0;
Shinya Kitaoka 120a6e
      unsigned int addedNode;
Shinya Kitaoka 120a6e
      for (k = *j; !k->hasAttribute(ContourNode::HEAD) || !count;
Shinya Kitaoka 120a6e
           k = k->m_next) {
Shinya Kitaoka 120a6e
        addedNode = output->newNode(
Shinya Kitaoka 120a6e
            k->m_position +
Shinya Kitaoka 120a6e
            k->m_direction *
Shinya Kitaoka 120a6e
                ((maxThickness - k->m_position.z) /
Shinya Kitaoka 120a6e
                 (k->m_direction.z > 0.01 ? k->m_direction.z : 1)));
Shinya Kitaoka 120a6e
        context.newSkeletonLink(addedNode, k);
Shinya Kitaoka 120a6e
        // output->node(addedNode).setAttribute(ContourNode::SS_OUTLINE);
Shinya Kitaoka 120a6e
        ++count;
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      n = output->getNodesCount();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      SkeletonArc arcCopy;
Shinya Kitaoka 120a6e
      SkeletonArc arcCopyRev;
Shinya Kitaoka 120a6e
      arcCopy.setAttribute(SkeletonArc::SS_OUTLINE);
Shinya Kitaoka 120a6e
      arcCopyRev.setAttribute(SkeletonArc::SS_OUTLINE_REVERSED);
Shinya Kitaoka 120a6e
      for (l = 1; l < count; ++l) {
Shinya Kitaoka 120a6e
        output->newLink(n - l, n - l - 1, arcCopyRev);
Shinya Kitaoka 120a6e
        output->newLink(n - l - 1, n - l, arcCopy);
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
      output->newLink(n - l, n - 1, arcCopyRev);
Shinya Kitaoka 120a6e
      output->newLink(n - 1, n - l, arcCopy);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  context.m_nodesHeap.clear();
Shinya Kitaoka 120a6e
  context.m_edgesHeap.clear();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  context.m_linearNodesHeap.clear();
Shinya Kitaoka 120a6e
  context.m_linearEdgesHeap.clear();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  return output;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
SkeletonList *skeletonize(Contours &contours, VectorizerCore *thisVectorizer,
Shinya Kitaoka 120a6e
                          VectorizerCoreGlobals &g) {
Shinya Kitaoka 120a6e
  VectorizationContext context(&g);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  SkeletonList *res = new SkeletonList;
Shinya Kitaoka 120a6e
  unsigned int i, j;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  // Find overall number of nodes
Shinya Kitaoka 120a6e
  unsigned int overallNodes = 0;
Shinya Kitaoka 120a6e
  for (i = 0; i < contours.size(); ++i)
Shinya Kitaoka 120a6e
    for (j = 0; j < contours[i].size(); ++j)
Shinya Kitaoka 120a6e
      overallNodes += contours[i][j].size();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  thisVectorizer->setOverallPartials(overallNodes);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  for (i = 0; i < contours.size(); ++i) {
Shinya Kitaoka 120a6e
    res->push_back(skeletonize(contours[i], context, thisVectorizer));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    if (thisVectorizer->isCanceled()) break;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return res;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------
Toshihiro Shimizu 890ddd
//    DEBUG
Toshihiro Shimizu 890ddd
//--------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef _SSDEBUG
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
SSDebugger::SSDebugger(VectorizationContext &context)
Shinya Kitaoka 120a6e
    : m_context(context)
Shinya Kitaoka 120a6e
    , m_scale(1.0)
Shinya Kitaoka 120a6e
    , m_loop(this)
Shinya Kitaoka 120a6e
    , m_transform(1, 0, 0, -1, 0, height()) {
Shinya Kitaoka 120a6e
  setMouseTracking(true);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline TPointD SSDebugger::updated(ContourNode *node) {
Toshihiro Shimizu 890ddd
#ifndef _PREPROCESS
Toshihiro Shimizu 890ddd
#ifdef _UPDATE
Shinya Kitaoka 120a6e
  if (node->m_direction.z > 1e-4) {
Shinya Kitaoka 120a6e
    return planeProjection(
Shinya Kitaoka 120a6e
        node->m_position +
Shinya Kitaoka 120a6e
        ((m_height - node->m_position.z) / node->m_direction.z) *
Shinya Kitaoka 120a6e
            node->m_direction);
Shinya Kitaoka 120a6e
  } else
Shinya Kitaoka 120a6e
    return planeProjection(node->m_position);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  return planeProjection(node->m_position);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#define line(a, b) p.drawLine(QLineF((a).x, (a).y, (b).x, (b).y));
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void SSDebugger::paintEvent(QPaintEvent *) {
Shinya Kitaoka 120a6e
  QPainter p(this);
Shinya Kitaoka 120a6e
  p.setTransform(m_transform);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Draw currently produced skeleton
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    const SkeletonGraph &skeleton = *m_context.m_output;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    p.setPen(Qt::blue);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    int n, nCount = skeleton.getNodesCount();
Shinya Kitaoka 120a6e
    for (n = 0; n != nCount; ++n) {
Shinya Kitaoka 120a6e
      const SkeletonGraph::Node &node = skeleton.getNode(n);
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      int l, lCount = node.getLinksCount();
Shinya Kitaoka 120a6e
      for (l = 0; l != lCount; ++l)
Shinya Kitaoka 120a6e
        line(*node, *skeleton.getNode(node.getLink(l).getNext()));
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Draw background Debug Point
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Versione updated
Shinya Kitaoka 120a6e
  IndexTable &activeTable = m_context.m_activeTable;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  unsigned int i;
Shinya Kitaoka 120a6e
  ContourNode *first, *last, *currNode;
Shinya Kitaoka 120a6e
  std::list<contournode *="">::iterator currentContour;</contournode>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  for (i = 0; i < activeTable.m_columns.size(); ++i) {
Shinya Kitaoka 120a6e
    for (currentContour = activeTable[i]->begin();
Shinya Kitaoka 120a6e
         currentContour != activeTable[i]->end(); currentContour++) {
Shinya Kitaoka 120a6e
      // Draw edge
Shinya Kitaoka 120a6e
      p.setPen(Qt::black);
Shinya Kitaoka 120a6e
      last = first = *currentContour;
Shinya Kitaoka 120a6e
      first        = first->m_next;
Shinya Kitaoka 120a6e
      // assert(!last->hasAttribute(ContourNode::ELIMINATED));
Shinya Kitaoka 120a6e
      line(updated(last), updated(first));
Shinya Kitaoka 120a6e
      for (currNode = first; !currNode->hasAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
           currNode = currNode->m_next) {
Shinya Kitaoka 120a6e
        // assert(!currNode->hasAttribute(ContourNode::ELIMINATED));
Shinya Kitaoka 120a6e
        line(updated(currNode), updated(currNode->m_next));
Shinya Kitaoka 120a6e
      }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Draw bisector
Shinya Kitaoka 120a6e
      p.setPen(Qt::red);
Shinya Kitaoka 120a6e
      last = first = *currentContour;
Shinya Kitaoka 120a6e
      first        = first->m_next;
Shinya Kitaoka 120a6e
      line(updated(last), updated(last) + planeProjection(last->m_direction));
Shinya Kitaoka 120a6e
      for (currNode = first; !currNode->hasAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
           currNode = currNode->m_next)
Shinya Kitaoka 120a6e
        line(updated(currNode),
Shinya Kitaoka 120a6e
             updated(currNode) + planeProjection(currNode->m_direction));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
      // Draw edge
Shinya Kitaoka 120a6e
      p.setPen(Qt::green);
Shinya Kitaoka 120a6e
      last = first = *currentContour;
Shinya Kitaoka 120a6e
      first        = first->m_next;
Shinya Kitaoka 120a6e
      line(updated(last), updated(last) + last->m_edge->m_direction);
Shinya Kitaoka 120a6e
      for (currNode = first; !currNode->hasAttribute(ContourNode::HEAD);
Shinya Kitaoka 120a6e
           currNode = currNode->m_next)
Shinya Kitaoka 120a6e
        line(updated(currNode),
Shinya Kitaoka 120a6e
             updated(currNode) + currNode->m_edge->m_direction);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  // Finally, draw text strings
Shinya Kitaoka 120a6e
  {
Shinya Kitaoka 120a6e
    p.setPen(Qt::red);
Shinya Kitaoka 120a6e
    p.setTransform(QTransform());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    const QPointF &worldPos = winToWorldF(m_pos.x(), m_pos.y());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    p.drawText(rect().bottomLeft(), QString("WinPos: %1 %2  WorldPos: %3 %4")
Shinya Kitaoka 120a6e
                                        .arg(m_pos.x())
Shinya Kitaoka 120a6e
                                        .arg(m_pos.y())
Shinya Kitaoka 120a6e
                                        .arg(worldPos.x())
Shinya Kitaoka 120a6e
                                        .arg(worldPos.y()));
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void SSDebugger::keyPressEvent(QKeyEvent *event) { m_loop.exit(); }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void SSDebugger::mouseMoveEvent(QMouseEvent *event) {
Shinya Kitaoka 120a6e
  m_pos = event->pos();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  if (event->buttons() == Qt::MiddleButton) {
Shinya Kitaoka 120a6e
    m_transform.translate((event->x() - m_pressPos.x()) / m_scale,
Shinya Kitaoka 120a6e
                          (m_pressPos.y() - event->y()) / m_scale);
Shinya Kitaoka 120a6e
    m_pressPos = event->pos();
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  update();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void SSDebugger::mousePressEvent(QMouseEvent *event) {
Shinya Kitaoka 120a6e
  m_pressPos = m_pos = event->pos();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void SSDebugger::mouseReleaseEvent(QMouseEvent *event) {}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
QPoint SSDebugger::worldToWin(double x, double y) {
Shinya Kitaoka 120a6e
  return m_transform.map(QPointF(x, y)).toPoint();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
QPoint SSDebugger::winToWorld(int x, int y) {
Shinya Kitaoka 120a6e
  return m_transform.inverted().map(QPoint(x, y));
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
QPointF SSDebugger::winToWorldF(int x, int y) {
Shinya Kitaoka 120a6e
  return m_transform.inverted().map(QPointF(x, y));
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
void SSDebugger::wheelEvent(QWheelEvent *event) {
Shinya Kitaoka 120a6e
  QPoint w_coords;
Shinya Kitaoka 120a6e
  double zoom_par = 1 + event->delta() * 0.001;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_scale *= zoom_par;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  w_coords = winToWorld(event->x(), event->y());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  m_transform.translate(w_coords.x(), w_coords.y());
Shinya Kitaoka 120a6e
  m_transform.scale(zoom_par, zoom_par);
Shinya Kitaoka 120a6e
  m_transform.translate(-w_coords.x(), -w_coords.y());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  update();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
inline bool SSDebugger::isOnScreen(ContourNode *node) {
Shinya Kitaoka 120a6e
  const TPointD &pos = updated(node);
Shinya Kitaoka 120a6e
  return rect().contains(worldToWin(pos.x, pos.y));
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif