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 "qtriangulatingstroker_p.h"
5#include <qmath.h>
6
7QT_BEGIN_NAMESPACE
8
9#define CURVE_FLATNESS Q_PI / 8
10
11
12
13
14void QTriangulatingStroker::endCapOrJoinClosed(const qreal *start, const qreal *cur,
15 bool implicitClose, bool endsAtStart)
16{
17 Q_ASSERT(start);
18 if (endsAtStart) {
19 join(pts: start + 2);
20 } else if (implicitClose) {
21 join(pts: start);
22 lineTo(pts: start);
23 join(pts: start+2);
24 } else {
25 endCap(pts: cur);
26 }
27 int count = m_vertices.size();
28
29 // Copy the (x, y) values because QDataBuffer::add(const float& t)
30 // may resize the buffer, which will leave t pointing at the
31 // previous buffer's memory region if we don't copy first.
32 float x = m_vertices.at(i: count-2);
33 float y = m_vertices.at(i: count-1);
34 m_vertices.add(t: x);
35 m_vertices.add(t: y);
36}
37
38static inline void skipDuplicatePoints(const qreal **pts, const qreal *endPts)
39{
40 while ((*pts + 2) < endPts && float((*pts)[0]) == float((*pts)[2])
41 && float((*pts)[1]) == float((*pts)[3]))
42 {
43 *pts += 2;
44 }
45}
46
47void QTriangulatingStroker::process(const QVectorPath &path, const QPen &pen, const QRectF &, QPainter::RenderHints)
48{
49 const qreal *pts = path.points();
50 const QPainterPath::ElementType *types = path.elements();
51 int count = path.elementCount();
52 m_vertices.reset();
53 if (count < 2)
54 return;
55
56 float realWidth = qpen_widthf(p: pen);
57 if (realWidth == 0)
58 realWidth = 1;
59
60 m_width = realWidth / 2;
61
62 bool cosmetic = pen.isCosmetic();
63 if (cosmetic) {
64 m_width = m_width * m_inv_scale;
65 }
66
67 m_join_style = qpen_joinStyle(p: pen);
68 m_cap_style = qpen_capStyle(p: pen);
69 m_miter_limit = pen.miterLimit() * qpen_widthf(p: pen);
70
71 // The curvyness is based on the notion that I originally wanted
72 // roughly one line segment pr 4 pixels. This may seem little, but
73 // because we sample at constantly incrementing B(t) E [0<t<1], we
74 // will get longer segments where the curvature is small and smaller
75 // segments when the curvature is high.
76 //
77 // To get a rough idea of the length of each curve, I pretend that
78 // the curve is a 90 degree arc, whose radius is
79 // qMax(curveBounds.width, curveBounds.height). Based on this
80 // logic we can estimate the length of the outline edges based on
81 // the radius + a pen width and adjusting for scale factors
82 // depending on if the pen is cosmetic or not.
83 //
84 // The curvyness value of PI/14 was based on,
85 // arcLength = 2*PI*r/4 = PI*r/2 and splitting length into somewhere
86 // between 3 and 8 where 5 seemed to be give pretty good results
87 // hence: Q_PI/14. Lower divisors will give more detail at the
88 // direct cost of performance.
89
90 // simplfy pens that are thin in device size (2px wide or less)
91 if (realWidth < 2.5 && (cosmetic || m_inv_scale == 1)) {
92 if (m_cap_style == Qt::RoundCap)
93 m_cap_style = Qt::SquareCap;
94 if (m_join_style == Qt::RoundJoin)
95 m_join_style = Qt::MiterJoin;
96 m_curvyness_add = 0.5;
97 m_curvyness_mul = CURVE_FLATNESS / m_inv_scale;
98 m_roundness = 1;
99 } else if (cosmetic) {
100 m_curvyness_add = realWidth / 2;
101 m_curvyness_mul = float(CURVE_FLATNESS);
102 m_roundness = qMax<int>(a: 4, b: realWidth * CURVE_FLATNESS);
103 } else {
104 m_curvyness_add = m_width;
105 m_curvyness_mul = CURVE_FLATNESS / m_inv_scale;
106 m_roundness = qMax<int>(a: 4, b: realWidth * m_curvyness_mul);
107 }
108
109 // Over this level of segmentation, there doesn't seem to be any
110 // benefit, even for huge penWidth
111 if (m_roundness > 24)
112 m_roundness = 24;
113
114 m_sin_theta = qFastSin(x: Q_PI / m_roundness);
115 m_cos_theta = qFastCos(x: Q_PI / m_roundness);
116
117 const qreal *endPts = pts + (count<<1);
118 const qreal *startPts = nullptr;
119
120 Qt::PenCapStyle cap = m_cap_style;
121
122 if (!types) {
123 skipDuplicatePoints(pts: &pts, endPts);
124 if ((pts + 2) == endPts)
125 return;
126
127 startPts = pts;
128
129 bool endsAtStart = float(startPts[0]) == float(endPts[-2])
130 && float(startPts[1]) == float(endPts[-1]);
131
132 if (endsAtStart || path.hasImplicitClose())
133 m_cap_style = Qt::FlatCap;
134 moveTo(pts);
135 m_cap_style = cap;
136 pts += 2;
137 skipDuplicatePoints(pts: &pts, endPts);
138 lineTo(pts);
139 pts += 2;
140 skipDuplicatePoints(pts: &pts, endPts);
141 while (pts < endPts) {
142 join(pts);
143 lineTo(pts);
144 pts += 2;
145 skipDuplicatePoints(pts: &pts, endPts);
146 }
147 endCapOrJoinClosed(start: startPts, cur: pts-2, implicitClose: path.hasImplicitClose(), endsAtStart);
148
149 } else {
150 bool endsAtStart = false;
151 QPainterPath::ElementType previousType = QPainterPath::MoveToElement;
152 const qreal *previousPts = pts;
153 while (pts < endPts) {
154 switch (*types) {
155 case QPainterPath::MoveToElement: {
156 int end = (endPts - pts) / 2;
157 int nextMoveElement = 1;
158 bool hasValidLineSegments = false;
159 while (nextMoveElement < end && types[nextMoveElement] != QPainterPath::MoveToElement) {
160 if (!hasValidLineSegments) {
161 hasValidLineSegments =
162 float(pts[0]) != float(pts[nextMoveElement * 2]) ||
163 float(pts[1]) != float(pts[nextMoveElement * 2 + 1]);
164 }
165 ++nextMoveElement;
166 }
167
168 /**
169 * 'LineToElement' may be skipped if it doesn't move the center point
170 * of the line. We should make sure that we don't end up with a lost
171 * 'MoveToElement' in the vertex buffer, not connected to anything. Since
172 * the buffer uses degenerate triangles trick to split the primitives,
173 * this spurious MoveToElement will create artifacts when rendering.
174 */
175 if (!hasValidLineSegments) {
176 pts += 2 * nextMoveElement;
177 types += nextMoveElement;
178 continue;
179 }
180
181 if (previousType != QPainterPath::MoveToElement)
182 endCapOrJoinClosed(start: startPts, cur: previousPts, implicitClose: path.hasImplicitClose(), endsAtStart);
183
184 startPts = pts;
185 skipDuplicatePoints(pts: &startPts, endPts); // Skip duplicates to find correct normal.
186 if (startPts + 2 >= endPts)
187 return; // Nothing to see here...
188
189 endsAtStart = float(startPts[0]) == float(pts[nextMoveElement * 2 - 2])
190 && float(startPts[1]) == float(pts[nextMoveElement * 2 - 1]);
191 if (endsAtStart || path.hasImplicitClose())
192 m_cap_style = Qt::FlatCap;
193
194 moveTo(pts: startPts);
195 m_cap_style = cap;
196 previousType = QPainterPath::MoveToElement;
197 previousPts = pts;
198 pts+=2;
199 ++types;
200 break; }
201 case QPainterPath::LineToElement:
202 if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])) {
203 if (previousType != QPainterPath::MoveToElement)
204 join(pts);
205 lineTo(pts);
206 previousType = QPainterPath::LineToElement;
207 previousPts = pts;
208 }
209 pts+=2;
210 ++types;
211 break;
212 case QPainterPath::CurveToElement:
213 if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])
214 || float(pts[0]) != float(pts[2]) || float(pts[1]) != float(pts[3])
215 || float(pts[2]) != float(pts[4]) || float(pts[3]) != float(pts[5]))
216 {
217 if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])) {
218 if (previousType != QPainterPath::MoveToElement)
219 join(pts);
220 }
221 cubicTo(pts);
222 previousType = QPainterPath::CurveToElement;
223 previousPts = pts + 4;
224 }
225 pts+=6;
226 types+=3;
227 break;
228 default:
229 Q_ASSERT(false);
230 break;
231 }
232 }
233
234 if (previousType != QPainterPath::MoveToElement)
235 endCapOrJoinClosed(start: startPts, cur: previousPts, implicitClose: path.hasImplicitClose(), endsAtStart);
236 }
237}
238
239void QTriangulatingStroker::moveTo(const qreal *pts)
240{
241 m_cx = pts[0];
242 m_cy = pts[1];
243
244 float x2 = pts[2];
245 float y2 = pts[3];
246 normalVector(x1: m_cx, y1: m_cy, x2, y2, nx: &m_nvx, ny: &m_nvy);
247
248
249 // To achieve jumps we insert zero-area tringles. This is done by
250 // adding two identical points in both the end of previous strip
251 // and beginning of next strip
252 bool invisibleJump = m_vertices.size();
253
254 switch (m_cap_style) {
255 case Qt::FlatCap:
256 if (invisibleJump) {
257 m_vertices.add(t: m_cx + m_nvx);
258 m_vertices.add(t: m_cy + m_nvy);
259 }
260 break;
261 case Qt::SquareCap: {
262 float sx = m_cx - m_nvy;
263 float sy = m_cy + m_nvx;
264 if (invisibleJump) {
265 m_vertices.add(t: sx + m_nvx);
266 m_vertices.add(t: sy + m_nvy);
267 }
268 emitLineSegment(x: sx, y: sy, vx: m_nvx, vy: m_nvy);
269 break; }
270 case Qt::RoundCap: {
271 QVarLengthArray<float> points;
272 arcPoints(cx: m_cx, cy: m_cy, fromX: m_cx + m_nvx, fromY: m_cy + m_nvy, toX: m_cx - m_nvx, toY: m_cy - m_nvy, points);
273 m_vertices.resize(size: m_vertices.size() + points.size() + 2 * int(invisibleJump));
274 int count = m_vertices.size();
275 int front = 0;
276 int end = points.size() / 2;
277 while (front != end) {
278 m_vertices.at(i: --count) = points[2 * end - 1];
279 m_vertices.at(i: --count) = points[2 * end - 2];
280 --end;
281 if (front == end)
282 break;
283 m_vertices.at(i: --count) = points[2 * front + 1];
284 m_vertices.at(i: --count) = points[2 * front + 0];
285 ++front;
286 }
287
288 if (invisibleJump) {
289 m_vertices.at(i: count - 1) = m_vertices.at(i: count + 1);
290 m_vertices.at(i: count - 2) = m_vertices.at(i: count + 0);
291 }
292 break; }
293 default: break; // ssssh gcc...
294 }
295 emitLineSegment(x: m_cx, y: m_cy, vx: m_nvx, vy: m_nvy);
296}
297
298void QTriangulatingStroker::cubicTo(const qreal *pts)
299{
300 const QPointF *p = (const QPointF *) pts;
301 QBezier bezier = QBezier::fromPoints(p1: *(p - 1), p2: p[0], p3: p[1], p4: p[2]);
302
303 QRectF bounds = bezier.bounds();
304 float rad = qMax(a: bounds.width(), b: bounds.height());
305 int threshold = qMin<float>(a: 64, b: (rad + m_curvyness_add) * m_curvyness_mul);
306 if (threshold < 4)
307 threshold = 4;
308 qreal threshold_minus_1 = threshold - 1;
309 float vx = 0, vy = 0;
310
311 float cx = m_cx, cy = m_cy;
312 float x, y;
313
314 for (int i=1; i<threshold; ++i) {
315 qreal t = qreal(i) / threshold_minus_1;
316 QPointF p = bezier.pointAt(t);
317 x = p.x();
318 y = p.y();
319
320 normalVector(x1: cx, y1: cy, x2: x, y2: y, nx: &vx, ny: &vy);
321
322 emitLineSegment(x, y, vx, vy);
323
324 cx = x;
325 cy = y;
326 }
327
328 m_cx = cx;
329 m_cy = cy;
330
331 m_nvx = vx;
332 m_nvy = vy;
333}
334
335void QTriangulatingStroker::join(const qreal *pts)
336{
337 // Creates a join to the next segment (m_cx, m_cy) -> (pts[0], pts[1])
338 normalVector(x1: m_cx, y1: m_cy, x2: pts[0], y2: pts[1], nx: &m_nvx, ny: &m_nvy);
339
340 switch (m_join_style) {
341 case Qt::BevelJoin:
342 break;
343 case Qt::SvgMiterJoin:
344 case Qt::MiterJoin: {
345 // Find out on which side the join should be.
346 int count = m_vertices.size();
347 float prevNvx = m_vertices.at(i: count - 2) - m_cx;
348 float prevNvy = m_vertices.at(i: count - 1) - m_cy;
349 float xprod = prevNvx * m_nvy - prevNvy * m_nvx;
350 float px, py, qx, qy;
351
352 // If the segments are parallel, use bevel join.
353 if (qFuzzyIsNull(f: xprod))
354 break;
355
356 // Find the corners of the previous and next segment to join.
357 if (xprod < 0) {
358 px = m_vertices.at(i: count - 2);
359 py = m_vertices.at(i: count - 1);
360 qx = m_cx - m_nvx;
361 qy = m_cy - m_nvy;
362 } else {
363 px = m_vertices.at(i: count - 4);
364 py = m_vertices.at(i: count - 3);
365 qx = m_cx + m_nvx;
366 qy = m_cy + m_nvy;
367 }
368
369 // Find intersection point.
370 float pu = px * prevNvx + py * prevNvy;
371 float qv = qx * m_nvx + qy * m_nvy;
372 float ix = (m_nvy * pu - prevNvy * qv) / xprod;
373 float iy = (prevNvx * qv - m_nvx * pu) / xprod;
374
375 // Check that the distance to the intersection point is less than the miter limit.
376 if ((ix - px) * (ix - px) + (iy - py) * (iy - py) <= m_miter_limit * m_miter_limit) {
377 m_vertices.add(t: ix);
378 m_vertices.add(t: iy);
379 m_vertices.add(t: ix);
380 m_vertices.add(t: iy);
381 }
382 // else
383 // Do a plain bevel join if the miter limit is exceeded or if
384 // the lines are parallel. This is not what the raster
385 // engine's stroker does, but it is both faster and similar to
386 // what some other graphics API's do.
387
388 break; }
389 case Qt::RoundJoin: {
390 QVarLengthArray<float> points;
391 int count = m_vertices.size();
392 float prevNvx = m_vertices.at(i: count - 2) - m_cx;
393 float prevNvy = m_vertices.at(i: count - 1) - m_cy;
394 if (m_nvx * prevNvy - m_nvy * prevNvx < 0) {
395 arcPoints(cx: 0, cy: 0, fromX: m_nvx, fromY: m_nvy, toX: -prevNvx, toY: -prevNvy, points);
396 for (int i = points.size() / 2; i > 0; --i)
397 emitLineSegment(x: m_cx, y: m_cy, vx: points[2 * i - 2], vy: points[2 * i - 1]);
398 } else {
399 arcPoints(cx: 0, cy: 0, fromX: -prevNvx, fromY: -prevNvy, toX: m_nvx, toY: m_nvy, points);
400 for (int i = 0; i < points.size() / 2; ++i)
401 emitLineSegment(x: m_cx, y: m_cy, vx: points[2 * i + 0], vy: points[2 * i + 1]);
402 }
403 break; }
404 default: break; // gcc warn--
405 }
406
407 emitLineSegment(x: m_cx, y: m_cy, vx: m_nvx, vy: m_nvy);
408}
409
410void QTriangulatingStroker::endCap(const qreal *)
411{
412 switch (m_cap_style) {
413 case Qt::FlatCap:
414 break;
415 case Qt::SquareCap:
416 emitLineSegment(x: m_cx + m_nvy, y: m_cy - m_nvx, vx: m_nvx, vy: m_nvy);
417 break;
418 case Qt::RoundCap: {
419 QVarLengthArray<float> points;
420 int count = m_vertices.size();
421 arcPoints(cx: m_cx, cy: m_cy, fromX: m_vertices.at(i: count - 2), fromY: m_vertices.at(i: count - 1), toX: m_vertices.at(i: count - 4), toY: m_vertices.at(i: count - 3), points);
422 int front = 0;
423 int end = points.size() / 2;
424 while (front != end) {
425 m_vertices.add(t: points[2 * end - 2]);
426 m_vertices.add(t: points[2 * end - 1]);
427 --end;
428 if (front == end)
429 break;
430 m_vertices.add(t: points[2 * front + 0]);
431 m_vertices.add(t: points[2 * front + 1]);
432 ++front;
433 }
434 break; }
435 default: break; // to shut gcc up...
436 }
437}
438
439void QTriangulatingStroker::arcPoints(float cx, float cy, float fromX, float fromY, float toX, float toY, QVarLengthArray<float> &points)
440{
441 float dx1 = fromX - cx;
442 float dy1 = fromY - cy;
443 float dx2 = toX - cx;
444 float dy2 = toY - cy;
445
446 // while more than 180 degrees left:
447 while (dx1 * dy2 - dx2 * dy1 < 0) {
448 float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta;
449 float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta;
450 dx1 = tmpx;
451 dy1 = tmpy;
452 points.append(t: cx + dx1);
453 points.append(t: cy + dy1);
454 }
455
456 // while more than 90 degrees left:
457 while (dx1 * dx2 + dy1 * dy2 < 0) {
458 float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta;
459 float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta;
460 dx1 = tmpx;
461 dy1 = tmpy;
462 points.append(t: cx + dx1);
463 points.append(t: cy + dy1);
464 }
465
466 // while more than 0 degrees left:
467 while (dx1 * dy2 - dx2 * dy1 > 0) {
468 float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta;
469 float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta;
470 dx1 = tmpx;
471 dy1 = tmpy;
472 points.append(t: cx + dx1);
473 points.append(t: cy + dy1);
474 }
475
476 // remove last point which was rotated beyond [toX, toY].
477 if (!points.isEmpty())
478 points.resize(sz: points.size() - 2);
479}
480
481static void qdashprocessor_moveTo(qreal x, qreal y, void *data)
482{
483 ((QDashedStrokeProcessor *) data)->addElement(type: QPainterPath::MoveToElement, x, y);
484}
485
486static void qdashprocessor_lineTo(qreal x, qreal y, void *data)
487{
488 ((QDashedStrokeProcessor *) data)->addElement(type: QPainterPath::LineToElement, x, y);
489}
490
491static void qdashprocessor_cubicTo(qreal, qreal, qreal, qreal, qreal, qreal, void *)
492{
493 Q_ASSERT(0); // The dasher should not produce curves...
494}
495
496QDashedStrokeProcessor::QDashedStrokeProcessor()
497 : m_points(0), m_types(0),
498 m_dash_stroker(nullptr), m_inv_scale(1)
499{
500 m_dash_stroker.setMoveToHook(qdashprocessor_moveTo);
501 m_dash_stroker.setLineToHook(qdashprocessor_lineTo);
502 m_dash_stroker.setCubicToHook(qdashprocessor_cubicTo);
503}
504
505void QDashedStrokeProcessor::process(const QVectorPath &path, const QPen &pen, const QRectF &clip, QPainter::RenderHints)
506{
507
508 const qreal *pts = path.points();
509 const QPainterPath::ElementType *types = path.elements();
510 int count = path.elementCount();
511
512 bool cosmetic = pen.isCosmetic();
513 bool implicitClose = path.hasImplicitClose();
514
515 m_points.reset();
516 m_types.reset();
517 m_points.reserve(size: path.elementCount());
518 m_types.reserve(size: path.elementCount());
519
520 qreal width = qpen_widthf(p: pen);
521 if (width == 0)
522 width = 1;
523
524 m_dash_stroker.setDashPattern(pen.dashPattern());
525 m_dash_stroker.setStrokeWidth(cosmetic ? width * m_inv_scale : width);
526 m_dash_stroker.setDashOffset(pen.dashOffset());
527 m_dash_stroker.setMiterLimit(pen.miterLimit());
528 m_dash_stroker.setClipRect(clip);
529
530 float curvynessAdd, curvynessMul;
531
532 // simplify pens that are thin in device size (2px wide or less)
533 if (width < 2.5 && (cosmetic || m_inv_scale == 1)) {
534 curvynessAdd = 0.5;
535 curvynessMul = CURVE_FLATNESS / m_inv_scale;
536 } else if (cosmetic) {
537 curvynessAdd= width / 2;
538 curvynessMul= float(CURVE_FLATNESS);
539 } else {
540 curvynessAdd = width * m_inv_scale;
541 curvynessMul = CURVE_FLATNESS / m_inv_scale;
542 }
543
544 if (count < 2)
545 return;
546
547 bool needsClose = false;
548 if (implicitClose) {
549 if (pts[0] != pts[count * 2 - 2] || pts[1] != pts[count * 2 - 1])
550 needsClose = true;
551 }
552
553 const qreal *firstPts = pts;
554 const qreal *endPts = pts + (count<<1);
555 m_dash_stroker.begin(data: this);
556
557 if (!types) {
558 m_dash_stroker.moveTo(x: pts[0], y: pts[1]);
559 pts += 2;
560 while (pts < endPts) {
561 m_dash_stroker.lineTo(x: pts[0], y: pts[1]);
562 pts += 2;
563 }
564 } else {
565 while (pts < endPts) {
566 switch (*types) {
567 case QPainterPath::MoveToElement:
568 m_dash_stroker.moveTo(x: pts[0], y: pts[1]);
569 pts += 2;
570 ++types;
571 break;
572 case QPainterPath::LineToElement:
573 m_dash_stroker.lineTo(x: pts[0], y: pts[1]);
574 pts += 2;
575 ++types;
576 break;
577 case QPainterPath::CurveToElement: {
578 QBezier b = QBezier::fromPoints(p1: *(((const QPointF *) pts) - 1),
579 p2: *(((const QPointF *) pts)),
580 p3: *(((const QPointF *) pts) + 1),
581 p4: *(((const QPointF *) pts) + 2));
582 QRectF bounds = b.bounds();
583 float rad = qMax(a: bounds.width(), b: bounds.height());
584 int threshold = qMin<float>(a: 64, b: (rad + curvynessAdd) * curvynessMul);
585 if (threshold < 4)
586 threshold = 4;
587
588 qreal threshold_minus_1 = threshold - 1;
589 for (int i=0; i<threshold; ++i) {
590 QPointF pt = b.pointAt(t: i / threshold_minus_1);
591 m_dash_stroker.lineTo(x: pt.x(), y: pt.y());
592 }
593 pts += 6;
594 types += 3;
595 break; }
596 default: break;
597 }
598 }
599 }
600 if (needsClose)
601 m_dash_stroker.lineTo(x: firstPts[0], y: firstPts[1]);
602
603 m_dash_stroker.end();
604}
605
606QT_END_NAMESPACE
607

source code of qtbase/src/gui/painting/qtriangulatingstroker.cpp