src/gui/painting/qrasterizer.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 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 "qrasterizer_p.h"
  43
  44 #include <QPoint>
  45 #include <QRect>
  46
  47 #include <private/qmath_p.h>
  48 #include <private/qdatabuffer_p.h>
  49 #include <private/qdrawhelper_p.h>
  50
  51 QT_BEGIN_NAMESPACE
  52
  53 typedef int Q16Dot16;
  54 #define Q16Dot16ToFloat(i) ((i)/65536.)
  55 #define FloatToQ16Dot16(i) (int)((i) * 65536.)
  56 #define IntToQ16Dot16(i) ((i) << 16)
  57 #define Q16Dot16ToInt(i) ((i) >> 16)
  58 #define Q16Dot16Factor 65536
  59
  60 #define Q16Dot16Multiply(x, y) (int)((qlonglong(x) * qlonglong(y)) >> 16)
  61 #define Q16Dot16FastMultiply(x, y) (((x) * (y)) >> 16)
  62
  63 #define SPAN_BUFFER_SIZE 256
  64
  65 #define COORD_ROUNDING 1 // 0: round up, 1: round down
  66 #define COORD_OFFSET 32 // 26.6, 32 is half a pixel
  67
  68 static inline QT_FT_Vector PointToVector(const QPointF &p)
  69 {
  70     QT_FT_Vector result = { QT_FT_Pos(p.x() * 64), QT_FT_Pos(p.y() * 64) };
  71     return result;
  72 }
  73
  74 class QSpanBuffer {
  75 public:
  76     QSpanBuffer(ProcessSpans blend, void *data, const QRect &clipRect)
  77         : m_spanCount(0)
  78         , m_blend(blend)
  79         , m_data(data)
  80         , m_clipRect(clipRect)
  81     {
  82     }
  83
  84     ~QSpanBuffer()
  85     {
  86         flushSpans();
  87     }
  88
  89     void addSpan(int x, unsigned int len, int y, unsigned char coverage)
  90     {
  91         if (!coverage || !len)
  92             return;
  93
  94         Q_ASSERT(y >= m_clipRect.top());
  95         Q_ASSERT(y <= m_clipRect.bottom());
  96         Q_ASSERT(x >= m_clipRect.left());
  97         Q_ASSERT(x + int(len) - 1 <= m_clipRect.right());
  98
  99         m_spans[m_spanCount].x = x;
 100         m_spans[m_spanCount].len = len;
 101         m_spans[m_spanCount].y = y;
 102         m_spans[m_spanCount].coverage = coverage;
 103
 104         if (++m_spanCount == SPAN_BUFFER_SIZE)
 105             flushSpans();
 106     }
 107
 108 private:
 109     void flushSpans()
 110     {
 111         m_blend(m_spanCount, m_spans, m_data);
 112         m_spanCount = 0;
 113     }
 114
 115     QT_FT_Span m_spans[SPAN_BUFFER_SIZE];
 116     int m_spanCount;
 117
 118     ProcessSpans m_blend;
 119     void *m_data;
 120
 121     QRect m_clipRect;
 122 };
 123
 124 #define CHUNK_SIZE 64
 125 class QScanConverter
 126 {
 127 public:
 128     QScanConverter();
 129     ~QScanConverter();
 130
 131     void begin(int top, int bottom, int left, int right,
 132                Qt::FillRule fillRule, bool legacyRounding, QSpanBuffer *spanBuffer);
 133     void end();
 134
 135     void mergeCurve(const QT_FT_Vector &a, const QT_FT_Vector &b,
 136                     const QT_FT_Vector &c, const QT_FT_Vector &d);
 137     void mergeLine(QT_FT_Vector a, QT_FT_Vector b);
 138
 139     struct Line
 140     {
 141         Q16Dot16 x;
 142         Q16Dot16 delta;
 143
 144         int top, bottom;
 145
 146         int winding;
 147     };
 148
 149 private:
 150     struct Intersection
 151     {
 152         int x;
 153         int winding;
 154
 155         int left, right;
 156     };
 157
 158     inline bool clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding);
 159     inline void mergeIntersection(Intersection *head, const Intersection &isect);
 160
 161     void prepareChunk();
 162
 163     void emitNode(const Intersection *node);
 164     void emitSpans(int chunk);
 165
 166     inline void allocate(int size);
 167
 168     QDataBuffer<Line> m_lines;
 169
 170     int m_alloc;
 171     int m_size;
 172
 173     int m_top;
 174     int m_bottom;
 175
 176     Q16Dot16 m_leftFP;
 177     Q16Dot16 m_rightFP;
 178
 179     int m_fillRuleMask;
 180     bool m_legacyRounding;
 181
 182     int m_x;
 183     int m_y;
 184     int m_winding;
 185
 186     Intersection *m_intersections;
 187
 188     QSpanBuffer *m_spanBuffer;
 189
 190     QDataBuffer<Line *> m_active;
 191
 192     template <typename T>
 193     friend void qScanConvert(QScanConverter &d, T allVertical);
 194 };
 195
 196 class QRasterizerPrivate
 197 {
 198 public:
 199     bool antialiased;
 200     bool legacyRounding;
 201     ProcessSpans blend;
 202     void *data;
 203     QRect clipRect;
 204
 205     QScanConverter scanConverter;
 206 };
 207
 208 QScanConverter::QScanConverter()
 209    : m_lines(0)
 210    , m_alloc(0)
 211    , m_size(0)
 212    , m_intersections(0)
 213    , m_active(0)
 214 {
 215 }
 216
 217 QScanConverter::~QScanConverter()
 218 {
 219     if (m_intersections)
 220         free(m_intersections);
 221 }
 222
 223 void QScanConverter::begin(int top, int bottom, int left, int right,
 224                            Qt::FillRule fillRule, bool legacyRounding,
 225                            QSpanBuffer *spanBuffer)
 226 {
 227     m_top = top;
 228     m_bottom = bottom;
 229     m_leftFP = IntToQ16Dot16(left);
 230     m_rightFP = IntToQ16Dot16(right + 1);
 231
 232     m_lines.reset();
 233
 234     m_fillRuleMask = fillRule == Qt::WindingFill ? ~0x0 : 0x1;
 235     m_legacyRounding = legacyRounding;
 236     m_spanBuffer = spanBuffer;
 237 }
 238
 239 void QScanConverter::prepareChunk()
 240 {
 241     m_size = CHUNK_SIZE;
 242
 243     allocate(CHUNK_SIZE);
 244     memset(m_intersections, 0, CHUNK_SIZE * sizeof(Intersection));
 245 }
 246
 247 void QScanConverter::emitNode(const Intersection *node)
 248 {
 249 tail_call:
 250     if (node->left)
 251         emitNode(node + node->left);
 252
 253     if (m_winding & m_fillRuleMask)
 254         m_spanBuffer->addSpan(m_x, node->x - m_x, m_y, 0xff);
 255
 256     m_x = node->x;
 257     m_winding += node->winding;
 258
 259     if (node->right) {
 260         node += node->right;
 261         goto tail_call;
 262     }
 263 }
 264
 265 void QScanConverter::emitSpans(int chunk)
 266 {
 267     for (int dy = 0; dy < CHUNK_SIZE; ++dy) {
 268         m_x = 0;
 269         m_y = chunk + dy;
 270         m_winding = 0;
 271
 272         emitNode(&m_intersections[dy]);
 273     }
 274 }
 275
 276 // split control points b[0] ... b[3] into
 277 // left (b[0] ... b[3]) and right (b[3] ... b[6])
 278 static void split(QT_FT_Vector *b)
 279 {
 280     b[6] = b[3];
 281
 282     {
 283         const QT_FT_Pos temp = (b[1].x + b[2].x)/2;
 284
 285         b[1].x = (b[0].x + b[1].x)/2;
 286         b[5].x = (b[2].x + b[3].x)/2;
 287         b[2].x = (b[1].x + temp)/2;
 288         b[4].x = (b[5].x + temp)/2;
 289         b[3].x = (b[2].x + b[4].x)/2;
 290     }
 291     {
 292         const QT_FT_Pos temp = (b[1].y + b[2].y)/2;
 293
 294         b[1].y = (b[0].y + b[1].y)/2;
 295         b[5].y = (b[2].y + b[3].y)/2;
 296         b[2].y = (b[1].y + temp)/2;
 297         b[4].y = (b[5].y + temp)/2;
 298         b[3].y = (b[2].y + b[4].y)/2;
 299     }
 300 }
 301
 302 static inline bool topOrder(const QScanConverter::Line &a, const QScanConverter::Line &b)
 303 {
 304     return a.top < b.top;
 305 }
 306
 307 static inline bool xOrder(const QScanConverter::Line *a, const QScanConverter::Line *b)
 308 {
 309     return a->x < b->x;
 310 }
 311
 312 template <bool B>
 313 struct QBoolToType
 314 {
 315     inline bool operator()() const
 316     {
 317         return B;
 318     }
 319 };
 320
 321 // should be a member function but VC6 doesn't support member template functions
 322 template <typename T>
 323 void qScanConvert(QScanConverter &d, T allVertical)
 324 {
 325     if (!d.m_lines.size()) {
 326         d.m_active.reset();
 327         return;
 328     }
 329     qSort(d.m_lines.data(), d.m_lines.data() + d.m_lines.size(), QT_PREPEND_NAMESPACE(topOrder));
 330     int line = 0;
 331     for (int y = d.m_lines.first().top; y <= d.m_bottom; ++y) {
 332         for (; line < d.m_lines.size() && d.m_lines.at(line).top == y; ++line) {
 333             // add node to active list
 334             if (allVertical()) {
 335                 QScanConverter::Line *l = &d.m_lines.at(line);
 336                 d.m_active.resize(d.m_active.size() + 1);
 337                 int j;
 338                 for (j = d.m_active.size() - 2; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(l, d.m_active.at(j)); --j)
 339                     d.m_active.at(j+1) = d.m_active.at(j);
 340                 d.m_active.at(j+1) = l;
 341             } else {
 342                 d.m_active << &d.m_lines.at(line);
 343             }
 344         }
 345
 346         int numActive = d.m_active.size();
 347         if (!allVertical()) {
 348         // use insertion sort instead of qSort, as the active edge list is quite small
 349         // and in the average case already sorted
 350             for (int i = 1; i < numActive; ++i) {
 351                 QScanConverter::Line *l = d.m_active.at(i);
 352                 int j;
 353                 for (j = i-1; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(l, d.m_active.at(j)); --j)
 354                     d.m_active.at(j+1) = d.m_active.at(j);
 355                 d.m_active.at(j+1) = l;
 356             }
 357         }
 358
 359         int x = 0;
 360         int winding = 0;
 361         for (int i = 0; i < numActive; ++i) {
 362             QScanConverter::Line *node = d.m_active.at(i);
 363
 364             const int current = Q16Dot16ToInt(node->x);
 365             if (winding & d.m_fillRuleMask)
 366                 d.m_spanBuffer->addSpan(x, current - x, y, 0xff);
 367
 368             x = current;
 369             winding += node->winding;
 370
 371             if (node->bottom == y) {
 372                 // remove node from active list
 373                 for (int j = i; j < numActive - 1; ++j)
 374                     d.m_active.at(j) = d.m_active.at(j+1);
 375
 376                 d.m_active.resize(--numActive);
 377                 --i;
 378             } else if (!allVertical())
 379                 node->x += node->delta;
 380         }
 381     }
 382     d.m_active.reset();
 383 }
 384
 385 void QScanConverter::end()
 386 {
 387     if (m_lines.isEmpty())
 388         return;
 389
 390     if (m_lines.size() <= 32) {
 391         bool allVertical = true;
 392         for (int i = 0; i < m_lines.size(); ++i) {
 393             if (m_lines.at(i).delta) {
 394                 allVertical = false;
 395                 break;
 396             }
 397         }
 398         if (allVertical)
 399             qScanConvert(*this, QBoolToType<true>());
 400         else
 401             qScanConvert(*this, QBoolToType<false>());
 402     } else {
 403         for (int chunkTop = m_top; chunkTop <= m_bottom; chunkTop += CHUNK_SIZE) {
 404             prepareChunk();
 405
 406             Intersection isect = { 0, 0, 0, 0 };
 407
 408             const int chunkBottom = chunkTop + CHUNK_SIZE;
 409             for (int i = 0; i < m_lines.size(); ++i) {
 410                 Line &line = m_lines.at(i);
 411
 412                 if ((line.bottom < chunkTop) || (line.top > chunkBottom))
 413                     continue;
 414
 415                 const int top = qMax(0, line.top - chunkTop);
 416                 const int bottom = qMin(CHUNK_SIZE, line.bottom + 1 - chunkTop);
 417                 allocate(m_size + bottom - top);
 418
 419                 isect.winding = line.winding;
 420
 421                 Intersection *it = m_intersections + top;
 422                 Intersection *end = m_intersections + bottom;
 423
 424                 if (line.delta) {
 425                     for (; it != end; ++it) {
 426                         isect.x = Q16Dot16ToInt(line.x);
 427                         line.x += line.delta;
 428                         mergeIntersection(it, isect);
 429                     }
 430                 } else {
 431                     isect.x = Q16Dot16ToInt(line.x);
 432                     for (; it != end; ++it)
 433                         mergeIntersection(it, isect);
 434                 }
 435             }
 436
 437             emitSpans(chunkTop);
 438         }
 439     }
 440
 441     if (m_alloc > 1024) {
 442         free(m_intersections);
 443         m_alloc = 0;
 444         m_size = 0;
 445         m_intersections = 0;
 446     }
 447
 448     if (m_lines.size() > 1024)
 449         m_lines.shrink(1024);
 450 }
 451
 452 inline void QScanConverter::allocate(int size)
 453 {
 454     if (m_alloc < size) {
 455         int newAlloc = qMax(size, 2 * m_alloc);
 456         m_intersections = q_check_ptr((Intersection *)realloc(m_intersections, newAlloc * sizeof(Intersection)));
 457         m_alloc = newAlloc;
 458     }
 459 }
 460
 461 inline void QScanConverter::mergeIntersection(Intersection *it, const Intersection &isect)
 462 {
 463     Intersection *current = it;
 464
 465     while (isect.x != current->x) {
 466         int &next = isect.x < current->x ? current->left : current->right;
 467         if (next)
 468             current += next;
 469         else {
 470             Intersection *last = m_intersections + m_size;
 471             next = last - current;
 472             *last = isect;
 473             ++m_size;
 474             return;
 475         }
 476     }
 477
 478     current->winding += isect.winding;
 479 }
 480
 481 void QScanConverter::mergeCurve(const QT_FT_Vector &pa, const QT_FT_Vector &pb,
 482                                 const QT_FT_Vector &pc, const QT_FT_Vector &pd)
 483 {
 484     // make room for 32 splits
 485     QT_FT_Vector beziers[4 + 3 * 32];
 486
 487     QT_FT_Vector *b = beziers;
 488
 489     b[0] = pa;
 490     b[1] = pb;
 491     b[2] = pc;
 492     b[3] = pd;
 493
 494     const QT_FT_Pos flatness = 16;
 495
 496     while (b >= beziers) {
 497         QT_FT_Vector delta = { b[3].x - b[0].x, b[3].y - b[0].y };
 498         QT_FT_Pos l = qAbs(delta.x) + qAbs(delta.y);
 499
 500         bool belowThreshold;
 501         if (l > 64) {
 502             qlonglong d2 = qAbs(qlonglong(b[1].x-b[0].x) * qlonglong(delta.y) -
 503                                 qlonglong(b[1].y-b[0].y) * qlonglong(delta.x));
 504             qlonglong d3 = qAbs(qlonglong(b[2].x-b[0].x) * qlonglong(delta.y) -
 505                                 qlonglong(b[2].y-b[0].y) * qlonglong(delta.x));
 506
 507             qlonglong d = d2 + d3;
 508
 509             belowThreshold = (d <= qlonglong(flatness) * qlonglong(l));
 510         } else {
 511             QT_FT_Pos d = qAbs(b[0].x-b[1].x) + qAbs(b[0].y-b[1].y) +
 512                           qAbs(b[0].x-b[2].x) + qAbs(b[0].y-b[2].y);
 513
 514             belowThreshold = (d <= flatness);
 515         }
 516
 517         if (belowThreshold || b == beziers + 3 * 32) {
 518             mergeLine(b[0], b[3]);
 519             b -= 3;
 520             continue;
 521         }
 522
 523         split(b);
 524         b += 3;
 525     }
 526 }
 527
 528 inline bool QScanConverter::clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding)
 529 {
 530     bool right = edgeFP == m_rightFP;
 531
 532     if (xFP == edgeFP) {
 533         if ((slopeFP > 0) ^ right)
 534             return false;
 535         else {
 536             Line line = { edgeFP, 0, iTop, iBottom, winding };
 537             m_lines.add(line);
 538             return true;
 539         }
 540     }
 541
 542     Q16Dot16 lastFP = xFP + slopeFP * (iBottom - iTop);
 543
 544     if (lastFP == edgeFP) {
 545         if ((slopeFP < 0) ^ right)
 546             return false;
 547         else {
 548             Line line = { edgeFP, 0, iTop, iBottom, winding };
 549             m_lines.add(line);
 550             return true;
 551         }
 552     }
 553
 554     // does line cross edge?
 555     if ((lastFP < edgeFP) ^ (xFP < edgeFP)) {
 556         Q16Dot16 deltaY = Q16Dot16((edgeFP - xFP) / Q16Dot16ToFloat(slopeFP));
 557
 558         if ((xFP < edgeFP) ^ right) {
 559             // top segment needs to be clipped
 560             int iHeight = Q16Dot16ToInt(deltaY + 1);
 561             int iMiddle = iTop + iHeight;
 562
 563             Line line = { edgeFP, 0, iTop, iMiddle, winding };
 564             m_lines.add(line);
 565
 566             if (iMiddle != iBottom) {
 567                 xFP += slopeFP * (iHeight + 1);
 568                 iTop = iMiddle + 1;
 569             } else
 570                 return true;
 571         } else {
 572             // bottom segment needs to be clipped
 573             int iHeight = Q16Dot16ToInt(deltaY);
 574             int iMiddle = iTop + iHeight;
 575
 576             if (iMiddle != iBottom) {
 577                 Line line = { edgeFP, 0, iMiddle + 1, iBottom, winding };
 578                 m_lines.add(line);
 579
 580                 iBottom = iMiddle;
 581             }
 582         }
 583         return false;
 584     } else if ((xFP < edgeFP) ^ right) {
 585         Line line = { edgeFP, 0, iTop, iBottom, winding };
 586         m_lines.add(line);
 587         return true;
 588     }
 589
 590     return false;
 591 }
 592
 593 void QScanConverter::mergeLine(QT_FT_Vector a, QT_FT_Vector b)
 594 {
 595     int winding = 1;
 596
 597     if (a.y > b.y) {
 598         qSwap(a, b);
 599         winding = -1;
 600     }
 601
 602     if (m_legacyRounding) {
 603         a.x += COORD_OFFSET;
 604         a.y += COORD_OFFSET;
 605         b.x += COORD_OFFSET;
 606         b.y += COORD_OFFSET;
 607     }
 608
 609     int rounding = m_legacyRounding ? COORD_ROUNDING : 0;
 610
 611     int iTop = qMax(m_top, int((a.y + 32 - rounding) >> 6));
 612     int iBottom = qMin(m_bottom, int((b.y - 32 - rounding) >> 6));
 613
 614     if (iTop <= iBottom) {
 615         Q16Dot16 aFP = Q16Dot16Factor/2 + (a.x << 10) - rounding;
 616
 617         if (b.x == a.x) {
 618             Line line = { qBound(m_leftFP, aFP, m_rightFP), 0, iTop, iBottom, winding };
 619             m_lines.add(line);
 620         } else {
 621             const qreal slope = (b.x - a.x) / qreal(b.y - a.y);
 622
 623             const Q16Dot16 slopeFP = FloatToQ16Dot16(slope);
 624
 625             Q16Dot16 xFP = aFP + Q16Dot16Multiply(slopeFP,
 626                                                   IntToQ16Dot16(iTop)
 627                                                   + Q16Dot16Factor/2 - (a.y << 10));
 628
 629             if (clip(xFP, iTop, iBottom, slopeFP, m_leftFP, winding))
 630                 return;
 631
 632             if (clip(xFP, iTop, iBottom, slopeFP, m_rightFP, winding))
 633                 return;
 634
 635             Q_ASSERT(xFP >= m_leftFP);
 636
 637             Line line = { xFP, slopeFP, iTop, iBottom, winding };
 638             m_lines.add(line);
 639         }
 640     }
 641 }
 642
 643 QRasterizer::QRasterizer()
 644     : d(new QRasterizerPrivate)
 645 {
 646     d->legacyRounding = false;
 647 }
 648
 649 QRasterizer::~QRasterizer()
 650 {
 651     delete d;
 652 }
 653
 654 void QRasterizer::setAntialiased(bool antialiased)
 655 {
 656     d->antialiased = antialiased;
 657 }
 658
 659 void QRasterizer::initialize(ProcessSpans blend, void *data)
 660 {
 661     d->blend = blend;
 662     d->data = data;
 663 }
 664
 665 void QRasterizer::setClipRect(const QRect &clipRect)
 666 {
 667     d->clipRect = clipRect;
 668 }
 669
 670 void QRasterizer::setLegacyRoundingEnabled(bool legacyRoundingEnabled)
 671 {
 672     d->legacyRounding = legacyRoundingEnabled;
 673 }
 674
 675 static Q16Dot16 intersectPixelFP(int x, Q16Dot16 top, Q16Dot16 bottom, Q16Dot16 leftIntersectX, Q16Dot16 rightIntersectX, Q16Dot16 slope, Q16Dot16 invSlope)
 676 {
 677     Q16Dot16 leftX = IntToQ16Dot16(x);
 678     Q16Dot16 rightX = IntToQ16Dot16(x) + Q16Dot16Factor;
 679
 680     Q16Dot16 leftIntersectY, rightIntersectY;
 681     if (slope > 0) {
 682         leftIntersectY = top + Q16Dot16Multiply(leftX - leftIntersectX, invSlope);
 683         rightIntersectY = leftIntersectY + invSlope;
 684     } else {
 685         leftIntersectY = top + Q16Dot16Multiply(leftX - rightIntersectX, invSlope);
 686         rightIntersectY = leftIntersectY + invSlope;
 687     }
 688
 689     if (leftIntersectX >= leftX && rightIntersectX <= rightX) {
 690         return Q16Dot16Multiply(bottom - top, leftIntersectX - leftX + ((rightIntersectX - leftIntersectX) >> 1));
 691     } else if (leftIntersectX >= rightX) {
 692         return bottom - top;
 693     } else if (leftIntersectX >= leftX) {
 694         if (slope > 0) {
 695             return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, rightIntersectY - top);
 696         } else {
 697             return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, bottom - rightIntersectY);
 698         }
 699     } else if (rightIntersectX <= leftX) {
 700         return 0;
 701     } else if (rightIntersectX <= rightX) {
 702         if (slope > 0) {
 703             return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, bottom - leftIntersectY);
 704         } else {
 705             return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, leftIntersectY - top);
 706         }
 707     } else {
 708         if (slope > 0) {
 709             return (bottom - rightIntersectY) + ((rightIntersectY - leftIntersectY) >> 1);
 710         } else {
 711             return (rightIntersectY - top) + ((leftIntersectY - rightIntersectY) >> 1);
 712         }
 713     }
 714 }
 715
 716 static inline bool q26Dot6Compare(qreal p1, qreal p2)
 717 {
 718     return int((p2  - p1) * 64.) == 0;
 719 }
 720
 721 static inline qreal qFloorF(qreal v)
 722 {
 723 #ifdef QT_USE_MATH_H_FLOATS
 724     if (sizeof(qreal) == sizeof(float))
 725         return floorf(v);
 726     else
 727 #endif
 728         return floor(v);
 729 }
 730
 731 static inline QPointF snapTo26Dot6Grid(const QPointF &p)
 732 {
 733     return QPointF(qFloorF(p.x() * 64) * (1 / qreal(64)),
 734                    qFloorF(p.y() * 64) * (1 / qreal(64)));
 735 }
 736
 737 void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap)
 738 {
 739     if (a == b || width == 0 || d->clipRect.isEmpty())
 740         return;
 741
 742     Q_ASSERT(width > 0.0);
 743
 744     QPointF pa = a;
 745     QPointF pb = b;
 746
 747     if (squareCap) {
 748         QPointF delta = pb - pa;
 749         pa -= (0.5f * width) * delta;
 750         pb += (0.5f * width) * delta;
 751     }
 752
 753     QPointF offs = QPointF(qAbs(b.y() - a.y()), qAbs(b.x() - a.x())) * width * 0.5;
 754     const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs);
 755
 756     if (!clip.contains(pa) || !clip.contains(pb)) {
 757         qreal t1 = 0;
 758         qreal t2 = 1;
 759
 760         const qreal o[2] = { pa.x(), pa.y() };
 761         const qreal d[2] = { pb.x() - pa.x(), pb.y() - pa.y() };
 762
 763         const qreal low[2] = { clip.left(), clip.top() };
 764         const qreal high[2] = { clip.right(), clip.bottom() };
 765
 766         for (int i = 0; i < 2; ++i) {
 767             if (d[i] == 0) {
 768                 if (o[i] <= low[i] || o[i] >= high[i])
 769                     return;
 770                 continue;
 771             }
 772             const qreal d_inv = 1 / d[i];
 773             qreal t_low = (low[i] - o[i]) * d_inv;
 774             qreal t_high = (high[i] - o[i]) * d_inv;
 775             if (t_low > t_high)
 776                 qSwap(t_low, t_high);
 777             if (t1 < t_low)
 778                 t1 = t_low;
 779             if (t2 > t_high)
 780                 t2 = t_high;
 781             if (t1 >= t2)
 782                 return;
 783         }
 784
 785         QPointF npa = pa + (pb - pa) * t1;
 786         QPointF npb = pa + (pb - pa) * t2;
 787
 788         pa = npa;
 789         pb = npb;
 790     }
 791
 792     if (!d->antialiased && d->legacyRounding) {
 793         pa.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 794         pa.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 795         pb.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 796         pb.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 797     }
 798
 799     {
 800         // old delta
 801         const QPointF d0 = a - b;
 802         const qreal w0 = d0.x() * d0.x() + d0.y() * d0.y();
 803
 804         // new delta
 805         const QPointF d = pa - pb;
 806         const qreal w = d.x() * d.x() + d.y() * d.y();
 807
 808         if (w == 0)
 809             return;
 810
 811         // adjust width which is given relative to |b - a|
 812         width *= sqrt(w0 / w);
 813     }
 814
 815     QSpanBuffer buffer(d->blend, d->data, d->clipRect);
 816
 817     if (q26Dot6Compare(pa.y(), pb.y())) {
 818         const qreal x = (pa.x() + pb.x()) * 0.5f;
 819         const qreal dx = qAbs(pb.x() - pa.x()) * 0.5f;
 820
 821         const qreal y = pa.y();
 822         const qreal dy = width * dx;
 823
 824         pa = QPointF(x, y - dy);
 825         pb = QPointF(x, y + dy);
 826
 827         width = 1 / width;
 828     }
 829
 830     if (q26Dot6Compare(pa.x(), pb.x())) {
 831         if (pa.y() > pb.y())
 832             qSwap(pa, pb);
 833
 834         const qreal dy = pb.y() - pa.y();
 835         const qreal halfWidth = 0.5f * width * dy;
 836
 837         qreal left = pa.x() - halfWidth;
 838         qreal right = pa.x() + halfWidth;
 839
 840         left = qBound(qreal(d->clipRect.left()), left, qreal(d->clipRect.right() + 1));
 841         right = qBound(qreal(d->clipRect.left()), right, qreal(d->clipRect.right() + 1));
 842
 843         pa.ry() = qBound(qreal(d->clipRect.top()), pa.y(), qreal(d->clipRect.bottom() + 1));
 844         pb.ry() = qBound(qreal(d->clipRect.top()), pb.y(), qreal(d->clipRect.bottom() + 1));
 845
 846         if (q26Dot6Compare(left, right) || q26Dot6Compare(pa.y(), pb.y()))
 847             return;
 848
 849         if (d->antialiased) {
 850             const Q16Dot16 iLeft = int(left);
 851             const Q16Dot16 iRight = int(right);
 852             const Q16Dot16 leftWidth = IntToQ16Dot16(iLeft + 1)
 853                                        - FloatToQ16Dot16(left);
 854             const Q16Dot16 rightWidth = FloatToQ16Dot16(right)
 855                                         - IntToQ16Dot16(iRight);
 856
 857             Q16Dot16 coverage[3];
 858             int x[3];
 859             int len[3];
 860
 861             int n = 1;
 862             if (iLeft == iRight) {
 863                 coverage[0] = (leftWidth + rightWidth) * 255;
 864                 x[0] = iLeft;
 865                 len[0] = 1;
 866             } else {
 867                 coverage[0] = leftWidth * 255;
 868                 x[0] = iLeft;
 869                 len[0] = 1;
 870                 if (leftWidth == Q16Dot16Factor) {
 871                     len[0] = iRight - iLeft;
 872                 } else if (iRight - iLeft > 1) {
 873                     coverage[1] = IntToQ16Dot16(255);
 874                     x[1] = iLeft + 1;
 875                     len[1] = iRight - iLeft - 1;
 876                     ++n;
 877                 }
 878                 if (rightWidth) {
 879                     coverage[n] = rightWidth * 255;
 880                     x[n] = iRight;
 881                     len[n] = 1;
 882                     ++n;
 883                 }
 884             }
 885
 886             const Q16Dot16 iTopFP = IntToQ16Dot16(int(pa.y()));
 887             const Q16Dot16 iBottomFP = IntToQ16Dot16(int(pb.y()));
 888             const Q16Dot16 yPa = FloatToQ16Dot16(pa.y());
 889             const Q16Dot16 yPb = FloatToQ16Dot16(pb.y());
 890             for (Q16Dot16 yFP = iTopFP; yFP <= iBottomFP; yFP += Q16Dot16Factor) {
 891                 const Q16Dot16 rowHeight = qMin(yFP + Q16Dot16Factor, yPb)
 892                                            - qMax(yFP, yPa);
 893                 const int y = Q16Dot16ToInt(yFP);
 894                 for (int i = 0; i < n; ++i) {
 895                     buffer.addSpan(x[i], len[i], y,
 896                                    Q16Dot16ToInt(Q16Dot16Multiply(rowHeight, coverage[i])));
 897                 }
 898             }
 899         } else { // aliased
 900             int iTop = int(pa.y() + 0.5f);
 901             int iBottom = pb.y() < 0.5f ? -1 : int(pb.y() - 0.5f);
 902             int iLeft = int(left + 0.5f);
 903             int iRight = right < 0.5f ? -1 : int(right - 0.5f);
 904
 905             int iWidth = iRight - iLeft + 1;
 906             for (int y = iTop; y <= iBottom; ++y)
 907                 buffer.addSpan(iLeft, iWidth, y, 255);
 908         }
 909     } else {
 910         if (pa.y() > pb.y())
 911             qSwap(pa, pb);
 912
 913         QPointF delta = pb - pa;
 914         delta *= 0.5f * width;
 915         const QPointF perp(delta.y(), -delta.x());
 916
 917         QPointF top;
 918         QPointF left;
 919         QPointF right;
 920         QPointF bottom;
 921
 922         if (pa.x() < pb.x()) {
 923             top = pa + perp;
 924             left = pa - perp;
 925             right = pb + perp;
 926             bottom = pb - perp;
 927         } else {
 928             top = pa - perp;
 929             left = pb - perp;
 930             right = pa + perp;
 931             bottom = pb + perp;
 932         }
 933
 934         top = snapTo26Dot6Grid(top);
 935         bottom = snapTo26Dot6Grid(bottom);
 936         left = snapTo26Dot6Grid(left);
 937         right = snapTo26Dot6Grid(right);
 938
 939         const qreal topBound = qBound(qreal(d->clipRect.top()), top.y(), qreal(d->clipRect.bottom()));
 940         const qreal bottomBound = qBound(qreal(d->clipRect.top()), bottom.y(), qreal(d->clipRect.bottom()));
 941
 942         const QPointF topLeftEdge = left - top;
 943         const QPointF topRightEdge = right - top;
 944         const QPointF bottomLeftEdge = bottom - left;
 945         const QPointF bottomRightEdge = bottom - right;
 946
 947         const qreal topLeftSlope = topLeftEdge.x() / topLeftEdge.y();
 948         const qreal bottomLeftSlope = bottomLeftEdge.x() / bottomLeftEdge.y();
 949
 950         const qreal topRightSlope = topRightEdge.x() / topRightEdge.y();
 951         const qreal bottomRightSlope = bottomRightEdge.x() / bottomRightEdge.y();
 952
 953         const Q16Dot16 topLeftSlopeFP = FloatToQ16Dot16(topLeftSlope);
 954         const Q16Dot16 topRightSlopeFP = FloatToQ16Dot16(topRightSlope);
 955
 956         const Q16Dot16 bottomLeftSlopeFP = FloatToQ16Dot16(bottomLeftSlope);
 957         const Q16Dot16 bottomRightSlopeFP = FloatToQ16Dot16(bottomRightSlope);
 958
 959         const Q16Dot16 invTopLeftSlopeFP = FloatToQ16Dot16(1 / topLeftSlope);
 960         const Q16Dot16 invTopRightSlopeFP = FloatToQ16Dot16(1 / topRightSlope);
 961
 962         const Q16Dot16 invBottomLeftSlopeFP = FloatToQ16Dot16(1 / bottomLeftSlope);
 963         const Q16Dot16 invBottomRightSlopeFP = FloatToQ16Dot16(1 / bottomRightSlope);
 964
 965         if (d->antialiased) {
 966             const Q16Dot16 iTopFP = IntToQ16Dot16(int(topBound));
 967             const Q16Dot16 iLeftFP = IntToQ16Dot16(int(left.y()));
 968             const Q16Dot16 iRightFP = IntToQ16Dot16(int(right.y()));
 969             const Q16Dot16 iBottomFP = IntToQ16Dot16(int(bottomBound));
 970
 971             Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * topLeftSlope);
 972             Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * topRightSlope);
 973             Q16Dot16 leftIntersectBf = 0;
 974             Q16Dot16 rightIntersectBf = 0;
 975
 976             if (iLeftFP < iTopFP)
 977                 leftIntersectBf = FloatToQ16Dot16(left.x() + (int(topBound) - left.y()) * bottomLeftSlope);
 978
 979             if (iRightFP < iTopFP)
 980                 rightIntersectBf = FloatToQ16Dot16(right.x() + (int(topBound) - right.y()) * bottomRightSlope);
 981
 982             Q16Dot16 rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom;
 983             Q16Dot16 topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf;
 984             Q16Dot16 bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf;
 985
 986             int leftMin, leftMax, rightMin, rightMax;
 987
 988             const Q16Dot16 yTopFP = FloatToQ16Dot16(top.y());
 989             const Q16Dot16 yLeftFP = FloatToQ16Dot16(left.y());
 990             const Q16Dot16 yRightFP = FloatToQ16Dot16(right.y());
 991             const Q16Dot16 yBottomFP = FloatToQ16Dot16(bottom.y());
 992
 993             rowTop = qMax(iTopFP, yTopFP);
 994             topLeftIntersectAf = leftIntersectAf +
 995                                  Q16Dot16Multiply(topLeftSlopeFP, rowTop - iTopFP);
 996             topRightIntersectAf = rightIntersectAf +
 997                                   Q16Dot16Multiply(topRightSlopeFP, rowTop - iTopFP);
 998
 999             Q16Dot16 yFP = iTopFP;
