src/quick/scenegraph/util/qsgdistancefieldutil.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 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 QtDeclarative module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qsgdistancefieldutil_p.h"
  43
  44 #include <qmath.h>
  45 #include <private/qsgpathsimplifier_p.h>
  46 #include <private/qsgadaptationlayer_p.h>
  47 #include <QtGui/private/qopenglengineshadersource_p.h>
  48 #include <QtQuick/private/qsgcontext_p.h>
  49
  50 QT_BEGIN_NAMESPACE
  51
  52 static float defaultThresholdFunc(float glyphScale)
  53 {
  54     static float base = qgetenv("QT_DF_BASE").isEmpty() ? 0.5f : qgetenv("QT_DF_BASE").toFloat();
  55     static float baseDev = qgetenv("QT_DF_BASEDEVIATION").isEmpty() ? 0.065f : qgetenv("QT_DF_BASEDEVIATION").toFloat();
  56     static float devScaleMin = qgetenv("QT_DF_SCALEFORMAXDEV").isEmpty() ? 0.15f : qgetenv("QT_DF_SCALEFORMAXDEV").toFloat();
  57     static float devScaleMax = qgetenv("QT_DF_SCALEFORNODEV").isEmpty() ? 0.3f : qgetenv("QT_DF_SCALEFORNODEV").toFloat();
  58     return base - ((qBound(devScaleMin, glyphScale, devScaleMax) - devScaleMin) / (devScaleMax - devScaleMin) * -baseDev + baseDev);
  59 }
  60
  61 static float defaultAntialiasingSpreadFunc(float glyphScale)
  62 {
  63     static float range = qgetenv("QT_DF_RANGE").isEmpty() ? 0.06f : qgetenv("QT_DF_RANGE").toFloat();
  64     return range / glyphScale;
  65 }
  66
  67 namespace
  68 {
  69     enum FillHDir
  70     {
  71         LeftToRight,
  72         RightToLeft
  73     };
  74
  75     enum FillVDir
  76     {
  77         TopDown,
  78         BottomUp
  79     };
  80
  81     enum FillClip
  82     {
  83         NoClip,
  84         Clip
  85     };
  86 }
  87
  88 template <FillClip clip, FillHDir dir>
  89 inline void fillLine(qint32 *, int, int, int, qint32, qint32)
  90 {
  91 }
  92
  93 template <>
  94 inline void fillLine<Clip, LeftToRight>(qint32 *line, int width, int lx, int rx, qint32 d, qint32 dd)
  95 {
  96     int fromX = qMax(0, lx >> 8);
  97     int toX = qMin(width, rx >> 8);
  98     int x = toX - fromX;
  99     if (x <= 0)
 100         return;
 101     qint32 val = d + (((fromX << 8) + 0xff - lx) * dd >> 8);
 102     line += fromX;
 103     do {
 104         *line = abs(val) < abs(*line) ? val : *line;
 105         val += dd;
 106         ++line;
 107     } while (--x);
 108 }
 109
 110 template <>
 111 inline void fillLine<Clip, RightToLeft>(qint32 *line, int width, int lx, int rx, qint32 d, qint32 dd)
 112 {
 113     int fromX = qMax(0, lx >> 8);
 114     int toX = qMin(width, rx >> 8);
 115     int x = toX - fromX;
 116     if (x <= 0)
 117         return;
 118     qint32 val = d + (((toX << 8) + 0xff - rx) * dd >> 8);
 119     line += toX;
 120     do {
 121         val -= dd;
 122         --line;
 123         *line = abs(val) < abs(*line) ? val : *line;
 124     } while (--x);
 125 }
 126
 127 template <>
 128 inline void fillLine<NoClip, LeftToRight>(qint32 *line, int, int lx, int rx, qint32 d, qint32 dd)
 129 {
 130     int fromX = lx >> 8;
 131     int toX = rx >> 8;
 132     int x = toX - fromX;
 133     if (x <= 0)
 134         return;
 135     qint32 val = d + ((~lx & 0xff) * dd >> 8);
 136     line += fromX;
 137     do {
 138         *line = abs(val) < abs(*line) ? val : *line;
 139         val += dd;
 140         ++line;
 141     } while (--x);
 142 }
 143
 144 template <>
 145 inline void fillLine<NoClip, RightToLeft>(qint32 *line, int, int lx, int rx, qint32 d, qint32 dd)
 146 {
 147     int fromX = lx >> 8;
 148     int toX = rx >> 8;
 149     int x = toX - fromX;
 150     if (x <= 0)
 151         return;
 152     qint32 val = d + ((~rx & 0xff) * dd >> 8);
 153     line += toX;
 154     do {
 155         val -= dd;
 156         --line;
 157         *line = abs(val) < abs(*line) ? val : *line;
 158     } while (--x);
 159 }
 160
 161 template <FillClip clip, FillVDir vDir, FillHDir hDir>
 162 inline void fillLines(qint32 *bits, int width, int height, int upperY, int lowerY,
 163                       int &lx, int ldx, int &rx, int rdx, qint32 &d, qint32 ddy, qint32 ddx)
 164 {
 165     Q_UNUSED(height);
 166     Q_ASSERT(upperY < lowerY);
 167     int y = lowerY - upperY;
 168     if (vDir == TopDown) {
 169         qint32 *line = bits + upperY * width;
 170         do {
 171             fillLine<clip, hDir>(line, width, lx, rx, d, ddx);
 172             lx += ldx;
 173             d += ddy;
 174             rx += rdx;
 175             line += width;
 176         } while (--y);
 177     } else {
 178         qint32 *line = bits + lowerY * width;
 179         do {
 180             lx -= ldx;
 181             d -= ddy;
 182             rx -= rdx;
 183             line -= width;
 184             fillLine<clip, hDir>(line, width, lx, rx, d, ddx);
 185         } while (--y);
 186     }
 187 }
 188
 189 template <FillClip clip>
 190 void drawTriangle(qint32 *bits, int width, int height, const QPoint *center,
 191                   const QPoint *v1, const QPoint *v2, qint32 value)
 192 {
 193     const int y1 = clip == Clip ? qBound(0, v1->y() >> 8, height) : v1->y() >> 8;
 194     const int y2 = clip == Clip ? qBound(0, v2->y() >> 8, height) : v2->y() >> 8;
 195     const int yC = clip == Clip ? qBound(0, center->y() >> 8, height) : center->y() >> 8;
 196
 197     const int v1Frac = clip == Clip ? (y1 << 8) + 0xff - v1->y() : ~v2->y() & 0xff;
 198     const int v2Frac = clip == Clip ? (y2 << 8) + 0xff - v2->y() : ~v1->y() & 0xff;
 199     const int centerFrac = clip == Clip ? (yC << 8) + 0xff - center->y() : ~center->y() & 0xff;
 200
 201     int dx1 = 0, x1 = 0, dx2 = 0, x2 = 0;
 202     qint32 dd1, d1, dd2, d2;
 203     if (v1->y() != center->y()) {
 204         dx1 = ((v1->x() - center->x()) << 8) / (v1->y() - center->y());
 205         x1 = center->x() + centerFrac * (v1->x() - center->x()) / (v1->y() - center->y());
 206     }
 207     if (v2->y() != center->y()) {
 208         dx2 = ((v2->x() - center->x()) << 8) / (v2->y() - center->y());
 209         x2 = center->x() + centerFrac * (v2->x() - center->x()) / (v2->y() - center->y());
 210     }
 211
 212     const qint32 div = (v2->x() - center->x()) * (v1->y() - center->y())
 213                      - (v2->y() - center->y()) * (v1->x() - center->x());
 214     const qint32 dd = div ? qint32((qint64(value * (v1->y() - v2->y())) << 8) / div) : 0;
 215
 216     if (y2 < yC) {
 217         if (y1 < yC) {
 218             // Center at the bottom.
 219             if (y2 < y1) {
 220                 // y2 < y1 < yC
 221                 // Long right edge.
 222                 d1 = centerFrac * value / (v1->y() - center->y());
 223                 dd1 = ((value << 8) / (v1->y() - center->y()));
 224                 fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y1, yC, x1, dx1,
 225                                                        x2, dx2, d1, dd1, dd);
 226                 dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
 227                 x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
 228                 fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, y1, x1, dx1,
 229                                                        x2, dx2, value, 0, dd);
 230             } else {
 231                 // y1 <= y2 < yC
 232                 // Long left edge.
 233                 d2 = centerFrac * value / (v2->y() - center->y());
 234                 dd2 = ((value << 8) / (v2->y() - center->y()));
 235                 fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y2, yC, x1, dx1,
 236                                                        x2, dx2, d2, dd2, dd);
 237                 if (y1 != y2) {
 238                     dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
 239                     x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
 240                     fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, y2, x1, dx1,
 241                                                            x2, dx2, value, 0, dd);
 242                 }
 243             }
 244         } else {
 245             // y2 < yC <= y1
 246             // Center to the right.
 247             int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
 248             int xUp, xDn;
 249             xUp = xDn = v2->x() + (clip == Clip ? (yC << 8) + 0xff - v2->y()
 250                                                 : (center->y() | 0xff) - v2->y())
 251                         * (v1->x() - v2->x()) / (v1->y() - v2->y());
 252             fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, yC, xUp, dx,
 253                                                    x2, dx2, value, 0, dd);
 254             if (yC != y1)
 255                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y1, xDn, dx,
 256                                                       x1, dx1, value, 0, dd);
 257         }
 258     } else {
 259         if (y1 < yC) {
 260             // y1 < yC <= y2
 261             // Center to the left.
 262             int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
 263             int xUp, xDn;
 264             xUp = xDn = v1->x() + (clip == Clip ? (yC << 8) + 0xff - v1->y()
 265                                                 : (center->y() | 0xff) - v1->y())
 266                         * (v1->x() - v2->x()) / (v1->y() - v2->y());
 267             fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, yC, x1, dx1,
 268                                                    xUp, dx, value, 0, dd);
 269             if (yC != y2)
 270                 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y2, x2, dx2,
 271                                                       xDn, dx, value, 0, dd);
 272         } else {
 273             // Center at the top.
 274             if (y2 < y1) {
 275                 // yC <= y2 < y1
 276                 // Long right edge.
 277                 if (yC != y2) {
 278                     d2 = centerFrac * value / (v2->y() - center->y());
 279                     dd2 = ((value << 8) / (v2->y() - center->y()));
 280                     fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y2, x2, dx2,
 281                                                           x1, dx1, d2, dd2, dd);
 282                 }
 283                 dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
 284                 x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
 285                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, y2, y1, x2, dx2,
 286                                                       x1, dx1, value, 0, dd);
 287             } else {
 288                 // Long left edge.
 289                 // yC <= y1 <= y2
 290                 if (yC != y1) {
 291                     d1 = centerFrac * value / (v1->y() - center->y());
 292                     dd1 = ((value << 8) / (v1->y() - center->y()));
 293                     fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y1, x2, dx2,
 294                                                           x1, dx1, d1, dd1, dd);
 295                 }
 296                 if (y1 != y2) {
 297                     dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
 298                     x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
 299                     fillLines<clip, TopDown, RightToLeft>(bits, width, height, y1, y2, x2, dx2,
 300                                                           x1, dx1, value, 0, dd);
 301                 }
 302             }
 303         }
 304     }
 305 }
 306
 307 template <FillClip clip>
 308 void drawRectangle(qint32 *bits, int width, int height,
 309                    const QPoint *int1, const QPoint *center1, const QPoint *ext1,
 310                    const QPoint *int2, const QPoint *center2, const QPoint *ext2,
 311                    qint32 extValue)
 312 {
 313     if (center1->y() > center2->y()) {
 314         qSwap(center1, center2);
 315         qSwap(int1, ext2);
 316         qSwap(ext1, int2);
 317         extValue = -extValue;
 318     }
 319
 320     Q_ASSERT(ext1->x() - center1->x() == center1->x() - int1->x());
 321     Q_ASSERT(ext1->y() - center1->y() == center1->y() - int1->y());
 322     Q_ASSERT(ext2->x() - center2->x() == center2->x() - int2->x());
 323     Q_ASSERT(ext2->y() - center2->y() == center2->y() - int2->y());
 324
 325     const int yc1 = clip == Clip ? qBound(0, center1->y() >> 8, height) : center1->y() >> 8;
 326     const int yc2 = clip == Clip ? qBound(0, center2->y() >> 8, height) : center2->y() >> 8;
 327     const int yi1 = clip == Clip ? qBound(0, int1->y() >> 8, height) : int1->y() >> 8;
 328     const int yi2 = clip == Clip ? qBound(0, int2->y() >> 8, height) : int2->y() >> 8;
 329     const int ye1 = clip == Clip ? qBound(0, ext1->y() >> 8, height) : ext1->y() >> 8;
 330     const int ye2 = clip == Clip ? qBound(0, ext2->y() >> 8, height) : ext2->y() >> 8;
 331
 332     const int center1Frac = clip == Clip ? (yc1 << 8) + 0xff - center1->y() : ~center1->y() & 0xff;
 333     const int center2Frac = clip == Clip ? (yc2 << 8) + 0xff - center2->y() : ~center2->y() & 0xff;
 334     const int int1Frac = clip == Clip ? (yi1 << 8) + 0xff - int1->y() : ~int1->y() & 0xff;
 335     const int ext1Frac = clip == Clip ? (ye1 << 8) + 0xff - ext1->y() : ~ext1->y() & 0xff;
 336
 337     int dxC = 0, dxE = 0; // cap slope, edge slope
 338     qint32 ddC = 0;
 339     if (ext1->y() != int1->y()) {
 340         dxC = ((ext1->x() - int1->x()) << 8) / (ext1->y() - int1->y());
 341         ddC = (extValue << 9) / (ext1->y() - int1->y());
 342     }
 343     if (ext1->y() != ext2->y())
 344         dxE = ((ext1->x() - ext2->x()) << 8) / (ext1->y() - ext2->y());
 345
 346     const qint32 div = (ext1->x() - int1->x()) * (ext2->y() - int1->y())
 347                      - (ext1->y() - int1->y()) * (ext2->x() - int1->x());
 348     const qint32 dd = div ? qint32((qint64(extValue * (ext2->y() - ext1->y())) << 9) / div) : 0;
 349
 350     int xe1, xe2, xc1, xc2;
 351     qint32 d;
 352
 353     qint32 intValue = -extValue;
 354
 355     if (center2->x() < center1->x()) {
 356         // Leaning to the right. '/'
 357         if (int1->y() < ext2->y()) {
 358             // Mostly vertical.
 359             Q_ASSERT(ext1->y() != ext2->y());
 360             xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 361             xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 362             if (ye1 != yi1) {
 363                 xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 364                 xc2 += (ye1 - yc1) * dxC;
 365                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, yi1, xe1, dxE,
 366                                                       xc2, dxC, extValue, 0, dd);
 367             }
 368             if (yi1 != ye2)
 369                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi1, ye2, xe1, dxE,
 370                                                       xe2, dxE, extValue, 0, dd);
 371             if (ye2 != yi2) {
 372                 xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 373                 xc1 += (ye2 - yc2) * dxC;
 374                 fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye2, yi2, xc1, dxC,
 375                                                       xe2, dxE, intValue, 0, dd);
 376             }
 377         } else {
 378             // Mostly horizontal.
 379             Q_ASSERT(ext1->y() != int1->y());
 380             xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 381             xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 382             xc1 += (ye2 - yc2) * dxC;
 383             xc2 += (ye1 - yc1) * dxC;
 384             if (ye1 != ye2) {
 385                 xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 386                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE,
 387                                                       xc2, dxC, extValue, 0, dd);
 388             }
 389             if (ye2 != yi1) {
 390                 d = (clip == Clip ? (ye2 << 8) + 0xff - center2->y()
 391                                   : (ext2->y() | 0xff) - center2->y())
 392                     * 2 * extValue / (ext1->y() - int1->y());
 393                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye2, yi1, xc1, dxC,
 394                                                       xc2, dxC, d, ddC, dd);
 395             }
 396             if (yi1 != yi2) {
 397                 xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 398                 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC,
 399                                                       xe2, dxE, intValue, 0, dd);
 400             }
 401         }
 402     } else {
 403         // Leaning to the left. '\'
 404         if (ext1->y() < int2->y()) {
 405             // Mostly vertical.
 406             Q_ASSERT(ext1->y() != ext2->y());
 407             xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 408             xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 409             if (yi1 != ye1) {
 410                 xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 411                 xc1 += (yi1 - yc1) * dxC;
 412                 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, ye1, xc1, dxC,
 413                                                       xe2, dxE, intValue, 0, dd);
 414             }
 415             if (ye1 != yi2)
 416                 fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye1, yi2, xe1, dxE,
 417                                                       xe2, dxE, intValue, 0, dd);
 418             if (yi2 != ye2) {
 419                 xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 420                 xc2 += (yi2 - yc2) * dxC;
 421                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi2, ye2, xe1, dxE,
 422                                                       xc2, dxC, extValue, 0, dd);
 423             }
 424         } else {
 425             // Mostly horizontal.
 426             Q_ASSERT(ext1->y() != int1->y());
 427             xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 428             xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
 429             xc1 += (yi1 - yc1) * dxC;
 430             xc2 += (yi2 - yc2) * dxC;
 431             if (yi1 != yi2) {
 432                 xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 433                 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC,
 434                                                       xe2, dxE, intValue, 0, dd);
 435             }
 436             if (yi2 != ye1) {
 437                 d = (clip == Clip ? (yi2 << 8) + 0xff - center2->y()
 438                                   : (int2->y() | 0xff) - center2->y())
 439                     * 2 * extValue / (ext1->y() - int1->y());
 440                 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi2, ye1, xc1, dxC,
 441                                                       xc2, dxC, d, ddC, dd);
 442             }
 443             if (ye1 != ye2) {
 444                 xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
 445                 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE,
 446                                                       xc2, dxC, extValue, 0, dd);
 447             }
 448         }
 449     }
 450 }
 451
 452 static void drawPolygons(qint32 *bits, int width, int height, const QPoint *vertices,
 453                          const quint32 *indices, int indexCount, qint32 value)
 454 {
 455     Q_ASSERT(indexCount != 0);
 456     Q_ASSERT(height <= 128);
 457     QVarLengthArray<quint8, 16> scans[128];
 458     int first = 0;
 459     for (int i = 1; i < indexCount; ++i) {
 460         quint32 idx1 = indices[i - 1];
 461         quint32 idx2 = indices[i];
 462         Q_ASSERT(idx1 != quint32(-1));
 463         if (idx2 == quint32(-1)) {
 464             idx2 = indices[first];
 465             Q_ASSERT(idx2 != quint32(-1));
 466             first = ++i;
 467         }
 468         const QPoint *v1 = &vertices[idx1];
 469         const QPoint *v2 = &vertices[idx2];
 470         if (v2->y() < v1->y())
 471             qSwap(v1, v2);
 472         int fromY = qMax(0, v1->y() >> 8);
 473         int toY = qMin(height, v2->y() >> 8);
 474         if (fromY >= toY)
 475             continue;
 476         int dx = ((v2->x() - v1->x()) << 8) / (v2->y() - v1->y());
 477         int x = v1->x() + ((fromY << 8) + 0xff - v1->y()) * (v2->x() - v1->x()) / (v2->y() - v1->y());
 478         for (int y = fromY; y < toY; ++y) {
 479             quint32 c = quint32(x >> 8);
 480             if (c < quint32(width))
 481                 scans[y].append(quint8(c));
 482             x += dx;
 483         }
 484     }
 485     for (int i = 0; i < height; ++i) {
 486         quint8 *scanline = scans[i].data();
 487         int size = scans[i].size();
 488         for (int j = 1; j < size; ++j) {
 489             int k = j;
 490             quint8 value = scanline[k];
 491             for (; k != 0 && value < scanline[k - 1]; --k)
 492                 scanline[k] = scanline[k - 1];
 493             scanline[k] = value;
 494         }
 495         qint32 *line = bits + i * width;
 496         int j = 0;
 497         for (; j + 1 < size; j += 2) {
 498             for (quint8 x = scanline[j]; x < scanline[j + 1]; ++x)
 499                 line[x] = value;
 500         }
 501         if (j < size) {
 502             for (int x = scanline[j]; x < width; ++x)
 503                 line[x] = value;
 504         }
 505     }
 506 }
 507
 508 static QImage makeDistanceField(int imgSize, const QPainterPath &path, int dfScale, int offs)
 509 {
 510     QImage image(imgSize, imgSize, QImage::Format_Indexed8);
 511
 512     if (path.isEmpty()) {
 513         image.fill(0);
 514         return image;
 515     }
 516
 517     QTransform transform;
 518     transform.translate(offs, offs);
 519     transform.scale(qreal(1) / dfScale, qreal(1) / dfScale);
 520
 521     QDataBuffer<quint32> pathIndices(0);
 522     QDataBuffer<QPoint> pathVertices(0);
 523     qSimplifyPath(path, pathVertices, pathIndices, transform);
 524
 525     const qint32 interiorColor = -0x7f80; // 8:8 signed format, -127.5
 526     const qint32 exteriorColor = 0x7f80; // 8:8 signed format, 127.5
 527
 528     QScopedArrayPointer<qint32> bits(new qint32[imgSize * imgSize]);
 529     for (int i = 0; i < imgSize * imgSize; ++i)
 530         bits[i] = exteriorColor;
 531
 532     const qreal angleStep = qreal(15 * 3.141592653589793238 / 180);
 533     const QPoint rotation(qRound(cos(angleStep) * 0x4000),
 534                           qRound(sin(angleStep) * 0x4000)); // 2:14 signed
 535
 536     const quint32 *indices = pathIndices.data();
 537     QVarLengthArray<QPoint> normals;
 538     QVarLengthArray<QPoint> vertices;
 539     QVarLengthArray<bool> isConvex;
 540     QVarLengthArray<bool> needsClipping;
 541
 542     drawPolygons(bits.data(), imgSize, imgSize, pathVertices.data(), indices, pathIndices.size(),
 543                  interiorColor);
 544
 545     int index = 0;
 546
 547     while (index < pathIndices.size()) {
 548         normals.clear();
 549         vertices.clear();
 550         needsClipping.clear();
 551
 552         // Find end of polygon.
 553         int end = index;
 554         while (indices[end] != quint32(-1))
 555             ++end;
 556
 557         // Calculate vertex normals.
 558         for (int next = index, prev = end - 1; next < end; prev = next++) {
 559             quint32 fromVertexIndex = indices[prev];
 560             quint32 toVertexIndex = indices[next];
 561
 562             const QPoint &from = pathVertices.at(fromVertexIndex);
 563             const QPoint &to = pathVertices.at(toVertexIndex);
 564
 565             QPoint n(to.y() - from.y(), from.x() - to.x());
 566             if (n.x() == 0 && n.y() == 0)
 567                 continue;
 568             int scale = qRound((offs << 16) / sqrt(qreal(n.x() * n.x() + n.y() * n.y()))); // 8:16
 569             n.rx() = n.x() * scale >> 8;
 570             n.ry() = n.y() * scale >> 8;
 571             normals.append(n);
 572             QPoint v(to.x() + 0x7f, to.y() + 0x7f);
 573             vertices.append(v);
 574             needsClipping.append((to.x() < offs << 8) || (to.x() >= (imgSize - offs) << 8)
 575                                  || (to.y() < offs << 8) || (to.y() >= (imgSize - offs) << 8));
 576         }
 577
 578         isConvex.resize(normals.count());
 579         for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) {
 580             isConvex[prev] = normals.at(prev).x() * normals.at(next).y()
 581                            - normals.at(prev).y() * normals.at(next).x() < 0;
 582         }
 583
 584         // Draw quads.
 585         for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) {
 586             QPoint n = normals.at(next);
 587             QPoint intPrev = vertices.at(prev);
 588             QPoint extPrev = vertices.at(prev);
 589             QPoint intNext = vertices.at(next);
 590             QPoint extNext = vertices.at(next);
 591
 592             extPrev.rx() -= n.x();
 593             extPrev.ry() -= n.y();
 594             intPrev.rx() += n.x();
 595             intPrev.ry() += n.y();
 596             extNext.rx() -= n.x();
 597             extNext.ry() -= n.y();
 598             intNext.rx() += n.x();
 599             intNext.ry() += n.y();
 600
 601             if (needsClipping[prev] || needsClipping[next]) {
 602                 drawRectangle<Clip>(bits.data(), imgSize, imgSize,
 603                                     &intPrev, &vertices.at(prev), &extPrev,
 604                                     &intNext, &vertices.at(next), &extNext,
 605                                     exteriorColor);
 606             } else {
 607                 drawRectangle<NoClip>(bits.data(), imgSize, imgSize,
 608                                       &intPrev, &vertices.at(prev), &extPrev,
 609                                       &intNext, &vertices.at(next), &extNext,
 610                                       exteriorColor);
 611             }
 612
 613             if (isConvex.at(prev)) {
 614                 QPoint p = extPrev;
 615                 if (needsClipping[prev]) {
 616                     for (;;) {
 617                         QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
 618                                   (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
 619                         n = rn;
 620                         if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) {
 621                             p.rx() = vertices.at(prev).x() - normals.at(prev).x();
 622                             p.ry() = vertices.at(prev).y() - normals.at(prev).y();
 623                             drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 624                                                &extPrev, &p, exteriorColor);
 625                             break;
 626                         }
 627
 628                         p.rx() = vertices.at(prev).x() - n.x();
 629                         p.ry() = vertices.at(prev).y() - n.y();
 630                         drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 631                                            &extPrev, &p, exteriorColor);
 632                         extPrev = p;
 633                     }
 634                 } else {
 635                     for (;;) {
 636                         QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
 637                                   (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
 638                         n = rn;
 639                         if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) {
 640                             p.rx() = vertices.at(prev).x() - normals.at(prev).x();
 641                             p.ry() = vertices.at(prev).y() - normals.at(prev).y();
 642                             drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 643                                                  &extPrev, &p, exteriorColor);
 644                             break;
 645                         }
 646
 647                         p.rx() = vertices.at(prev).x() - n.x();
 648                         p.ry() = vertices.at(prev).y() - n.y();
 649                         drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 650                                              &extPrev, &p, exteriorColor);
 651                         extPrev = p;
 652                     }
 653                 }
 654             } else {
 655                 QPoint p = intPrev;
 656                 if (needsClipping[prev]) {
 657                     for (;;) {
 658                         QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
 659                                   (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
 660                         n = rn;
 661                         if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) {
 662                             p.rx() = vertices.at(prev).x() + normals.at(prev).x();
 663                             p.ry() = vertices.at(prev).y() + normals.at(prev).y();
 664                             drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 665                                                &p, &intPrev, interiorColor);
 666                             break;
 667                         }
 668
 669                         p.rx() = vertices.at(prev).x() + n.x();
 670                         p.ry() = vertices.at(prev).y() + n.y();
 671                         drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 672                                            &p, &intPrev, interiorColor);
 673                         intPrev = p;
 674                     }
 675                 } else {
 676                     for (;;) {
 677                         QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
 678                                   (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
 679                         n = rn;
 680                         if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) {
 681                             p.rx() = vertices.at(prev).x() + normals.at(prev).x();
 682                             p.ry() = vertices.at(prev).y() + normals.at(prev).y();
 683                             drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 684                                                  &p, &intPrev, interiorColor);
 685                             break;
 686                         }
 687
 688                         p.rx() = vertices.at(prev).x() + n.x();
 689                         p.ry() = vertices.at(prev).y() + n.y();
 690                         drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev),
 691                                              &p, &intPrev, interiorColor);
 692                         intPrev = p;
 693                     }
 694                 }
 695             }
 696         }
 697
 698         index = end + 1;
 699     }
 700
 701     const qint32 *inLine = bits.data();
 702     uchar *outLine = image.bits();
 703     int padding = image.bytesPerLine() - image.width();
 704     for (int y = 0; y < imgSize; ++y) {
 705         for (int x = 0; x < imgSize; ++x, ++inLine, ++outLine)
 706             *outLine = uchar((0x7f80 - *inLine) >> 8);
 707         outLine += padding;
 708     }
 709
 710     return image;
 711 }
 712
 713 bool qt_fontHasNarrowOutlines(const QRawFont &f)
 714 {
 715     QRawFont font = f;
 716     font.setPixelSize(QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE);
 717     Q_ASSERT(font.isValid());
 718
 719     QVector<quint32> glyphIndices = font.glyphIndexesForString(QLatin1String("O"));
 720     if (glyphIndices.size() < 1)
 721         return false;
 722
 723     QImage im = font.alphaMapForGlyph(glyphIndices.at(0), QRawFont::PixelAntialiasing);
 724     if (im.isNull())
 725         return false;
 726
 727     int minHThick = 999;
 728     int minVThick = 999;
 729
 730     int thick = 0;
 731     bool in = false;
 732     int y = (im.height() + 1) / 2;
 733     for (int x = 0; x < im.width(); ++x) {
 734         int a = qAlpha(im.pixel(x, y));
 735         if (a > 127) {
 736             in = true;
 737             ++thick;
 738         } else if (in) {
 739             in = false;
 740             minHThick = qMin(minHThick, thick);
 741             thick = 0;
 742         }
 743     }
 744
 745     thick = 0;
 746     in = false;
 747     int x = (im.width() + 1) / 2;
 748     for (int y = 0; y < im.height(); ++y) {
 749         int a = qAlpha(im.pixel(x, y));
 750         if (a > 127) {
 751             in = true;
 752             ++thick;
 753         } else if (in) {
 754             in = false;
 755             minVThick = qMin(minVThick, thick);
 756             thick = 0;
 757         }
 758     }
 759
 760     return minHThick == 1 || minVThick == 1;
 761 }
 762
 763 QImage qt_renderDistanceFieldGlyph(const QRawFont &font, glyph_t glyph, bool doubleResolution)
 764 {
 765     QRawFont renderFont = font;
 766     renderFont.setPixelSize(QT_DISTANCEFIELD_BASEFONTSIZE(doubleResolution) * QT_DISTANCEFIELD_SCALE(doubleResolution));
 767
 768     QPainterPath path = renderFont.pathForGlyph(glyph);
 769     path.translate(-path.boundingRect().topLeft());
 770     path.setFillRule(Qt::WindingFill);
 771
 772     QImage im = makeDistanceField(QT_DISTANCEFIELD_TILESIZE(doubleResolution),
 773                                   path,
 774                                   QT_DISTANCEFIELD_SCALE(doubleResolution),
 775                                   QT_DISTANCEFIELD_RADIUS(doubleResolution) / QT_DISTANCEFIELD_SCALE(doubleResolution));
 776     return im;
 777 }
 778
 779 QSGDistanceFieldGlyphCacheManager::QSGDistanceFieldGlyphCacheManager(QSGContext *c)
 780     : sgCtx(c)
 781     , m_threshold_func(defaultThresholdFunc)
 782     , m_antialiasingSpread_func(defaultAntialiasingSpreadFunc)
 783 {
 784 #ifndef QT_OPENGL_ES
 785     m_defaultAntialiasingMode = QSGGlyphNode::HighQualitySubPixelAntialiasing;
 786 #else
 787     m_defaultAntialiasingMode = QSGGlyphNode::GrayAntialiasing;
 788 #endif
 789 }
 790
 791 QSGDistanceFieldGlyphCacheManager::~QSGDistanceFieldGlyphCacheManager()
 792 {
 793     qDeleteAll(m_caches.values());
 794 }
 795
 796 QSGDistanceFieldGlyphCache *QSGDistanceFieldGlyphCacheManager::cache(const QRawFont &font)
 797 {
 798     QRawFontPrivate *fontD = QRawFontPrivate::get(font);
 799     QHash<QFontEngine *, QSGDistanceFieldGlyphCache *>::iterator cache = m_caches.find(fontD->fontEngine);
 800     if (cache == m_caches.end())
 801         cache = m_caches.insert(fontD->fontEngine, sgCtx->createDistanceFieldGlyphCache(font));
 802     return cache.value();
 803 }
 804
 805 QT_END_NAMESPACE