source: trunk/src/gui/painting/qtessellator.cpp

Last change on this file was 846, checked in by Dmitry A. Kuminov, 14 years ago

trunk: Merged in qt 4.7.2 sources from branches/vendor/nokia/qt.
File size: 44.0 KB
Line 
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** Commercial Usage
11** Licensees holding valid Qt Commercial licenses may use this file in
12** accordance with the Qt Commercial License Agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and Nokia.
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** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you have questions regarding the use of this file, please contact
37** Nokia at qt-info@nokia.com.
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
51QT_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
60static const bool emit_clever = true;
61static const bool mark_clever = false;
62
63enum VertexFlags {
64 LineBeforeStarts = 0x1,
65 LineBeforeEnds = 0x2,
66 LineBeforeHorizontal = 0x4,
67 LineAfterStarts = 0x8,
68 LineAfterEnds = 0x10,
69 LineAfterHorizontal = 0x20
70};
71
72
73
74class QTessellatorPrivate {
75public:
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
235private:
236 void addIntersection(const Edge *e1, const Edge *e2);
237 bool edgeInChain(Intersection i, int edge);
238};
239
240
241QTessellatorPrivate::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
280static inline bool sameSign(qint64 a, qint64 b) {
281 return (((qint64) ((quint64) a ^ (quint64) b)) >= 0 );
282}
283
284bool 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
334bool 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
368static 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
379Q27Dot5 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
390bool QTessellatorPrivate::EdgeSorter::operator() (const Edge *e1, const Edge *e2)
391{
392 return e1->isLeftOf(*e2, y);
393}
394
395
396QTessellatorPrivate::Scanline::Scanline()
397{
398 edges = 0;
399 edge_table = 0;
400 old = 0;
401}
402
403void 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
421void 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
433QTessellatorPrivate::Scanline::~Scanline()
434{
435 free(edges);
436 free(old);
437 free(edge_table);
438}
439
440int 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
456int 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
474int 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
485void 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
494void 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
507void 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
520void 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
531void 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
539void 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
549QTessellatorPrivate::Vertices::Vertices()
550{
551 storage = 0;
552 sorted = 0;
553 allocated = 0;
554 nPoints = 0;
555}
556
557QTessellatorPrivate::Vertices::~Vertices()
558{
559 if (storage) {
560 free(storage);
561 free(sorted);
562 }
563}
564
565void 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
575void 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
588static 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
606QRectF 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
694struct 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
706static 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
725void 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
788void 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
850void 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
915void 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
950void 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
1001static 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
1027bool 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
1055void 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
1167void 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
1199QTessellator::QTessellator()
1200{
1201 d = new QTessellatorPrivate;
1202}
1203
1204QTessellator::~QTessellator()
1205{
1206 delete d;
1207}
1208
1209void QTessellator::setWinding(bool w)
1210{
1211 d->winding = w;
1212}
1213
1214
1215QRectF 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
1291void 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
1386void 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
1498QT_END_NAMESPACE
Note: See TracBrowser for help on using the repository browser.