Update copyright year in Nokia copyright headers.
[profile/ivi/qtdeclarative.git] / 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