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