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
478 const qint32 interiorColor = -0x7f80; // 8:8 signed format, -127.5
479 const qint32 exteriorColor = 0x7f80; // 8:8 signed format, 127.5
480
481 QScopedArrayPointer<qint32> bits(new qint32[imgWidth * imgHeight]);
482 for (int i = 0; i < imgWidth * imgHeight; ++i)
483 bits[i] = exteriorColor;
484
485 const qreal angleStep = qDegreesToRadians(degrees: qreal(15));
486 const QPoint rotation(qRound(d: qCos(v: angleStep) * 0x4000),
487 qRound(d: qSin(v: angleStep) * 0x4000)); // 2:14 signed
488
489 const quint32 *indices = pathIndices.data();
490 QVarLengthArray<QPoint> normals;
491 QVarLengthArray<QPoint> vertices;
492 QVarLengthArray<bool> isConvex;
493 QVarLengthArray<bool> needsClipping;
494
495 drawPolygons(bits: bits.data(), width: imgWidth, height: imgHeight, vertices: pathVertices.data(),
496 indices, indexCount: pathIndices.size(), value: interiorColor);
497
498 int index = 0;
499
500 while (index < pathIndices.size()) {
501 normals.clear();
502 vertices.clear();
503 needsClipping.clear();
504
505 // Find end of polygon.
506 int end = index;
507 while (indices[end] != quint32(-1))
508 ++end;
509
510 // Calculate vertex normals.
511 for (int next = index, prev = end - 1; next < end; prev = next++) {
512 quint32 fromVertexIndex = indices[prev];
513 quint32 toVertexIndex = indices[next];
514
515 const QPoint &from = pathVertices.at(i: fromVertexIndex);
516 const QPoint &to = pathVertices.at(i: toVertexIndex);
517
518 QPoint n(to.y() - from.y(), from.x() - to.x());
519 if (n.x() == 0 && n.y() == 0)
520 continue;
521 int scale = qRound(d: (offs << 16) / qSqrt(v: qreal(n.x()) * n.x() + qreal(n.y()) * n.y())); // 8:16
522 Q_ASSERT(scale != 0);
523
524 n.rx() = n.x() * scale >> 8;
525 n.ry() = n.y() * scale >> 8;
526 normals.append(t: n);
527 QPoint v(to.x() + 0x7f, to.y() + 0x7f);
528 vertices.append(t: v);
529 needsClipping.append(t: (to.x() < offs << 8) || (to.x() >= (imgWidth - offs) << 8)
530 || (to.y() < offs << 8) || (to.y() >= (imgHeight - offs) << 8));
531 }
532
533 isConvex.resize(sz: normals.size());
534 for (int next = 0, prev = normals.size() - 1; next < normals.size(); prev = next++) {
535 isConvex[prev] = normals.at(idx: prev).x() * normals.at(idx: next).y()
536 - normals.at(idx: prev).y() * normals.at(idx: next).x() < 0;
537 }
538
539 // Draw quads.
540 for (int next = 0, prev = normals.size() - 1; next < normals.size(); prev = next++) {
541 QPoint n = normals.at(idx: next);
542 QPoint intPrev = vertices.at(idx: prev);
543 QPoint extPrev = vertices.at(idx: prev);
544 QPoint intNext = vertices.at(idx: next);
545 QPoint extNext = vertices.at(idx: next);
546
547 extPrev.rx() -= n.x();
548 extPrev.ry() -= n.y();
549 intPrev.rx() += n.x();
550 intPrev.ry() += n.y();
551 extNext.rx() -= n.x();
552 extNext.ry() -= n.y();
553 intNext.rx() += n.x();
554 intNext.ry() += n.y();
555
556 if (needsClipping[prev] || needsClipping[next]) {
557 drawRectangle<Clip>(bits: bits.data(), width: imgWidth, height: imgHeight,
558 int1: &intPrev, center1: &vertices.at(idx: prev), ext1: &extPrev,
559 int2: &intNext, center2: &vertices.at(idx: next), ext2: &extNext,
560 extValue: exteriorColor);
561 } else {
562 drawRectangle<NoClip>(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 }
567
568 if (isConvex.at(idx: prev)) {
569 QPoint p = extPrev;
570 if (needsClipping[prev]) {
571 for (;;) {
572 QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
573 (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
574 n = rn;
575 if (n.x() * normals.at(idx: prev).y() - n.y() * normals.at(idx: prev).x() <= 0) {
576 p.rx() = vertices.at(idx: prev).x() - normals.at(idx: prev).x();
577 p.ry() = vertices.at(idx: prev).y() - normals.at(idx: prev).y();
578 drawTriangle<Clip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
579 v1: &extPrev, v2: &p, value: exteriorColor);
580 break;
581 }
582
583 p.rx() = vertices.at(idx: prev).x() - n.x();
584 p.ry() = vertices.at(idx: prev).y() - n.y();
585 drawTriangle<Clip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
586 v1: &extPrev, v2: &p, value: exteriorColor);
587 extPrev = p;
588 }
589 } else {
590 for (;;) {
591 QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14,
592 (n.y() * rotation.x() + n.x() * rotation.y()) >> 14);
593 n = rn;
594 if (n.x() * normals.at(idx: prev).y() - n.y() * normals.at(idx: prev).x() <= 0) {
595 p.rx() = vertices.at(idx: prev).x() - normals.at(idx: prev).x();
596 p.ry() = vertices.at(idx: prev).y() - normals.at(idx: prev).y();
597 drawTriangle<NoClip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
598 v1: &extPrev, v2: &p, value: exteriorColor);
599 break;
600 }
601
602 p.rx() = vertices.at(idx: prev).x() - n.x();
603 p.ry() = vertices.at(idx: prev).y() - n.y();
604 drawTriangle<NoClip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
605 v1: &extPrev, v2: &p, value: exteriorColor);
606 extPrev = p;
607 }
608 }
609 } else {
610 QPoint p = intPrev;
611 if (needsClipping[prev]) {
612 for (;;) {
613 QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
614 (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
615 n = rn;
616 if (n.x() * normals.at(idx: prev).y() - n.y() * normals.at(idx: prev).x() >= 0) {
617 p.rx() = vertices.at(idx: prev).x() + normals.at(idx: prev).x();
618 p.ry() = vertices.at(idx: prev).y() + normals.at(idx: prev).y();
619 drawTriangle<Clip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
620 v1: &p, v2: &intPrev, value: interiorColor);
621 break;
622 }
623
624 p.rx() = vertices.at(idx: prev).x() + n.x();
625 p.ry() = vertices.at(idx: prev).y() + n.y();
626 drawTriangle<Clip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
627 v1: &p, v2: &intPrev, value: interiorColor);
628 intPrev = p;
629 }
630 } else {
631 for (;;) {
632 QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14,
633 (n.y() * rotation.x() - n.x() * rotation.y()) >> 14);
634 n = rn;
635 if (n.x() * normals.at(idx: prev).y() - n.y() * normals.at(idx: prev).x() >= 0) {
636 p.rx() = vertices.at(idx: prev).x() + normals.at(idx: prev).x();
637 p.ry() = vertices.at(idx: prev).y() + normals.at(idx: prev).y();
638 drawTriangle<NoClip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
639 v1: &p, v2: &intPrev, value: interiorColor);
640 break;
641 }
642
643 p.rx() = vertices.at(idx: prev).x() + n.x();
644 p.ry() = vertices.at(idx: prev).y() + n.y();
645 drawTriangle<NoClip>(bits: bits.data(), width: imgWidth, height: imgHeight, center: &vertices.at(idx: prev),
646 v1: &p, v2: &intPrev, value: interiorColor);
647 intPrev = p;
648 }
649 }
650 }
651 }
652
653 index = end + 1;
654 }
655
656 const qint32 *inLine = bits.data();
657 uchar *outLine = data->data;
658 for (int y = 0; y < imgHeight; ++y) {
659 for (int x = 0; x < imgWidth; ++x, ++inLine, ++outLine)
660 *outLine = uchar((0x7f80 - *inLine) >> 8);
661 }
662}
663
664static bool imageHasNarrowOutlines(const QImage &im)
665{
666 if (im.isNull() || im.width() < 1 || im.height() < 1)
667 return false;
668 else if (im.width() == 1 || im.height() == 1)
669 return true;
670
671 int minHThick = 999;
672 int minVThick = 999;
673
674 int thick = 0;
675 bool in = false;
676 int y = (im.height() + 1) / 2;
677 for (int x = 0; x < im.width(); ++x) {
678 int a = qAlpha(rgb: im.pixel(x, y));
679 if (a > 127) {
680 in = true;
681 ++thick;
682 } else if (in) {
683 in = false;
684 minHThick = qMin(a: minHThick, b: thick);
685 thick = 0;
686 }
687 }
688
689 thick = 0;
690 in = false;
691 int x = (im.width() + 1) / 2;
692 for (int y = 0; y < im.height(); ++y) {
693 int a = qAlpha(rgb: im.pixel(x, y));
694 if (a > 127) {
695 in = true;
696 ++thick;
697 } else if (in) {
698 in = false;
699 minVThick = qMin(a: minVThick, b: thick);
700 thick = 0;
701 }
702 }
703
704 return minHThick == 1 || minVThick == 1;
705}
706
707static int QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE = 54;
708static int QT_DISTANCEFIELD_DEFAULT_SCALE = 16;
709static int QT_DISTANCEFIELD_DEFAULT_RADIUS = 80;
710static int QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT = 2000;
711
712static void initialDistanceFieldFactor()
713{
714 static bool initialized = false;
715 if (initialized)
716 return;
717 initialized = true;
718
719 if (qEnvironmentVariableIsSet(varName: "QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE")) {
720 QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE = qEnvironmentVariableIntValue(varName: "QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE");
721 qCDebug(lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE:" << QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE;
722 }
723
724 if (qEnvironmentVariableIsSet(varName: "QT_DISTANCEFIELD_DEFAULT_SCALE")) {
725 QT_DISTANCEFIELD_DEFAULT_SCALE = qEnvironmentVariableIntValue(varName: "QT_DISTANCEFIELD_DEFAULT_SCALE");
726 qCDebug(lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_SCALE:" << QT_DISTANCEFIELD_DEFAULT_SCALE;
727 }
728 if (qEnvironmentVariableIsSet(varName: "QT_DISTANCEFIELD_DEFAULT_RADIUS")) {
729 QT_DISTANCEFIELD_DEFAULT_RADIUS = qEnvironmentVariableIntValue(varName: "QT_DISTANCEFIELD_DEFAULT_RADIUS");
730 qDebug(catFunc: lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_RADIUS:" << QT_DISTANCEFIELD_DEFAULT_RADIUS;
731 }
732 if (qEnvironmentVariableIsSet(varName: "QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT")) {
733 QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT = qEnvironmentVariableIntValue(varName: "QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT");
734 qCDebug(lcDistanceField) << "set the QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT:" << QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT;
735 }
736}
737
738bool qt_fontHasNarrowOutlines(QFontEngine *fontEngine)
739{
740 initialDistanceFieldFactor();
741 QFontEngine *fe = fontEngine->cloneWithSize(QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE);
742 if (!fe)
743 return false;
744
745 QImage im;
746
747 const glyph_t glyph = fe->glyphIndex(ucs4: 'O');
748 if (glyph != 0)
749 im = fe->alphaMapForGlyph(glyph, subPixelPosition: QFixedPoint(), t: QTransform());
750
751 Q_ASSERT(fe->ref.loadRelaxed() == 0);
752 delete fe;
753
754 return imageHasNarrowOutlines(im);
755}
756
757bool qt_fontHasNarrowOutlines(const QRawFont &f)
758{
759 QRawFont font = f;
760 initialDistanceFieldFactor();
761 font.setPixelSize(QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE);
762 if (!font.isValid())
763 return false;
764
765 QList<quint32> glyphIndices = font.glyphIndexesForString(text: "O"_L1);
766 if (glyphIndices.isEmpty() || glyphIndices[0] == 0)
767 return false;
768
769 return imageHasNarrowOutlines(im: font.alphaMapForGlyph(glyphIndex: glyphIndices.at(i: 0),
770 antialiasingType: QRawFont::PixelAntialiasing));
771}
772
773int QT_DISTANCEFIELD_BASEFONTSIZE(bool narrowOutlineFont)
774{
775 initialDistanceFieldFactor();
776
777 if (Q_UNLIKELY(narrowOutlineFont))
778 return QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE * 2;
779 else
780 return QT_DISTANCEFIELD_DEFAULT_BASEFONTSIZE;
781}
782
783int QT_DISTANCEFIELD_SCALE(bool narrowOutlineFont)
784{
785 initialDistanceFieldFactor();
786
787 if (Q_UNLIKELY(narrowOutlineFont))
788 return QT_DISTANCEFIELD_DEFAULT_SCALE / 2;
789 else
790 return QT_DISTANCEFIELD_DEFAULT_SCALE;
791}
792
793int QT_DISTANCEFIELD_RADIUS(bool narrowOutlineFont)
794{
795 initialDistanceFieldFactor();
796
797 if (Q_UNLIKELY(narrowOutlineFont))
798 return QT_DISTANCEFIELD_DEFAULT_RADIUS / 2;
799 else
800 return QT_DISTANCEFIELD_DEFAULT_RADIUS;
801}
802
803int QT_DISTANCEFIELD_HIGHGLYPHCOUNT()
804{
805 initialDistanceFieldFactor();
806 return QT_DISTANCEFIELD_DEFAULT_HIGHGLYPHCOUNT;
807}
808
809QDistanceFieldData::QDistanceFieldData(const QDistanceFieldData &other)
810 : QSharedData(other)
811 , glyph(other.glyph)
812 , width(other.width)
813 , height(other.height)
814 , nbytes(other.nbytes)
815{
816 if (nbytes && other.data)
817 data = (uchar *)memcpy(dest: malloc(size: nbytes), src: other.data, n: nbytes);
818 else
819 data = nullptr;
820}
821
822QDistanceFieldData::~QDistanceFieldData()
823{
824 free(ptr: data);
825}
826
827QDistanceFieldData *QDistanceFieldData::create(const QSize &size)
828{
829 QDistanceFieldData *data = new QDistanceFieldData;
830
831 if (size.isValid()) {
832 data->width = size.width();
833 data->height = size.height();
834 // pixel data stored as a 1-byte alpha value
835 data->nbytes = data->width * data->height; // tightly packed
836 data->data = (uchar *)malloc(size: data->nbytes);
837 }
838
839 return data;
840}
841
842QDistanceFieldData *QDistanceFieldData::create(const QPainterPath &path, bool doubleResolution)
843{
844 int dfMargin = QT_DISTANCEFIELD_RADIUS(narrowOutlineFont: doubleResolution) / QT_DISTANCEFIELD_SCALE(narrowOutlineFont: doubleResolution);
845 int glyphWidth = qCeil(v: path.boundingRect().width() / QT_DISTANCEFIELD_SCALE(narrowOutlineFont: doubleResolution)) + dfMargin * 2;
846 int glyphHeight = qCeil(v: path.boundingRect().height() / QT_DISTANCEFIELD_SCALE(narrowOutlineFont: doubleResolution)) + dfMargin * 2;
847
848 QDistanceFieldData *data = create(size: QSize(glyphWidth, glyphHeight));
849
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
858QDistanceField::QDistanceField()
859 : d(new QDistanceFieldData)
860{
861}
862
863QDistanceField::QDistanceField(int width, int height)
864 : d(QDistanceFieldData::create(size: QSize(width, height)))
865{
866}
867
868QDistanceField::QDistanceField(const QRawFont &font, glyph_t glyph, bool doubleResolution)
869{
870 setGlyph(font, glyph, doubleResolution);
871}
872
873QDistanceField::QDistanceField(QFontEngine *fontEngine, glyph_t glyph, bool doubleResolution)
874{
875 setGlyph(fontEngine, glyph, doubleResolution);
876}
877
878QDistanceField::QDistanceField(const QPainterPath &path, glyph_t glyph, bool doubleResolution)
879{
880 QPainterPath dfPath = path;
881 dfPath.translate(offset: -dfPath.boundingRect().topLeft());
882 dfPath.setFillRule(Qt::WindingFill);
883
884 d = QDistanceFieldData::create(path: dfPath, doubleResolution);
885 d->glyph = glyph;
886}
887
888
889QDistanceField::QDistanceField(QDistanceFieldData *data)
890 : d(data)
891{
892}
893
894bool QDistanceField::isNull() const
895{
896 return !d->data;
897}
898
899glyph_t QDistanceField::glyph() const
900{
901 return d->glyph;
902}
903
904void QDistanceField::setGlyph(const QRawFont &font, glyph_t glyph, bool doubleResolution)
905{
906 QRawFont renderFont = font;
907 renderFont.setPixelSize(QT_DISTANCEFIELD_BASEFONTSIZE(narrowOutlineFont: doubleResolution) * QT_DISTANCEFIELD_SCALE(narrowOutlineFont: doubleResolution));
908
909 QPainterPath path = renderFont.pathForGlyph(glyphIndex: glyph);
910 path.translate(offset: -path.boundingRect().topLeft());
911 path.setFillRule(Qt::WindingFill);
912
913 d = QDistanceFieldData::create(path, doubleResolution);
914 d->glyph = glyph;
915}
916
917void QDistanceField::setGlyph(QFontEngine *fontEngine, glyph_t glyph, bool doubleResolution)
918{
919 QFixedPoint position;
920 QPainterPath path;
921 fontEngine->addGlyphsToPath(glyphs: &glyph, positions: &position, nglyphs: 1, path: &path, flags: { });
922 path.translate(offset: -path.boundingRect().topLeft());
923 path.setFillRule(Qt::WindingFill);
924
925 d = QDistanceFieldData::create(path, doubleResolution);
926 d->glyph = glyph;
927}
928
929int QDistanceField::width() const
930{
931 return d->width;
932}
933
934int QDistanceField::height() const
935{
936 return d->height;
937}
938
939QDistanceField QDistanceField::copy(const QRect &r) const
940{
941 if (isNull())
942 return QDistanceField();
943
944 if (r.isNull())
945 return QDistanceField(new QDistanceFieldData(*d));
946
947 int x = r.x();
948 int y = r.y();
949 int w = r.width();
950 int h = r.height();
951
952 int dx = 0;
953 int dy = 0;
954 if (w <= 0 || h <= 0)
955 return QDistanceField();
956
957 QDistanceField df(w, h);
958 if (df.isNull())
959 return df;
960
961 if (x < 0 || y < 0 || x + w > d->width || y + h > d->height) {
962 memset(s: df.d->data, c: 0, n: df.d->nbytes);
963 if (x < 0) {
964 dx = -x;
965 x = 0;
966 }
967 if (y < 0) {
968 dy = -y;
969 y = 0;
970 }
971 }
972
973 int pixels_to_copy = qMax(a: w - dx, b: 0);
974 if (x > d->width)
975 pixels_to_copy = 0;
976 else if (pixels_to_copy > d->width - x)
977 pixels_to_copy = d->width - x;
978 int lines_to_copy = qMax(a: h - dy, b: 0);
979 if (y > d->height)
980 lines_to_copy = 0;
981 else if (lines_to_copy > d->height - y)
982 lines_to_copy = d->height - y;
983
984 const uchar *src = d->data + x + y * d->width;
985 uchar *dest = df.d->data + dx + dy * df.d->width;
986 for (int i = 0; i < lines_to_copy; ++i) {
987 memcpy(dest: dest, src: src, n: pixels_to_copy);
988 src += d->width;
989 dest += df.d->width;
990 }
991
992 df.d->glyph = d->glyph;
993
994 return df;
995}
996
997uchar *QDistanceField::bits()
998{
999 return d->data;
1000}
1001
1002const uchar *QDistanceField::bits() const
1003{
1004 return d->data;
1005}
1006
1007const uchar *QDistanceField::constBits() const
1008{
1009 return d->data;
1010}
1011
1012uchar *QDistanceField::scanLine(int i)
1013{
1014 if (isNull())
1015 return nullptr;
1016
1017 Q_ASSERT(i >= 0 && i < d->height);
1018 return d->data + i * d->width;
1019}
1020
1021const uchar *QDistanceField::scanLine(int i) const
1022{
1023 if (isNull())
1024 return nullptr;
1025
1026 Q_ASSERT(i >= 0 && i < d->height);
1027 return d->data + i * d->width;
1028}
1029
1030const uchar *QDistanceField::constScanLine(int i) const
1031{
1032 if (isNull())
1033 return nullptr;
1034
1035 Q_ASSERT(i >= 0 && i < d->height);
1036 return d->data + i * d->width;
1037}
1038
1039QImage QDistanceField::toImage(QImage::Format format) const
1040{
1041 if (isNull())
1042 return QImage();
1043
1044 QImage image(d->width, d->height, qt_depthForFormat(format) == 8 ?
1045 format : QImage::Format_ARGB32_Premultiplied);
1046 if (image.isNull())
1047 return image;
1048
1049 if (image.depth() == 8) {
1050 for (int y = 0; y < d->height; ++y)
1051 memcpy(dest: image.scanLine(y), src: scanLine(i: y), n: d->width);
1052 } else {
1053 for (int y = 0; y < d->height; ++y) {
1054 for (int x = 0; x < d->width; ++x) {
1055 uint alpha = *(d->data + x + y * d->width);
1056 image.setPixel(x, y, index_or_rgb: alpha << 24);
1057 }
1058 }
1059
1060 if (image.format() != format)
1061 image = image.convertToFormat(f: format);
1062 }
1063
1064 return image;
1065}
1066
1067QT_END_NAMESPACE
1068
1069

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