1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #include "private/qstroker_p.h"

    43 #include "private/qbezier_p.h"

    44 #include "private/qmath_p.h"

    45 #include "qline.h"

    46 #include "qtransform.h"

    47 #include <qmath.h>

    48 

    49 QT_BEGIN_NAMESPACE

    50 

    51 // #define QPP_STROKE_DEBUG

    52 

    53 class QSubpathForwardIterator

    54 {

    55 public:

    56     QSubpathForwardIterator(const QDataBuffer<QStrokerOps::Element> *path)

    57         : m_path(path), m_pos(0) { }

    58     inline int position() const { return m_pos; }

    59     inline bool hasNext() const { return m_pos < m_path->size(); }

    60     inline QStrokerOps::Element next() { Q_ASSERT(hasNext()); return m_path->at(m_pos++); }

    61 

    62 private:

    63     const QDataBuffer<QStrokerOps::Element> *m_path;

    64     int m_pos;

    65 };

    66 

    67 class QSubpathBackwardIterator

    68 {

    69 public:

    70     QSubpathBackwardIterator(const QDataBuffer<QStrokerOps::Element> *path)

    71         : m_path(path), m_pos(path->size() - 1) { }

    72 

    73     inline int position() const { return m_pos; }

    74 

    75     inline bool hasNext() const { return m_pos >= 0; }

    76 

    77     inline QStrokerOps::Element next()

    78     {

    79         Q_ASSERT(hasNext());

    80 

    81         QStrokerOps::Element ce = m_path->at(m_pos);   // current element

    82 

    83         if (m_pos == m_path->size() - 1) {

    84             --m_pos;

    85             ce.type = QPainterPath::MoveToElement;

    86             return ce;

    87         }

    88 

    89         const QStrokerOps::Element &pe = m_path->at(m_pos + 1); // previous element

    90 

    91         switch (pe.type) {

    92         case QPainterPath::LineToElement:

    93             ce.type = QPainterPath::LineToElement;

    94             break;

    95         case QPainterPath::CurveToDataElement:

    96             // First control point?

    97             if (ce.type == QPainterPath::CurveToElement) {

    98                 ce.type = QPainterPath::CurveToDataElement;

    99             } else { // Second control point then

   100                 ce.type = QPainterPath::CurveToElement;

   101             }

   102             break;

   103         case QPainterPath::CurveToElement:

   104             ce.type = QPainterPath::CurveToDataElement;

   105             break;

   106         default:

   107             qWarning("QSubpathReverseIterator::next: Case %d unhandled", ce.type);

   108             break;

   109         }

   110         --m_pos;

   111 

   112         return ce;

   113     }

   114 

   115 private:

   116     const QDataBuffer<QStrokerOps::Element> *m_path;

   117     int m_pos;

   118 };

   119 

   120 class QSubpathFlatIterator

   121 {

   122 public:

   123     QSubpathFlatIterator(const QDataBuffer<QStrokerOps::Element> *path)

   124         : m_path(path), m_pos(0), m_curve_index(-1) { }

   125 

   126     inline bool hasNext() const { return m_curve_index >= 0 || m_pos < m_path->size(); }

   127 

   128     QStrokerOps::Element next()

   129     {

   130         Q_ASSERT(hasNext());

   131 

   132         if (m_curve_index >= 0) {

   133             QStrokerOps::Element e = { QPainterPath::LineToElement,

   134                                        qt_real_to_fixed(m_curve.at(m_curve_index).x()),

   135                                        qt_real_to_fixed(m_curve.at(m_curve_index).y())

   136                                        };

   137             ++m_curve_index;

   138             if (m_curve_index >= m_curve.size())

   139                 m_curve_index = -1;

   140             return e;

   141         }

   142 

   143         QStrokerOps::Element e = m_path->at(m_pos);

   144         if (e.isCurveTo()) {

   145             Q_ASSERT(m_pos > 0);

   146             Q_ASSERT(m_pos < m_path->size());

   147 

   148             m_curve = QBezier::fromPoints(QPointF(qt_fixed_to_real(m_path->at(m_pos-1).x),

   149                                                   qt_fixed_to_real(m_path->at(m_pos-1).y)),

   150                                           QPointF(qt_fixed_to_real(e.x),

   151                                                   qt_fixed_to_real(e.y)),

   152                                           QPointF(qt_fixed_to_real(m_path->at(m_pos+1).x),

   153                                                   qt_fixed_to_real(m_path->at(m_pos+1).y)),

   154                                           QPointF(qt_fixed_to_real(m_path->at(m_pos+2).x),

   155                                                   qt_fixed_to_real(m_path->at(m_pos+2).y))).toPolygon();

   156             m_curve_index = 1;

   157             e.type = QPainterPath::LineToElement;

   158             e.x = m_curve.at(0).x();

   159             e.y = m_curve.at(0).y();

   160             m_pos += 2;

   161         }

   162         Q_ASSERT(e.isLineTo() || e.isMoveTo());

   163         ++m_pos;

   164         return e;

   165     }

   166 

   167 private:

   168     const QDataBuffer<QStrokerOps::Element> *m_path;

   169     int m_pos;

   170     QPolygonF m_curve;

   171     int m_curve_index;

   172 };

   173 

   174 template <class Iterator> bool qt_stroke_side(Iterator *it, QStroker *stroker,

   175                                               bool capFirst, QLineF *startTangent);

   176 

   177 /*******************************************************************************

   178  * QLineF::angle gives us the smalles angle between two lines. Here we

   179  * want to identify the line's angle direction on the unit circle.

   180  */

   181 static inline qreal adapted_angle_on_x(const QLineF &line)

   182 {

   183     qreal angle = line.angle(QLineF(0, 0, 1, 0));

   184     if (line.dy() > 0)

   185         angle = 360 - angle;

   186     return angle;

   187 }

   188 

   189 QStrokerOps::QStrokerOps()

   190     : m_customData(0), m_moveTo(0), m_lineTo(0), m_cubicTo(0)

   191 {

   192 }

   193 

   194 QStrokerOps::~QStrokerOps()

   195 {

   196 }

   197 

   198 

   199 /*!

   200     Prepares the stroker. Call this function once before starting a

   201     stroke by calling moveTo, lineTo or cubicTo.

   202 

   203     The \a customData is passed back through that callback functions

   204     and can be used by the user to for instance maintain state

   205     information.

   206 */

   207 void QStrokerOps::begin(void *customData)

   208 {

   209     m_customData = customData;

   210     m_elements.reset();

   211 }

   212 

   213 

   214 /*!

   215     Finishes the stroke. Call this function once when an entire

   216     primitive has been stroked.

   217 */

   218 void QStrokerOps::end()

   219 {

   220     if (m_elements.size() > 1)

   221         processCurrentSubpath();

   222     m_customData = 0;

   223 }

   224 

   225 /*!

   226     Convenience function that decomposes \a path into begin(),

   227     moveTo(), lineTo(), curevTo() and end() calls.

   228 

   229     The \a customData parameter is used in the callback functions

   230 

   231     The \a matrix is used to transform the points before input to the

   232     stroker.

   233 

   234     \sa begin()

   235 */

   236 void QStrokerOps::strokePath(const QPainterPath &path, void *customData, const QTransform &matrix)

   237 {

   238     if (path.isEmpty())

   239         return;

   240 

   241     begin(customData);

   242     int count = path.elementCount();

   243     if (matrix.isIdentity()) {

   244         for (int i=0; i<count; ++i) {

   245             const QPainterPath::Element &e = path.elementAt(i);

   246             switch (e.type) {

   247             case QPainterPath::MoveToElement:

   248                 moveTo(qt_real_to_fixed(e.x), qt_real_to_fixed(e.y));

   249                 break;

   250             case QPainterPath::LineToElement:

   251                 lineTo(qt_real_to_fixed(e.x), qt_real_to_fixed(e.y));

   252                 break;

   253             case QPainterPath::CurveToElement:

   254                 {

   255                     const QPainterPath::Element &cp2 = path.elementAt(++i);

   256                     const QPainterPath::Element &ep = path.elementAt(++i);

   257                     cubicTo(qt_real_to_fixed(e.x), qt_real_to_fixed(e.y),

   258                             qt_real_to_fixed(cp2.x), qt_real_to_fixed(cp2.y),

   259                             qt_real_to_fixed(ep.x), qt_real_to_fixed(ep.y));

   260                 }

   261                 break;

   262             default:

   263                 break;

   264             }

   265         }

   266     } else {

   267         for (int i=0; i<count; ++i) {

   268             const QPainterPath::Element &e = path.elementAt(i);

   269             QPointF pt = QPointF(e.x, e.y) * matrix;

   270             switch (e.type) {

   271             case QPainterPath::MoveToElement:

   272                 moveTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()));

   273                 break;

   274             case QPainterPath::LineToElement:

   275                 lineTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()));

   276                 break;

   277             case QPainterPath::CurveToElement:

   278                 {

   279                     QPointF cp2 = ((QPointF) path.elementAt(++i)) * matrix;

   280                     QPointF ep = ((QPointF) path.elementAt(++i)) * matrix;

   281                     cubicTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()),

   282                             qt_real_to_fixed(cp2.x()), qt_real_to_fixed(cp2.y()),

   283                             qt_real_to_fixed(ep.x()), qt_real_to_fixed(ep.y()));

   284                 }

   285                 break;

   286             default:

   287                 break;

   288             }

   289         }

   290     }

   291     end();

   292 }

   293 

   294 /*!

   295     Convenience function for stroking a polygon of the \a pointCount

   296     first points in \a points. If \a implicit_close is set to true a

   297     line is implictly drawn between the first and last point in the

   298     polygon. Typically true for polygons and false for polylines.

   299 

   300     The \a matrix is used to transform the points before they enter the

   301     stroker.

   302 

   303     \sa begin()

   304 */

   305 

   306 void QStrokerOps::strokePolygon(const QPointF *points, int pointCount, bool implicit_close,

   307                                 void *data, const QTransform &matrix)

   308 {

   309     if (!pointCount)

   310         return;

   311     begin(data);

   312     if (matrix.isIdentity()) {

   313         moveTo(qt_real_to_fixed(points[0].x()), qt_real_to_fixed(points[0].y()));

   314         for (int i=1; i<pointCount; ++i)

   315             lineTo(qt_real_to_fixed(points[i].x()),

   316                    qt_real_to_fixed(points[i].y()));

   317         if (implicit_close)

   318             lineTo(qt_real_to_fixed(points[0].x()), qt_real_to_fixed(points[0].y()));

   319     } else {

   320         QPointF start = points[0] * matrix;

   321         moveTo(qt_real_to_fixed(start.x()), qt_real_to_fixed(start.y()));

   322         for (int i=1; i<pointCount; ++i) {

   323             QPointF pt = points[i] * matrix;

   324             lineTo(qt_real_to_fixed(pt.x()), qt_real_to_fixed(pt.y()));

   325         }

   326         if (implicit_close)

   327             lineTo(qt_real_to_fixed(start.x()), qt_real_to_fixed(start.y()));

   328     }

   329     end();

   330 }

   331 

   332 /*!

   333     Convenience function for stroking an ellipse with bounding rect \a

   334     rect. The \a matrix is used to transform the coordinates before

   335     they enter the stroker.

   336 */

   337 void QStrokerOps::strokeEllipse(const QRectF &rect, void *data, const QTransform &matrix)

   338 {

   339     int count = 0;

   340     QPointF pts[12];

   341     QPointF start = qt_curves_for_arc(rect, 0, -360, pts, &count);

   342     Q_ASSERT(count == 12); // a perfect circle..

   343 

   344     if (!matrix.isIdentity()) {

   345         start = start * matrix;

   346         for (int i=0; i<12; ++i) {

   347             pts[i] = pts[i] * matrix;

   348         }

   349     }

   350 

   351     begin(data);

   352     moveTo(qt_real_to_fixed(start.x()), qt_real_to_fixed(start.y()));

   353     for (int i=0; i<12; i+=3) {

   354         cubicTo(qt_real_to_fixed(pts[i].x()), qt_real_to_fixed(pts[i].y()),

   355                 qt_real_to_fixed(pts[i+1].x()), qt_real_to_fixed(pts[i+1].y()),

   356                 qt_real_to_fixed(pts[i+2].x()), qt_real_to_fixed(pts[i+2].y()));

   357     }

   358     end();

   359 }

   360 

   361 

   362 QStroker::QStroker()

   363     : m_capStyle(SquareJoin), m_joinStyle(FlatJoin),

   364       m_back1X(0), m_back1Y(0),

   365       m_back2X(0), m_back2Y(0)

   366 {

   367     m_strokeWidth = qt_real_to_fixed(1);

   368     m_miterLimit = qt_real_to_fixed(2);

   369     m_curveThreshold = qt_real_to_fixed(0.25);

   370 }

   371 

   372 QStroker::~QStroker()

   373 {

   374 

   375 }

   376 

   377 Qt::PenCapStyle QStroker::capForJoinMode(LineJoinMode mode)

   378 {

   379     if (mode == FlatJoin) return Qt::FlatCap;

   380     else if (mode == SquareJoin) return Qt::SquareCap;

   381     else return Qt::RoundCap;

   382 }

   383 

   384 QStroker::LineJoinMode QStroker::joinModeForCap(Qt::PenCapStyle style)

   385 {

   386     if (style == Qt::FlatCap) return FlatJoin;

   387     else if (style == Qt::SquareCap) return SquareJoin;

   388     else return RoundCap;

   389 }

   390 

   391 Qt::PenJoinStyle QStroker::joinForJoinMode(LineJoinMode mode)

   392 {

   393     if (mode == FlatJoin) return Qt::BevelJoin;

   394     else if (mode == MiterJoin) return Qt::MiterJoin;

   395     else if (mode == SvgMiterJoin) return Qt::SvgMiterJoin;

   396     else return Qt::RoundJoin;

   397 }

   398 

   399 QStroker::LineJoinMode QStroker::joinModeForJoin(Qt::PenJoinStyle joinStyle)

   400 {

   401     if (joinStyle == Qt::BevelJoin) return FlatJoin;

   402     else if (joinStyle == Qt::MiterJoin) return MiterJoin;

   403     else if (joinStyle == Qt::SvgMiterJoin) return SvgMiterJoin;

   404     else return RoundJoin;

   405 }

   406 

   407 

   408 /*!

   409     This function is called to stroke the currently built up

   410     subpath. The subpath is cleared when the function completes.

   411 */

   412 void QStroker::processCurrentSubpath()

   413 {

   414     Q_ASSERT(!m_elements.isEmpty());

   415     Q_ASSERT(m_elements.first().type == QPainterPath::MoveToElement);

   416     Q_ASSERT(m_elements.size() > 1);

   417 

   418     QSubpathForwardIterator fwit(&m_elements);

   419     QSubpathBackwardIterator bwit(&m_elements);

   420 

   421     QLineF fwStartTangent, bwStartTangent;

   422 

   423     bool fwclosed = qt_stroke_side(&fwit, this, false, &fwStartTangent);

   424     bool bwclosed = qt_stroke_side(&bwit, this, !fwclosed, &bwStartTangent);

   425 

   426     if (!bwclosed)

   427         joinPoints(m_elements.at(0).x, m_elements.at(0).y, fwStartTangent, m_capStyle);

   428 }

   429 

   430 

   431 /*!

   432     \internal

   433 */

   434 void QStroker::joinPoints(qfixed focal_x, qfixed focal_y, const QLineF &nextLine, LineJoinMode join)

   435 {

   436 #ifdef QPP_STROKE_DEBUG

   437     printf(" -----> joinPoints: around=(%.0f, %.0f), next_p1=(%.0f, %.f) next_p2=(%.0f, %.f)\n",

   438            qt_fixed_to_real(focal_x),

   439            qt_fixed_to_real(focal_y),

   440            nextLine.x1(), nextLine.y1(), nextLine.x2(), nextLine.y2());

   441 #endif

   442     // points connected already, don't join

   443 

   444 #if !defined (QFIXED_26_6) && !defined (Q_FIXED_32_32)

   445     if (qFuzzyCompare(m_back1X, nextLine.x1()) && qFuzzyCompare(m_back1Y, nextLine.y1()))

   446         return;

   447 #else

   448     if (m_back1X == qt_real_to_fixed(nextLine.x1())

   449         && m_back1Y == qt_real_to_fixed(nextLine.y1())) {

   450         return;

   451     }

   452 #endif

   453 

   454     if (join == FlatJoin) {

   455         emitLineTo(qt_real_to_fixed(nextLine.x1()),

   456                    qt_real_to_fixed(nextLine.y1()));

   457 

   458     } else {

   459         QLineF prevLine(qt_fixed_to_real(m_back2X), qt_fixed_to_real(m_back2Y),

   460                         qt_fixed_to_real(m_back1X), qt_fixed_to_real(m_back1Y));

   461 

   462         QPointF isect;

   463         QLineF::IntersectType type = prevLine.intersect(nextLine, &isect);

   464 

   465         if (join == MiterJoin) {

   466             qreal appliedMiterLimit = qt_fixed_to_real(m_strokeWidth * m_miterLimit);

   467 

   468             // If we are on the inside, do the short cut...

   469             QLineF shortCut(prevLine.p2(), nextLine.p1());

   470             qreal angle = shortCut.angleTo(prevLine);

   471 

   472             if (type == QLineF::BoundedIntersection || (angle > 90 && !qFuzzyCompare(angle, (qreal)90))) {

   473                 emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

   474                 return;

   475             }

   476             QLineF miterLine(QPointF(qt_fixed_to_real(m_back1X),

   477                                      qt_fixed_to_real(m_back1Y)), isect);

   478             if (type == QLineF::NoIntersection || miterLine.length() > appliedMiterLimit) {

   479                 QLineF l1(prevLine);

   480                 l1.setLength(appliedMiterLimit);

   481                 l1.translate(prevLine.dx(), prevLine.dy());

   482 

   483                 QLineF l2(nextLine);

   484                 l2.setLength(appliedMiterLimit);

   485                 l2.translate(-l2.dx(), -l2.dy());

   486 

   487                 emitLineTo(qt_real_to_fixed(l1.x2()), qt_real_to_fixed(l1.y2()));

   488                 emitLineTo(qt_real_to_fixed(l2.x1()), qt_real_to_fixed(l2.y1()));

   489                 emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

   490             } else {

   491                 emitLineTo(qt_real_to_fixed(isect.x()), qt_real_to_fixed(isect.y()));

   492                 emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

   493             }

   494 

   495         } else if (join == SquareJoin) {

   496             qfixed offset = m_strokeWidth / 2;

   497 

   498             QLineF l1(prevLine);

   499             l1.translate(l1.dx(), l1.dy());

   500             l1.setLength(qt_fixed_to_real(offset));

   501             QLineF l2(nextLine.p2(), nextLine.p1());

   502             l2.translate(l2.dx(), l2.dy());

   503             l2.setLength(qt_fixed_to_real(offset));

   504             emitLineTo(qt_real_to_fixed(l1.x2()), qt_real_to_fixed(l1.y2()));

   505             emitLineTo(qt_real_to_fixed(l2.x2()), qt_real_to_fixed(l2.y2()));

   506             emitLineTo(qt_real_to_fixed(l2.x1()), qt_real_to_fixed(l2.y1()));

   507 

   508         } else if (join == RoundJoin) {

   509             qfixed offset = m_strokeWidth / 2;

   510 

   511             QLineF shortCut(prevLine.p2(), nextLine.p1());

   512             qreal angle = prevLine.angle(shortCut);

   513             if (type == QLineF::BoundedIntersection || (angle > 90 && !qFuzzyCompare(angle, (qreal)90))) {

   514                 emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

   515                 return;

   516             }

   517             qreal l1_on_x = adapted_angle_on_x(prevLine);

   518             qreal l2_on_x = adapted_angle_on_x(nextLine);

   519 

   520             qreal sweepLength = qAbs(l2_on_x - l1_on_x);

   521 

   522             int point_count;

   523             QPointF curves[15];

   524 

   525             QPointF curve_start =

   526                 qt_curves_for_arc(QRectF(qt_fixed_to_real(focal_x - offset),

   527                                          qt_fixed_to_real(focal_y - offset),

   528                                          qt_fixed_to_real(offset * 2),

   529                                          qt_fixed_to_real(offset * 2)),

   530                                   l1_on_x + 90, -sweepLength,

   531                                   curves, &point_count);

   532 

   533 //             // line to the beginning of the arc segment, (should not be needed).

   534 //             emitLineTo(qt_real_to_fixed(curve_start.x()), qt_real_to_fixed(curve_start.y()));

   535 

   536             for (int i=0; i<point_count; i+=3) {

   537                 emitCubicTo(qt_real_to_fixed(curves[i].x()),

   538                             qt_real_to_fixed(curves[i].y()),

   539                             qt_real_to_fixed(curves[i+1].x()),

   540                             qt_real_to_fixed(curves[i+1].y()),

   541                             qt_real_to_fixed(curves[i+2].x()),

   542                             qt_real_to_fixed(curves[i+2].y()));

   543             }

   544 

   545             // line to the end of the arc segment, (should also not be needed).

   546             emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

   547 

   548         // Same as round join except we know its 180 degrees. Can also optimize this

   549         // later based on the addEllipse logic

   550         } else if (join == RoundCap) {

   551             qfixed offset = m_strokeWidth / 2;

   552 

   553             // first control line

   554             QLineF l1 = prevLine;

   555             l1.translate(l1.dx(), l1.dy());

   556             l1.setLength(QT_PATH_KAPPA * offset);

   557 

   558             // second control line, find through normal between prevLine and focal.

   559             QLineF l2(qt_fixed_to_real(focal_x), qt_fixed_to_real(focal_y),

   560                       prevLine.x2(), prevLine.y2());

   561             l2.translate(-l2.dy(), l2.dx());

   562             l2.setLength(QT_PATH_KAPPA * offset);

   563 

   564             emitCubicTo(qt_real_to_fixed(l1.x2()),

   565                         qt_real_to_fixed(l1.y2()),

   566                         qt_real_to_fixed(l2.x2()),

   567                         qt_real_to_fixed(l2.y2()),

   568                         qt_real_to_fixed(l2.x1()),

   569                         qt_real_to_fixed(l2.y1()));

   570 

   571             // move so that it matches

   572             l2 = QLineF(l2.x1(), l2.y1(), l2.x1()-l2.dx(), l2.y1()-l2.dy());

   573 

   574             // last line is parallel to l1 so just shift it down.

   575             l1.translate(nextLine.x1() - l1.x1(), nextLine.y1() - l1.y1());

   576 

   577             emitCubicTo(qt_real_to_fixed(l2.x2()),

   578                         qt_real_to_fixed(l2.y2()),

   579                         qt_real_to_fixed(l1.x2()),

   580                         qt_real_to_fixed(l1.y2()),

   581                         qt_real_to_fixed(l1.x1()),

   582                         qt_real_to_fixed(l1.y1()));

   583         } else if (join == SvgMiterJoin) {

   584             QLineF miterLine(QPointF(qt_fixed_to_real(focal_x),

   585                                      qt_fixed_to_real(focal_y)), isect);

   586             if (miterLine.length() > qt_fixed_to_real(m_strokeWidth * m_miterLimit) / 2) {

   587                 emitLineTo(qt_real_to_fixed(nextLine.x1()),

   588                            qt_real_to_fixed(nextLine.y1()));

   589             } else {

   590                 emitLineTo(qt_real_to_fixed(isect.x()), qt_real_to_fixed(isect.y()));

   591                 emitLineTo(qt_real_to_fixed(nextLine.x1()), qt_real_to_fixed(nextLine.y1()));

   592             }

   593         } else {

   594             Q_ASSERT(!"QStroker::joinPoints(), bad join style...");

   595         }

   596     }

   597 }

   598 

   599 

   600 /*

   601    Strokes a subpath side using the \a it as source. Results are put into

   602    \a stroke. The function returns true if the subpath side was closed.

   603    If \a capFirst is true, we will use capPoints instead of joinPoints to

   604    connect the first segment, other segments will be joined using joinPoints.

   605    This is to put capping in order...

   606 */

   607 template <class Iterator> bool qt_stroke_side(Iterator *it,

   608                                               QStroker *stroker,

   609                                               bool capFirst,

   610                                               QLineF *startTangent)

   611 {

   612     // Used in CurveToElement section below.

   613     const int MAX_OFFSET = 16;

   614     QBezier offsetCurves[MAX_OFFSET];

   615 

   616     Q_ASSERT(it->hasNext()); // The initaial move to

   617     QStrokerOps::Element first_element = it->next();

   618     Q_ASSERT(first_element.isMoveTo());

   619 

   620     qfixed2d start = first_element;

   621 

   622 #ifdef QPP_STROKE_DEBUG

   623     qDebug(" -> (side) [%.2f, %.2f], startPos=%d",

   624            qt_fixed_to_real(start.x),

   625            qt_fixed_to_real(start.y));

   626 #endif

   627 

   628     qfixed2d prev = start;

   629 

   630     bool first = true;

   631 

   632     qfixed offset = stroker->strokeWidth() / 2;

   633 

   634     while (it->hasNext()) {

   635         QStrokerOps::Element e = it->next();

   636 

   637         // LineToElement

   638         if (e.isLineTo()) {

   639 #ifdef QPP_STROKE_DEBUG

   640             qDebug("\n ---> (side) lineto [%.2f, %.2f]", e.x, e.y);

   641 #endif

   642             QLineF line(qt_fixed_to_real(prev.x), qt_fixed_to_real(prev.y),

   643                         qt_fixed_to_real(e.x), qt_fixed_to_real(e.y));

   644             QLineF normal = line.normalVector();

   645             normal.setLength(offset);

   646             line.translate(normal.dx(), normal.dy());

   647 

   648             // If we are starting a new subpath, move to correct starting point.

   649             if (first) {

   650                 if (capFirst)

   651                     stroker->joinPoints(prev.x, prev.y, line, stroker->capStyleMode());

   652                 else

   653                     stroker->emitMoveTo(qt_real_to_fixed(line.x1()), qt_real_to_fixed(line.y1()));

   654                 *startTangent = line;

   655                 first = false;

   656             } else {

   657                 stroker->joinPoints(prev.x, prev.y, line, stroker->joinStyleMode());

   658             }

   659 

   660             // Add the stroke for this line.

   661             stroker->emitLineTo(qt_real_to_fixed(line.x2()),

   662                                 qt_real_to_fixed(line.y2()));

   663             prev = e;

   664 

   665         // CurveToElement

   666         } else if (e.isCurveTo()) {

   667             QStrokerOps::Element cp2 = it->next(); // control point 2

   668             QStrokerOps::Element ep = it->next();  // end point

   669 

   670 #ifdef QPP_STROKE_DEBUG

   671             qDebug("\n ---> (side) cubicTo [%.2f, %.2f]",

   672                    qt_fixed_to_real(ep.x),

   673                    qt_fixed_to_real(ep.y));

   674 #endif

   675 

   676             QBezier bezier =

   677                 QBezier::fromPoints(QPointF(qt_fixed_to_real(prev.x), qt_fixed_to_real(prev.y)),

   678                                     QPointF(qt_fixed_to_real(e.x), qt_fixed_to_real(e.y)),

   679                                     QPointF(qt_fixed_to_real(cp2.x), qt_fixed_to_real(cp2.y)),

   680                                     QPointF(qt_fixed_to_real(ep.x), qt_fixed_to_real(ep.y)));

   681 

   682             int count = bezier.shifted(offsetCurves,

   683                                        MAX_OFFSET,

   684                                        offset,

   685                                        stroker->curveThreshold());

   686 

   687             if (count) {

   688                 // If we are starting a new subpath, move to correct starting point

   689                 QLineF tangent = bezier.startTangent();

   690                 tangent.translate(offsetCurves[0].pt1() - bezier.pt1());

   691                 if (first) {

   692                     QPointF pt = offsetCurves[0].pt1();

   693                     if (capFirst) {

   694                         stroker->joinPoints(prev.x, prev.y,

   695                                             tangent,

   696                                             stroker->capStyleMode());

   697                     } else {

   698                         stroker->emitMoveTo(qt_real_to_fixed(pt.x()),

   699                                             qt_real_to_fixed(pt.y()));

   700                     }

   701                     *startTangent = tangent;

   702                     first = false;

   703                 } else {

   704                     stroker->joinPoints(prev.x, prev.y,

   705                                         tangent,

   706                                         stroker->joinStyleMode());

   707                 }

   708 

   709                 // Add these beziers

   710                 for (int i=0; i<count; ++i) {

   711                     QPointF cp1 = offsetCurves[i].pt2();

   712                     QPointF cp2 = offsetCurves[i].pt3();

   713                     QPointF ep = offsetCurves[i].pt4();

   714                     stroker->emitCubicTo(qt_real_to_fixed(cp1.x()), qt_real_to_fixed(cp1.y()),

   715                                          qt_real_to_fixed(cp2.x()), qt_real_to_fixed(cp2.y()),

   716                                          qt_real_to_fixed(ep.x()), qt_real_to_fixed(ep.y()));

   717                 }

   718             }

   719 

   720             prev = ep;

   721         }

   722     }

   723 

   724     if (start == prev) {

   725         // closed subpath, join first and last point

   726 #ifdef QPP_STROKE_DEBUG

   727         qDebug("\n ---> (side) closed subpath");

   728 #endif

   729         stroker->joinPoints(prev.x, prev.y, *startTangent, stroker->joinStyleMode());

   730         return true;

   731     } else {

   732 #ifdef QPP_STROKE_DEBUG

   733         qDebug("\n ---> (side) open subpath");

   734 #endif

   735         return false;

   736     }

   737 }

   738 

   739 /*!

   740     \internal

   741 

   742     For a given angle in the range [0 .. 90], finds the corresponding parameter t

   743     of the prototype cubic bezier arc segment

   744     b = fromPoints(QPointF(1, 0), QPointF(1, KAPPA), QPointF(KAPPA, 1), QPointF(0, 1));

   745 

   746     From the bezier equation:

   747     b.pointAt(t).x() = (1-t)^3 + t*(1-t)^2 + t^2*(1-t)*KAPPA

   748     b.pointAt(t).y() = t*(1-t)^2 * KAPPA + t^2*(1-t) + t^3

   749 

   750     Third degree coefficients:

   751     b.pointAt(t).x() = at^3 + bt^2 + ct + d

   752     where a = 2-3*KAPPA, b = 3*(KAPPA-1), c = 0, d = 1

   753 

   754     b.pointAt(t).y() = at^3 + bt^2 + ct + d

   755     where a = 3*KAPPA-2, b = 6*KAPPA+3, c = 3*KAPPA, d = 0

   756 

   757     Newton's method to find the zero of a function:

   758     given a function f(x) and initial guess x_0

   759     x_1 = f(x_0) / f'(x_0)

   760     x_2 = f(x_1) / f'(x_1)

   761     etc...

   762 */

   763 

   764 qreal qt_t_for_arc_angle(qreal angle)

   765 {

   766     if (qFuzzyIsNull(angle))

   767         return 0;

   768 

   769     if (qFuzzyCompare(angle, qreal(90)))

   770         return 1;

   771 

   772     qreal radians = Q_PI * angle / 180;

   773     qreal cosAngle = qCos(radians);

   774     qreal sinAngle = qSin(radians);

   775 

   776     // initial guess

   777     qreal tc = angle / 90;

   778     // do some iterations of newton's method to approximate cosAngle

   779     // finds the zero of the function b.pointAt(tc).x() - cosAngle

   780     tc -= ((((2-3*QT_PATH_KAPPA) * tc + 3*(QT_PATH_KAPPA-1)) * tc) * tc + 1 - cosAngle) // value

   781          / (((6-9*QT_PATH_KAPPA) * tc + 6*(QT_PATH_KAPPA-1)) * tc); // derivative

   782     tc -= ((((2-3*QT_PATH_KAPPA) * tc + 3*(QT_PATH_KAPPA-1)) * tc) * tc + 1 - cosAngle) // value

   783          / (((6-9*QT_PATH_KAPPA) * tc + 6*(QT_PATH_KAPPA-1)) * tc); // derivative

   784 

   785     // initial guess

   786     qreal ts = tc;

   787     // do some iterations of newton's method to approximate sinAngle

   788     // finds the zero of the function b.pointAt(tc).y() - sinAngle

   789     ts -= ((((3*QT_PATH_KAPPA-2) * ts -  6*QT_PATH_KAPPA + 3) * ts + 3*QT_PATH_KAPPA) * ts - sinAngle)

   790          / (((9*QT_PATH_KAPPA-6) * ts + 12*QT_PATH_KAPPA - 6) * ts + 3*QT_PATH_KAPPA);

   791     ts -= ((((3*QT_PATH_KAPPA-2) * ts -  6*QT_PATH_KAPPA + 3) * ts + 3*QT_PATH_KAPPA) * ts - sinAngle)

   792          / (((9*QT_PATH_KAPPA-6) * ts + 12*QT_PATH_KAPPA - 6) * ts + 3*QT_PATH_KAPPA);

   793 

   794     // use the average of the t that best approximates cosAngle

   795     // and the t that best approximates sinAngle

   796     qreal t = 0.5 * (tc + ts);

   797 

   798 #if 0

   799     printf("angle: %f, t: %f\n", angle, t);

   800     qreal a, b, c, d;

   801     bezierCoefficients(t, a, b, c, d);

   802     printf("cosAngle: %.10f, value: %.10f\n", cosAngle, a + b + c * QT_PATH_KAPPA);

   803     printf("sinAngle: %.10f, value: %.10f\n", sinAngle, b * QT_PATH_KAPPA + c + d);

   804 #endif

   805 

   806     return t;

   807 }

   808 

   809 void qt_find_ellipse_coords(const QRectF &r, qreal angle, qreal length,

   810                             QPointF* startPoint, QPointF *endPoint);

   811 

   812 /*!

   813     \internal

   814 

   815     Creates a number of curves for a given arc definition. The arc is

   816     defined an arc along the ellipses that fits into \a rect starting

   817     at \a startAngle and an arc length of \a sweepLength.

   818 

   819     The function has three out parameters. The return value is the

   820     starting point of the arc. The \a curves array represents the list

   821     of cubicTo elements up to a maximum of \a point_count. There are of course

   822     3 points pr curve.

   823 */

   824 QPointF qt_curves_for_arc(const QRectF &rect, qreal startAngle, qreal sweepLength,

   825                        QPointF *curves, int *point_count)

   826 {

   827     Q_ASSERT(point_count);

   828     Q_ASSERT(curves);

   829 

   830     *point_count = 0;

   831     if (qt_is_nan(rect.x()) || qt_is_nan(rect.y()) || qt_is_nan(rect.width()) || qt_is_nan(rect.height())

   832         || qt_is_nan(startAngle) || qt_is_nan(sweepLength)) {

   833         qWarning("QPainterPath::arcTo: Adding arc where a parameter is NaN, results are undefined");

   834         return QPointF();

   835     }

   836 

   837     if (rect.isNull()) {

   838         return QPointF();

   839     }

   840 

   841     qreal x = rect.x();

   842     qreal y = rect.y();

   843 

   844     qreal w = rect.width();

   845     qreal w2 = rect.width() / 2;

   846     qreal w2k = w2 * QT_PATH_KAPPA;

   847 

   848     qreal h = rect.height();

   849     qreal h2 = rect.height() / 2;

   850     qreal h2k = h2 * QT_PATH_KAPPA;

   851 

   852     QPointF points[16] =

   853     {

   854         // start point

   855         QPointF(x + w, y + h2),

   856 

   857         // 0 -> 270 degrees

   858         QPointF(x + w, y + h2 + h2k),

   859         QPointF(x + w2 + w2k, y + h),

   860         QPointF(x + w2, y + h),

   861 

   862         // 270 -> 180 degrees

   863         QPointF(x + w2 - w2k, y + h),

   864         QPointF(x, y + h2 + h2k),

   865         QPointF(x, y + h2),

   866 

   867         // 180 -> 90 degrees

   868         QPointF(x, y + h2 - h2k),

   869         QPointF(x + w2 - w2k, y),

   870         QPointF(x + w2, y),

   871 

   872         // 90 -> 0 degrees

   873         QPointF(x + w2 + w2k, y),

   874         QPointF(x + w, y + h2 - h2k),

   875         QPointF(x + w, y + h2)

   876     };

   877 

   878     if (sweepLength > 360) sweepLength = 360;

   879     else if (sweepLength < -360) sweepLength = -360;

   880 

   881     // Special case fast paths

   882     if (startAngle == 0.0) {

   883         if (sweepLength == 360.0) {

   884             for (int i = 11; i >= 0; --i)

   885                 curves[(*point_count)++] = points[i];

   886             return points[12];

   887         } else if (sweepLength == -360.0) {

   888             for (int i = 1; i <= 12; ++i)

   889                 curves[(*point_count)++] = points[i];

   890             return points[0];

   891         }

   892     }

   893 

   894     int startSegment = int(floor(startAngle / 90));

   895     int endSegment = int(floor((startAngle + sweepLength) / 90));

   896 

   897     qreal startT = (startAngle - startSegment * 90) / 90;

   898     qreal endT = (startAngle + sweepLength - endSegment * 90) / 90;

   899 

   900     int delta = sweepLength > 0 ? 1 : -1;

   901     if (delta < 0) {

   902         startT = 1 - startT;

   903         endT = 1 - endT;

   904     }

   905 

   906     // avoid empty start segment

   907     if (qFuzzyIsNull(startT - qreal(1))) {

   908         startT = 0;

   909         startSegment += delta;

   910     }

   911 

   912     // avoid empty end segment

   913     if (qFuzzyIsNull(endT)) {

   914         endT = 1;

   915         endSegment -= delta;

   916     }

   917 

   918     startT = qt_t_for_arc_angle(startT * 90);

   919     endT = qt_t_for_arc_angle(endT * 90);

   920 

   921     const bool splitAtStart = !qFuzzyIsNull(startT);

   922     const bool splitAtEnd = !qFuzzyIsNull(endT - qreal(1));

   923 

   924     const int end = endSegment + delta;

   925 

   926     // empty arc?

   927     if (startSegment == end) {

   928         const int quadrant = 3 - ((startSegment % 4) + 4) % 4;

   929         const int j = 3 * quadrant;

   930         return delta > 0 ? points[j + 3] : points[j];

   931     }

   932 

   933     QPointF startPoint, endPoint;

   934     qt_find_ellipse_coords(rect, startAngle, sweepLength, &startPoint, &endPoint);

   935 

   936     for (int i = startSegment; i != end; i += delta) {

   937         const int quadrant = 3 - ((i % 4) + 4) % 4;

   938         const int j = 3 * quadrant;

   939 

   940         QBezier b;

   941         if (delta > 0)

   942             b = QBezier::fromPoints(points[j + 3], points[j + 2], points[j + 1], points[j]);

   943         else

   944             b = QBezier::fromPoints(points[j], points[j + 1], points[j + 2], points[j + 3]);

   945 

   946         // empty arc?

   947         if (startSegment == endSegment && qFuzzyCompare(startT, endT))

   948             return startPoint;

   949 

   950         if (i == startSegment) {

   951             if (i == endSegment && splitAtEnd)

   952                 b = b.bezierOnInterval(startT, endT);

   953             else if (splitAtStart)

   954                 b = b.bezierOnInterval(startT, 1);

   955         } else if (i == endSegment && splitAtEnd) {

   956             b = b.bezierOnInterval(0, endT);

   957         }

   958 

   959         // push control points

   960         curves[(*point_count)++] = b.pt2();

   961         curves[(*point_count)++] = b.pt3();

   962         curves[(*point_count)++] = b.pt4();

   963     }

   964 

   965     Q_ASSERT(*point_count > 0);

   966     curves[*(point_count)-1] = endPoint;

   967 

   968     return startPoint;

   969 }

   970 

   971 

   972 static inline void qdashstroker_moveTo(qfixed x, qfixed y, void *data) {

   973     ((QStroker *) data)->moveTo(x, y);

   974 }

   975 

   976 static inline void qdashstroker_lineTo(qfixed x, qfixed y, void *data) {

   977     ((QStroker *) data)->lineTo(x, y);

   978 }

   979 

   980 static inline void qdashstroker_cubicTo(qfixed, qfixed, qfixed, qfixed, qfixed, qfixed, void *) {

   981     Q_ASSERT(0);

   982 //     ((QStroker *) data)->cubicTo(c1x, c1y, c2x, c2y, ex, ey);

   983 }

   984 

   985 

   986 /*******************************************************************************

   987  * QDashStroker members

   988  */

   989 QDashStroker::QDashStroker(QStroker *stroker)

   990     : m_stroker(stroker), m_dashOffset(0), m_stroke_width(1), m_miter_limit(1)

   991 {

   992     if (m_stroker) {

   993         setMoveToHook(qdashstroker_moveTo);

   994         setLineToHook(qdashstroker_lineTo);

   995         setCubicToHook(qdashstroker_cubicTo);

   996     }

   997 }

   998 

   999 QVector<qfixed> QDashStroker::patternForStyle(Qt::PenStyle style)

  1000 {

  1001     const qfixed space = 2;

  1002     const qfixed dot = 1;

  1003     const qfixed dash = 4;

  1004 

  1005     QVector<qfixed> pattern;

  1006 

  1007     switch (style) {

  1008     case Qt::DashLine:

  1009         pattern << dash << space;

  1010         break;

  1011     case Qt::DotLine:

  1012         pattern << dot << space;

  1013         break;

  1014     case Qt::DashDotLine:

  1015         pattern << dash << space << dot << space;

  1016         break;

  1017     case Qt::DashDotDotLine:

  1018         pattern << dash << space << dot << space << dot << space;

  1019         break;

  1020     default:

  1021         break;

  1022     }

  1023 

  1024     return pattern;

  1025 }

  1026 

  1027 

  1028 void QDashStroker::processCurrentSubpath()

  1029 {

  1030     int dashCount = qMin(m_dashPattern.size(), 32);

  1031     qfixed dashes[32];

  1032 

  1033     if (m_stroker) {

  1034         m_customData = m_stroker;

  1035         m_stroke_width = m_stroker->strokeWidth();

  1036         m_miter_limit = m_stroker->miterLimit();

  1037     }

  1038 

  1039     qreal longestLength = 0;

  1040     qreal sumLength = 0;

  1041     for (int i=0; i<dashCount; ++i) {

  1042         dashes[i] = qMax(m_dashPattern.at(i), qreal(0)) * m_stroke_width;

  1043         sumLength += dashes[i];

  1044         if (dashes[i] > longestLength)

  1045             longestLength = dashes[i];

  1046     }

  1047 

  1048     if (qFuzzyIsNull(sumLength))

  1049         return;

  1050 

  1051     Q_ASSERT(dashCount > 0);

  1052 

  1053     dashCount = (dashCount / 2) * 2; // Round down to even number

  1054 

  1055     int idash = 0; // Index to current dash

  1056     qreal pos = 0; // The position on the curve, 0 <= pos <= path.length

  1057     qreal elen = 0; // element length

  1058     qreal doffset = m_dashOffset * m_stroke_width;

  1059 

  1060     // make sure doffset is in range [0..sumLength)

  1061     doffset -= qFloor(doffset / sumLength) * sumLength;

  1062 

  1063     while (doffset >= dashes[idash]) {

  1064         doffset -= dashes[idash];

  1065         idash = (idash + 1) % dashCount;

  1066     }

  1067 

  1068     qreal estart = 0; // The elements starting position

  1069     qreal estop = 0; // The element stop position

  1070 

  1071     QLineF cline;

  1072 

  1073     QPainterPath dashPath;

  1074 

  1075     QSubpathFlatIterator it(&m_elements);

  1076     qfixed2d prev = it.next();

  1077 

  1078     bool clipping = !m_clip_rect.isEmpty();

  1079     qfixed2d move_to_pos = prev;

  1080     qfixed2d line_to_pos;

  1081 

  1082     // Pad to avoid clipping the borders of thick pens.

  1083     qfixed padding = qt_real_to_fixed(qMax(m_stroke_width, m_miter_limit) * longestLength);

  1084     qfixed2d clip_tl = { qt_real_to_fixed(m_clip_rect.left()) - padding,

  1085                          qt_real_to_fixed(m_clip_rect.top()) - padding };

  1086     qfixed2d clip_br = { qt_real_to_fixed(m_clip_rect.right()) + padding ,

  1087                          qt_real_to_fixed(m_clip_rect.bottom()) + padding };

  1088 

  1089     bool hasMoveTo = false;

  1090     while (it.hasNext()) {

  1091         QStrokerOps::Element e = it.next();

  1092 

  1093         Q_ASSERT(e.isLineTo());

  1094         cline = QLineF(qt_fixed_to_real(prev.x),

  1095                        qt_fixed_to_real(prev.y),

  1096                        qt_fixed_to_real(e.x),

  1097                        qt_fixed_to_real(e.y));

  1098         elen = cline.length();

  1099 

  1100         estop = estart + elen;

  1101 

  1102         bool done = pos >= estop;

  1103         // Dash away...

  1104         while (!done) {

  1105             QPointF p2;

  1106 

  1107             int idash_incr = 0;

  1108             bool has_offset = doffset > 0;

  1109             qreal dpos = pos + dashes[idash] - doffset - estart;

  1110 

  1111             Q_ASSERT(dpos >= 0);

  1112 

  1113             if (dpos > elen) { // dash extends this line

  1114                 doffset = dashes[idash] - (dpos - elen); // subtract the part already used

  1115                 pos = estop; // move pos to next path element

  1116                 done = true;

  1117                 p2 = cline.p2();

  1118             } else { // Dash is on this line

  1119                 p2 = cline.pointAt(dpos/elen);

  1120                 pos = dpos + estart;

  1121                 done = pos >= estop;

  1122                 idash_incr = 1;

  1123                 doffset = 0; // full segment so no offset on next.

  1124             }

  1125 

  1126             if (idash % 2 == 0) {

  1127                 line_to_pos.x = qt_real_to_fixed(p2.x());

  1128                 line_to_pos.y = qt_real_to_fixed(p2.y());

  1129 

  1130                 // If we have an offset, we're continuing a dash

  1131                 // from a previous element and should only

  1132                 // continue the current dash, without starting a

  1133                 // new subpath.

  1134                 if (!has_offset || !hasMoveTo) {