src/gui/painting/qtessellator.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the QtGui module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qtessellator_p.h"
  43
  44 #include <QRect>
  45 #include <QList>
  46 #include <QDebug>
  47
  48 #include <qmath.h>
  49 #include <limits.h>
  50
  51 QT_BEGIN_NAMESPACE
  52
  53 //#define DEBUG
  54 #ifdef DEBUG
  55 #define QDEBUG qDebug
  56 #else
  57 #define QDEBUG if (1){} else qDebug
  58 #endif
  59
  60 static const bool emit_clever = true;
  61 static const bool mark_clever = false;
  62
  63 enum VertexFlags {
  64     LineBeforeStarts = 0x1,
  65     LineBeforeEnds = 0x2,
  66     LineBeforeHorizontal = 0x4,
  67     LineAfterStarts = 0x8,
  68     LineAfterEnds = 0x10,
  69     LineAfterHorizontal = 0x20
  70 };
  71
  72
  73
  74 class QTessellatorPrivate {
  75 public:
  76     struct Vertices;
  77
  78     QTessellatorPrivate() {}
  79
  80     QRectF collectAndSortVertices(const QPointF *points, int *maxActiveEdges);
  81     void cancelCoincidingEdges();
  82
  83     void emitEdges(QTessellator *tessellator);
  84     void processIntersections();
  85     void removeEdges();
  86     void addEdges();
  87     void addIntersections();
  88
  89     struct Vertex : public QTessellator::Vertex
  90     {
  91         int flags;
  92     };
  93
  94     struct Intersection
  95     {
  96         Q27Dot5 y;
  97         int edge;
  98         bool operator <(const Intersection &other) const {
  99             if (y != other.y)
 100                 return y < other.y;
 101             return edge < other.edge;
 102         }
 103     };
 104     struct IntersectionLink
 105     {
 106         int next;
 107         int prev;
 108     };
 109     typedef QMap<Intersection, IntersectionLink> Intersections;
 110
 111     struct Edge {
 112         Edge(const Vertices &v, int _edge);
 113         int edge;
 114         const Vertex *v0;
 115         const Vertex *v1;
 116         Q27Dot5 y_left;
 117         Q27Dot5 y_right;
 118         signed int winding : 8;
 119         bool mark;
 120         bool free;
 121         bool intersect_left;
 122         bool intersect_right;
 123         bool isLeftOf(const Edge &other, Q27Dot5 y) const;
 124         Q27Dot5 positionAt(Q27Dot5 y) const;
 125         bool intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const;
 126
 127     };
 128
 129     class EdgeSorter
 130     {
 131     public:
 132         EdgeSorter(int _y) : y(_y) {}
 133         bool operator() (const Edge *e1, const Edge *e2);
 134         int y;
 135     };
 136
 137     class Scanline {
 138     public:
 139         Scanline();
 140         ~Scanline();
 141
 142         void init(int maxActiveEdges);
 143         void done();
 144
 145         int findEdgePosition(Q27Dot5 x, Q27Dot5 y) const;
 146         int findEdgePosition(const Edge &e) const;
 147         int findEdge(int edge) const;
 148         void clearMarks();
 149
 150         void swap(int p1, int p2) {
 151             Edge *tmp = edges[p1];
 152             edges[p1] = edges[p2];
 153             edges[p2] = tmp;
 154         }
 155         void insert(int pos, const Edge &e);
 156         void removeAt(int pos);
 157         void markEdges(int pos1, int pos2);
 158
 159         void prepareLine();
 160         void lineDone();
 161
 162         Edge **old;
 163         int old_size;
 164
 165         Edge **edges;
 166         int size;
 167
 168     private:
 169         Edge *edge_table;
 170         int first_unused;
 171         int max_edges;
 172         enum { default_alloc = 32 };
 173     };
 174
 175     struct Vertices {
 176         enum { default_alloc = 128 };
 177         Vertices();
 178         ~Vertices();
 179         void init(int maxVertices);
 180         void done();
 181         Vertex *storage;
 182         Vertex **sorted;
 183
 184         Vertex *operator[] (int i) { return storage + i; }
 185         const Vertex *operator[] (int i) const { return storage + i; }
 186         int position(const Vertex *v) const {
 187             return v - storage;
 188         }
 189         Vertex *next(Vertex *v) {
 190             ++v;
 191             if (v == storage + nPoints)
 192                 v = storage;
 193             return v;
 194         }
 195         const Vertex *next(const Vertex *v) const {
 196             ++v;
 197             if (v == storage + nPoints)
 198                 v = storage;
 199             return v;
 200         }
 201         int nextPos(const Vertex *v) const {
 202             ++v;
 203             if (v == storage + nPoints)
 204                 return 0;
 205             return v - storage;
 206         }
 207         Vertex *prev(Vertex *v) {
 208             if (v == storage)
 209                 v = storage + nPoints;
 210             --v;
 211             return v;
 212         }
 213         const Vertex *prev(const Vertex *v) const {
 214             if (v == storage)
 215                 v = storage + nPoints;
 216             --v;
 217             return v;
 218         }
 219         int prevPos(const Vertex *v) const {
 220             if (v == storage)
 221                 v = storage + nPoints;
 222             --v;
 223             return v - storage;
 224         }
 225         int nPoints;
 226         int allocated;
 227     };
 228     Vertices vertices;
 229     Intersections intersections;
 230     Scanline scanline;
 231     bool winding;
 232     Q27Dot5 y;
 233     int currentVertex;
 234
 235 private:
 236     void addIntersection(const Edge *e1, const Edge *e2);
 237     bool edgeInChain(Intersection i, int edge);
 238 };
 239
 240
 241 QTessellatorPrivate::Edge::Edge(const QTessellatorPrivate::Vertices &vertices, int edge)
 242 {
 243     this->edge = edge;
 244     intersect_left = intersect_right = true;
 245     mark = false;
 246     free = false;
 247
 248     v0 = vertices[edge];
 249     v1 = vertices.next(v0);
 250
 251     Q_ASSERT(v0->y != v1->y);
 252
 253     if (v0->y > v1->y) {
 254         qSwap(v0, v1);
 255         winding = -1;
 256     } else {
 257         winding = 1;
 258     }
 259     y_left = y_right = v0->y;
 260 }
 261
 262 // This is basically the algorithm from graphics gems. The algorithm
 263 // is cubic in the coordinates at one place.  Since we use 64bit
 264 // integers, this implies, that the allowed range for our coordinates
 265 // is limited to 21 bits.  With 5 bits behind the decimal, this
 266 // implies that differences in coordaintes can range from 2*SHORT_MIN
 267 // to 2*SHORT_MAX, giving us efficiently a coordinate system from
 268 // SHORT_MIN to SHORT_MAX.
 269 //
 270
 271 // WARNING: It's absolutely critical that the intersect() and isLeftOf() methods use
 272 // exactly the same algorithm to calulate yi. It's also important to be sure the algorithms
 273 // are transitive (ie. the conditions below are true for all input data):
 274 //
 275 // a.intersect(b) == b.intersect(a)
 276 // a.isLeftOf(b) != b.isLeftOf(a)
 277 //
 278 // This is tricky to get right, so be very careful when changing anything in here!
 279
 280 static inline bool sameSign(qint64 a, qint64 b) {
 281     return (((qint64) ((quint64) a ^ (quint64) b)) >= 0 );
 282 }
 283
 284 bool QTessellatorPrivate::Edge::intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const
 285 {
 286     qint64 a1 = v1->y - v0->y;
 287     qint64 b1 = v0->x - v1->x;
 288
 289     qint64 a2 = other.v1->y - other.v0->y;
 290     qint64 b2 = other.v0->x - other.v1->x;
 291
 292     qint64 det = a1 * b2 - a2 * b1;
 293     if (det == 0)
 294         return false;
 295
 296     qint64 c1 = qint64(v1->x) * v0->y - qint64(v0->x) * v1->y;
 297
 298     qint64 r3 = a1 * other.v0->x + b1 * other.v0->y + c1;
 299     qint64 r4 = a1 * other.v1->x + b1 * other.v1->y + c1;
 300
 301     // Check signs of r3 and r4.  If both point 3 and point 4 lie on
 302     // same side of line 1, the line segments do not intersect.
 303     QDEBUG() << "        " << r3 << r4;
 304     if (r3 != 0 && r4 != 0 && sameSign( r3, r4 ))
 305         return false;
 306
 307     qint64 c2 = qint64(other.v1->x) * other.v0->y - qint64(other.v0->x) * other.v1->y;
 308
 309     qint64 r1 = a2 * v0->x + b2 * v0->y + c2;
 310     qint64 r2 = a2 * v1->x + b2 * v1->y + c2;
 311
 312     // Check signs of r1 and r2.  If both point 1 and point 2 lie
 313     // on same side of second line segment, the line segments do not intersect.
 314     QDEBUG() << "        " << r1 << r2;
 315     if (r1 != 0 && r2 != 0 && sameSign( r1, r2 ))
 316         return false;
 317
 318     // The det/2 is to get rounding instead of truncating.  It
 319     // is added or subtracted to the numerator, depending upon the
 320     // sign of the numerator.
 321     qint64 offset = det < 0 ? -det : det;
 322     offset >>= 1;
 323
 324     qint64 num = a2 * c1 - a1 * c2;
 325     *y = ( num < 0 ? num - offset : num + offset ) / det;
 326
 327     *det_positive = (det > 0);
 328
 329     return true;
 330 }
 331
 332 #undef SAME_SIGNS
 333
 334 bool QTessellatorPrivate::Edge::isLeftOf(const Edge &other, Q27Dot5 y) const
 335 {
 336 //     QDEBUG() << "isLeftOf" << edge << other.edge << y;
 337     qint64 a1 = v1->y - v0->y;
 338     qint64 b1 = v0->x - v1->x;
 339     qint64 a2 = other.v1->y - other.v0->y;
 340     qint64 b2 = other.v0->x - other.v1->x;
 341
 342     qint64 c2 = qint64(other.v1->x) * other.v0->y - qint64(other.v0->x) * other.v1->y;
 343
 344     qint64 det = a1 * b2 - a2 * b1;
 345     if (det == 0) {
 346         // lines are parallel. Only need to check side of one point
 347         // fixed ordering for coincident edges
 348         qint64 r1 = a2 * v0->x + b2 * v0->y + c2;
 349 //         QDEBUG() << "det = 0" << r1;
 350         if (r1 == 0)
 351             return edge < other.edge;
 352         return (r1 < 0);
 353     }
 354
 355     // not parallel, need to find the y coordinate of the intersection point
 356     qint64 c1 = qint64(v1->x) * v0->y - qint64(v0->x) * v1->y;
 357
 358     qint64 offset = det < 0 ? -det : det;
 359     offset >>= 1;
 360
 361     qint64 num = a2 * c1 - a1 * c2;
 362     qint64 yi = ( num < 0 ? num - offset : num + offset ) / det;
 363 //     QDEBUG() << "    num=" << num << "offset=" << offset << "det=" << det;
 364
 365     return ((yi > y) ^ (det < 0));
 366 }
 367
 368 static inline bool compareVertex(const QTessellatorPrivate::Vertex *p1,
 369                                  const QTessellatorPrivate::Vertex *p2)
 370 {
 371     if (p1->y == p2->y) {
 372         if (p1->x == p2->x)
 373             return p1 < p2;
 374         return p1->x < p2->x;
 375     }
 376     return p1->y < p2->y;
 377 }
 378
 379 Q27Dot5 QTessellatorPrivate::Edge::positionAt(Q27Dot5 y) const
 380 {
 381     if (y == v0->y)
 382         return v0->x;
 383     else if (y == v1->y)
 384         return v1->x;
 385
 386     qint64 d = v1->x - v0->x;
 387     return (v0->x + d*(y - v0->y)/(v1->y-v0->y));
 388 }
 389
 390 bool QTessellatorPrivate::EdgeSorter::operator() (const Edge *e1, const Edge *e2)
 391 {
 392     return e1->isLeftOf(*e2, y);
 393 }
 394
 395
 396 QTessellatorPrivate::Scanline::Scanline()
 397 {
 398     edges = 0;
 399     edge_table = 0;
 400     old = 0;
 401 }
 402
 403 void QTessellatorPrivate::Scanline::init(int maxActiveEdges)
 404 {
 405     maxActiveEdges *= 2;
 406     if (!edges || maxActiveEdges > default_alloc) {
 407         max_edges = maxActiveEdges;
 408         int s = qMax(maxActiveEdges + 1, default_alloc + 1);
 409         edges = q_check_ptr((Edge **)realloc(edges, s*sizeof(Edge *)));
 410         edge_table = q_check_ptr((Edge *)realloc(edge_table, s*sizeof(Edge)));
 411         old = q_check_ptr((Edge **)realloc(old, s*sizeof(Edge *)));
 412     }
 413     size = 0;
 414     old_size = 0;
 415     first_unused = 0;
 416     for (int i = 0; i < maxActiveEdges; ++i)
 417         edge_table[i].edge = i+1;
 418     edge_table[maxActiveEdges].edge = -1;
 419 }
 420
 421 void QTessellatorPrivate::Scanline::done()
 422 {
 423     if (max_edges > default_alloc) {
 424         free(edges);
 425         free(old);
 426         free(edge_table);
 427         edges = 0;
 428         old = 0;
 429         edge_table = 0;
 430     }
 431 }
 432
 433 QTessellatorPrivate::Scanline::~Scanline()
 434 {
 435     free(edges);
 436     free(old);
 437     free(edge_table);
 438 }
 439
 440 int QTessellatorPrivate::Scanline::findEdgePosition(Q27Dot5 x, Q27Dot5 y) const
 441 {
 442     int min = 0;
 443     int max = size - 1;
 444     while (min < max) {
 445         int pos = min + ((max - min + 1) >> 1);
 446         Q27Dot5 ax = edges[pos]->positionAt(y);
 447         if (ax > x) {
 448             max = pos - 1;
 449         } else {
 450             min = pos;
 451         }
 452     }
 453     return min;
 454 }
 455
 456 int QTessellatorPrivate::Scanline::findEdgePosition(const Edge &e) const
 457 {
 458 //     qDebug() << ">>      findEdgePosition";
 459     int min = 0;
 460     int max = size;
 461     while (min < max) {
 462         int pos = min + ((max - min) >> 1);
 463 //         qDebug() << "        " << min << max << pos << edges[pos]->isLeftOf(e, e.y0);
 464         if (edges[pos]->isLeftOf(e, e.v0->y)) {
 465             min = pos + 1;
 466         } else {
 467             max = pos;
 468         }
 469     }
 470 //     qDebug() << "<<      findEdgePosition got" << min;
 471     return min;
 472 }
 473
 474 int QTessellatorPrivate::Scanline::findEdge(int edge) const
 475 {
 476     for (int i = 0; i < size; ++i) {
 477         int item_edge = edges[i]->edge;
 478         if (item_edge == edge)
 479             return i;
 480     }
 481     //Q_ASSERT(false);
 482     return -1;
 483 }
 484
 485 void QTessellatorPrivate::Scanline::clearMarks()
 486 {
 487     for (int i = 0; i < size; ++i) {
 488         edges[i]->mark = false;
 489         edges[i]->intersect_left = false;
 490         edges[i]->intersect_right = false;
 491     }
 492 }
 493
 494 void QTessellatorPrivate::Scanline::prepareLine()
 495 {
 496     Edge **end = edges + size;
 497     Edge **e = edges;
 498     Edge **o = old;
 499     while (e < end) {
 500         *o = *e;
 501         ++o;
 502         ++e;
 503     }
 504     old_size = size;
 505 }
 506
 507 void QTessellatorPrivate::Scanline::lineDone()
 508 {
 509     Edge **end = old + old_size;
 510     Edge **e = old;
 511     while (e < end) {
 512         if ((*e)->free) {
 513             (*e)->edge = first_unused;
 514             first_unused = (*e - edge_table);
 515         }
 516         ++e;
 517     }
 518 }
 519
 520 void QTessellatorPrivate::Scanline::insert(int pos, const Edge &e)
 521 {
 522     Edge *edge = edge_table + first_unused;
 523     first_unused = edge->edge;
 524     Q_ASSERT(first_unused != -1);
 525     *edge = e;
 526     memmove(edges + pos + 1, edges + pos, (size - pos)*sizeof(Edge *));
 527     edges[pos] = edge;
 528     ++size;
 529 }
 530
 531 void QTessellatorPrivate::Scanline::removeAt(int pos)
 532 {
 533     Edge *e = edges[pos];
 534     e->free = true;
 535     --size;
 536     memmove(edges + pos, edges + pos + 1, (size - pos)*sizeof(Edge *));
 537 }
 538
 539 void QTessellatorPrivate::Scanline::markEdges(int pos1, int pos2)
 540 {
 541     if (pos2 < pos1)
 542         return;
 543
 544     for (int i = pos1; i <= pos2; ++i)
 545         edges[i]->mark = true;
 546 }
 547
 548
 549 QTessellatorPrivate::Vertices::Vertices()
 550 {
 551     storage = 0;
 552     sorted = 0;
 553     allocated = 0;
 554     nPoints = 0;
 555 }
 556
 557 QTessellatorPrivate::Vertices::~Vertices()
 558 {
 559     if (storage) {
 560         free(storage);
 561         free(sorted);
 562     }
 563 }
 564
 565 void QTessellatorPrivate::Vertices::init(int maxVertices)
 566 {
 567     if (!storage || maxVertices > allocated) {
 568         int size = qMax((int)default_alloc, maxVertices);
 569         storage = q_check_ptr((Vertex *)realloc(storage, size*sizeof(Vertex)));
 570         sorted = q_check_ptr((Vertex **)realloc(sorted, size*sizeof(Vertex *)));
 571         allocated = maxVertices;
 572     }
 573 }
 574
 575 void QTessellatorPrivate::Vertices::done()
 576 {
 577     if (allocated > default_alloc) {
 578         free(storage);
 579         free(sorted);
 580         storage = 0;
 581         sorted = 0;
 582         allocated = 0;
 583     }
 584 }
 585
 586
 587
 588 static inline void fillTrapezoid(Q27Dot5 y1, Q27Dot5 y2, int left, int right,
 589                                  const QTessellatorPrivate::Vertices &vertices,
 590                                  QTessellator::Trapezoid *trap)
 591 {
 592     trap->top = y1;
 593     trap->bottom = y2;
 594     const QTessellatorPrivate::Vertex *v = vertices[left];
 595     trap->topLeft = v;
 596     trap->bottomLeft = vertices.next(v);
 597     if (trap->topLeft->y > trap->bottomLeft->y)
 598         qSwap(trap->topLeft,trap->bottomLeft);
 599     v = vertices[right];
 600     trap->topRight = v;
 601     trap->bottomRight = vertices.next(v);
 602     if (trap->topRight->y > trap->bottomRight->y)
 603         qSwap(trap->topRight, trap->bottomRight);
 604 }
 605
 606 QRectF QTessellatorPrivate::collectAndSortVertices(const QPointF *points, int *maxActiveEdges)
 607 {
 608     *maxActiveEdges = 0;
 609     Vertex *v = vertices.storage;
 610     Vertex **vv = vertices.sorted;
 611
 612     qreal xmin(points[0].x());
 613     qreal xmax(points[0].x());
 614     qreal ymin(points[0].y());
 615     qreal ymax(points[0].y());
 616
 617     // collect vertex data
 618     Q27Dot5 y_prev = FloatToQ27Dot5(points[vertices.nPoints-1].y());
 619     Q27Dot5 x_next = FloatToQ27Dot5(points[0].x());
 620     Q27Dot5 y_next = FloatToQ27Dot5(points[0].y());
 621     int j = 0;
 622     int i = 0;
 623     while (i < vertices.nPoints) {
 624         Q27Dot5 y_curr = y_next;
 625
 626         *vv = v;
 627
 628         v->x = x_next;
 629         v->y = y_next;
 630         v->flags = 0;
 631
 632     next_point:
 633
 634         xmin = qMin(xmin, points[i+1].x());
 635         xmax = qMax(xmax, points[i+1].x());
 636         ymin = qMin(ymin, points[i+1].y());
 637         ymax = qMax(ymax, points[i+1].y());
 638
 639         y_next = FloatToQ27Dot5(points[i+1].y());
 640         x_next = FloatToQ27Dot5(points[i+1].x());
 641
 642         // skip vertices on top of each other
 643         if (v->x == x_next && v->y == y_next) {
 644             ++i;
 645             if (i < vertices.nPoints)
 646                 goto next_point;
 647             Vertex *v0 = vertices.storage;
 648             v0->flags &= ~(LineBeforeStarts|LineBeforeEnds|LineBeforeHorizontal);
 649             if (y_prev < y_curr)
 650                 v0->flags |= LineBeforeEnds;
 651             else if (y_prev > y_curr)
 652                 v0->flags |= LineBeforeStarts;
 653             else
 654                 v0->flags |= LineBeforeHorizontal;
 655             if ((v0->flags & (LineBeforeStarts|LineAfterStarts))
 656                 && !(v0->flags & (LineAfterEnds|LineBeforeEnds)))
 657                 *maxActiveEdges += 2;
 658             break;
 659         }
 660
 661         if (y_prev < y_curr)
 662             v->flags |= LineBeforeEnds;
 663         else if (y_prev > y_curr)
 664             v->flags |= LineBeforeStarts;
 665         else
 666             v->flags |= LineBeforeHorizontal;
 667
 668
 669         if (y_curr < y_next)
 670             v->flags |= LineAfterStarts;
 671         else if (y_curr > y_next)
 672             v->flags |= LineAfterEnds;
 673         else
 674             v->flags |= LineAfterHorizontal;
 675         // ### could probably get better limit by looping over sorted list and counting down on ending edges
 676         if ((v->flags & (LineBeforeStarts|LineAfterStarts))
 677             && !(v->flags & (LineAfterEnds|LineBeforeEnds)))
 678             *maxActiveEdges += 2;
 679         y_prev = y_curr;
 680         ++v;
 681         ++vv;
 682         ++j;
 683         ++i;
 684     }
 685     vertices.nPoints = j;
 686
 687     QDEBUG() << "maxActiveEdges=" << *maxActiveEdges;
 688     vv = vertices.sorted;
 689     qSort(vv, vv + vertices.nPoints, compareVertex);
 690
 691     return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
 692 }
 693
 694 struct QCoincidingEdge {
 695     QTessellatorPrivate::Vertex *start;
 696     QTessellatorPrivate::Vertex *end;
 697     bool used;
 698     bool before;
 699
 700     inline bool operator<(const QCoincidingEdge &e2) const
 701     {
 702         return end->y == e2.end->y ? end->x < e2.end->x : end->y < e2.end->y;
 703     }
 704 };
 705
 706 static void cancelEdges(QCoincidingEdge &e1, QCoincidingEdge &e2)
 707 {
 708     if (e1.before) {
 709         e1.start->flags &= ~(LineBeforeStarts|LineBeforeHorizontal);
 710         e1.end->flags &= ~(LineAfterEnds|LineAfterHorizontal);
 711     } else {
 712         e1.start->flags &= ~(LineAfterStarts|LineAfterHorizontal);
 713         e1.end->flags &= ~(LineBeforeEnds|LineBeforeHorizontal);
 714     }
 715     if (e2.before) {
 716         e2.start->flags &= ~(LineBeforeStarts|LineBeforeHorizontal);
 717         e2.end->flags &= ~(LineAfterEnds|LineAfterHorizontal);
 718     } else {
 719         e2.start->flags &= ~(LineAfterStarts|LineAfterHorizontal);
 720         e2.end->flags &= ~(LineBeforeEnds|LineBeforeHorizontal);
 721     }
 722     e1.used = e2.used = true;
 723 }
 724
 725 void QTessellatorPrivate::cancelCoincidingEdges()
 726 {
 727     Vertex **vv = vertices.sorted;
 728
 729     QCoincidingEdge *tl = 0;
 730     int tlSize = 0;
 731
 732     for (int i = 0; i < vertices.nPoints - 1; ++i) {
 733         Vertex *v = vv[i];
 734         int testListSize = 0;
 735         while (i < vertices.nPoints - 1) {
 736             Vertex *n = vv[i];
 737             if (v->x != n->x || v->y != n->y)
 738                 break;
 739
 740             if (testListSize > tlSize - 2) {
 741                 tlSize = qMax(tlSize*2, 16);
 742                 tl = q_check_ptr((QCoincidingEdge *)realloc(tl, tlSize*sizeof(QCoincidingEdge)));
 743             }
 744             if (n->flags & (LineBeforeStarts|LineBeforeHorizontal)) {
 745                 tl[testListSize].start = n;
 746                 tl[testListSize].end = vertices.prev(n);
 747                 tl[testListSize].used = false;
 748                 tl[testListSize].before = true;
 749                 ++testListSize;
 750             }
 751             if (n->flags & (LineAfterStarts|LineAfterHorizontal)) {
 752                 tl[testListSize].start = n;
 753                 tl[testListSize].end = vertices.next(n);
 754                 tl[testListSize].used = false;
 755                 tl[testListSize].before = false;
 756                 ++testListSize;
 757             }
 758             ++i;
 759         }
 760         if (!testListSize)
 761             continue;
 762
 763         qSort(tl, tl + testListSize);
 764
 765         for (int j = 0; j < testListSize; ++j) {
 766             if (tl[j].used)
 767                 continue;
 768
 769             for (int k = j + 1; k < testListSize; ++k) {
 770                 if (tl[j].end->x != tl[k].end->x
 771                     || tl[j].end->y != tl[k].end->y
 772                     || tl[k].used)
 773                     break;
 774
 775                 if (!winding || tl[j].before != tl[k].before) {
 776                     cancelEdges(tl[j], tl[k]);
 777                     break;
 778                 }
 779                 ++k;
 780             }
 781             ++j;
 782         }
 783     }
 784     free(tl);
 785 }
 786
 787
 788 void QTessellatorPrivate::emitEdges(QTessellator *tessellator)
 789 {
 790     //QDEBUG() << "TRAPS:";
 791     if (!scanline.old_size)
 792         return;
 793
 794     // emit edges
 795     if (winding) {
 796         // winding fill rule
 797         int w = 0;
 798
 799         scanline.old[0]->y_left = y;
 800
 801         for (int i = 0; i < scanline.old_size - 1; ++i) {
 802             Edge *left = scanline.old[i];
 803             Edge *right = scanline.old[i+1];
 804             w += left->winding;
 805 //             qDebug() << "i=" << i << "edge->winding=" << left->winding << "winding=" << winding;
 806             if (w == 0) {
 807                 left->y_right = y;
 808                 right->y_left = y;
 809             } else if (!emit_clever || left->mark || right->mark) {
 810                 Q27Dot5 top = qMax(left->y_right, right->y_left);
 811                 if (top != y) {
 812                     QTessellator::Trapezoid trap;
 813                     fillTrapezoid(top, y, left->edge, right->edge, vertices, &trap);
 814                     tessellator->addTrap(trap);
 815 //                     QDEBUG() << "    top=" << Q27Dot5ToDouble(top) << "left=" << left->edge << "right=" << right->edge;
 816                 }
 817                 right->y_left = y;
 818                 left->y_right = y;
 819             }
 820             left->mark = false;
 821         }
 822         if (scanline.old[scanline.old_size - 1]->mark) {
 823             scanline.old[scanline.old_size - 1]->y_right = y;
 824             scanline.old[scanline.old_size - 1]->mark = false;
 825         }
 826     } else {
 827         // odd-even fill rule
 828         for (int i = 0; i < scanline.old_size; i += 2) {
 829             Edge *left = scanline.old[i];
 830             Edge *right = scanline.old[i+1];
 831             if (!emit_clever || left->mark || right->mark) {
 832                 Q27Dot5 top = qMax(left->y_right, right->y_left);
 833                 if (top != y) {
 834                     QTessellator::Trapezoid trap;
 835                     fillTrapezoid(top, y, left->edge, right->edge, vertices, &trap);
 836                     tessellator->addTrap(trap);
 837                 }
 838 //                 QDEBUG() << "    top=" << Q27Dot5ToDouble(top) << "left=" << left->edge << "right=" << right->edge;
 839                 left->y_left = y;
 840                 left->y_right = y;
 841                 right->y_left = y;
 842                 right->y_right = y;
 843                 left->mark = right->mark = false;
 844             }
 845         }
 846     }
 847 }
 848
 849
 850 void QTessellatorPrivate::processIntersections()
 851 {
 852     QDEBUG() << "PROCESS INTERSECTIONS";
 853     // process intersections
 854     while (!intersections.isEmpty()) {
 855         Intersections::iterator it = intersections.begin();
 856         if (it.key().y != y)
 857             break;
 858
 859         // swap edges
 860         QDEBUG() << "    swapping intersecting edges ";
 861         int min = scanline.size;
 862         int max = 0;
 863         Q27Dot5 xmin = INT_MAX;
 864         Q27Dot5 xmax = INT_MIN;
 865         int num = 0;
 866         while (1) {
 867             const Intersection &i = it.key();
 868             int next = it->next;
 869
 870             int edgePos = scanline.findEdge(i.edge);
 871             if (edgePos >= 0) {
 872                 ++num;
 873                 min = qMin(edgePos, min);
 874                 max = qMax(edgePos, max);
 875                 Edge *edge = scanline.edges[edgePos];
 876                 xmin = qMin(xmin, edge->positionAt(y));
 877                 xmax = qMax(xmax, edge->positionAt(y));
 878             }
 879             Intersection key;
 880             key.y = y;
 881             key.edge = next;
 882             it = intersections.find(key);
 883             intersections.remove(i);
 884             if (it == intersections.end())
 885                 break;
 886         }
 887         if (num < 2)
 888             continue;
 889
 890         Q_ASSERT(min != max);
 891         QDEBUG() << "sorting between" << min << "and" << max << "xpos=" << xmin << xmax;
 892         while (min > 0 && scanline.edges[min - 1]->positionAt(y) >= xmin) {
 893             QDEBUG() << "    adding edge on left";
 894             --min;
 895         }
 896         while (max + 1 < scanline.size && scanline.edges[max + 1]->positionAt(y) <=  xmax) {
 897             QDEBUG() << "    adding edge on right";
 898             ++max;
 899         }
 900
 901         qSort(scanline.edges + min, scanline.edges + max + 1, EdgeSorter(y));
 902 #ifdef DEBUG
 903         for (int i = min; i <= max; ++i)
 904             QDEBUG() << "        " << scanline.edges[i]->edge << "at pos" << i;
 905 #endif
 906         for (int i = min; i <= max; ++i) {
 907             Edge *edge = scanline.edges[i];
 908             edge->intersect_left = true;
 909             edge->intersect_right = true;
 910             edge->mark = true;
 911         }
 912     }
 913 }
 914
 915 void QTessellatorPrivate::removeEdges()
 916 {
 917     int cv = currentVertex;
 918     while (cv < vertices.nPoints) {
 919         const Vertex *v = vertices.sorted[cv];
 920         if (v->y > y)
 921             break;
 922         if (v->flags & LineBeforeEnds) {
 923             QDEBUG() << "    removing edge" << vertices.prevPos(v);
 924             int pos = scanline.findEdge(vertices.prevPos(v));
 925             if (pos == -1)
 926                 continue;
 927             scanline.edges[pos]->mark = true;
 928             if (pos > 0)
 929                 scanline.edges[pos - 1]->intersect_right = true;
 930             if (pos < scanline.size - 1)
 931                 scanline.edges[pos + 1]->intersect_left = true;
 932             scanline.removeAt(pos);
 933         }
 934         if (v->flags & LineAfterEnds) {
 935             QDEBUG() << "    removing edge" << vertices.position(v);
 936             int pos = scanline.findEdge(vertices.position(v));
 937             if (pos == -1)
 938                 continue;
 939             scanline.edges[pos]->mark = true;
 940             if (pos > 0)
 941                 scanline.edges[pos - 1]->intersect_right = true;
 942             if (pos < scanline.size - 1)
 943                 scanline.edges[pos + 1]->intersect_left = true;
 944             scanline.removeAt(pos);
 945         }
 946         ++cv;
 947     }
 948 }
 949
 950 void QTessellatorPrivate::addEdges()
 951 {
 952     while (currentVertex < vertices.nPoints) {
 953         const Vertex *v = vertices.sorted[currentVertex];
 954         if (v->y > y)
 955             break;
 956         if (v->flags & LineBeforeStarts) {
 957             // add new edge
 958             int start = vertices.prevPos(v);
 959             Edge e(vertices, start);
 960             int pos = scanline.findEdgePosition(e);
 961             QDEBUG() << "    adding edge" << start << "at position" << pos;
 962             scanline.insert(pos, e);
 963             if (!mark_clever || !(v->flags & LineAfterEnds)) {
 964                 if (pos > 0)
 965                     scanline.edges[pos - 1]->mark = true;
 966                 if (pos < scanline.size - 1)
 967                     scanline.edges[pos + 1]->mark = true;
 968             }
 969         }
 970         if (v->flags & LineAfterStarts) {
 971             Edge e(vertices, vertices.position(v));
 972             int pos = scanline.findEdgePosition(e);
 973             QDEBUG() << "    adding edge" << vertices.position(v) << "at position" << pos;
 974             scanline.insert(pos, e);
 975             if (!mark_clever || !(v->flags & LineBeforeEnds)) {
 976                 if (pos > 0)
 977                     scanline.edges[pos - 1]->mark = true;
 978                 if (pos < scanline.size - 1)
 979                     scanline.edges[pos + 1]->mark = true;
 980             }
 981         }
 982         if (v->flags & LineAfterHorizontal) {
 983             int pos1 = scanline.findEdgePosition(v->x, v->y);
 984             const Vertex *next = vertices.next(v);
 985             Q_ASSERT(v->y == next->y);
 986             int pos2 = scanline.findEdgePosition(next->x, next->y);
 987             if (pos2 < pos1)
 988                 qSwap(pos1, pos2);
 989             if (pos1 > 0)
 990                 --pos1;
 991             if (pos2 == scanline.size)
 992                 --pos2;
 993             //QDEBUG() << "marking horizontal edge from " << pos1 << "to" << pos2;
 994             scanline.markEdges(pos1, pos2);
 995         }
 996         ++currentVertex;
 997     }
 998 }
 999
