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];
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 QList<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 m_next[0][0] = -1;
300 m_next[1][0] = -1;
301 m_next[0][0] = -1;
302 m_next[1][0] = -1;
303}
304
305inline int QPathEdge::next(Traversal traversal, Direction direction) const
306{
307 return m_next[int(traversal)][int(direction)];
308}
309
310inline void QPathEdge::setNext(Traversal traversal, Direction direction, int next)
311{
312 m_next[int(traversal)][int(direction)] = next;
313}
314
315inline void QPathEdge::setNext(Direction direction, int next)
316{
317 m_next[0][int(direction)] = next;
318 m_next[1][int(direction)] = next;
319}
320
321inline QPathEdge::Direction QPathEdge::directionTo(int vertex) const
322{
323 return first == vertex ? Backward : Forward;
324}
325
326inline int QPathEdge::vertex(Direction direction) const
327{
328 return direction == Backward ? first : second;
329}
330
331inline QPathVertex::QPathVertex(const QPointF &p, int e)
332 : edge(e)
333 , x(p.x())
334 , y(p.y())
335{
336}
337
338inline QPathVertex::operator QPointF() const
339{
340 return QPointF(x, y);
341}
342
343inline QPathSegments::QPathSegments(int reserve) :
344 m_points(reserve),
345 m_segments(reserve),
346 m_intersections(reserve),
347 m_pathId(0)
348{
349}
350
351inline int QPathSegments::segments() const
352{
353 return m_segments.size();
354}
355
356inline int QPathSegments::points() const
357{
358 return m_points.size();
359}
360
361inline const QPointF &QPathSegments::pointAt(int i) const
362{
363 return m_points.at(i);
364}
365
366inline int QPathSegments::addPoint(const QPointF &point)
367{
368 m_points << point;
369 return m_points.size() - 1;
370}
371
372inline const QPathSegments::Segment &QPathSegments::segmentAt(int index) const
373{
374 return m_segments.at(index);
375}
376
377inline const QLineF QPathSegments::lineAt(int index) const
378{
379 const Segment &segment = m_segments.at(index);
380 return QLineF(m_points.at(segment.va), m_points.at(segment.vb));
381}
382
383inline const QRectF &QPathSegments::elementBounds(int index) const
384{
385 return m_segments.at(index).bounds;
386}
387
388inline int QPathSegments::pathId(int index) const
389{
390 return m_segments.at(index).path;
391}
392
393inline const QPathSegments::Intersection *QPathSegments::intersectionAt(int index) const
394{
395 const int intersection = m_segments.at(index).intersection;
396 if (intersection < 0)
397 return nullptr;
398 else
399 return &m_intersections.at(intersection);
400}
401
402inline int QPathSegments::intersections() const
403{
404 return m_intersections.size();
405}
406
407inline void QPathSegments::addIntersection(int index, const Intersection &intersection)
408{
409 m_intersections << intersection;
410
411 Segment &segment = m_segments.at(index);
412 if (segment.intersection < 0) {
413 segment.intersection = m_intersections.size() - 1;
414 } else {
415 Intersection *isect = &m_intersections.at(segment.intersection);
416
417 while (isect->next != 0)
418 isect += isect->next;
419
420 isect->next = (m_intersections.size() - 1) - (isect - m_intersections.data());
421 }
422}
423
424inline int QWingedEdge::edgeCount() const
425{
426 return m_edges.size();
427}
428
429inline QPathEdge *QWingedEdge::edge(int edge)
430{
431 return edge < 0 ? nullptr : &m_edges.at(edge);
432}
433
434inline const QPathEdge *QWingedEdge::edge(int edge) const
435{
436 return edge < 0 ? nullptr : &m_edges.at(edge);
437}
438
439inline int QWingedEdge::vertexCount() const
440{
441 return m_vertices.size();
442}
443
444inline int QWingedEdge::addVertex(const QPointF &p)
445{
446 m_vertices << p;
447 return m_vertices.size() - 1;
448}
449
450inline QPathVertex *QWingedEdge::vertex(int vertex)
451{
452 return vertex < 0 ? nullptr : &m_vertices.at(vertex);
453}
454
455inline const QPathVertex *QWingedEdge::vertex(int vertex) const
456{
457 return vertex < 0 ? nullptr : &m_vertices.at(vertex);
458}
459
460inline QPathEdge::Traversal QWingedEdge::flip(QPathEdge::Traversal traversal)
461{
462 return traversal == QPathEdge::RightTraversal ? QPathEdge::LeftTraversal : QPathEdge::RightTraversal;
463}
464
465inline void QWingedEdge::TraversalStatus::flipTraversal()
466{
467 traversal = QWingedEdge::flip(traversal);
468}
469
470inline QPathEdge::Direction QWingedEdge::flip(QPathEdge::Direction direction)
471{
472 return direction == QPathEdge::Forward ? QPathEdge::Backward : QPathEdge::Forward;
473}
474
475inline void QWingedEdge::TraversalStatus::flipDirection()
476{
477 direction = QWingedEdge::flip(direction);
478}
479
480inline void QWingedEdge::TraversalStatus::flip()
481{
482 flipDirection();
483 flipTraversal();
484}
485
486QT_END_NAMESPACE
487
488#endif // QPATHCLIPPER_P_H
489