Qt 4.8
qtessellator.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtGui module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia. For licensing terms and
14 ** conditions see http://qt.digia.com/licensing. For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights. These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file. Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
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 
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 
68  LineAfterEnds = 0x10,
70 };
71 
72 
73 
75 public:
76  struct Vertices;
77 
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  {
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  };
105  {
106  int next;
107  int prev;
108  };
110 
111  struct Edge {
112  Edge(const Vertices &v, int _edge);
113  int edge;
114  const Vertex *v0;
115  const Vertex *v1;
118  signed int winding : 8;
119  bool mark;
120  bool free;
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 
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 
163  int old_size;
164 
166  int size;
167 
168  private:
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();
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  }
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  }
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;
227  };
229  Intersections intersections;
231  bool winding;
234 
235 private:
236  void addIntersection(const Edge *e1, const Edge *e2);
237  bool edgeInChain(Intersection i, int edge);
238 };
239 
240 
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 
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 
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 
391 {
392  return e1->isLeftOf(*e2, y);
393 }
394 
395 
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 
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 
434 {
435  free(edges);
436  free(old);
437  free(edge_table);
438 }
439 
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 
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 
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 
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 
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 
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 
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 
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 
540 {
541  if (pos2 < pos1)
542  return;
543 
544  for (int i = pos1; i <= pos2; ++i)
545  edges[i]->mark = true;
546 }
547 
548 
550 {
551  storage = 0;
552  sorted = 0;
553  allocated = 0;
554  nPoints = 0;
555 }
556 
558 {
559  if (storage) {
560  free(storage);
561  free(sorted);
562  }
563 }
564 
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 
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,
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;
649  if (y_prev < y_curr)
650  v0->flags |= LineBeforeEnds;
651  else if (y_prev > y_curr)
652  v0->flags |= LineBeforeStarts;
653  else
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
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
675  // ### could probably get better limit by looping over sorted list and counting down on ending edges
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 
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 
707 {
708  if (e1.before) {
711  } else {
714  }
715  if (e2.before) {
718  } else {
721  }
722  e1.used = e2.used = true;
723 }
724 
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  }
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  }
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 
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) {
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) {
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) {
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 
851 {
852  QDEBUG() << "PROCESS INTERSECTIONS";
853  // process intersections
854  while (!intersections.isEmpty()) {
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  }
880  key.y = y;
881  key.edge = next;
882  it = intersections.find(key);
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 
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 
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) {
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,
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 
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 
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 
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 
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 
1200 {
1201  d = new QTessellatorPrivate;
1202 }
1203 
1205 {
1206  delete d;
1207 }
1208 
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 
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 = qreal(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 
double d
Definition: qnumeric_p.h:62
T * q_check_ptr(T *p)
Definition: qglobal.h:1857
void init(int maxActiveEdges)
void markEdges(int pos1, int pos2)
const Vertex * topRight
double qreal
Definition: qglobal.h:1193
Q_DECL_CONSTEXPR const T & qMin(const T &a, const T &b)
Definition: qglobal.h:1215
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
QTessellatorPrivate::Vertex * end
#define it(className, varName)
static const bool emit_clever
The QPointF class defines a point in the plane using floating point precision.
Definition: qpoint.h:214
const Vertex * bottomLeft
VertexFlags
#define Q27Dot5ToDouble(i)
QRectF tessellate(const QPointF *points, int nPoints)
int findEdgePosition(Q27Dot5 x, Q27Dot5 y) const
QTessellatorPrivate::Vertex * start
static bool compareVertex(const QTessellatorPrivate::Vertex *p1, const QTessellatorPrivate::Vertex *p2)
long ASN1_INTEGER_get ASN1_INTEGER * a
int nextPos(const Vertex *v) const
int position(const Vertex *v) const
iterator find(const Key &key)
Returns an iterator pointing to the item with key key in the map.
Definition: qmap.h:618
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
bool edgeInChain(Intersection i, int edge)
bool operator<(int priority, const QPair< QRunnable *, int > &p)
Definition: qthreadpool.cpp:50
bool operator()(const Edge *e1, const Edge *e2)
Q_CORE_EXPORT QTextStream & right(QTextStream &s)
#define FloatToQ27Dot5(i)
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
qreal x() const
Returns the x-coordinate of this point.
Definition: qpoint.h:282
virtual ~QTessellator()
#define QDEBUG
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
static QIntfbScreen * connected
bool intersect(const Edge &other, Q27Dot5 *y, bool *det_positive) const
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
static void fillTrapezoid(Q27Dot5 y1, Q27Dot5 y2, int left, int right, const QTessellatorPrivate::Vertices &vertices, QTessellator::Trapezoid *trap)
static void cancelEdges(QCoincidingEdge &e1, QCoincidingEdge &e2)
unsigned __int64 quint64
Definition: qglobal.h:943
static bool init
Edge(const Vertices &v, int _edge)
const T value(const Key &key) const
Returns the value associated with the key key.
Definition: qmap.h:499
void emitEdges(QTessellator *tessellator)
__int64 qint64
Definition: qglobal.h:942
const Vertex * bottomRight
void init(int maxVertices)
const Vertex * prev(const Vertex *v) const
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the map.
Definition: qmap.h:374
Q27Dot5 positionAt(Q27Dot5 y) const
int Q27Dot5
void qSort(RandomAccessIterator start, RandomAccessIterator end)
Definition: qalgorithms.h:177
void setWinding(bool w)
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
static int perp(bool vertical, const QSize &size)
iterator begin()
Returns an STL-style iterator pointing to the first item in the map.
Definition: qmap.h:372
int remove(const Key &key)
Removes all the items that have the key key from the map.
Definition: qmap.h:662
const Vertex * topLeft
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the map...
Definition: qmap.h:375
static bool sameSign(qint64 a, qint64 b)
Intersections intersections
iterator insert(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
Definition: qmap.h:559
int prevPos(const Vertex *v) const
int key
bool isEmpty() const
Returns true if the map contains no items; otherwise returns false.
Definition: qmap.h:203
bool operator<(const QCoincidingEdge &e2) const
QFactoryLoader * l
QRectF collectAndSortVertices(const QPointF *points, int *maxActiveEdges)
int findEdge(int edge) const
qreal y() const
Returns the y-coordinate of this point.
Definition: qpoint.h:287
static Q_DECL_CONSTEXPR bool qFuzzyIsNull(double d)
Definition: qglobal.h:2043
static const bool mark_clever
virtual void addTrap(const Trapezoid &trap)=0
bool isLeftOf(const Edge &other, Q27Dot5 y) const
void tessellateRect(const QPointF &a, const QPointF &b, qreal width)
void tessellateConvex(const QPointF *points, int nPoints)
QMap< Intersection, IntersectionLink > Intersections
void swap(int p1, int p2)
static const KeyPair *const end
void addIntersection(const Edge *e1, const Edge *e2)
Q_CORE_EXPORT QTextStream & left(QTextStream &s)
void insert(int pos, const Edge &e)
qreal qSqrt(qreal v)
Definition: qmath.h:205
#define INT_MAX
const Vertex * next(const Vertex *v) const