diff options
Diffstat (limited to 'src/gui/painting/qtessellator.cpp')
| -rw-r--r-- | src/gui/painting/qtessellator.cpp | 1499 |
1 files changed, 1499 insertions, 0 deletions
diff --git a/src/gui/painting/qtessellator.cpp b/src/gui/painting/qtessellator.cpp new file mode 100644 index 0000000..e02f02d --- /dev/null +++ b/src/gui/painting/qtessellator.cpp @@ -0,0 +1,1499 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qtessellator_p.h" + +#include <QRect> +#include <QList> +#include <QDebug> + +#include <qmath.h> +#include <limits.h> + +QT_BEGIN_NAMESPACE + +//#define DEBUG +#ifdef DEBUG +#define QDEBUG qDebug +#else +#define QDEBUG if (1); else qDebug +#endif + +static const bool emit_clever = true; +static const bool mark_clever = false; + +enum VertexFlags { + LineBeforeStarts = 0x1, + LineBeforeEnds = 0x2, + LineBeforeHorizontal = 0x4, + LineAfterStarts = 0x8, + LineAfterEnds = 0x10, + LineAfterHorizontal = 0x20 +}; + + + +class QTessellatorPrivate { +public: + struct Vertices; + + QTessellatorPrivate() {} + + QRectF collectAndSortVertices(const QPointF *points, int *maxActiveEdges); + void cancelCoincidingEdges(); + + void emitEdges(QTessellator *tessellator); + void processIntersections(); + void removeEdges(); + void addEdges(); + void addIntersections(); + + struct Vertex : public QTessellator::Vertex + { + int flags; + }; + + struct Intersection + { + Q27Dot5 y; + int edge; + bool operator <(const Intersection &other) const { + if (y != other.y) + return y < other.y; + return edge < other.edge; + } + }; + struct IntersectionLink + { + int next; + int prev; + }; + typedef QMap<Intersection, IntersectionLink> Intersections; + + struct Edge { + Edge(const Vertices &v, int _edge); + int edge; + const Vertex *v0; + const Vertex *v1; + Q27Dot5 y_left; + Q27Dot5 y_right; + signed int winding : 8; + bool mark; + bool free; + bool intersect_left; + bool intersect_right; + bool isLeftOf(const Edge &other, Q27Dot5 y) const; + Q27Dot5 positionAt(Q27Dot5 y) const; + bool intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const; + + }; + + class EdgeSorter + { + public: + EdgeSorter(int _y) : y(_y) {} + bool operator() (const Edge *e1, const Edge *e2); + int y; + }; + + class Scanline { + public: + Scanline(); + ~Scanline(); + + void init(int maxActiveEdges); + void done(); + + int findEdgePosition(Q27Dot5 x, Q27Dot5 y) const; + int findEdgePosition(const Edge &e) const; + int findEdge(int edge) const; + void clearMarks(); + + void swap(int p1, int p2) { + Edge *tmp = edges[p1]; + edges[p1] = edges[p2]; + edges[p2] = tmp; + } + void insert(int pos, const Edge &e); + void removeAt(int pos); + void markEdges(int pos1, int pos2); + + void prepareLine(); + void lineDone(); + + Edge **old; + int old_size; + + Edge **edges; + int size; + + private: + Edge *edge_table; + int first_unused; + int max_edges; + enum { default_alloc = 32 }; + }; + + struct Vertices { + enum { default_alloc = 128 }; + Vertices(); + ~Vertices(); + void init(int maxVertices); + void done(); + Vertex *storage; + Vertex **sorted; + + Vertex *operator[] (int i) { return storage + i; } + const Vertex *operator[] (int i) const { return storage + i; } + int position(const Vertex *v) const { + return v - storage; + } + Vertex *next(Vertex *v) { + ++v; + if (v == storage + nPoints) + v = storage; + return v; + } + const Vertex *next(const Vertex *v) const { + ++v; + if (v == storage + nPoints) + v = storage; + return v; + } + int nextPos(const Vertex *v) const { + ++v; + if (v == storage + nPoints) + return 0; + return v - storage; + } + Vertex *prev(Vertex *v) { + if (v == storage) + v = storage + nPoints; + --v; + return v; + } + const Vertex *prev(const Vertex *v) const { + if (v == storage) + v = storage + nPoints; + --v; + return v; + } + int prevPos(const Vertex *v) const { + if (v == storage) + v = storage + nPoints; + --v; + return v - storage; + } + int nPoints; + int allocated; + }; + Vertices vertices; + Intersections intersections; + Scanline scanline; + bool winding; + Q27Dot5 y; + int currentVertex; + +private: + void addIntersection(const Edge *e1, const Edge *e2); + bool edgeInChain(Intersection i, int edge); +}; + + +QTessellatorPrivate::Edge::Edge(const QTessellatorPrivate::Vertices &vertices, int edge) +{ + this->edge = edge; + intersect_left = intersect_right = true; + mark = false; + free = false; + + v0 = vertices[edge]; + v1 = vertices.next(v0); + + Q_ASSERT(v0->y != v1->y); + + if (v0->y > v1->y) { + qSwap(v0, v1); + winding = -1; + } else { + winding = 1; + } + y_left = y_right = v0->y; +} + +// This is basically the algorithm from graphics gems. The algorithm +// is cubic in the coordinates at one place. Since we use 64bit +// integers, this implies, that the allowed range for our coordinates +// is limited to 21 bits. With 5 bits behind the decimal, this +// implies that differences in coordaintes can range from 2*SHORT_MIN +// to 2*SHORT_MAX, giving us efficiently a coordinate system from +// SHORT_MIN to SHORT_MAX. +// + +// WARNING: It's absolutely critical that the intersect() and isLeftOf() methods use +// exactly the same algorithm to calulate yi. It's also important to be sure the algorithms +// are transitive (ie. the conditions below are true for all input data): +// +// a.intersect(b) == b.intersect(a) +// a.isLeftOf(b) != b.isLeftOf(a) +// +// This is tricky to get right, so be very careful when changing anything in here! + +static inline bool sameSign(qint64 a, qint64 b) { + return (((qint64) ((quint64) a ^ (quint64) b)) >= 0 ); +} + +bool QTessellatorPrivate::Edge::intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const +{ + qint64 a1 = v1->y - v0->y; + qint64 b1 = v0->x - v1->x; + + qint64 a2 = other.v1->y - other.v0->y; + qint64 b2 = other.v0->x - other.v1->x; + + qint64 det = a1 * b2 - a2 * b1; + if (det == 0) + return false; + + qint64 c1 = qint64(v1->x) * v0->y - qint64(v0->x) * v1->y; + + qint64 r3 = a1 * other.v0->x + b1 * other.v0->y + c1; + qint64 r4 = a1 * other.v1->x + b1 * other.v1->y + c1; + + // Check signs of r3 and r4. If both point 3 and point 4 lie on + // same side of line 1, the line segments do not intersect. + QDEBUG() << " " << r3 << r4; + if (r3 != 0 && r4 != 0 && sameSign( r3, r4 )) + return false; + + qint64 c2 = qint64(other.v1->x) * other.v0->y - qint64(other.v0->x) * other.v1->y; + + qint64 r1 = a2 * v0->x + b2 * v0->y + c2; + qint64 r2 = a2 * v1->x + b2 * v1->y + c2; + + // Check signs of r1 and r2. If both point 1 and point 2 lie + // on same side of second line segment, the line segments do not intersect. + QDEBUG() << " " << r1 << r2; + if (r1 != 0 && r2 != 0 && sameSign( r1, r2 )) + return false; + + // The det/2 is to get rounding instead of truncating. It + // is added or subtracted to the numerator, depending upon the + // sign of the numerator. + qint64 offset = det < 0 ? -det : det; + offset >>= 1; + + qint64 num = a2 * c1 - a1 * c2; + *y = ( num < 0 ? num - offset : num + offset ) / det; + + *det_positive = (det > 0); + + return true; +} + +#undef SAME_SIGNS + +bool QTessellatorPrivate::Edge::isLeftOf(const Edge &other, Q27Dot5 y) const +{ +// QDEBUG() << "isLeftOf" << edge << other.edge << y; + qint64 a1 = v1->y - v0->y; + qint64 b1 = v0->x - v1->x; + qint64 a2 = other.v1->y - other.v0->y; + qint64 b2 = other.v0->x - other.v1->x; + + qint64 c2 = qint64(other.v1->x) * other.v0->y - qint64(other.v0->x) * other.v1->y; + + qint64 det = a1 * b2 - a2 * b1; + if (det == 0) { + // lines are parallel. Only need to check side of one point + // fixed ordering for coincident edges + qint64 r1 = a2 * v0->x + b2 * v0->y + c2; +// QDEBUG() << "det = 0" << r1; + if (r1 == 0) + return edge < other.edge; + return (r1 < 0); + } + + // not parallel, need to find the y coordinate of the intersection point + qint64 c1 = qint64(v1->x) * v0->y - qint64(v0->x) * v1->y; + + qint64 offset = det < 0 ? -det : det; + offset >>= 1; + + qint64 num = a2 * c1 - a1 * c2; + qint64 yi = ( num < 0 ? num - offset : num + offset ) / det; +// QDEBUG() << " num=" << num << "offset=" << offset << "det=" << det; + + return ((yi > y) ^ (det < 0)); +} + +static inline bool compareVertex(const QTessellatorPrivate::Vertex *p1, + const QTessellatorPrivate::Vertex *p2) +{ + if (p1->y == p2->y) { + if (p1->x == p2->x) + return p1 < p2; + return p1->x < p2->x; + } + return p1->y < p2->y; +} + +Q27Dot5 QTessellatorPrivate::Edge::positionAt(Q27Dot5 y) const +{ + if (y == v0->y) + return v0->x; + else if (y == v1->y) + return v1->x; + + qint64 d = v1->x - v0->x; + return (v0->x + d*(y - v0->y)/(v1->y-v0->y)); +} + +bool QTessellatorPrivate::EdgeSorter::operator() (const Edge *e1, const Edge *e2) +{ + return e1->isLeftOf(*e2, y); +} + + +QTessellatorPrivate::Scanline::Scanline() +{ + edges = 0; + edge_table = 0; + old = 0; +} + +void QTessellatorPrivate::Scanline::init(int maxActiveEdges) +{ + maxActiveEdges *= 2; + if (!edges || maxActiveEdges > default_alloc) { + max_edges = maxActiveEdges; + int s = qMax(maxActiveEdges + 1, default_alloc + 1); + edges = (Edge **)realloc(edges, s*sizeof(Edge *)); + edge_table = (Edge *)realloc(edge_table, s*sizeof(Edge)); + old = (Edge **)realloc(old, s*sizeof(Edge *)); + } + size = 0; + old_size = 0; + first_unused = 0; + for (int i = 0; i < maxActiveEdges; ++i) + edge_table[i].edge = i+1; + edge_table[maxActiveEdges].edge = -1; +} + +void QTessellatorPrivate::Scanline::done() +{ + if (max_edges > default_alloc) { + free(edges); + free(old); + free(edge_table); + edges = 0; + old = 0; + edge_table = 0; + } +} + +QTessellatorPrivate::Scanline::~Scanline() +{ + free(edges); + free(old); + free(edge_table); +} + +int QTessellatorPrivate::Scanline::findEdgePosition(Q27Dot5 x, Q27Dot5 y) const +{ + int min = 0; + int max = size - 1; + while (min < max) { + int pos = min + ((max - min + 1) >> 1); + Q27Dot5 ax = edges[pos]->positionAt(y); + if (ax > x) { + max = pos - 1; + } else { + min = pos; + } + } + return min; +} + +int QTessellatorPrivate::Scanline::findEdgePosition(const Edge &e) const +{ +// qDebug() << ">> findEdgePosition"; + int min = 0; + int max = size; + while (min < max) { + int pos = min + ((max - min) >> 1); +// qDebug() << " " << min << max << pos << edges[pos]->isLeftOf(e, e.y0); + if (edges[pos]->isLeftOf(e, e.v0->y)) { + min = pos + 1; + } else { + max = pos; + } + } +// qDebug() << "<< findEdgePosition got" << min; + return min; +} + +int QTessellatorPrivate::Scanline::findEdge(int edge) const +{ + for (int i = 0; i < size; ++i) { + int item_edge = edges[i]->edge; + if (item_edge == edge) + return i; + } + //Q_ASSERT(false); + return -1; +} + +void QTessellatorPrivate::Scanline::clearMarks() +{ + for (int i = 0; i < size; ++i) { + edges[i]->mark = false; + edges[i]->intersect_left = false; + edges[i]->intersect_right = false; + } +} + +void QTessellatorPrivate::Scanline::prepareLine() +{ + Edge **end = edges + size; + Edge **e = edges; + Edge **o = old; + while (e < end) { + *o = *e; + ++o; + ++e; + } + old_size = size; +} + +void QTessellatorPrivate::Scanline::lineDone() +{ + Edge **end = old + old_size; + Edge **e = old; + while (e < end) { + if ((*e)->free) { + (*e)->edge = first_unused; + first_unused = (*e - edge_table); + } + ++e; + } +} + +void QTessellatorPrivate::Scanline::insert(int pos, const Edge &e) +{ + Edge *edge = edge_table + first_unused; + first_unused = edge->edge; + Q_ASSERT(first_unused != -1); + *edge = e; + memmove(edges + pos + 1, edges + pos, (size - pos)*sizeof(Edge *)); + edges[pos] = edge; + ++size; +} + +void QTessellatorPrivate::Scanline::removeAt(int pos) +{ + Edge *e = edges[pos]; + e->free = true; + --size; + memmove(edges + pos, edges + pos + 1, (size - pos)*sizeof(Edge *)); +} + +void QTessellatorPrivate::Scanline::markEdges(int pos1, int pos2) +{ + if (pos2 < pos1) + return; + + for (int i = pos1; i <= pos2; ++i) + edges[i]->mark = true; +} + + +QTessellatorPrivate::Vertices::Vertices() +{ + storage = 0; + sorted = 0; + allocated = 0; + nPoints = 0; +} + +QTessellatorPrivate::Vertices::~Vertices() +{ + if (storage) { + free(storage); + free(sorted); + } +} + +void QTessellatorPrivate::Vertices::init(int maxVertices) +{ + if (!storage || maxVertices > allocated) { + int size = qMax((int)default_alloc, maxVertices); + storage = (Vertex *)realloc(storage, size*sizeof(Vertex)); + sorted = (Vertex **)realloc(sorted, size*sizeof(Vertex *)); + allocated = maxVertices; + } +} + +void QTessellatorPrivate::Vertices::done() +{ + if (allocated > default_alloc) { + free(storage); + free(sorted); + storage = 0; + sorted = 0; + allocated = 0; + } +} + + + +static inline void fillTrapezoid(Q27Dot5 y1, Q27Dot5 y2, int left, int right, + const QTessellatorPrivate::Vertices &vertices, + QTessellator::Trapezoid *trap) +{ + trap->top = y1; + trap->bottom = y2; + const QTessellatorPrivate::Vertex *v = vertices[left]; + trap->topLeft = v; + trap->bottomLeft = vertices.next(v); + if (trap->topLeft->y > trap->bottomLeft->y) + qSwap(trap->topLeft,trap->bottomLeft); + v = vertices[right]; + trap->topRight = v; + trap->bottomRight = vertices.next(v); + if (trap->topRight->y > trap->bottomRight->y) + qSwap(trap->topRight, trap->bottomRight); +} + +QRectF QTessellatorPrivate::collectAndSortVertices(const QPointF *points, int *maxActiveEdges) +{ + *maxActiveEdges = 0; + Vertex *v = vertices.storage; + Vertex **vv = vertices.sorted; + + qreal xmin(points[0].x()); + qreal xmax(points[0].x()); + qreal ymin(points[0].y()); + qreal ymax(points[0].y()); + + // collect vertex data + Q27Dot5 y_prev = FloatToQ27Dot5(points[vertices.nPoints-1].y()); + Q27Dot5 x_next = FloatToQ27Dot5(points[0].x()); + Q27Dot5 y_next = FloatToQ27Dot5(points[0].y()); + int j = 0; + int i = 0; + while (i < vertices.nPoints) { + Q27Dot5 y_curr = y_next; + + *vv = v; + + v->x = x_next; + v->y = y_next; + v->flags = 0; + + next_point: + + xmin = qMin(xmin, points[i+1].x()); + xmax = qMax(xmax, points[i+1].x()); + ymin = qMin(ymin, points[i+1].y()); + ymax = qMax(ymax, points[i+1].y()); + + y_next = FloatToQ27Dot5(points[i+1].y()); + x_next = FloatToQ27Dot5(points[i+1].x()); + + // skip vertices on top of each other + if (v->x == x_next && v->y == y_next) { + ++i; + if (i < vertices.nPoints) + goto next_point; + Vertex *v0 = vertices.storage; + v0->flags &= ~(LineBeforeStarts|LineBeforeEnds|LineBeforeHorizontal); + if (y_prev < y_curr) + v0->flags |= LineBeforeEnds; + else if (y_prev > y_curr) + v0->flags |= LineBeforeStarts; + else + v0->flags |= LineBeforeHorizontal; + if ((v0->flags & (LineBeforeStarts|LineAfterStarts)) + && !(v0->flags & (LineAfterEnds|LineBeforeEnds))) + *maxActiveEdges += 2; + break; + } + + if (y_prev < y_curr) + v->flags |= LineBeforeEnds; + else if (y_prev > y_curr) + v->flags |= LineBeforeStarts; + else + v->flags |= LineBeforeHorizontal; + + + if (y_curr < y_next) + v->flags |= LineAfterStarts; + else if (y_curr > y_next) + v->flags |= LineAfterEnds; + else + v->flags |= LineAfterHorizontal; + // ### could probably get better limit by looping over sorted list and counting down on ending edges + if ((v->flags & (LineBeforeStarts|LineAfterStarts)) + && !(v->flags & (LineAfterEnds|LineBeforeEnds))) + *maxActiveEdges += 2; + y_prev = y_curr; + ++v; + ++vv; + ++j; + ++i; + } + vertices.nPoints = j; + + QDEBUG() << "maxActiveEdges=" << *maxActiveEdges; + vv = vertices.sorted; + qSort(vv, vv + vertices.nPoints, compareVertex); + + return QRectF(xmin, ymin, xmax-xmin, ymax-ymin); +} + +struct QCoincidingEdge { + QTessellatorPrivate::Vertex *start; + QTessellatorPrivate::Vertex *end; + bool used; + bool before; + + inline bool operator<(const QCoincidingEdge &e2) const + { + return end->y == e2.end->y ? end->x < e2.end->x : end->y < e2.end->y; + } +}; + + +static void cancelEdges(QCoincidingEdge &e1, QCoincidingEdge &e2) +{ + if (e1.before) { + e1.start->flags &= ~(LineBeforeStarts|LineBeforeHorizontal); + e1.end->flags &= ~(LineAfterEnds|LineAfterHorizontal); + } else { + e1.start->flags &= ~(LineAfterStarts|LineAfterHorizontal); + e1.end->flags &= ~(LineBeforeEnds|LineBeforeHorizontal); + } + if (e2.before) { + e2.start->flags &= ~(LineBeforeStarts|LineBeforeHorizontal); + e2.end->flags &= ~(LineAfterEnds|LineAfterHorizontal); + } else { + e2.start->flags &= ~(LineAfterStarts|LineAfterHorizontal); + e2.end->flags &= ~(LineBeforeEnds|LineBeforeHorizontal); + } + e1.used = e2.used = true; +} + +void QTessellatorPrivate::cancelCoincidingEdges() +{ + Vertex **vv = vertices.sorted; + + QCoincidingEdge *tl = 0; + int tlSize = 0; + + for (int i = 0; i < vertices.nPoints - 1; ++i) { + Vertex *v = vv[i]; + int testListSize = 0; + while (i < vertices.nPoints - 1) { + Vertex *n = vv[i]; + if (v->x != n->x || v->y != n->y) + break; + + if (testListSize > tlSize - 2) { + tlSize = qMax(tlSize*2, 16); + tl = (QCoincidingEdge *)realloc(tl, tlSize*sizeof(QCoincidingEdge)); + } + if (n->flags & (LineBeforeStarts|LineBeforeHorizontal)) { + tl[testListSize].start = n; + tl[testListSize].end = vertices.prev(n); + tl[testListSize].used = false; + tl[testListSize].before = true; + ++testListSize; + } + if (n->flags & (LineAfterStarts|LineAfterHorizontal)) { + tl[testListSize].start = n; + tl[testListSize].end = vertices.next(n); + tl[testListSize].used = false; + tl[testListSize].before = false; + ++testListSize; + } + ++i; + } + if (!testListSize) + continue; + + qSort(tl, tl + testListSize); + + for (int j = 0; j < testListSize; ++j) { + if (tl[j].used) + continue; + + for (int k = j + 1; k < testListSize; ++k) { + if (tl[j].end->x != tl[k].end->x + || tl[j].end->y != tl[k].end->y + || tl[k].used) + break; + + if (!winding || tl[j].before != tl[k].before) { + cancelEdges(tl[j], tl[k]); + break; + } + ++k; + } + ++j; + } + } + free(tl); +} + + +void QTessellatorPrivate::emitEdges(QTessellator *tessellator) +{ + //QDEBUG() << "TRAPS:"; + if (!scanline.old_size) + return; + + // emit edges + if (winding) { + // winding fill rule + int w = 0; + + scanline.old[0]->y_left = y; + + for (int i = 0; i < scanline.old_size - 1; ++i) { + Edge *left = scanline.old[i]; + Edge *right = scanline.old[i+1]; + w += left->winding; +// qDebug() << "i=" << i << "edge->winding=" << left->winding << "winding=" << winding; + if (w == 0) { + left->y_right = y; + right->y_left = y; + } else if (!emit_clever || left->mark || right->mark) { + Q27Dot5 top = qMax(left->y_right, right->y_left); + if (top != y) { + QTessellator::Trapezoid trap; + fillTrapezoid(top, y, left->edge, right->edge, vertices, &trap); + tessellator->addTrap(trap); +// QDEBUG() << " top=" << Q27Dot5ToDouble(top) << "left=" << left->edge << "right=" << right->edge; + } + right->y_left = y; + left->y_right = y; + } + left->mark = false; + } + if (scanline.old[scanline.old_size - 1]->mark) { + scanline.old[scanline.old_size - 1]->y_right = y; + scanline.old[scanline.old_size - 1]->mark = false; + } + } else { + // odd-even fill rule + for (int i = 0; i < scanline.old_size; i += 2) { + Edge *left = scanline.old[i]; + Edge *right = scanline.old[i+1]; + if (!emit_clever || left->mark || right->mark) { + Q27Dot5 top = qMax(left->y_right, right->y_left); + if (top != y) { + QTessellator::Trapezoid trap; + fillTrapezoid(top, y, left->edge, right->edge, vertices, &trap); + tessellator->addTrap(trap); + } +// QDEBUG() << " top=" << Q27Dot5ToDouble(top) << "left=" << left->edge << "right=" << right->edge; + left->y_left = y; + left->y_right = y; + right->y_left = y; + right->y_right = y; + left->mark = right->mark = false; + } + } + } +} + + +void QTessellatorPrivate::processIntersections() +{ + QDEBUG() << "PROCESS INTERSECTIONS"; + // process intersections + while (!intersections.isEmpty()) { + Intersections::iterator it = intersections.begin(); + if (it.key().y != y) + break; + + // swap edges + QDEBUG() << " swapping intersecting edges "; + int min = scanline.size; + int max = 0; + Q27Dot5 xmin = INT_MAX; + Q27Dot5 xmax = INT_MIN; + int num = 0; + while (1) { + const Intersection &i = it.key(); + int next = it->next; + + int edgePos = scanline.findEdge(i.edge); + if (edgePos >= 0) { + ++num; + min = qMin(edgePos, min); + max = qMax(edgePos, max); + Edge *edge = scanline.edges[edgePos]; + xmin = qMin(xmin, edge->positionAt(y)); + xmax = qMax(xmax, edge->positionAt(y)); + } + Intersection key; + key.y = y; + key.edge = next; + it = intersections.find(key); + intersections.remove(i); + if (it == intersections.end()) + break; + } + if (num < 2) + continue; + + Q_ASSERT(min != max); + QDEBUG() << "sorting between" << min << "and" << max << "xpos=" << xmin << xmax; + while (min > 0 && scanline.edges[min - 1]->positionAt(y) >= xmin) { + QDEBUG() << " adding edge on left"; + --min; + } + while (max < scanline.size - 1 && scanline.edges[max + 1]->positionAt(y) <= xmax) { + QDEBUG() << " adding edge on right"; + ++max; + } + + qSort(scanline.edges + min, scanline.edges + max + 1, EdgeSorter(y)); +#ifdef DEBUG + for (int i = min; i <= max; ++i) + QDEBUG() << " " << scanline.edges[i]->edge << "at pos" << i; +#endif + for (int i = min; i <= max; ++i) { + Edge *edge = scanline.edges[i]; + edge->intersect_left = true; + edge->intersect_right = true; + edge->mark = true; + } + } +} + +void QTessellatorPrivate::removeEdges() +{ + int cv = currentVertex; + while (cv < vertices.nPoints) { + const Vertex *v = vertices.sorted[cv]; + if (v->y > y) + break; + if (v->flags & LineBeforeEnds) { + QDEBUG() << " removing edge" << vertices.prevPos(v); + int pos = scanline.findEdge(vertices.prevPos(v)); + if (pos == -1) + continue; + scanline.edges[pos]->mark = true; + if (pos > 0) + scanline.edges[pos - 1]->intersect_right = true; + if (pos < scanline.size - 1) + scanline.edges[pos + 1]->intersect_left = true; + scanline.removeAt(pos); + } + if (v->flags & LineAfterEnds) { + QDEBUG() << " removing edge" << vertices.position(v); + int pos = scanline.findEdge(vertices.position(v)); + if (pos == -1) + continue; + scanline.edges[pos]->mark = true; + if (pos > 0) + scanline.edges[pos - 1]->intersect_right = true; + if (pos < scanline.size - 1) + scanline.edges[pos + 1]->intersect_left = true; + scanline.removeAt(pos); + } + ++cv; + } +} + +void QTessellatorPrivate::addEdges() +{ + while (currentVertex < vertices.nPoints) { + const Vertex *v = vertices.sorted[currentVertex]; + if (v->y > y) + break; + if (v->flags & LineBeforeStarts) { + // add new edge + int start = vertices.prevPos(v); + Edge e(vertices, start); + int pos = scanline.findEdgePosition(e); + QDEBUG() << " adding edge" << start << "at position" << pos; + scanline.insert(pos, e); + if (!mark_clever || !(v->flags & LineAfterEnds)) { + if (pos > 0) + scanline.edges[pos - 1]->mark = true; + if (pos < scanline.size - 1) + scanline.edges[pos + 1]->mark = true; + } + } + if (v->flags & LineAfterStarts) { + Edge e(vertices, vertices.position(v)); + int pos = scanline.findEdgePosition(e); + QDEBUG() << " adding edge" << vertices.position(v) << "at position" << pos; + scanline.insert(pos, e); + if (!mark_clever || !(v->flags & LineBeforeEnds)) { + if (pos > 0) + scanline.edges[pos - 1]->mark = true; + if (pos < scanline.size - 1) + scanline.edges[pos + 1]->mark = true; + } + } + if (v->flags & LineAfterHorizontal) { + int pos1 = scanline.findEdgePosition(v->x, v->y); + const Vertex *next = vertices.next(v); + Q_ASSERT(v->y == next->y); + int pos2 = scanline.findEdgePosition(next->x, next->y); + if (pos2 < pos1) + qSwap(pos1, pos2); + if (pos1 > 0) + --pos1; + if (pos2 == scanline.size) + --pos2; + //QDEBUG() << "marking horizontal edge from " << pos1 << "to" << pos2; + scanline.markEdges(pos1, pos2); + } + ++currentVertex; + } +} + +#ifdef DEBUG +static void checkLinkChain(const QTessellatorPrivate::Intersections &intersections, + QTessellatorPrivate::Intersection i) +{ +// qDebug() << " Link chain: "; + int end = i.edge; + while (1) { + QTessellatorPrivate::IntersectionLink l = intersections.value(i); +// qDebug() << " " << i.edge << "next=" << l.next << "prev=" << l.prev; + if (l.next == end) + break; + Q_ASSERT(l.next != -1); + Q_ASSERT(l.prev != -1); + + QTessellatorPrivate::Intersection i2 = i; + i2.edge = l.next; + QTessellatorPrivate::IntersectionLink l2 = intersections.value(i2); + + Q_ASSERT(l2.next != -1); + Q_ASSERT(l2.prev != -1); + Q_ASSERT(l.next == i2.edge); + Q_ASSERT(l2.prev == i.edge); + i = i2; + } +} +#endif + +bool QTessellatorPrivate::edgeInChain(Intersection i, int edge) +{ + int end = i.edge; + while (1) { + if (i.edge == edge) + return true; + IntersectionLink l = intersections.value(i); + if (l.next == end) + break; + Q_ASSERT(l.next != -1); + Q_ASSERT(l.prev != -1); + + Intersection i2 = i; + i2.edge = l.next; + +#ifndef QT_NO_DEBUG + IntersectionLink l2 = intersections.value(i2); + Q_ASSERT(l2.next != -1); + Q_ASSERT(l2.prev != -1); + Q_ASSERT(l.next == i2.edge); + Q_ASSERT(l2.prev == i.edge); +#endif + i = i2; + } + return false; +} + + +void QTessellatorPrivate::addIntersection(const Edge *e1, const Edge *e2) +{ + const IntersectionLink emptyLink = {-1, -1}; + + int next = vertices.nextPos(vertices[e1->edge]); + if (e2->edge == next) + return; + int prev = vertices.prevPos(vertices[e1->edge]); + if (e2->edge == prev) + return; + + Q27Dot5 yi; + bool det_positive; + bool isect = e1->intersect(*e2, &yi, &det_positive); + QDEBUG("checking edges %d and %d", e1->edge, e2->edge); + if (!isect) { + QDEBUG() << " no intersection"; + return; + } + + // don't emit an intersection if it's at the start of a line segment or above us + if (yi <= y) { + if (!det_positive) + return; + QDEBUG() << " ----->>>>>> WRONG ORDER!"; + yi = y; + } + QDEBUG() << " between edges " << e1->edge << "and" << e2->edge << "at point (" + << Q27Dot5ToDouble(yi) << ")"; + + Intersection i1; + i1.y = yi; + i1.edge = e1->edge; + IntersectionLink link1 = intersections.value(i1, emptyLink); + Intersection i2; + i2.y = yi; + i2.edge = e2->edge; + IntersectionLink link2 = intersections.value(i2, emptyLink); + + // new pair of edges + if (link1.next == -1 && link2.next == -1) { + link1.next = link1.prev = i2.edge; + link2.next = link2.prev = i1.edge; + } else if (link1.next == i2.edge || link1.prev == i2.edge + || link2.next == i1.edge || link2.prev == i1.edge) { +#ifdef DEBUG + checkLinkChain(intersections, i1); + checkLinkChain(intersections, i2); + Q_ASSERT(edgeInChain(i1, i2.edge)); +#endif + return; + } else if (link1.next == -1 || link2.next == -1) { + if (link2.next == -1) { + qSwap(i1, i2); + qSwap(link1, link2); + } + Q_ASSERT(link1.next == -1); +#ifdef DEBUG + checkLinkChain(intersections, i2); +#endif + // only i2 in list + link1.next = i2.edge; + link1.prev = link2.prev; + link2.prev = i1.edge; + Intersection other; + other.y = yi; + other.edge = link1.prev; + IntersectionLink link = intersections.value(other, emptyLink); + Q_ASSERT(link.next == i2.edge); + Q_ASSERT(link.prev != -1); + link.next = i1.edge; + intersections.insert(other, link); + } else { + bool connected = edgeInChain(i1, i2.edge); + if (connected) + return; +#ifdef DEBUG + checkLinkChain(intersections, i1); + checkLinkChain(intersections, i2); +#endif + // both already in some list. Have to make sure they are connected + // this can be done by cutting open the ring(s) after the two eges and + // connecting them again + Intersection other1; + other1.y = yi; + other1.edge = link1.next; + IntersectionLink linko1 = intersections.value(other1, emptyLink); + Intersection other2; + other2.y = yi; + other2.edge = link2.next; + IntersectionLink linko2 = intersections.value(other2, emptyLink); + + linko1.prev = i2.edge; + link2.next = other1.edge; + + linko2.prev = i1.edge; + link1.next = other2.edge; + intersections.insert(other1, linko1); + intersections.insert(other2, linko2); + } + intersections.insert(i1, link1); + intersections.insert(i2, link2); +#ifdef DEBUG + checkLinkChain(intersections, i1); + checkLinkChain(intersections, i2); + Q_ASSERT(edgeInChain(i1, i2.edge)); +#endif + return; + +} + + +void QTessellatorPrivate::addIntersections() +{ + if (scanline.size) { + QDEBUG() << "INTERSECTIONS"; + // check marked edges for intersections +#ifdef DEBUG + for (int i = 0; i < scanline.size; ++i) { + Edge *e = scanline.edges[i]; + QDEBUG() << " " << i << e->edge << "isect=(" << e->intersect_left << e->intersect_right + << ")"; + } +#endif + + for (int i = 0; i < scanline.size - 1; ++i) { + Edge *e1 = scanline.edges[i]; + Edge *e2 = scanline.edges[i + 1]; + // check for intersection + if (e1->intersect_right || e2->intersect_left) + addIntersection(e1, e2); + } + } +#if 0 + if (intersections.constBegin().key().y == y) { + QDEBUG() << "----------------> intersection on same line"; + scanline.clearMarks(); + scanline.processIntersections(y, &intersections); + goto redo; + } +#endif +} + + +QTessellator::QTessellator() +{ + d = new QTessellatorPrivate; +} + +QTessellator::~QTessellator() +{ + delete d; +} + +void QTessellator::setWinding(bool w) +{ + d->winding = w; +} + + +QRectF QTessellator::tessellate(const QPointF *points, int nPoints) +{ + Q_ASSERT(points[0] == points[nPoints-1]); + --nPoints; + +#ifdef DEBUG + QDEBUG()<< "POINTS:"; + for (int i = 0; i < nPoints; ++i) { + QDEBUG() << points[i]; + } +#endif + + // collect edges and calculate bounds + d->vertices.nPoints = nPoints; + d->vertices.init(nPoints); + + int maxActiveEdges = 0; + QRectF br = d->collectAndSortVertices(points, &maxActiveEdges); + d->cancelCoincidingEdges(); + +#ifdef DEBUG + QDEBUG() << "nPoints = " << nPoints << "using " << d->vertices.nPoints; + QDEBUG()<< "VERTICES:"; + for (int i = 0; i < d->vertices.nPoints; ++i) { + QDEBUG() << " " << i << ": " + << "point=" << d->vertices.position(d->vertices.sorted[i]) + << "flags=" << d->vertices.sorted[i]->flags + << "pos=(" << Q27Dot5ToDouble(d->vertices.sorted[i]->x) << "/" + << Q27Dot5ToDouble(d->vertices.sorted[i]->y) << ")"; + } +#endif + + d->scanline.init(maxActiveEdges); + d->y = INT_MIN/256; + d->currentVertex = 0; + + while (d->currentVertex < d->vertices.nPoints) { + d->scanline.clearMarks(); + + d->y = d->vertices.sorted[d->currentVertex]->y; + if (!d->intersections.isEmpty()) + d->y = qMin(d->y, d->intersections.constBegin().key().y); + + QDEBUG()<< "===== SCANLINE: y =" << Q27Dot5ToDouble(d->y) << " ====="; + + d->scanline.prepareLine(); + d->processIntersections(); + d->removeEdges(); + d->addEdges(); + d->addIntersections(); + d->emitEdges(this); + d->scanline.lineDone(); + +#ifdef DEBUG + QDEBUG()<< "===== edges:"; + for (int i = 0; i < d->scanline.size; ++i) { + QDEBUG() << " " << d->scanline.edges[i]->edge + << "p0= (" << Q27Dot5ToDouble(d->scanline.edges[i]->v0->x) + << "/" << Q27Dot5ToDouble(d->scanline.edges[i]->v0->y) + << ") p1= (" << Q27Dot5ToDouble(d->scanline.edges[i]->v1->x) + << "/" << Q27Dot5ToDouble(d->scanline.edges[i]->v1->y) << ")" + << "x=" << Q27Dot5ToDouble(d->scanline.edges[i]->positionAt(d->y)) + << "isLeftOfNext=" + << ((i < d->scanline.size - 1) + ? d->scanline.edges[i]->isLeftOf(*d->scanline.edges[i+1], d->y) + : true); + } +#endif +} + + d->scanline.done(); + d->intersections.clear(); + return br; +} + +// tessellates the given convex polygon +void QTessellator::tessellateConvex(const QPointF *points, int nPoints) +{ + Q_ASSERT(points[0] == points[nPoints-1]); + --nPoints; + + d->vertices.nPoints = nPoints; + d->vertices.init(nPoints); + + for (int i = 0; i < nPoints; ++i) { + d->vertices[i]->x = FloatToQ27Dot5(points[i].x()); + d->vertices[i]->y = FloatToQ27Dot5(points[i].y()); + } + + int left = 0, right = 0; + + int top = 0; + for (int i = 1; i < nPoints; ++i) { + if (d->vertices[i]->y < d->vertices[top]->y) + top = i; + } + + left = (top + nPoints - 1) % nPoints; + right = (top + 1) % nPoints; + + while (d->vertices[left]->x == d->vertices[top]->x && d->vertices[left]->y == d->vertices[top]->y && left != right) + left = (left + nPoints - 1) % nPoints; + + while (d->vertices[right]->x == d->vertices[top]->x && d->vertices[right]->y == d->vertices[top]->y && left != right) + right = (right + 1) % nPoints; + + if (left == right) + return; + + int dir = 1; + + Vertex dLeft = { d->vertices[top]->x - d->vertices[left]->x, + d->vertices[top]->y - d->vertices[left]->y }; + + Vertex dRight = { d->vertices[right]->x - d->vertices[top]->x, + d->vertices[right]->y - d->vertices[top]->y }; + + Q27Dot5 cross = dLeft.x * dRight.y - dLeft.y * dRight.x; + + // flip direction if polygon is clockwise + if (cross < 0 || (cross == 0 && dLeft.x > 0)) { + qSwap(left, right); + dir = -1; + } + + Vertex *lastLeft = d->vertices[top]; + Vertex *lastRight = d->vertices[top]; + + QTessellator::Trapezoid trap; + + while (lastLeft->y == d->vertices[left]->y && left != right) { + lastLeft = d->vertices[left]; + left = (left + nPoints - dir) % nPoints; + } + + while (lastRight->y == d->vertices[right]->y && left != right) { + lastRight = d->vertices[right]; + right = (right + nPoints + dir) % nPoints; + } + + while (true) { + trap.top = qMax(lastRight->y, lastLeft->y); + trap.bottom = qMin(d->vertices[left]->y, d->vertices[right]->y); + trap.topLeft = lastLeft; + trap.topRight = lastRight; + trap.bottomLeft = d->vertices[left]; + trap.bottomRight = d->vertices[right]; + + if (trap.bottom > trap.top) + addTrap(trap); + + if (left == right) + break; + + if (d->vertices[right]->y < d->vertices[left]->y) { + do { + lastRight = d->vertices[right]; + right = (right + nPoints + dir) % nPoints; + } + while (lastRight->y == d->vertices[right]->y && left != right); + } else { + do { + lastLeft = d->vertices[left]; + left = (left + nPoints - dir) % nPoints; + } + while (lastLeft->y == d->vertices[left]->y && left != right); + } + } +} + +// tessellates the stroke of the line from a_ to b_ with the given width and a flat cap +void QTessellator::tessellateRect(const QPointF &a_, const QPointF &b_, qreal width) +{ + Vertex a = { FloatToQ27Dot5(a_.x()), FloatToQ27Dot5(a_.y()) }; + Vertex b = { FloatToQ27Dot5(b_.x()), FloatToQ27Dot5(b_.y()) }; + + QPointF pa = a_, pb = b_; + + if (a.y > b.y) { + qSwap(a, b); + qSwap(pa, pb); + } + + Vertex delta = { b.x - a.x, b.y - a.y }; + + if (delta.x == 0 && delta.y == 0) + return; + + qreal hw = 0.5 * width; + + if (delta.x == 0) { + Q27Dot5 halfWidth = FloatToQ27Dot5(hw); + + if (halfWidth == 0) + return; + + Vertex topLeft = { a.x - halfWidth, a.y }; + Vertex topRight = { a.x + halfWidth, a.y }; + Vertex bottomLeft = { a.x - halfWidth, b.y }; + Vertex bottomRight = { a.x + halfWidth, b.y }; + + QTessellator::Trapezoid trap = { topLeft.y, bottomLeft.y, &topLeft, &bottomLeft, &topRight, &bottomRight }; + addTrap(trap); + } else if (delta.y == 0) { + Q27Dot5 halfWidth = FloatToQ27Dot5(hw); + + if (halfWidth == 0) + return; + + if (a.x > b.x) + qSwap(a.x, b.x); + + Vertex topLeft = { a.x, a.y - halfWidth }; + Vertex topRight = { b.x, a.y - halfWidth }; + Vertex bottomLeft = { a.x, a.y + halfWidth }; + Vertex bottomRight = { b.x, a.y + halfWidth }; + + QTessellator::Trapezoid trap = { topLeft.y, bottomLeft.y, &topLeft, &bottomLeft, &topRight, &bottomRight }; + addTrap(trap); + } else { + QPointF perp(pb.y() - pa.y(), pa.x() - pb.x()); + qreal length = qSqrt(perp.x() * perp.x() + perp.y() * perp.y()); + + if (qFuzzyCompare(length + 1, static_cast<qreal>(1))) + return; + + // need the half of the width + perp *= hw / length; + + QPointF pta = pa + perp; + QPointF ptb = pa - perp; + QPointF ptc = pb - perp; + QPointF ptd = pb + perp; + + Vertex ta = { FloatToQ27Dot5(pta.x()), FloatToQ27Dot5(pta.y()) }; + Vertex tb = { FloatToQ27Dot5(ptb.x()), FloatToQ27Dot5(ptb.y()) }; + Vertex tc = { FloatToQ27Dot5(ptc.x()), FloatToQ27Dot5(ptc.y()) }; + Vertex td = { FloatToQ27Dot5(ptd.x()), FloatToQ27Dot5(ptd.y()) }; + + if (ta.y < tb.y) { + if (tb.y < td.y) { + QTessellator::Trapezoid top = { ta.y, tb.y, &ta, &tb, &ta, &td }; + QTessellator::Trapezoid bottom = { td.y, tc.y, &tb, &tc, &td, &tc }; + addTrap(top); + addTrap(bottom); + + QTessellator::Trapezoid middle = { tb.y, td.y, &tb, &tc, &ta, &td }; + addTrap(middle); + } else { + QTessellator::Trapezoid top = { ta.y, td.y, &ta, &tb, &ta, &td }; + QTessellator::Trapezoid bottom = { tb.y, tc.y, &tb, &tc, &td, &tc }; + addTrap(top); + addTrap(bottom); + + if (tb.y != td.y) { + QTessellator::Trapezoid middle = { td.y, tb.y, &ta, &tb, &td, &tc }; + addTrap(middle); + } + } + } else { + if (ta.y < tc.y) { + QTessellator::Trapezoid top = { tb.y, ta.y, &tb, &tc, &tb, &ta }; + QTessellator::Trapezoid bottom = { tc.y, td.y, &tc, &td, &ta, &td }; + addTrap(top); + addTrap(bottom); + + QTessellator::Trapezoid middle = { ta.y, tc.y, &tb, &tc, &ta, &td }; + addTrap(middle); + } else { + QTessellator::Trapezoid top = { tb.y, tc.y, &tb, &tc, &tb, &ta }; + QTessellator::Trapezoid bottom = { ta.y, td.y, &tc, &td, &ta, &td }; + addTrap(top); + addTrap(bottom); + + if (ta.y != tc.y) { + QTessellator::Trapezoid middle = { tc.y, ta.y, &tc, &td, &tb, &ta }; + addTrap(middle); + } + } + } + } +} + +QT_END_NAMESPACE |