1000             while (yFP <= iBottomFP) {
1001                 rowBottomLeft = qMin(yFP + Q16Dot16Factor, yLeftFP);
1002                 rowBottomRight = qMin(yFP + Q16Dot16Factor, yRightFP);
1003                 rowTopLeft = qMax(yFP, yLeftFP);
1004                 rowTopRight = qMax(yFP, yRightFP);
1005                 rowBottom = qMin(yFP + Q16Dot16Factor, yBottomFP);
1006
1007                 if (yFP == iLeftFP) {
1008                     const int y = Q16Dot16ToInt(yFP);
1009                     leftIntersectBf = FloatToQ16Dot16(left.x() + (y - left.y()) * bottomLeftSlope);
1010                     topLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(bottomLeftSlopeFP, rowTopLeft - yFP);
1011                     bottomLeftIntersectAf = leftIntersectAf + Q16Dot16Multiply(topLeftSlopeFP, rowBottomLeft - yFP);
1012                 } else {
1013                     topLeftIntersectBf = leftIntersectBf;
1014                     bottomLeftIntersectAf = leftIntersectAf + topLeftSlopeFP;
1015                 }
1016
1017                 if (yFP == iRightFP) {
1018                     const int y = Q16Dot16ToInt(yFP);
1019                     rightIntersectBf = FloatToQ16Dot16(right.x() + (y - right.y()) * bottomRightSlope);
1020                     topRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(bottomRightSlopeFP, rowTopRight - yFP);
1021                     bottomRightIntersectAf = rightIntersectAf + Q16Dot16Multiply(topRightSlopeFP, rowBottomRight - yFP);
1022                 } else {
1023                     topRightIntersectBf = rightIntersectBf;
1024                     bottomRightIntersectAf = rightIntersectAf + topRightSlopeFP;
1025                 }
1026
1027                 if (yFP == iBottomFP) {
1028                     bottomLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(bottomLeftSlopeFP, rowBottom - yFP);
1029                     bottomRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(bottomRightSlopeFP, rowBottom - yFP);
1030                 } else {
1031                     bottomLeftIntersectBf = leftIntersectBf + bottomLeftSlopeFP;
1032                     bottomRightIntersectBf = rightIntersectBf + bottomRightSlopeFP;
1033                 }
1034
1035                 if (yFP < iLeftFP) {
1036                     leftMin = Q16Dot16ToInt(bottomLeftIntersectAf);
1037                     leftMax = Q16Dot16ToInt(topLeftIntersectAf);
1038                 } else if (yFP == iLeftFP) {
1039                     leftMin = Q16Dot16ToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf));
1040                     leftMax = Q16Dot16ToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf));
1041                 } else {
1042                     leftMin = Q16Dot16ToInt(topLeftIntersectBf);
1043                     leftMax = Q16Dot16ToInt(bottomLeftIntersectBf);
1044                 }
1045
1046                 leftMin = qBound(d->clipRect.left(), leftMin, d->clipRect.right());
1047                 leftMax = qBound(d->clipRect.left(), leftMax, d->clipRect.right());
1048
1049                 if (yFP < iRightFP) {
1050                     rightMin = Q16Dot16ToInt(topRightIntersectAf);
1051                     rightMax = Q16Dot16ToInt(bottomRightIntersectAf);
1052                 } else if (yFP == iRightFP) {
1053                     rightMin = Q16Dot16ToInt(qMin(topRightIntersectAf, bottomRightIntersectBf));
1054                     rightMax = Q16Dot16ToInt(qMin(bottomRightIntersectAf, topRightIntersectBf));
1055                 } else {
1056                     rightMin = Q16Dot16ToInt(bottomRightIntersectBf);
1057                     rightMax = Q16Dot16ToInt(topRightIntersectBf);
1058                 }
1059
1060                 rightMin = qBound(d->clipRect.left(), rightMin, d->clipRect.right());
1061                 rightMax = qBound(d->clipRect.left(), rightMax, d->clipRect.right());
1062
1063                 if (leftMax > rightMax)
1064                     leftMax = rightMax;
1065                 if (rightMin < leftMin)
1066                     rightMin = leftMin;
1067
1068                 Q16Dot16 rowHeight = rowBottom - rowTop;
1069
1070                 int x = leftMin;
1071                 while (x <= leftMax) {
1072                     Q16Dot16 excluded = 0;
1073
1074                     if (yFP <= iLeftFP)
1075                         excluded += intersectPixelFP(x, rowTop, rowBottomLeft,
1076                                                      bottomLeftIntersectAf, topLeftIntersectAf,
1077                                                      topLeftSlopeFP, invTopLeftSlopeFP);
1078                     if (yFP >= iLeftFP)
1079                         excluded += intersectPixelFP(x, rowTopLeft, rowBottom,
1080                                                      topLeftIntersectBf, bottomLeftIntersectBf,
1081                                                      bottomLeftSlopeFP, invBottomLeftSlopeFP);
1082
1083                     if (x >= rightMin) {
1084                         if (yFP <= iRightFP)
1085                             excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
1086                                                                                      topRightIntersectAf, bottomRightIntersectAf,
1087                                                                                      topRightSlopeFP, invTopRightSlopeFP);
1088                         if (yFP >= iRightFP)
1089                             excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
1090                                                                                      bottomRightIntersectBf, topRightIntersectBf,
1091                                                                                      bottomRightSlopeFP, invBottomRightSlopeFP);
1092                     }
1093
1094                     Q16Dot16 coverage = rowHeight - excluded;
1095                     buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
1096                                    Q16Dot16ToInt(255 * coverage));
1097                     ++x;
1098                 }
1099                 if (x < rightMin) {
1100                     buffer.addSpan(x, rightMin - x, Q16Dot16ToInt(yFP),
1101                                    Q16Dot16ToInt(255 * rowHeight));
1102                     x = rightMin;
1103                 }
1104                 while (x <= rightMax) {
1105                     Q16Dot16 excluded = 0;
1106                     if (yFP <= iRightFP)
1107                         excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
1108                                                                                  topRightIntersectAf, bottomRightIntersectAf,
1109                                                                                  topRightSlopeFP, invTopRightSlopeFP);
1110                     if (yFP >= iRightFP)
1111                         excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
1112                                                                                  bottomRightIntersectBf, topRightIntersectBf,
1113                                                                                  bottomRightSlopeFP, invBottomRightSlopeFP);
1114
1115                     Q16Dot16 coverage = rowHeight - excluded;
1116                     buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
1117                                    Q16Dot16ToInt(255 * coverage));
1118                     ++x;
1119                 }
1120
1121                 leftIntersectAf += topLeftSlopeFP;
1122                 leftIntersectBf += bottomLeftSlopeFP;
1123                 rightIntersectAf += topRightSlopeFP;
1124                 rightIntersectBf += bottomRightSlopeFP;
1125                 topLeftIntersectAf = leftIntersectAf;
1126                 topRightIntersectAf = rightIntersectAf;
1127
1128                 yFP += Q16Dot16Factor;
1129                 rowTop = yFP;
1130             }
1131         } else { // aliased
1132             int iTop = int(top.y() + 0.5f);
1133             int iLeft = left.y() < 0.5f ? -1 : int(left.y() - 0.5f);
1134             int iRight = right.y() < 0.5f ? -1 : int(right.y() - 0.5f);
1135             int iBottom = bottom.y() < 0.5f? -1 : int(bottom.y() - 0.5f);
1136             int iMiddle = qMin(iLeft, iRight);
1137
1138             Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + 0.5f + (iTop + 0.5f - top.y()) * topLeftSlope);
1139             Q16Dot16 leftIntersectBf = FloatToQ16Dot16(left.x() + 0.5f + (iLeft + 1.5f - left.y()) * bottomLeftSlope);
1140             Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() - 0.5f + (iTop + 0.5f - top.y()) * topRightSlope);
1141             Q16Dot16 rightIntersectBf = FloatToQ16Dot16(right.x() - 0.5f + (iRight + 1.5f - right.y()) * bottomRightSlope);
1142
1143             int ny;
1144             int y = iTop;
1145 #define DO_SEGMENT(next, li, ri, ls, rs) \
1146             ny = qMin(next + 1, d->clipRect.top()); \
1147             if (y < ny) { \
1148                 li += ls * (ny - y); \
1149                 ri += rs * (ny - y); \
1150                 y = ny; \
1151             } \
1152             if (next > d->clipRect.bottom()) \
1153                 next = d->clipRect.bottom(); \
1154             for (; y <= next; ++y) { \
1155                 const int x1 = qMax(Q16Dot16ToInt(li), d->clipRect.left()); \
1156                 const int x2 = qMin(Q16Dot16ToInt(ri), d->clipRect.right()); \
1157                 if (x2 >= x1) \
1158                     buffer.addSpan(x1, x2 - x1 + 1, y, 255); \
1159                 li += ls; \
1160                 ri += rs; \
1161              }
1162
1163             DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, topLeftSlopeFP, topRightSlopeFP)
1164             DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, bottomLeftSlopeFP, topRightSlopeFP)
1165             DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, topLeftSlopeFP, bottomRightSlopeFP);
1166             DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, bottomLeftSlopeFP, bottomRightSlopeFP);
1167 #undef DO_SEGMENT
1168         }
1169     }
1170 }
1171
1172 void QRasterizer::rasterize(const QT_FT_Outline *outline, Qt::FillRule fillRule)
1173 {
1174     if (outline->n_points < 3 || outline->n_contours == 0)
1175         return;
1176
1177     const QT_FT_Vector *points = outline->points;
1178
1179     QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1180
1181     // ### QT_FT_Outline already has a bounding rect which is
1182     // ### precomputed at this point, so we should probably just be
1183     // ### using that instead...
1184     QT_FT_Pos min_y = points[0].y, max_y = points[0].y;
1185     for (int i = 1; i < outline->n_points; ++i) {
1186         const QT_FT_Vector &p = points[i];
1187         min_y = qMin(p.y, min_y);
1188         max_y = qMax(p.y, max_y);
1189     }
1190
1191     int rounding = d->legacyRounding ? COORD_OFFSET - COORD_ROUNDING : 0;
1192
1193     int iTopBound = qMax(d->clipRect.top(), int((min_y + 32 + rounding) >> 6));
1194     int iBottomBound = qMin(d->clipRect.bottom(), int((max_y - 32 + rounding) >> 6));
1195
1196     if (iTopBound > iBottomBound)
1197         return;
1198
1199     d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, d->legacyRounding, &buffer);
1200
1201     int first = 0;
1202     for (int i = 0; i < outline->n_contours; ++i) {
1203         const int last = outline->contours[i];
1204         for (int j = first; j < last; ++j) {
1205             if (outline->tags[j+1] == QT_FT_CURVE_TAG_CUBIC) {
1206                 Q_ASSERT(outline->tags[j+2] == QT_FT_CURVE_TAG_CUBIC);
1207                 d->scanConverter.mergeCurve(points[j], points[j+1], points[j+2], points[j+3]);
1208                 j += 2;
1209             } else {
1210                 d->scanConverter.mergeLine(points[j], points[j+1]);
1211             }
1212         }
1213
1214         first = last + 1;
1215     }
1216
1217     d->scanConverter.end();
1218 }
1219
1220 void QRasterizer::rasterize(const QPainterPath &path, Qt::FillRule fillRule)
1221 {
1222     if (path.isEmpty())
1223         return;
1224
1225     QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1226
1227     QRectF bounds = path.controlPointRect();
1228
1229     double rounding = d->legacyRounding ? (COORD_OFFSET - COORD_ROUNDING) / 64. : 0.0;
1230
1231     int iTopBound = qMax(d->clipRect.top(), int(bounds.top() + 0.5 + rounding));
1232     int iBottomBound = qMin(d->clipRect.bottom(), int(bounds.bottom() - 0.5 + rounding));
1233
1234     if (iTopBound > iBottomBound)
1235         return;
1236
1237     d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, d->legacyRounding, &buffer);
1238
1239     int subpathStart = 0;
1240     QT_FT_Vector last = { 0, 0 };
1241     for (int i = 0; i < path.elementCount(); ++i) {
1242         switch (path.elementAt(i).type) {
1243         case QPainterPath::LineToElement:
1244             {
1245                 QT_FT_Vector p1 = last;
1246                 QT_FT_Vector p2 = PointToVector(path.elementAt(i));
1247                 d->scanConverter.mergeLine(p1, p2);
1248                 last = p2;
1249                 break;
1250             }
1251         case QPainterPath::MoveToElement:
1252             {
1253                 if (i != 0) {
1254                     QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));
1255                     // close previous subpath
1256                     if (first.x != last.x || first.y != last.y)
1257                         d->scanConverter.mergeLine(last, first);
1258                 }
1259                 subpathStart = i;
1260                 last = PointToVector(path.elementAt(i));
1261                 break;
1262             }
1263         case QPainterPath::CurveToElement:
1264             {
1265                 QT_FT_Vector p1 = last;
1266                 QT_FT_Vector p2 = PointToVector(path.elementAt(i));
1267                 QT_FT_Vector p3 = PointToVector(path.elementAt(++i));
1268                 QT_FT_Vector p4 = PointToVector(path.elementAt(++i));
1269                 d->scanConverter.mergeCurve(p1, p2, p3, p4);
1270                 last = p4;
1271                 break;
1272             }
1273         default:
1274             Q_ASSERT(false);
1275             break;
1276         }
1277     }
1278
1279     QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));
1280
1281     // close path
1282     if (first.x != last.x || first.y != last.y)
1283         d->scanConverter.mergeLine(last, first);
1284
1285     d->scanConverter.end();
1286 }
1287
1288 QT_END_NAMESPACE