src/gui/text/qdistancefield.cpp

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