src/gui/painting/qpathclipper_p.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 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 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  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     static bool pathToRect(const QPainterPath &path, QRectF *rect = 0);
  90     static QPainterPath intersect(const QPainterPath &path, const QRectF &rect);
  91
  92 private:
  93     Q_DISABLE_COPY(QPathClipper)
  94
  95     enum ClipperMode {
  96         ClipMode, // do the full clip
  97         CheckMode // for contains/intersects (only interested in whether the result path is non-empty)
  98     };
  99
 100     bool handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode);
 101     bool doClip(QWingedEdge &list, ClipperMode mode);
 102
 103     QPainterPath subjectPath;
 104     QPainterPath clipPath;
 105     Operation op;
 106
 107     int aMask;
 108     int bMask;
 109 };
 110
 111 struct QPathVertex
 112 {
 113 public:
 114     QPathVertex(const QPointF &p = QPointF(), int e = -1);
 115     operator QPointF() const;
 116
 117     int edge;
 118
 119     qreal x;
 120     qreal y;
 121 };
 122
 123 class QPathEdge
 124 {
 125 public:
 126     enum Traversal {
 127         RightTraversal,
 128         LeftTraversal
 129     };
 130
 131     enum Direction {
 132         Forward,
 133         Backward
 134     };
 135
 136     enum Type {
 137         Line,
 138         Curve
 139     };
 140
 141     QPathEdge(int a = -1, int b = -1);
 142
 143     mutable int flag;
 144
 145     int windingA;
 146     int windingB;
 147
 148     int first;
 149     int second;
 150
 151     double angle;
 152     double invAngle;
 153
 154     int next(Traversal traversal, Direction direction) const;
 155
 156     void setNext(Traversal traversal, Direction direction, int next);
 157     void setNext(Direction direction, int next);
 158
 159     Direction directionTo(int vertex) const;
 160     int vertex(Direction direction) const;
 161
 162 private:
 163     int m_next[2][2];
 164 };
 165
 166 class QPathSegments
 167 {
 168 public:
 169     struct Intersection {
 170         int vertex;
 171         qreal t;
 172
 173         int next;
 174
 175         bool operator<(const Intersection &o) const {
 176             return t < o.t;
 177         }
 178     };
 179
 180     struct Segment {
 181         Segment(int pathId, int vertexA, int vertexB)
 182             : path(pathId)
 183             , va(vertexA)
 184             , vb(vertexB)
 185             , intersection(-1)
 186         {
 187         }
 188
 189         int path;
 190
 191         // vertices
 192         int va;
 193         int vb;
 194
 195         // intersection index
 196         int intersection;
 197
 198         QRectF bounds;
 199     };
 200
 201
 202     QPathSegments(int reserve);
 203
 204     void setPath(const QPainterPath &path);
 205     void addPath(const QPainterPath &path);
 206
 207     int intersections() const;
 208     int segments() const;
 209     int points() const;
 210
 211     const Segment &segmentAt(int index) const;
 212     const QLineF lineAt(int index) const;
 213     const QRectF &elementBounds(int index) const;
 214     int pathId(int index) const;
 215
 216     const QPointF &pointAt(int vertex) const;
 217     int addPoint(const QPointF &point);
 218
 219     const Intersection *intersectionAt(int index) const;
 220     void addIntersection(int index, const Intersection &intersection);
 221
 222     void mergePoints();
 223
 224 private:
 225     QDataBuffer<QPointF> m_points;
 226     QDataBuffer<Segment> m_segments;
 227     QDataBuffer<Intersection> m_intersections;
 228
 229     int m_pathId;
 230 };
 231
 232 class Q_AUTOTEST_EXPORT QWingedEdge
 233 {
 234 public:
 235     struct TraversalStatus
 236     {
 237         int edge;
 238         QPathEdge::Traversal traversal;
 239         QPathEdge::Direction direction;
 240
 241         void flipDirection();
 242         void flipTraversal();
 243
 244         void flip();
 245     };
 246
 247     QWingedEdge();
 248     QWingedEdge(const QPainterPath &subject, const QPainterPath &clip);
 249
 250     void simplify();
 251     QPainterPath toPath() const;
 252
 253     int edgeCount() const;
 254
 255     QPathEdge *edge(int edge);
 256     const QPathEdge *edge(int edge) const;
 257
 258     int vertexCount() const;
 259
 260     int addVertex(const QPointF &p);
 261
 262     QPathVertex *vertex(int vertex);
 263     const QPathVertex *vertex(int vertex) const;
 264
 265     TraversalStatus next(const TraversalStatus &status) const;
 266
 267     int addEdge(const QPointF &a, const QPointF &b);
 268     int addEdge(int vertexA, int vertexB);
 269
 270     bool isInside(qreal x, qreal y) const;
 271
 272     static QPathEdge::Traversal flip(QPathEdge::Traversal traversal);
 273     static QPathEdge::Direction flip(QPathEdge::Direction direction);
 274
 275 private:
 276     void intersectAndAdd();
 277
 278     void printNode(int i, FILE *handle);
 279
 280     void removeEdge(int ei);
 281
 282     int insert(const QPathVertex &vertex);
 283     TraversalStatus findInsertStatus(int vertex, int edge) const;
 284
 285     qreal delta(int vertex, int a, int b) const;
 286
 287     QDataBuffer<QPathEdge> m_edges;
 288     QDataBuffer<QPathVertex> m_vertices;
 289
 290     QVector<qreal> m_splitPoints;
 291
 292     QPathSegments m_segments;
 293 };
 294
 295 inline QPathEdge::QPathEdge(int a, int b)
 296     : flag(0)
 297     , windingA(0)
 298     , windingB(0)
 299     , first(a)
 300     , second(b)
 301     , angle(0)
 302     , invAngle(0)
 303 {
 304     m_next[0][0] = -1;
 305     m_next[1][0] = -1;
 306     m_next[0][0] = -1;
 307     m_next[1][0] = -1;
 308 }
 309
 310 inline int QPathEdge::next(Traversal traversal, Direction direction) const
 311 {
 312     return m_next[int(traversal)][int(direction)];
 313 }
 314
 315 inline void QPathEdge::setNext(Traversal traversal, Direction direction, int next)
 316 {
 317     m_next[int(traversal)][int(direction)] = next;
 318 }
 319
 320 inline void QPathEdge::setNext(Direction direction, int next)
 321 {
 322     m_next[0][int(direction)] = next;
 323     m_next[1][int(direction)] = next;
 324 }
 325
 326 inline QPathEdge::Direction QPathEdge::directionTo(int vertex) const
 327 {
 328     return first == vertex ? Backward : Forward;
 329 }
 330
 331 inline int QPathEdge::vertex(Direction direction) const
 332 {
 333     return direction == Backward ? first : second;
 334 }
 335
 336 inline QPathVertex::QPathVertex(const QPointF &p, int e)
 337     : edge(e)
 338     , x(p.x())
 339     , y(p.y())
 340 {
 341 }
 342
 343 inline QPathVertex::operator QPointF() const
 344 {
 345     return QPointF(x, y);
 346 }
 347
 348 inline QPathSegments::QPathSegments(int reserve) :
 349     m_points(reserve),
 350     m_segments(reserve),
 351     m_intersections(reserve)
 352 {
 353 }
 354
 355 inline int QPathSegments::segments() const
 356 {
 357     return m_segments.size();
 358 }
 359
 360 inline int QPathSegments::points() const
 361 {
 362     return m_points.size();
 363 }
 364
 365 inline const QPointF &QPathSegments::pointAt(int i) const
 366 {
 367     return m_points.at(i);
 368 }
 369
 370 inline int QPathSegments::addPoint(const QPointF &point)
 371 {
 372     m_points << point;
 373     return m_points.size() - 1;
 374 }
 375
 376 inline const QPathSegments::Segment &QPathSegments::segmentAt(int index) const
 377 {
 378     return m_segments.at(index);
 379 }
 380
 381 inline const QLineF QPathSegments::lineAt(int index) const
 382 {
 383     const Segment &segment = m_segments.at(index);
 384     return QLineF(m_points.at(segment.va), m_points.at(segment.vb));
 385 }
 386
 387 inline const QRectF &QPathSegments::elementBounds(int index) const
 388 {
 389     return m_segments.at(index).bounds;
 390 }
 391
 392 inline int QPathSegments::pathId(int index) const
 393 {
 394     return m_segments.at(index).path;
 395 }
 396
 397 inline const QPathSegments::Intersection *QPathSegments::intersectionAt(int index) const
 398 {
 399     const int intersection = m_segments.at(index).intersection;
 400     if (intersection < 0)
 401         return 0;
 402     else
 403         return &m_intersections.at(intersection);
 404 }
 405
 406 inline int QPathSegments::intersections() const
 407 {
 408     return m_intersections.size();
 409 }
 410
 411 inline void QPathSegments::addIntersection(int index, const Intersection &intersection)
 412 {
 413     m_intersections << intersection;
 414
 415     Segment &segment = m_segments.at(index);
 416     if (segment.intersection < 0) {
 417         segment.intersection = m_intersections.size() - 1;
 418     } else {
 419         Intersection *isect = &m_intersections.at(segment.intersection);
 420
 421         while (isect->next != 0)
 422             isect += isect->next;
 423
 424         isect->next = (m_intersections.size() - 1) - (isect - m_intersections.data());
 425     }
 426 }
 427
 428 inline void QWingedEdge::TraversalStatus::flipDirection()
 429 {
 430     direction = QWingedEdge::flip(direction);
 431 }
 432
 433 inline void QWingedEdge::TraversalStatus::flipTraversal()
 434 {
 435     traversal = QWingedEdge::flip(traversal);
 436 }
 437
 438 inline void QWingedEdge::TraversalStatus::flip()
 439 {
 440     flipDirection();
 441     flipTraversal();
 442 }
 443
 444 inline int QWingedEdge::edgeCount() const
 445 {
 446     return m_edges.size();
 447 }
 448
 449 inline QPathEdge *QWingedEdge::edge(int edge)
 450 {
 451     return edge < 0 ? 0 : &m_edges.at(edge);
 452 }
 453
 454 inline const QPathEdge *QWingedEdge::edge(int edge) const
 455 {
 456     return edge < 0 ? 0 : &m_edges.at(edge);
 457 }
 458
 459 inline int QWingedEdge::vertexCount() const
 460 {
 461     return m_vertices.size();
 462 }
 463
 464 inline int QWingedEdge::addVertex(const QPointF &p)
 465 {
 466     m_vertices << p;
 467     return m_vertices.size() - 1;
 468 }
 469
 470 inline QPathVertex *QWingedEdge::vertex(int vertex)
 471 {
 472     return vertex < 0 ? 0 : &m_vertices.at(vertex);
 473 }
 474
 475 inline const QPathVertex *QWingedEdge::vertex(int vertex) const
 476 {
 477     return vertex < 0 ? 0 : &m_vertices.at(vertex);
 478 }
 479
 480 inline QPathEdge::Traversal QWingedEdge::flip(QPathEdge::Traversal traversal)
 481 {
 482     return traversal == QPathEdge::RightTraversal ? QPathEdge::LeftTraversal : QPathEdge::RightTraversal;
 483 }
 484
 485 inline QPathEdge::Direction QWingedEdge::flip(QPathEdge::Direction direction)
 486 {
 487     return direction == QPathEdge::Forward ? QPathEdge::Backward : QPathEdge::Forward;
 488 }
 489
 490 QT_END_NAMESPACE
 491
 492 QT_END_HEADER
 493
 494 #endif // QPATHCLIPPER_P_H