1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 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 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    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 < scanline.size - 1 && 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