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 if (count < 2)
88 return;
89
90 float realWidth = qpen_widthf(pen);
91 if (realWidth == 0)
92 realWidth = 1;
93
94 m_width = realWidth / 2;
95
96 bool cosmetic = qt_pen_is_cosmetic(pen, hints);
97 if (cosmetic) {
98 m_width = m_width * m_inv_scale;
99 }
100
101 m_join_style = qpen_joinStyle(pen);
102 m_cap_style = qpen_capStyle(pen);
103 m_vertices.reset();
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 = 0;
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 if (previousType != QPainterPath::MoveToElement)
192 endCapOrJoinClosed(startPts, previousPts, path.hasImplicitClose(), endsAtStart);
193
194 startPts = pts;
195 skipDuplicatePoints(&startPts, endPts); // Skip duplicates to find correct normal.
196 if (startPts + 2 >= endPts)
197 return; // Nothing to see here...
198
199 int end = (endPts - pts) / 2;
200 int i = 2; // Start looking to ahead since we never have two moveto's in a row
201 while (i<end && types[i] != QPainterPath::MoveToElement) {
202 ++i;
203 }
204 endsAtStart = float(startPts[0]) == float(pts[i*2 - 2])
205 && float(startPts[1]) == float(pts[i*2 - 1]);
206 if (endsAtStart || path.hasImplicitClose())
207 m_cap_style = Qt::FlatCap;
208
209 moveTo(startPts);
210 m_cap_style = cap;
211 previousType = QPainterPath::MoveToElement;
212 previousPts = pts;
213 pts+=2;
214 ++types;
215 break; }
216 case QPainterPath::LineToElement:
217 if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])) {
218 if (previousType != QPainterPath::MoveToElement)
219 join(pts);
220 lineTo(pts);
221 previousType = QPainterPath::LineToElement;
222 previousPts = pts;
223 }
224 pts+=2;
225 ++types;
226 break;
227 case QPainterPath::CurveToElement:
228 if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])
229 || float(pts[0]) != float(pts[2]) || float(pts[1]) != float(pts[3])
230 || float(pts[2]) != float(pts[4]) || float(pts[3]) != float(pts[5]))
231 {
232 if (float(m_cx) != float(pts[0]) || float(m_cy) != float(pts[1])) {
233 if (previousType != QPainterPath::MoveToElement)
234 join(pts);
235 }
236 cubicTo(pts);
237 previousType = QPainterPath::CurveToElement;
238 previousPts = pts + 4;
239 }
240 pts+=6;
241 types+=3;
242 break;
243 default:
244 Q_ASSERT(false);
245 break;
246 }
247 }
248
249 if (previousType != QPainterPath::MoveToElement)
250 endCapOrJoinClosed(startPts, previousPts, path.hasImplicitClose(), endsAtStart);
251 }
252}
253
254void QTriangulatingStroker::moveTo(const qreal *pts)
255{
256 m_cx = pts[0];
257 m_cy = pts[1];
258
259 float x2 = pts[2];
260 float y2 = pts[3];
261 normalVector(m_cx, m_cy, x2, y2, &m_nvx, &m_nvy);
262
263
264 // To achieve jumps we insert zero-area tringles. This is done by
265 // adding two identical points in both the end of previous strip
266 // and beginning of next strip
267 bool invisibleJump = m_vertices.size();
268
269 switch (m_cap_style) {
270 case Qt::FlatCap:
271 if (invisibleJump) {
272 m_vertices.add(m_cx + m_nvx);
273 m_vertices.add(m_cy + m_nvy);
274 }
275 break;
276 case Qt::SquareCap: {
277 float sx = m_cx - m_nvy;
278 float sy = m_cy + m_nvx;
279 if (invisibleJump) {
280 m_vertices.add(sx + m_nvx);
281 m_vertices.add(sy + m_nvy);
282 }
283 emitLineSegment(sx, sy, m_nvx, m_nvy);
284 break; }
285 case Qt::RoundCap: {
286 QVarLengthArray<float> points;
287 arcPoints(m_cx, m_cy, m_cx + m_nvx, m_cy + m_nvy, m_cx - m_nvx, m_cy - m_nvy, points);
288 m_vertices.resize(m_vertices.size() + points.size() + 2 * int(invisibleJump));
289 int count = m_vertices.size();
290 int front = 0;
291 int end = points.size() / 2;
292 while (front != end) {
293 m_vertices.at(--count) = points[2 * end - 1];
294 m_vertices.at(--count) = points[2 * end - 2];
295 --end;
296 if (front == end)
297 break;
298 m_vertices.at(--count) = points[2 * front + 1];
299 m_vertices.at(--count) = points[2 * front + 0];
300 ++front;
301 }
302
303 if (invisibleJump) {
304 m_vertices.at(count - 1) = m_vertices.at(count + 1);
305 m_vertices.at(count - 2) = m_vertices.at(count + 0);
306 }
307 break; }
308 default: break; // ssssh gcc...
309 }
310 emitLineSegment(m_cx, m_cy, m_nvx, m_nvy);
311}
312
313void QTriangulatingStroker::cubicTo(const qreal *pts)
314{
315 const QPointF *p = (const QPointF *) pts;
316 QBezier bezier = QBezier::fromPoints(*(p - 1), p[0], p[1], p[2]);
317
318 QRectF bounds = bezier.bounds();
319 float rad = qMax(bounds.width(), bounds.height());
320 int threshold = qMin<float>(64, (rad + m_curvyness_add) * m_curvyness_mul);
321 if (threshold < 4)
322 threshold = 4;
323 qreal threshold_minus_1 = threshold - 1;
324 float vx = 0, vy = 0;
325
326 float cx = m_cx, cy = m_cy;
327 float x, y;
328
329 for (int i=1; i<threshold; ++i) {
330 qreal t = qreal(i) / threshold_minus_1;
331 QPointF p = bezier.pointAt(t);
332 x = p.x();
333 y = p.y();
334
335 normalVector(cx, cy, x, y, &vx, &vy);
336
337 emitLineSegment(x, y, vx, vy);
338
339 cx = x;
340 cy = y;
341 }
342
343 m_cx = cx;
344 m_cy = cy;
345
346 m_nvx = vx;
347 m_nvy = vy;
348}
349
350void QTriangulatingStroker::join(const qreal *pts)
351{
352 // Creates a join to the next segment (m_cx, m_cy) -> (pts[0], pts[1])
353 normalVector(m_cx, m_cy, pts[0], pts[1], &m_nvx, &m_nvy);
354
355 switch (m_join_style) {
356 case Qt::BevelJoin:
357 break;
358 case Qt::SvgMiterJoin:
359 case Qt::MiterJoin: {
360 // Find out on which side the join should be.
361 int count = m_vertices.size();
362 float prevNvx = m_vertices.at(count - 2) - m_cx;
363 float prevNvy = m_vertices.at(count - 1) - m_cy;
364 float xprod = prevNvx * m_nvy - prevNvy * m_nvx;
365 float px, py, qx, qy;
366
367 // If the segments are parallel, use bevel join.
368 if (qFuzzyIsNull(xprod))
369 break;
370
371 // Find the corners of the previous and next segment to join.
372 if (xprod < 0) {
373 px = m_vertices.at(count - 2);
374 py = m_vertices.at(count - 1);
375 qx = m_cx - m_nvx;
376 qy = m_cy - m_nvy;
377 } else {
378 px = m_vertices.at(count - 4);
379 py = m_vertices.at(count - 3);
380 qx = m_cx + m_nvx;
381 qy = m_cy + m_nvy;
382 }
383
384 // Find intersection point.
385 float pu = px * prevNvx + py * prevNvy;
386 float qv = qx * m_nvx + qy * m_nvy;
387 float ix = (m_nvy * pu - prevNvy * qv) / xprod;
388 float iy = (prevNvx * qv - m_nvx * pu) / xprod;
389
390 // Check that the distance to the intersection point is less than the miter limit.
391 if ((ix - px) * (ix - px) + (iy - py) * (iy - py) <= m_miter_limit * m_miter_limit) {
392 m_vertices.add(ix);
393 m_vertices.add(iy);
394 m_vertices.add(ix);
395 m_vertices.add(iy);
396 }
397 // else
398 // Do a plain bevel join if the miter limit is exceeded or if
399 // the lines are parallel. This is not what the raster
400 // engine's stroker does, but it is both faster and similar to
401 // what some other graphics API's do.
402
403 break; }
404 case Qt::RoundJoin: {
405 QVarLengthArray<float> points;
406 int count = m_vertices.size();
407 float prevNvx = m_vertices.at(count - 2) - m_cx;
408 float prevNvy = m_vertices.at(count - 1) - m_cy;
409 if (m_nvx * prevNvy - m_nvy * prevNvx < 0) {
410 arcPoints(0, 0, m_nvx, m_nvy, -prevNvx, -prevNvy, points);
411 for (int i = points.size() / 2; i > 0; --i)
412 emitLineSegment(m_cx, m_cy, points[2 * i - 2], points[2 * i - 1]);
413 } else {
414 arcPoints(0, 0, -prevNvx, -prevNvy, m_nvx, m_nvy, points);
415 for (int i = 0; i < points.size() / 2; ++i)
416 emitLineSegment(m_cx, m_cy, points[2 * i + 0], points[2 * i + 1]);
417 }
418 break; }
419 default: break; // gcc warn--
420 }
421
422 emitLineSegment(m_cx, m_cy, m_nvx, m_nvy);
423}
424
425void QTriangulatingStroker::endCap(const qreal *)
426{
427 switch (m_cap_style) {
428 case Qt::FlatCap:
429 break;
430 case Qt::SquareCap:
431 emitLineSegment(m_cx + m_nvy, m_cy - m_nvx, m_nvx, m_nvy);
432 break;
433 case Qt::RoundCap: {
434 QVarLengthArray<float> points;
435 int count = m_vertices.size();
436 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);
437 int front = 0;
438 int end = points.size() / 2;
439 while (front != end) {
440 m_vertices.add(points[2 * end - 2]);
441 m_vertices.add(points[2 * end - 1]);
442 --end;
443 if (front == end)
444 break;
445 m_vertices.add(points[2 * front + 0]);
446 m_vertices.add(points[2 * front + 1]);
447 ++front;
448 }
449 break; }
450 default: break; // to shut gcc up...
451 }
452}
453
454void QTriangulatingStroker::arcPoints(float cx, float cy, float fromX, float fromY, float toX, float toY, QVarLengthArray<float> &points)
455{
456 float dx1 = fromX - cx;
457 float dy1 = fromY - cy;
458 float dx2 = toX - cx;
459 float dy2 = toY - cy;
460
461 // while more than 180 degrees left:
462 while (dx1 * dy2 - dx2 * dy1 < 0) {
463 float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta;
464 float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta;
465 dx1 = tmpx;
466 dy1 = tmpy;
467 points.append(cx + dx1);
468 points.append(cy + dy1);
469 }
470
471 // while more than 90 degrees left:
472 while (dx1 * dx2 + dy1 * dy2 < 0) {
473 float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta;
474 float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta;
475 dx1 = tmpx;
476 dy1 = tmpy;
477 points.append(cx + dx1);
478 points.append(cy + dy1);
479 }
480
481 // while more than 0 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 // remove last point which was rotated beyond [toX, toY].
492 if (!points.isEmpty())
493 points.resize(points.size() - 2);
494}
495
496static void qdashprocessor_moveTo(qreal x, qreal y, void *data)
497{
498 ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::MoveToElement, x, y);
499}
500
501static void qdashprocessor_lineTo(qreal x, qreal y, void *data)
502{
503 ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::LineToElement, x, y);
504}
505
506static void qdashprocessor_cubicTo(qreal, qreal, qreal, qreal, qreal, qreal, void *)
507{
508 Q_ASSERT(0); // The dasher should not produce curves...
509}
510
511QDashedStrokeProcessor::QDashedStrokeProcessor()
512 : m_points(0), m_types(0),
513 m_dash_stroker(0), m_inv_scale(1)
514{
515 m_dash_stroker.setMoveToHook(qdashprocessor_moveTo);
516 m_dash_stroker.setLineToHook(qdashprocessor_lineTo);
517 m_dash_stroker.setCubicToHook(qdashprocessor_cubicTo);
518}
519
520void QDashedStrokeProcessor::process(const QVectorPath &path, const QPen &pen, const QRectF &clip, QPainter::RenderHints hints)
521{
522
523 const qreal *pts = path.points();
524 const QPainterPath::ElementType *types = path.elements();
525 int count = path.elementCount();
526
527 bool cosmetic = qt_pen_is_cosmetic(pen, hints);
528 bool implicitClose = path.hasImplicitClose();
529
530 m_points.reset();
531 m_types.reset();
532 m_points.reserve(path.elementCount());
533 m_types.reserve(path.elementCount());
534
535 qreal width = qpen_widthf(pen);
536 if (width == 0)
537 width = 1;
538
539 m_dash_stroker.setDashPattern(pen.dashPattern());
540 m_dash_stroker.setStrokeWidth(cosmetic ? width * m_inv_scale : width);
541 m_dash_stroker.setDashOffset(pen.dashOffset());
542 m_dash_stroker.setMiterLimit(pen.miterLimit());
543 m_dash_stroker.setClipRect(clip);
544
545 float curvynessAdd, curvynessMul;
546
547 // simplify pens that are thin in device size (2px wide or less)
548 if (width < 2.5 && (cosmetic || m_inv_scale == 1)) {
549 curvynessAdd = 0.5;
550 curvynessMul = CURVE_FLATNESS / m_inv_scale;
551 } else if (cosmetic) {
552 curvynessAdd= width / 2;
553 curvynessMul= float(CURVE_FLATNESS);
554 } else {
555 curvynessAdd = width * m_inv_scale;
556 curvynessMul = CURVE_FLATNESS / m_inv_scale;
557 }
558
559 if (count < 2)
560 return;
561
562 bool needsClose = false;
563 if (implicitClose) {
564 if (pts[0] != pts[count * 2 - 2] || pts[1] != pts[count * 2 - 1])
565 needsClose = true;
566 }
567
568 const qreal *firstPts = pts;
569 const qreal *endPts = pts + (count<<1);
570 m_dash_stroker.begin(this);
571
572 if (!types) {
573 m_dash_stroker.moveTo(pts[0], pts[1]);
574 pts += 2;
575 while (pts < endPts) {
576 m_dash_stroker.lineTo(pts[0], pts[1]);
577 pts += 2;
578 }
579 } else {
580 while (pts < endPts) {
581 switch (*types) {
582 case QPainterPath::MoveToElement:
583 m_dash_stroker.moveTo(pts[0], pts[1]);
584 pts += 2;
585 ++types;
586 break;
587 case QPainterPath::LineToElement:
588 m_dash_stroker.lineTo(pts[0], pts[1]);
589 pts += 2;
590 ++types;
591 break;
592 case QPainterPath::CurveToElement: {
593 QBezier b = QBezier::fromPoints(*(((const QPointF *) pts) - 1),
594 *(((const QPointF *) pts)),
595 *(((const QPointF *) pts) + 1),
596 *(((const QPointF *) pts) + 2));
597 QRectF bounds = b.bounds();
598 float rad = qMax(bounds.width(), bounds.height());
599 int threshold = qMin<float>(64, (rad + curvynessAdd) * curvynessMul);
600 if (threshold < 4)
601 threshold = 4;
602
603 qreal threshold_minus_1 = threshold - 1;
604 for (int i=0; i<threshold; ++i) {
605 QPointF pt = b.pointAt(i / threshold_minus_1);
606 m_dash_stroker.lineTo(pt.x(), pt.y());
607 }
608 pts += 6;
609 types += 3;
610 break; }
611 default: break;
612 }
613 }
614 }
615 if (needsClose)
616 m_dash_stroker.lineTo(firstPts[0], firstPts[1]);
617
618 m_dash_stroker.end();
619}
620
621QT_END_NAMESPACE
622
623