source: trunk/src/gui/painting/qpathclipper.cpp@ 115

Last change on this file since 115 was 2, checked in by Dmitry A. Kuminov, 17 years ago

Initially imported qt-all-opensource-src-4.5.1 from Trolltech.
File size: 57.7 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
4** Contact: Qt Software Information ([email protected])
5**
6** This file is part of the QtGui module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial Usage
10** Licensees holding valid Qt Commercial licenses may use this file in
11** accordance with the Qt Commercial License Agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and Nokia.
14**
15** GNU Lesser General Public License Usage
16** Alternatively, this file may be used under the terms of the GNU Lesser
17** General Public License version 2.1 as published by the Free Software
18** Foundation and appearing in the file LICENSE.LGPL included in the
19** packaging of this file. Please review the following information to
20** ensure the GNU Lesser General Public License version 2.1 requirements
21** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
22**
23** In addition, as a special exception, Nokia gives you certain
24** additional rights. These rights are described in the Nokia Qt LGPL
25** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
26** package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you are unsure which license is appropriate for your use, please
37** contact the sales department at [email protected].
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42#include "qpathclipper_p.h"
43
44#include <private/qbezier_p.h>
45#include <private/qdatabuffer_p.h>
46#include <qmath.h>
47
48#include <QImage>
49#include <QPainter>
50
51/**
52 The algorithm is as follows:
53
54 1. Find all intersections between the two paths (including self-intersections),
55 and build a winged edge structure of non-intersecting parts.
56 2. While there are more unhandled edges:
57 3. Pick a y-coordinate from an unhandled edge.
58 4. Intersect the horizontal line at y-coordinate with all edges.
59 5. Traverse intersections left to right deciding whether each subpath should be added or not.
60 6. If the subpath should be added, traverse the winged-edge structure and add the edges to
61 a separate winged edge structure.
62 7. Mark all edges in subpaths crossing the horizontal line as handled.
63 8. (Optional) Simplify the resulting winged edge structure by merging shared edges.
64 9. Convert the resulting winged edge structure to a painter path.
65 */
66
67#include <qdebug.h>
68
69QT_BEGIN_NAMESPACE
70
71//#define QDEBUG_CLIPPER
72static qreal dot(const QPointF &a, const QPointF &b)
73{
74 return a.x() * b.x() + a.y() * b.y();
75}
76
77static QPointF normalize(const QPointF &p)
78{
79 return p / qSqrt(p.x() * p.x() + p.y() * p.y());
80}
81
82static bool pathToRect(const QPainterPath &path, QRectF *rect = 0);
83
84struct QIntersection
85{
86 qreal alphaA;
87 qreal alphaB;
88
89 QPointF pos;
90};
91
92class QIntersectionFinder
93{
94public:
95 void produceIntersections(QPathSegments &segments);
96 bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const;
97
98private:
99 void intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections);
100 void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections);
101
102 bool beziersIntersect(const QBezier &one, const QBezier &two) const;
103 bool linesIntersect(const QLineF &a, const QLineF &b) const;
104};
105
106bool QIntersectionFinder::beziersIntersect(const QBezier &one, const QBezier &two) const
107{
108 return (one.pt1() == two.pt1() && one.pt2() == two.pt2() && one.pt3() == two.pt3() && one.pt4() == two.pt4())
109 || (one.pt1() == two.pt4() && one.pt2() == two.pt3() && one.pt3() == two.pt2() && one.pt4() == two.pt1())
110 || QBezier::findIntersections(one, two, 0);
111}
112
113bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const
114{
115 const QPointF p1 = a.p1();
116 const QPointF p2 = a.p2();
117
118 const QPointF q1 = b.p1();
119 const QPointF q2 = b.p2();
120
121 if (p1 == p2 || q1 == q2)
122 return false;
123
124 const bool p1_equals_q1 = (p1 == q1);
125 const bool p2_equals_q2 = (p2 == q2);
126
127 if (p1_equals_q1 && p2_equals_q2)
128 return true;
129
130 const bool p1_equals_q2 = (p1 == q2);
131 const bool p2_equals_q1 = (p2 == q1);
132
133 if (p1_equals_q2 && p2_equals_q1)
134 return true;
135
136 const QPointF pDelta = p2 - p1;
137 const QPointF qDelta = q2 - q1;
138
139 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();
140
141 if (qFuzzyCompare(par + 1, 1)) {
142 const QPointF normal(-pDelta.y(), pDelta.x());
143
144 // coinciding?
145 if (qFuzzyCompare(dot(normal, q1 - p1) + 1, 1)) {
146 const qreal dp = dot(pDelta, pDelta);
147
148 const qreal tq1 = dot(pDelta, q1 - p1);
149 const qreal tq2 = dot(pDelta, q2 - p1);
150
151 if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp))
152 return true;
153
154 const qreal dq = dot(qDelta, qDelta);
155
156 const qreal tp1 = dot(qDelta, p1 - q1);
157 const qreal tp2 = dot(qDelta, p2 - q1);
158
159 if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq))
160 return true;
161 }
162
163 return false;
164 }
165
166 // if the lines are not parallel and share a common end point, then they
167 // don't intersect
168 if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2)
169 return false;
170
171 const qreal invPar = 1 / par;
172
173 const qreal tp = (qDelta.y() * (q1.x() - p1.x()) -
174 qDelta.x() * (q1.y() - p1.y())) * invPar;
175
176 if (tp < 0 || tp > 1)
177 return false;
178
179 const qreal tq = (pDelta.y() * (q1.x() - p1.x()) -
180 pDelta.x() * (q1.y() - p1.y())) * invPar;
181
182 return tq >= 0 && tq <= 1;
183}
184
185void QIntersectionFinder::intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections)
186{
187 if ((one.pt1() == two.pt1() && one.pt2() == two.pt2() && one.pt3() == two.pt3() && one.pt4() == two.pt4())
188 || (one.pt1() == two.pt4() && one.pt2() == two.pt3() && one.pt3() == two.pt2() && one.pt4() == two.pt1())) {
189
190 return;
191 }
192
193 t.clear();
194
195 if (!QBezier::findIntersections(one, two, &t))
196 return;
197
198 int count = t.size();
199
200 for (int i = 0; i < count; ++i) {
201 qreal alpha_p = t.at(i).first;
202 qreal alpha_q = t.at(i).second;
203
204 QPointF pt;
205 if (qFuzzyCompare(alpha_p + 1, 1)) {
206 pt = one.pt1();
207 } else if (qFuzzyCompare(alpha_p, 1)) {
208 pt = one.pt4();
209 } else if (qFuzzyCompare(alpha_q + 1, 1)) {
210 pt = two.pt1();
211 } else if (qFuzzyCompare(alpha_q, 1)) {
212 pt = two.pt4();
213 } else {
214 pt = one.pointAt(alpha_p);
215 }
216
217 QIntersection intersection;
218 intersection.alphaA = alpha_p;
219 intersection.alphaB = alpha_q;
220 intersection.pos = pt;
221 intersections.add(intersection);
222 }
223}
224
225void QIntersectionFinder::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections)
226{
227 const QPointF p1 = a.p1();
228 const QPointF p2 = a.p2();
229
230 const QPointF q1 = b.p1();
231 const QPointF q2 = b.p2();
232
233 if (p1 == p2 || q1 == q2)
234 return;
235
236 const bool p1_equals_q1 = (p1 == q1);
237 const bool p2_equals_q2 = (p2 == q2);
238
239 if (p1_equals_q1 && p2_equals_q2)
240 return;
241
242 const bool p1_equals_q2 = (p1 == q2);
243 const bool p2_equals_q1 = (p2 == q1);
244
245 if (p1_equals_q2 && p2_equals_q1)
246 return;
247
248 const QPointF pDelta = p2 - p1;
249 const QPointF qDelta = q2 - q1;
250
251 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x();
252
253 if (qFuzzyCompare(par + 1, 1)) {
254 const QPointF normal(-pDelta.y(), pDelta.x());
255
256 // coinciding?
257 if (qFuzzyCompare(dot(normal, q1 - p1) + 1, 1)) {
258 const qreal invDp = 1 / dot(pDelta, pDelta);
259
260 const qreal tq1 = dot(pDelta, q1 - p1) * invDp;
261 const qreal tq2 = dot(pDelta, q2 - p1) * invDp;
262
263 if (tq1 > 0 && tq1 < 1) {
264 QIntersection intersection;
265 intersection.alphaA = tq1;
266 intersection.alphaB = 0;
267 intersection.pos = q1;
268 intersections.add(intersection);
269 }
270
271 if (tq2 > 0 && tq2 < 1) {
272 QIntersection intersection;
273 intersection.alphaA = tq2;
274 intersection.alphaB = 1;
275 intersection.pos = q2;
276 intersections.add(intersection);
277 }
278
279 const qreal invDq = 1 / dot(qDelta, qDelta);
280
281 const qreal tp1 = dot(qDelta, p1 - q1) * invDq;
282 const qreal tp2 = dot(qDelta, p2 - q1) * invDq;
283
284 if (tp1 > 0 && tp1 < 1) {
285 QIntersection intersection;
286 intersection.alphaA = 0;
287 intersection.alphaB = tp1;
288 intersection.pos = p1;
289 intersections.add(intersection);
290 }
291
292 if (tp2 > 0 && tp2 < 1) {
293 QIntersection intersection;
294 intersection.alphaA = 1;
295 intersection.alphaB = tp2;
296 intersection.pos = p2;
297 intersections.add(intersection);
298 }
299 }
300
301 return;
302 }
303
304 // if the lines are not parallel and share a common end point, then they
305 // don't intersect
306 if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2)
307 return;
308
309
310 const qreal tp = (qDelta.y() * (q1.x() - p1.x()) -
311 qDelta.x() * (q1.y() - p1.y())) / par;
312 const qreal tq = (pDelta.y() * (q1.x() - p1.x()) -
313 pDelta.x() * (q1.y() - p1.y())) / par;
314
315 if (tp<0 || tp>1 || tq<0 || tq>1)
316 return;
317
318 const bool p_zero = qFuzzyCompare(tp + 1, 1);
319 const bool p_one = qFuzzyCompare(tp, 1);
320
321 const bool q_zero = qFuzzyCompare(tq + 1, 1);
322 const bool q_one = qFuzzyCompare(tq, 1);
323
324 if ((q_zero || q_one) && (p_zero || p_one))
325 return;
326
327 QPointF pt;
328 if (p_zero) {
329 pt = p1;
330 } else if (p_one) {
331 pt = p2;
332 } else if (q_zero) {
333 pt = q1;
334 } else if (q_one) {
335 pt = q2;
336 } else {
337 pt = q1 + (q2 - q1) * tq;
338 }
339
340 QIntersection intersection;
341 intersection.alphaA = tp;
342 intersection.alphaB = tq;
343 intersection.pos = pt;
344 intersections.add(intersection);
345}
346
347static const QBezier bezierFromLine(const QLineF &line)
348{
349 const QPointF p1 = line.p1();
350 const QPointF p2 = line.p2();
351 const QPointF delta = (p2 - p1) / 3;
352 return QBezier::fromPoints(p1, p1 + delta, p1 + 2 * delta, p2);
353}
354
355bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const
356{
357 QBezier tempA;
358 QBezier tempB;
359
360 if (a.segments() == 0 || b.segments() == 0)
361 return false;
362
363 const QRectF &rb0 = b.elementBounds(0);
364
365 qreal minX = rb0.left();
366 qreal minY = rb0.top();
367 qreal maxX = rb0.right();
368 qreal maxY = rb0.bottom();
369
370 for (int i = 1; i < b.segments(); ++i) {
371 const QRectF &r = b.elementBounds(i);
372 minX = qMin(minX, r.left());
373 minY = qMin(minY, r.top());
374 maxX = qMax(maxX, r.right());
375 maxY = qMax(maxY, r.bottom());
376 }
377
378 QRectF rb(minX, minY, maxX - minX, maxY - minY);
379
380 for (int i = 0; i < a.segments(); ++i) {
381 const QBezier *bezierA = a.bezierAt(i);
382 bool isBezierA = bezierA != 0;
383
384 const QRectF &r1 = a.elementBounds(i);
385
386 if (r1.left() > rb.right() || rb.left() > r1.right())
387 continue;
388 if (r1.top() > rb.bottom() || rb.top() > r1.bottom())
389 continue;
390
391 for (int j = 0; j < b.segments(); ++j) {
392 const QRectF &r2 = b.elementBounds(j);
393
394 if (r1.left() > r2.right() || r2.left() > r1.right())
395 continue;
396 if (r1.top() > r2.bottom() || r2.top() > r1.bottom())
397 continue;
398
399 bool isBezierB = b.bezierAt(j) != 0;
400
401 if (isBezierA || isBezierB) {
402 const QBezier *bezierB;
403 if (isBezierB) {
404 bezierB = b.bezierAt(j);