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

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