src/gui/painting/qrasterizer.cpp

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