| /**************************************************************************** |
| ** |
| ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). |
| ** All rights reserved. |
| ** Contact: Nokia Corporation (qt-info@nokia.com) |
| ** |
| ** This file is part of the QtGui module of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:LGPL$ |
| ** GNU Lesser General Public License Usage |
| ** 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.1, 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. |
| ** |
| ** Other Usage |
| ** Alternatively, this file may be used in accordance with the terms and |
| ** conditions contained in a signed written agreement between you and Nokia. |
| ** |
| ** |
| ** |
| ** |
| ** |
| ** $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 = q_check_ptr((Edge **)realloc(edges, s*sizeof(Edge *))); |
| edge_table = q_check_ptr((Edge *)realloc(edge_table, s*sizeof(Edge))); |
| old = q_check_ptr((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 = q_check_ptr((Vertex *)realloc(storage, size*sizeof(Vertex))); |
| sorted = q_check_ptr((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 = q_check_ptr((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 (qFuzzyIsNull(length)) |
| 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 |