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

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