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

source code of qtbase/src/gui/text/qdistancefield.cpp