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 #ifndef QPATHCLIPPER_P_H

    43 #define QPATHCLIPPER_P_H

    44 

    45 //

    46 //  W A R N I N G

    47 //  -------------

    48 //

    49 // This file is not part of the Qt API.  It exists purely as an

    50 // implementation detail.  This header file may change from version to

    51 // version without notice, or even be removed.

    52 //

    53 // We mean it.

    54 //

    55 

    56 #include <QtGui/qpainterpath.h>

    57 #include <QtCore/qlist.h>

    58 

    59 #include <private/qbezier_p.h>

    60 #include <private/qdatabuffer_p.h>

    61 #include <stdio.h>

    62 

    63 QT_BEGIN_HEADER

    64 

    65 QT_BEGIN_NAMESPACE

    66 

    67 QT_MODULE(Gui)

    68 

    69 class QWingedEdge;

    70 

    71 class Q_AUTOTEST_EXPORT QPathClipper

    72 {

    73 public:

    74     enum Operation {

    75         BoolAnd,

    76         BoolOr,

    77         BoolSub,

    78         Simplify

    79     };

    80 public:

    81     QPathClipper(const QPainterPath &subject,

    82                  const QPainterPath &clip);

    83 

    84     QPainterPath clip(Operation op = BoolAnd);

    85 

    86     bool intersect();

    87     bool contains();

    88 

    89 private:

    90     Q_DISABLE_COPY(QPathClipper)

    91 

    92     enum ClipperMode {

    93         ClipMode, // do the full clip

    94         CheckMode // for contains/intersects (only interested in whether the result path is non-empty)

    95     };

    96 

    97     bool handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode);

    98     bool doClip(QWingedEdge &list, ClipperMode mode);

    99 

   100     QPainterPath subjectPath;

   101     QPainterPath clipPath;

   102     Operation op;

   103 

   104     int aMask;

   105     int bMask;

   106 };

   107 

   108 struct QPathVertex

   109 {

   110 public:

   111     QPathVertex(const QPointF &p = QPointF(), int e = -1);

   112     operator QPointF() const;

   113 

   114     int edge;

   115 

   116     qreal x;

   117     qreal y;

   118 };

   119 

   120 class QPathEdge

   121 {

   122 public:

   123     enum Traversal {

   124         RightTraversal,

   125         LeftTraversal

   126     };

   127 

   128     enum Direction {

   129         Forward,

   130         Backward

   131     };

   132 

   133     enum Type {

   134         Line,

   135         Curve

   136     };

   137 

   138     QPathEdge(int a = -1, int b = -1);

   139 

   140     mutable int flag;

   141 

   142     int windingA;

   143     int windingB;

   144 

   145     int first;

   146     int second;

   147 

   148     qreal angle;

   149     qreal invAngle;

   150 

   151     const QBezier *bezier;

   152     qreal t0;

   153     qreal t1;

   154 

   155     int next(Traversal traversal, Direction direction) const;

   156 

   157     void setNext(Traversal traversal, Direction direction, int next);

   158     void setNext(Direction direction, int next);

   159 

   160     Direction directionTo(int vertex) const;

   161     int vertex(Direction direction) const;

   162 

   163 private:

   164     int m_next[2][2];

   165 };

   166 

   167 class QPathSegments

   168 {

   169 public:

   170     struct Intersection {

   171         int vertex;

   172         qreal t;

   173 

   174         int next;

   175 

   176         bool operator<(const Intersection &o) const {

   177             return t < o.t;

   178         }

   179     };

   180 

   181     struct Segment {

   182         Segment(int pathId, int vertexA, int vertexB, int bezierIndex = -1)

   183             : path(pathId)

   184             , bezier(bezierIndex)

   185             , va(vertexA)

   186             , vb(vertexB)

   187             , intersection(-1)

   188         {

   189         }

   190 

   191         int path;

   192         int bezier;

   193 

   194         // vertices

   195         int va;

   196         int vb;

   197 

   198         // intersection index

   199         int intersection;

   200 

   201         QRectF bounds;

   202     };

   203 

   204 

   205     QPathSegments();

   206 

   207     void setPath(const QPainterPath &path);

   208     void addPath(const QPainterPath &path);

   209 

   210     int intersections() const;

   211     int segments() const;

   212     int points() const;

   213 

   214     const Segment &segmentAt(int index) const;

   215     const QLineF lineAt(int index) const;

   216     const QBezier *bezierAt(int index) const;

   217     const QRectF &elementBounds(int index) const;

   218     int pathId(int index) const;

   219 

   220     const QPointF &pointAt(int vertex) const;

   221     int addPoint(const QPointF &point);

   222 

   223     const Intersection *intersectionAt(int index) const;

   224     void addIntersection(int index, const Intersection &intersection);

   225 

   226     void mergePoints();

   227 

   228 private:

   229     QDataBuffer<QPointF> m_points;

   230     QDataBuffer<Segment> m_segments;

   231     QDataBuffer<QBezier> m_beziers;

   232     QDataBuffer<Intersection> m_intersections;

   233 

   234     int m_pathId;

   235 };

   236 

   237 class Q_AUTOTEST_EXPORT QWingedEdge

   238 {

   239 public:

   240     struct TraversalStatus

   241     {

   242         int edge;

   243         QPathEdge::Traversal traversal;

   244         QPathEdge::Direction direction;

   245 

   246         void flipDirection();

   247         void flipTraversal();

   248 

   249         void flip();

   250     };

   251 

   252     QWingedEdge();

   253     QWingedEdge(const QPainterPath &subject, const QPainterPath &clip);

   254 

   255     void simplify();

   256     QPainterPath toPath() const;

   257 

   258     int edgeCount() const;

   259 

   260     QPathEdge *edge(int edge);

   261     const QPathEdge *edge(int edge) const;

   262 

   263     int vertexCount() const;

   264 

   265     int addVertex(const QPointF &p);

   266 

   267     QPathVertex *vertex(int vertex);

   268     const QPathVertex *vertex(int vertex) const;

   269 

   270     TraversalStatus next(const TraversalStatus &status) const;

   271 

   272     int addEdge(const QPointF &a, const QPointF &b, const QBezier *bezier = 0, qreal t0 = 0, qreal t1 = 1);

   273     int addEdge(int vertexA, int vertexB, const QBezier *bezier = 0, qreal t0 = 0, qreal t1 = 1);

   274 

   275     bool isInside(qreal x, qreal y) const;

   276 

   277     static QPathEdge::Traversal flip(QPathEdge::Traversal traversal);

   278     static QPathEdge::Direction flip(QPathEdge::Direction direction);

   279 

   280 private:

   281     void intersectAndAdd();

   282 

   283     void printNode(int i, FILE *handle);

   284 

   285     QBezier bezierFromIndex(int index) const;

   286 

   287     void removeEdge(int ei);

   288     void addBezierEdge(const QBezier *bezier, const QPointF &a, const QPointF &b, qreal alphaA, qreal alphaB, int path);

   289     void addBezierEdge(const QBezier *bezier, int vertexA, int vertexB, qreal alphaA, qreal alphaB, int path);

   290 

   291     int insert(const QPathVertex &vertex);

   292     TraversalStatus findInsertStatus(int vertex, int edge) const;

   293 

   294     qreal delta(int vertex, int a, int b) const;

   295 

   296     QDataBuffer<QPathEdge> m_edges;

   297     QDataBuffer<QPathVertex> m_vertices;

   298 

   299     QVector<qreal> m_splitPoints;

   300 

   301     QPathSegments m_segments;

   302 };

   303 

   304 inline QPathEdge::QPathEdge(int a, int b)

   305     : flag(0)

   306     , windingA(0)

   307     , windingB(0)

   308     , first(a)

   309     , second(b)

   310     , angle(0)

   311     , invAngle(0)

   312     , bezier(0)

   313     , t0(0)

   314     , t1(0)

   315 {

   316     m_next[0][0] = -1;

   317     m_next[1][0] = -1;

   318     m_next[0][0] = -1;

   319     m_next[1][0] = -1;

   320 }

   321 

   322 inline int QPathEdge::next(Traversal traversal, Direction direction) const

   323 {

   324     return m_next[int(traversal)][int(direction)];

   325 }

   326 

   327 inline void QPathEdge::setNext(Traversal traversal, Direction direction, int next)

   328 {

   329     m_next[int(traversal)][int(direction)] = next;

   330 }

   331 

   332 inline void QPathEdge::setNext(Direction direction, int next)

   333 {

   334     m_next[0][int(direction)] = next;

   335     m_next[1][int(direction)] = next;

   336 }

   337 

   338 inline QPathEdge::Direction QPathEdge::directionTo(int vertex) const

   339 {

   340     return first == vertex ? Backward : Forward;

   341 }

   342 

   343 inline int QPathEdge::vertex(Direction direction) const

   344 {

   345     return direction == Backward ? first : second;

   346 }

   347 

   348 inline QPathVertex::QPathVertex(const QPointF &p, int e)

   349     : edge(e)

   350     , x(p.x())

   351     , y(p.y())

   352 {

   353 }

   354 

   355 inline QPathVertex::operator QPointF() const

   356 {

   357     return QPointF(x, y);

   358 }

   359 

   360 inline QPathSegments::QPathSegments()

   361 {

   362 }

   363 

   364 inline int QPathSegments::segments() const

   365 {

   366     return m_segments.size();

   367 }

   368 

   369 inline int QPathSegments::points() const

   370 {

   371     return m_points.size();

   372 }

   373 

   374 inline const QPointF &QPathSegments::pointAt(int i) const

   375 {

   376     return m_points.at(i);

   377 }

   378 

   379 inline int QPathSegments::addPoint(const QPointF &point)

   380 {

   381     m_points << point;

   382     return m_points.size() - 1;

   383 }

   384 

   385 inline const QPathSegments::Segment &QPathSegments::segmentAt(int index) const

   386 {

   387     return m_segments.at(index);

   388 }

   389 

   390 inline const QLineF QPathSegments::lineAt(int index) const

   391 {

   392     const Segment &segment = m_segments.at(index);

   393     return QLineF(m_points.at(segment.va), m_points.at(segment.vb));

   394 }

   395 

   396 inline const QBezier *QPathSegments::bezierAt(int index) const

   397 {

   398     const Segment &segment = m_segments.at(index);

   399     if (segment.bezier >= 0)

   400         return &m_beziers.at(segment.bezier);

   401     else

   402         return 0;

   403 }

   404 

   405 inline const QRectF &QPathSegments::elementBounds(int index) const

   406 {

   407     return m_segments.at(index).bounds;

   408 }

   409 

   410 inline int QPathSegments::pathId(int index) const

   411 {

   412     return m_segments.at(index).path;

   413 }

   414 

   415 inline const QPathSegments::Intersection *QPathSegments::intersectionAt(int index) const

   416 {

   417     const int intersection = m_segments.at(index).intersection;

   418     if (intersection < 0)

   419         return 0;

   420     else

   421         return &m_intersections.at(intersection);

   422 }

   423 

   424 inline int QPathSegments::intersections() const

   425 {

   426     return m_intersections.size();

   427 }

   428 

   429 inline void QPathSegments::addIntersection(int index, const Intersection &intersection)

   430 {

   431     m_intersections << intersection;

   432 

   433     Segment &segment = m_segments.at(index);

   434     if (segment.intersection < 0) {

   435         segment.intersection = m_intersections.size() - 1;

   436     } else {

   437         Intersection *isect = &m_intersections.at(segment.intersection);

   438 

   439         while (isect->next != 0)

   440             isect += isect->next;

   441 

   442         isect->next = (m_intersections.size() - 1) - (isect - m_intersections.data());

   443     }

   444 }

   445 

   446 inline void QWingedEdge::TraversalStatus::flipDirection()

   447 {

   448     direction = QWingedEdge::flip(direction);

   449 }

   450 

   451 inline void QWingedEdge::TraversalStatus::flipTraversal()

   452 {

   453     traversal = QWingedEdge::flip(traversal);

   454 }

   455 

   456 inline void QWingedEdge::TraversalStatus::flip()

   457 {

   458     flipDirection();

   459     flipTraversal();

   460 }

   461 

   462 inline int QWingedEdge::edgeCount() const

   463 {

   464     return m_edges.size();

   465 }

   466 

   467 inline QPathEdge *QWingedEdge::edge(int edge)

   468 {

   469     return edge < 0 ? 0 : &m_edges.at(edge);

   470 }

   471 

   472 inline const QPathEdge *QWingedEdge::edge(int edge) const

   473 {

   474     return edge < 0 ? 0 : &m_edges.at(edge);

   475 }

   476 

   477 inline int QWingedEdge::vertexCount() const

   478 {

   479     return m_vertices.size();

   480 }

   481 

   482 inline int QWingedEdge::addVertex(const QPointF &p)

   483 {

   484     m_vertices << p;

   485     return m_vertices.size() - 1;

   486 }

   487 

   488 inline QPathVertex *QWingedEdge::vertex(int vertex)

   489 {

   490     return vertex < 0 ? 0 : &m_vertices.at(vertex);

   491 }

   492 

   493 inline const QPathVertex *QWingedEdge::vertex(int vertex) const

   494 {

   495     return vertex < 0 ? 0 : &m_vertices.at(vertex);

   496 }

   497 

   498 inline QPathEdge::Traversal QWingedEdge::flip(QPathEdge::Traversal traversal)

   499 {

   500     return traversal == QPathEdge::RightTraversal ? QPathEdge::LeftTraversal : QPathEdge::RightTraversal;

   501 }

   502 

   503 inline QPathEdge::Direction QWingedEdge::flip(QPathEdge::Direction direction)

   504 {

   505     return direction == QPathEdge::Forward ? QPathEdge::Backward : QPathEdge::Forward;

   506 }

   507 

   508 QT_END_NAMESPACE

   509 

   510 QT_END_HEADER

   511 

   512 #endif // QPATHCLIPPER_P_H