Qt 4.8
qtriangulatingstroker.cpp
Go to the documentation of this file.
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
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 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 
43 #include <qmath.h>
44 
46 
47 #define CURVE_FLATNESS Q_PI / 8
48 
49 
50 
51 
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 
76 void QTriangulatingStroker::process(const QVectorPath &path, const QPen &pen, const QRectF &)
77 {
78  const qreal *pts = path.points();
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) {
93  }
94 
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)
125  m_curvyness_add = 0.5;
127  m_roundness = 1;
128  } else if (cosmetic) {
129  m_curvyness_add = realWidth / 2;
131  m_roundness = qMax<int>(4, realWidth * CURVE_FLATNESS);
132  } else {
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 
145 
146  const qreal *endPts = pts + (count<<1);
147  const qreal *startPts = 0;
148 
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())
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) {
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())
196 
197  moveTo(pts);
198  m_cap_style = cap;
199  pts+=2;
200  ++types;
201  break; }
203  if (*(types - 1) != QPainterPath::MoveToElement)
204  join(pts);
205  lineTo(pts);
206  pts+=2;
207  ++types;
208  break;
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 
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) {
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  }
283 }
284 
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 
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 
395 }
396 
398 {
399  switch (m_cap_style) {
400  case Qt::FlatCap:
401  break;
402  case Qt::SquareCap:
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 
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 
468 static void qdashprocessor_moveTo(qreal x, qreal y, void *data)
469 {
470  ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::MoveToElement, x, y);
471 }
472 
473 static void qdashprocessor_lineTo(qreal x, qreal y, void *data)
474 {
475  ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::LineToElement, x, y);
476 }
477 
479 {
480  Q_ASSERT(0); // The dasher should not produce curves...
481 }
482 
484  : m_points(0), m_types(0),
485  m_dash_stroker(0), m_inv_scale(1)
486 {
490 }
491 
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 
511  m_dash_stroker.setStrokeWidth(cosmetic ? width * m_inv_scale : width);
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) {
548  m_dash_stroker.moveTo(pts[0], pts[1]);
549  pts += 2;
550  ++types;
551  break;
553  m_dash_stroker.lineTo(pts[0], pts[1]);
554  pts += 2;
555  ++types;
556  break;
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 
582 }
583 
585 
void resize(int size)
ElementType
This enum describes the types of elements used to connect vertices in subpaths.
Definition: qpainterpath.h:70
void setClipRect(const QRectF &clip)
Definition: qstroker_p.h:165
double qreal
Definition: qglobal.h:1193
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
int elementCount() const
void lineTo(qfixed x, qfixed y)
Definition: qstroker_p.h:317
void cubicTo(const qreal *pts)
void setDashOffset(qreal offset)
Definition: qstroker_p.h:265
void resize(int size)
The QPointF class defines a point in the plane using floating point precision.
Definition: qpoint.h:214
static void qdashprocessor_cubicTo(qreal, qreal, qreal, qreal, qreal, qreal, void *)
void process(const QVectorPath &path, const QPen &pen, const QRectF &clip)
qreal qFastSin(qreal x)
Definition: qmath.h:264
#define CURVE_FLATNESS
Qt::PenJoinStyle qpen_joinStyle(const QPen &p)
Definition: qpainter_p.h:91
QPointF pointAt(qreal t) const
Definition: qbezier_p.h:163
Qt::PenCapStyle qpen_capStyle(const QPen &p)
Definition: qpainter_p.h:90
void setDashPattern(const QVector< qfixed > &dashPattern)
Definition: qstroker_p.h:262
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
static void qdashprocessor_moveTo(qreal x, qreal y, void *data)
The QPen class defines how a QPainter should draw lines and outlines of shapes.
Definition: qpen.h:64
void append(const T &t)
const QPainterPath::ElementType * elements() const
void emitLineSegment(float x, float y, float nx, float ny)
QVector< qreal > dashPattern() const
Returns the dash pattern of this pen.
Definition: qpen.cpp:466
void setCubicToHook(qStrokerCubicToHook cubicToHook)
Definition: qstroker_p.h:150
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
qreal x() const
Returns the x-coordinate of this point.
Definition: qpoint.h:282
PenCapStyle
Definition: qnamespace.h:1147
void setMiterLimit(qreal limit)
Definition: qstroker_p.h:272
virtual void end()
Finishes the stroke.
Definition: qstroker_p.h:385
static QBezier fromPoints(const QPointF &p1, const QPointF &p2, const QPointF &p3, const QPointF &p4)
Definition: qbezier.cpp:71
void reserve(int size)
QDataBuffer< QPainterPath::ElementType > m_types
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
void normalVector(float x1, float y1, float x2, float y2, float *nx, float *ny)
void endCapOrJoinClosed(const qreal *start, const qreal *cur, bool implicitClose, bool endsAtStart)
bool isCosmetic() const
Returns true if the pen is cosmetic; otherwise returns false.
Definition: qpen.cpp:840
virtual void begin(void *data)
Prepares the stroker.
Definition: qstroker_p.h:378
qreal height() const
Returns the height of the rectangle.
Definition: qrect.h:710
qreal qpen_widthf(const QPen &p)
Definition: qpainter_p.h:88
Type & at(int i)
Definition: qdatabuffer_p.h:86
static const char * data(const QByteArray &arr)
QDataBuffer< qreal > m_points
qreal width() const
Returns the width of the rectangle.
Definition: qrect.h:707
void add(const Type &t)
Definition: qdatabuffer_p.h:93
bool isEmpty() const
void process(const QVectorPath &path, const QPen &pen, const QRectF &clip)
QRectF bounds() const
Definition: qbezier.cpp:223
QDataBuffer< float > m_vertices
static void qdashprocessor_lineTo(qreal x, qreal y, void *data)
static const struct @32 types[]
qreal miterLimit() const
Returns the miter limit of the pen.
Definition: qpen.cpp:589
void join(const qreal *pts)
qreal qFastCos(qreal x)
Definition: qmath.h:274
const qreal * points() const
void lineTo(const qreal *pts)
bool hasImplicitClose() const
void moveTo(const qreal *pts)
void arcPoints(float cx, float cy, float fromX, float fromY, float toX, float toY, QVarLengthArray< float > &points)
qreal y() const
Returns the y-coordinate of this point.
Definition: qpoint.h:287
qreal dashOffset() const
Returns the dash offset for the pen.
Definition: qpen.cpp:547
static Q_DECL_CONSTEXPR bool qFuzzyIsNull(double d)
Definition: qglobal.h:2043
void setLineToHook(qStrokerLineToHook lineToHook)
Definition: qstroker_p.h:149
void endCap(const qreal *pts)
void moveTo(qfixed x, qfixed y)
Definition: qstroker_p.h:308
void setMoveToHook(qStrokerMoveToHook moveToHook)
Definition: qstroker_p.h:148
static const KeyPair *const end
void setStrokeWidth(qreal width)
Definition: qstroker_p.h:271
void reset()
Definition: qdatabuffer_p.h:79
int size() const
int size() const
Definition: qdatabuffer_p.h:83
static const qreal Q_PI
Definition: qmath_p.h:61