| |
| |
| #include "tcenterlinevectP.h" |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| struct VectorizationContext; |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| #ifdef _SSDEBUG |
| |
| #include <QWidget> |
| #include <QTransform> |
| #include <QEventLoop> |
| #include <QPainter> |
| #include <QMouseEvent> |
| #include <QWheelEvent> |
| |
| class SSDebugger final : public QWidget { |
| public: |
| VectorizationContext &m_context; |
| |
| QPoint m_pos, m_pressPos; |
| |
| double m_scale; |
| QTransform m_transform; |
| QEventLoop m_loop; |
| |
| public: |
| double m_height; |
| |
| public: |
| SSDebugger(VectorizationContext &context); |
| ~SSDebugger() {} |
| |
| void loop() { m_loop.exec(); } |
| |
| void paintEvent(QPaintEvent *event); |
| void keyPressEvent(QKeyEvent *event); |
| void mouseMoveEvent(QMouseEvent *event); |
| void mousePressEvent(QMouseEvent *event); |
| void mouseReleaseEvent(QMouseEvent *event); |
| void wheelEvent(QWheelEvent *event); |
| |
| inline QPoint winToWorld(int x, int y); |
| inline QPoint worldToWin(double x, double y); |
| inline QPointF winToWorldF(int x, int y); |
| |
| inline bool isOnScreen(ContourNode *node); |
| |
| |
| TPointD updated(ContourNode *input); |
| }; |
| |
| #endif |
| |
| |
| |
| |
| |
| class ContourEdge { |
| public: |
| enum { NOT_OPPOSITE = 0x1 }; |
| |
| public: |
| TPointD m_direction; |
| unsigned short m_attributes; |
| |
| public: |
| ContourEdge() : m_attributes(0) {} |
| ContourEdge(TPointD dir) : m_direction(dir), m_attributes(0) {} |
| |
| int hasAttribute(int attr) const { return m_attributes & attr; } |
| void setAttribute(int attr) { m_attributes |= attr; } |
| void clearAttribute(int attr) { m_attributes &= ~attr; } |
| }; |
| |
| |
| |
| class IndexTable { |
| public: |
| typedef std::list<ContourNode *> IndexColumn; |
| |
| std::vector<IndexColumn> |
| m_columns; |
| std::vector<int> |
| m_identifiers; |
| |
| |
| |
| |
| |
| public: |
| IndexTable() {} |
| |
| IndexColumn *operator[](int i) { return &m_columns[i]; } |
| IndexColumn &columnOfId(int id) { return m_columns[m_identifiers[id]]; } |
| |
| |
| void build(ContourFamily &family); |
| void clear(); |
| |
| |
| IndexColumn::iterator find(ContourNode *index); |
| void merge(IndexColumn::iterator index1, IndexColumn::iterator index2); |
| void remove(IndexColumn::iterator index); |
| }; |
| |
| |
| |
| class Event { |
| public: |
| |
| |
| enum Type |
| { special, |
| edge, |
| vertex, |
| split_regenerate, |
| |
| split, |
| failure }; |
| |
| public: |
| double m_height; |
| double m_displacement; |
| ContourNode *m_generator; |
| ContourNode *m_coGenerator; |
| Type m_type; |
| unsigned int m_algoritmicTime; |
| |
| VectorizationContext *m_context; |
| |
| public: |
| |
| Event(ContourNode *generator, VectorizationContext *context); |
| |
| |
| inline void calculateEdgeEvent(); |
| inline void calculateSplitEvent(); |
| |
| |
| inline double splitDisplacementWith(ContourNode *plane); |
| inline bool tryRayEdgeCollisionWith(ContourNode *edge); |
| |
| |
| inline bool process(); |
| inline void processEdgeEvent(); |
| inline void processMaxEvent(); |
| inline void processSplitEvent(); |
| inline void processVertexEvent(); |
| inline void processSpecialEvent(); |
| |
| private: |
| inline bool testRayEdgeCollision(ContourNode *opposite, double &displacement, |
| double &height, double &side1, |
| double &side2); |
| }; |
| |
| |
| |
| struct EventGreater { |
| bool operator()(const Event &event1, const Event &event2) const { |
| return event1.m_height > event2.m_height || |
| (event1.m_height == event2.m_height && |
| event1.m_type > event2.m_type); |
| } |
| }; |
| |
| class Timeline final |
| : public std::priority_queue<Event, std::vector<Event>, EventGreater> { |
| public: |
| Timeline() {} |
| |
| |
| |
| |
| |
| void build(ContourFamily &polygons, VectorizationContext &context, |
| VectorizerCore *thisVectorizer); |
| }; |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| void IndexTable::build(ContourFamily &family) { |
| unsigned int i; |
| |
| m_columns.resize(family.size()); |
| m_identifiers.resize(family.size()); |
| |
| |
| for (i = 0; i < m_columns.size(); ++i) { |
| m_identifiers[i] = i; |
| m_columns[i].push_back(&family[i][0]); |
| |
| |
| family[i][0].setAttribute(ContourNode::HEAD); |
| } |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| inline IndexTable::IndexColumn::iterator IndexTable::find(ContourNode *sought) { |
| int indexId = m_identifiers[sought->m_ancestorContour]; |
| IndexColumn::iterator res; |
| |
| |
| for (; !sought->hasAttribute(ContourNode::HEAD); sought = sought->m_next) |
| ; |
| |
| |
| for (res = m_columns[indexId].begin(); (*res) != sought; ++res) |
| ; |
| |
| return res; |
| } |
| |
| |
| |
| |
| void IndexTable::merge(IndexColumn::iterator index1, |
| IndexColumn::iterator index2) { |
| IndexColumn::iterator current; |
| |
| int identifier1 = m_identifiers[(*index1)->m_ancestorContour], |
| identifier2 = m_identifiers[(*index2)->m_ancestorContour]; |
| |
| remove(index2); |
| |
| |
| if (!m_columns[identifier2].empty()) { |
| append<IndexTable::IndexColumn, IndexTable::IndexColumn::reverse_iterator>( |
| m_columns[identifier1], m_columns[identifier2]); |
| m_columns[identifier2].clear(); |
| } |
| |
| |
| for (unsigned int k = 0; k < m_columns.size(); ++k) { |
| if (m_identifiers[k] == identifier2) m_identifiers[k] = identifier1; |
| } |
| } |
| |
| |
| |
| |
| inline void IndexTable::remove(IndexColumn::iterator index) { |
| m_columns[m_identifiers[(*index)->m_ancestorContour]].erase(index); |
| } |
| |
| |
| |
| inline void IndexTable::clear() { m_columns.clear(), m_identifiers.clear(); } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| struct VectorizationContext { |
| VectorizerCoreGlobals *m_globals; |
| |
| |
| unsigned int m_totalNodes; |
| unsigned int m_contoursCount; |
| IndexTable m_activeTable; |
| SkeletonGraph *m_output; |
| double m_currentHeight; |
| Timeline m_timeline; |
| unsigned int m_algoritmicTime; |
| |
| |
| std::vector<ContourEdge> m_edgesHeap; |
| std::vector<ContourNode> m_nodesHeap; |
| unsigned int m_nodesHeapCount; |
| |
| |
| std::vector<ContourNode> m_linearNodesHeap; |
| std::vector<ContourEdge> m_linearEdgesHeap; |
| unsigned int m_linearNodesHeapCount; |
| |
| public: |
| VectorizationContext(VectorizerCoreGlobals *globals) : m_globals(globals) {} |
| |
| ContourNode *getNode() { return &m_nodesHeap[m_nodesHeapCount++]; } |
| ContourNode *getLinearNode() { |
| return &m_linearNodesHeap[m_linearNodesHeapCount]; |
| } |
| ContourEdge *getLinearEdge() { |
| return &m_linearEdgesHeap[m_linearNodesHeapCount++]; |
| } |
| |
| inline void addLinearNodeBefore(ContourNode *node); |
| inline void repairDegenerations( |
| const std::vector<ContourNode *> °enerates); |
| |
| inline void prepareGlobals(); |
| inline void prepareContours(ContourFamily &family); |
| |
| inline void newSkeletonLink(unsigned int cur, ContourNode *node); |
| }; |
| |
| |
| |
| |
| |
| inline void VectorizationContext::prepareGlobals() { |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| m_nodesHeap.resize(m_totalNodes + 3 * m_contoursCount - 6); |
| m_nodesHeapCount = 0; |
| |
| |
| m_currentHeight = 0; |
| m_algoritmicTime = 0; |
| |
| |
| m_activeTable.clear(); |
| } |
| |
| |
| |
| inline void VectorizationContext::newSkeletonLink(unsigned int cur, |
| ContourNode *node) { |
| if (node->hasAttribute(ContourNode::SK_NODE_DROPPED)) { |
| SkeletonArc arcCopy(node); |
| m_output->newLink(node->m_outputNode, cur, arcCopy); |
| |
| arcCopy.turn(); |
| m_output->newLink(cur, node->m_outputNode, arcCopy); |
| } |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| inline void VectorizationContext::addLinearNodeBefore(ContourNode *node) { |
| ContourNode *newNode = getLinearNode(); |
| ContourEdge *newEdge = getLinearEdge(); |
| |
| newNode->m_position = node->m_position; |
| |
| |
| if (node->m_direction.z < 0.1) |
| newEdge->m_direction = rotate270(node->m_edge->m_direction); |
| else |
| newEdge->m_direction = normalize(node->m_edge->m_direction + |
| node->m_prev->m_edge->m_direction); |
| |
| newNode->m_edge = newEdge; |
| |
| |
| newNode->m_prev = node->m_prev; |
| newNode->m_next = node; |
| node->m_prev->m_next = newNode; |
| node->m_prev = newNode; |
| |
| |
| node->buildNodeInfos(); |
| newNode->buildNodeInfos(); |
| |
| newNode->m_updateTime = 0; |
| newNode->m_ancestor = node->m_ancestor; |
| newNode->m_ancestorContour = node->m_ancestorContour; |
| |
| |
| |
| |
| node->m_notOpposites.push_back(newNode->m_edge); |
| node->m_notOpposites.push_back(newNode->m_prev->m_edge); |
| newNode->m_notOpposites.push_back(node->m_edge); |
| |
| |
| newNode->setAttribute(ContourNode::LINEAR_ADDED); |
| } |
| |
| |
| |
| inline void VectorizationContext::repairDegenerations( |
| const std::vector<ContourNode *> °enerates) { |
| unsigned int i; |
| |
| m_linearNodesHeap.resize(degenerates.size()); |
| m_linearEdgesHeap.resize(degenerates.size()); |
| m_linearNodesHeapCount = 0; |
| |
| for (i = 0; i < degenerates.size(); ++i) { |
| if (!degenerates[i]->hasAttribute(ContourNode::AMBIGUOUS_LEFT)) { |
| addLinearNodeBefore(degenerates[i]); |
| m_totalNodes++; |
| } |
| } |
| } |
| |
| |
| |
| |
| |
| |
| |
| inline void VectorizationContext::prepareContours(ContourFamily &family) { |
| std::vector<ContourNode *> degenerateNodes; |
| |
| |
| unsigned int i, j, k; |
| unsigned int current; |
| |
| m_contoursCount = family.size(); |
| m_totalNodes = 0; |
| for (i = 0; i < family.size(); ++i) { |
| for (j = 0, k = family[i].size() - 1; j < family[i].size(); k = j, ++j) { |
| family[i][k].m_next = &family[i][j]; |
| family[i][j].m_prev = &family[i][k]; |
| } |
| m_totalNodes += family[i].size(); |
| } |
| |
| |
| m_edgesHeap.resize(m_totalNodes); |
| current = 0; |
| for (i = 0; i < family.size(); ++i) { |
| for (j = 0, k = family[i].size() - 1; j < family[i].size(); k = j, ++j) { |
| m_edgesHeap[current].m_direction = normalize( |
| planeProjection(family[i][j].m_position - family[i][k].m_position)); |
| family[i][k].m_edge = &m_edgesHeap[current]; |
| current++; |
| } |
| } |
| |
| bool maxThicknessNotZero = m_globals->currConfig->m_maxThickness > 0.0; |
| |
| |
| for (i = 0; i < family.size(); ++i) { |
| for (j = 0; j < family[i].size(); ++j) { |
| family[i][j].buildNodeInfos(); |
| |
| family[i][j].m_updateTime = 0; |
| |
| family[i][j].m_ancestor = j; |
| family[i][j].m_ancestorContour = i; |
| |
| |
| if (family[i][j].m_concave && family[i][j].m_direction.z < 0.3) { |
| |
| degenerateNodes.push_back(&family[i][j]); |
| } |
| |
| |
| if (!family[i][j].m_concave && family[i][j].m_direction.z < 0.6 && |
| maxThicknessNotZero) { |
| family[i][j].setAttribute(ContourNode::SK_NODE_DROPPED); |
| family[i][j].m_outputNode = m_output->newNode(family[i][j].m_position); |
| } |
| |
| |
| if (family[i][j].hasAttribute(ContourNode::AMBIGUOUS_RIGHT)) |
| family[i][j].m_position += 0.02 * family[i][j].m_direction; |
| } |
| } |
| |
| |
| if (maxThicknessNotZero) repairDegenerations(degenerateNodes); |
| } |
| |
| |
| |
| |
| inline void ContourNode::buildNodeInfos(bool forceConvex) { |
| TPointD direction; |
| double parameter; |
| |
| |
| if (forceConvex) |
| m_concave = 0; |
| else if (cross(m_edge->m_direction, m_prev->m_edge->m_direction) < 0) { |
| m_concave = 1; |
| } else |
| m_concave = 0; |
| |
| |
| direction = m_edge->m_direction - m_prev->m_edge->m_direction; |
| parameter = norm(direction); |
| if (parameter > 0.01) { |
| direction = direction * (1 / parameter); |
| if (m_concave) direction = -direction; |
| } else |
| direction = rotate270(m_edge->m_direction); |
| |
| m_direction.x = direction.x; |
| m_direction.y = direction.y; |
| |
| |
| m_direction.z = cross(planeProjection(m_direction), m_edge->m_direction); |
| if (m_direction.z < 0) m_direction.z = 0; |
| |
| |
| m_AngularMomentum = cross(m_position, m_direction); |
| |
| if (m_concave) { |
| m_AuxiliaryMomentum1 = m_AuxiliaryMomentum2 = m_AngularMomentum; |
| } else { |
| m_AuxiliaryMomentum1 = |
| cross(m_position, |
| T3DPointD(m_edge->m_direction.y, -m_edge->m_direction.x, 1)); |
| m_AuxiliaryMomentum2 = |
| cross(m_position, T3DPointD(m_prev->m_edge->m_direction.y, |
| -m_prev->m_edge->m_direction.x, 1)); |
| } |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| class RandomizedNode { |
| public: |
| ContourNode *m_node; |
| int m_number; |
| |
| RandomizedNode() {} |
| RandomizedNode(ContourNode *node) : m_node(node), m_number(rand()) {} |
| |
| inline ContourNode *operator->(void) { return m_node; } |
| }; |
| |
| class RandomizedNodeLess { |
| public: |
| RandomizedNodeLess() {} |
| |
| inline bool operator()(RandomizedNode a, RandomizedNode b) { |
| return (a.m_number < b.m_number); |
| } |
| }; |
| |
| |
| |
| void Timeline::build(ContourFamily &polygons, VectorizationContext &context, |
| VectorizerCore *thisVectorizer) { |
| unsigned int i, j, current; |
| std::vector<RandomizedNode> nodesToBeTreated(context.m_totalNodes); |
| T3DPointD momentum, ray; |
| |
| |
| for (i = 0, current = 0; i < polygons.size(); ++i) |
| for (j = 0; j < polygons[i].size(); ++j) |
| nodesToBeTreated[current++] = RandomizedNode(&polygons[i][j]); |
| |
| |
| for (i = 0; i < context.m_linearNodesHeapCount; ++i) |
| nodesToBeTreated[current++] = RandomizedNode(&context.m_linearNodesHeap[i]); |
| |
| double maxThickness = context.m_globals->currConfig->m_maxThickness; |
| |
| |
| |
| for (i = 0; i < nodesToBeTreated.size(); ++i) { |
| |
| if (thisVectorizer->isCanceled()) break; |
| |
| Event currentEvent(nodesToBeTreated[i].m_node, &context); |
| |
| |
| if (!nodesToBeTreated[i].m_node->hasAttribute(ContourNode::LINEAR_ADDED)) |
| thisVectorizer->emitPartialDone(); |
| |
| if (currentEvent.m_type != Event::failure && |
| currentEvent.m_height < maxThickness) |
| |
| #ifdef _PREPROCESS |
| |
| if (currentEvent.m_type == Event::split) { |
| if (currentEvent.m_coGenerator->m_concave) { |
| ray = |
| T3DPointD(currentEvent.m_coGenerator->m_edge->m_direction.y, |
| -currentEvent.m_coGenerator->m_edge->m_direction.x, 1); |
| momentum = cross(currentEvent.m_coGenerator->m_position, ray); |
| |
| if (currentEvent.m_generator->m_direction * momentum + |
| ray * currentEvent.m_generator->m_AngularMomentum < |
| 0) { |
| timeline.push(currentEvent); |
| continue; |
| } |
| } |
| |
| if (currentEvent.m_coGenerator->m_next->m_concave) { |
| ray = |
| T3DPointD(currentEvent.m_coGenerator->m_edge->m_direction.y, |
| -currentEvent.m_coGenerator->m_edge->m_direction.x, 1); |
| momentum = cross(currentEvent.m_coGenerator->m_next->m_position, ray); |
| |
| if (currentEvent.m_generator->m_direction * momentum + |
| ray * currentEvent.m_generator->m_AngularMomentum > |
| 0) { |
| timeline.push(currentEvent); |
| continue; |
| } |
| } |
| |
| if (cross(currentEvent.m_generator->m_edge->m_direction, |
| currentEvent.m_coGenerator->m_edge->m_direction) > 0.02 && |
| cross(currentEvent.m_coGenerator->m_edge->m_direction, |
| currentEvent.m_generator->m_prev->m_edge->m_direction) > |
| 0.02) |
| { |
| |
| currentEvent.process(); |
| continue; |
| } |
| } |
| |
| #endif |
| |
| push(currentEvent); |
| } |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| Event::Event(ContourNode *generator, VectorizationContext *context) |
| : m_height(infinity) |
| , m_displacement(infinity) |
| , m_generator(generator) |
| , m_type(failure) |
| , m_algoritmicTime(context->m_algoritmicTime) |
| , m_context(context) { |
| if (generator->m_concave) |
| calculateSplitEvent(); |
| else |
| calculateEdgeEvent(); |
| } |
| |
| |
| |
| |
| |
| |
| |
| inline void Event::calculateEdgeEvent() { |
| struct locals { |
| static inline void buildDisplacements(ContourNode *edgeFirst, double &d1, |
| double &d2) { |
| ContourNode *edgeSecond = edgeFirst->m_next; |
| |
| |
| |
| |
| if ((edgeFirst->m_concave && edgeSecond->m_concave) || |
| edgeFirst->m_direction * edgeSecond->m_direction < -0.9) { |
| d1 = d2 = -1.0; |
| return; |
| } |
| |
| double det = edgeFirst->m_direction.y * edgeSecond->m_direction.x - |
| edgeFirst->m_direction.x * edgeSecond->m_direction.y; |
| |
| double cx = edgeSecond->m_position.x - edgeFirst->m_position.x, |
| cy = edgeSecond->m_position.y - edgeFirst->m_position.y; |
| |
| d1 = (edgeSecond->m_direction.x * cy - edgeSecond->m_direction.y * cx) / |
| det; |
| d2 = |
| (edgeFirst->m_direction.x * cy - edgeFirst->m_direction.y * cx) / det; |
| } |
| |
| static inline double height(ContourNode *node, double displacement) { |
| return node->m_position.z + displacement * node->m_direction.z; |
| } |
| }; |
| |
| double minHeight, minDisplacement; |
| bool positiveEdgeDispl; |
| |
| m_type = edge; |
| |
| |
| double firstDisplacement, prevDisplacement, nextDisplacement, |
| lastDisplacement; |
| |
| |
| |
| locals::buildDisplacements(m_generator, nextDisplacement, lastDisplacement); |
| locals::buildDisplacements(m_generator->m_prev, firstDisplacement, |
| prevDisplacement); |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| static const double minusTol = -0.03; |
| |
| bool prevDispPositive = (prevDisplacement > minusTol); |
| bool nextDispPositive = (nextDisplacement > minusTol); |
| |
| if (nextDispPositive) { |
| if (!prevDispPositive || nextDisplacement < prevDisplacement) { |
| m_coGenerator = m_generator; |
| minDisplacement = nextDisplacement; |
| minHeight = locals::height(m_coGenerator, nextDisplacement); |
| positiveEdgeDispl = (nextDispPositive && lastDisplacement > minusTol); |
| } else { |
| m_coGenerator = m_generator->m_prev; |
| minDisplacement = prevDisplacement; |
| minHeight = locals::height( |
| m_coGenerator, |
| firstDisplacement); |
| positiveEdgeDispl = |
| (prevDispPositive && |
| firstDisplacement > |
| minusTol); |
| } |
| } else if (prevDispPositive) { |
| m_coGenerator = m_generator->m_prev; |
| minDisplacement = prevDisplacement; |
| minHeight = locals::height(m_coGenerator, firstDisplacement); |
| positiveEdgeDispl = (prevDispPositive && firstDisplacement > minusTol); |
| } else { |
| m_type = failure; |
| return; |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| if (nextDispPositive && !m_generator->m_concave) { |
| if (m_generator->m_prev->m_concave && m_generator->m_next->m_concave && |
| fabs(nextDisplacement - prevDisplacement) < |
| 0.1) |
| |
| { |
| |
| ContourNode *prevRay = m_generator->m_prev, |
| *nextRay = m_generator->m_next; |
| |
| double side = prevRay->m_direction * nextRay->m_AngularMomentum + |
| nextRay->m_direction * prevRay->m_AngularMomentum; |
| |
| |
| |
| if (fabs(side) < |
| 0.03 * norm(cross(prevRay->m_direction, nextRay->m_direction))) |
| m_type = special, m_coGenerator = m_generator; |
| } else if (fabs(nextDisplacement - prevDisplacement) < 0.01) { |
| |
| |
| m_coGenerator = |
| m_generator->m_next->m_concave ? m_generator : m_generator->m_prev; |
| } |
| } |
| |
| |
| if (positiveEdgeDispl |
| || |
| minHeight > m_context->m_currentHeight - |
| 0.01) |
| m_height = minHeight, |
| m_displacement = |
| minDisplacement; |
| else |
| m_type = failure; |
| } |
| |
| |
| |
| inline void Event::calculateSplitEvent() { |
| unsigned int i; |
| bool forceFirst; |
| ContourNode *opposite, *first, *last; |
| std::list<ContourNode *>::iterator currentContour; |
| |
| |
| for (i = 0; i < m_generator->m_notOpposites.size(); ++i) |
| m_generator->m_notOpposites[i]->setAttribute(ContourEdge::NOT_OPPOSITE); |
| |
| |
| calculateEdgeEvent(); |
| |
| |
| first = |
| m_generator->m_next->m_next; |
| last = m_generator->m_prev->m_prev; |
| for (opposite = first; opposite != last; opposite = opposite->m_next) { |
| if (!opposite->m_edge->hasAttribute(ContourEdge::NOT_OPPOSITE)) |
| tryRayEdgeCollisionWith(opposite); |
| } |
| |
| IndexTable &activeTable = m_context->m_activeTable; |
| |
| |
| for (i = 0; i < activeTable.m_columns.size(); ++i) { |
| for (currentContour = activeTable[i]->begin(); |
| currentContour != activeTable[i]->end(); currentContour++) { |
| |
| if (activeTable.m_identifiers[(*currentContour)->m_ancestorContour] != |
| activeTable.m_identifiers[m_generator->m_ancestorContour]) { |
| first = *currentContour; |
| for (opposite = first, forceFirst = 1; |
| |
| |
| !opposite->hasAttribute(ContourNode::HEAD) |
| || (forceFirst ? forceFirst = 0, 1 : 0); |
| opposite = opposite->m_next) { |
| if (!opposite->m_edge->hasAttribute(ContourEdge::NOT_OPPOSITE)) |
| tryRayEdgeCollisionWith(opposite); |
| } |
| } |
| } |
| } |
| |
| |
| for (i = 0; i < m_generator->m_notOpposites.size(); ++i) |
| m_generator->m_notOpposites[i]->clearAttribute(ContourEdge::NOT_OPPOSITE); |
| } |
| |
| |
| |
| inline bool Event::testRayEdgeCollision(ContourNode *opposite, |
| double &displacement, double &height, |
| double &side1, double &side2) { |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| T3DPointD firstSlabGuard = |
| opposite->m_concave ? opposite->m_direction |
| : T3DPointD(opposite->m_edge->m_direction.y, |
| -opposite->m_edge->m_direction.x, 1); |
| T3DPointD lastSlabGuard = |
| opposite->m_next->m_concave |
| ? opposite->m_next->m_direction |
| : T3DPointD(opposite->m_edge->m_direction.y, |
| -opposite->m_edge->m_direction.x, 1); |
| |
| T3DPointD roofSlabOrthogonal(-opposite->m_edge->m_direction.y, |
| opposite->m_edge->m_direction.x, 1); |
| |
| if (roofSlabOrthogonal * (opposite->m_position - m_generator->m_position) > |
| -0.01 |
| |
| |
| && |
| planeProjection(roofSlabOrthogonal) * |
| planeProjection(m_generator->m_direction) > |
| 0 |
| && |
| (side1 = m_generator->m_direction * |
| opposite->m_AuxiliaryMomentum1 + |
| |
| firstSlabGuard * m_generator->m_AngularMomentum) > -0.01 |
| && |
| (side2 = m_generator->m_direction * |
| opposite->m_next->m_AuxiliaryMomentum2 + |
| |
| |
| |
| lastSlabGuard * m_generator->m_AngularMomentum) < 0.01 |
| && |
| (m_generator->m_ancestorContour != |
| opposite->m_ancestorContour |
| |
| || m_generator->m_ancestor != opposite->m_ancestor)) |
| { |
| displacement = splitDisplacementWith(opposite); |
| |
| |
| |
| |
| if (displacement > -0.01 && displacement < 0.01) { |
| T3DPointD slabLeftOrthogonal(-opposite->m_edge->m_direction.y, |
| opposite->m_edge->m_direction.x, 1); |
| double check1 = |
| (m_generator->m_position - opposite->m_position) * |
| normalize(cross(opposite->m_direction, slabLeftOrthogonal)); |
| |
| double check2 = |
| (m_generator->m_position - opposite->m_next->m_position) * |
| normalize(cross(opposite->m_next->m_direction, slabLeftOrthogonal)); |
| |
| if (check1 > 0.02 || check2 < -0.02) return false; |
| } |
| |
| |
| |
| |
| if (displacement > -0.01 && |
| displacement < m_displacement + 0.01 |
| && |
| (height = m_generator->m_position.z + |
| displacement * m_generator->m_direction.z) > |
| m_context->m_currentHeight - 0.01) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| |
| |
| inline bool Event::tryRayEdgeCollisionWith(ContourNode *opposite) { |
| ContourNode *newCoGenerator; |
| Type type; |
| |
| double displacement, height, side1, side2; |
| |
| if (testRayEdgeCollision(opposite, displacement, height, side1, side2)) { |
| type = split_regenerate; |
| newCoGenerator = opposite; |
| |
| |
| double firstSide = |
| opposite->m_concave |
| ? side1 |
| : m_generator->m_direction * opposite->m_AngularMomentum + |
| opposite->m_direction * m_generator->m_AngularMomentum, |
| secondSide = opposite->m_next->m_concave |
| ? side2 |
| : m_generator->m_direction * |
| opposite->m_next->m_AngularMomentum + |
| opposite->m_next->m_direction * |
| m_generator->m_AngularMomentum; |
| |
| if (firstSide > -0.01 && secondSide < 0.01) { |
| double displacement_, height_; |
| |
| if (firstSide < 0.01) { |
| |
| if (opposite->m_concave || |
| testRayEdgeCollision(opposite->m_prev, displacement_, height_, |
| side1, side2)) |
| type = vertex; |
| } else if (secondSide > -0.01) { |
| |
| if (opposite->m_next->m_concave || |
| testRayEdgeCollision(opposite->m_next, displacement_, height_, |
| side1, side2)) { |
| type = vertex; |
| newCoGenerator = opposite->m_next; |
| } |
| } else |
| type = split; |
| } |
| |
| if (type == split_regenerate && |
| height <= |
| m_context |
| ->m_currentHeight) |
| return false; |
| |
| |
| |
| |
| |
| if (m_type != edge && fabs(displacement - m_displacement) < 0.01 && |
| angleLess(m_coGenerator->m_edge->m_direction, |
| newCoGenerator->m_edge->m_direction, |
| m_generator->m_edge->m_direction)) |
| return false; |
| |
| |
| |
| |
| |
| m_type = type, m_coGenerator = newCoGenerator; |
| m_displacement = displacement, m_height = height; |
| |
| return true; |
| } |
| |
| return false; |
| } |
| |
| |
| |
| inline double Event::splitDisplacementWith(ContourNode *slab) { |
| TPointD slabLeftOrthogonal(-slab->m_edge->m_direction.y, |
| slab->m_edge->m_direction.x); |
| double denom = m_generator->m_direction.z + |
| slabLeftOrthogonal * TPointD(m_generator->m_direction.x, |
| m_generator->m_direction.y); |
| |
| if (denom < 0.01) |
| return -1; |
| |
| TPointD difference = |
| planeProjection(slab->m_position - m_generator->m_position); |
| |
| return (slabLeftOrthogonal * difference + slab->m_position.z - |
| m_generator->m_position.z) / |
| denom; |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| inline bool Event::process() { |
| Timeline &timeline = m_context->m_timeline; |
| unsigned int &algoritmicTime = m_context->m_algoritmicTime; |
| |
| if (!m_generator->hasAttribute(ContourNode::ELIMINATED)) { |
| switch (m_type) { |
| case special: |
| assert(!m_coGenerator->hasAttribute(ContourNode::ELIMINATED)); |
| |
| if (m_coGenerator->m_prev->hasAttribute( |
| ContourNode::ELIMINATED) || |
| |
| m_coGenerator->m_next->hasAttribute( |
| ContourNode::ELIMINATED) || |
| |
| m_algoritmicTime < m_coGenerator->m_prev->m_updateTime || |
| m_algoritmicTime < m_coGenerator->m_next->m_updateTime) { |
| |
| Event newEvent(m_generator, m_context); |
| if (newEvent.m_type != failure) timeline.push(newEvent); |
| return false; |
| } |
| |
| |
| algoritmicTime++; |
| processSpecialEvent(); |
| |
| break; |
| |
| case edge: |
| if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) || |
| m_algoritmicTime < m_coGenerator->m_next->m_updateTime) { |
| |
| Event newEvent(m_generator, m_context); |
| if (newEvent.m_type != failure) timeline.push(newEvent); |
| return false; |
| } |
| |
| |
| |
| if ((m_coGenerator->m_direction.z == 0.0 && |
| m_coGenerator != m_generator) || |
| (m_coGenerator->m_next->m_direction.z == 0.0 && |
| m_coGenerator == m_generator)) |
| return false; |
| |
| |
| algoritmicTime++; |
| if (m_generator->m_next->m_next == m_generator->m_prev) |
| processMaxEvent(); |
| else |
| processEdgeEvent(); |
| |
| break; |
| |
| case vertex: |
| if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED)) { |
| |
| Event newEvent(m_generator, m_context); |
| if (newEvent.m_type != failure) timeline.push(newEvent); |
| return false; |
| } |
| |
| |
| |
| |
| |
| if (m_coGenerator == |
| m_generator->m_next |
| ->m_next |
| || |
| m_coGenerator == |
| m_generator->m_prev |
| ->m_prev) |
| return false; |
| |
| |
| algoritmicTime++; |
| processVertexEvent(); |
| |
| break; |
| |
| case split_regenerate: |
| if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) || |
| (m_algoritmicTime < m_coGenerator->m_next->m_updateTime)) { |
| |
| Event newEvent(m_generator, m_context); |
| if (newEvent.m_type != failure) timeline.push(newEvent); |
| return false; |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| case split: |
| if (m_coGenerator->hasAttribute(ContourNode::ELIMINATED) || |
| (m_algoritmicTime < m_coGenerator->m_next->m_updateTime)) { |
| |
| Event newEvent(m_generator, m_context); |
| if (newEvent.m_type != failure) timeline.push(newEvent); |
| return false; |
| } |
| |
| |
| if (m_coGenerator != m_generator->m_next && |
| m_coGenerator != |
| m_generator->m_prev |
| ->m_prev) |
| { |
| algoritmicTime++; |
| processSplitEvent(); |
| } |
| |
| break; |
| } |
| } |
| |
| return true; |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| inline void Event::processEdgeEvent() { |
| ContourNode *newNode; |
| T3DPointD position(m_generator->m_position + |
| m_displacement * m_generator->m_direction); |
| |
| |
| m_coGenerator->setAttribute(ContourNode::ELIMINATED); |
| m_coGenerator->m_next->setAttribute(ContourNode::ELIMINATED); |
| |
| |
| newNode = m_context->getNode(); |
| newNode->m_position = position; |
| |
| newNode->m_next = m_coGenerator->m_next->m_next; |
| m_coGenerator->m_next->m_next->m_prev = newNode; |
| |
| newNode->m_prev = m_coGenerator->m_prev; |
| m_coGenerator->m_prev->m_next = newNode; |
| |
| |
| newNode->m_position = |
| m_generator->m_position + m_displacement * m_generator->m_direction; |
| newNode->m_edge = m_coGenerator->m_next->m_edge; |
| |
| newNode->buildNodeInfos(1); |
| |
| newNode->m_ancestor = m_coGenerator->m_next->m_ancestor; |
| newNode->m_ancestorContour = m_coGenerator->m_next->m_ancestorContour; |
| newNode->m_updateTime = m_context->m_algoritmicTime; |
| |
| |
| |
| if (newNode->m_direction.z < 0.7 || |
| m_coGenerator->hasAttribute(ContourNode::SK_NODE_DROPPED) || |
| m_coGenerator->m_next->hasAttribute(ContourNode::SK_NODE_DROPPED)) { |
| newNode->setAttribute(ContourNode::SK_NODE_DROPPED); |
| newNode->m_outputNode = m_context->m_output->newNode(position); |
| m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator); |
| m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_next); |
| } |
| |
| |
| |
| if (m_coGenerator->hasAttribute(ContourNode::HEAD) || |
| m_coGenerator->m_next->hasAttribute(ContourNode::HEAD)) { |
| std::list<ContourNode *>::iterator it; |
| std::list<ContourNode *> &column = |
| m_context->m_activeTable.columnOfId(m_generator->m_ancestorContour); |
| |
| for (it = column.begin(); !(*it)->hasAttribute(ContourNode::ELIMINATED); |
| ++it) |
| ; |
| |
| |
| |
| *it = newNode, newNode->setAttribute(ContourNode::HEAD); |
| } |
| |
| |
| Event newEvent(newNode, m_context); |
| if (newEvent.m_type != Event::failure) m_context->m_timeline.push(newEvent); |
| } |
| |
| |
| |
| |
| |
| inline void Event::processMaxEvent() { |
| T3DPointD position(m_generator->m_position + |
| m_displacement * m_generator->m_direction); |
| |
| unsigned int outputNode = m_context->m_output->newNode(position); |
| |
| m_context->newSkeletonLink(outputNode, m_generator); |
| m_context->newSkeletonLink(outputNode, m_generator->m_prev); |
| m_context->newSkeletonLink(outputNode, m_generator->m_next); |
| |
| |
| std::list<ContourNode *>::iterator eventVertexIndex = |
| m_context->m_activeTable.find(m_generator); |
| |
| m_context->m_activeTable.remove(eventVertexIndex); |
| |
| m_generator->setAttribute(ContourNode::ELIMINATED); |
| m_generator->m_prev->setAttribute(ContourNode::ELIMINATED); |
| m_generator->m_next->setAttribute(ContourNode::ELIMINATED); |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| inline void Event::processSplitEvent() { |
| ContourNode *newLeftNode, |
| *newRightNode; |
| T3DPointD position(m_generator->m_position + |
| m_displacement * m_generator->m_direction); |
| IndexTable &activeTable = m_context->m_activeTable; |
| unsigned int &algoritmicTime = m_context->m_algoritmicTime; |
| |
| |
| std::list<ContourNode *>::iterator genContour, coGenContour; |
| genContour = activeTable.find(m_generator); |
| |
| if (activeTable.m_identifiers[m_generator->m_ancestorContour] != |
| activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) { |
| |
| coGenContour = activeTable.find(m_coGenerator); |
| } |
| |
| |
| m_generator->setAttribute(ContourNode::ELIMINATED); |
| |
| |
| newLeftNode = m_context->getNode(); |
| newRightNode = m_context->getNode(); |
| newLeftNode->m_position = newRightNode->m_position = position; |
| |
| |
| m_coGenerator->m_next->m_prev = newRightNode; |
| newRightNode->m_next = m_coGenerator->m_next; |
| m_generator->m_prev->m_next = newRightNode; |
| newRightNode->m_prev = m_generator->m_prev; |
| |
| |
| m_coGenerator->m_next = newLeftNode; |
| newLeftNode->m_prev = m_coGenerator; |
| m_generator->m_next->m_prev = newLeftNode; |
| newLeftNode->m_next = m_generator->m_next; |
| |
| |
| newLeftNode->m_edge = m_generator->m_edge; |
| newRightNode->m_edge = m_coGenerator->m_edge; |
| |
| newLeftNode->m_ancestor = m_generator->m_ancestor; |
| newLeftNode->m_ancestorContour = m_generator->m_ancestorContour; |
| newRightNode->m_ancestor = m_coGenerator->m_ancestor; |
| newRightNode->m_ancestorContour = m_coGenerator->m_ancestorContour; |
| |
| |
| newLeftNode->buildNodeInfos(1); |
| newRightNode->buildNodeInfos(1); |
| |
| newLeftNode->m_updateTime = newRightNode->m_updateTime = algoritmicTime; |
| |
| |
| newLeftNode->setAttribute(ContourNode::SK_NODE_DROPPED); |
| newRightNode->setAttribute(ContourNode::SK_NODE_DROPPED); |
| newLeftNode->m_outputNode = m_context->m_output->newNode(position); |
| newRightNode->m_outputNode = newLeftNode->m_outputNode; |
| m_context->newSkeletonLink(newLeftNode->m_outputNode, m_generator); |
| |
| |
| if (activeTable.m_identifiers[m_generator->m_ancestorContour] != |
| activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) { |
| |
| |
| (*genContour)->clearAttribute(ContourNode::HEAD); |
| activeTable.merge(coGenContour, genContour); |
| } else { |
| |
| (*genContour)->clearAttribute(ContourNode::HEAD); |
| *genContour = newLeftNode; |
| |
| newLeftNode->setAttribute(ContourNode::HEAD); |
| newRightNode->setAttribute(ContourNode::HEAD); |
| |
| activeTable.columnOfId(m_generator->m_ancestorContour) |
| .push_back(newRightNode); |
| } |
| |
| |
| newRightNode->m_position += 0.02 * newRightNode->m_direction; |
| |
| |
| Event newLeftEvent(newLeftNode, m_context); |
| if (newLeftEvent.m_type != Event::failure) |
| m_context->m_timeline.push(newLeftEvent); |
| |
| Event newRightEvent(newRightNode, m_context); |
| if (newRightEvent.m_type != Event::failure) |
| m_context->m_timeline.push(newRightEvent); |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| inline void Event::processVertexEvent() { |
| ContourNode *newLeftNode, |
| *newRightNode; |
| T3DPointD position(m_generator->m_position + |
| m_displacement * m_generator->m_direction); |
| IndexTable &activeTable = m_context->m_activeTable; |
| unsigned int &algoritmicTime = m_context->m_algoritmicTime; |
| |
| |
| std::list<ContourNode *>::iterator genContour, coGenContour; |
| genContour = activeTable.find(m_generator); |
| |
| if (activeTable.m_identifiers[m_generator->m_ancestorContour] != |
| activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) { |
| |
| coGenContour = activeTable.find(m_coGenerator); |
| } |
| |
| |
| m_generator->setAttribute(ContourNode::ELIMINATED); |
| m_coGenerator->setAttribute(ContourNode::ELIMINATED); |
| |
| |
| newLeftNode = m_context->getNode(); |
| newRightNode = m_context->getNode(); |
| newLeftNode->m_position = newRightNode->m_position = position; |
| |
| |
| m_coGenerator->m_next->m_prev = newRightNode; |
| newRightNode->m_next = m_coGenerator->m_next; |
| m_generator->m_prev->m_next = newRightNode; |
| newRightNode->m_prev = m_generator->m_prev; |
| |
| |
| m_coGenerator->m_prev->m_next = newLeftNode; |
| newLeftNode->m_prev = m_coGenerator->m_prev; |
| m_generator->m_next->m_prev = newLeftNode; |
| newLeftNode->m_next = m_generator->m_next; |
| |
| |
| newLeftNode->m_edge = m_generator->m_edge; |
| newRightNode->m_edge = m_coGenerator->m_edge; |
| |
| newLeftNode->m_ancestor = m_generator->m_ancestor; |
| newLeftNode->m_ancestorContour = m_generator->m_ancestorContour; |
| newRightNode->m_ancestor = m_coGenerator->m_ancestor; |
| newRightNode->m_ancestorContour = m_coGenerator->m_ancestorContour; |
| |
| |
| newLeftNode->buildNodeInfos(); |
| newRightNode->buildNodeInfos(); |
| |
| newLeftNode->m_updateTime = newRightNode->m_updateTime = algoritmicTime; |
| |
| |
| newLeftNode->setAttribute(ContourNode::SK_NODE_DROPPED); |
| newRightNode->setAttribute(ContourNode::SK_NODE_DROPPED); |
| newLeftNode->m_outputNode = m_context->m_output->newNode(position); |
| newRightNode->m_outputNode = newLeftNode->m_outputNode; |
| m_context->newSkeletonLink(newLeftNode->m_outputNode, m_generator); |
| m_context->newSkeletonLink(newLeftNode->m_outputNode, m_coGenerator); |
| |
| |
| if (activeTable.m_identifiers[m_generator->m_ancestorContour] != |
| activeTable.m_identifiers[m_coGenerator->m_ancestorContour]) { |
| |
| (*coGenContour)->clearAttribute(ContourNode::HEAD); |
| activeTable.merge(genContour, coGenContour); |
| |
| |
| if (m_generator->hasAttribute(ContourNode::HEAD)) { |
| newLeftNode->setAttribute(ContourNode::HEAD); |
| *genContour = newLeftNode; |
| } |
| |
| } else { |
| |
| (*genContour)->clearAttribute(ContourNode::HEAD); |
| *genContour = newLeftNode; |
| |
| newLeftNode->setAttribute(ContourNode::HEAD); |
| newRightNode->setAttribute(ContourNode::HEAD); |
| |
| activeTable.columnOfId(m_generator->m_ancestorContour) |
| .push_back(newRightNode); |
| } |
| |
| |
| |
| if (newLeftNode->m_concave) { |
| newLeftNode->m_notOpposites = m_generator->m_notOpposites; |
| append<std::vector<ContourEdge *>, |
| std::vector<ContourEdge *>::reverse_iterator>( |
| newLeftNode->m_notOpposites, m_coGenerator->m_notOpposites); |
| |
| newLeftNode->m_notOpposites.push_back(newRightNode->m_edge); |
| newLeftNode->m_notOpposites.push_back(newRightNode->m_prev->m_edge); |
| } else if (newRightNode->m_concave) { |
| newRightNode->m_notOpposites = m_generator->m_notOpposites; |
| append<std::vector<ContourEdge *>, |
| std::vector<ContourEdge *>::reverse_iterator>( |
| newRightNode->m_notOpposites, m_coGenerator->m_notOpposites); |
| |
| newRightNode->m_notOpposites.push_back(newLeftNode->m_edge); |
| newRightNode->m_notOpposites.push_back(newLeftNode->m_prev->m_edge); |
| } |
| |
| |
| |
| |
| newRightNode->m_position += 0.02 * newRightNode->m_direction; |
| |
| |
| Event newLeftEvent(newLeftNode, m_context); |
| if (newLeftEvent.m_type != Event::failure) |
| m_context->m_timeline.push(newLeftEvent); |
| |
| Event newRightEvent(newRightNode, m_context); |
| if (newRightEvent.m_type != Event::failure) |
| m_context->m_timeline.push(newRightEvent); |
| } |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| inline void Event::processSpecialEvent() { |
| ContourNode *newNode; |
| T3DPointD position(m_generator->m_position + |
| m_displacement * m_generator->m_direction); |
| |
| m_coGenerator->setAttribute(ContourNode::ELIMINATED); |
| m_coGenerator->m_prev->setAttribute(ContourNode::ELIMINATED); |
| m_coGenerator->m_next->setAttribute(ContourNode::ELIMINATED); |
| |
| |
| newNode = m_context->getNode(); |
| newNode->m_position = position; |
| |
| m_coGenerator->m_prev->m_prev->m_next = newNode; |
| newNode->m_prev = m_coGenerator->m_prev->m_prev; |
| |
| m_coGenerator->m_next->m_next->m_prev = newNode; |
| newNode->m_next = m_coGenerator->m_next->m_next; |
| |
| |
| newNode->m_edge = m_coGenerator->m_next->m_edge; |
| |
| newNode->m_ancestor = m_coGenerator->m_next->m_ancestor; |
| newNode->m_ancestorContour = m_coGenerator->m_next->m_ancestorContour; |
| |
| |
| newNode->buildNodeInfos(); |
| newNode->m_updateTime = m_context->m_algoritmicTime; |
| |
| |
| newNode->setAttribute(ContourNode::SK_NODE_DROPPED); |
| newNode->m_outputNode = m_context->m_output->newNode(position); |
| m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_prev); |
| m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator); |
| m_context->newSkeletonLink(newNode->m_outputNode, m_coGenerator->m_next); |
| |
| |
| |
| if (m_coGenerator->hasAttribute(ContourNode::HEAD) || |
| m_coGenerator->m_next->hasAttribute(ContourNode::HEAD) || |
| m_coGenerator->m_prev->hasAttribute(ContourNode::HEAD)) { |
| std::list<ContourNode *>::iterator it; |
| std::list<ContourNode *> &column = |
| m_context->m_activeTable.columnOfId(m_generator->m_ancestorContour); |
| |
| for (it = column.begin(); !(*it)->hasAttribute(ContourNode::ELIMINATED); |
| ++it) |
| ; |
| |
| |
| |
| |
| *it = newNode, newNode->setAttribute(ContourNode::HEAD); |
| } |
| |
| |
| Event newEvent(newNode, m_context); |
| if (newEvent.m_type != Event::failure) m_context->m_timeline.push(newEvent); |
| } |
| |
| |
| |
| |
| |
| |
| |
| static SkeletonGraph *skeletonize(ContourFamily ®ionContours, |
| VectorizationContext &context, |
| VectorizerCore *thisVectorizer) { |
| SkeletonGraph *output = context.m_output = new SkeletonGraph; |
| |
| context.prepareContours(regionContours); |
| context.prepareGlobals(); |
| |
| IndexTable &activeTable = context.m_activeTable; |
| activeTable.build(regionContours); |
| |
| double maxThickness = context.m_globals->currConfig->m_maxThickness; |
| |
| if (maxThickness > 0.0) |
| { |
| Timeline &timeline = context.m_timeline; |
| timeline.build(regionContours, context, thisVectorizer); |
| |
| #ifdef _SSDEBUG |
| SSDebugger debugger(context); |
| |
| bool spawnDebugger = false; |
| if (timeline.size() > 1000) { |
| debugger.m_height = context.m_currentHeight; |
| |
| debugger.show(); |
| debugger.raise(); |
| |
| debugger.repaint(); |
| debugger.loop(); |
| |
| spawnDebugger = true; |
| } |
| #endif |
| |
| if (thisVectorizer->isCanceled()) { |
| |
| while (!timeline.empty()) timeline.pop(); |
| |
| context.m_nodesHeap.clear(); |
| context.m_edgesHeap.clear(); |
| |
| context.m_linearNodesHeap.clear(); |
| context.m_linearEdgesHeap.clear(); |
| |
| return output; |
| } |
| |
| |
| while (!timeline.empty()) { |
| Event currentEvent = timeline.top(); |
| timeline.pop(); |
| |
| |
| if (currentEvent.m_height >= maxThickness) break; |
| |
| |
| #ifdef _SSDEBUG |
| |
| if (spawnDebugger && debugger.isOnScreen(currentEvent.m_generator)) { |
| debugger.m_height = currentEvent.m_height; |
| |
| debugger.repaint(); |
| debugger.loop(); |
| |
| if (currentEvent.m_type == Event::split || |
| currentEvent.m_type == Event::vertex) |
| currentEvent.tryRayEdgeCollisionWith(currentEvent.m_coGenerator); |
| |
| if (currentEvent.m_type == Event::edge) |
| currentEvent.calculateEdgeEvent(); |
| } |
| |
| #endif |
| |
| |
| currentEvent.process(); |
| context.m_currentHeight = currentEvent.m_height; |
| } |
| |
| |
| while (!timeline.empty()) timeline.pop(); |
| |
| #ifdef _SSDEBUG |
| if (spawnDebugger) { |
| debugger.m_height = context.m_currentHeight; |
| |
| debugger.repaint(); |
| debugger.loop(); |
| } |
| #endif |
| } |
| |
| |
| |
| unsigned int i, l, n; |
| IndexTable::IndexColumn::iterator j; |
| ContourNode *k; |
| |
| for (i = 0; i < regionContours.size(); ++i) |
| for (j = activeTable[i]->begin(); j != activeTable[i]->end(); ++j) { |
| unsigned int count = 0; |
| unsigned int addedNode; |
| for (k = *j; !k->hasAttribute(ContourNode::HEAD) || !count; |
| k = k->m_next) { |
| addedNode = output->newNode( |
| k->m_position + |
| k->m_direction * |
| ((maxThickness - k->m_position.z) / |
| (k->m_direction.z > 0.01 ? k->m_direction.z : 1))); |
| context.newSkeletonLink(addedNode, k); |
| |
| ++count; |
| } |
| |
| n = output->getNodesCount(); |
| |
| SkeletonArc arcCopy; |
| SkeletonArc arcCopyRev; |
| arcCopy.setAttribute(SkeletonArc::SS_OUTLINE); |
| arcCopyRev.setAttribute(SkeletonArc::SS_OUTLINE_REVERSED); |
| for (l = 1; l < count; ++l) { |
| output->newLink(n - l, n - l - 1, arcCopyRev); |
| output->newLink(n - l - 1, n - l, arcCopy); |
| } |
| output->newLink(n - l, n - 1, arcCopyRev); |
| output->newLink(n - 1, n - l, arcCopy); |
| } |
| |
| context.m_nodesHeap.clear(); |
| context.m_edgesHeap.clear(); |
| |
| context.m_linearNodesHeap.clear(); |
| context.m_linearEdgesHeap.clear(); |
| |
| return output; |
| } |
| |
| |
| |
| SkeletonList *skeletonize(Contours &contours, VectorizerCore *thisVectorizer, |
| VectorizerCoreGlobals &g) { |
| VectorizationContext context(&g); |
| |
| SkeletonList *res = new SkeletonList; |
| unsigned int i, j; |
| |
| |
| unsigned int overallNodes = 0; |
| for (i = 0; i < contours.size(); ++i) |
| for (j = 0; j < contours[i].size(); ++j) |
| overallNodes += contours[i][j].size(); |
| |
| thisVectorizer->setOverallPartials(overallNodes); |
| |
| for (i = 0; i < contours.size(); ++i) { |
| res->push_back(skeletonize(contours[i], context, thisVectorizer)); |
| |
| if (thisVectorizer->isCanceled()) break; |
| } |
| |
| return res; |
| } |
| |
| |
| |
| |
| |
| |
| |
| #ifdef _SSDEBUG |
| |
| SSDebugger::SSDebugger(VectorizationContext &context) |
| : m_context(context) |
| , m_scale(1.0) |
| , m_loop(this) |
| , m_transform(1, 0, 0, -1, 0, height()) { |
| setMouseTracking(true); |
| } |
| |
| |
| |
| inline TPointD SSDebugger::updated(ContourNode *node) { |
| #ifndef _PREPROCESS |
| #ifdef _UPDATE |
| if (node->m_direction.z > 1e-4) { |
| return planeProjection( |
| node->m_position + |
| ((m_height - node->m_position.z) / node->m_direction.z) * |
| node->m_direction); |
| } else |
| return planeProjection(node->m_position); |
| |
| #endif |
| #endif |
| |
| return planeProjection(node->m_position); |
| } |
| |
| |
| |
| #define line(a, b) p.drawLine(QLineF((a).x, (a).y, (b).x, (b).y)); |
| |
| |
| |
| void SSDebugger::paintEvent(QPaintEvent *) { |
| QPainter p(this); |
| p.setTransform(m_transform); |
| |
| |
| { |
| const SkeletonGraph &skeleton = *m_context.m_output; |
| |
| p.setPen(Qt::blue); |
| |
| int n, nCount = skeleton.getNodesCount(); |
| for (n = 0; n != nCount; ++n) { |
| const SkeletonGraph::Node &node = skeleton.getNode(n); |
| |
| int l, lCount = node.getLinksCount(); |
| for (l = 0; l != lCount; ++l) |
| line(*node, *skeleton.getNode(node.getLink(l).getNext())); |
| } |
| } |
| |
| |
| |
| |
| IndexTable &activeTable = m_context.m_activeTable; |
| |
| unsigned int i; |
| ContourNode *first, *last, *currNode; |
| std::list<ContourNode *>::iterator currentContour; |
| |
| for (i = 0; i < activeTable.m_columns.size(); ++i) { |
| for (currentContour = activeTable[i]->begin(); |
| currentContour != activeTable[i]->end(); currentContour++) { |
| |
| p.setPen(Qt::black); |
| last = first = *currentContour; |
| first = first->m_next; |
| |
| line(updated(last), updated(first)); |
| for (currNode = first; !currNode->hasAttribute(ContourNode::HEAD); |
| currNode = currNode->m_next) { |
| |
| line(updated(currNode), updated(currNode->m_next)); |
| } |
| |
| |
| p.setPen(Qt::red); |
| last = first = *currentContour; |
| first = first->m_next; |
| line(updated(last), updated(last) + planeProjection(last->m_direction)); |
| for (currNode = first; !currNode->hasAttribute(ContourNode::HEAD); |
| currNode = currNode->m_next) |
| line(updated(currNode), |
| updated(currNode) + planeProjection(currNode->m_direction)); |
| |
| |
| p.setPen(Qt::green); |
| last = first = *currentContour; |
| first = first->m_next; |
| line(updated(last), updated(last) + last->m_edge->m_direction); |
| for (currNode = first; !currNode->hasAttribute(ContourNode::HEAD); |
| currNode = currNode->m_next) |
| line(updated(currNode), |
| updated(currNode) + currNode->m_edge->m_direction); |
| } |
| } |
| |
| |
| { |
| p.setPen(Qt::red); |
| p.setTransform(QTransform()); |
| |
| const QPointF &worldPos = winToWorldF(m_pos.x(), m_pos.y()); |
| |
| p.drawText(rect().bottomLeft(), QString("WinPos: %1 %2 WorldPos: %3 %4") |
| .arg(m_pos.x()) |
| .arg(m_pos.y()) |
| .arg(worldPos.x()) |
| .arg(worldPos.y())); |
| } |
| } |
| |
| |
| |
| void SSDebugger::keyPressEvent(QKeyEvent *event) { m_loop.exit(); } |
| |
| |
| |
| void SSDebugger::mouseMoveEvent(QMouseEvent *event) { |
| m_pos = event->pos(); |
| |
| if (event->buttons() == Qt::MiddleButton) { |
| m_transform.translate((event->x() - m_pressPos.x()) / m_scale, |
| (m_pressPos.y() - event->y()) / m_scale); |
| m_pressPos = event->pos(); |
| } |
| |
| update(); |
| } |
| |
| |
| |
| void SSDebugger::mousePressEvent(QMouseEvent *event) { |
| m_pressPos = m_pos = event->pos(); |
| } |
| |
| |
| |
| void SSDebugger::mouseReleaseEvent(QMouseEvent *event) {} |
| |
| |
| |
| QPoint SSDebugger::worldToWin(double x, double y) { |
| return m_transform.map(QPointF(x, y)).toPoint(); |
| } |
| |
| |
| |
| QPoint SSDebugger::winToWorld(int x, int y) { |
| return m_transform.inverted().map(QPoint(x, y)); |
| } |
| |
| |
| |
| QPointF SSDebugger::winToWorldF(int x, int y) { |
| return m_transform.inverted().map(QPointF(x, y)); |
| } |
| |
| |
| |
| void SSDebugger::wheelEvent(QWheelEvent *event) { |
| QPoint w_coords; |
| double zoom_par = 1 + event->delta() * 0.001; |
| |
| m_scale *= zoom_par; |
| |
| w_coords = winToWorld(event->x(), event->y()); |
| |
| m_transform.translate(w_coords.x(), w_coords.y()); |
| m_transform.scale(zoom_par, zoom_par); |
| m_transform.translate(-w_coords.x(), -w_coords.y()); |
| |
| update(); |
| } |
| |
| |
| |
| inline bool SSDebugger::isOnScreen(ContourNode *node) { |
| const TPointD &pos = updated(node); |
| return rect().contains(worldToWin(pos.x, pos.y)); |
| } |
| |
| #endif |
| |