103 public: |
104 public: |
104 void produceIntersections(QPathSegments &segments); |
105 void produceIntersections(QPathSegments &segments); |
105 bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const; |
106 bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const; |
106 |
107 |
107 private: |
108 private: |
108 void intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections); |
|
109 void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections); |
|
110 |
|
111 bool beziersIntersect(const QBezier &one, const QBezier &two) const; |
|
112 bool linesIntersect(const QLineF &a, const QLineF &b) const; |
109 bool linesIntersect(const QLineF &a, const QLineF &b) const; |
113 }; |
110 }; |
114 |
|
115 bool QIntersectionFinder::beziersIntersect(const QBezier &one, const QBezier &two) const |
|
116 { |
|
117 return (comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2()) |
|
118 && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4())) |
|
119 || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3()) |
|
120 && comparePoints(one.pt3(), two.pt2()) && comparePoints(one.pt4(), two.pt1())) |
|
121 || QBezier::findIntersections(one, two, 0); |
|
122 } |
|
123 |
111 |
124 bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const |
112 bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const |
125 { |
113 { |
126 const QPointF p1 = a.p1(); |
114 const QPointF p1 = a.p1(); |
127 const QPointF p2 = a.p2(); |
115 const QPointF p2 = a.p2(); |
191 pDelta.x() * (q1.y() - p1.y())) * invPar; |
174 pDelta.x() * (q1.y() - p1.y())) * invPar; |
192 |
175 |
193 return tq >= 0 && tq <= 1; |
176 return tq >= 0 && tq <= 1; |
194 } |
177 } |
195 |
178 |
196 void QIntersectionFinder::intersectBeziers(const QBezier &one, const QBezier &two, QVector<QPair<qreal, qreal> > &t, QDataBuffer<QIntersection> &intersections) |
179 bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const |
197 { |
180 { |
198 if ((comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2()) |
181 if (a.segments() == 0 || b.segments() == 0) |
199 && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4())) |
182 return false; |
200 || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3()) |
183 |
201 && comparePoints(one.pt3(), two.pt2()) && comparePoints(one.pt4(), two.pt1()))) { |
184 const QRectF &rb0 = b.elementBounds(0); |
202 |
185 |
203 return; |
186 qreal minX = rb0.left(); |
204 } |
187 qreal minY = rb0.top(); |
205 |
188 qreal maxX = rb0.right(); |
206 t.clear(); |
189 qreal maxY = rb0.bottom(); |
207 |
190 |
208 if (!QBezier::findIntersections(one, two, &t)) |
191 for (int i = 1; i < b.segments(); ++i) { |
209 return; |
192 const QRectF &r = b.elementBounds(i); |
210 |
193 minX = qMin(minX, r.left()); |
211 int count = t.size(); |
194 minY = qMin(minY, r.top()); |
212 |
195 maxX = qMax(maxX, r.right()); |
213 for (int i = 0; i < count; ++i) { |
196 maxY = qMax(maxY, r.bottom()); |
214 qreal alpha_p = t.at(i).first; |
197 } |
215 qreal alpha_q = t.at(i).second; |
198 |
216 |
199 QRectF rb(minX, minY, maxX - minX, maxY - minY); |
217 QPointF pt; |
200 |
218 if (qFuzzyIsNull(alpha_p)) { |
201 for (int i = 0; i < a.segments(); ++i) { |
219 pt = one.pt1(); |
202 const QRectF &r1 = a.elementBounds(i); |
220 } else if (qFuzzyIsNull(alpha_p - 1)) { |
203 |
221 pt = one.pt4(); |
204 if (r1.left() > rb.right() || rb.left() > r1.right()) |
222 } else if (qFuzzyIsNull(alpha_q)) { |
205 continue; |
223 pt = two.pt1(); |
206 if (r1.top() > rb.bottom() || rb.top() > r1.bottom()) |
224 } else if (qFuzzyIsNull(alpha_q - 1)) { |
207 continue; |
225 pt = two.pt4(); |
208 |
|
209 for (int j = 0; j < b.segments(); ++j) { |
|
210 const QRectF &r2 = b.elementBounds(j); |
|
211 |
|
212 if (r1.left() > r2.right() || r2.left() > r1.right()) |
|
213 continue; |
|
214 if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) |
|
215 continue; |
|
216 |
|
217 if (linesIntersect(a.lineAt(i), b.lineAt(j))) |
|
218 return true; |
|
219 } |
|
220 } |
|
221 |
|
222 return false; |
|
223 } |
|
224 |
|
225 namespace { |
|
226 struct TreeNode |
|
227 { |
|
228 qreal splitLeft; |
|
229 qreal splitRight; |
|
230 bool leaf; |
|
231 |
|
232 int lowestLeftIndex; |
|
233 int lowestRightIndex; |
|
234 |
|
235 union { |
|
236 struct { |
|
237 int first; |
|
238 int last; |
|
239 } interval; |
|
240 struct { |
|
241 int left; |
|
242 int right; |
|
243 } children; |
|
244 } index; |
|
245 }; |
|
246 |
|
247 struct RectF |
|
248 { |
|
249 qreal x1; |
|
250 qreal y1; |
|
251 qreal x2; |
|
252 qreal y2; |
|
253 }; |
|
254 |
|
255 class SegmentTree |
|
256 { |
|
257 public: |
|
258 SegmentTree(QPathSegments &segments); |
|
259 |
|
260 QRectF boundingRect() const; |
|
261 |
|
262 void produceIntersections(int segment); |
|
263 |
|
264 private: |
|
265 TreeNode buildTree(int first, int last, int depth, const RectF &bounds); |
|
266 |
|
267 void produceIntersectionsLeaf(const TreeNode &node, int segment); |
|
268 void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis); |
|
269 void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections); |
|
270 |
|
271 QPathSegments &m_segments; |
|
272 QVector<int> m_index; |
|
273 |
|
274 RectF m_bounds; |
|
275 |
|
276 QVector<TreeNode> m_tree; |
|
277 QDataBuffer<QIntersection> m_intersections; |
|
278 }; |
|
279 |
|
280 SegmentTree::SegmentTree(QPathSegments &segments) |
|
281 : m_segments(segments), |
|
282 m_intersections(0) |
|
283 { |
|
284 m_bounds.x1 = qt_inf(); |
|
285 m_bounds.y1 = qt_inf(); |
|
286 m_bounds.x2 = -qt_inf(); |
|
287 m_bounds.y2 = -qt_inf(); |
|
288 |
|
289 m_index.resize(m_segments.segments()); |
|
290 |
|
291 for (int i = 0; i < m_index.size(); ++i) { |
|
292 m_index[i] = i; |
|
293 |
|
294 const QRectF &segmentBounds = m_segments.elementBounds(i); |
|
295 |
|
296 if (segmentBounds.left() < m_bounds.x1) |
|
297 m_bounds.x1 = segmentBounds.left(); |
|
298 if (segmentBounds.top() < m_bounds.y1) |
|
299 m_bounds.y1 = segmentBounds.top(); |
|
300 if (segmentBounds.right() > m_bounds.x2) |
|
301 m_bounds.x2 = segmentBounds.right(); |
|
302 if (segmentBounds.bottom() > m_bounds.y2) |
|
303 m_bounds.y2 = segmentBounds.bottom(); |
|
304 } |
|
305 |
|
306 m_tree.resize(1); |
|
307 |
|
308 TreeNode root = buildTree(0, m_index.size(), 0, m_bounds); |
|
309 m_tree[0] = root; |
|
310 } |
|
311 |
|
312 QRectF SegmentTree::boundingRect() const |
|
313 { |
|
314 return QRectF(QPointF(m_bounds.x1, m_bounds.y1), |
|
315 QPointF(m_bounds.x2, m_bounds.y2)); |
|
316 } |
|
317 |
|
318 static inline qreal coordinate(const QPointF &pos, int axis) |
|
319 { |
|
320 return axis == 0 ? pos.x() : pos.y(); |
|
321 } |
|
322 |
|
323 TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds) |
|
324 { |
|
325 if (depth >= 24 || (last - first) <= 10) { |
|
326 TreeNode node; |
|
327 node.leaf = true; |
|
328 node.index.interval.first = first; |
|
329 node.index.interval.last = last; |
|
330 |
|
331 return node; |
|
332 } |
|
333 |
|
334 int splitAxis = (depth & 1); |
|
335 |
|
336 TreeNode node; |
|
337 node.leaf = false; |
|
338 |
|
339 qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]); |
|
340 |
|
341 node.splitLeft = (&bounds.x1)[splitAxis]; |
|
342 node.splitRight = (&bounds.x2)[splitAxis]; |
|
343 |
|
344 node.lowestLeftIndex = INT_MAX; |
|
345 node.lowestRightIndex = INT_MAX; |
|
346 |
|
347 const int treeSize = m_tree.size(); |
|
348 |
|
349 node.index.children.left = treeSize; |
|
350 node.index.children.right = treeSize + 1; |
|
351 |
|
352 m_tree.resize(treeSize + 2); |
|
353 |
|
354 int l = first; |
|
355 int r = last - 1; |
|
356 |
|
357 // partition into left and right sets |
|
358 while (l <= r) { |
|
359 const int index = m_index.at(l); |
|
360 const QRectF &segmentBounds = m_segments.elementBounds(index); |
|
361 |
|
362 qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis); |
|
363 |
|
364 if (coordinate(segmentBounds.center(), splitAxis) < split) { |
|
365 qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis); |
|
366 if (highCoordinate > node.splitLeft) |
|
367 node.splitLeft = highCoordinate; |
|
368 if (index < node.lowestLeftIndex) |
|
369 node.lowestLeftIndex = index; |
|
370 ++l; |
226 } else { |
371 } else { |
227 pt = one.pointAt(alpha_p); |
372 if (lowCoordinate < node.splitRight) |
228 } |
373 node.splitRight = lowCoordinate; |
229 |
374 if (index < node.lowestRightIndex) |
230 QIntersection intersection; |
375 node.lowestRightIndex = index; |
231 intersection.alphaA = alpha_p; |
376 qSwap(m_index[l], m_index[r]); |
232 intersection.alphaB = alpha_q; |
377 --r; |
233 intersection.pos = pt; |
378 } |
234 intersections.add(intersection); |
379 } |
235 } |
380 |
236 } |
381 RectF lbounds = bounds; |
237 |
382 (&lbounds.x2)[splitAxis] = node.splitLeft; |
238 void QIntersectionFinder::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections) |
383 |
|
384 RectF rbounds = bounds; |
|
385 (&rbounds.x1)[splitAxis] = node.splitRight; |
|
386 |
|
387 TreeNode left = buildTree(first, l, depth + 1, lbounds); |
|
388 m_tree[node.index.children.left] = left; |
|
389 |
|
390 TreeNode right = buildTree(l, last, depth + 1, rbounds); |
|
391 m_tree[node.index.children.right] = right; |
|
392 |
|
393 return node; |
|
394 } |
|
395 |
|
396 void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections) |
239 { |
397 { |
240 const QPointF p1 = a.p1(); |
398 const QPointF p1 = a.p1(); |
241 const QPointF p2 = a.p2(); |
399 const QPointF p2 = a.p2(); |
242 |
400 |
243 const QPointF q1 = b.p1(); |
401 const QPointF q1 = b.p1(); |
355 intersection.alphaB = tq; |
513 intersection.alphaB = tq; |
356 intersection.pos = pt; |
514 intersection.pos = pt; |
357 intersections.add(intersection); |
515 intersections.add(intersection); |
358 } |
516 } |
359 |
517 |
360 static const QBezier bezierFromLine(const QLineF &line) |
518 void SegmentTree::produceIntersections(int segment) |
361 { |
519 { |
362 const QPointF p1 = line.p1(); |
520 const QRectF &segmentBounds = m_segments.elementBounds(segment); |
363 const QPointF p2 = line.p2(); |
521 |
364 const QPointF delta = (p2 - p1) / 3; |
522 RectF sbounds; |
365 return QBezier::fromPoints(p1, p1 + delta, p1 + 2 * delta, p2); |
523 sbounds.x1 = segmentBounds.left(); |
366 } |
524 sbounds.y1 = segmentBounds.top(); |
367 |
525 sbounds.x2 = segmentBounds.right(); |
368 bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const |
526 sbounds.y2 = segmentBounds.bottom(); |
369 { |
527 |
370 QBezier tempA; |
528 produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0); |
371 QBezier tempB; |
529 } |
372 |
530 |
373 if (a.segments() == 0 || b.segments() == 0) |
531 void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment) |
374 return false; |
532 { |
375 |
533 const QRectF &r1 = m_segments.elementBounds(segment); |
376 const QRectF &rb0 = b.elementBounds(0); |
534 const QLineF lineA = m_segments.lineAt(segment); |
377 |
535 |
378 qreal minX = rb0.left(); |
536 for (int i = node.index.interval.first; i < node.index.interval.last; ++i) { |
379 qreal minY = rb0.top(); |
537 const int other = m_index.at(i); |
380 qreal maxX = rb0.right(); |
538 if (other >= segment) |
381 qreal maxY = rb0.bottom(); |
|
382 |
|
383 for (int i = 1; i < b.segments(); ++i) { |
|
384 const QRectF &r = b.elementBounds(i); |
|
385 minX = qMin(minX, r.left()); |
|
386 minY = qMin(minY, r.top()); |
|
387 maxX = qMax(maxX, r.right()); |
|
388 maxY = qMax(maxY, r.bottom()); |
|
389 } |
|
390 |
|
391 QRectF rb(minX, minY, maxX - minX, maxY - minY); |
|
392 |
|
393 for (int i = 0; i < a.segments(); ++i) { |
|
394 const QBezier *bezierA = a.bezierAt(i); |
|
395 bool isBezierA = bezierA != 0; |
|
396 |
|
397 const QRectF &r1 = a.elementBounds(i); |
|
398 |
|
399 if (r1.left() > rb.right() || rb.left() > r1.right()) |
|
400 continue; |
539 continue; |
401 if (r1.top() > rb.bottom() || rb.top() > r1.bottom()) |
540 |
|
541 const QRectF &r2 = m_segments.elementBounds(other); |
|
542 |
|
543 if (r1.left() > r2.right() || r2.left() > r1.right()) |
402 continue; |
544 continue; |
403 |
545 if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) |
404 for (int j = 0; j < b.segments(); ++j) { |
546 continue; |
405 const QRectF &r2 = b.elementBounds(j); |
547 |
406 |
548 m_intersections.reset(); |
407 if (r1.left() > r2.right() || r2.left() > r1.right()) |
549 |
408 continue; |
550 const QLineF lineB = m_segments.lineAt(other); |
409 if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) |
551 |
410 continue; |
552 intersectLines(lineA, lineB, m_intersections); |
411 |
553 |
412 bool isBezierB = b.bezierAt(j) != 0; |
554 for (int k = 0; k < m_intersections.size(); ++k) { |
413 |
555 QPathSegments::Intersection i_isect, j_isect; |
414 if (isBezierA || isBezierB) { |
556 i_isect.vertex = j_isect.vertex = m_segments.addPoint(m_intersections.at(k).pos); |
415 const QBezier *bezierB; |
557 |
416 if (isBezierB) { |
558 i_isect.t = m_intersections.at(k).alphaA; |
417 bezierB = b.bezierAt(j); |
559 j_isect.t = m_intersections.at(k).alphaB; |
418 } else { |
560 |
419 tempB = bezierFromLine(b.lineAt(j)); |
561 i_isect.next = 0; |
420 bezierB = &tempB; |
562 j_isect.next = 0; |
421 } |
563 |
422 |
564 m_segments.addIntersection(segment, i_isect); |
423 if (!bezierA) { |
565 m_segments.addIntersection(other, j_isect); |
424 tempA = bezierFromLine(a.lineAt(i)); |
566 } |
425 bezierA = &tempA; |
567 } |
426 } |
568 } |
427 |
569 |
428 if (beziersIntersect(*bezierA, *bezierB)) |
570 void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis) |
429 return true; |
571 { |
430 } else { |
572 if (node.leaf) { |
431 if (linesIntersect(a.lineAt(i), b.lineAt(j))) |
573 produceIntersectionsLeaf(node, segment); |
432 return true; |
574 return; |
433 } |
575 } |
434 } |
576 |
435 } |
577 RectF lbounds = nodeBounds; |
436 |
578 (&lbounds.x2)[axis] = node.splitLeft; |
437 return false; |
579 |
|
580 RectF rbounds = nodeBounds; |
|
581 (&rbounds.x1)[axis] = node.splitRight; |
|
582 |
|
583 if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft) |
|
584 produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis); |
|
585 |
|
586 if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight) |
|
587 produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis); |
|
588 } |
|
589 |
438 } |
590 } |
439 |
591 |
440 void QIntersectionFinder::produceIntersections(QPathSegments &segments) |
592 void QIntersectionFinder::produceIntersections(QPathSegments &segments) |
441 { |
593 { |
442 QBezier tempA; |
594 SegmentTree tree(segments); |
443 QBezier tempB; |
595 |
444 |
596 for (int i = 0; i < segments.segments(); ++i) |
445 QVector<QPair<qreal, qreal> > t; |
597 tree.produceIntersections(i); |
446 QDataBuffer<QIntersection> intersections; |
|
447 |
|
448 for (int i = 0; i < segments.segments(); ++i) { |
|
449 const QBezier *bezierA = segments.bezierAt(i); |
|
450 bool isBezierA = bezierA != 0; |
|
451 |
|
452 const QRectF &r1 = segments.elementBounds(i); |
|
453 |
|
454 for (int j = 0; j < i; ++j) { |
|
455 const QRectF &r2 = segments.elementBounds(j); |
|
456 |
|
457 if (r1.left() > r2.right() || r2.left() > r1.right()) |
|
458 continue; |
|
459 if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) |
|
460 continue; |
|
461 |
|
462 intersections.reset(); |
|
463 |
|
464 bool isBezierB = segments.bezierAt(j) != 0; |
|
465 |
|
466 if (isBezierA || isBezierB) { |
|
467 const QBezier *bezierB; |
|
468 if (isBezierB) { |
|
469 bezierB = segments.bezierAt(j); |
|
470 } else { |
|
471 tempB = bezierFromLine(segments.lineAt(j)); |
|
472 bezierB = &tempB; |
|
473 } |
|
474 |
|
475 if (!bezierA) { |
|
476 tempA = bezierFromLine(segments.lineAt(i)); |
|
477 bezierA = &tempA; |
|
478 } |
|
479 |
|
480 intersectBeziers(*bezierA, *bezierB, t, intersections); |
|
481 } else { |
|
482 const QLineF lineA = segments.lineAt(i); |
|
483 const QLineF lineB = segments.lineAt(j); |
|
484 |
|
485 intersectLines(lineA, lineB, intersections); |
|
486 } |
|
487 |
|
488 for (int k = 0; k < intersections.size(); ++k) { |
|
489 QPathSegments::Intersection i_isect, j_isect; |
|
490 i_isect.vertex = j_isect.vertex = segments.addPoint(intersections.at(k).pos); |
|
491 |
|
492 i_isect.t = intersections.at(k).alphaA; |
|
493 j_isect.t = intersections.at(k).alphaB; |
|
494 |
|
495 i_isect.next = 0; |
|
496 j_isect.next = 0; |
|
497 |
|
498 segments.addIntersection(i, i_isect); |
|
499 segments.addIntersection(j, j_isect); |
|
500 } |
|
501 } |
|
502 } |
|
503 } |
598 } |
504 |
599 |
505 class QKdPointTree |
600 class QKdPointTree |
506 { |
601 { |
507 public: |
602 public: |
729 } |
824 } |
730 } |
825 } |
731 |
826 |
732 qSort(intersections.data(), intersections.data() + intersections.size()); |
827 qSort(intersections.data(), intersections.data() + intersections.size()); |
733 |
828 |
734 const QBezier *bezier = m_segments.bezierAt(i); |
829 int first = m_segments.segmentAt(i).va; |
735 if (bezier) { |
830 int second = m_segments.segmentAt(i).vb; |
736 int first = m_segments.segmentAt(i).va; |
831 |
737 int second = m_segments.segmentAt(i).vb; |
832 int last = first; |
738 |
833 for (int j = 0; j < intersections.size(); ++j) { |
739 qreal alpha = 0.0; |
834 const QPathSegments::Intersection &isect = intersections.at(j); |
740 int last = first; |
835 |
741 for (int j = 0; j < intersections.size(); ++j) { |
836 QPathEdge *ep = edge(addEdge(last, isect.vertex)); |
742 const QPathSegments::Intersection &isect = intersections.at(j); |
|
743 |
|
744 addBezierEdge(bezier, last, isect.vertex, alpha, isect.t, pathId); |
|
745 |
|
746 alpha = isect.t; |
|
747 last = isect.vertex; |
|
748 } |
|
749 |
|
750 addBezierEdge(bezier, last, second, alpha, 1.0, pathId); |
|
751 } else { |
|
752 int first = m_segments.segmentAt(i).va; |
|
753 int second = m_segments.segmentAt(i).vb; |
|
754 |
|
755 int last = first; |
|
756 for (int j = 0; j < intersections.size(); ++j) { |
|
757 const QPathSegments::Intersection &isect = intersections.at(j); |
|
758 |
|
759 QPathEdge *ep = edge(addEdge(last, isect.vertex)); |
|
760 |
|
761 if (ep) { |
|
762 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1; |
|
763 if (pathId == 0) |
|
764 ep->windingA += dir; |
|
765 else |
|
766 ep->windingB += dir; |
|
767 } |
|
768 |
|
769 last = isect.vertex; |
|
770 } |
|
771 |
|
772 QPathEdge *ep = edge(addEdge(last, second)); |
|
773 |
837 |
774 if (ep) { |
838 if (ep) { |
775 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1; |
839 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1; |
776 if (pathId == 0) |
840 if (pathId == 0) |
777 ep->windingA += dir; |
841 ep->windingA += dir; |
778 else |
842 else |
779 ep->windingB += dir; |
843 ep->windingB += dir; |
780 } |
844 } |
781 } |
845 |
782 } |
846 last = isect.vertex; |
783 } |
847 } |
784 |
848 |
785 QWingedEdge::QWingedEdge() |
849 QPathEdge *ep = edge(addEdge(last, second)); |
786 { |
850 |
787 } |
851 if (ep) { |
788 |
852 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1; |
789 QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) |
853 if (pathId == 0) |
|
854 ep->windingA += dir; |
|
855 else |
|
856 ep->windingB += dir; |
|
857 } |
|
858 } |
|
859 } |
|
860 |
|
861 QWingedEdge::QWingedEdge() : |
|
862 m_edges(0), |
|
863 m_vertices(0), |
|
864 m_segments(0) |
|
865 { |
|
866 } |
|
867 |
|
868 QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) : |
|
869 m_edges(subject.length()), |
|
870 m_vertices(subject.length()), |
|
871 m_segments(subject.length()) |
790 { |
872 { |
791 m_segments.setPath(subject); |
873 m_segments.setPath(subject); |
792 m_segments.addPath(clip); |
874 m_segments.addPath(clip); |
793 |
875 |
794 intersectAndAdd(); |
876 intersectAndAdd(); |
933 if (vertex == bp->second) |
1026 if (vertex == bp->second) |
934 b_angle = bp->invAngle; |
1027 b_angle = bp->invAngle; |
935 |
1028 |
936 qreal result = b_angle - a_angle; |
1029 qreal result = b_angle - a_angle; |
937 |
1030 |
938 if (qFuzzyIsNull(result) || qFuzzyCompare(result, 128)) |
1031 if (result >= 128.) |
939 return 0; |
1032 return result - 128.; |
940 |
1033 else if (result < 0) |
941 if (result < 0) |
|
942 return result + 128.; |
1034 return result + 128.; |
943 else |
1035 else |
944 return result; |
1036 return result; |
945 } |
1037 } |
946 |
1038 |
947 static inline QPointF tangentAt(const QWingedEdge &list, int vi, int ei) |
1039 static inline QPointF tangentAt(const QWingedEdge &list, int vi, int ei) |
948 { |
1040 { |
949 const QPathEdge *ep = list.edge(ei); |
1041 const QPathEdge *ep = list.edge(ei); |
950 Q_ASSERT(ep); |
1042 Q_ASSERT(ep); |
951 |
1043 |
952 qreal t; |
|
953 qreal sign; |
1044 qreal sign; |
954 |
1045 |
955 if (ep->first == vi) { |
1046 if (ep->first == vi) { |
956 t = ep->t0; |
|
957 sign = 1; |
1047 sign = 1; |
958 } else { |
1048 } else { |
959 t = ep->t1; |
|
960 sign = -1; |
1049 sign = -1; |
961 } |
1050 } |
962 |
1051 |
963 QPointF normal; |
1052 const QPointF a = *list.vertex(ep->first); |
964 if (ep->bezier) { |
1053 const QPointF b = *list.vertex(ep->second); |
965 normal = ep->bezier->derivedAt(t); |
1054 QPointF normal = b - a; |
966 |
|
967 if (qFuzzyIsNull(normal.x()) && qFuzzyIsNull(normal.y())) |
|
968 normal = ep->bezier->secondDerivedAt(t); |
|
969 } else { |
|
970 const QPointF a = *list.vertex(ep->first); |
|
971 const QPointF b = *list.vertex(ep->second); |
|
972 normal = b - a; |
|
973 } |
|
974 |
1055 |
975 return normalize(sign * normal); |
1056 return normalize(sign * normal); |
976 } |
1057 } |
977 |
1058 |
978 static inline QPointF midPoint(const QWingedEdge &list, int ei) |
1059 static inline QPointF midPoint(const QWingedEdge &list, int ei) |
979 { |
1060 { |
980 const QPathEdge *ep = list.edge(ei); |
1061 const QPathEdge *ep = list.edge(ei); |
981 Q_ASSERT(ep); |
1062 Q_ASSERT(ep); |
982 |
1063 |
983 if (ep->bezier) { |
1064 const QPointF a = *list.vertex(ep->first); |
984 return ep->bezier->pointAt(0.5 * (ep->t0 + ep->t1)); |
1065 const QPointF b = *list.vertex(ep->second); |
985 } else { |
1066 return a + 0.5 * (b - a); |
986 const QPointF a = *list.vertex(ep->first); |
|
987 const QPointF b = *list.vertex(ep->second); |
|
988 return a + 0.5 * (b - a); |
|
989 } |
|
990 } |
|
991 |
|
992 static QBezier transform(const QBezier &bezier, const QPointF &xAxis, const QPointF &yAxis, const QPointF &origin) |
|
993 { |
|
994 QPointF points[4] = { |
|
995 bezier.pt1(), |
|
996 bezier.pt2(), |
|
997 bezier.pt3(), |
|
998 bezier.pt4() |
|
999 }; |
|
1000 |
|
1001 for (int i = 0; i < 4; ++i) { |
|
1002 const QPointF p = points[i] - origin; |
|
1003 |
|
1004 points[i].rx() = dot(xAxis, p); |
|
1005 points[i].ry() = dot(yAxis, p); |
|
1006 } |
|
1007 |
|
1008 return QBezier::fromPoints(points[0], points[1], points[2], points[3]); |
|
1009 } |
|
1010 |
|
1011 static bool isLeftOf(const QWingedEdge &list, int vi, int ai, int bi) |
|
1012 { |
|
1013 const QPathEdge *ap = list.edge(ai); |
|
1014 const QPathEdge *bp = list.edge(bi); |
|
1015 |
|
1016 Q_ASSERT(ap); |
|
1017 Q_ASSERT(bp); |
|
1018 |
|
1019 if (!(ap->bezier || bp->bezier)) |
|
1020 return false; |
|
1021 |
|
1022 const QPointF tangent = tangentAt(list, vi, ai); |
|
1023 const QPointF normal(tangent.y(), -tangent.x()); |
|
1024 |
|
1025 const QPointF origin = *list.vertex(vi); |
|
1026 |
|
1027 const QPointF dpA = midPoint(list, ai) - origin; |
|
1028 const QPointF dpB = midPoint(list, bi) - origin; |
|
1029 |
|
1030 qreal xA = dot(normal, dpA); |
|
1031 qreal xB = dot(normal, dpB); |
|
1032 |
|
1033 if (xA <= 0 && xB >= 0) |
|
1034 return true; |
|
1035 |
|
1036 if (xA >= 0 && xB <= 0) |
|
1037 return false; |
|
1038 |
|
1039 if (!ap->bezier) |
|
1040 return xB > 0; |
|
1041 |
|
1042 if (!bp->bezier) |
|
1043 return xA < 0; |
|
1044 |
|
1045 // both are beziers on the same side of the tangent |
|
1046 |
|
1047 // transform the beziers into the local coordinate system |
|
1048 // such that positive y is along the tangent, and positive x is along the normal |
|
1049 |
|
1050 QBezier bezierA = transform(*ap->bezier, normal, tangent, origin); |
|
1051 QBezier bezierB = transform(*bp->bezier, normal, tangent, origin); |
|
1052 |
|
1053 qreal y = qMin(bezierA.pointAt(0.5 * (ap->t0 + ap->t1)).y(), |
|
1054 bezierB.pointAt(0.5 * (bp->t0 + bp->t1)).y()); |
|
1055 |
|
1056 xA = bezierA.pointAt(bezierA.tForY(ap->t0, ap->t1, y)).x(); |
|
1057 xB = bezierB.pointAt(bezierB.tForY(bp->t0, bp->t1, y)).x(); |
|
1058 |
|
1059 return xA < xB; |
|
1060 } |
1067 } |
1061 |
1068 |
1062 QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const |
1069 QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const |
1063 { |
1070 { |
1064 const QPathVertex *vp = vertex(vi); |
1071 const QPathVertex *vp = vertex(vi); |
1235 QPathVertex *fp = vertex(fi); |
1240 QPathVertex *fp = vertex(fi); |
1236 QPathVertex *sp = vertex(si); |
1241 QPathVertex *sp = vertex(si); |
1237 |
1242 |
1238 QPathEdge *ep = edge(ei); |
1243 QPathEdge *ep = edge(ei); |
1239 |
1244 |
1240 ep->bezier = bezier; |
1245 const QPointF tangent = QPointF(*sp) - QPointF(*fp); |
1241 ep->t0 = t0; |
1246 ep->angle = computeAngle(tangent); |
1242 ep->t1 = t1; |
1247 ep->invAngle = ep->angle + 64; |
1243 |
1248 if (ep->invAngle >= 128) |
1244 if (bezier) { |
1249 ep->invAngle -= 128; |
1245 QPointF aTangent = bezier->derivedAt(t0); |
|
1246 QPointF bTangent = -bezier->derivedAt(t1); |
|
1247 |
|
1248 if (qFuzzyIsNull(aTangent.x()) && qFuzzyIsNull(aTangent.y())) |
|
1249 aTangent = bezier->secondDerivedAt(t0); |
|
1250 |
|
1251 if (qFuzzyIsNull(bTangent.x()) && qFuzzyIsNull(bTangent.y())) |
|
1252 bTangent = bezier->secondDerivedAt(t1); |
|
1253 |
|
1254 ep->angle = computeAngle(aTangent); |
|
1255 ep->invAngle = computeAngle(bTangent); |
|
1256 } else { |
|
1257 const QPointF tangent = QPointF(*sp) - QPointF(*fp); |
|
1258 ep->angle = computeAngle(tangent); |
|
1259 ep->invAngle = ep->angle + 64; |
|
1260 if (ep->invAngle >= 128) |
|
1261 ep->invAngle -= 128; |
|
1262 } |
|
1263 |
1250 |
1264 QPathVertex *vertices[2] = { fp, sp }; |
1251 QPathVertex *vertices[2] = { fp, sp }; |
1265 QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward }; |
1252 QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward }; |
1266 |
1253 |
1267 #ifdef QDEBUG_CLIPPER |
1254 #ifdef QDEBUG_CLIPPER |
1312 Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0); |
1299 Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0); |
1313 |
1300 |
1314 return ei; |
1301 return ei; |
1315 } |
1302 } |
1316 |
1303 |
1317 void QWingedEdge::addBezierEdge(const QBezier *bezier, int vertexA, int vertexB, qreal alphaA, qreal alphaB, int path) |
|
1318 { |
|
1319 if (qFuzzyCompare(alphaA, alphaB)) |
|
1320 return; |
|
1321 |
|
1322 qreal alphaMid = (alphaA + alphaB) * 0.5; |
|
1323 |
|
1324 qreal s0 = 0; |
|
1325 qreal s1 = 1; |
|
1326 int count = bezier->stationaryYPoints(s0, s1); |
|
1327 |
|
1328 m_splitPoints.clear(); |
|
1329 m_splitPoints << alphaA; |
|
1330 m_splitPoints << alphaMid; |
|
1331 m_splitPoints << alphaB; |
|
1332 |
|
1333 if (count > 0 && !qFuzzyCompare(s0, alphaA) && !qFuzzyCompare(s0, alphaMid) && !qFuzzyCompare(s0, alphaB) && s0 > alphaA && s0 < alphaB) |
|
1334 m_splitPoints << s0; |
|
1335 |
|
1336 if (count > 1 && !qFuzzyCompare(s1, alphaA) && !qFuzzyCompare(s1, alphaMid) && !qFuzzyCompare(s1, alphaB) && s1 > alphaA && s1 < alphaB) |
|
1337 m_splitPoints << s1; |
|
1338 |
|
1339 if (count > 0) |
|
1340 qSort(m_splitPoints.begin(), m_splitPoints.end()); |
|
1341 |
|
1342 int last = vertexA; |
|
1343 for (int i = 0; i < m_splitPoints.size() - 1; ++i) { |
|
1344 const qreal t0 = m_splitPoints[i]; |
|
1345 const qreal t1 = m_splitPoints[i+1]; |
|
1346 |
|
1347 int current; |
|
1348 if ((i + 1) == (m_splitPoints.size() - 1)) { |
|
1349 current = vertexB; |
|
1350 } else { |
|
1351 current = insert(bezier->pointAt(t1)); |
|
1352 } |
|
1353 |
|
1354 QPathEdge *ep = edge(addEdge(last, current, bezier, t0, t1)); |
|
1355 |
|
1356 if (ep) { |
|
1357 const int dir = m_vertices.at(last).y < m_vertices.at(current).y ? 1 : -1; |
|
1358 if (path == 0) |
|
1359 ep->windingA += dir; |
|
1360 else |
|
1361 ep->windingB += dir; |
|
1362 } |
|
1363 |
|
1364 last = current; |
|
1365 } |
|
1366 } |
|
1367 |
|
1368 void QWingedEdge::addBezierEdge(const QBezier *bezier, const QPointF &a, const QPointF &b, qreal alphaA, qreal alphaB, int path) |
|
1369 { |
|
1370 if (qFuzzyCompare(alphaA, alphaB)) |
|
1371 return; |
|
1372 |
|
1373 if (comparePoints(a, b)) { |
|
1374 int v = insert(a); |
|
1375 |
|
1376 addBezierEdge(bezier, v, v, alphaA, alphaB, path); |
|
1377 } else { |
|
1378 int va = insert(a); |
|
1379 int vb = insert(b); |
|
1380 |
|
1381 addBezierEdge(bezier, va, vb, alphaA, alphaB, path); |
|
1382 } |
|
1383 } |
|
1384 |
|
1385 int QWingedEdge::insert(const QPathVertex &vertex) |
1304 int QWingedEdge::insert(const QPathVertex &vertex) |
1386 { |
1305 { |
1387 if (!m_vertices.isEmpty()) { |
1306 if (!m_vertices.isEmpty()) { |
1388 const QPathVertex &last = m_vertices.last(); |
1307 const QPathVertex &last = m_vertices.last(); |
1389 if (vertex.x == last.x && vertex.y == last.y) |
1308 if (vertex.x == last.x && vertex.y == last.y) |
1428 QWingedEdge::TraversalStatus status; |
1347 QWingedEdge::TraversalStatus status; |
1429 status.edge = edge; |
1348 status.edge = edge; |
1430 status.traversal = traversal; |
1349 status.traversal = traversal; |
1431 status.direction = QPathEdge::Forward; |
1350 status.direction = QPathEdge::Forward; |
1432 |
1351 |
1433 const QBezier *bezier = 0; |
|
1434 qreal t0 = 1; |
|
1435 qreal t1 = 0; |
|
1436 bool forward = true; |
|
1437 |
|
1438 path.moveTo(*list.vertex(list.edge(edge)->first)); |
1352 path.moveTo(*list.vertex(list.edge(edge)->first)); |
1439 |
1353 |
1440 do { |
1354 do { |
1441 const QPathEdge *ep = list.edge(status.edge); |
1355 const QPathEdge *ep = list.edge(status.edge); |
1442 |
1356 |
1443 if (ep->bezier != bezier || (bezier && t0 != ep->t1 && t1 != ep->t0)) { |
1357 addLineTo(path, *list.vertex(ep->vertex(status.direction))); |
1444 if (bezier) { |
|
1445 QBezier sub = bezier->bezierOnInterval(t0, t1); |
|
1446 |
|
1447 if (forward) |
|
1448 path.cubicTo(sub.pt2(), sub.pt3(), sub.pt4()); |
|
1449 else |
|
1450 path.cubicTo(sub.pt3(), sub.pt2(), sub.pt1()); |
|
1451 } |
|
1452 |
|
1453 bezier = ep->bezier; |
|
1454 t0 = 1; |
|
1455 t1 = 0; |
|
1456 forward = status.direction == QPathEdge::Forward; |
|
1457 } |
|
1458 |
|
1459 if (ep->bezier) { |
|
1460 t0 = qMin(t0, ep->t0); |
|
1461 t1 = qMax(t1, ep->t1); |
|
1462 } else |
|
1463 addLineTo(path, *list.vertex(ep->vertex(status.direction))); |
|
1464 |
1358 |
1465 if (status.traversal == QPathEdge::LeftTraversal) |
1359 if (status.traversal == QPathEdge::LeftTraversal) |
1466 ep->flag &= ~16; |
1360 ep->flag &= ~16; |
1467 else |
1361 else |
1468 ep->flag &= ~32; |
1362 ep->flag &= ~32; |
1469 |
1363 |
1470 status = list.next(status); |
1364 status = list.next(status); |
1471 } while (status.edge != edge); |
1365 } while (status.edge != edge); |
1472 |
|
1473 if (bezier) { |
|
1474 QBezier sub = bezier->bezierOnInterval(t0, t1); |
|
1475 if (forward) |
|
1476 path.cubicTo(sub.pt2(), sub.pt3(), sub.pt4()); |
|
1477 else |
|
1478 path.cubicTo(sub.pt3(), sub.pt2(), sub.pt1()); |
|
1479 } |
|
1480 } |
1366 } |
1481 |
1367 |
1482 void QWingedEdge::simplify() |
1368 void QWingedEdge::simplify() |
1483 { |
1369 { |
1484 for (int i = 0; i < edgeCount(); ++i) { |
1370 for (int i = 0; i < edgeCount(); ++i) { |
2050 } |
1921 } |
2051 |
1922 |
2052 return false; |
1923 return false; |
2053 } |
1924 } |
2054 |
1925 |
|
1926 namespace { |
|
1927 |
|
1928 QList<QPainterPath> toSubpaths(const QPainterPath &path) |
|
1929 { |
|
1930 |
|
1931 QList<QPainterPath> subpaths; |
|
1932 if (path.isEmpty()) |
|
1933 return subpaths; |
|
1934 |
|
1935 QPainterPath current; |
|
1936 for (int i = 0; i < path.elementCount(); ++i) { |
|
1937 const QPainterPath::Element &e = path.elementAt(i); |
|
1938 switch (e.type) { |
|
1939 case QPainterPath::MoveToElement: |
|
1940 if (current.elementCount() > 1) |
|
1941 subpaths += current; |
|
1942 current = QPainterPath(); |
|
1943 current.moveTo(e); |
|
1944 break; |
|
1945 case QPainterPath::LineToElement: |
|
1946 current.lineTo(e); |
|
1947 break; |
|
1948 case QPainterPath::CurveToElement: { |
|
1949 current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2)); |
|
1950 i+=2; |
|
1951 break; |
|
1952 } |
|
1953 case QPainterPath::CurveToDataElement: |
|
1954 Q_ASSERT(!"toSubpaths(), bad element type"); |
|
1955 break; |
|
1956 } |
|
1957 } |
|
1958 |
|
1959 if (current.elementCount() > 1) |
|
1960 subpaths << current; |
|
1961 |
|
1962 return subpaths; |
|
1963 } |
|
1964 |
|
1965 enum Edge |
|
1966 { |
|
1967 Left, Top, Right, Bottom |
|
1968 }; |
|
1969 |
|
1970 static bool isVertical(Edge edge) |
|
1971 { |
|
1972 return edge == Left || edge == Right; |
|
1973 } |
|
1974 |
|
1975 template <Edge edge> |
|
1976 bool compare(const QPointF &p, qreal t) |
|
1977 { |
|
1978 switch (edge) |
|
1979 { |
|
1980 case Left: |
|
1981 return p.x() < t; |
|
1982 case Right: |
|
1983 return p.x() > t; |
|
1984 case Top: |
|
1985 return p.y() < t; |
|
1986 default: |
|
1987 return p.y() > t; |
|
1988 } |
|
1989 } |
|
1990 |
|
1991 template <Edge edge> |
|
1992 QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t) |
|
1993 { |
|
1994 QLineF line(a, b); |
|
1995 switch (edge) { |
|
1996 case Left: // fall-through |
|
1997 case Right: |
|
1998 return line.pointAt((t - a.x()) / (b.x() - a.x())); |
|
1999 default: |
|
2000 return line.pointAt((t - a.y()) / (b.y() - a.y())); |
|
2001 } |
|
2002 } |
|
2003 |
|
2004 void addLine(QPainterPath &path, const QLineF &line) |
|
2005 { |
|
2006 if (path.elementCount() > 0) |
|
2007 path.lineTo(line.p1()); |
|
2008 else |
|
2009 path.moveTo(line.p1()); |
|
2010 |
|
2011 path.lineTo(line.p2()); |
|
2012 } |
|
2013 |
|
2014 template <Edge edge> |
|
2015 void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result) |
|
2016 { |
|
2017 bool outA = compare<edge>(a, t); |
|
2018 bool outB = compare<edge>(b, t); |
|
2019 if (outA && outB) |
|
2020 return; |
|
2021 |
|
2022 if (outA) |
|
2023 addLine(result, QLineF(intersectLine<edge>(a, b, t), b)); |
|
2024 else if(outB) |
|
2025 addLine(result, QLineF(a, intersectLine<edge>(a, b, t))); |
|
2026 else |
|
2027 addLine(result, QLineF(a, b)); |
|
2028 } |
|
2029 |
|
2030 void addBezier(QPainterPath &path, const QBezier &bezier) |
|
2031 { |
|
2032 if (path.elementCount() > 0) |
|
2033 path.lineTo(bezier.pt1()); |
|
2034 else |
|
2035 path.moveTo(bezier.pt1()); |
|
2036 |
|
2037 path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4()); |
|
2038 } |
|
2039 |
|
2040 template <Edge edge> |
|
2041 void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result) |
|
2042 { |
|
2043 QBezier bezier = QBezier::fromPoints(a, b, c, d); |
|
2044 |
|
2045 bool outA = compare<edge>(a, t); |
|
2046 bool outB = compare<edge>(b, t); |
|
2047 bool outC = compare<edge>(c, t); |
|
2048 bool outD = compare<edge>(d, t); |
|
2049 |
|
2050 int outCount = int(outA) + int(outB) + int(outC) + int(outD); |
|
2051 |
|
2052 if (outCount == 4) |
|
2053 return; |
|
2054 |
|
2055 if (outCount == 0) { |
|
2056 addBezier(result, bezier); |
|
2057 return; |
|
2058 } |
|
2059 |
|
2060 QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform(); |
|
2061 QBezier unflipped = bezier; |
|
2062 QBezier flipped = bezier.mapBy(flip); |
|
2063 |
|
2064 qreal t0 = 0, t1 = 1; |
|
2065 int stationary = flipped.stationaryYPoints(t0, t1); |
|
2066 |
|
2067 qreal segments[4]; |
|
2068 QPointF points[4]; |
|
2069 points[0] = unflipped.pt1(); |
|
2070 segments[0] = 0; |
|
2071 |
|
2072 int segmentCount = 0; |
|
2073 if (stationary > 0) { |
|
2074 ++segmentCount; |
|
2075 segments[segmentCount] = t0; |
|
2076 points[segmentCount] = unflipped.pointAt(t0); |
|
2077 } |
|
2078 if (stationary > 1) { |
|
2079 ++segmentCount; |
|
2080 segments[segmentCount] = t1; |
|
2081 points[segmentCount] = unflipped.pointAt(t1); |
|
2082 } |
|
2083 ++segmentCount; |
|
2084 segments[segmentCount] = 1; |
|
2085 points[segmentCount] = unflipped.pt4(); |
|
2086 |
|
2087 qreal lastIntersection = 0; |
|
2088 for (int i = 0; i < segmentCount; ++i) { |
|
2089 outA = compare<edge>(points[i], t); |
|
2090 outB = compare<edge>(points[i+1], t); |
|
2091 |
|
2092 if (outA != outB) { |
|
2093 qreal intersection = flipped.tForY(segments[i], segments[i+1], t); |
|
2094 |
|
2095 if (outB) |
|
2096 addBezier(result, unflipped.getSubRange(lastIntersection, intersection)); |
|
2097 |
|
2098 lastIntersection = intersection; |
|
2099 } |
|
2100 } |
|
2101 |
|
2102 if (!outB) |
|
2103 addBezier(result, unflipped.getSubRange(lastIntersection, 1)); |
|
2104 } |
|
2105 |
|
2106 // clips a single subpath against a single edge |
|
2107 template <Edge edge> |
|
2108 QPainterPath clip(const QPainterPath &path, qreal t) |
|
2109 { |
|
2110 QPainterPath result; |
|
2111 for (int i = 1; i < path.elementCount(); ++i) { |
|
2112 const QPainterPath::Element &element = path.elementAt(i); |
|
2113 Q_ASSERT(!element.isMoveTo()); |
|
2114 if (element.isLineTo()) { |
|
2115 clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result); |
|
2116 } else { |
|
2117 clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result); |
|
2118 i += 2; |
|
2119 } |
|
2120 } |
|
2121 |
|
2122 int last = path.elementCount() - 1; |
|
2123 if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0))) |
|
2124 clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result); |
|
2125 |
|
2126 return result; |
|
2127 } |
|
2128 |
|
2129 QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect) |
|
2130 { |
|
2131 QList<QPainterPath> subpaths = toSubpaths(path); |
|
2132 |
|
2133 QPainterPath result; |
|
2134 result.setFillRule(path.fillRule()); |
|
2135 for (int i = 0; i < subpaths.size(); ++i) { |
|
2136 QPainterPath subPath = subpaths.at(i); |
|
2137 QRectF bounds = subPath.boundingRect(); |
|
2138 if (bounds.intersects(rect)) { |
|
2139 if (bounds.left() < rect.left()) |
|
2140 subPath = clip<Left>(subPath, rect.left()); |
|
2141 if (bounds.right() > rect.right()) |
|
2142 subPath = clip<Right>(subPath, rect.right()); |
|
2143 |
|
2144 bounds = subPath.boundingRect(); |
|
2145 |
|
2146 if (bounds.top() < rect.top()) |
|
2147 subPath = clip<Top>(subPath, rect.top()); |
|
2148 if (bounds.bottom() > rect.bottom()) |
|
2149 subPath = clip<Bottom>(subPath, rect.bottom()); |
|
2150 |
|
2151 if (subPath.elementCount() > 1) |
|
2152 result.addPath(subPath); |
|
2153 } |
|
2154 } |
|
2155 return result; |
|
2156 } |
|
2157 |
|
2158 } |
|
2159 |
|
2160 QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect) |
|
2161 { |
|
2162 return intersectPath(path, rect); |
|
2163 } |
|
2164 |
2055 QT_END_NAMESPACE |
2165 QT_END_NAMESPACE |