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