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, 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) * 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 void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap)
 724 {
 725     if (a == b || width == 0 || d->clipRect.isEmpty())
 726         return;
 727
 728     Q_ASSERT(width > 0.0);
 729
 730     QPointF pa = a;
 731     QPointF pb = b;
 732
 733     if (squareCap) {
 734         QPointF delta = pb - pa;
 735         pa -= (0.5f * width) * delta;
 736         pb += (0.5f * width) * delta;
 737     }
 738
 739     QPointF offs = QPointF(qAbs(b.y() - a.y()), qAbs(b.x() - a.x())) * width * 0.5;
 740     const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs);
 741
 742     if (!clip.contains(pa) || !clip.contains(pb)) {
 743         qreal t1 = 0;
 744         qreal t2 = 1;
 745
 746         const qreal o[2] = { pa.x(), pa.y() };
 747         const qreal d[2] = { pb.x() - pa.x(), pb.y() - pa.y() };
 748
 749         const qreal low[2] = { clip.left(), clip.top() };
 750         const qreal high[2] = { clip.right(), clip.bottom() };
 751
 752         for (int i = 0; i < 2; ++i) {
 753             if (d[i] == 0) {
 754                 if (o[i] <= low[i] || o[i] >= high[i])
 755                     return;
 756                 continue;
 757             }
 758             const qreal d_inv = 1 / d[i];
 759             qreal t_low = (low[i] - o[i]) * d_inv;
 760             qreal t_high = (high[i] - o[i]) * d_inv;
 761             if (t_low > t_high)
 762                 qSwap(t_low, t_high);
 763             if (t1 < t_low)
 764                 t1 = t_low;
 765             if (t2 > t_high)
 766                 t2 = t_high;
 767             if (t1 >= t2)
 768                 return;
 769         }
 770
 771         QPointF npa = pa + (pb - pa) * t1;
 772         QPointF npb = pa + (pb - pa) * t2;
 773
 774         pa = npa;
 775         pb = npb;
 776     }
 777
 778     if (!d->antialiased) {
 779         pa.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 780         pa.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 781         pb.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 782         pb.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
 783     }
 784
 785     {
 786         // old delta
 787         const QPointF d0 = a - b;
 788         const qreal w0 = d0.x() * d0.x() + d0.y() * d0.y();
 789
 790         // new delta
 791         const QPointF d = pa - pb;
 792         const qreal w = d.x() * d.x() + d.y() * d.y();
 793
 794         if (w == 0)
 795             return;
 796
 797         // adjust width which is given relative to |b - a|
 798         width *= sqrt(w0 / w);
 799     }
 800
 801     QSpanBuffer buffer(d->blend, d->data, d->clipRect);
 802
 803     if (q26Dot6Compare(pa.y(), pb.y())) {
 804         const qreal x = (pa.x() + pb.x()) * 0.5f;
 805         const qreal dx = qAbs(pb.x() - pa.x()) * 0.5f;
 806
 807         const qreal y = pa.y();
 808         const qreal dy = width * dx;
 809
 810         pa = QPointF(x, y - dy);
 811         pb = QPointF(x, y + dy);
 812
 813         width = 1 / width;
 814     }
 815
 816     if (q26Dot6Compare(pa.x(), pb.x())) {
 817         if (pa.y() > pb.y())
 818             qSwap(pa, pb);
 819
 820         const qreal dy = pb.y() - pa.y();
 821         const qreal halfWidth = 0.5f * width * dy;
 822
 823         qreal left = pa.x() - halfWidth;
 824         qreal right = pa.x() + halfWidth;
 825
 826         left = qBound(qreal(d->clipRect.left()), left, qreal(d->clipRect.right() + 1));
 827         right = qBound(qreal(d->clipRect.left()), right, qreal(d->clipRect.right() + 1));
 828
 829         pa.ry() = qBound(qreal(d->clipRect.top()), pa.y(), qreal(d->clipRect.bottom() + 1));
 830         pb.ry() = qBound(qreal(d->clipRect.top()), pb.y(), qreal(d->clipRect.bottom() + 1));
 831
 832         if (q26Dot6Compare(left, right) || q26Dot6Compare(pa.y(), pb.y()))
 833             return;
 834
 835         if (d->antialiased) {
 836             const Q16Dot16 iLeft = int(left);
 837             const Q16Dot16 iRight = int(right);
 838             const Q16Dot16 leftWidth = IntToQ16Dot16(iLeft + 1)
 839                                        - FloatToQ16Dot16(left);
 840             const Q16Dot16 rightWidth = FloatToQ16Dot16(right)
 841                                         - IntToQ16Dot16(iRight);
 842
 843             Q16Dot16 coverage[3];
 844             int x[3];
 845             int len[3];
 846
 847             int n = 1;
 848             if (iLeft == iRight) {
 849                 coverage[0] = (leftWidth + rightWidth) * 255;
 850                 x[0] = iLeft;
 851                 len[0] = 1;
 852             } else {
 853                 coverage[0] = leftWidth * 255;
 854                 x[0] = iLeft;
 855                 len[0] = 1;
 856                 if (leftWidth == Q16Dot16Factor) {
 857                     len[0] = iRight - iLeft;
 858                 } else if (iRight - iLeft > 1) {
 859                     coverage[1] = IntToQ16Dot16(255);
 860                     x[1] = iLeft + 1;
 861                     len[1] = iRight - iLeft - 1;
 862                     ++n;
 863                 }
 864                 if (rightWidth) {
 865                     coverage[n] = rightWidth * 255;
 866                     x[n] = iRight;
 867                     len[n] = 1;
 868                     ++n;
 869                 }
 870             }
 871
 872             const Q16Dot16 iTopFP = IntToQ16Dot16(int(pa.y()));
 873             const Q16Dot16 iBottomFP = IntToQ16Dot16(int(pb.y()));
 874             const Q16Dot16 yPa = FloatToQ16Dot16(pa.y());
 875             const Q16Dot16 yPb = FloatToQ16Dot16(pb.y());
 876             for (Q16Dot16 yFP = iTopFP; yFP <= iBottomFP; yFP += Q16Dot16Factor) {
 877                 const Q16Dot16 rowHeight = qMin(yFP + Q16Dot16Factor, yPb)
 878                                            - qMax(yFP, yPa);
 879                 const int y = Q16Dot16ToInt(yFP);
 880                 for (int i = 0; i < n; ++i) {
 881                     buffer.addSpan(x[i], len[i], y,
 882                                    Q16Dot16ToInt(Q16Dot16Multiply(rowHeight, coverage[i])));
 883                 }
 884             }
 885         } else { // aliased
 886             int iTop = int(pa.y() + 0.5f);
 887             int iBottom = pb.y() < 0.5f ? -1 : int(pb.y() - 0.5f);
 888             int iLeft = int(left + 0.5f);
 889             int iRight = right < 0.5f ? -1 : int(right - 0.5f);
 890
 891             int iWidth = iRight - iLeft + 1;
 892             for (int y = iTop; y <= iBottom; ++y)
 893                 buffer.addSpan(iLeft, iWidth, y, 255);
 894         }
 895     } else {
 896         if (pa.y() > pb.y())
 897             qSwap(pa, pb);
 898
 899         QPointF delta = pb - pa;
 900         delta *= 0.5f * width;
 901         const QPointF perp(delta.y(), -delta.x());
 902
 903         QPointF top;
 904         QPointF left;
 905         QPointF right;
 906         QPointF bottom;
 907
 908         if (pa.x() < pb.x()) {
 909             top = pa + perp;
 910             left = pa - perp;
 911             right = pb + perp;
 912             bottom = pb - perp;
 913         } else {
 914             top = pa - perp;
 915             left = pb - perp;
 916             right = pa + perp;
 917             bottom = pb + perp;
 918         }
 919
 920         top = snapTo26Dot6Grid(top);
 921         bottom = snapTo26Dot6Grid(bottom);
 922         left = snapTo26Dot6Grid(left);
 923         right = snapTo26Dot6Grid(right);
 924
 925         const qreal topBound = qBound(qreal(d->clipRect.top()), top.y(), qreal(d->clipRect.bottom()));
 926         const qreal bottomBound = qBound(qreal(d->clipRect.top()), bottom.y(), qreal(d->clipRect.bottom()));
 927
 928         const QPointF topLeftEdge = left - top;
 929         const QPointF topRightEdge = right - top;
 930         const QPointF bottomLeftEdge = bottom - left;
 931         const QPointF bottomRightEdge = bottom - right;
 932
 933         const qreal topLeftSlope = topLeftEdge.x() / topLeftEdge.y();
 934         const qreal bottomLeftSlope = bottomLeftEdge.x() / bottomLeftEdge.y();
 935
 936         const qreal topRightSlope = topRightEdge.x() / topRightEdge.y();
 937         const qreal bottomRightSlope = bottomRightEdge.x() / bottomRightEdge.y();
 938
 939         const Q16Dot16 topLeftSlopeFP = FloatToQ16Dot16(topLeftSlope);
 940         const Q16Dot16 topRightSlopeFP = FloatToQ16Dot16(topRightSlope);
 941
 942         const Q16Dot16 bottomLeftSlopeFP = FloatToQ16Dot16(bottomLeftSlope);
 943         const Q16Dot16 bottomRightSlopeFP = FloatToQ16Dot16(bottomRightSlope);
 944
 945         const Q16Dot16 invTopLeftSlopeFP = FloatToQ16Dot16(1 / topLeftSlope);
 946         const Q16Dot16 invTopRightSlopeFP = FloatToQ16Dot16(1 / topRightSlope);
 947
 948         const Q16Dot16 invBottomLeftSlopeFP = FloatToQ16Dot16(1 / bottomLeftSlope);
 949         const Q16Dot16 invBottomRightSlopeFP = FloatToQ16Dot16(1 / bottomRightSlope);
 950
 951         if (d->antialiased) {
 952             const Q16Dot16 iTopFP = IntToQ16Dot16(int(topBound));
 953             const Q16Dot16 iLeftFP = IntToQ16Dot16(int(left.y()));
 954             const Q16Dot16 iRightFP = IntToQ16Dot16(int(right.y()));
 955             const Q16Dot16 iBottomFP = IntToQ16Dot16(int(bottomBound));
 956
 957             Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * topLeftSlope);
 958             Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * topRightSlope);
 959             Q16Dot16 leftIntersectBf = 0;
 960             Q16Dot16 rightIntersectBf = 0;
 961
 962             if (iLeftFP < iTopFP)
 963                 leftIntersectBf = FloatToQ16Dot16(left.x() + (int(topBound) - left.y()) * bottomLeftSlope);
 964
 965             if (iRightFP < iTopFP)
 966                 rightIntersectBf = FloatToQ16Dot16(right.x() + (int(topBound) - right.y()) * bottomRightSlope);
 967
 968             Q16Dot16 rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom;
 969             Q16Dot16 topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf;
 970             Q16Dot16 bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf;
 971
 972             int leftMin, leftMax, rightMin, rightMax;
 973
 974             const Q16Dot16 yTopFP = FloatToQ16Dot16(top.y());
 975             const Q16Dot16 yLeftFP = FloatToQ16Dot16(left.y());
 976             const Q16Dot16 yRightFP = FloatToQ16Dot16(right.y());
 977             const Q16Dot16 yBottomFP = FloatToQ16Dot16(bottom.y());
 978
 979             rowTop = qMax(iTopFP, yTopFP);
 980             topLeftIntersectAf = leftIntersectAf +
 981                                  Q16Dot16Multiply(topLeftSlopeFP, rowTop - iTopFP);
 982             topRightIntersectAf = rightIntersectAf +
 983                                   Q16Dot16Multiply(topRightSlopeFP, rowTop - iTopFP);
 984
 985             Q16Dot16 yFP = iTopFP;
 986             while (yFP <= iBottomFP) {
 987                 rowBottomLeft = qMin(yFP + Q16Dot16Factor, yLeftFP);
 988                 rowBottomRight = qMin(yFP + Q16Dot16Factor, yRightFP);
 989                 rowTopLeft = qMax(yFP, yLeftFP);
 990                 rowTopRight = qMax(yFP, yRightFP);
 991                 rowBottom = qMin(yFP + Q16Dot16Factor, yBottomFP);
 992
 993                 if (yFP == iLeftFP) {
 994                     const int y = Q16Dot16ToInt(yFP);
 995                     leftIntersectBf = FloatToQ16Dot16(left.x() + (y - left.y()) * bottomLeftSlope);
 996                     topLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(bottomLeftSlopeFP, rowTopLeft - yFP);
 997                     bottomLeftIntersectAf = leftIntersectAf + Q16Dot16Multiply(topLeftSlopeFP, rowBottomLeft - yFP);
 998                 } else {
 999                     topLeftIntersectBf = leftIntersectBf;
1000                     bottomLeftIntersectAf = leftIntersectAf + topLeftSlopeFP;
1001                 }
1002
1003                 if (yFP == iRightFP) {
1004                     const int y = Q16Dot16ToInt(yFP);
1005                     rightIntersectBf = FloatToQ16Dot16(right.x() + (y - right.y()) * bottomRightSlope);
1006                     topRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(bottomRightSlopeFP, rowTopRight - yFP);
1007                     bottomRightIntersectAf = rightIntersectAf + Q16Dot16Multiply(topRightSlopeFP, rowBottomRight - yFP);
1008                 } else {
1009                     topRightIntersectBf = rightIntersectBf;
1010                     bottomRightIntersectAf = rightIntersectAf + topRightSlopeFP;
1011                 }
1012
1013                 if (yFP == iBottomFP) {
1014                     bottomLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(bottomLeftSlopeFP, rowBottom - yFP);
1015                     bottomRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(bottomRightSlopeFP, rowBottom - yFP);
1016                 } else {
1017                     bottomLeftIntersectBf = leftIntersectBf + bottomLeftSlopeFP;
1018                     bottomRightIntersectBf = rightIntersectBf + bottomRightSlopeFP;
1019                 }
1020
1021                 if (yFP < iLeftFP) {
1022                     leftMin = Q16Dot16ToInt(bottomLeftIntersectAf);
1023                     leftMax = Q16Dot16ToInt(topLeftIntersectAf);
1024                 } else if (yFP == iLeftFP) {
1025                     leftMin = Q16Dot16ToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf));
1026                     leftMax = Q16Dot16ToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf));
1027                 } else {
1028                     leftMin = Q16Dot16ToInt(topLeftIntersectBf);
1029                     leftMax = Q16Dot16ToInt(bottomLeftIntersectBf);
1030                 }
1031
1032                 leftMin = qBound(d->clipRect.left(), leftMin, d->clipRect.right());
1033                 leftMax = qBound(d->clipRect.left(), leftMax, d->clipRect.right());
1034
1035                 if (yFP < iRightFP) {
1036                     rightMin = Q16Dot16ToInt(topRightIntersectAf);
1037                     rightMax = Q16Dot16ToInt(bottomRightIntersectAf);
1038                 } else if (yFP == iRightFP) {
1039                     rightMin = Q16Dot16ToInt(qMin(topRightIntersectAf, bottomRightIntersectBf));
1040                     rightMax = Q16Dot16ToInt(qMin(bottomRightIntersectAf, topRightIntersectBf));
1041                 } else {
1042                     rightMin = Q16Dot16ToInt(bottomRightIntersectBf);
1043                     rightMax = Q16Dot16ToInt(topRightIntersectBf);
1044                 }
1045
1046                 rightMin = qBound(d->clipRect.left(), rightMin, d->clipRect.right());
1047                 rightMax = qBound(d->clipRect.left(), rightMax, d->clipRect.right());
1048
1049                 if (leftMax > rightMax)
1050                     leftMax = rightMax;
1051                 if (rightMin < leftMin)
1052                     rightMin = leftMin;
1053
1054                 Q16Dot16 rowHeight = rowBottom - rowTop;
1055
1056                 int x = leftMin;
1057                 while (x <= leftMax) {
1058                     Q16Dot16 excluded = 0;
1059
1060                     if (yFP <= iLeftFP)
1061                         excluded += intersectPixelFP(x, rowTop, rowBottomLeft,
1062                                                      bottomLeftIntersectAf, topLeftIntersectAf,
1063                                                      topLeftSlopeFP, invTopLeftSlopeFP);
1064                     if (yFP >= iLeftFP)
1065                         excluded += intersectPixelFP(x, rowTopLeft, rowBottom,
1066                                                      topLeftIntersectBf, bottomLeftIntersectBf,
1067                                                      bottomLeftSlopeFP, invBottomLeftSlopeFP);
1068
1069                     if (x >= rightMin) {
1070                         if (yFP <= iRightFP)
1071                             excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
1072                                                                                      topRightIntersectAf, bottomRightIntersectAf,
1073                                                                                      topRightSlopeFP, invTopRightSlopeFP);
1074                         if (yFP >= iRightFP)
1075                             excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
1076                                                                                      bottomRightIntersectBf, topRightIntersectBf,
1077                                                                                      bottomRightSlopeFP, invBottomRightSlopeFP);
1078                     }
1079
1080                     Q16Dot16 coverage = rowHeight - excluded;
1081                     buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
1082                                    Q16Dot16ToInt(255 * coverage));
1083                     ++x;
1084                 }
1085                 if (x < rightMin) {
1086                     buffer.addSpan(x, rightMin - x, Q16Dot16ToInt(yFP),
1087                                    Q16Dot16ToInt(255 * rowHeight));
1088                     x = rightMin;
1089                 }
1090                 while (x <= rightMax) {
1091                     Q16Dot16 excluded = 0;
1092                     if (yFP <= iRightFP)
1093                         excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
1094                                                                                  topRightIntersectAf, bottomRightIntersectAf,
1095                                                                                  topRightSlopeFP, invTopRightSlopeFP);
1096                     if (yFP >= iRightFP)
1097                         excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
1098                                                                                  bottomRightIntersectBf, topRightIntersectBf,
1099                                                                                  bottomRightSlopeFP, invBottomRightSlopeFP);
1100
1101                     Q16Dot16 coverage = rowHeight - excluded;
1102                     buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
1103                                    Q16Dot16ToInt(255 * coverage));
1104                     ++x;
1105                 }
1106
1107                 leftIntersectAf += topLeftSlopeFP;
1108                 leftIntersectBf += bottomLeftSlopeFP;
1109                 rightIntersectAf += topRightSlopeFP;
1110                 rightIntersectBf += bottomRightSlopeFP;
1111                 topLeftIntersectAf = leftIntersectAf;
1112                 topRightIntersectAf = rightIntersectAf;
1113
1114                 yFP += Q16Dot16Factor;
1115                 rowTop = yFP;
1116             }
1117         } else { // aliased
1118             int iTop = int(top.y() + 0.5f);
1119             int iLeft = left.y() < 0.5f ? -1 : int(left.y() - 0.5f);
1120             int iRight = right.y() < 0.5f ? -1 : int(right.y() - 0.5f);
1121             int iBottom = bottom.y() < 0.5f? -1 : int(bottom.y() - 0.5f);
1122             int iMiddle = qMin(iLeft, iRight);
1123
1124             Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + 0.5f + (iTop + 0.5f - top.y()) * topLeftSlope);
1125             Q16Dot16 leftIntersectBf = FloatToQ16Dot16(left.x() + 0.5f + (iLeft + 1.5f - left.y()) * bottomLeftSlope);
1126             Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() - 0.5f + (iTop + 0.5f - top.y()) * topRightSlope);
1127             Q16Dot16 rightIntersectBf = FloatToQ16Dot16(right.x() - 0.5f + (iRight + 1.5f - right.y()) * bottomRightSlope);
1128
1129             int ny;
1130             int y = iTop;
1131 #define DO_SEGMENT(next, li, ri, ls, rs) \
1132             ny = qMin(next + 1, d->clipRect.top()); \
1133             if (y < ny) { \
1134                 li += ls * (ny - y); \
1135                 ri += rs * (ny - y); \
1136                 y = ny; \
1137             } \
1138             if (next > d->clipRect.bottom()) \
1139                 next = d->clipRect.bottom(); \
1140             for (; y <= next; ++y) { \
1141                 const int x1 = qMax(Q16Dot16ToInt(li), d->clipRect.left()); \
1142                 const int x2 = qMin(Q16Dot16ToInt(ri), d->clipRect.right()); \
1143                 if (x2 >= x1) \
1144                     buffer.addSpan(x1, x2 - x1 + 1, y, 255); \
1145                 li += ls; \
1146                 ri += rs; \
1147              }
1148
1149             DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, topLeftSlopeFP, topRightSlopeFP)
1150             DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, bottomLeftSlopeFP, topRightSlopeFP)
1151             DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, topLeftSlopeFP, bottomRightSlopeFP);
1152             DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, bottomLeftSlopeFP, bottomRightSlopeFP);
1153 #undef DO_SEGMENT
1154         }
1155     }
1156 }
1157
1158 void QRasterizer::rasterize(const QT_FT_Outline *outline, Qt::FillRule fillRule)
1159 {
1160     if (outline->n_points < 3 || outline->n_contours == 0)
1161         return;
1162
1163     const QT_FT_Vector *points = outline->points;
1164
1165     QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1166
1167     // ### QT_FT_Outline already has a bounding rect which is
1168     // ### precomputed at this point, so we should probably just be
1169     // ### using that instead...
1170     QT_FT_Pos min_y = points[0].y, max_y = points[0].y;
1171     for (int i = 1; i < outline->n_points; ++i) {
1172         const QT_FT_Vector &p = points[i];
1173         min_y = qMin(p.y, min_y);
1174         max_y = qMax(p.y, max_y);
1175     }
1176
1177     int iTopBound = qMax(d->clipRect.top(), int((min_y + 32 + COORD_OFFSET - COORD_ROUNDING) >> 6));
1178     int iBottomBound = qMin(d->clipRect.bottom(), int((max_y - 32 + COORD_OFFSET - COORD_ROUNDING) >> 6));
1179
1180     if (iTopBound > iBottomBound)
1181         return;
1182
1183     d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer);
1184
1185     int first = 0;
1186     for (int i = 0; i < outline->n_contours; ++i) {
1187         const int last = outline->contours[i];
1188         for (int j = first; j < last; ++j) {
1189             if (outline->tags[j+1] == QT_FT_CURVE_TAG_CUBIC) {
1190                 Q_ASSERT(outline->tags[j+2] == QT_FT_CURVE_TAG_CUBIC);
1191                 d->scanConverter.mergeCurve(points[j], points[j+1], points[j+2], points[j+3]);
1192                 j += 2;
1193             } else {
1194                 d->scanConverter.mergeLine(points[j], points[j+1]);
1195             }
1196         }
1197
1198         first = last + 1;
1199     }
1200
1201     d->scanConverter.end();
1202 }
1203
1204 void QRasterizer::rasterize(const QPainterPath &path, Qt::FillRule fillRule)
1205 {
1206     if (path.isEmpty())
1207         return;
1208
1209     QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1210
1211     QRectF bounds = path.controlPointRect();
1212
1213     int iTopBound = qMax(d->clipRect.top(), int(bounds.top() + 0.5 + (COORD_OFFSET - COORD_ROUNDING)/64.));
1214     int iBottomBound = qMin(d->clipRect.bottom(), int(bounds.bottom() - 0.5 + (COORD_OFFSET - COORD_ROUNDING)/64.));
1215
1216     if (iTopBound > iBottomBound)
1217         return;
1218
1219     d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer);
1220
1221     int subpathStart = 0;
1222     QT_FT_Vector last = { 0, 0 };
1223     for (int i = 0; i < path.elementCount(); ++i) {
1224         switch (path.elementAt(i).type) {
1225         case QPainterPath::LineToElement:
1226             {
1227                 QT_FT_Vector p1 = last;
1228                 QT_FT_Vector p2 = PointToVector(path.elementAt(i));
1229                 d->scanConverter.mergeLine(p1, p2);
1230                 last = p2;
1231                 break;
1232             }
1233         case QPainterPath::MoveToElement:
1234             {
1235                 if (i != 0) {
1236                     QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));
1237                     // close previous subpath
1238                     if (first.x != last.x || first.y != last.y)
1239                         d->scanConverter.mergeLine(last, first);
1240                 }
1241                 subpathStart = i;
1242                 last = PointToVector(path.elementAt(i));
1243                 break;
1244             }
1245         case QPainterPath::CurveToElement:
1246             {
1247                 QT_FT_Vector p1 = last;
1248                 QT_FT_Vector p2 = PointToVector(path.elementAt(i));
1249                 QT_FT_Vector p3 = PointToVector(path.elementAt(++i));
1250                 QT_FT_Vector p4 = PointToVector(path.elementAt(++i));
1251                 d->scanConverter.mergeCurve(p1, p2, p3, p4);
1252                 last = p4;
1253                 break;
1254             }
1255         default:
1256             Q_ASSERT(false);
1257             break;
1258         }
1259     }
1260
1261     QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));
1262
1263     // close path
1264     if (first.x != last.x || first.y != last.y)
1265         d->scanConverter.mergeLine(last, first);
1266
1267     d->scanConverter.end();
1268 }
1269
1270 QT_END_NAMESPACE