1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    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 class QSpanBuffer {

    69 public:

    70     QSpanBuffer(ProcessSpans blend, void *data, const QRect &clipRect)

    71         : m_spanCount(0)

    72         , m_blend(blend)

    73         , m_data(data)

    74         , m_clipRect(clipRect)

    75     {

    76     }

    77 

    78     ~QSpanBuffer()

    79     {

    80         flushSpans();

    81     }

    82 

    83     void addSpan(int x, unsigned int len, int y, unsigned char coverage)

    84     {

    85         if (!coverage || !len)

    86             return;

    87 

    88         Q_ASSERT(y >= m_clipRect.top());

    89         Q_ASSERT(y <= m_clipRect.bottom());

    90         Q_ASSERT(x >= m_clipRect.left());

    91         Q_ASSERT(x + int(len) - 1 <= m_clipRect.right());

    92 

    93         m_spans[m_spanCount].x = x;

    94         m_spans[m_spanCount].len = len;

    95         m_spans[m_spanCount].y = y;

    96         m_spans[m_spanCount].coverage = coverage;

    97 

    98         if (++m_spanCount == SPAN_BUFFER_SIZE)

    99             flushSpans();

   100     }

   101 

   102 private:

   103     void flushSpans()

   104     {

   105         m_blend(m_spanCount, m_spans, m_data);

   106         m_spanCount = 0;

   107     }

   108 

   109     QT_FT_Span m_spans[SPAN_BUFFER_SIZE];

   110     int m_spanCount;

   111 

   112     ProcessSpans m_blend;

   113     void *m_data;

   114 

   115     QRect m_clipRect;

   116 };

   117 

   118 #define CHUNK_SIZE 64

   119 class QScanConverter

   120 {

   121 public:

   122     QScanConverter();

   123     ~QScanConverter();

   124 

   125     void begin(int top, int bottom, int left, int right,

   126                Qt::FillRule fillRule, QSpanBuffer *spanBuffer);

   127     void end();

   128 

   129     void mergeCurve(const QT_FT_Vector &a, const QT_FT_Vector &b,

   130                     const QT_FT_Vector &c, const QT_FT_Vector &d);

   131     void mergeLine(QT_FT_Vector a, QT_FT_Vector b);

   132 

   133     struct Line

   134     {

   135         Q16Dot16 x;

   136         Q16Dot16 delta;

   137 

   138         int top, bottom;

   139 

   140         int winding;

   141     };

   142 

   143 private:

   144     struct Intersection

   145     {

   146         int x;

   147         int winding;

   148 

   149         int left, right;

   150     };

   151 

   152     inline bool clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding);

   153     inline void mergeIntersection(Intersection *head, const Intersection &isect);

   154 

   155     void prepareChunk();

   156 

   157     void emitNode(const Intersection *node);

   158     void emitSpans(int chunk);

   159 

   160     inline void allocate(int size);

   161 

   162     QDataBuffer<Line> m_lines;

   163 

   164     int m_alloc;

   165     int m_size;

   166 

   167     int m_top;

   168     int m_bottom;

   169 

   170     Q16Dot16 m_leftFP;

   171     Q16Dot16 m_rightFP;

   172 

   173     int m_fillRuleMask;

   174 

   175     int m_x;

   176     int m_y;

   177     int m_winding;

   178 

   179     Intersection *m_intersections;

   180 

   181     QSpanBuffer *m_spanBuffer;

   182 

   183     QDataBuffer<Line *> m_active;

   184 

   185     template <typename T>

   186     friend void qScanConvert(QScanConverter &d, T allVertical);

   187 };

   188 

   189 class QRasterizerPrivate

   190 {

   191 public:

   192     bool antialiased;

   193     ProcessSpans blend;

   194     void *data;

   195     QRect clipRect;

   196 

   197     QScanConverter scanConverter;

   198 };

   199 

   200 QScanConverter::QScanConverter()

   201    : m_alloc(0)

   202    , m_size(0)

   203    , m_intersections(0)

   204 {

   205 }

   206 

   207 QScanConverter::~QScanConverter()

   208 {

   209     if (m_intersections)

   210         free(m_intersections);

   211 }

   212 

   213 void QScanConverter::begin(int top, int bottom, int left, int right,

   214                            Qt::FillRule fillRule, QSpanBuffer *spanBuffer)

   215 {

   216     m_top = top;

   217     m_bottom = bottom;

   218     m_leftFP = IntToQ16Dot16(left);

   219     m_rightFP = IntToQ16Dot16(right + 1);

   220 

   221     m_lines.reset();

   222 

   223     m_fillRuleMask = fillRule == Qt::WindingFill ? ~0x0 : 0x1;

   224     m_spanBuffer = spanBuffer;

   225 }

   226 

   227 void QScanConverter::prepareChunk()

   228 {

   229     m_size = CHUNK_SIZE;

   230 

   231     allocate(CHUNK_SIZE);

   232     memset(m_intersections, 0, CHUNK_SIZE * sizeof(Intersection));

   233 }

   234 

   235 void QScanConverter::emitNode(const Intersection *node)

   236 {

   237 tail_call:

   238     if (node->left)

   239         emitNode(node + node->left);

   240 

   241     if (m_winding & m_fillRuleMask)

   242         m_spanBuffer->addSpan(m_x, node->x - m_x, m_y, 0xff);

   243 

   244     m_x = node->x;

   245     m_winding += node->winding;

   246 

   247     if (node->right) {

   248         node += node->right;

   249         goto tail_call;

   250     }

   251 }

   252 

   253 void QScanConverter::emitSpans(int chunk)

   254 {

   255     for (int dy = 0; dy < CHUNK_SIZE; ++dy) {

   256         m_x = 0;

   257         m_y = chunk + dy;

   258         m_winding = 0;

   259 

   260         emitNode(&m_intersections[dy]);

   261     }

   262 }

   263 

   264 // split control points b[0] ... b[3] into

   265 // left (b[0] ... b[3]) and right (b[3] ... b[6])

   266 static void split(QT_FT_Vector *b)

   267 {

   268     b[6] = b[3];

   269 

   270     {

   271         const QT_FT_Pos temp = (b[1].x + b[2].x)/2;

   272 

   273         b[1].x = (b[0].x + b[1].x)/2;

   274         b[5].x = (b[2].x + b[3].x)/2;

   275         b[2].x = (b[1].x + temp)/2;

   276         b[4].x = (b[5].x + temp)/2;

   277         b[3].x = (b[2].x + b[4].x)/2;

   278     }

   279     {

   280         const QT_FT_Pos temp = (b[1].y + b[2].y)/2;

   281 

   282         b[1].y = (b[0].y + b[1].y)/2;

   283         b[5].y = (b[2].y + b[3].y)/2;

   284         b[2].y = (b[1].y + temp)/2;

   285         b[4].y = (b[5].y + temp)/2;

   286         b[3].y = (b[2].y + b[4].y)/2;

   287     }

   288 }

   289 

   290 static inline bool topOrder(const QScanConverter::Line &a, const QScanConverter::Line &b)

   291 {

   292     return a.top < b.top;

   293 }

   294 

   295 static inline bool xOrder(const QScanConverter::Line *a, const QScanConverter::Line *b)

   296 {

   297     return a->x < b->x;

   298 }

   299 

   300 template <bool B>

   301 struct QBoolToType

   302 {

   303     inline bool operator()() const

   304     {

   305         return B;

   306     }

   307 };

   308 

   309 // should be a member function but VC6 doesn't support member template functions

   310 template <typename T>

   311 void qScanConvert(QScanConverter &d, T allVertical)

   312 {

   313     qSort(d.m_lines.data(), d.m_lines.data() + d.m_lines.size(), QT_PREPEND_NAMESPACE(topOrder));

   314     int line = 0;

   315     for (int y = d.m_lines.first().top; y <= d.m_bottom; ++y) {

   316         for (; line < d.m_lines.size() && d.m_lines.at(line).top == y; ++line) {

   317             // add node to active list

   318             if (allVertical()) {

   319                 QScanConverter::Line *l = &d.m_lines.at(line);

   320                 d.m_active.resize(d.m_active.size() + 1);

   321                 int j;

   322                 for (j = d.m_active.size() - 2; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(l, d.m_active.at(j)); --j)

   323                     d.m_active.at(j+1) = d.m_active.at(j);

   324                 d.m_active.at(j+1) = l;

   325             } else {

   326                 d.m_active << &d.m_lines.at(line);

   327             }

   328         }

   329 

   330         int numActive = d.m_active.size();

   331         if (!allVertical()) {

   332         // use insertion sort instead of qSort, as the active edge list is quite small

   333         // and in the average case already sorted

   334             for (int i = 1; i < numActive; ++i) {

   335                 QScanConverter::Line *l = d.m_active.at(i);

   336                 int j;

   337                 for (j = i-1; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(l, d.m_active.at(j)); --j)

   338                     d.m_active.at(j+1) = d.m_active.at(j);

   339                 d.m_active.at(j+1) = l;

   340             }

   341         }

   342 

   343         int x = 0;

   344         int winding = 0;

   345         for (int i = 0; i < numActive; ++i) {

   346             QScanConverter::Line *node = d.m_active.at(i);

   347 

   348             const int current = Q16Dot16ToInt(node->x);

   349             if (winding & d.m_fillRuleMask)

   350                 d.m_spanBuffer->addSpan(x, current - x, y, 0xff);

   351 

   352             x = current;

   353             winding += node->winding;

   354 

   355             if (node->bottom == y) {

   356                 // remove node from active list

   357                 for (int j = i; j < numActive - 1; ++j)

   358                     d.m_active.at(j) = d.m_active.at(j+1);

   359 

   360                 d.m_active.resize(--numActive);

   361                 --i;

   362             } else if (!allVertical())

   363                 node->x += node->delta;

   364         }

   365     }

   366     d.m_active.reset();

   367 }

   368 

   369 void QScanConverter::end()

   370 {

   371     if (m_lines.isEmpty())

   372         return;

   373 

   374     if (m_lines.size() <= 32) {

   375         bool allVertical = true;

   376         for (int i = 0; i < m_lines.size(); ++i) {

   377             if (m_lines.at(i).delta) {

   378                 allVertical = false;

   379                 break;

   380             }

   381         }

   382         if (allVertical)

   383             qScanConvert(*this, QBoolToType<true>());

   384         else

   385             qScanConvert(*this, QBoolToType<false>());

   386     } else {

   387         for (int chunkTop = m_top; chunkTop <= m_bottom; chunkTop += CHUNK_SIZE) {

   388             prepareChunk();

   389 

   390             Intersection isect = { 0, 0, 0, 0 };

   391 

   392             const int chunkBottom = chunkTop + CHUNK_SIZE;

   393             for (int i = 0; i < m_lines.size(); ++i) {

   394                 Line &line = m_lines.at(i);

   395 

   396                 if ((line.bottom < chunkTop) || (line.top > chunkBottom))

   397                     continue;

   398 

   399                 const int top = qMax(0, line.top - chunkTop);

   400                 const int bottom = qMin(CHUNK_SIZE, line.bottom + 1 - chunkTop);

   401                 allocate(m_size + bottom - top);

   402 

   403                 isect.winding = line.winding;

   404 

   405                 Intersection *it = m_intersections + top;

   406                 Intersection *end = m_intersections + bottom;

   407 

   408                 if (line.delta) {

   409                     for (; it != end; ++it) {

   410                         isect.x = Q16Dot16ToInt(line.x);

   411                         line.x += line.delta;

   412                         mergeIntersection(it, isect);

   413                     }

   414                 } else {

   415                     isect.x = Q16Dot16ToInt(line.x);

   416                     for (; it != end; ++it)

   417                         mergeIntersection(it, isect);

   418                 }

   419             }

   420 

   421             emitSpans(chunkTop);

   422         }

   423     }

   424 

   425     if (m_alloc > 1024) {

   426         free(m_intersections);

   427         m_alloc = 0;

   428         m_size = 0;

   429         m_intersections = 0;

   430     }

   431 

   432     if (m_lines.size() > 1024)

   433         m_lines.shrink(1024);

   434 }

   435 

   436 inline void QScanConverter::allocate(int size)

   437 {

   438     if (m_alloc < size) {

   439         int newAlloc = qMax(size, 2 * m_alloc);

   440         m_intersections = q_check_ptr((Intersection *)realloc(m_intersections, newAlloc * sizeof(Intersection)));

   441         m_alloc = newAlloc;

   442     }

   443 }

   444 

   445 inline void QScanConverter::mergeIntersection(Intersection *it, const Intersection &isect)

   446 {

   447     Intersection *current = it;

   448 

   449     while (isect.x != current->x) {

   450         int &next = isect.x < current->x ? current->left : current->right;

   451         if (next)

   452             current += next;

   453         else {

   454             Intersection *last = m_intersections + m_size;

   455             next = last - current;

   456             *last = isect;

   457             ++m_size;

   458             return;

   459         }

   460     }

   461 

   462     current->winding += isect.winding;

   463 }

   464 

   465 void QScanConverter::mergeCurve(const QT_FT_Vector &pa, const QT_FT_Vector &pb,

   466                                 const QT_FT_Vector &pc, const QT_FT_Vector &pd)

   467 {

   468     // make room for 32 splits

   469     QT_FT_Vector beziers[4 + 3 * 32];

   470 

   471     QT_FT_Vector *b = beziers;

   472 

   473     b[0] = pa;

   474     b[1] = pb;

   475     b[2] = pc;

   476     b[3] = pd;

   477 

   478     const QT_FT_Pos flatness = 16;

   479 

   480     while (b >= beziers) {

   481         QT_FT_Vector delta = { b[3].x - b[0].x, b[3].y - b[0].y };

   482         QT_FT_Pos l = qAbs(delta.x) + qAbs(delta.y);

   483 

   484         bool belowThreshold;

   485         if (l > 64) {

   486             qlonglong d2 = qAbs(qlonglong(b[1].x-b[0].x) * qlonglong(delta.y) -

   487                                 qlonglong(b[1].y-b[0].y) * qlonglong(delta.x));

   488             qlonglong d3 = qAbs(qlonglong(b[2].x-b[0].x) * qlonglong(delta.y) -

   489                                 qlonglong(b[2].y-b[0].y) * qlonglong(delta.x));

   490 

   491             qlonglong d = d2 + d3;

   492 

   493             belowThreshold = (d <= qlonglong(flatness) * qlonglong(l));

   494         } else {

   495             QT_FT_Pos d = qAbs(b[0].x-b[1].x) + qAbs(b[0].y-b[1].y) +

   496                           qAbs(b[0].x-b[2].x) + qAbs(b[0].y-b[2].y);

   497 

   498             belowThreshold = (d <= flatness);

   499         }

   500 

   501         if (belowThreshold || b == beziers + 3 * 32) {

   502             mergeLine(b[0], b[3]);

   503             b -= 3;

   504             continue;

   505         }

   506 

   507         split(b);

   508         b += 3;

   509     }

   510 }

   511 

   512 inline bool QScanConverter::clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding)

   513 {

   514     bool right = edgeFP == m_rightFP;

   515 

   516     if (xFP == edgeFP) {

   517         if ((slopeFP > 0) ^ right)

   518             return false;

   519         else {

   520             Line line = { edgeFP, 0, iTop, iBottom, winding };

   521             m_lines.add(line);

   522             return true;

   523         }

   524     }

   525 

   526     Q16Dot16 lastFP = xFP + slopeFP * (iBottom - iTop);

   527 

   528     if (lastFP == 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     // does line cross edge?

   539     if ((lastFP < edgeFP) ^ (xFP < edgeFP)) {

   540         Q16Dot16 deltaY = Q16Dot16((edgeFP - xFP) / Q16Dot16ToFloat(slopeFP));

   541 

   542         if ((xFP < edgeFP) ^ right) {

   543             // top segment needs to be clipped

   544             int iHeight = Q16Dot16ToInt(deltaY + 1);

   545             int iMiddle = iTop + iHeight;

   546 

   547             Line line = { edgeFP, 0, iTop, iMiddle, winding };

   548             m_lines.add(line);

   549 

   550             if (iMiddle != iBottom) {

   551                 xFP += slopeFP * (iHeight + 1);

   552                 iTop = iMiddle + 1;

   553             } else

   554                 return true;

   555         } else {

   556             // bottom segment needs to be clipped

   557             int iHeight = Q16Dot16ToInt(deltaY);

   558             int iMiddle = iTop + iHeight;

   559 

   560             if (iMiddle != iBottom) {

   561                 Line line = { edgeFP, 0, iMiddle + 1, iBottom, winding };

   562                 m_lines.add(line);

   563 

   564                 iBottom = iMiddle;

   565             }

   566         }

   567         return false;

   568     } else if ((xFP < edgeFP) ^ right) {

   569         Line line = { edgeFP, 0, iTop, iBottom, winding };

   570         m_lines.add(line);

   571         return true;

   572     }

   573 

   574     return false;

   575 }

   576 

   577 void QScanConverter::mergeLine(QT_FT_Vector a, QT_FT_Vector b)

   578 {

   579     int winding = 1;

   580 

   581     if (a.y > b.y) {

   582         qSwap(a, b);

   583         winding = -1;

   584     }

   585 

   586     a.x += COORD_OFFSET;

   587     a.y += COORD_OFFSET;

   588     b.x += COORD_OFFSET;

   589     b.y += COORD_OFFSET;

   590 

   591     int iTop = qMax(m_top, int((a.y + 32 - COORD_ROUNDING) >> 6));

   592     int iBottom = qMin(m_bottom, int((b.y - 32 - COORD_ROUNDING) >> 6));

   593 

   594     if (iTop <= iBottom) {

   595         Q16Dot16 aFP = Q16Dot16Factor/2 + (a.x << 10) - COORD_ROUNDING;

   596 

   597         if (b.x == a.x) {

   598             Line line = { qBound(m_leftFP, aFP, m_rightFP), 0, iTop, iBottom, winding };

   599             m_lines.add(line);

   600         } else {

   601             const qreal slope = (b.x - a.x) / qreal(b.y - a.y);

   602 

   603             const Q16Dot16 slopeFP = FloatToQ16Dot16(slope);

   604 

   605             Q16Dot16 xFP = aFP + Q16Dot16Multiply(slopeFP,

   606                                                   IntToQ16Dot16(iTop)

   607                                                   + Q16Dot16Factor/2 - (a.y << 10));

   608 

   609             if (clip(xFP, iTop, iBottom, slopeFP, m_leftFP, winding))

   610                 return;

   611 

   612             if (clip(xFP, iTop, iBottom, slopeFP, m_rightFP, winding))

   613                 return;

   614 

   615             Q_ASSERT(xFP >= m_leftFP);

   616 

   617             Line line = { xFP, slopeFP, iTop, iBottom, winding };

   618             m_lines.add(line);

   619         }

   620     }

   621 }

   622 

   623 QRasterizer::QRasterizer()

   624     : d(new QRasterizerPrivate)

   625 {

   626 }

   627 

   628 QRasterizer::~QRasterizer()

   629 {

   630     delete d;

   631 }

   632 

   633 void QRasterizer::setAntialiased(bool antialiased)

   634 {

   635     d->antialiased = antialiased;

   636 }

   637 

   638 void QRasterizer::initialize(ProcessSpans blend, void *data)

   639 {

   640     d->blend = blend;

   641     d->data = data;

   642 }

   643 

   644 void QRasterizer::setClipRect(const QRect &clipRect)

   645 {

   646     d->clipRect = clipRect;

   647 }

   648 

   649 static Q16Dot16 intersectPixelFP(int x, Q16Dot16 top, Q16Dot16 bottom, Q16Dot16 leftIntersectX, Q16Dot16 rightIntersectX, Q16Dot16 slope, Q16Dot16 invSlope)

   650 {

   651     Q16Dot16 leftX = IntToQ16Dot16(x);

   652     Q16Dot16 rightX = IntToQ16Dot16(x) + Q16Dot16Factor;

   653 

   654     Q16Dot16 leftIntersectY, rightIntersectY;

   655     if (slope > 0) {

   656         leftIntersectY = top + Q16Dot16Multiply(leftX - leftIntersectX, invSlope);

   657         rightIntersectY = leftIntersectY + invSlope;

   658     } else {

   659         leftIntersectY = top + Q16Dot16Multiply(leftX - rightIntersectX, invSlope);

   660         rightIntersectY = leftIntersectY + invSlope;

   661     }

   662 

   663     if (leftIntersectX >= leftX && rightIntersectX <= rightX) {

   664         return Q16Dot16Multiply(bottom - top, leftIntersectX - leftX + ((rightIntersectX - leftIntersectX) >> 1));

   665     } else if (leftIntersectX >= rightX) {

   666         return bottom - top;

   667     } else if (leftIntersectX >= leftX) {

   668         if (slope > 0) {

   669             return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, rightIntersectY - top);

   670         } else {

   671             return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, bottom - rightIntersectY);

   672         }

   673     } else if (rightIntersectX <= leftX) {

   674         return 0;

   675     } else if (rightIntersectX <= rightX) {

   676         if (slope > 0) {

   677             return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, bottom - leftIntersectY);

   678         } else {

   679             return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, leftIntersectY - top);

   680         }

   681     } else {

   682         if (slope > 0) {

   683             return (bottom - rightIntersectY) + ((rightIntersectY - leftIntersectY) >> 1);

   684         } else {

   685             return (rightIntersectY - top) + ((leftIntersectY - rightIntersectY) >> 1);

   686         }

   687     }

   688 }

   689 

   690 static inline bool q16Dot16Compare(qreal p1, qreal p2)

   691 {

   692     return FloatToQ16Dot16(p2 - p1) == 0;

   693 }

   694 

   695 static inline qreal qFloorF(qreal v)

   696 {

   697 #ifdef QT_USE_MATH_H_FLOATS

   698     if (sizeof(qreal) == sizeof(float))

   699         return floorf(v);

   700     else

   701 #endif

   702         return floor(v);

   703 }

   704 

   705 void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap)

   706 {

   707     if (a == b || width == 0 || d->clipRect.isEmpty())

   708         return;

   709 

   710     Q_ASSERT(width > 0.0);

   711 

   712     QPointF pa = a;

   713     QPointF pb = b;

   714 

   715     QPointF offs = QPointF(qAbs(b.y() - a.y()), qAbs(b.x() - a.x())) * width * 0.5;    

   716     if (squareCap)

   717         offs += QPointF(offs.y(), offs.x());

   718     const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs);

   719 

   720     if (!clip.contains(a) || !clip.contains(b)) {

   721         qreal t1 = 0;

   722         qreal t2 = 1;

   723 

   724         const qreal o[2] = { a.x(), a.y() };

   725         const qreal d[2] = { b.x() - a.x(), b.y() - a.y() };

   726 

   727         const qreal low[2] = { clip.left(), clip.top() };

   728         const qreal high[2] = { clip.right(), clip.bottom() };

   729 

   730         for (int i = 0; i < 2; ++i) {

   731             if (d[i] == 0) {

   732                 if (o[i] <= low[i] || o[i] >= high[i])

   733                     return;

   734                 continue;

   735             }

   736             const qreal d_inv = 1 / d[i];

   737             qreal t_low = (low[i] - o[i]) * d_inv;

   738             qreal t_high = (high[i] - o[i]) * d_inv;

   739             if (t_low > t_high)

   740                 qSwap(t_low, t_high);

   741             if (t1 < t_low)

   742                 t1 = t_low;

   743             if (t2 > t_high)

   744                 t2 = t_high;

   745             if (t1 >= t2)

   746                 return;

   747         }

   748         pa = a + (b - a) * t1;

   749         pb = a + (b - a) * t2;

   750     }

   751 

   752     if (!d->antialiased) {

   753         pa.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;

   754         pa.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;

   755         pb.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;

   756         pb.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;

   757     }

   758 

   759     {

   760         const qreal gridResolution = 64;

   761         const qreal reciprocal = 1 / gridResolution;

   762 

   763         // snap to grid to prevent large slopes

   764         pa.rx() = qFloorF(pa.rx() * gridResolution) * reciprocal;

   765         pa.ry() = qFloorF(pa.ry() * gridResolution) * reciprocal;

   766         pb.rx() = qFloorF(pb.rx() * gridResolution) * reciprocal;

   767         pb.ry() = qFloorF(pb.ry() * gridResolution) * reciprocal;

   768 

   769         // old delta

   770         const QPointF d0 = a - b;

   771         const qreal w0 = d0.x() * d0.x() + d0.y() * d0.y();

   772 

   773         // new delta

   774         const QPointF d = pa - pb;

   775         const qreal w = d.x() * d.x() + d.y() * d.y();

   776 

   777         if (w == 0)

   778             return;

   779 

   780         // adjust width which is given relative to |b - a|

   781         width *= sqrt(w0 / w);

   782     }

   783 

   784     QSpanBuffer buffer(d->blend, d->data, d->clipRect);

   785 

   786     if (q16Dot16Compare(pa.y(), pb.y())) {

   787         const qreal x = (pa.x() + pb.x()) * 0.5f;

   788         const qreal dx = qAbs(pb.x() - pa.x()) * 0.5f;

   789 

   790         const qreal y = pa.y();

   791         const qreal dy = width * dx;

   792 

   793         pa = QPointF(x, y - dy);

   794         pb = QPointF(x, y + dy);

   795 

   796         if (squareCap)

   797             width = 1 / width + 1.0f;

   798         else

   799             width = 1 / width;

   800 

   801         squareCap = false;

   802     }

   803 

   804     if (q16Dot16Compare(pa.x(), pb.x())) {

   805         if (pa.y() > pb.y())

   806             qSwap(pa, pb);

   807 

   808         const qreal dy = pb.y() - pa.y();

   809         const qreal halfWidth = 0.5f * width * dy;

   810 

   811         if (squareCap) {

   812             pa.ry() -= halfWidth;

   813             pb.ry() += halfWidth;

   814         }

   815 

   816         qreal left = pa.x() - halfWidth;

   817         qreal right = pa.x() + halfWidth;

   818 

   819         left = qBound(qreal(d->clipRect.left()), left, qreal(d->clipRect.right() + 1));

   820         right = qBound(qreal(d->clipRect.left()), right, qreal(d->clipRect.right() + 1));

   821 

   822         pa.ry() = qBound(qreal(d->clipRect.top()), pa.y(), qreal(d->clipRect.bottom() + 1));

   823         pb.ry() = qBound(qreal(d->clipRect.top()), pb.y(), qreal(d->clipRect.bottom() + 1));

   824 

   825         if (q16Dot16Compare(left, right) || q16Dot16Compare(pa.y(), pb.y()))

   826             return;

   827 

   828         if (d->antialiased) {

   829             const Q16Dot16 iLeft = int(left);

   830             const Q16Dot16 iRight = int(right);

   831             const Q16Dot16 leftWidth = IntToQ16Dot16(iLeft + 1)

   832                                        - FloatToQ16Dot16(left);

   833             const Q16Dot16 rightWidth = FloatToQ16Dot16(right)

   834                                         - IntToQ16Dot16(iRight);

   835 

   836             Q16Dot16 coverage[3];

   837             int x[3];

   838             int len[3];

   839 

   840             int n = 1;

   841             if (iLeft == iRight) {

   842                 coverage[0] = (leftWidth + rightWidth) * 255;

   843                 x[0] = iLeft;

   844                 len[0] = 1;

   845             } else {

   846                 coverage[0] = leftWidth * 255;

   847                 x[0] = iLeft;

   848                 len[0] = 1;

   849                 if (leftWidth == Q16Dot16Factor) {

   850                     len[0] = iRight - iLeft;

   851                 } else if (iRight - iLeft > 1) {

   852                     coverage[1] = IntToQ16Dot16(255);

   853                     x[1] = iLeft + 1;

   854                     len[1] = iRight - iLeft - 1;

   855                     ++n;

   856                 }

   857                 if (rightWidth) {

   858                     coverage[n] = rightWidth * 255;

   859                     x[n] = iRight;

   860                     len[n] = 1;

   861                     ++n;

   862                 }

   863             }

   864 

   865             const Q16Dot16 iTopFP = IntToQ16Dot16(int(pa.y()));

   866             const Q16Dot16 iBottomFP = IntToQ16Dot16(int(pb.y()));

   867             const Q16Dot16 yPa = FloatToQ16Dot16(pa.y());

   868             const Q16Dot16 yPb = FloatToQ16Dot16(pb.y());

   869             for (Q16Dot16 yFP = iTopFP; yFP <= iBottomFP; yFP += Q16Dot16Factor) {

   870                 const Q16Dot16 rowHeight = qMin(yFP + Q16Dot16Factor, yPb)

   871                                            - qMax(yFP, yPa);

   872                 const int y = Q16Dot16ToInt(yFP);

   873                 for (int i = 0; i < n; ++i) {

   874                     buffer.addSpan(x[i], len[i], y,

   875                                    Q16Dot16ToInt(Q16Dot16Multiply(rowHeight, coverage[i])));

   876                 }

   877             }

   878         } else { // aliased

   879             int iTop = int(pa.y() + 0.5f);

   880             int iBottom = pb.y() < 0.5f ? -1 : int(pb.y() - 0.5f);

   881             int iLeft = int(left + 0.5f);

   882             int iRight = right < 0.5f ? -1 : int(right - 0.5f);

   883 

   884             int iWidth = iRight - iLeft + 1;

   885             for (int y = iTop; y <= iBottom; ++y)

   886                 buffer.addSpan(iLeft, iWidth, y, 255);

   887         }

   888     } else {

   889         if (pa.y() > pb.y())

   890             qSwap(pa, pb);

   891 

   892         QPointF delta = pb - pa;

   893         delta *= 0.5f * width;

   894         const QPointF perp(delta.y(), -delta.x());

   895 

   896         if (squareCap) {

   897             pa -= delta;

   898             pb += delta;

   899         }

   900 

   901         QPointF top;

   902         QPointF left;

   903         QPointF right;

   904         QPointF bottom;

   905 

   906         if (pa.x() < pb.x()) {

   907             top = pa + perp;

   908             left = pa - perp;

   909             right = pb + perp;

   910             bottom = pb - perp;

   911         } else {

   912             top = pa - perp;

   913             left = pb - perp;

   914             right = pa + perp;

   915             bottom = pb + perp;

   916         }

   917 

   918         const qreal topBound = qBound(qreal(d->clipRect.top()), top.y(), qreal(d->clipRect.bottom()));

   919         const qreal bottomBound = qBound(qreal(d->clipRect.top()), bottom.y(), qreal(d->clipRect.bottom()));

   920 

   921         const qreal leftSlope = (left.x() - top.x()) / (left.y() - top.y());

   922         const qreal rightSlope = -1.0f / leftSlope;

   923 

   924         const Q16Dot16 leftSlopeFP = FloatToQ16Dot16(leftSlope);

   925         const Q16Dot16 rightSlopeFP = FloatToQ16Dot16(rightSlope);

   926 

   927         if (d->antialiased) {

   928             const Q16Dot16 iTopFP = IntToQ16Dot16(int(topBound));

   929             const Q16Dot16 iLeftFP = IntToQ16Dot16(int(left.y()));

   930             const Q16Dot16 iRightFP = IntToQ16Dot16(int(right.y()));

   931             const Q16Dot16 iBottomFP = IntToQ16Dot16(int(bottomBound));

   932 

   933             Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * leftSlope);

   934             Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * rightSlope);

   935             Q16Dot16 leftIntersectBf = 0;

   936             Q16Dot16 rightIntersectBf = 0;

   937 

   938             if (iLeftFP < iTopFP)

   939                 leftIntersectBf = FloatToQ16Dot16(left.x() + (int(topBound) - left.y()) * rightSlope);

   940 

   941             if (iRightFP < iTopFP)

   942                 rightIntersectBf = FloatToQ16Dot16(right.x() + (int(topBound) - right.y()) * leftSlope);

   943 

   944             Q16Dot16 rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom;

   945             Q16Dot16 topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf;

   946             Q16Dot16 bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf;

   947 

   948             int leftMin, leftMax, rightMin, rightMax;

   949 

   950             const Q16Dot16 yTopFP = FloatToQ16Dot16(top.y());

   951             const Q16Dot16 yLeftFP = FloatToQ16Dot16(left.y());

   952             const Q16Dot16 yRightFP = FloatToQ16Dot16(right.y());

   953             const Q16Dot16 yBottomFP = FloatToQ16Dot16(bottom.y());

   954 

   955             rowTop = qMax(iTopFP, yTopFP);

   956             topLeftIntersectAf = leftIntersectAf +

   957                                  Q16Dot16Multiply(leftSlopeFP, rowTop - iTopFP);

   958             topRightIntersectAf = rightIntersectAf +

   959                                   Q16Dot16Multiply(rightSlopeFP, rowTop - iTopFP);

   960 

   961             Q16Dot16 yFP = iTopFP;

   962             while (yFP <= iBottomFP) {

   963                 rowBottomLeft = qMin(yFP + Q16Dot16Factor, yLeftFP);

   964                 rowBottomRight = qMin(yFP + Q16Dot16Factor, yRightFP);

   965                 rowTopLeft = qMax(yFP, yLeftFP);

   966                 rowTopRight = qMax(yFP, yRightFP);

   967                 rowBottom = qMin(yFP + Q16Dot16Factor, yBottomFP);

   968 

   969                 if (yFP == iLeftFP) {

   970                     const int y = Q16Dot16ToInt(yFP);

   971                     leftIntersectBf = FloatToQ16Dot16(left.x() + (y - left.y()) * rightSlope);

   972                     topLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowTopLeft - yFP);

   973                     bottomLeftIntersectAf = leftIntersectAf + Q16Dot16Multiply(leftSlopeFP, rowBottomLeft - yFP);

   974                 } else {

   975                     topLeftIntersectBf = leftIntersectBf;

   976                     bottomLeftIntersectAf = leftIntersectAf + leftSlopeFP;

   977                 }

   978 

   979                 if (yFP == iRightFP) {

   980                     const int y = Q16Dot16ToInt(yFP);

   981                     rightIntersectBf = FloatToQ16Dot16(right.x() + (y - right.y()) * leftSlope);

   982                     topRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowTopRight - yFP);

   983                     bottomRightIntersectAf = rightIntersectAf + Q16Dot16Multiply(rightSlopeFP, rowBottomRight - yFP);

   984                 } else {

   985                     topRightIntersectBf = rightIntersectBf;

   986                     bottomRightIntersectAf = rightIntersectAf + rightSlopeFP;

   987                 }

   988 

   989                 if (yFP == iBottomFP) {

   990                     bottomLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowBottom - yFP);

   991                     bottomRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowBottom - yFP);

   992                 } else {

   993                     bottomLeftIntersectBf = leftIntersectBf + rightSlopeFP;

   994                     bottomRightIntersectBf = rightIntersectBf + leftSlopeFP;

   995                 }

   996 

   997                 if (yFP < iLeftFP) {

   998                     leftMin = Q16Dot16ToInt(bottomLeftIntersectAf);

   999                     leftMax = Q16Dot16ToInt(topLeftIntersectAf);

  1000                 } else if (yFP == iLeftFP) {

  1001                     leftMin = Q16Dot16ToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf));

  1002                     leftMax = Q16Dot16ToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf));

  1003                 } else {

  1004                     leftMin = Q16Dot16ToInt(topLeftIntersectBf);

  1005                     leftMax = Q16Dot16ToInt(bottomLeftIntersectBf);

  1006                 }

  1007 

  1008                 leftMin = qBound(d->clipRect.left(), leftMin, d->clipRect.right());

  1009                 leftMax = qBound(d->clipRect.left(), leftMax, d->clipRect.right());

  1010 

  1011                 if (yFP < iRightFP) {

  1012                     rightMin = Q16Dot16ToInt(topRightIntersectAf);

  1013                     rightMax = Q16Dot16ToInt(bottomRightIntersectAf);

  1014                 } else if (yFP == iRightFP) {

  1015                     rightMin = Q16Dot16ToInt(qMin(topRightIntersectAf, bottomRightIntersectBf));

  1016                     rightMax = Q16Dot16ToInt(qMin(bottomRightIntersectAf, topRightIntersectBf));

  1017                 } else {

  1018                     rightMin = Q16Dot16ToInt(bottomRightIntersectBf);

  1019                     rightMax = Q16Dot16ToInt(topRightIntersectBf);

  1020                 }

  1021 

  1022                 rightMin = qBound(d->clipRect.left(), rightMin, d->clipRect.right());

  1023                 rightMax = qBound(d->clipRect.left(), rightMax, d->clipRect.right());

  1024 

  1025                 if (leftMax > rightMax)

  1026                     leftMax = rightMax;

  1027                 if (rightMin < leftMin)

  1028                     rightMin = leftMin;

  1029 

  1030                 Q16Dot16 rowHeight = rowBottom - rowTop;

  1031 

  1032                 int x = leftMin;

  1033                 while (x <= leftMax) {

  1034                     Q16Dot16 excluded = 0;

  1035 

  1036                     if (yFP <= iLeftFP)

  1037                         excluded += intersectPixelFP(x, rowTop, rowBottomLeft,

  1038                                                      bottomLeftIntersectAf, topLeftIntersectAf,

  1039                                                      leftSlopeFP, -rightSlopeFP);

  1040                     if (yFP >= iLeftFP)

  1041                         excluded += intersectPixelFP(x, rowTopLeft, rowBottom,

  1042                                                      topLeftIntersectBf, bottomLeftIntersectBf,

  1043                                                      rightSlopeFP, -leftSlopeFP);

  1044 

  1045                     if (x >= rightMin) {

  1046                         if (yFP <= iRightFP)

  1047                             excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,

  1048                                                                                      topRightIntersectAf, bottomRightIntersectAf,

  1049                                                                                      rightSlopeFP, -leftSlopeFP);

  1050                         if (yFP >= iRightFP)

  1051                             excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,

  1052                                                                                      bottomRightIntersectBf, topRightIntersectBf,

  1053                                                                                      leftSlopeFP, -rightSlopeFP);

  1054                     }

  1055 

  1056                     Q16Dot16 coverage = rowHeight - excluded;

  1057                     buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),

  1058                                    Q16Dot16ToInt(255 * coverage));

  1059                     ++x;

  1060                 }

  1061                 if (x < rightMin) {

  1062                     buffer.addSpan(x, rightMin - x, Q16Dot16ToInt(yFP),

  1063                                    Q16Dot16ToInt(255 * rowHeight));

  1064                     x = rightMin;

  1065                 }

  1066                 while (x <= rightMax) {

  1067                     Q16Dot16 excluded = 0;

  1068                     if (yFP <= iRightFP)

  1069                         excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,

  1070                                                                                  topRightIntersectAf, bottomRightIntersectAf,

  1071                                                                                  rightSlopeFP, -leftSlopeFP);

  1072                     if (yFP >= iRightFP)

  1073                         excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,

  1074                                                                                  bottomRightIntersectBf, topRightIntersectBf,

  1075                                                                                  leftSlopeFP, -rightSlopeFP);

  1076 

  1077                     Q16Dot16 coverage = rowHeight - excluded;

  1078                     buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),

  1079                                    Q16Dot16ToInt(255 * coverage));

  1080                     ++x;

  1081                 }

  1082 

  1083                 leftIntersectAf += leftSlopeFP;

  1084                 leftIntersectBf += rightSlopeFP;

  1085                 rightIntersectAf += rightSlopeFP;

  1086                 rightIntersectBf += leftSlopeFP;

  1087                 topLeftIntersectAf = leftIntersectAf;

  1088                 topRightIntersectAf = rightIntersectAf;

  1089 

  1090                 yFP += Q16Dot16Factor;

  1091                 rowTop = yFP;

  1092             }

  1093         } else { // aliased

  1094             int iTop = int(top.y() + 0.5f);

  1095             int iLeft = left.y() < 0.5f ? -1 : int(left.y() - 0.5f);

  1096             int iRight = right.y() < 0.5f ? -1 : int(right.y() - 0.5f);

  1097             int iBottom = bottom.y() < 0.5f? -1 : int(bottom.y() - 0.5f);

  1098             int iMiddle = qMin(iLeft, iRight);

  1099 

  1100             Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + 0.5f + (iTop + 0.5f - top.y()) * leftSlope);

  1101             Q16Dot16 leftIntersectBf = FloatToQ16Dot16(left.x() + 0.5f + (iLeft + 1.5f - left.y()) * rightSlope);

  1102             Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() - 0.5f + (iTop + 0.5f - top.y()) * rightSlope);

  1103             Q16Dot16 rightIntersectBf = FloatToQ16Dot16(right.x() - 0.5f + (iRight + 1.5f - right.y()) * leftSlope);

  1104 

  1105             int ny;

  1106             int y = iTop;

  1107 #define DO_SEGMENT(next, li, ri, ls, rs) \

  1108             ny = qMin(next + 1, d->clipRect.top()); \

  1109             if (y < ny) { \

  1110                 li += ls * (ny - y); \

  1111                 ri += rs * (ny - y); \

  1112                 y = ny; \

  1113             } \

  1114             if (next > d->clipRect.bottom()) \

  1115                 next = d->clipRect.bottom(); \

  1116             for (; y <= next; ++y) { \

  1117                 const int x1 = qMax(Q16Dot16ToInt(li), d->clipRect.left()); \

  1118                 const int x2 = qMin(Q16Dot16ToInt(ri), d->clipRect.right()); \

  1119                 if (x2 >= x1) \

  1120                     buffer.addSpan(x1, x2 - x1 + 1, y, 255); \

  1121                 li += ls; \

  1122                 ri += rs; \

  1123              }

  1124 

  1125             DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, leftSlopeFP, rightSlopeFP)

  1126             DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, rightSlopeFP, rightSlopeFP)

  1127             DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, leftSlopeFP, leftSlopeFP)

  1128             DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, rightSlopeFP, leftSlopeFP)

  1129 #undef DO_SEGMENT

  1130         }

  1131     }

  1132 }

  1133 

  1134 void QRasterizer::rasterize(const QT_FT_Outline *outline, Qt::FillRule fillRule)