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