1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtGui module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qdistancefield_p.h"
41#include <qmath.h>
42#include <private/qdatabuffer_p.h>
43#include <private/qimage_p.h>
44#include <private/qpathsimplifier_p.h>
45
46QT_BEGIN_NAMESPACE
47
48Q_LOGGING_CATEGORY(lcDistanceField, "qt.distanceField");
49
50namespace
51{
52 enum FillHDir
53 {
54 LeftToRight,
55 RightToLeft
56 };
57
58 enum FillVDir
59 {
60 TopDown,
61 BottomUp
62 };
63
64 enum FillClip
65 {
66 NoClip,
67 Clip
68 };
69}
70
71template <FillClip clip, FillHDir dir>
72inline void fillLine(qint32 *, int, int, int, qint32, qint32)
73{
74}
75
76template <>
77inline void fillLine<Clip, LeftToRight>(qint32 *line, int width, int lx, int rx, qint32 d, qint32 dd)
78{
79 int fromX = qMax(0, lx >> 8);
80 int toX = qMin(width, rx >> 8);
81 int x = toX - fromX;
82 if (x <= 0)
83 return;
84 qint32 val = d + (((fromX << 8) + 0xff - lx) * dd >> 8);
85 line += fromX;
86 do {
87 *line = abs(val) < abs(*line) ? val : *line;
88 val += dd;
89 ++line;
90 } while (--x);
91}
92
93template <>
94inline void fillLine<Clip, RightToLeft>(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 + (((toX << 8) + 0xff - rx) * dd >> 8);
102 line += toX;
103 do {
104 val -= dd;
105 --line;
106 *line = abs(val) < abs(*line) ? val : *line;
107 } while (--x);
108}
109
110template <>
111inline void fillLine<NoClip, LeftToRight>(qint32 *line, int, int lx, int rx, qint32 d, qint32 dd)
112{
113 int fromX = lx >> 8;
114 int toX = rx >> 8;
115 int x = toX - fromX;
116 if (x <= 0)
117 return;
118 qint32 val = d + ((~lx & 0xff) * dd >> 8);
119 line += fromX;
120 do {
121 *line = abs(val) < abs(*line) ? val : *line;
122 val += dd;
123 ++line;
124 } while (--x);
125}
126
127template <>
128inline void fillLine<NoClip, RightToLeft>(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 + ((~rx & 0xff) * dd >> 8);
136 line += toX;
137 do {
138 val -= dd;
139 --line;
140 *line = abs(val) < abs(*line) ? val : *line;
141 } while (--x);
142}
143
144template <FillClip clip, FillVDir vDir, FillHDir hDir>
145inline void fillLines(qint32 *bits, int width, int height, int upperY, int lowerY,
146 int &lx, int ldx, int &rx, int rdx, qint32 &d, qint32 ddy, qint32 ddx)
147{
148 Q_UNUSED(height);
149 Q_ASSERT(upperY < lowerY);
150 int y = lowerY - upperY;
151 if (vDir == TopDown) {
152 qint32 *line = bits + upperY * width;
153 do {
154 fillLine<clip, hDir>(line, width, lx, rx, d, ddx);
155 lx += ldx;
156 d += ddy;
157 rx += rdx;
158 line += width;
159 } while (--y);
160 } else {
161 qint32 *line = bits + lowerY * width;
162 do {
163 lx -= ldx;
164 d -= ddy;
165 rx -= rdx;
166 line -= width;
167 fillLine<clip, hDir>(line, width, lx, rx, d, ddx);
168 } while (--y);
169 }
170}
171
172template <FillClip clip>
173void drawTriangle(qint32 *bits, int width, int height, const QPoint *center,
174 const QPoint *v1, const QPoint *v2, qint32 value)
175{
176 const int y1 = clip == Clip ? qBound(0, v1->y() >> 8, height) : v1->y() >> 8;
177 const int y2 = clip == Clip ? qBound(0, v2->y() >> 8, height) : v2->y() >> 8;
178 const int yC = clip == Clip ? qBound(0, center->y() >> 8, height) : center->y() >> 8;
179
180 const int v1Frac = clip == Clip ? (y1 << 8) + 0xff - v1->y() : ~v1->y() & 0xff;
181 const int v2Frac = clip == Clip ? (y2 << 8) + 0xff - v2->y() : ~v2->y() & 0xff;
182 const int centerFrac = clip == Clip ? (yC << 8) + 0xff - center->y() : ~center->y() & 0xff;
183
184 int dx1 = 0, x1 = 0, dx2 = 0, x2 = 0;
185 qint32 dd1, d1, dd2, d2;
186 if (v1->y() != center->y()) {
187 dx1 = ((v1->x() - center->x()) << 8) / (v1->y() - center->y());
188 x1 = center->x() + centerFrac * (v1->x() - center->x()) / (v1->y() - center->y());
189 }
190 if (v2->y() != center->y()) {
191 dx2 = ((v2->x() - center->x()) << 8) / (v2->y() - center->y());
192 x2 = center->x() + centerFrac * (v2->x() - center->x()) / (v2->y() - center->y());
193 }
194
195 const qint32 div = (v2->x() - center->x()) * (v1->y() - center->y())
196 - (v2->y() - center->y()) * (v1->x() - center->x());
197 const qint32 dd = div ? qint32((qint64(value * (v1->y() - v2->y())) << 8) / div) : 0;
198
199 if (y2 < yC) {
200 if (y1 < yC) {
201 // Center at the bottom.
202 if (y2 < y1) {
203 // y2 < y1 < yC
204 // Long right edge.
205 d1 = centerFrac * value / (v1->y() - center->y());
206 dd1 = ((value << 8) / (v1->y() - center->y()));
207 fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y1, yC, x1, dx1,
208 x2, dx2, d1, dd1, dd);
209 dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
210 x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
211 fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, y1, x1, dx1,
212 x2, dx2, value, 0, dd);
213 } else {
214 // y1 <= y2 < yC
215 // Long left edge.
216 d2 = centerFrac * value / (v2->y() - center->y());
217 dd2 = ((value << 8) / (v2->y() - center->y()));
218 fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y2, yC, x1, dx1,
219 x2, dx2, d2, dd2, dd);
220 if (y1 != y2) {
221 dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
222 x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
223 fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, y2, x1, dx1,
224 x2, dx2, value, 0, dd);
225 }
226 }
227 } else {
228 // y2 < yC <= y1
229 // Center to the right.
230 int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
231 int xUp, xDn;
232 xUp = xDn = v2->x() + (clip == Clip ? (yC << 8) + 0xff - v2->y()
233 : (center->y() | 0xff) - v2->y())
234 * (v1->x() - v2->x()) / (v1->y() - v2->y());
235 fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, yC, xUp, dx,
236 x2, dx2, value, 0, dd);
237 if (yC != y1)
238 fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y1, xDn, dx,
239 x1, dx1, value, 0, dd);
240 }
241 } else {
242 if (y1 < yC) {
243 // y1 < yC <= y2
244 // Center to the left.
245 int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
246 int xUp, xDn;
247 xUp = xDn = v1->x() + (clip == Clip ? (yC << 8) + 0xff - v1->y()
248 : (center->y() | 0xff) - v1->y())
249 * (v1->x() - v2->x()) / (v1->y() - v2->y());
250 fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, yC, x1, dx1,
251 xUp, dx, value, 0, dd);
252 if (yC != y2)
253 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y2, x2, dx2,
254 xDn, dx, value, 0, dd);
255 } else {
256 // Center at the top.
257 if (y2 < y1) {
258 // yC <= y2 < y1
259 // Long right edge.
260 if (yC != y2) {
261 d2 = centerFrac * value / (v2->y() - center->y());
262 dd2 = ((value << 8) / (v2->y() - center->y()));
263 fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y2, x2, dx2,
264 x1, dx1, d2, dd2, dd);
265 }
266 dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
267 x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
268 fillLines<clip, TopDown, LeftToRight>(bits, width, height, y2, y1, x2, dx2,
269 x1, dx1, value, 0, dd);
270 } else {
271 // Long left edge.
272 // yC <= y1 <= y2
273 if (yC != y1) {
274 d1 = centerFrac * value / (v1->y() - center->y());
275 dd1 = ((value << 8) / (v1->y() - center->y()));
276 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y1, x2, dx2,
277 x1, dx1, d1, dd1, dd);
278 }
279 if (y1 != y2) {
280 dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y());
281 x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y());
282 fillLines<clip, TopDown, RightToLeft>(bits, width, height, y1, y2, x2, dx2,
283 x1, dx1, value, 0, dd);
284 }
285 }
286 }
287 }
288}
289
290template <FillClip clip>
291void drawRectangle(qint32 *bits, int width, int height,
292 const QPoint *int1, const QPoint *center1, const QPoint *ext1,
293 const QPoint *int2, const QPoint *center2, const QPoint *ext2,
294 qint32 extValue)
295{
296 if (center1->y() > center2->y()) {
297 qSwap(center1, center2);
298 qSwap(int1, ext2);
299 qSwap(ext1, int2);
300 extValue = -extValue;
301 }
302
303 Q_ASSERT(ext1->x() - center1->x() == center1->x() - int1->x());
304 Q_ASSERT(ext1->y() - center1->y() == center1->y() - int1->y());
305 Q_ASSERT(ext2->x() - center2->x() == center2->x() - int2->x());
306 Q_ASSERT(ext2->y() - center2->y() == center2->y() - int2->y());
307
308 const int yc1 = clip == Clip ? qBound(0, center1->y() >> 8, height) : center1->y() >> 8;
309 const int yc2 = clip == Clip ? qBound(0, center2->y() >> 8, height) : center2->y() >> 8;
310 const int yi1 = clip == Clip ? qBound(0, int1->y() >> 8, height) : int1->y() >> 8;
311 const int yi2 = clip == Clip ? qBound(0, int2->y() >> 8, height) : int2->y() >> 8;
312 const int ye1 = clip == Clip ? qBound(0, ext1->y() >> 8, height) : ext1->y() >> 8;
313 const int ye2 = clip == Clip ? qBound(0, ext2->y() >> 8, height) : ext2->y() >> 8;
314
315 const int center1Frac = clip == Clip ? (yc1 << 8) + 0xff - center1->y() : ~center1->y() & 0xff;
316 const int center2Frac = clip == Clip ? (yc2 << 8) + 0xff - center2->y() : ~center2->y() & 0xff;
317 const int int1Frac = clip == Clip ? (yi1 << 8) + 0xff - int1->y() : ~int1->y() & 0xff;
318 const int ext1Frac = clip == Clip ? (ye1 << 8) + 0xff - ext1->y() : ~ext1->y() & 0xff;
319
320 int dxC = 0, dxE = 0; // cap slope, edge slope
321 qint32 ddC = 0;
322 if (ext1->y() != int1->y()) {
323 dxC = ((ext1->x() - int1->x()) << 8) / (ext1->y() - int1->y());
324 ddC = (extValue << 9) / (ext1->y() - int1->y());
325 }
326 if (ext1->y() != ext2->y())
327 dxE = ((ext1->x() - ext2->x()) << 8) / (ext1->y() - ext2->y());
328
329 const qint32 div = (ext1->x() - int1->x()) * (ext2->y() - int1->y())
330 - (ext1->y() - int1->y()) * (ext2->x() - int1->x());
331 const qint32 dd = div ? qint32((qint64(extValue * (ext2->y() - ext1->y())) << 9) / div) : 0;
332
333 int xe1, xe2, xc1, xc2;
334 qint32 d;
335
336 qint32 intValue = -extValue;
337
338 if (center2->x() < center1->x()) {
339 // Leaning to the right. '/'
340 if (int1->y() < ext2->y()) {
341 // Mostly vertical.
342 Q_ASSERT(ext1->y() != ext2->y());
343 xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
344 xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
345 if (ye1 != yi1) {
346 xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
347 xc2 += (ye1 - yc1) * dxC;
348 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, yi1, xe1, dxE,
349 xc2, dxC, extValue, 0, dd);
350 }
351 if (yi1 != ye2)
352 fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi1, ye2, xe1, dxE,
353 xe2, dxE, extValue, 0, dd);
354 if (ye2 != yi2) {
355 xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
356 xc1 += (ye2 - yc2) * dxC;
357 fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye2, yi2, xc1, dxC,
358 xe2, dxE, intValue, 0, dd);
359 }
360 } else {
361 // Mostly horizontal.
362 Q_ASSERT(ext1->y() != int1->y());
363 xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
364 xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
365 xc1 += (ye2 - yc2) * dxC;
366 xc2 += (ye1 - yc1) * dxC;
367 if (ye1 != ye2) {
368 xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
369 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE,
370 xc2, dxC, extValue, 0, dd);
371 }
372 if (ye2 != yi1) {
373 d = (clip == Clip ? (ye2 << 8) + 0xff - center2->y()
374 : (ext2->y() | 0xff) - center2->y())
375 * 2 * extValue / (ext1->y() - int1->y());
376 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye2, yi1, xc1, dxC,
377 xc2, dxC, d, ddC, dd);
378 }
379 if (yi1 != yi2) {
380 xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
381 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC,
382 xe2, dxE, intValue, 0, dd);
383 }
384 }
385 } else {
386 // Leaning to the left. '\'
387 if (ext1->y() < int2->y()) {
388 // Mostly vertical.
389 Q_ASSERT(ext1->y() != ext2->y());
390 xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
391 xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
392 if (yi1 != ye1) {
393 xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
394 xc1 += (yi1 - yc1) * dxC;
395 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, ye1, xc1, dxC,
396 xe2, dxE, intValue, 0, dd);
397 }
398 if (ye1 != yi2)
399 fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye1, yi2, xe1, dxE,
400 xe2, dxE, intValue, 0, dd);
401 if (yi2 != ye2) {
402 xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
403 xc2 += (yi2 - yc2) * dxC;
404 fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi2, ye2, xe1, dxE,
405 xc2, dxC, extValue, 0, dd);
406 }
407 } else {
408 // Mostly horizontal.
409 Q_ASSERT(ext1->y() != int1->y());
410 xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
411 xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y());
412 xc1 += (yi1 - yc1) * dxC;
413 xc2 += (yi2 - yc2) * dxC;
414 if (yi1 != yi2) {
415 xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
416 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC,
417 xe2, dxE, intValue, 0, dd);
418 }
419 if (yi2 != ye1) {
420 d = (clip == Clip ? (yi2 << 8) + 0xff - center2->y()
421 : (int2->y() | 0xff) - center2->y())
422 * 2 * extValue / (ext1->y() - int1->y());
423 fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi2, ye1, xc1, dxC,
424 xc2, dxC, d, ddC, dd);
425 }
426 if (ye1 != ye2) {
427 xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y());
428 fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE,
429 xc2, dxC, extValue, 0, dd);
430 }
431 }
432 }
433}
434
435static void drawPolygons(qint32 *bits, int width, int height, const QPoint *vertices,
436 const quint32 *indices, int indexCount, qint32 value)
437{
438 Q_ASSERT(indexCount != 0);
439 typedef QVarLengthArray<quint16, 16> ScanLine;
440 QVarLengthArray<ScanLine, 128> scans(height);
441 int first = 0;
442 for (int i = 1; i < indexCount; ++i) {
443 quint32 idx1 = indices[i - 1];
444 quint32 idx2 = indices[i];
445 Q_ASSERT(idx1 != quint32(-1));
446 if (idx2 == quint32(-1)) {
447 idx2 = indices[first];
448 Q_ASSERT(idx2 != quint32(-1));
449 first = ++i;
450 }
451 const QPoint *v1 = &vertices[idx1];
452 const QPoint *v2 = &vertices[idx2];
453 if (v2->y() < v1->y())
454 qSwap(v1, v2);
455 int fromY = qMax(0, v1->y() >> 8);
456 int toY = qMin(height, v2->y() >> 8);
457 if (fromY >= toY)
458 continue;
459 int dx = ((v2->x() - v1->x()) << 8) / (v2->y() - v1->y());
460 int x = v1->x() + ((fromY << 8) + 0xff - v1->y()) * (v2->x() - v1->x()) / (v2->y() - v1->y());
461 for (int y = fromY; y < toY; ++y) {
462 quint32 c = quint32(x >> 8);
463 if (c < quint32(width))
464 scans[y].append(quint16(c));
465 x += dx;
466 }
467 }
468 for (int i = 0; i < height; ++i) {
469 quint16 *scanline = scans[i].data();
470 int size = scans[i].size();
471 for (int j = 1; j < size; ++j) {
472 int k = j;
473 quint16 value = scanline[k];
474 for (; k != 0 && value < scanline[k - 1]; --k)
475 scanline[k] = scanline[k - 1];
476 scanline[k] = value;
477 }
478 qint32 *line = bits + i * width;
479 int j = 0;
480 for (; j + 1 < size; j += 2) {
481 for (quint16 x = scanline[j]; x < scanline[j + 1]; ++x)
482 line[x] = value;
483 }
484 if (j < size) {
485 for (int x = scanline[j]; x < width; ++x)
486 line[x] = value;
487 }
488 }
489}
490
491static void makeDistanceField(QDistanceFieldData *data, const QPainterPath &path, int dfScale, int offs)
492{
493 if (!data || !data->data)
494 return;
495
496 if (path.isEmpty()) {
497 memset(data->data, 0, data->nbytes);
498 return;
499 }
500
501 int imgWidth = data->width;
502 int imgHeight = data->height;
503
504 QTransform transform;
505 transform.translate(offs, offs);
506 transform.scale(qreal(1) / dfScale, qreal(1) / dfScale);
507
508 QDataBuffer<quint32> pathIndices(0);
509 QDataBuffer<QPoint> pathVertices(0);
510 qSimplifyPath(path, pathVertices, pathIndices, transform);
511
512 const qint32 interiorColor = -0x7f80; // 8:8 signed format, -127.5
513 const qint32 exteriorColor = 0x7f80; // 8:8 signed format, 127.5
514
515 QScopedArrayPointer<qint32> bits(new qint32[imgWidth * imgHeight]);
516 for (int i = 0; i < imgWidth * imgHeight; ++i)
517 bits[i] = exteriorColor;
518
519 const qreal angleStep = qDegreesToRadians(qreal(15));
520 const QPoint rotation(qRound(qCos(angleStep) * 0x4000),
521 qRound(qSin(angleStep) * 0x4000)); // 2:14 signed
522
523 const quint32 *indices = pathIndices.data();
524 QVarLengthArray<QPoint> normals;
525 QVarLengthArray<QPoint> vertices;
526 QVarLengthArray<bool> isConvex;
527 QVarLengthArray<bool> needsClipping;
528
529 drawPolygons(bits.data(), imgWidth, imgHeight, pathVertices.data(),
530 indices, pathIndices.size(), interiorColor);
531
532 int index = 0;
533
534 while (index < pathIndices.size()) {
535 normals.clear();
536 vertices.clear();
537 needsClipping.clear();
538
539 // Find end of polygon.
540 int end = index;
541 while (indices[end] != quint32(-1))
542 ++end;
543
544 // Calculate vertex normals.
545 for (int next = index, prev = end - 1; next < end; prev = next++) {
546 quint32 fromVertexIndex = indices[prev];
547 quint32 toVertexIndex = indices[next];
548
549 const QPoint &from = pathVertices.at(fromVertexIndex);
550 const QPoint &to = pathVertices.at(toVertexIndex);
551
552 QPoint n(to.y() - from.y(), from.x() - to.x());
553 if (n.x() == 0 && n.y() == 0)
554 continue;
555 int scale = qRound((offs << 16) / qSqrt(qreal(n.x()) * n.x() + qreal(n.y()) * n.y())); // 8:16
556 Q_ASSERT(scale != 0);
557
558 n.rx() = n.x() * scale >> 8;
559 n.ry() = n.y() * scale >> 8;
560 normals.append(n);
561 QPoint v(to.x() + 0x7f, to.y() + 0x7f);
562 vertices.append(v);
563 needsClipping.append((to.x() < offs << 8) || (to.x() >= (imgWidth - offs) << 8)
564 || (to.y() < offs << 8) || (to.y() >= (imgHeight - offs) << 8));
565 }
566
567 isConvex.resize(normals.count());
568 for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) {
569 isConvex[prev] = normals.at(prev).x() * normals.at(next).y()
570 - normals.at(prev).y() * normals.at(next).x() < 0;
571 }
572
573 // Draw quads.
574 for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) {
575 QPoint n = normals.at(next);
576 QPoint intPrev = vertices.at(prev);
577 QPoint extPrev = vertices.at(prev);
578 QPoint intNext = vertices.at(next);
579 QPoint extNext = vertices.at(next);
580
581 extPrev.rx() -= n.x();
582 extPrev.ry() -= n.y();
583 intPrev.rx() += n.x();
584 intPrev.ry() += n.y();
585 extNext.rx() -= n.x();
586 extNext.ry() -= n.y();
587 intNext.rx() += n.x();
588 intNext.ry() += n.y();
589
590 if (needsClipping[prev] || needsClipping[next]) {
591 drawRectangle<Clip>(bits.data(), imgWidth, imgHeight,
592 &intPrev, &vertices.at(prev), &extPrev,
593 &intNext, &vertices.at(next), &extNext,
594 exteriorColor);
595 } else {
596 drawRectangle<NoClip>(bits.data(), imgWidth, imgHeight,
597 &intPrev, &vertices.at(prev), &extPrev,
598 &intNext, &vertices.at(next), &extNext,
599 exteriorColor);
600 }
601
602 if (isConvex.at(prev)) {
603 QPoint p = extPrev;
604 if (needsClipping[prev]) {
605 for (;;) {
606 QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
607 (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
608 n = rn;
609 if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) {
610 p.rx() = vertices.at(prev).x() - normals.at(prev).x();
611 p.ry() = vertices.at(prev).y() - normals.at(prev).y();
612 drawTriangle<Clip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
613 &extPrev, &p, exteriorColor);
614 break;
615 }
616
617 p.rx() = vertices.at(prev).x() - n.x();
618 p.ry() = vertices.at(prev).y() - n.y();
619 drawTriangle<Clip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
620 &extPrev, &p, exteriorColor);
621 extPrev = p;
622 }
623 } else {
624 for (;;) {
625 QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
626 (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
627 n = rn;
628 if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) {
629 p.rx() = vertices.at(prev).x() - normals.at(prev).x();
630 p.ry() = vertices.at(prev).y() - normals.at(prev).y();
631 drawTriangle<NoClip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
632 &extPrev, &p, exteriorColor);
633 break;
634 }
635
636 p.rx() = vertices.at(prev).x() - n.x();
637 p.ry() = vertices.at(prev).y() - n.y();
638 drawTriangle<NoClip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
639 &extPrev, &p, exteriorColor);
640 extPrev = p;
641 }
642 }
643 } else {
644 QPoint p = intPrev;
645 if (needsClipping[prev]) {
646 for (;;) {
647 QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
648 (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
649 n = rn;
650 if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) {
651 p.rx() = vertices.at(prev).x() + normals.at(prev).x();
652 p.ry() = vertices.at(prev).y() + normals.at(prev).y();
653 drawTriangle<Clip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
654 &p, &intPrev, interiorColor);
655 break;
656 }
657
658 p.rx() = vertices.at(prev).x() + n.x();
659 p.ry() = vertices.at(prev).y() + n.y();
660 drawTriangle<Clip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
661 &p, &intPrev, interiorColor);
662 intPrev = p;
663 }
664 } else {
665 for (;;) {
666 QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
667 (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
668 n = rn;
669 if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) {
670 p.rx() = vertices.at(prev).x() + normals.at(prev).x();
671 p.ry() = vertices.at(prev).y() + normals.at(prev).y();
672 drawTriangle<NoClip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
673 &p, &intPrev, interiorColor);
674 break;
675 }
676
677 p.rx() = vertices.at(prev).x() + n.x();
678 p.ry() = vertices.at(prev).y() + n.y();
679 drawTriangle<NoClip>(bits.data(), imgWidth, imgHeight, &vertices.at(prev),
680 &p, &intPrev, interiorColor);
681 intPrev = p;
682 }
683 }
684 }
685 }
686
687 index = end + 1;
688 }
689
690 const qint32 *inLine = bits.data();
691 uchar *outLine = data->data;
692 for (int y = 0; y < imgHeight; ++y) {
693 for (int x = 0; x < imgWidth; ++x, ++inLine, ++outLine)
694 *outLine = uchar((0x7f80 - *inLine) >> 8);
695 }
696}
697
698static bool imageHasNarrowOutlines(const QImage &im)
699{
700 if (im.isNull() || im.width() < 1 || im.height() < 1)
701 return false;
702 else if (im.width() == 1 || im.height() == 1)
703 return true;
704
705 int minHThick = 999;
706 int minVThick = 999;
707
708 int thick = 0;
709 bool in = false;
710 int y = (im.height() + 1) / 2;
711 for (int x = 0; x < im.width(); ++x) {
712 int a = qAlpha(im.pixel(x, y));
713 if (a > 127) {
714 in = true;
715 ++thick;
716 } else if (in) {
717 in = false;
718 minHThick = qMin(minHThick, thick);
719 thick = 0;
720 }
721 }
722
723 thick = 0;
724 in = false;
725 int x = (im.width() + 1) / 2;
726 for (int y = 0; y < im.height(); ++y) {
727 int a = qAlpha(im.pixel(x, y));
728 if (a > 127) {
729 in = true;
730 ++thick;
731 } else if (in) {
732 in = false;
733 minVThick = qMin(minVThick, thick);
734 thick = 0;
735 }
736 }
737
738 return minHThick == 1 || minVThick == 1;
739}
740
741static int QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE = 54;
742static int QT_DISTANCEFIELD_DEFAULT_SCALE = 16;
743static int QT_DISTANCEFIELD_DEFAULT_RADIUS = 80;
744static int QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT = 2000;
745
746static void initialDistanceFieldFactor()
747{
748 static bool initialized = false;
749 if (initialized)
750 return;
751 initialized = true;
752
753 if (qEnvironmentVariableIsSet("QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE")) {
754 QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE = qEnvironmentVariableIntValue("QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE");
755 qCDebug(lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE:" << QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE;
756 }
757
758 if (qEnvironmentVariableIsSet("QT_DISTANCEFIELD_DEFAULT_SCALE")) {
759 QT_DISTANCEFIELD_DEFAULT_SCALE = qEnvironmentVariableIntValue("QT_DISTANCEFIELD_DEFAULT_SCALE");
760 qCDebug(lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_SCALE:" << QT_DISTANCEFIELD_DEFAULT_SCALE;
761 }
762 if (qEnvironmentVariableIsSet("QT_DISTANCEFIELD_DEFAULT_RADIUS")) {
763 QT_DISTANCEFIELD_DEFAULT_RADIUS = qEnvironmentVariableIntValue("QT_DISTANCEFIELD_DEFAULT_RADIUS");
764 qDebug(lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_RADIUS:" << QT_DISTANCEFIELD_DEFAULT_RADIUS;
765 }
766 if (qEnvironmentVariableIsSet("QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT")) {
767 QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT = qEnvironmentVariableIntValue("QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT");
768 qCDebug(lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT:" << QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT;
769 }
770}
771
772bool qt_fontHasNarrowOutlines(QFontEngine *fontEngine)
773{
774 initialDistanceFieldFactor();
775 QFontEngine *fe = fontEngine->cloneWithSize(QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE);
776 if (!fe)
777 return false;
778
779 QImage im;
780
781 const glyph_t glyph = fe->glyphIndex('O');
782 if (glyph != 0)
783 im = fe->alphaMapForGlyph(glyph, QFixed(), QTransform());
784
785 Q_ASSERT(fe->ref.loadRelaxed() == 0);
786 delete fe;
787
788 return imageHasNarrowOutlines(im);
789}
790
791bool qt_fontHasNarrowOutlines(const QRawFont &f)
792{
793 QRawFont font = f;
794 initialDistanceFieldFactor();
795 font.setPixelSize(QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE);
796 if (!font.isValid())
797 return false;
798
799 QList<quint32> glyphIndices = font.glyphIndexesForString(QLatin1String("O"));
800 if (glyphIndices.isEmpty() || glyphIndices[0] == 0)
801 return false;
802
803 return imageHasNarrowOutlines(font.alphaMapForGlyph(glyphIndices.at(0),
804 QRawFont::PixelAntialiasing));
805}
806
807int QT_DISTANCEFIELD_BASEFONTSIZE(bool narrowOutlineFont)
808{
809 initialDistanceFieldFactor();
810
811 if (Q_UNLIKELY(narrowOutlineFont))
812 return QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE * 2;
813 else
814 return QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE;
815}
816
817int QT_DISTANCEFIELD_SCALE(bool narrowOutlineFont)
818{
819 initialDistanceFieldFactor();
820
821 if (Q_UNLIKELY(narrowOutlineFont))
822 return QT_DISTANCEFIELD_DEFAULT_SCALE / 2;
823 else
824 return QT_DISTANCEFIELD_DEFAULT_SCALE;
825}
826
827int QT_DISTANCEFIELD_RADIUS(bool narrowOutlineFont)
828{
829 initialDistanceFieldFactor();
830
831 if (Q_UNLIKELY(narrowOutlineFont))
832 return QT_DISTANCEFIELD_DEFAULT_RADIUS / 2;
833 else
834 return QT_DISTANCEFIELD_DEFAULT_RADIUS;
835}
836
837int QT_DISTANCEFIELD_HIGHGLYPHCOUNT()
838{
839 initialDistanceFieldFactor();
840 return QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT;
841}
842
843QDistanceFieldData::QDistanceFieldData(const QDistanceFieldData &other)
844 : QSharedData(other)
845 , glyph(other.glyph)
846 , width(other.width)
847 , height(other.height)
848 , nbytes(other.nbytes)
849{
850 if (nbytes && other.data)
851 data = (uchar *)memcpy(malloc(nbytes), other.data, nbytes);
852 else
853 data = nullptr;
854}
855
856QDistanceFieldData::~QDistanceFieldData()
857{
858 free(data);
859}
860
861QDistanceFieldData *QDistanceFieldData::create(const QSize &size)
862{
863 QDistanceFieldData *data = new QDistanceFieldData;
864
865 if (size.isValid()) {
866 data->width = size.width();
867 data->height = size.height();
868 // pixel data stored as a 1-byte alpha value
869 data->nbytes = data->width * data->height; // tightly packed
870 data->data = (uchar *)malloc(data->nbytes);
871 }
872
873 return data;
874}
875
876QDistanceFieldData *QDistanceFieldData::create(const QPainterPath &path, bool doubleResolution)
877{
878 int dfMargin = QT_DISTANCEFIELD_RADIUS(doubleResolution) / QT_DISTANCEFIELD_SCALE(doubleResolution);
879 int glyphWidth = qCeil(path.boundingRect().width() / QT_DISTANCEFIELD_SCALE(doubleResolution)) + dfMargin * 2;
880 int glyphHeight = qCeil(path.boundingRect().height() / QT_DISTANCEFIELD_SCALE(doubleResolution)) + dfMargin * 2;
881
882 QDistanceFieldData *data = create(QSize(glyphWidth, glyphHeight));
883
884 makeDistanceField(data,
885 path,
886 QT_DISTANCEFIELD_SCALE(doubleResolution),
887 QT_DISTANCEFIELD_RADIUS(doubleResolution) / QT_DISTANCEFIELD_SCALE(doubleResolution));
888 return data;
889}
890
891
892QDistanceField::QDistanceField()
893 : d(new QDistanceFieldData)
894{
895}
896
897QDistanceField::QDistanceField(int width, int height)
898 : d(QDistanceFieldData::create(QSize(width, height)))
899{
900}
901
902QDistanceField::QDistanceField(const QRawFont &font, glyph_t glyph, bool doubleResolution)
903{
904 setGlyph(font, glyph, doubleResolution);
905}
906
907QDistanceField::QDistanceField(QFontEngine *fontEngine, glyph_t glyph, bool doubleResolution)
908{
909 setGlyph(fontEngine, glyph, doubleResolution);
910}
911
912QDistanceField::QDistanceField(const QPainterPath &path, glyph_t glyph, bool doubleResolution)
913{
914 QPainterPath dfPath = path;
915 dfPath.translate(-dfPath.boundingRect().topLeft());
916 dfPath.setFillRule(Qt::WindingFill);
917
918 d = QDistanceFieldData::create(dfPath, doubleResolution);
919 d->glyph = glyph;
920}
921
922
923QDistanceField::QDistanceField(QDistanceFieldData *data)
924 : d(data)
925{
926}
927
928bool QDistanceField::isNull() const
929{
930 return !d->data;
931}
932
933glyph_t QDistanceField::glyph() const
934{
935 return d->glyph;
936}
937
938void QDistanceField::setGlyph(const QRawFont &font, glyph_t glyph, bool doubleResolution)
939{
940 QRawFont renderFont = font;
941 renderFont.setPixelSize(QT_DISTANCEFIELD_BASEFONTSIZE(doubleResolution) * QT_DISTANCEFIELD_SCALE(doubleResolution));
942
943 QPainterPath path = renderFont.pathForGlyph(glyph);
944 path.translate(-path.boundingRect().topLeft());
945 path.setFillRule(Qt::WindingFill);
946
947 d = QDistanceFieldData::create(path, doubleResolution);
948 d->glyph = glyph;
949}
950
951void QDistanceField::setGlyph(QFontEngine *fontEngine, glyph_t glyph, bool doubleResolution)
952{
953 QFixedPoint position;
954 QPainterPath path;
955 fontEngine->addGlyphsToPath(&glyph, &position, 1, &path, { });
956 path.translate(-path.boundingRect().topLeft());
957 path.setFillRule(Qt::WindingFill);
958
959 d = QDistanceFieldData::create(path, doubleResolution);
960 d->glyph = glyph;
961}
962
963int QDistanceField::width() const
964{
965 return d->width;
966}
967
968int QDistanceField::height() const
969{
970 return d->height;
971}
972
973QDistanceField QDistanceField::copy(const QRect &r) const
974{
975 if (isNull())
976 return QDistanceField();
977
978 if (r.isNull())
979 return QDistanceField(new QDistanceFieldData(*d));
980
981 int x = r.x();
982 int y = r.y();
983 int w = r.width();
984 int h = r.height();
985
986 int dx = 0;
987 int dy = 0;
988 if (w <= 0 || h <= 0)
989 return QDistanceField();
990
991 QDistanceField df(w, h);
992 if (df.isNull())
993 return df;
994
995 if (x < 0 || y < 0 || x + w > d->width || y + h > d->height) {
996 memset(df.d->data, 0, df.d->nbytes);
997 if (x < 0) {
998 dx = -x;
999 x = 0;
1000 }
1001 if (y < 0) {
1002 dy = -y;
1003 y = 0;
1004 }
1005 }
1006
1007 int pixels_to_copy = qMax(w - dx, 0);
1008 if (x > d->width)
1009 pixels_to_copy = 0;
1010 else if (pixels_to_copy > d->width - x)
1011 pixels_to_copy = d->width - x;
1012 int lines_to_copy = qMax(h - dy, 0);
1013 if (y > d->height)
1014 lines_to_copy = 0;
1015 else if (lines_to_copy > d->height - y)
1016 lines_to_copy = d->height - y;
1017
1018 const uchar *src = d->data + x + y * d->width;
1019 uchar *dest = df.d->data + dx + dy * df.d->width;
1020 for (int i = 0; i < lines_to_copy; ++i) {
1021 memcpy(dest, src, pixels_to_copy);
1022 src += d->width;
1023 dest += df.d->width;
1024 }
1025
1026 df.d->glyph = d->glyph;
1027
1028 return df;
1029}
1030
1031uchar *QDistanceField::bits()
1032{
1033 return d->data;
1034}
1035
1036const uchar *QDistanceField::bits() const
1037{
1038 return d->data;
1039}
1040
1041const uchar *QDistanceField::constBits() const
1042{
1043 return d->data;
1044}
1045
1046uchar *QDistanceField::scanLine(int i)
1047{
1048 if (isNull())
1049 return nullptr;
1050
1051 Q_ASSERT(i >= 0 && i < d->height);
1052 return d->data + i * d->width;
1053}
1054
1055const uchar *QDistanceField::scanLine(int i) const
1056{
1057 if (isNull())
1058 return nullptr;
1059
1060 Q_ASSERT(i >= 0 && i < d->height);
1061 return d->data + i * d->width;
1062}
1063
1064const uchar *QDistanceField::constScanLine(int i) const
1065{
1066 if (isNull())
1067 return nullptr;
1068
1069 Q_ASSERT(i >= 0 && i < d->height);
1070 return d->data + i * d->width;
1071}
1072
1073QImage QDistanceField::toImage(QImage::Format format) const
1074{
1075 if (isNull())
1076 return QImage();
1077
1078 QImage image(d->width, d->height, qt_depthForFormat(format) == 8 ?
1079 format : QImage::Format_ARGB32_Premultiplied);
1080 if (image.isNull())
1081 return image;
1082
1083 if (image.depth() == 8) {
1084 for (int y = 0; y < d->height; ++y)
1085 memcpy(image.scanLine(y), scanLine(y), d->width);
1086 } else {
1087 for (int y = 0; y < d->height; ++y) {
1088 for (int x = 0; x < d->width; ++x) {
1089 uint alpha = *(d->data + x + y * d->width);
1090 image.setPixel(x, y, alpha << 24);
1091 }
1092 }
1093
1094 if (image.format() != format)
1095 image = image.convertToFormat(format);
1096 }
1097
1098 return image;
1099}
1100
1101QT_END_NAMESPACE
1102
1103