1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtGui module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifndef QPATHCLIPPER_P_H
41#define QPATHCLIPPER_P_H
42
43//
44// W A R N I N G
45// -------------
46//
47// This file is not part of the Qt API. It exists purely as an
48// implementation detail. This header file may change from version to
49// version without notice, or even be removed.
50//
51// We mean it.
52//
53
54#include <QtGui/private/qtguiglobal_p.h>
55#include <QtGui/qpainterpath.h>
56#include <QtCore/qlist.h>
57
58#include <private/qbezier_p.h>
59#include <private/qdatabuffer_p.h>
60#include <stdio.h>
61
62QT_BEGIN_NAMESPACE
63
64
65class QWingedEdge;
66
67class Q_GUI_EXPORT QPathClipper
68{
69public:
70 enum Operation {
71 BoolAnd,
72 BoolOr,
73 BoolSub,
74 Simplify
75 };
76public:
77 QPathClipper(const QPainterPath &subject,
78 const QPainterPath &clip);
79
80 QPainterPath clip(Operation op = BoolAnd);
81
82 bool intersect();
83 bool contains();
84
85 static bool pathToRect(const QPainterPath &path, QRectF *rect = nullptr);
86 static QPainterPath intersect(const QPainterPath &path, const QRectF &rect);
87
88private:
89 Q_DISABLE_COPY_MOVE(QPathClipper)
90
91 enum ClipperMode {
92 ClipMode, // do the full clip
93 CheckMode // for contains/intersects (only interested in whether the result path is non-empty)
94 };
95
96 bool handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode);
97 bool doClip(QWingedEdge &list, ClipperMode mode);
98
99 QPainterPath subjectPath;
100 QPainterPath clipPath;
101 Operation op;
102
103 int aMask;
104 int bMask;
105};
106
107struct QPathVertex
108{
109public:
110 QPathVertex(const QPointF &p = QPointF(), int e = -1);
111 operator QPointF() const;
112
113 int edge;
114
115 qreal x;
116 qreal y;
117};
118
119class QPathEdge
120{
121public:
122 enum Traversal {
123 RightTraversal,
124 LeftTraversal
125 };
126
127 enum Direction {
128 Forward,
129 Backward
130 };
131
132 enum Type {
133 Line,
134 Curve
135 };
136
137 explicit QPathEdge(int a = -1, int b = -1);
138
139 mutable int flag;
140
141 int windingA;
142 int windingB;
143
144 int first;
145 int second;
146
147 double angle;
148 double invAngle;
149
150 int next(Traversal traversal, Direction direction) const;
151
152 void setNext(Traversal traversal, Direction direction, int next);
153 void setNext(Direction direction, int next);
154
155 Direction directionTo(int vertex) const;
156 int vertex(Direction direction) const;
157
158private:
159 int m_next[2][2] = { { -1, -1 }, { -1, -1 } };
160};
161
162class QPathSegments
163{
164public:
165 struct Intersection {
166 qreal t;
167 int vertex;
168 int next;
169
170 bool operator<(const Intersection &o) const {
171 return t < o.t;
172 }
173 };
174
175 struct Segment {
176 Segment(int pathId, int vertexA, int vertexB)
177 : path(pathId)
178 , va(vertexA)
179 , vb(vertexB)
180 , intersection(-1)
181 {
182 }
183
184 int path;
185
186 // vertices
187 int va;
188 int vb;
189
190 // intersection index
191 int intersection;
192
193 QRectF bounds;
194 };
195
196
197 QPathSegments(int reserve);
198
199 void setPath(const QPainterPath &path);
200 void addPath(const QPainterPath &path);
201
202 int intersections() const;
203 int segments() const;
204 int points() const;
205
206 const Segment &segmentAt(int index) const;
207 const QLineF lineAt(int index) const;
208 const QRectF &elementBounds(int index) const;
209 int pathId(int index) const;
210
211 const QPointF &pointAt(int vertex) const;
212 int addPoint(const QPointF &point);
213
214 const Intersection *intersectionAt(int index) const;
215 void addIntersection(int index, const Intersection &intersection);
216
217 void mergePoints();
218
219private:
220 QDataBuffer<QPointF> m_points;
221 QDataBuffer<Segment> m_segments;
222 QDataBuffer<Intersection> m_intersections;
223
224 int m_pathId;
225};
226
227class Q_AUTOTEST_EXPORT QWingedEdge
228{
229public:
230 struct TraversalStatus
231 {
232 int edge;
233 QPathEdge::Traversal traversal;
234 QPathEdge::Direction direction;
235
236 void flipDirection();
237 void flipTraversal();
238
239 void flip();
240 };
241
242 QWingedEdge();
243 QWingedEdge(const QPainterPath &subject, const QPainterPath &clip);
244
245 void simplify();
246 QPainterPath toPath() const;
247
248 int edgeCount() const;
249
250 QPathEdge *edge(int edge);
251 const QPathEdge *edge(int edge) const;
252
253 int vertexCount() const;
254
255 int addVertex(const QPointF &p);
256
257 QPathVertex *vertex(int vertex);
258 const QPathVertex *vertex(int vertex) const;
259
260 TraversalStatus next(const TraversalStatus &status) const;
261
262 int addEdge(const QPointF &a, const QPointF &b);
263 int addEdge(int vertexA, int vertexB);
264
265 bool isInside(qreal x, qreal y) const;
266
267 static QPathEdge::Traversal flip(QPathEdge::Traversal traversal);
268 static QPathEdge::Direction flip(QPathEdge::Direction direction);
269
270private:
271 void intersectAndAdd();
272
273 void printNode(int i, FILE *handle);
274
275 void removeEdge(int ei);
276
277 int insert(const QPathVertex &vertex);
278 TraversalStatus findInsertStatus(int vertex, int edge) const;
279
280 qreal delta(int vertex, int a, int b) const;
281
282 QDataBuffer<QPathEdge> m_edges;
283 QDataBuffer<QPathVertex> m_vertices;
284
285 QVector<qreal> m_splitPoints;
286
287 QPathSegments m_segments;
288};
289
290inline QPathEdge::QPathEdge(int a, int b)
291 : flag(0)
292 , windingA(0)
293 , windingB(0)
294 , first(a)
295 , second(b)
296 , angle(0)
297 , invAngle(0)
298{
299}
300
301inline int QPathEdge::next(Traversal traversal, Direction direction) const
302{
303 return m_next[int(traversal)][int(direction)];
304}
305
306inline void QPathEdge::setNext(Traversal traversal, Direction direction, int next)
307{
308 m_next[int(traversal)][int(direction)] = next;
309}
310
311inline void QPathEdge::setNext(Direction direction, int next)
312{
313 m_next[0][int(direction)] = next;
314 m_next[1][int(direction)] = next;
315}
316
317inline QPathEdge::Direction QPathEdge::directionTo(int vertex) const
318{
319 return first == vertex ? Backward : Forward;
320}
321
322inline int QPathEdge::vertex(Direction direction) const
323{
324 return direction == Backward ? first : second;
325}
326
327inline QPathVertex::QPathVertex(const QPointF &p, int e)
328 : edge(e)
329 , x(p.x())
330 , y(p.y())
331{
332}
333
334inline QPathVertex::operator QPointF() const
335{
336 return QPointF(x, y);
337}
338
339inline QPathSegments::QPathSegments(int reserve) :
340 m_points(reserve),
341 m_segments(reserve),
342 m_intersections(reserve),
343 m_pathId(0)
344{
345}
346
347inline int QPathSegments::segments() const
348{
349 return m_segments.size();
350}
351
352inline int QPathSegments::points() const
353{
354 return m_points.size();
355}
356
357inline const QPointF &QPathSegments::pointAt(int i) const
358{
359 return m_points.at(i);
360}
361
362inline int QPathSegments::addPoint(const QPointF &point)
363{
364 m_points << point;
365 return m_points.size() - 1;
366}
367
368inline const QPathSegments::Segment &QPathSegments::segmentAt(int index) const
369{
370 return m_segments.at(i: index);
371}
372
373inline const QLineF QPathSegments::lineAt(int index) const
374{
375 const Segment &segment = m_segments.at(i: index);
376 return QLineF(m_points.at(i: segment.va), m_points.at(i: segment.vb));
377}
378
379inline const QRectF &QPathSegments::elementBounds(int index) const
380{
381 return m_segments.at(i: index).bounds;
382}
383
384inline int QPathSegments::pathId(int index) const
385{
386 return m_segments.at(i: index).path;
387}
388
389inline const QPathSegments::Intersection *QPathSegments::intersectionAt(int index) const
390{
391 const int intersection = m_segments.at(i: index).intersection;
392 if (intersection < 0)
393 return nullptr;
394 else
395 return &m_intersections.at(i: intersection);
396}
397
398inline int QPathSegments::intersections() const
399{
400 return m_intersections.size();
401}
402
403inline void QPathSegments::addIntersection(int index, const Intersection &intersection)
404{
405 m_intersections << intersection;
406
407 Segment &segment = m_segments.at(i: index);
408 if (segment.intersection < 0) {
409 segment.intersection = m_intersections.size() - 1;
410 } else {
411 Intersection *isect = &m_intersections.at(i: segment.intersection);
412
413 while (isect->next != 0)
414 isect += isect->next;
415
416 isect->next = (m_intersections.size() - 1) - (isect - m_intersections.data());
417 }
418}
419
420inline int QWingedEdge::edgeCount() const
421{
422 return m_edges.size();
423}
424
425inline QPathEdge *QWingedEdge::edge(int edge)
426{
427 return edge < 0 ? nullptr : &m_edges.at(i: edge);
428}
429
430inline const QPathEdge *QWingedEdge::edge(int edge) const
431{
432 return edge < 0 ? nullptr : &m_edges.at(i: edge);
433}
434
435inline int QWingedEdge::vertexCount() const
436{
437 return m_vertices.size();
438}
439
440inline int QWingedEdge::addVertex(const QPointF &p)
441{
442 m_vertices << p;
443 return m_vertices.size() - 1;
444}
445
446inline QPathVertex *QWingedEdge::vertex(int vertex)
447{
448 return vertex < 0 ? nullptr : &m_vertices.at(i: vertex);
449}
450
451inline const QPathVertex *QWingedEdge::vertex(int vertex) const
452{
453 return vertex < 0 ? nullptr : &m_vertices.at(i: vertex);
454}
455
456inline QPathEdge::Traversal QWingedEdge::flip(QPathEdge::Traversal traversal)
457{
458 return traversal == QPathEdge::RightTraversal ? QPathEdge::LeftTraversal : QPathEdge::RightTraversal;
459}
460
461inline void QWingedEdge::TraversalStatus::flipTraversal()
462{
463 traversal = QWingedEdge::flip(traversal);
464}
465
466inline QPathEdge::Direction QWingedEdge::flip(QPathEdge::Direction direction)
467{
468 return direction == QPathEdge::Forward ? QPathEdge::Backward : QPathEdge::Forward;
469}
470
471inline void QWingedEdge::TraversalStatus::flipDirection()
472{
473 direction = QWingedEdge::flip(direction);
474}
475
476inline void QWingedEdge::TraversalStatus::flip()
477{
478 flipDirection();
479 flipTraversal();
480}
481
482QT_END_NAMESPACE
483
484#endif // QPATHCLIPPER_P_H
485

source code of qtbase/src/gui/painting/qpathclipper_p.h