1000 #ifdef DEBUG
1001 static void checkLinkChain(const QTessellatorPrivate::Intersections &intersections,
1002                            QTessellatorPrivate::Intersection i)
1003 {
1004 //     qDebug() << "              Link chain: ";
1005     int end = i.edge;
1006     while (1) {
1007         QTessellatorPrivate::IntersectionLink l = intersections.value(i);
1008 //         qDebug() << "                     " << i.edge << "next=" << l.next << "prev=" << l.prev;
1009         if (l.next == end)
1010             break;
1011         Q_ASSERT(l.next != -1);
1012         Q_ASSERT(l.prev != -1);
1013
1014         QTessellatorPrivate::Intersection i2 = i;
1015         i2.edge = l.next;
1016         QTessellatorPrivate::IntersectionLink l2 = intersections.value(i2);
1017
1018         Q_ASSERT(l2.next != -1);
1019         Q_ASSERT(l2.prev != -1);
1020         Q_ASSERT(l.next == i2.edge);
1021         Q_ASSERT(l2.prev == i.edge);
1022         i = i2;
1023     }
1024 }
1025 #endif
1026
1027 bool QTessellatorPrivate::edgeInChain(Intersection i, int edge)
1028 {
1029     int end = i.edge;
1030     while (1) {
1031         if (i.edge == edge)
1032             return true;
1033         IntersectionLink l = intersections.value(i);
1034         if (l.next == end)
1035             break;
1036         Q_ASSERT(l.next != -1);
1037         Q_ASSERT(l.prev != -1);
1038
1039         Intersection i2 = i;
1040         i2.edge = l.next;
1041
1042 #ifndef QT_NO_DEBUG
1043         IntersectionLink l2 = intersections.value(i2);
1044         Q_ASSERT(l2.next != -1);
1045         Q_ASSERT(l2.prev != -1);
1046         Q_ASSERT(l.next == i2.edge);
1047         Q_ASSERT(l2.prev == i.edge);
1048 #endif
1049         i = i2;
1050     }
1051     return false;
1052 }
1053
1054
1055 void QTessellatorPrivate::addIntersection(const Edge *e1, const Edge *e2)
1056 {
1057     const IntersectionLink emptyLink = {-1, -1};
1058
1059     int next = vertices.nextPos(vertices[e1->edge]);
1060     if (e2->edge == next)
1061         return;
1062     int prev = vertices.prevPos(vertices[e1->edge]);
1063     if (e2->edge == prev)
1064         return;
1065
1066     Q27Dot5 yi;
1067     bool det_positive;
1068     bool isect = e1->intersect(*e2, &yi, &det_positive);
1069     QDEBUG("checking edges %d and %d", e1->edge, e2->edge);
1070     if (!isect) {
1071         QDEBUG() << "    no intersection";
1072         return;
1073     }
1074
1075     // don't emit an intersection if it's at the start of a line segment or above us
1076     if (yi <= y) {
1077         if (!det_positive)
1078             return;
1079         QDEBUG() << "        ----->>>>>> WRONG ORDER!";
1080         yi = y;
1081     }
1082     QDEBUG() << "   between edges " << e1->edge << "and" << e2->edge << "at point ("
1083              << Q27Dot5ToDouble(yi) << ')';
1084
1085     Intersection i1;
1086     i1.y = yi;
1087     i1.edge = e1->edge;
1088     IntersectionLink link1 = intersections.value(i1, emptyLink);
1089     Intersection i2;
1090     i2.y = yi;
1091     i2.edge = e2->edge;
1092     IntersectionLink link2 = intersections.value(i2, emptyLink);
1093
1094     // new pair of edges
1095     if (link1.next == -1 && link2.next == -1) {
1096         link1.next = link1.prev = i2.edge;
1097         link2.next = link2.prev = i1.edge;
1098     } else if (link1.next == i2.edge || link1.prev == i2.edge
1099                || link2.next == i1.edge || link2.prev == i1.edge) {
1100 #ifdef DEBUG
1101         checkLinkChain(intersections, i1);
1102         checkLinkChain(intersections, i2);
1103         Q_ASSERT(edgeInChain(i1, i2.edge));
1104 #endif
1105         return;
1106     } else if (link1.next == -1 || link2.next == -1) {
1107         if (link2.next == -1) {
1108             qSwap(i1, i2);
1109             qSwap(link1, link2);
1110         }
1111         Q_ASSERT(link1.next == -1);
1112 #ifdef DEBUG
1113         checkLinkChain(intersections, i2);
1114 #endif
1115         // only i2 in list
1116         link1.next = i2.edge;
1117         link1.prev = link2.prev;
1118         link2.prev = i1.edge;
1119         Intersection other;
1120         other.y = yi;
1121         other.edge = link1.prev;
1122         IntersectionLink link = intersections.value(other, emptyLink);
1123         Q_ASSERT(link.next == i2.edge);
1124         Q_ASSERT(link.prev != -1);
1125         link.next = i1.edge;
1126         intersections.insert(other, link);
1127     } else {
1128         bool connected = edgeInChain(i1, i2.edge);
1129         if (connected)
1130             return;
1131 #ifdef DEBUG
1132         checkLinkChain(intersections, i1);
1133         checkLinkChain(intersections, i2);
1134 #endif
1135         // both already in some list. Have to make sure they are connected
1136         // this can be done by cutting open the ring(s) after the two eges and
1137         // connecting them again
1138         Intersection other1;
1139         other1.y = yi;
1140         other1.edge = link1.next;
1141         IntersectionLink linko1 = intersections.value(other1, emptyLink);
1142         Intersection other2;
1143         other2.y = yi;
1144         other2.edge = link2.next;
1145         IntersectionLink linko2 = intersections.value(other2, emptyLink);
1146
1147         linko1.prev = i2.edge;
1148         link2.next = other1.edge;
1149
1150         linko2.prev = i1.edge;
1151         link1.next = other2.edge;
1152         intersections.insert(other1, linko1);
1153         intersections.insert(other2, linko2);
1154     }
1155     intersections.insert(i1, link1);
1156     intersections.insert(i2, link2);
1157 #ifdef DEBUG
1158     checkLinkChain(intersections, i1);
1159     checkLinkChain(intersections, i2);
1160     Q_ASSERT(edgeInChain(i1, i2.edge));
1161 #endif
1162     return;
1163
1164 }
1165
1166
1167 void QTessellatorPrivate::addIntersections()
1168 {
1169     if (scanline.size) {
1170         QDEBUG() << "INTERSECTIONS";
1171         // check marked edges for intersections
1172 #ifdef DEBUG
1173         for (int i = 0; i < scanline.size; ++i) {
1174             Edge *e = scanline.edges[i];
1175             QDEBUG() << "    " << i << e->edge << "isect=(" << e->intersect_left << e->intersect_right
1176                      << ')';
1177         }
1178 #endif
1179
1180         for (int i = 0; i < scanline.size - 1; ++i) {
1181             Edge *e1 = scanline.edges[i];
1182             Edge *e2 = scanline.edges[i + 1];
1183             // check for intersection
1184             if (e1->intersect_right || e2->intersect_left)
1185                 addIntersection(e1, e2);
1186         }
1187     }
1188 #if 0
1189     if (intersections.constBegin().key().y == y) {
1190         QDEBUG() << "----------------> intersection on same line";
1191         scanline.clearMarks();
1192         scanline.processIntersections(y, &intersections);
1193         goto redo;
1194     }
1195 #endif
1196 }
1197
1198
1199 QTessellator::QTessellator()
1200 {
1201     d = new QTessellatorPrivate;
1202 }
1203
1204 QTessellator::~QTessellator()
1205 {
1206     delete d;
1207 }
1208
1209 void QTessellator::setWinding(bool w)
1210 {
1211     d->winding = w;
1212 }
1213
1214
1215 QRectF QTessellator::tessellate(const QPointF *points, int nPoints)
1216 {
1217     Q_ASSERT(points[0] == points[nPoints-1]);
1218     --nPoints;
1219
1220 #ifdef DEBUG
1221     QDEBUG()<< "POINTS:";
1222     for (int i = 0; i < nPoints; ++i) {
1223         QDEBUG() << points[i];
1224     }
1225 #endif
1226
1227     // collect edges and calculate bounds
1228     d->vertices.nPoints = nPoints;
1229     d->vertices.init(nPoints);
1230
1231     int maxActiveEdges = 0;
1232     QRectF br = d->collectAndSortVertices(points, &maxActiveEdges);
1233     d->cancelCoincidingEdges();
1234
1235 #ifdef DEBUG
1236     QDEBUG() << "nPoints = " << nPoints << "using " << d->vertices.nPoints;
1237     QDEBUG()<< "VERTICES:";
1238     for (int i = 0; i < d->vertices.nPoints; ++i) {
1239         QDEBUG() << "    " << i << ": "
1240                  << "point=" << d->vertices.position(d->vertices.sorted[i])
1241                  << "flags=" << d->vertices.sorted[i]->flags
1242                  << "pos=(" << Q27Dot5ToDouble(d->vertices.sorted[i]->x) << '/'
1243                  << Q27Dot5ToDouble(d->vertices.sorted[i]->y) << ')';
1244     }
1245 #endif
1246
1247     d->scanline.init(maxActiveEdges);
1248     d->y = INT_MIN/256;
1249     d->currentVertex = 0;
1250
1251     while (d->currentVertex < d->vertices.nPoints) {
1252         d->scanline.clearMarks();
1253
1254         d->y = d->vertices.sorted[d->currentVertex]->y;
1255         if (!d->intersections.isEmpty())
1256             d->y = qMin(d->y, d->intersections.constBegin().key().y);
1257
1258         QDEBUG()<< "===== SCANLINE: y =" << Q27Dot5ToDouble(d->y) << " =====";
1259
1260         d->scanline.prepareLine();
1261         d->processIntersections();
1262         d->removeEdges();
1263         d->addEdges();
1264         d->addIntersections();
1265         d->emitEdges(this);
1266         d->scanline.lineDone();
1267
1268 #ifdef DEBUG
1269         QDEBUG()<< "===== edges:";
1270         for (int i = 0; i < d->scanline.size; ++i) {
1271             QDEBUG() << "   " << d->scanline.edges[i]->edge
1272                      << "p0= (" << Q27Dot5ToDouble(d->scanline.edges[i]->v0->x)
1273                      << '/' << Q27Dot5ToDouble(d->scanline.edges[i]->v0->y)
1274                      << ") p1= (" << Q27Dot5ToDouble(d->scanline.edges[i]->v1->x)
1275                      << '/' << Q27Dot5ToDouble(d->scanline.edges[i]->v1->y) << ')'
1276                      << "x=" << Q27Dot5ToDouble(d->scanline.edges[i]->positionAt(d->y))
1277                      << "isLeftOfNext="
1278                      << ((i < d->scanline.size - 1)
1279                          ? d->scanline.edges[i]->isLeftOf(*d->scanline.edges[i+1], d->y)
1280                          : true);
1281         }
1282 #endif
1283 }
1284
1285     d->scanline.done();
1286     d->intersections.clear();
1287     return br;
1288 }
1289
1290 // tessellates the given convex polygon
1291 void QTessellator::tessellateConvex(const QPointF *points, int nPoints)
1292 {
1293     Q_ASSERT(points[0] == points[nPoints-1]);
1294     --nPoints;
1295
1296     d->vertices.nPoints = nPoints;
1297     d->vertices.init(nPoints);
1298
1299     for (int i = 0; i < nPoints; ++i) {
1300         d->vertices[i]->x = FloatToQ27Dot5(points[i].x());
1301         d->vertices[i]->y = FloatToQ27Dot5(points[i].y());
1302     }
1303
1304     int left = 0, right = 0;
1305
1306     int top = 0;
1307     for (int i = 1; i < nPoints; ++i) {
1308         if (d->vertices[i]->y < d->vertices[top]->y)
1309             top = i;
1310     }
1311
1312     left = (top + nPoints - 1) % nPoints;
1313     right = (top + 1) % nPoints;
1314
1315     while (d->vertices[left]->x == d->vertices[top]->x && d->vertices[left]->y == d->vertices[top]->y && left != right)
1316         left = (left + nPoints - 1) % nPoints;
1317
1318     while (d->vertices[right]->x == d->vertices[top]->x && d->vertices[right]->y == d->vertices[top]->y && left != right)
1319         right = (right + 1) % nPoints;
1320
1321     if (left == right)
1322         return;
1323
1324     int dir = 1;
1325
1326     Vertex dLeft = { d->vertices[top]->x - d->vertices[left]->x,
1327                      d->vertices[top]->y - d->vertices[left]->y };
1328
1329     Vertex dRight = { d->vertices[right]->x - d->vertices[top]->x,
1330                       d->vertices[right]->y - d->vertices[top]->y };
1331
1332     Q27Dot5 cross = dLeft.x * dRight.y - dLeft.y * dRight.x;
1333
1334     // flip direction if polygon is clockwise
1335     if (cross < 0 || (cross == 0 && dLeft.x > 0)) {
1336         qSwap(left, right);
1337         dir = -1;
1338     }
1339
1340     Vertex *lastLeft = d->vertices[top];
1341     Vertex *lastRight = d->vertices[top];
1342
1343     QTessellator::Trapezoid trap;
1344
1345     while (lastLeft->y == d->vertices[left]->y && left != right) {
1346         lastLeft = d->vertices[left];
1347         left = (left + nPoints - dir) % nPoints;
1348     }
1349
1350     while (lastRight->y == d->vertices[right]->y && left != right) {
1351         lastRight = d->vertices[right];
1352         right = (right + nPoints + dir) % nPoints;
1353     }
1354
1355     while (true) {
1356         trap.top = qMax(lastRight->y, lastLeft->y);
1357         trap.bottom = qMin(d->vertices[left]->y, d->vertices[right]->y);
1358         trap.topLeft = lastLeft;
1359         trap.topRight = lastRight;
1360         trap.bottomLeft = d->vertices[left];
1361         trap.bottomRight = d->vertices[right];
1362
1363         if (trap.bottom > trap.top)
1364             addTrap(trap);
1365
1366         if (left == right)
1367             break;
1368
1369         if (d->vertices[right]->y < d->vertices[left]->y) {
1370             do {
1371                 lastRight = d->vertices[right];
1372                 right = (right + nPoints + dir) % nPoints;
1373             }
1374             while (lastRight->y == d->vertices[right]->y && left != right);
1375         } else {
1376             do {
1377                 lastLeft = d->vertices[left];
1378                 left = (left + nPoints - dir) % nPoints;
1379             }
1380             while (lastLeft->y == d->vertices[left]->y && left != right);
1381         }
1382     }
1383 }
1384
1385 // tessellates the stroke of the line from a_ to b_ with the given width and a flat cap
1386 void QTessellator::tessellateRect(const QPointF &a_, const QPointF &b_, qreal width)
1387 {
1388     Vertex a = { FloatToQ27Dot5(a_.x()), FloatToQ27Dot5(a_.y()) };
1389     Vertex b = { FloatToQ27Dot5(b_.x()), FloatToQ27Dot5(b_.y()) };
1390
1391     QPointF pa = a_, pb = b_;
1392
1393     if (a.y > b.y) {
1394         qSwap(a, b);
1395         qSwap(pa, pb);
1396     }
1397
1398     Vertex delta = { b.x - a.x, b.y - a.y };
1399
1400     if (delta.x == 0 && delta.y == 0)
1401         return;
1402
1403     qreal hw = 0.5 * width;
1404
1405     if (delta.x == 0) {
1406         Q27Dot5 halfWidth = FloatToQ27Dot5(hw);
1407
1408         if (halfWidth == 0)
1409             return;
1410
1411         Vertex topLeft = { a.x - halfWidth, a.y };
1412         Vertex topRight = { a.x + halfWidth, a.y };
1413         Vertex bottomLeft = { a.x - halfWidth, b.y };
1414         Vertex bottomRight = { a.x + halfWidth, b.y };
1415
1416         QTessellator::Trapezoid trap = { topLeft.y, bottomLeft.y, &topLeft, &bottomLeft, &topRight, &bottomRight };
1417         addTrap(trap);
1418     } else if (delta.y == 0) {
1419         Q27Dot5 halfWidth = FloatToQ27Dot5(hw);
1420
1421         if (halfWidth == 0)
1422             return;
1423
1424         if (a.x > b.x)
1425             qSwap(a.x, b.x);
1426
1427         Vertex topLeft = { a.x, a.y - halfWidth };
1428         Vertex topRight = { b.x, a.y - halfWidth };
1429         Vertex bottomLeft = { a.x, a.y + halfWidth };
1430         Vertex bottomRight = { b.x, a.y + halfWidth };
1431
1432         QTessellator::Trapezoid trap = { topLeft.y, bottomLeft.y, &topLeft, &bottomLeft, &topRight, &bottomRight };
1433         addTrap(trap);
1434     } else {
1435         QPointF perp(pb.y() - pa.y(), pa.x() - pb.x());
1436         qreal length = qSqrt(perp.x() * perp.x() + perp.y() * perp.y());
1437
1438         if (qFuzzyIsNull(length))
1439             return;
1440
1441         // need the half of the width
1442         perp *= hw / length;
1443
1444         QPointF pta = pa + perp;
1445         QPointF ptb = pa - perp;
1446         QPointF ptc = pb - perp;
1447         QPointF ptd = pb + perp;
1448
1449         Vertex ta = { FloatToQ27Dot5(pta.x()), FloatToQ27Dot5(pta.y()) };
1450         Vertex tb = { FloatToQ27Dot5(ptb.x()), FloatToQ27Dot5(ptb.y()) };
1451         Vertex tc = { FloatToQ27Dot5(ptc.x()), FloatToQ27Dot5(ptc.y()) };
1452         Vertex td = { FloatToQ27Dot5(ptd.x()), FloatToQ27Dot5(ptd.y()) };
1453
1454         if (ta.y < tb.y) {
1455             if (tb.y < td.y) {
1456                 QTessellator::Trapezoid top = { ta.y, tb.y, &ta, &tb, &ta, &td };
1457                 QTessellator::Trapezoid bottom = { td.y, tc.y, &tb, &tc, &td, &tc };
1458                 addTrap(top);
1459                 addTrap(bottom);
1460
1461                 QTessellator::Trapezoid middle = { tb.y, td.y, &tb, &tc, &ta, &td };
1462                 addTrap(middle);
1463             } else {
1464                 QTessellator::Trapezoid top = { ta.y, td.y, &ta, &tb, &ta, &td };
1465                 QTessellator::Trapezoid bottom = { tb.y, tc.y, &tb, &tc, &td, &tc };
1466                 addTrap(top);
1467                 addTrap(bottom);
1468
1469                 if (tb.y != td.y) {
1470                     QTessellator::Trapezoid middle = { td.y, tb.y, &ta, &tb, &td, &tc };
1471                     addTrap(middle);
1472                 }
1473             }
1474         } else {
1475             if (ta.y < tc.y) {
1476                 QTessellator::Trapezoid top = { tb.y, ta.y, &tb, &tc, &tb, &ta };
1477                 QTessellator::Trapezoid bottom = { tc.y, td.y, &tc, &td, &ta, &td };
1478                 addTrap(top);
1479                 addTrap(bottom);
1480
1481                 QTessellator::Trapezoid middle = { ta.y, tc.y, &tb, &tc, &ta, &td };
1482                 addTrap(middle);
1483             } else {
1484                 QTessellator::Trapezoid top = { tb.y, tc.y, &tb, &tc, &tb, &ta };
1485                 QTessellator::Trapezoid bottom = { ta.y, td.y, &tc, &td, &ta, &td };
1486                 addTrap(top);
1487                 addTrap(bottom);
1488
1489                 if (ta.y != tc.y) {
1490                     QTessellator::Trapezoid middle = { tc.y, ta.y, &tc, &td, &tb, &ta };
1491                     addTrap(middle);
1492                 }
1493             }
1494         }
1495     }
1496 }
1497
1498 QT_END_NAMESPACE