Replace 'i < len-1 && func(i+1)' by 'i+1 < len && func(i+1)'
[profile/ivi/qtbase.git] / 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