src/gui/opengl/qtriangulatingstroker.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtGui module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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     // simplify 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