|
Ankit Kumar Dwivedi |
b59311 |
/* === S Y N F I G ========================================================= */
|
|
Ankit Kumar Dwivedi |
b59311 |
/*! \file centerlineskeletonizer.cpp
|
|
Ankit Kumar Dwivedi |
b59311 |
**
|
|
Ankit Kumar Dwivedi |
b59311 |
** $Id$
|
|
Ankit Kumar Dwivedi |
b59311 |
**
|
|
Ankit Kumar Dwivedi |
b59311 |
** \legal
|
|
Ankit Kumar Dwivedi |
b59311 |
** Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
|
|
Ankit Kumar Dwivedi |
b59311 |
**
|
|
Ankit Kumar Dwivedi |
b59311 |
** This package is free software; you can redistribute it and/or
|
|
Ankit Kumar Dwivedi |
b59311 |
** modify it under the terms of the GNU General Public License as
|
|
Ankit Kumar Dwivedi |
b59311 |
** published by the Free Software Foundation; either version 2 of
|
|
Ankit Kumar Dwivedi |
b59311 |
** the License, or (at your option) any later version.
|
|
Ankit Kumar Dwivedi |
b59311 |
**
|
|
Ankit Kumar Dwivedi |
b59311 |
** This package is distributed in the hope that it will be useful,
|
|
Ankit Kumar Dwivedi |
b59311 |
** but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Ankit Kumar Dwivedi |
b59311 |
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Ankit Kumar Dwivedi |
b59311 |
** General Public License for more details.
|
|
Ankit Kumar Dwivedi |
b59311 |
** \endlegal
|
|
Ankit Kumar Dwivedi |
b59311 |
*/
|
|
Ankit Kumar Dwivedi |
b59311 |
/* ========================================================================= */
|
|
Ankit Kumar Dwivedi |
b59311 |
|
|
Ankit Kumar Dwivedi |
b59311 |
/* === H E A D E R S ======================================================= */
|
|
Ankit Kumar Dwivedi |
703f0f |
|
|
Ankit Kumar Dwivedi |
4114f2 |
#include "polygonizerclasses.h"
|
|
Ankit Kumar Dwivedi |
4114f2 |
#include <queue></queue>
|
|
Ankit Kumar Dwivedi |
4114f2 |
#include <synfig vector.h=""></synfig>
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
c67741 |
/* === U S I N G =========================================================== */
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
c67741 |
using namespace std;
|
|
Ankit Kumar Dwivedi |
c67741 |
using namespace etl;
|
|
Ankit Kumar Dwivedi |
c67741 |
using namespace studio;
|
|
Ankit Kumar Dwivedi |
4114f2 |
using namespace synfig;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//<---------------------------Some Useful functions----------------------------->
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline double cross(const synfig::Point &a, const synfig::Point &b)
|
|
Ankit Kumar Dwivedi |
4114f2 |
{
|
|
Ankit Kumar Dwivedi |
4114f2 |
return a[0] * b[1] - a[1] * b[0];
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline synfig::Point3 cross(const synfig::Point3 &a, const synfig::Point3 &b) {
|
|
Ankit Kumar Dwivedi |
4114f2 |
return synfig::Point3(a[1] * b[2] - b[1] * a[2], a[2] * b[0] - b[2] * a[0],
|
|
Ankit Kumar Dwivedi |
4114f2 |
a[0] * b[1] - b[0] * a[1]);
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline bool angleLess(const synfig::Point &a, const synfig::Point &b) {
|
|
Ankit Kumar Dwivedi |
4114f2 |
return a[1] >= 0 ? b[1] >= 0 ? a[0] > b[0] : 1 : b[1] < 0 ? a[0] < b[0] : 0;
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// a, b, ref assumed normalized
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline bool angleLess(const synfig::Point &a, const synfig::Point &b, const synfig::Point &ref) {
|
|
Ankit Kumar Dwivedi |
4114f2 |
return angleLess(a, ref) ? angleLess(b, ref) ? angleLess(a, b) : 0
|
|
Ankit Kumar Dwivedi |
4114f2 |
: angleLess(b, ref) ? 1 : angleLess(a, b);
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//**************************************************************
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Classes
|
|
Ankit Kumar Dwivedi |
4114f2 |
//**************************************************************
|
|
Ankit Kumar Dwivedi |
4114f2 |
struct VectorizationContext;
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
class studio::ContourEdge
|
|
Ankit Kumar Dwivedi |
4114f2 |
{
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
enum { NOT_OPPOSITE = 0x1 };
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point m_direction;
|
|
Ankit Kumar Dwivedi |
4114f2 |
unsigned short m_attributes;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourEdge() : m_attributes(0) {}
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourEdge(synfig::Point dir) : m_direction(dir), m_attributes(0) {}
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
int hasAttribute(int attr) const { return m_attributes & attr; }
|
|
Ankit Kumar Dwivedi |
4114f2 |
void setAttribute(int attr) { m_attributes |= attr; }
|
|
Ankit Kumar Dwivedi |
4114f2 |
void clearAttribute(int attr) { m_attributes &= ~attr; }
|
|
Ankit Kumar Dwivedi |
4114f2 |
};
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
class IndexTable {
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
typedef std::list<contournode *=""> IndexColumn;</contournode>
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
std::vector<indexcolumn></indexcolumn>
|
|
luz.paz |
7040b8 |
m_columns; //!< Contours set by 'column identifier'.
|
|
Ankit Kumar Dwivedi |
4114f2 |
std::vector<int></int>
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_identifiers; //!< Column identifiers by original contour index.
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// NOTE: Contours are stored in 'comb' structure (vector of lists) since
|
|
Ankit Kumar Dwivedi |
4114f2 |
// contours may both
|
|
Ankit Kumar Dwivedi |
4114f2 |
// be SPLIT (new entry in a list) and MERGED (two lists merge).
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
IndexTable() {}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
IndexColumn *operator[](int i) { return &m_columns[i]; }
|
|
Ankit Kumar Dwivedi |
4114f2 |
IndexColumn &columnOfId(int id) { return m_columns[m_identifiers[id]]; }
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Initialization
|
|
Ankit Kumar Dwivedi |
4114f2 |
void build(ContourFamily &family);
|
|
Ankit Kumar Dwivedi |
4114f2 |
void clear();
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Specific handlers
|
|
Ankit Kumar Dwivedi |
4114f2 |
IndexColumn::iterator find(ContourNode *index);
|
|
Ankit Kumar Dwivedi |
4114f2 |
void merge(IndexColumn::iterator index1, IndexColumn::iterator index2);
|
|
Ankit Kumar Dwivedi |
4114f2 |
void remove(IndexColumn::iterator index);
|
|
Ankit Kumar Dwivedi |
4114f2 |
};
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
class Event {
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
/*! \remark Values are sorted by preference at simultaneous events. */
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
enum Type //! An event's possible types.
|
|
Ankit Kumar Dwivedi |
4114f2 |
{ special, //!< A vertex event that is also an edge event (V case).
|
|
Ankit Kumar Dwivedi |
4114f2 |
edge, //!< An edge shrinks to 0 length.
|
|
Ankit Kumar Dwivedi |
4114f2 |
vertex, //!< Two contour nodes clash.
|
|
Ankit Kumar Dwivedi |
4114f2 |
split_regenerate, //!< Placeholder type for split events that must be
|
|
Ankit Kumar Dwivedi |
4114f2 |
//! regenerated.
|
|
Ankit Kumar Dwivedi |
4114f2 |
split, //!< An edge is split by a clashing contour node.
|
|
Ankit Kumar Dwivedi |
4114f2 |
failure };
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
double m_height;
|
|
Ankit Kumar Dwivedi |
4114f2 |
double m_displacement;
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourNode *m_generator;
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourNode *m_coGenerator;
|
|
Ankit Kumar Dwivedi |
4114f2 |
Type m_type;
|
|
luzpaz |
7cbe4e |
unsigned int m_algorithmicTime;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
VectorizationContext *m_context;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
// In-builder event constructor
|
|
Ankit Kumar Dwivedi |
4114f2 |
Event(ContourNode *generator, VectorizationContext *context);
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Event calculators
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void calculateEdgeEvent();
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void calculateSplitEvent();
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Auxiliary event calculators
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline double splitDisplacementWith(ContourNode *plane);
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline bool tryRayEdgeCollisionWith(ContourNode *edge);
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Event handlers
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline bool process();
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void processEdgeEvent();
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void processMaxEvent();
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void processSplitEvent();
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void processVertexEvent();
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void processSpecialEvent();
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
private:
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline bool testRayEdgeCollision(studio::ContourNode *opposite, double &displacement,
|
|
Ankit Kumar Dwivedi |
4114f2 |
double &height, double &side1,
|
|
Ankit Kumar Dwivedi |
4114f2 |
double &side2);
|
|
Ankit Kumar Dwivedi |
4114f2 |
};
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
struct EventGreater {
|
|
Ankit Kumar Dwivedi |
4114f2 |
bool operator()(const Event &event1, const Event &event2) const {
|
|
Ankit Kumar Dwivedi |
4114f2 |
return event1.m_height > event2.m_height ||
|
|
Ankit Kumar Dwivedi |
4114f2 |
(event1.m_height == event2.m_height &&
|
|
Ankit Kumar Dwivedi |
4114f2 |
event1.m_type > event2.m_type);
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
};
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
class Timeline final
|
|
Ankit Kumar Dwivedi |
4114f2 |
: public std::priority_queue<event, std::vector<event="">, EventGreater> {</event,>
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
Timeline() {}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// NOTE: Timeline construction contains the most complex part of
|
|
Ankit Kumar Dwivedi |
4114f2 |
// vectorization;
|
|
ankit-kumar-dwivedi |
81bea2 |
void build(ContourFamily &polygons, VectorizationContext &context);
|
|
Ankit Kumar Dwivedi |
4114f2 |
};
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//==========================================================================
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//--------------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Preliminary methods/functions
|
|
Ankit Kumar Dwivedi |
4114f2 |
//--------------------------------------
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// IndexTable methods
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
701ccf |
void IndexTable::build(ContourFamily &family) {
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int i;
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_columns.resize(family.size());
|
|
Ankit Kumar Dwivedi |
701ccf |
m_identifiers.resize(family.size());
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: At the beginning, m_identifiers= 1, .. , m_columns.size() - 1;
|
|
Ankit Kumar Dwivedi |
701ccf |
for (i = 0; i < m_columns.size(); ++i) {
|
|
Ankit Kumar Dwivedi |
701ccf |
m_identifiers[i] = i;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_columns[i].push_back(&family[i][0]);
|
|
Ankit Kumar Dwivedi |
701ccf |
// Each node referenced in the Table is signed as 'head' of the cirular
|
|
Ankit Kumar Dwivedi |
701ccf |
// list.
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][0].setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Explanation: during the skeletonization process, ContourNodes and calculated
|
|
Ankit Kumar Dwivedi |
701ccf |
// Events are unaware of global index-changes generated by other events, so
|
|
Ankit Kumar Dwivedi |
701ccf |
// the position of index stored in one Event has to be retrieved in the
|
|
Ankit Kumar Dwivedi |
701ccf |
// IndexTable before event processing begins.
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: Can this be done in a more efficient way?...
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline IndexTable::IndexColumn::iterator IndexTable::find(ContourNode *sought) {
|
|
Ankit Kumar Dwivedi |
701ccf |
int indexId = m_identifiers[sought->m_ancestorContour];
|
|
Ankit Kumar Dwivedi |
701ccf |
IndexColumn::iterator res;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Search for the HEAD attribute in index's Contour
|
|
Ankit Kumar Dwivedi |
701ccf |
for (; !sought->hasAttribute(ContourNode::HEAD); sought = sought->m_next)
|
|
Ankit Kumar Dwivedi |
701ccf |
;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Finally, find index through our column
|
|
Ankit Kumar Dwivedi |
701ccf |
for (res = m_columns[indexId].begin(); (*res) != sought; ++res)
|
|
Ankit Kumar Dwivedi |
701ccf |
;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
return res;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Handles active contour merging due to split/vertex events
|
|
Ankit Kumar Dwivedi |
701ccf |
void IndexTable::merge(IndexColumn::iterator index1,
|
|
Ankit Kumar Dwivedi |
701ccf |
IndexColumn::iterator index2) {
|
|
Ankit Kumar Dwivedi |
701ccf |
IndexColumn::iterator current;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
int identifier1 = m_identifiers[(*index1)->m_ancestorContour],
|
|
Ankit Kumar Dwivedi |
701ccf |
identifier2 = m_identifiers[(*index2)->m_ancestorContour];
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
remove(index2); // We maintain only one index of the merged contour
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now, append columns
|
|
Ankit Kumar Dwivedi |
701ccf |
if (!m_columns[identifier2].empty()) {
|
|
Ankit Kumar Dwivedi |
701ccf |
append<indextable::indexcolumn, indextable::indexcolumn::reverse_iterator="">(</indextable::indexcolumn,>
|
|
Ankit Kumar Dwivedi |
701ccf |
m_columns[identifier1], m_columns[identifier2]);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_columns[identifier2].clear();
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Then, update stored identifiers
|
|
Ankit Kumar Dwivedi |
701ccf |
for (unsigned int k = 0; k < m_columns.size(); ++k) {
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_identifiers[k] == identifier2) m_identifiers[k] = identifier1;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Removes given index in Table
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void IndexTable::remove(IndexColumn::iterator index) {
|
|
Ankit Kumar Dwivedi |
701ccf |
m_columns[m_identifiers[(*index)->m_ancestorContour]].erase(index);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void IndexTable::clear() { m_columns.clear(), m_identifiers.clear(); }
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//==========================================================================
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Straight Skeleton Algorithm
|
|
Ankit Kumar Dwivedi |
4114f2 |
//==========================================================================
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Global Variables
|
|
Ankit Kumar Dwivedi |
4114f2 |
//------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
struct VectorizationContext {
|
|
Ankit Kumar Dwivedi |
4114f2 |
VectorizerCoreGlobals *m_globals;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Globals
|
|
Ankit Kumar Dwivedi |
4114f2 |
unsigned int m_totalNodes; // Number of original contour nodes
|
|
Ankit Kumar Dwivedi |
4114f2 |
unsigned int m_contoursCount; // Number of contours in input region
|
|
Ankit Kumar Dwivedi |
4114f2 |
IndexTable m_activeTable; // Index table of active contours
|
|
Ankit Kumar Dwivedi |
4114f2 |
SkeletonGraph *m_output; // Output skeleton of input region
|
|
Ankit Kumar Dwivedi |
4114f2 |
double m_currentHeight; // Height of our 'roof-flooding' process
|
|
Ankit Kumar Dwivedi |
4114f2 |
Timeline m_timeline; // Ordered queue of all possible events
|
|
luzpaz |
7cbe4e |
unsigned int m_algorithmicTime; // Number of events processed up to now
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Containers
|
|
Ankit Kumar Dwivedi |
4114f2 |
std::vector<contouredge> m_edgesHeap;</contouredge>
|
|
Ankit Kumar Dwivedi |
4114f2 |
std::vector<contournode> m_nodesHeap; // of *non-original* nodes only</contournode>
|
|
Ankit Kumar Dwivedi |
4114f2 |
unsigned int m_nodesHeapCount; // number of nodes used in nodesHeap
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//'Linear Axis-added' *pseudo-original* nodes and edges
|
|
Ankit Kumar Dwivedi |
4114f2 |
std::vector<contournode> m_linearNodesHeap;</contournode>
|
|
Ankit Kumar Dwivedi |
4114f2 |
std::vector<contouredge> m_linearEdgesHeap;</contouredge>
|
|
Ankit Kumar Dwivedi |
4114f2 |
unsigned int m_linearNodesHeapCount;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
public:
|
|
Ankit Kumar Dwivedi |
4114f2 |
VectorizationContext(VectorizerCoreGlobals *globals) : m_globals(globals) {}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourNode *getNode() { return &m_nodesHeap[m_nodesHeapCount++]; }
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourNode *getLinearNode() {
|
|
Ankit Kumar Dwivedi |
4114f2 |
return &m_linearNodesHeap[m_linearNodesHeapCount];
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
studio::ContourEdge *getLinearEdge() {
|
|
Ankit Kumar Dwivedi |
4114f2 |
return &m_linearEdgesHeap[m_linearNodesHeapCount++];
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void addLinearNodeBefore(ContourNode *node);
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void repairDegenerations(
|
|
Ankit Kumar Dwivedi |
4114f2 |
const std::vector<contournode *=""> °enerates);</contournode>
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void prepareGlobals();
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void prepareContours(ContourFamily &family);
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void newSkeletonLink(unsigned int cur, ContourNode *node);
|
|
Ankit Kumar Dwivedi |
4114f2 |
};
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// WARNING: To be launched only *after* prepareContours - node countings happen
|
|
Ankit Kumar Dwivedi |
4114f2 |
// there
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void VectorizationContext::prepareGlobals() {
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: Let n be the total number of nodes in the family, k the number of
|
|
Ankit Kumar Dwivedi |
701ccf |
// split events
|
|
Ankit Kumar Dwivedi |
701ccf |
// effectively happening in the process, m the number of original
|
|
Ankit Kumar Dwivedi |
701ccf |
// contours of the family.
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now:
|
|
Ankit Kumar Dwivedi |
701ccf |
// * Each split event eliminates its generating reflex node and
|
|
Ankit Kumar Dwivedi |
701ccf |
// introduces
|
|
Ankit Kumar Dwivedi |
701ccf |
// two convex nodes
|
|
Ankit Kumar Dwivedi |
701ccf |
// * Each edge event eliminates its couple of generating nodes and
|
|
Ankit Kumar Dwivedi |
701ccf |
// introduces one new convex node
|
|
Ankit Kumar Dwivedi |
701ccf |
// * Each max event eliminates 3 generating nodes without introducing
|
|
Ankit Kumar Dwivedi |
701ccf |
// new ones
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// So, split events introduce 2k non-original nodes, and (k-m+2) is the number
|
|
Ankit Kumar Dwivedi |
701ccf |
// of max events
|
|
Ankit Kumar Dwivedi |
701ccf |
// necessarily happening, since (m-1) are the *merging* split events.
|
|
Ankit Kumar Dwivedi |
701ccf |
// On the n+k-3(k-m+2) nodes remaining for pure edge events, as many
|
|
Ankit Kumar Dwivedi |
701ccf |
// non-original nodes are inserted.
|
|
Ankit Kumar Dwivedi |
701ccf |
//=> This yields 2k + n-2k+3m-6= n+3m-6 non-original nodes. Contemporaneous
|
|
Ankit Kumar Dwivedi |
701ccf |
// events such as
|
|
Ankit Kumar Dwivedi |
701ccf |
// vertex and special events can only decrease the number of non-original
|
|
Ankit Kumar Dwivedi |
701ccf |
// nodes requested.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Initialize non-original nodes container
|
|
Ankit Kumar Dwivedi |
701ccf |
m_nodesHeap.resize(m_totalNodes + 3 * m_contoursCount - 6);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_nodesHeapCount = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Reset time/height variables
|
|
Ankit Kumar Dwivedi |
701ccf |
m_currentHeight = 0;
|
|
luzpaz |
7cbe4e |
m_algorithmicTime = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Clean IndexTable
|
|
Ankit Kumar Dwivedi |
701ccf |
m_activeTable.clear();
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
inline void VectorizationContext::newSkeletonLink(unsigned int cur, ContourNode *node)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (node->hasAttribute(ContourNode::SK_NODE_DROPPED)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
SkeletonArc arcCopy(node);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_output->newLink(node->m_outputNode, cur, arcCopy);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
arcCopy.turn();
|
|
Ankit Kumar Dwivedi |
701ccf |
m_output->newLink(cur, node->m_outputNode, arcCopy);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//==========================================================================
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//===================================
|
|
Ankit Kumar Dwivedi |
701ccf |
// Thinning Functions/Methods
|
|
Ankit Kumar Dwivedi |
701ccf |
//===================================
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//----------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
// Repair Polygon Degenerations
|
|
Ankit Kumar Dwivedi |
701ccf |
//----------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// EXPLANATION: After "Polygonizer", there may be simpleness degenerations
|
|
Ankit Kumar Dwivedi |
701ccf |
// about polygons which are dangerous to deal in the thinning process.
|
|
Ankit Kumar Dwivedi |
16a65e |
// Typically, these correspond to cases in which node->m_direction[2] ~ 0
|
|
Ankit Kumar Dwivedi |
701ccf |
//(too fast), and are concave.
|
|
Ankit Kumar Dwivedi |
701ccf |
// We then deal with them *before* the process begins, by splitting one
|
|
Ankit Kumar Dwivedi |
701ccf |
// such node in two slower ones (known as 'Linear Axis' method).
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
inline void VectorizationContext::addLinearNodeBefore(ContourNode *node)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *newNode = getLinearNode();
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourEdge *newEdge = getLinearEdge();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_position = node->m_position;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Build new edge
|
|
Ankit Kumar Dwivedi |
16a65e |
if (node->m_direction[2] < 0.1)
|
|
Ankit Kumar Dwivedi |
16a65e |
newEdge->m_direction = (node->m_edge->m_direction).perp();
|
|
Ankit Kumar Dwivedi |
701ccf |
else
|
|
Ankit Kumar Dwivedi |
16a65e |
newEdge->m_direction = (node->m_edge->m_direction + node->m_prev->m_edge->m_direction).norm();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_edge = newEdge;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Link newNode
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_prev = node->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_next = node;
|
|
Ankit Kumar Dwivedi |
701ccf |
node->m_prev->m_next = newNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
node->m_prev = newNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Build remaining infos
|
|
Ankit Kumar Dwivedi |
701ccf |
node->buildNodeInfos(); // Rebuild
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->buildNodeInfos();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_updateTime = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_ancestor = node->m_ancestor;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_ancestorContour = node->m_ancestorContour;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Set node and newNode's edges not to be recognized as possible
|
|
Ankit Kumar Dwivedi |
701ccf |
// opposites by the other (could happen in *future* instants)
|
|
Ankit Kumar Dwivedi |
701ccf |
// *DO NOT REMOVE!*
|
|
Ankit Kumar Dwivedi |
701ccf |
node->m_notOpposites.push_back(newNode->m_edge);
|
|
Ankit Kumar Dwivedi |
701ccf |
node->m_notOpposites.push_back(newNode->m_prev->m_edge);
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_notOpposites.push_back(node->m_edge);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Further sign newly added node
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->setAttribute(ContourNode::LINEAR_ADDED);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void VectorizationContext::repairDegenerations(
|
|
Ankit Kumar Dwivedi |
701ccf |
const std::vector<contournode *=""> °enerates) {</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int i;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_linearNodesHeap.resize(degenerates.size());
|
|
Ankit Kumar Dwivedi |
701ccf |
m_linearEdgesHeap.resize(degenerates.size());
|
|
Ankit Kumar Dwivedi |
701ccf |
m_linearNodesHeapCount = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
for (i = 0; i < degenerates.size(); ++i) {
|
|
Ankit Kumar Dwivedi |
701ccf |
if (!degenerates[i]->hasAttribute(ContourNode::AMBIGUOUS_LEFT)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
addLinearNodeBefore(degenerates[i]);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_totalNodes++;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
// Node Infos Construction
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void VectorizationContext::prepareContours(ContourFamily &family) {
|
|
Ankit Kumar Dwivedi |
701ccf |
std::vector<contournode *=""> degenerateNodes;</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Build circular links
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int i, j, k;
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int current;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_contoursCount = family.size();
|
|
Ankit Kumar Dwivedi |
701ccf |
m_totalNodes = 0;
|
|
Ankit Kumar Dwivedi |
703f0f |
for (i = 0; i < family.size(); ++i)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
703f0f |
for (j = 0, k = family[i].size() - 1; j < family[i].size(); k = j, ++j)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][k].m_next = &family[i][j];
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][j].m_prev = &family[i][k];
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
m_totalNodes += family[i].size();
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Build node edges
|
|
Ankit Kumar Dwivedi |
701ccf |
m_edgesHeap.resize(m_totalNodes);
|
|
Ankit Kumar Dwivedi |
701ccf |
current = 0;
|
|
Ankit Kumar Dwivedi |
703f0f |
for (i = 0; i < family.size(); ++i)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
703f0f |
for (j = 0, k = family[i].size() - 1; j < family[i].size(); k = j, ++j)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
703f0f |
m_edgesHeap[current].m_direction = ((family[i][j].m_position - family[i][k].m_position).to_2d()).norm();
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][k].m_edge = &m_edgesHeap[current];
|
|
Ankit Kumar Dwivedi |
701ccf |
current++;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
bool maxThicknessNotZero = m_globals->currConfig->m_maxThickness > 0.0;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now build remaining infos
|
|
Ankit Kumar Dwivedi |
703f0f |
for (i = 0; i < family.size(); ++i)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
703f0f |
for (j = 0; j < family[i].size(); ++j)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][j].buildNodeInfos();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][j].m_updateTime = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][j].m_ancestor = j;
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][j].m_ancestorContour = i;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Check the following degeneration
|
|
Ankit Kumar Dwivedi |
703f0f |
if (family[i][j].m_concave && family[i][j].m_direction[2] < 0.3)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
// Push this node among degenerate ones
|
|
Ankit Kumar Dwivedi |
701ccf |
degenerateNodes.push_back(&family[i][j]);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Insert output node in sharp angles
|
|
Ankit Kumar Dwivedi |
703f0f |
if (!family[i][j].m_concave && family[i][j].m_direction[2] < 0.6 && maxThicknessNotZero)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][j].setAttribute(ContourNode::SK_NODE_DROPPED);
|
|
Ankit Kumar Dwivedi |
701ccf |
family[i][j].m_outputNode = m_output->newNode(family[i][j].m_position);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Push on nodes having AMBIGUOUS_RIGHT attribute
|
|
Ankit Kumar Dwivedi |
701ccf |
if (family[i][j].hasAttribute(ContourNode::AMBIGUOUS_RIGHT))
|
|
Ankit Kumar Dwivedi |
295555 |
family[i][j].m_position += (family[i][j].m_direction) * 0.02;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Finally, ensure polygon degenerations found are solved
|
|
Ankit Kumar Dwivedi |
701ccf |
if (maxThicknessNotZero) repairDegenerations(degenerateNodes);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// WARNING: m_edge field of *this* and *previous* node must already be defined.
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void ContourNode::buildNodeInfos(bool forceConvex) {
|
|
Ankit Kumar Dwivedi |
16a65e |
synfig::Point direction;
|
|
Ankit Kumar Dwivedi |
701ccf |
double parameter;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Calculate node convexity
|
|
Ankit Kumar Dwivedi |
701ccf |
if (forceConvex)
|
|
Ankit Kumar Dwivedi |
701ccf |
m_concave = 0;
|
|
Ankit Kumar Dwivedi |
703f0f |
else if (cross(m_edge->m_direction, m_prev->m_edge->m_direction) < 0)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
m_concave = 1;
|
|
Ankit Kumar Dwivedi |
703f0f |
}
|
|
Ankit Kumar Dwivedi |
703f0f |
else
|
|
Ankit Kumar Dwivedi |
701ccf |
m_concave = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Build node direction
|
|
Ankit Kumar Dwivedi |
701ccf |
direction = m_edge->m_direction - m_prev->m_edge->m_direction;
|
|
Ankit Kumar Dwivedi |
703f0f |
parameter = direction.mag();
|
|
Ankit Kumar Dwivedi |
16a65e |
if (parameter > 0.01)
|
|
Ankit Kumar Dwivedi |
16a65e |
{
|
|
Ankit Kumar Dwivedi |
4114f2 |
direction = direction * (1 / parameter);
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (m_concave) direction = -direction;
|
|
Ankit Kumar Dwivedi |
4114f2 |
}
|
|
Ankit Kumar Dwivedi |
16a65e |
else
|
|
Ankit Kumar Dwivedi |
703f0f |
direction = (m_edge->m_direction).perp();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
16a65e |
m_direction[0] = direction[0];
|
|
Ankit Kumar Dwivedi |
16a65e |
m_direction[1] = direction[1];
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Calculate node speed
|
|
Ankit Kumar Dwivedi |
703f0f |
m_direction[2] = cross(m_direction.to_2d(), m_edge->m_direction);
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (m_direction[2] < 0) m_direction[2] = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Calculate angular momentum
|
|
Ankit Kumar Dwivedi |
701ccf |
m_AngularMomentum = cross(m_position, m_direction);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
16a65e |
if (m_concave)
|
|
Ankit Kumar Dwivedi |
16a65e |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
m_AuxiliaryMomentum1 = m_AuxiliaryMomentum2 = m_AngularMomentum;
|
|
Ankit Kumar Dwivedi |
16a65e |
}
|
|
Ankit Kumar Dwivedi |
16a65e |
else
|
|
Ankit Kumar Dwivedi |
16a65e |
{
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_AuxiliaryMomentum1 =
|
|
Ankit Kumar Dwivedi |
4114f2 |
cross(m_position,
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point3(m_edge->m_direction[1], -(m_edge->m_direction[0]), 1));
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_AuxiliaryMomentum2 =
|
|
Ankit Kumar Dwivedi |
4114f2 |
cross(m_position, synfig::Point3(m_prev->m_edge->m_direction[1],
|
|
Ankit Kumar Dwivedi |
df3317 |
-(m_prev->m_edge->m_direction[0]), 1));
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//---------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
// Timeline Construction
|
|
Ankit Kumar Dwivedi |
701ccf |
//---------------------------------
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: In the following, we achieve these results:
|
|
Ankit Kumar Dwivedi |
701ccf |
// * Build the timeline - events priority queue
|
|
Ankit Kumar Dwivedi |
701ccf |
// * Process those split events which *necessarily* happen
|
|
Ankit Kumar Dwivedi |
701ccf |
// Pre-processing of split events is useful in order to lower execution times.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Each node is first associated to a random integer; then a referencing
|
|
Ankit Kumar Dwivedi |
701ccf |
// vector is ordered according to those integers - events are calculated
|
|
Ankit Kumar Dwivedi |
701ccf |
// following this order. Split events are therefore calculated sparsely
|
|
Ankit Kumar Dwivedi |
701ccf |
// along the polygons, allowing a significant time reduction effect.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
class RandomizedNode {
|
|
Ankit Kumar Dwivedi |
c67741 |
public:
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *m_node;
|
|
Ankit Kumar Dwivedi |
701ccf |
int m_number;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
RandomizedNode() {}
|
|
Ankit Kumar Dwivedi |
701ccf |
RandomizedNode(ContourNode *node) : m_node(node), m_number(rand()) {}
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline ContourNode *operator->(void) { return m_node; }
|
|
Ankit Kumar Dwivedi |
701ccf |
};
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
class RandomizedNodeLess {
|
|
Ankit Kumar Dwivedi |
c67741 |
public:
|
|
Ankit Kumar Dwivedi |
701ccf |
RandomizedNodeLess() {}
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline bool operator()(RandomizedNode a, RandomizedNode b) {
|
|
Ankit Kumar Dwivedi |
701ccf |
return (a.m_number < b.m_number);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
c67741 |
};
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
c67741 |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
ankit-kumar-dwivedi |
81bea2 |
void Timeline::build(ContourFamily &polygons, VectorizationContext &context) {
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int i, j, current;
|
|
Ankit Kumar Dwivedi |
701ccf |
std::vector<randomizednode> nodesToBeTreated(context.m_totalNodes);</randomizednode>
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point3 momentum, ray;
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Build casual ordered node-array
|
|
Ankit Kumar Dwivedi |
701ccf |
for (i = 0, current = 0; i < polygons.size(); ++i)
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (j = 0; j < polygons[i].size(); ++j)
|
|
Ankit Kumar Dwivedi |
701ccf |
nodesToBeTreated[current++] = RandomizedNode(&polygons[i][j]);
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Same for linear-added nodes
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (i = 0; i < context.m_linearNodesHeapCount; ++i)
|
|
Ankit Kumar Dwivedi |
701ccf |
nodesToBeTreated[current++] = RandomizedNode(&context.m_linearNodesHeap[i]);
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
double maxThickness = context.m_globals->currConfig->m_maxThickness;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Compute events generated by nodes
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: are edge events to be computed BEFORE split ones?
|
|
Ankit Kumar Dwivedi |
16a65e |
for (i = 0; i < nodesToBeTreated.size(); ++i)
|
|
Ankit Kumar Dwivedi |
16a65e |
{
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
Event currentEvent(nodesToBeTreated[i].m_node, &context);
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Notify event calculation
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (currentEvent.m_type != Event::failure &&
|
|
Ankit Kumar Dwivedi |
701ccf |
currentEvent.m_height < maxThickness)
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
push(currentEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
c67741 |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
//------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
// Event Calculation
|
|
Ankit Kumar Dwivedi |
701ccf |
//------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Calculates event generated by input node
|
|
Ankit Kumar Dwivedi |
701ccf |
Event::Event(ContourNode *generator, VectorizationContext *context)
|
|
Ankit Kumar Dwivedi |
701ccf |
: m_height(infinity)
|
|
Ankit Kumar Dwivedi |
701ccf |
, m_displacement(infinity)
|
|
Ankit Kumar Dwivedi |
701ccf |
, m_generator(generator)
|
|
Ankit Kumar Dwivedi |
701ccf |
, m_type(failure)
|
|
luzpaz |
7cbe4e |
, m_algorithmicTime(context->m_algorithmicTime)
|
|
Ankit Kumar Dwivedi |
701ccf |
, m_context(context) {
|
|
Ankit Kumar Dwivedi |
701ccf |
if (generator->m_concave)
|
|
Ankit Kumar Dwivedi |
701ccf |
calculateSplitEvent();
|
|
Ankit Kumar Dwivedi |
701ccf |
else
|
|
Ankit Kumar Dwivedi |
701ccf |
calculateEdgeEvent();
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// The edge event *generated by a node* is defined as the earliest edge event
|
|
Ankit Kumar Dwivedi |
701ccf |
// generated by its adjacent edges. Remember that 'edge events' correspond to
|
|
Ankit Kumar Dwivedi |
701ccf |
// those in which one edge gets 0 length.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void Event::calculateEdgeEvent() {
|
|
Ankit Kumar Dwivedi |
701ccf |
struct locals {
|
|
Ankit Kumar Dwivedi |
4114f2 |
static inline void buildDisplacements(ContourNode *edgeFirst, double &d1,
|
|
Ankit Kumar Dwivedi |
4114f2 |
double &d2) {
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *edgeSecond = edgeFirst->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// If bisectors are almost opposite, avoid: there must be another bisector
|
|
Ankit Kumar Dwivedi |
701ccf |
// colliding with m_generator *before* coGenerator - allowing a positive
|
|
Ankit Kumar Dwivedi |
701ccf |
// result here may interfere with it.
|
|
Ankit Kumar Dwivedi |
701ccf |
if ((edgeFirst->m_concave && edgeSecond->m_concave) ||
|
|
Ankit Kumar Dwivedi |
4114f2 |
edgeFirst->m_direction * edgeSecond->m_direction < -0.9) {
|
|
Ankit Kumar Dwivedi |
701ccf |
d1 = d2 = -1.0;
|
|
Ankit Kumar Dwivedi |
701ccf |
return;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
df3317 |
double det = edgeFirst->m_direction[1] * edgeSecond->m_direction[0] -
|
|
Ankit Kumar Dwivedi |
df3317 |
edgeFirst->m_direction[0] * edgeSecond->m_direction[1];
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
16a65e |
double cx = edgeSecond->m_position[0] - edgeFirst->m_position[0],
|
|
Ankit Kumar Dwivedi |
df3317 |
cy = edgeSecond->m_position[1] - edgeFirst->m_position[1];
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
df3317 |
d1 = (edgeSecond->m_direction[0] * cy - edgeSecond->m_direction[1] * cx) /
|
|
Ankit Kumar Dwivedi |
df3317 |
det;
|
|
Ankit Kumar Dwivedi |
df3317 |
d2 =
|
|
Ankit Kumar Dwivedi |
df3317 |
(edgeFirst->m_direction[0] * cy - edgeFirst->m_direction[1] * cx) / det;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
static inline double height(ContourNode *node, double displacement) {
|
|
Ankit Kumar Dwivedi |
16a65e |
return node->m_position[2] + displacement * node->m_direction[2];
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}; // locals
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
double minHeight, minDisplacement;
|
|
Ankit Kumar Dwivedi |
701ccf |
bool positiveEdgeDispl;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_type = edge;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Calculate the two possible displacement parameters
|
|
Ankit Kumar Dwivedi |
16a65e |
double firstDisplacement, prevDisplacement, nextDisplacement, lastDisplacement;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// right == prev
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
locals::buildDisplacements(m_generator, nextDisplacement, lastDisplacement);
|
|
Ankit Kumar Dwivedi |
703f0f |
locals::buildDisplacements(m_generator->m_prev, firstDisplacement, prevDisplacement);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Take the smallest positive between them and assign the co-generator
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: In a missed vertex event, the threshold value is to compare with the
|
|
Ankit Kumar Dwivedi |
701ccf |
// possible pushes at the end of processSplit
|
|
Ankit Kumar Dwivedi |
701ccf |
// However, admitting slightly negative displacements should be ok: due to the
|
|
Ankit Kumar Dwivedi |
701ccf |
// weak linear axis imposed for concave
|
|
Ankit Kumar Dwivedi |
701ccf |
// vertices, it is impossible to have little negative displacements apart from
|
|
Ankit Kumar Dwivedi |
701ccf |
// the above mentioned pushed case.
|
|
Ankit Kumar Dwivedi |
701ccf |
// ..currently almost true..
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
static const double minusTol = -0.03;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
bool prevDispPositive = (prevDisplacement > minusTol);
|
|
Ankit Kumar Dwivedi |
701ccf |
bool nextDispPositive = (nextDisplacement > minusTol);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
if (nextDispPositive)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
703f0f |
if (!prevDispPositive || nextDisplacement < prevDisplacement)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator = m_generator;
|
|
Ankit Kumar Dwivedi |
701ccf |
minDisplacement = nextDisplacement;
|
|
Ankit Kumar Dwivedi |
701ccf |
minHeight = locals::height(m_coGenerator, nextDisplacement);
|
|
Ankit Kumar Dwivedi |
701ccf |
positiveEdgeDispl = (nextDispPositive && lastDisplacement > minusTol);
|
|
Ankit Kumar Dwivedi |
703f0f |
}
|
|
Ankit Kumar Dwivedi |
703f0f |
else
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator = m_generator->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
minDisplacement = prevDisplacement;
|
|
Ankit Kumar Dwivedi |
701ccf |
minHeight = locals::height(
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator,
|
|
Ankit Kumar Dwivedi |
701ccf |
firstDisplacement); // Height is built on the edge's first
|
|
Ankit Kumar Dwivedi |
701ccf |
positiveEdgeDispl =
|
|
Ankit Kumar Dwivedi |
701ccf |
(prevDispPositive &&
|
|
Ankit Kumar Dwivedi |
701ccf |
firstDisplacement >
|
|
Ankit Kumar Dwivedi |
701ccf |
minusTol); // endpoint to have the same values on adjacent
|
|
Ankit Kumar Dwivedi |
701ccf |
} // generators. It's important for SPECIAL events.
|
|
Ankit Kumar Dwivedi |
703f0f |
}
|
|
Ankit Kumar Dwivedi |
703f0f |
else if (prevDispPositive)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator = m_generator->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
minDisplacement = prevDisplacement;
|
|
Ankit Kumar Dwivedi |
701ccf |
minHeight = locals::height(m_coGenerator, firstDisplacement); // Same here
|
|
Ankit Kumar Dwivedi |
701ccf |
positiveEdgeDispl = (prevDispPositive && firstDisplacement > minusTol);
|
|
Ankit Kumar Dwivedi |
703f0f |
}
|
|
Ankit Kumar Dwivedi |
703f0f |
else
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
m_type = failure;
|
|
Ankit Kumar Dwivedi |
701ccf |
return;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
if (nextDispPositive && !m_generator->m_concave)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_generator->m_prev->m_concave && m_generator->m_next->m_concave &&
|
|
Ankit Kumar Dwivedi |
703f0f |
fabs(nextDisplacement - prevDisplacement) < 0.1)
|
|
Ankit Kumar Dwivedi |
c67741 |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *prevRay = m_generator->m_prev,
|
|
Ankit Kumar Dwivedi |
701ccf |
*nextRay = m_generator->m_next;
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
double side = prevRay->m_direction * nextRay->m_AngularMomentum +
|
|
Ankit Kumar Dwivedi |
701ccf |
nextRay->m_direction * prevRay->m_AngularMomentum;
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (fabs(side) < 0.03 * (cross(prevRay->m_direction, nextRay->m_direction)).mag())
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_type = special, m_coGenerator = m_generator;
|
|
Ankit Kumar Dwivedi |
703f0f |
}
|
|
Ankit Kumar Dwivedi |
703f0f |
else if (fabs(nextDisplacement - prevDisplacement) < 0.01)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator =
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_next->m_concave ? m_generator : m_generator->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now, if calculated height is coherent, this Event is valid.
|
|
Ankit Kumar Dwivedi |
701ccf |
if (positiveEdgeDispl // Edges shrinking to a point after a FORWARD
|
|
Ankit Kumar Dwivedi |
701ccf |
||
|
|
Ankit Kumar Dwivedi |
701ccf |
minHeight > m_context->m_currentHeight -
|
|
Ankit Kumar Dwivedi |
701ccf |
0.01) // displacement are processable - this dominates
|
|
Ankit Kumar Dwivedi |
701ccf |
m_height = minHeight,
|
|
Ankit Kumar Dwivedi |
701ccf |
m_displacement =
|
|
Ankit Kumar Dwivedi |
701ccf |
minDisplacement; // height considerations which may be affected by
|
|
Ankit Kumar Dwivedi |
701ccf |
else // numerical errors
|
|
Ankit Kumar Dwivedi |
701ccf |
m_type = failure;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
c67741 |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
703f0f |
inline void Event::calculateSplitEvent()
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int i;
|
|
Ankit Kumar Dwivedi |
701ccf |
bool forceFirst;
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *opposite, *first, *last;
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *="">::iterator currentContour;</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Sign *edges* not to be taken as possible opposites
|
|
Ankit Kumar Dwivedi |
701ccf |
for (i = 0; i < m_generator->m_notOpposites.size(); ++i)
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_notOpposites[i]->setAttribute(ContourEdge::NOT_OPPOSITE);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Check adjacent edge events
|
|
Ankit Kumar Dwivedi |
701ccf |
calculateEdgeEvent(); // DO NOT REMOVE - adjacent convexes may have
|
|
Ankit Kumar Dwivedi |
701ccf |
// been calculated too earlier
|
|
Ankit Kumar Dwivedi |
701ccf |
// First check opposites in the m_generator active contour
|
|
Ankit Kumar Dwivedi |
701ccf |
first =
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_next->m_next; // Adjacent edges were already considered
|
|
Ankit Kumar Dwivedi |
701ccf |
last = m_generator->m_prev->m_prev; // by calculateEdgeEvents()
|
|
Ankit Kumar Dwivedi |
703f0f |
for (opposite = first; opposite != last; opposite = opposite->m_next)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
if (!opposite->m_edge->hasAttribute(ContourEdge::NOT_OPPOSITE))
|
|
Ankit Kumar Dwivedi |
701ccf |
tryRayEdgeCollisionWith(opposite);
|
|
Ankit Kumar Dwivedi |
c67741 |
}
|
|
Ankit Kumar Dwivedi |
c67741 |
|
|
Ankit Kumar Dwivedi |
701ccf |
IndexTable &activeTable = m_context->m_activeTable;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Then, try in the remaining active contours whose identifier is != our
|
|
Ankit Kumar Dwivedi |
703f0f |
for (i = 0; i < activeTable.m_columns.size(); ++i)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
for (currentContour = activeTable[i]->begin();
|
|
Ankit Kumar Dwivedi |
703f0f |
currentContour != activeTable[i]->end(); currentContour++)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
// Da spostare sopra il 2o for
|
|
Ankit Kumar Dwivedi |
701ccf |
if (activeTable.m_identifiers[(*currentContour)->m_ancestorContour] !=
|
|
Ankit Kumar Dwivedi |
703f0f |
activeTable.m_identifiers[m_generator->m_ancestorContour])
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
first = *currentContour;
|
|
Ankit Kumar Dwivedi |
703f0f |
for (opposite = first, forceFirst = 1; !opposite->hasAttribute(ContourNode::HEAD) // opposite!=first
|
|
Ankit Kumar Dwivedi |
703f0f |
|| (forceFirst ? forceFirst = 0, 1 : 0); opposite = opposite->m_next)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
if (!opposite->m_edge->hasAttribute(ContourEdge::NOT_OPPOSITE))
|
|
Ankit Kumar Dwivedi |
701ccf |
tryRayEdgeCollisionWith(opposite);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Restore edge attributes
|
|
Ankit Kumar Dwivedi |
701ccf |
for (i = 0; i < m_generator->m_notOpposites.size(); ++i)
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_notOpposites[i]->clearAttribute(ContourEdge::NOT_OPPOSITE);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline bool Event::testRayEdgeCollision(ContourNode *opposite,
|
|
Ankit Kumar Dwivedi |
701ccf |
double &displacement, double &height,
|
|
Ankit Kumar Dwivedi |
701ccf |
double &side1, double &side2) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// Initialize test vectors
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: In the convex case, slab guards MUST be orthogonal to the edge, due
|
|
Ankit Kumar Dwivedi |
701ccf |
// to this case:
|
|
Ankit Kumar Dwivedi |
701ccf |
//
|
|
Ankit Kumar Dwivedi |
701ccf |
// ______/| the ray would not hit the edge - AND THUS FOREGO
|
|
Ankit Kumar Dwivedi |
701ccf |
// INTERACTION
|
|
Ankit Kumar Dwivedi |
701ccf |
// | WITH IT COMPLETELY
|
|
Ankit Kumar Dwivedi |
701ccf |
// -> |
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
16a65e |
synfig::Point3 firstSlabGuard =
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_concave ? opposite->m_direction
|
|
Ankit Kumar Dwivedi |
df3317 |
: synfig::Point3(opposite->m_edge->m_direction[1],
|
|
Ankit Kumar Dwivedi |
df3317 |
-(opposite->m_edge->m_direction[0]), 1);
|
|
Ankit Kumar Dwivedi |
16a65e |
synfig::Point3 lastSlabGuard =
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_next->m_concave
|
|
Ankit Kumar Dwivedi |
701ccf |
? opposite->m_next->m_direction
|
|
Ankit Kumar Dwivedi |
df3317 |
: synfig::Point3(opposite->m_edge->m_direction[1],
|
|
Ankit Kumar Dwivedi |
df3317 |
-(opposite->m_edge->m_direction[0]), 1);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
df3317 |
synfig::Point3 roofSlabOrthogonal(-(opposite->m_edge->m_direction[1]),
|
|
Ankit Kumar Dwivedi |
16a65e |
opposite->m_edge->m_direction[0], 1);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (roofSlabOrthogonal * (opposite->m_position - m_generator->m_position) >
|
|
Ankit Kumar Dwivedi |
701ccf |
-0.01 // Ray's vertex generator is below the roof slab
|
|
Ankit Kumar Dwivedi |
701ccf |
//&& roofSlabOrthogonal * m_generator->m_direction > 0
|
|
Ankit Kumar Dwivedi |
701ccf |
//// Ray must go 'against' the roof slab
|
|
Ankit Kumar Dwivedi |
4114f2 |
&& (roofSlabOrthogonal.to_2d()) * (m_generator->m_direction.to_2d()) > 0
|
|
Ankit Kumar Dwivedi |
4114f2 |
// Ray must go against the opposing edge
|
|
Ankit Kumar Dwivedi |
701ccf |
&&
|
|
Ankit Kumar Dwivedi |
701ccf |
(side1 = m_generator->m_direction *
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_AuxiliaryMomentum1 + // Ray must pass inside the
|
|
Ankit Kumar Dwivedi |
701ccf |
// first slab guard
|
|
Ankit Kumar Dwivedi |
701ccf |
firstSlabGuard * m_generator->m_AngularMomentum) > -0.01 //
|
|
Ankit Kumar Dwivedi |
701ccf |
&&
|
|
Ankit Kumar Dwivedi |
701ccf |
(side2 = m_generator->m_direction *
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_next->m_AuxiliaryMomentum2 + // Ray must pass
|
|
Ankit Kumar Dwivedi |
701ccf |
// inside the
|
|
Ankit Kumar Dwivedi |
701ccf |
// second slab
|
|
Ankit Kumar Dwivedi |
701ccf |
// guard
|
|
Ankit Kumar Dwivedi |
701ccf |
lastSlabGuard * m_generator->m_AngularMomentum) < 0.01 //
|
|
Ankit Kumar Dwivedi |
701ccf |
&&
|
|
Ankit Kumar Dwivedi |
701ccf |
(m_generator->m_ancestorContour !=
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_ancestorContour // Helps with immediate splits from
|
|
Ankit Kumar Dwivedi |
701ccf |
// coincident
|
|
Ankit Kumar Dwivedi |
701ccf |
|| m_generator->m_ancestor != opposite->m_ancestor)) // linear vertexes
|
|
Ankit Kumar Dwivedi |
701ccf |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
displacement = splitDisplacementWith(opposite);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Possible Security checks for almost complanarity cases
|
|
Ankit Kumar Dwivedi |
701ccf |
//----------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (displacement > -0.01 && displacement < 0.01) {
|
|
Ankit Kumar Dwivedi |
df3317 |
synfig::Point3 slabLeftOrthogonal(-(opposite->m_edge->m_direction[1]),
|
|
Ankit Kumar Dwivedi |
16a65e |
opposite->m_edge->m_direction[0], 1);
|
|
Ankit Kumar Dwivedi |
701ccf |
double check1 =
|
|
Ankit Kumar Dwivedi |
701ccf |
(m_generator->m_position - opposite->m_position) *
|
|
Ankit Kumar Dwivedi |
703f0f |
(cross(opposite->m_direction, slabLeftOrthogonal)).norm();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
double check2 =
|
|
Ankit Kumar Dwivedi |
701ccf |
(m_generator->m_position - opposite->m_next->m_position) *
|
|
Ankit Kumar Dwivedi |
4114f2 |
(cross(opposite->m_next->m_direction, slabLeftOrthogonal).norm());
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (check1 > 0.02 || check2 < -0.02) return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//----------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Check height/displacement conditions
|
|
Ankit Kumar Dwivedi |
701ccf |
if (displacement > -0.01 &&
|
|
Ankit Kumar Dwivedi |
701ccf |
displacement < m_displacement + 0.01 // admitting concurrent events
|
|
Ankit Kumar Dwivedi |
701ccf |
&&
|
|
Ankit Kumar Dwivedi |
16a65e |
(height = m_generator->m_position[2] +
|
|
Ankit Kumar Dwivedi |
16a65e |
displacement * m_generator->m_direction[2]) >
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_currentHeight - 0.01)
|
|
Ankit Kumar Dwivedi |
701ccf |
return true;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
inline bool Event::tryRayEdgeCollisionWith(ContourNode *opposite)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *newCoGenerator;
|
|
Ankit Kumar Dwivedi |
701ccf |
Type type;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
double displacement, height, side1, side2;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
if (testRayEdgeCollision(opposite, displacement, height, side1, side2))
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
703f0f |
type = split_regenerate;
|
|
Ankit Kumar Dwivedi |
701ccf |
newCoGenerator = opposite;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Check against the REAL slab guards for type deduction
|
|
Ankit Kumar Dwivedi |
701ccf |
double firstSide =
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_concave
|
|
Ankit Kumar Dwivedi |
701ccf |
? side1
|
|
Ankit Kumar Dwivedi |
701ccf |
: m_generator->m_direction * opposite->m_AngularMomentum +
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_direction * m_generator->m_AngularMomentum,
|
|
Ankit Kumar Dwivedi |
701ccf |
secondSide = opposite->m_next->m_concave
|
|
Ankit Kumar Dwivedi |
701ccf |
? side2
|
|
Ankit Kumar Dwivedi |
701ccf |
: m_generator->m_direction *
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_next->m_AngularMomentum +
|
|
Ankit Kumar Dwivedi |
701ccf |
opposite->m_next->m_direction *
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_AngularMomentum;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
if (firstSide > -0.01 && secondSide < 0.01)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
double displacement_, height_;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
if (firstSide < 0.01)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
// Ray hits first extremity of edge
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (opposite->m_concave || testRayEdgeCollision(opposite->m_prev, displacement_, height_, side1, side2))
|
|
Ankit Kumar Dwivedi |
701ccf |
type = vertex;
|
|
Ankit Kumar Dwivedi |
703f0f |
}
|
|
Ankit Kumar Dwivedi |
703f0f |
else if (secondSide > -0.01)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
// Ray hits second extremity of edge
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (opposite->m_next->m_concave || testRayEdgeCollision(opposite->m_next, displacement_, height_, side1, side2))
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
type = vertex;
|
|
Ankit Kumar Dwivedi |
701ccf |
newCoGenerator = opposite->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
} else
|
|
Ankit Kumar Dwivedi |
701ccf |
type = split;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (type == split_regenerate &&
|
|
Ankit Kumar Dwivedi |
701ccf |
height <=
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context
|
|
Ankit Kumar Dwivedi |
701ccf |
->m_currentHeight) // Split regeneration is allowed only at
|
|
Ankit Kumar Dwivedi |
701ccf |
return false; // future times
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// If competing with another event split/vertex, approve replacement only if
|
|
Ankit Kumar Dwivedi |
701ccf |
// the angle
|
|
Ankit Kumar Dwivedi |
701ccf |
// between m_generator and newCoGenerator is < than with current
|
|
Ankit Kumar Dwivedi |
701ccf |
// m_coGenerator.
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_type != edge && fabs(displacement - m_displacement) < 0.01 &&
|
|
Ankit Kumar Dwivedi |
701ccf |
angleLess(m_coGenerator->m_edge->m_direction,
|
|
Ankit Kumar Dwivedi |
701ccf |
newCoGenerator->m_edge->m_direction,
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_edge->m_direction))
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_type = type, m_coGenerator = newCoGenerator;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_displacement = displacement, m_height = height;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
return true;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline double Event::splitDisplacementWith(ContourNode *slab) {
|
|
Ankit Kumar Dwivedi |
df3317 |
synfig::Point slabLeftOrthogonal(-(slab->m_edge->m_direction[1]),
|
|
Ankit Kumar Dwivedi |
16a65e |
slab->m_edge->m_direction[0]);
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point temp(m_generator->m_direction[0], m_generator->m_direction[1]);
|
|
Ankit Kumar Dwivedi |
4114f2 |
double denom = m_generator->m_direction[2] + slabLeftOrthogonal * temp;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (denom < 0.01)
|
|
Ankit Kumar Dwivedi |
701ccf |
return -1; // generator-emitted ray is almost parallel to slab
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
synfig::Point difference = (slab->m_position - m_generator->m_position).to_2d();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
16a65e |
return (slabLeftOrthogonal * difference + slab->m_position[2] -
|
|
Ankit Kumar Dwivedi |
16a65e |
m_generator->m_position[2]) /
|
|
Ankit Kumar Dwivedi |
701ccf |
denom;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
// Event Processing
|
|
Ankit Kumar Dwivedi |
701ccf |
//------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Event::Process discriminates event types and calls their specific handlers
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
inline bool Event::process()
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
Timeline &timeline = m_context->m_timeline;
|
|
luzpaz |
7cbe4e |
unsigned int &algorithmicTime = m_context->m_algorithmicTime;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
if (!m_generator->hasAttribute(ContourNode::ELIMINATED))
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
703f0f |
switch (m_type)
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
case special:
|
|
Ankit Kumar Dwivedi |
701ccf |
assert(!m_coGenerator->hasAttribute(ContourNode::ELIMINATED));
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator->m_prev->hasAttribute(
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode::ELIMINATED) || // These two are most probably
|
|
Ankit Kumar Dwivedi |
701ccf |
// useless - could
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->hasAttribute(
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode::ELIMINATED) || // try to remove them once I'm in for
|
|
Ankit Kumar Dwivedi |
701ccf |
// some testing...
|
|
luzpaz |
7cbe4e |
m_algorithmicTime < m_coGenerator->m_prev->m_updateTime ||
|
|
luzpaz |
7cbe4e |
m_algorithmicTime < m_coGenerator->m_next->m_updateTime) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// recalculate event
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newEvent(m_generator, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newEvent.m_type != failure) timeline.push(newEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// else allow processing
|
|
luzpaz |
7cbe4e |
algorithmicTime++;
|
|
Ankit Kumar Dwivedi |
701ccf |
processSpecialEvent();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
break;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
case edge:
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) ||
|
|
luzpaz |
7cbe4e |
m_algorithmicTime < m_coGenerator->m_next->m_updateTime) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// recalculate event
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newEvent(m_generator, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newEvent.m_type != failure) timeline.push(newEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Deal with edge superposition cases *only* when m_generator has the
|
|
Ankit Kumar Dwivedi |
16a65e |
// m_direction[2] == 0.0
|
|
Ankit Kumar Dwivedi |
16a65e |
if ((m_coGenerator->m_direction[2] == 0.0 &&
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator != m_generator) ||
|
|
Ankit Kumar Dwivedi |
16a65e |
(m_coGenerator->m_next->m_direction[2] == 0.0 &&
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator == m_generator))
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// else allow processing
|
|
luzpaz |
7cbe4e |
algorithmicTime++; // global
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_generator->m_next->m_next == m_generator->m_prev)
|
|
Ankit Kumar Dwivedi |
701ccf |
processMaxEvent();
|
|
Ankit Kumar Dwivedi |
701ccf |
else
|
|
Ankit Kumar Dwivedi |
701ccf |
processEdgeEvent();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
break;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
case vertex:
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// recalculate event
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newEvent(m_generator, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newEvent.m_type != failure) timeline.push(newEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Unlike the split case, we don't need to rebuild if
|
|
Ankit Kumar Dwivedi |
701ccf |
// the event is not up to date with m_coGenerator - since
|
|
Ankit Kumar Dwivedi |
701ccf |
// the event is not about splitting an edge
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator ==
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_next
|
|
Ankit Kumar Dwivedi |
701ccf |
->m_next // CAN devolve to a special event - which should
|
|
Ankit Kumar Dwivedi |
701ccf |
||
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator ==
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_prev
|
|
Ankit Kumar Dwivedi |
701ccf |
->m_prev) // already be present in the timeline
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// then, process it
|
|
luzpaz |
7cbe4e |
algorithmicTime++;
|
|
Ankit Kumar Dwivedi |
701ccf |
processVertexEvent();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
break;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
case split_regenerate:
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) ||
|
|
luzpaz |
7cbe4e |
(m_algorithmicTime < m_coGenerator->m_next->m_updateTime)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// recalculate event
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newEvent(m_generator, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newEvent.m_type != failure) timeline.push(newEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// This may actually happen on current implementation, due to quirky event
|
|
Ankit Kumar Dwivedi |
701ccf |
// generation and preferential events rejection. See function tryRay..()
|
|
Ankit Kumar Dwivedi |
701ccf |
// around the end. Historically resolved to a split event, so we maintain
|
|
Ankit Kumar Dwivedi |
701ccf |
// that.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// assert(false);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
/* fallthrough */
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
case split: // No break is intended
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) ||
|
|
luzpaz |
7cbe4e |
(m_algorithmicTime < m_coGenerator->m_next->m_updateTime)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// recalculate event
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newEvent(m_generator, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newEvent.m_type != failure) timeline.push(newEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
return false;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// else allow processing (but check these conditions)
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator != m_generator->m_next &&
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator !=
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_prev
|
|
Ankit Kumar Dwivedi |
701ccf |
->m_prev) // Because another edge already occurs at his place
|
|
Ankit Kumar Dwivedi |
701ccf |
{
|
|
luzpaz |
7cbe4e |
algorithmicTime++;
|
|
Ankit Kumar Dwivedi |
701ccf |
processSplitEvent();
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
break;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
return true; // Processing succeeded
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// EXPLANATION: Here is the typical case:
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// \ /
|
|
Ankit Kumar Dwivedi |
701ccf |
// \ x /
|
|
Ankit Kumar Dwivedi |
701ccf |
// 2---1 = m_coGenerator
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// m_coGenerator's edge reduces to 0. Then, nodes 1 and 2 gets ELIMINATED from
|
|
Ankit Kumar Dwivedi |
701ccf |
// the active contour and a new node at position "x" is placed instead.
|
|
Ankit Kumar Dwivedi |
701ccf |
// Observe also that nodes 1 or 2 may be concave (but not both)...
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void Event::processEdgeEvent() {
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *newNode;
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point3 position(m_generator->m_position + m_generator->m_direction * m_displacement);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Eliminate and unlink extremities of m_coGenerator's edge
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Then, take a node from heap and insert it at their place.
|
|
Ankit Kumar Dwivedi |
4114f2 |
newNode = m_context->getNode();
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_position = position;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
newNode->m_next = m_coGenerator->m_next->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->m_next->m_prev = newNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
newNode->m_prev = m_coGenerator->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_prev->m_next = newNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Then, initialize new node (however, 3rd component is m_height...)
|
|
Ankit Kumar Dwivedi |
4114f2 |
newNode->m_position =
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_generator->m_position + m_generator->m_direction * m_displacement;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_edge = m_coGenerator->m_next->m_edge;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->buildNodeInfos(1); // 1 => Force convex node
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_ancestor = m_coGenerator->m_next->m_ancestor;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_ancestorContour = m_coGenerator->m_next->m_ancestorContour;
|
|
luzpaz |
7cbe4e |
newNode->m_updateTime = m_context->m_algorithmicTime;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// We allocate an output vertex on newNode's position under these conditions
|
|
Ankit Kumar Dwivedi |
701ccf |
// NOTE: Update once graph_old is replaced
|
|
Ankit Kumar Dwivedi |
16a65e |
if (newNode->m_direction[2] < 0.7 ||
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->hasAttribute(ContourNode::SK_NODE_DROPPED) ||
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_coGenerator->m_next->hasAttribute(ContourNode::SK_NODE_DROPPED)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->setAttribute(ContourNode::SK_NODE_DROPPED);
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_outputNode = m_context->m_output->newNode(position);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_next);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// If m_coGenerator or its m_next is HEAD of this contour, then
|
|
Ankit Kumar Dwivedi |
701ccf |
// redefine newNode as the new head.
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator->hasAttribute(ContourNode::HEAD) ||
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_coGenerator->m_next->hasAttribute(ContourNode::HEAD)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *="">::iterator it;</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *=""> &column =</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_activeTable.columnOfId(m_generator->m_ancestorContour);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (it = column.begin(); !(*it)->hasAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
4114f2 |
++it)
|
|
Ankit Kumar Dwivedi |
4114f2 |
;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// assert(*it == m_coGenerator || *it == m_coGenerator->m_next);
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
701ccf |
*it = newNode, newNode->setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Finally, calculate the Event raising by newNode
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newEvent(newNode, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newEvent.m_type != Event::failure) m_context->m_timeline.push(newEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Typical triangle case
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
inline void Event::processMaxEvent() {
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point3 position(m_generator->m_position +
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_generator->m_direction * m_displacement);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int outputNode = m_context->m_output->newNode(position);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(outputNode, m_generator);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(outputNode, m_generator->m_prev);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(outputNode, m_generator->m_next);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Then remove active contour and eliminate nodes
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *="">::iterator eventVertexIndex =</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_activeTable.find(m_generator);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_activeTable.remove(eventVertexIndex);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_prev->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_next->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// EXPLANATION: Ordinary split event:
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// m_coGenerator = a'---------b'
|
|
Ankit Kumar Dwivedi |
701ccf |
// x
|
|
Ankit Kumar Dwivedi |
701ccf |
// b = m_generator
|
|
Ankit Kumar Dwivedi |
701ccf |
// / \
|
|
Ankit Kumar Dwivedi |
701ccf |
// c a
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// We eliminate b and split/merge the border/s represented in the scheme.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void Event::processSplitEvent() {
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourNode *newLeftNode,
|
|
Ankit Kumar Dwivedi |
4114f2 |
*newRightNode; // left-right in the sense of the picture
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point3 position(m_generator->m_position +
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_generator->m_direction * m_displacement);
|
|
Ankit Kumar Dwivedi |
4114f2 |
IndexTable &activeTable = m_context->m_activeTable;
|
|
luzpaz |
7cbe4e |
unsigned int &algorithmicTime = m_context->m_algorithmicTime;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// First, we find in the Index Table the contours involved
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *="">::iterator genContour, coGenContour;</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
genContour = activeTable.find(m_generator);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
|
|
Ankit Kumar Dwivedi |
701ccf |
activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// We have two different contours, that merge in one
|
|
Ankit Kumar Dwivedi |
701ccf |
coGenContour = activeTable.find(m_coGenerator);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now, update known nodes
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Allocate 2 new nodes and link the following way:
|
|
Ankit Kumar Dwivedi |
4114f2 |
newLeftNode = m_context->getNode();
|
|
Ankit Kumar Dwivedi |
4114f2 |
newRightNode = m_context->getNode();
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_position = newRightNode->m_position = position;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// On the right side
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->m_prev = newRightNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_next = m_coGenerator->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_prev->m_next = newRightNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_prev = m_generator->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// On the left side
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next = newLeftNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_prev = m_coGenerator;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_next->m_prev = newLeftNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_next = m_generator->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
luzpaz |
7cbe4e |
// Assign and calculate the new nodes' information
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_edge = m_generator->m_edge;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_edge = m_coGenerator->m_edge;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_ancestor = m_generator->m_ancestor;
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_ancestorContour = m_generator->m_ancestorContour;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_ancestor = m_coGenerator->m_ancestor;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_ancestorContour = m_coGenerator->m_ancestorContour;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// We can force the new nodes to be convex
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->buildNodeInfos(1);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->buildNodeInfos(1);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
luzpaz |
7cbe4e |
newLeftNode->m_updateTime = newRightNode->m_updateTime = algorithmicTime;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now, output the found interaction
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->setAttribute(ContourNode::SK_NODE_DROPPED);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->setAttribute(ContourNode::SK_NODE_DROPPED);
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_outputNode = m_context->m_output->newNode(position);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_outputNode = newLeftNode->m_outputNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newLeftNode->m_outputNode, m_generator);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Update the active Index Table:
|
|
Ankit Kumar Dwivedi |
701ccf |
if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
|
|
Ankit Kumar Dwivedi |
703f0f |
activeTable.m_identifiers[m_coGenerator->m_ancestorContour])
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
// If we have two different contours, they merge in one
|
|
Ankit Kumar Dwivedi |
701ccf |
// We keep coGenContour and remove genContour
|
|
Ankit Kumar Dwivedi |
701ccf |
(*genContour)->clearAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
activeTable.merge(coGenContour, genContour);
|
|
Ankit Kumar Dwivedi |
703f0f |
}
|
|
Ankit Kumar Dwivedi |
703f0f |
else
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
// Else we have only one contour, which splits in two
|
|
Ankit Kumar Dwivedi |
701ccf |
(*genContour)->clearAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
*genContour = newLeftNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
activeTable.columnOfId(m_generator->m_ancestorContour)
|
|
Ankit Kumar Dwivedi |
4114f2 |
.push_back(newRightNode);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// (Vertex compatibility): Moving newRightNode a bit on
|
|
Ankit Kumar Dwivedi |
4114f2 |
newRightNode->m_position += newRightNode->m_direction * 0.02;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Finally, calculate the new left and right Events
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newLeftEvent(newLeftNode, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newLeftEvent.m_type != Event::failure)
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_timeline.push(newLeftEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newRightEvent(newRightNode, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newRightEvent.m_type != Event::failure)
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_timeline.push(newRightEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// EXPLANATION:
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// c L a'
|
|
Ankit Kumar Dwivedi |
701ccf |
// \ /
|
|
Ankit Kumar Dwivedi |
701ccf |
// m_generator = b x b' = m_coGenerator
|
|
Ankit Kumar Dwivedi |
701ccf |
// / \
|
|
Ankit Kumar Dwivedi |
701ccf |
// a R c'
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Reflex vertices b and b' collide. Observe that a new reflex vertex may rise
|
|
Ankit Kumar Dwivedi |
701ccf |
// here.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
inline void Event::processVertexEvent() {
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourNode *newLeftNode, *newRightNode; // left-right in the sense of the picture
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point3 position(m_generator->m_position +
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_generator->m_direction * m_displacement);
|
|
Ankit Kumar Dwivedi |
701ccf |
IndexTable &activeTable = m_context->m_activeTable;
|
|
luzpaz |
7cbe4e |
unsigned int &algorithmicTime = m_context->m_algorithmicTime;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// First, we find in the Index Table the contours involved
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *="">::iterator genContour, coGenContour;</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
genContour = activeTable.find(m_generator);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
|
|
Ankit Kumar Dwivedi |
4114f2 |
activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// We have two different contours, that merge in one
|
|
Ankit Kumar Dwivedi |
701ccf |
coGenContour = activeTable.find(m_coGenerator);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now, update known nodes
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Allocate 2 new nodes and link the following way:
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode = m_context->getNode();
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode = m_context->getNode();
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_position = newRightNode->m_position = position;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// On the right side
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->m_prev = newRightNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_next = m_coGenerator->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_prev->m_next = newRightNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_prev = m_generator->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// On the left side
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_prev->m_next = newLeftNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_prev = m_coGenerator->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_generator->m_next->m_prev = newLeftNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_next = m_generator->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
luz.paz |
7040b8 |
// Assign and calculate the new nodes' information
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_edge = m_generator->m_edge;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_edge = m_coGenerator->m_edge;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_ancestor = m_generator->m_ancestor;
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_ancestorContour = m_generator->m_ancestorContour;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_ancestor = m_coGenerator->m_ancestor;
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_ancestorContour = m_coGenerator->m_ancestorContour;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// We *CAN'T* force the new nodes to be convex here
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->buildNodeInfos();
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->buildNodeInfos();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
luzpaz |
7cbe4e |
newLeftNode->m_updateTime = newRightNode->m_updateTime = algorithmicTime;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now, output the found interaction
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->setAttribute(ContourNode::SK_NODE_DROPPED);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->setAttribute(ContourNode::SK_NODE_DROPPED);
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_outputNode = m_context->m_output->newNode(position);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_outputNode = newLeftNode->m_outputNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newLeftNode->m_outputNode, m_generator);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newLeftNode->m_outputNode, m_coGenerator);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Update the active Index Table
|
|
Ankit Kumar Dwivedi |
701ccf |
if (activeTable.m_identifiers[m_generator->m_ancestorContour] !=
|
|
Ankit Kumar Dwivedi |
4114f2 |
activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) {
|
|
Ankit Kumar Dwivedi |
701ccf |
// If we have two different contours, they merge in one
|
|
Ankit Kumar Dwivedi |
701ccf |
(*coGenContour)->clearAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
activeTable.merge(genContour, coGenContour);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Check if the generator is head, if so update.
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (m_generator->hasAttribute(ContourNode::HEAD)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
*genContour = newLeftNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
} else {
|
|
Ankit Kumar Dwivedi |
701ccf |
// Else we have only one contour, which splits in two
|
|
Ankit Kumar Dwivedi |
701ccf |
(*genContour)->clearAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
*genContour = newLeftNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
activeTable.columnOfId(m_generator->m_ancestorContour)
|
|
Ankit Kumar Dwivedi |
4114f2 |
.push_back(newRightNode);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Before calculating the new interactions, to each new node we assign
|
|
Ankit Kumar Dwivedi |
701ccf |
// as impossible opposite edges the adjacent of the other node.
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (newLeftNode->m_concave) {
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_notOpposites = m_generator->m_notOpposites;
|
|
Ankit Kumar Dwivedi |
701ccf |
append<std::vector<contouredge *="">,</std::vector<contouredge>
|
|
Ankit Kumar Dwivedi |
701ccf |
std::vector<contouredge *="">::reverse_iterator>(</contouredge>
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_notOpposites, m_coGenerator->m_notOpposites);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_notOpposites.push_back(newRightNode->m_edge);
|
|
Ankit Kumar Dwivedi |
701ccf |
newLeftNode->m_notOpposites.push_back(newRightNode->m_prev->m_edge);
|
|
Ankit Kumar Dwivedi |
4114f2 |
} else if (newRightNode->m_concave) {
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_notOpposites = m_generator->m_notOpposites;
|
|
Ankit Kumar Dwivedi |
701ccf |
append<std::vector<contouredge *="">,</std::vector<contouredge>
|
|
Ankit Kumar Dwivedi |
701ccf |
std::vector<contouredge *="">::reverse_iterator>(</contouredge>
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_notOpposites, m_coGenerator->m_notOpposites);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_notOpposites.push_back(newLeftNode->m_edge);
|
|
Ankit Kumar Dwivedi |
701ccf |
newRightNode->m_notOpposites.push_back(newLeftNode->m_prev->m_edge);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// We also forbid newRightNode to be involved in events at the same location
|
|
Ankit Kumar Dwivedi |
701ccf |
// of this one.
|
|
Ankit Kumar Dwivedi |
701ccf |
// We just push its position in the m_direction by 0.02.
|
|
Ankit Kumar Dwivedi |
4114f2 |
newRightNode->m_position += newRightNode->m_direction * 0.02;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Finally, calculate the new left and right Events
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newLeftEvent(newLeftNode, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newLeftEvent.m_type != Event::failure)
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_timeline.push(newLeftEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newRightEvent(newRightNode, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newRightEvent.m_type != Event::failure)
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_timeline.push(newRightEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// EXPLANATION:
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// x
|
|
Ankit Kumar Dwivedi |
701ccf |
// ---c a---
|
|
Ankit Kumar Dwivedi |
701ccf |
// \ /
|
|
Ankit Kumar Dwivedi |
701ccf |
// b = m_coGenerator
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Typical "V" event in which rays emitted from a, b and c collide.
|
|
Ankit Kumar Dwivedi |
701ccf |
// This events have to be recognized different from vertex events, and
|
|
Ankit Kumar Dwivedi |
701ccf |
// better treated as a whole event, rather than two simultaneous edge events.
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
703f0f |
inline void Event::processSpecialEvent()
|
|
Ankit Kumar Dwivedi |
703f0f |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
ContourNode *newNode;
|
|
Ankit Kumar Dwivedi |
4114f2 |
synfig::Point3 position(m_generator->m_position +
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_generator->m_direction * m_displacement);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_prev->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->setAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Get and link newNode to the rest of this contour
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode = m_context->getNode();
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_position = position;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_prev->m_prev->m_next = newNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_prev = m_coGenerator->m_prev->m_prev;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->m_next->m_prev = newNode;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_next = m_coGenerator->m_next->m_next;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Then, initialize newNode infos
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_edge = m_coGenerator->m_next->m_edge;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_ancestor = m_coGenerator->m_next->m_ancestor;
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_ancestorContour = m_coGenerator->m_next->m_ancestorContour;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Neither this case can be forced convex
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->buildNodeInfos();
|
|
luzpaz |
7cbe4e |
newNode->m_updateTime = m_context->m_algorithmicTime;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Now build output
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->setAttribute(ContourNode::SK_NODE_DROPPED);
|
|
Ankit Kumar Dwivedi |
701ccf |
newNode->m_outputNode = m_context->m_output->newNode(position);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_prev);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator);
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_next);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// If m_coGenerator or one of his adjacents is HEAD of this contour, then
|
|
Ankit Kumar Dwivedi |
701ccf |
// redefine newNode as the new head.
|
|
Ankit Kumar Dwivedi |
701ccf |
if (m_coGenerator->hasAttribute(ContourNode::HEAD) ||
|
|
Ankit Kumar Dwivedi |
701ccf |
m_coGenerator->m_next->hasAttribute(ContourNode::HEAD) ||
|
|
Ankit Kumar Dwivedi |
4114f2 |
m_coGenerator->m_prev->hasAttribute(ContourNode::HEAD)) {
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *="">::iterator it;</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
std::list<contournode *=""> &column =</contournode>
|
|
Ankit Kumar Dwivedi |
701ccf |
m_context->m_activeTable.columnOfId(m_generator->m_ancestorContour);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (it = column.begin(); !(*it)->hasAttribute(ContourNode::ELIMINATED);
|
|
Ankit Kumar Dwivedi |
4114f2 |
++it)
|
|
Ankit Kumar Dwivedi |
4114f2 |
;
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
4114f2 |
// assert(*it == m_coGenerator || *it == m_coGenerator->m_next || *it ==
|
|
Ankit Kumar Dwivedi |
4114f2 |
// m_coGenerator->m_prev);
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
701ccf |
*it = newNode, newNode->setAttribute(ContourNode::HEAD);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Finally, calculate the Event raising by newNode
|
|
Ankit Kumar Dwivedi |
701ccf |
Event newEvent(newNode, m_context);
|
|
Ankit Kumar Dwivedi |
701ccf |
if (newEvent.m_type != Event::failure) m_context->m_timeline.push(newEvent);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//==========================================================================
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//-------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
// Straight Skeleton mains
|
|
Ankit Kumar Dwivedi |
701ccf |
//-------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
static SkeletonGraph *skeletonize(ContourFamily ®ionContours,
|
|
ankit-kumar-dwivedi |
81bea2 |
VectorizationContext &context) {
|
|
Ankit Kumar Dwivedi |
701ccf |
SkeletonGraph *output = context.m_output = new SkeletonGraph;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
context.prepareContours(regionContours);
|
|
Ankit Kumar Dwivedi |
701ccf |
context.prepareGlobals();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
IndexTable &activeTable = context.m_activeTable;
|
|
Ankit Kumar Dwivedi |
701ccf |
activeTable.build(regionContours);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
double maxThickness = context.m_globals->currConfig->m_maxThickness;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
4114f2 |
if (maxThickness > 0.0) // if(!currConfig->m_outline)
|
|
Ankit Kumar Dwivedi |
701ccf |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
Timeline &timeline = context.m_timeline;
|
|
ankit-kumar-dwivedi |
81bea2 |
timeline.build(regionContours, context);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Process timeline
|
|
Ankit Kumar Dwivedi |
4114f2 |
while (!timeline.empty()) {
|
|
Ankit Kumar Dwivedi |
701ccf |
Event currentEvent = timeline.top();
|
|
Ankit Kumar Dwivedi |
701ccf |
timeline.pop();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// If maxThickness hit, stop before processing
|
|
Ankit Kumar Dwivedi |
701ccf |
if (currentEvent.m_height >= maxThickness) break;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Process event
|
|
Ankit Kumar Dwivedi |
701ccf |
currentEvent.process();
|
|
Ankit Kumar Dwivedi |
701ccf |
context.m_currentHeight = currentEvent.m_height;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// The thinning process terminates: deleting non-original nodes and edges.
|
|
Ankit Kumar Dwivedi |
701ccf |
while (!timeline.empty()) timeline.pop();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Finally, update remaining nodes not processed due to maxThickness and
|
|
Ankit Kumar Dwivedi |
701ccf |
// connect them to output skeleton
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int i, l, n;
|
|
Ankit Kumar Dwivedi |
701ccf |
IndexTable::IndexColumn::iterator j;
|
|
Ankit Kumar Dwivedi |
4114f2 |
ContourNode *k;
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
for (i = 0; i < regionContours.size(); ++i)
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (j = activeTable[i]->begin(); j != activeTable[i]->end(); ++j) {
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int count = 0;
|
|
Ankit Kumar Dwivedi |
701ccf |
unsigned int addedNode;
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (k = *j; !k->hasAttribute(ContourNode::HEAD) || !count;
|
|
Ankit Kumar Dwivedi |
4114f2 |
k = k->m_next) {
|
|
Ankit Kumar Dwivedi |
4114f2 |
addedNode = output->newNode(k->m_position + k->m_direction *((maxThickness - k->m_position[2]) /
|
|
Ankit Kumar Dwivedi |
4114f2 |
(k->m_direction[2] > 0.01 ? k->m_direction[2] : 1)));
|
|
Ankit Kumar Dwivedi |
701ccf |
context.newSkeletonLink(addedNode, k);
|
|
Ankit Kumar Dwivedi |
4114f2 |
// output->node(addedNode).setAttribute(ContourNode::SS_OUTLINE);
|
|
Ankit Kumar Dwivedi |
701ccf |
++count;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
n = output->getNodesCount();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
SkeletonArc arcCopy;
|
|
Ankit Kumar Dwivedi |
701ccf |
SkeletonArc arcCopyRev;
|
|
Ankit Kumar Dwivedi |
701ccf |
arcCopy.setAttribute(SkeletonArc::SS_OUTLINE);
|
|
Ankit Kumar Dwivedi |
701ccf |
arcCopyRev.setAttribute(SkeletonArc::SS_OUTLINE_REVERSED);
|
|
Ankit Kumar Dwivedi |
295555 |
for (l = 1; l < count; ++l)
|
|
Ankit Kumar Dwivedi |
295555 |
{
|
|
Ankit Kumar Dwivedi |
701ccf |
output->newLink(n - l, n - l - 1, arcCopyRev);
|
|
Ankit Kumar Dwivedi |
701ccf |
output->newLink(n - l - 1, n - l, arcCopy);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
output->newLink(n - l, n - 1, arcCopyRev);
|
|
Ankit Kumar Dwivedi |
701ccf |
output->newLink(n - 1, n - l, arcCopy);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
701ccf |
context.m_nodesHeap.clear();
|
|
Ankit Kumar Dwivedi |
701ccf |
context.m_edgesHeap.clear();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
context.m_linearNodesHeap.clear();
|
|
Ankit Kumar Dwivedi |
701ccf |
context.m_linearEdgesHeap.clear();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
return output;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
//--------------------------------------------------------------------------
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
ankit-kumar-dwivedi |
81bea2 |
SkeletonList* studio::skeletonize(Contours &contours, const etl::handle<synfigapp::uiinterface> &ui_interface, VectorizerCoreGlobals &g) {</synfigapp::uiinterface>
|
|
Ankit Kumar Dwivedi |
701ccf |
VectorizationContext context(&g);
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
SkeletonList *res = new SkeletonList;
|
|
ankit-kumar-dwivedi |
81bea2 |
unsigned int i, j,contours_size = contours.size();
|
|
Ankit Kumar Dwivedi |
4114f2 |
|
|
Ankit Kumar Dwivedi |
701ccf |
// Find overall number of nodes
|
|
Ankit Kumar Dwivedi |
4114f2 |
unsigned int overallNodes = 0;
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (i = 0; i < contours.size(); ++i)
|
|
Ankit Kumar Dwivedi |
4114f2 |
for (j = 0; j < contours[i].size(); ++j)
|
|
Ankit Kumar Dwivedi |
4114f2 |
overallNodes += contours[i][j].size();
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
ankit-kumar-dwivedi |
81bea2 |
for (i = 0; i
|
|
ankit-kumar-dwivedi |
81bea2 |
res->push_back(skeletonize(contours[i], context));
|
|
ankit-kumar-dwivedi |
81bea2 |
float partial = 30.0 + ((i/(float)contours_size)*30.0);
|
|
ankit-kumar-dwivedi |
81bea2 |
ui_interface->amount_complete(partial,100);
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
701ccf |
|
|
Ankit Kumar Dwivedi |
701ccf |
return res;
|
|
Ankit Kumar Dwivedi |
701ccf |
}
|
|
Ankit Kumar Dwivedi |
4114f2 |
|