From f7d61dab69308f0993c8a5f2232226d1713ac4a7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Samuel=20R=C3=B8dal?= Date: Thu, 22 Apr 2010 09:58:03 +0200 Subject: Removed bezier intersection code in path clipper. The bezier intersections caused a lot of numerical stability issues, so instead we now convert them to line segments. In the future it might be possible to keep track of which bezier curve a line segment originated from and reconstruct the bezier curves at the end. Task-number: QTBUG-8035 Reviewed-by: Gunnar Sletta --- src/gui/painting/qbezier.cpp | 305 ---------------- src/gui/painting/qbezier_p.h | 9 - src/gui/painting/qpainterpath.cpp | 9 +- src/gui/painting/qpathclipper.cpp | 508 +++++---------------------- src/gui/painting/qpathclipper_p.h | 30 +- src/s60installs/bwins/QtGuiu.def | 6 +- src/s60installs/eabi/QtGuiu.def | 6 +- tests/auto/qpathclipper/tst_qpathclipper.cpp | 50 --- 8 files changed, 98 insertions(+), 825 deletions(-) diff --git a/src/gui/painting/qbezier.cpp b/src/gui/painting/qbezier.cpp index a08c79e..7ff2a37 100644 --- a/src/gui/painting/qbezier.cpp +++ b/src/gui/painting/qbezier.cpp @@ -612,88 +612,6 @@ give_up: return o - curveSegments; } -#if 0 -static inline bool IntersectBB(const QBezier &a, const QBezier &b) -{ - return a.bounds().intersects(b.bounds()); -} -#else -static int IntersectBB(const QBezier &a, const QBezier &b) -{ - // Compute bounding box for a - qreal minax, maxax, minay, maxay; - if (a.x1 > a.x4) // These are the most likely to be extremal - minax = a.x4, maxax = a.x1; - else - minax = a.x1, maxax = a.x4; - - if (a.x3 < minax) - minax = a.x3; - else if (a.x3 > maxax) - maxax = a.x3; - - if (a.x2 < minax) - minax = a.x2; - else if (a.x2 > maxax) - maxax = a.x2; - - if (a.y1 > a.y4) - minay = a.y4, maxay = a.y1; - else - minay = a.y1, maxay = a.y4; - - if (a.y3 < minay) - minay = a.y3; - else if (a.y3 > maxay) - maxay = a.y3; - - if (a.y2 < minay) - minay = a.y2; - else if (a.y2 > maxay) - maxay = a.y2; - - // Compute bounding box for b - qreal minbx, maxbx, minby, maxby; - if (b.x1 > b.x4) - minbx = b.x4, maxbx = b.x1; - else - minbx = b.x1, maxbx = b.x4; - - if (b.x3 < minbx) - minbx = b.x3; - else if (b.x3 > maxbx) - maxbx = b.x3; - - if (b.x2 < minbx) - minbx = b.x2; - else if (b.x2 > maxbx) - maxbx = b.x2; - - if (b.y1 > b.y4) - minby = b.y4, maxby = b.y1; - else - minby = b.y1, maxby = b.y4; - - if (b.y3 < minby) - minby = b.y3; - else if (b.y3 > maxby) - maxby = b.y3; - - if (b.y2 < minby) - minby = b.y2; - else if (b.y2 > maxby) - maxby = b.y2; - - // Test bounding box of b against bounding box of a - if ((minax > maxbx) || (minay > maxby) // Not >= : need boundary case - || (minbx > maxax) || (minby > maxay)) - return 0; // they don't intersect - else - return 1; // they intersect -} -#endif - - #ifdef QDEBUG_BEZIER static QDebug operator<<(QDebug dbg, const QBezier &bz) { @@ -705,193 +623,6 @@ static QDebug operator<<(QDebug dbg, const QBezier &bz) } #endif -static bool RecursivelyIntersect(const QBezier &a, qreal t0, qreal t1, int deptha, - const QBezier &b, qreal u0, qreal u1, int depthb, - QVector > *t) -{ -#ifdef QDEBUG_BEZIER - static int I = 0; - int currentD = I; - fprintf(stderr, "%d) t0 = %lf, t1 = %lf, deptha = %d\n" - "u0 = %lf, u1 = %lf, depthb = %d\n", I++, t0, t1, deptha, - u0, u1, depthb); -#endif - if (deptha > 0) { - QBezier A[2]; - a.split(&A[0], &A[1]); - qreal tmid = (t0+t1)*0.5; - //qDebug()<<"\t1)"< 0) { - QBezier B[2]; - b.split(&B[0], &B[1]); - //qDebug()<<"\t3)"<isEmpty() : false; - } else { - if (IntersectBB(A[0], b)) { - //fprintf(stderr, "\t 5 from %d\n", currentD); - if (RecursivelyIntersect(A[0], t0, tmid, deptha, - b, u0, u1, depthb, - t) && !t) - return true; - } - if (IntersectBB(A[1], b)) { - //fprintf(stderr, "\t 6 from %d\n", currentD); - if (RecursivelyIntersect(A[1], tmid, t1, deptha, - b, u0, u1, depthb, - t) && !t) - return true; - } - return t ? !t->isEmpty() : false; - } - } else { - if (depthb > 0) { - QBezier B[2]; - b.split(&B[0], &B[1]); - qreal umid = (u0 + u1)*0.5; - depthb--; - if (IntersectBB(a, B[0])) { - //fprintf(stderr, "\t 7 from %d\n", currentD); - if (RecursivelyIntersect(a, t0, t1, deptha, - B[0], u0, umid, depthb, - t) && !t) - return true; - } - if (IntersectBB(a, B[1])) { - //fprintf(stderr, "\t 8 from %d\n", currentD); - if (RecursivelyIntersect(a, t0, t1, deptha, - B[1], umid, u1, depthb, - t) && !t) - return true; - } - return t ? !t->isEmpty() : false; - } - else { - // Both segments are fully subdivided; now do line segments - qreal xlk = a.x4 - a.x1; - qreal ylk = a.y4 - a.y1; - qreal xnm = b.x4 - b.x1; - qreal ynm = b.y4 - b.y1; - qreal xmk = b.x1 - a.x1; - qreal ymk = b.y1 - a.y1; - qreal det = xnm * ylk - ynm * xlk; - if (1.0 + det == 1.0) { - return false; - } else { - qreal detinv = 1.0 / det; - qreal rs = (xnm * ymk - ynm *xmk) * detinv; - qreal rt = (xlk * ymk - ylk * xmk) * detinv; - if ((rs < 0.0) || (rs > 1.0) || (rt < 0.0) || (rt > 1.0)) - return false; - - if (t) { - const qreal alpha_a = t0 + rs * (t1 - t0); - const qreal alpha_b = u0 + rt * (u1 - u0); - - *t << qMakePair(alpha_a, alpha_b); - } - - return true; - } - } - } -} - -QVector< QPair > QBezier::findIntersections(const QBezier &a, const QBezier &b) -{ - QVector< QPair > v(2); - findIntersections(a, b, &v); - return v; -} - -bool QBezier::findIntersections(const QBezier &a, const QBezier &b, - QVector > *t) -{ - if (IntersectBB(a, b)) { - QPointF la1(qFabs((a.x3 - a.x2) - (a.x2 - a.x1)), - qFabs((a.y3 - a.y2) - (a.y2 - a.y1))); - QPointF la2(qFabs((a.x4 - a.x3) - (a.x3 - a.x2)), - qFabs((a.y4 - a.y3) - (a.y3 - a.y2))); - QPointF la; - if (la1.x() > la2.x()) la.setX(la1.x()); else la.setX(la2.x()); - if (la1.y() > la2.y()) la.setY(la1.y()); else la.setY(la2.y()); - QPointF lb1(qFabs((b.x3 - b.x2) - (b.x2 - b.x1)), - qFabs((b.y3 - b.y2) - (b.y2 - b.y1))); - QPointF lb2(qFabs((b.x4 - b.x3) - (b.x3 - b.x2)), - qFabs((b.y4 - b.y3) - (b.y3 - b.y2))); - QPointF lb; - if (lb1.x() > lb2.x()) lb.setX(lb1.x()); else lb.setX(lb2.x()); - if (lb1.y() > lb2.y()) lb.setY(lb1.y()); else lb.setY(lb2.y()); - qreal l0; - if (la.x() > la.y()) - l0 = la.x(); - else - l0 = la.y(); - int ra; - if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0) - ra = 0; - else - ra = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0)); - if (lb.x() > lb.y()) - l0 = lb.x(); - else - l0 = lb.y(); - int rb; - if (l0 * 0.75 * M_SQRT2 + 1.0 == 1.0) - rb = 0; - else - rb = qCeil(log4(M_SQRT2 * 6.0 / 8.0 * INV_EPS * l0)); - - // if qreal is float then halve the number of subdivisions - if (sizeof(qreal) == 4) { - ra /= 2; - rb /= 2; - } - - return RecursivelyIntersect(a, 0., 1., ra, b, 0., 1., rb, t); - } - - //Don't sort here because it breaks the orders of corresponding - // intersections points. this way t's at the same locations correspond - // to the same intersection point. - //qSort(parameters[0].begin(), parameters[0].end(), qLess()); - //qSort(parameters[1].begin(), parameters[1].end(), qLess()); - - return false; -} - static inline void splitBezierAt(const QBezier &bez, qreal t, QBezier *left, QBezier *right) { @@ -920,42 +651,6 @@ static inline void splitBezierAt(const QBezier &bez, qreal t, right->y4 = bez.y4; } -QVector< QList > QBezier::splitAtIntersections(QBezier &b) -{ - QVector< QList > curves(2); - - QVector< QPair > allInters = findIntersections(*this, b); - - QList inters1; - QList inters2; - - for (int i = 0; i < allInters.size(); ++i) { - inters1 << allInters[i].first; - inters2 << allInters[i].second; - } - - qSort(inters1.begin(), inters1.end(), qLess()); - qSort(inters2.begin(), inters2.end(), qLess()); - - Q_ASSERT(inters1.count() == inters2.count()); - - int i; - for (i = 0; i < inters1.count(); ++i) { - qreal t1 = inters1.at(i); - qreal t2 = inters2.at(i); - - QBezier curve1, curve2; - parameterSplitLeft(t1, &curve1); - b.parameterSplitLeft(t2, &curve2); - curves[0].append(curve1); - curves[0].append(curve2); - } - curves[0].append(*this); - curves[1].append(b); - - return curves; -} - qreal QBezier::length(qreal error) const { qreal length = 0.0; diff --git a/src/gui/painting/qbezier_p.h b/src/gui/painting/qbezier_p.h index f015ea8..846635f 100644 --- a/src/gui/painting/qbezier_p.h +++ b/src/gui/painting/qbezier_p.h @@ -111,16 +111,7 @@ public: int shifted(QBezier *curveSegments, int maxSegmets, qreal offset, float threshold) const; - QVector< QList > splitAtIntersections(QBezier &a); - QBezier bezierOnInterval(qreal t0, qreal t1) const; - - static QVector< QPair > findIntersections(const QBezier &a, - const QBezier &b); - - static bool findIntersections(const QBezier &a, const QBezier &b, - QVector > *t); - QBezier getSubRange(qreal t0, qreal t1) const; qreal x1, y1, x2, y2, x3, y3, x4, y4; diff --git a/src/gui/painting/qpainterpath.cpp b/src/gui/painting/qpainterpath.cpp index 965b84c..f5a698e 100644 --- a/src/gui/painting/qpainterpath.cpp +++ b/src/gui/painting/qpainterpath.cpp @@ -3167,6 +3167,8 @@ void QPainterPath::addRoundRect(const QRectF &r, int xRnd, int yRnd) Set operations on paths will treat the paths as areas. Non-closed paths will be treated as implicitly closed. + Bezier curves may be flattened to line segments due to numerical instability of + doing bezier curve intersections. \sa intersected(), subtracted() */ @@ -3182,6 +3184,8 @@ QPainterPath QPainterPath::united(const QPainterPath &p) const \since 4.3 Returns a path which is the intersection of this path's fill area and \a p's fill area. + Bezier curves may be flattened to line segments due to numerical instability of + doing bezier curve intersections. */ QPainterPath QPainterPath::intersected(const QPainterPath &p) const { @@ -3198,7 +3202,8 @@ QPainterPath QPainterPath::intersected(const QPainterPath &p) const Set operations on paths will treat the paths as areas. Non-closed paths will be treated as implicitly closed. - + Bezier curves may be flattened to line segments due to numerical instability of + doing bezier curve intersections. */ QPainterPath QPainterPath::subtracted(const QPainterPath &p) const { @@ -3227,6 +3232,8 @@ QPainterPath QPainterPath::subtractedInverted(const QPainterPath &p) const Returns a simplified version of this path. This implies merging all subpaths that intersect, and returning a path containing no intersecting edges. Consecutive parallel lines will also be merged. The simplified path will always use the default fill rule, Qt::OddEvenFill. + Bezier curves may be flattened to line segments due to numerical instability of + doing bezier curve intersections. */ QPainterPath QPainterPath::simplified() const { diff --git a/src/gui/painting/qpathclipper.cpp b/src/gui/painting/qpathclipper.cpp index 00e74ba..4d319a4 100644 --- a/src/gui/painting/qpathclipper.cpp +++ b/src/gui/painting/qpathclipper.cpp @@ -105,22 +105,10 @@ public: bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const; private: - void intersectBeziers(const QBezier &one, const QBezier &two, QVector > &t, QDataBuffer &intersections); void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer &intersections); - - bool beziersIntersect(const QBezier &one, const QBezier &two) const; bool linesIntersect(const QLineF &a, const QLineF &b) const; }; -bool QIntersectionFinder::beziersIntersect(const QBezier &one, const QBezier &two) const -{ - return (comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2()) - && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4())) - || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3()) - && comparePoints(one.pt3(), two.pt2()) && comparePoints(one.pt4(), two.pt1())) - || QBezier::findIntersections(one, two, 0); -} - bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const { const QPointF p1 = a.p1(); @@ -193,48 +181,6 @@ bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const return tq >= 0 && tq <= 1; } -void QIntersectionFinder::intersectBeziers(const QBezier &one, const QBezier &two, QVector > &t, QDataBuffer &intersections) -{ - if ((comparePoints(one.pt1(), two.pt1()) && comparePoints(one.pt2(), two.pt2()) - && comparePoints(one.pt3(), two.pt3()) && comparePoints(one.pt4(), two.pt4())) - || (comparePoints(one.pt1(), two.pt4()) && comparePoints(one.pt2(), two.pt3()) - && comparePoints(one.pt3(), two.pt2()) && comparePoints(one.pt4(), two.pt1()))) { - - return; - } - - t.clear(); - - if (!QBezier::findIntersections(one, two, &t)) - return; - - int count = t.size(); - - for (int i = 0; i < count; ++i) { - qreal alpha_p = t.at(i).first; - qreal alpha_q = t.at(i).second; - - QPointF pt; - if (qFuzzyIsNull(alpha_p)) { - pt = one.pt1(); - } else if (qFuzzyIsNull(alpha_p - 1)) { - pt = one.pt4(); - } else if (qFuzzyIsNull(alpha_q)) { - pt = two.pt1(); - } else if (qFuzzyIsNull(alpha_q - 1)) { - pt = two.pt4(); - } else { - pt = one.pointAt(alpha_p); - } - - QIntersection intersection; - intersection.alphaA = alpha_p; - intersection.alphaB = alpha_q; - intersection.pos = pt; - intersections.add(intersection); - } -} - void QIntersectionFinder::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer &intersections) { const QPointF p1 = a.p1(); @@ -357,19 +303,8 @@ void QIntersectionFinder::intersectLines(const QLineF &a, const QLineF &b, QData intersections.add(intersection); } -static const QBezier bezierFromLine(const QLineF &line) -{ - const QPointF p1 = line.p1(); - const QPointF p2 = line.p2(); - const QPointF delta = (p2 - p1) / 3; - return QBezier::fromPoints(p1, p1 + delta, p1 + 2 * delta, p2); -} - bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const { - QBezier tempA; - QBezier tempB; - if (a.segments() == 0 || b.segments() == 0) return false; @@ -391,9 +326,6 @@ bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSe QRectF rb(minX, minY, maxX - minX, maxY - minY); for (int i = 0; i < a.segments(); ++i) { - const QBezier *bezierA = a.bezierAt(i); - bool isBezierA = bezierA != 0; - const QRectF &r1 = a.elementBounds(i); if (r1.left() > rb.right() || rb.left() > r1.right()) @@ -409,28 +341,8 @@ bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSe if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) continue; - bool isBezierB = b.bezierAt(j) != 0; - - if (isBezierA || isBezierB) { - const QBezier *bezierB; - if (isBezierB) { - bezierB = b.bezierAt(j); - } else { - tempB = bezierFromLine(b.lineAt(j)); - bezierB = &tempB; - } - - if (!bezierA) { - tempA = bezierFromLine(a.lineAt(i)); - bezierA = &tempA; - } - - if (beziersIntersect(*bezierA, *bezierB)) - return true; - } else { - if (linesIntersect(a.lineAt(i), b.lineAt(j))) - return true; - } + if (linesIntersect(a.lineAt(i), b.lineAt(j))) + return true; } } @@ -439,16 +351,10 @@ bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSe void QIntersectionFinder::produceIntersections(QPathSegments &segments) { - QBezier tempA; - QBezier tempB; - QVector > t; QDataBuffer intersections; for (int i = 0; i < segments.segments(); ++i) { - const QBezier *bezierA = segments.bezierAt(i); - bool isBezierA = bezierA != 0; - const QRectF &r1 = segments.elementBounds(i); for (int j = 0; j < i; ++j) { @@ -461,29 +367,10 @@ void QIntersectionFinder::produceIntersections(QPathSegments &segments) intersections.reset(); - bool isBezierB = segments.bezierAt(j) != 0; - - if (isBezierA || isBezierB) { - const QBezier *bezierB; - if (isBezierB) { - bezierB = segments.bezierAt(j); - } else { - tempB = bezierFromLine(segments.lineAt(j)); - bezierB = &tempB; - } - - if (!bezierA) { - tempA = bezierFromLine(segments.lineAt(i)); - bezierA = &tempA; - } + const QLineF lineA = segments.lineAt(i); + const QLineF lineB = segments.lineAt(j); - intersectBeziers(*bezierA, *bezierB, t, intersections); - } else { - const QLineF lineA = segments.lineAt(i); - const QLineF lineB = segments.lineAt(j); - - intersectLines(lineA, lineB, intersections); - } + intersectLines(lineA, lineB, intersections); for (int k = 0; k < intersections.size(); ++k) { QPathSegments::Intersection i_isect, j_isect; @@ -731,53 +618,34 @@ void QWingedEdge::intersectAndAdd() qSort(intersections.data(), intersections.data() + intersections.size()); - const QBezier *bezier = m_segments.bezierAt(i); - if (bezier) { - int first = m_segments.segmentAt(i).va; - int second = m_segments.segmentAt(i).vb; + int first = m_segments.segmentAt(i).va; + int second = m_segments.segmentAt(i).vb; - qreal alpha = 0.0; - int last = first; - for (int j = 0; j < intersections.size(); ++j) { - const QPathSegments::Intersection &isect = intersections.at(j); + int last = first; + for (int j = 0; j < intersections.size(); ++j) { + const QPathSegments::Intersection &isect = intersections.at(j); - addBezierEdge(bezier, last, isect.vertex, alpha, isect.t, pathId); - - alpha = isect.t; - last = isect.vertex; - } - - addBezierEdge(bezier, last, second, alpha, 1.0, pathId); - } else { - int first = m_segments.segmentAt(i).va; - int second = m_segments.segmentAt(i).vb; - - int last = first; - for (int j = 0; j < intersections.size(); ++j) { - const QPathSegments::Intersection &isect = intersections.at(j); - - QPathEdge *ep = edge(addEdge(last, isect.vertex)); - - if (ep) { - const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1; - if (pathId == 0) - ep->windingA += dir; - else - ep->windingB += dir; - } - - last = isect.vertex; - } - - QPathEdge *ep = edge(addEdge(last, second)); + QPathEdge *ep = edge(addEdge(last, isect.vertex)); if (ep) { - const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1; + const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1; if (pathId == 0) ep->windingA += dir; else ep->windingB += dir; } + + last = isect.vertex; + } + + QPathEdge *ep = edge(addEdge(last, second)); + + if (ep) { + const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1; + if (pathId == 0) + ep->windingA += dir; + else + ep->windingB += dir; } } } @@ -832,7 +700,6 @@ static bool isLine(const QBezier &bezier) void QPathSegments::setPath(const QPainterPath &path) { m_points.reset(); - m_beziers.reset(); m_intersections.reset(); m_segments.reset(); @@ -845,6 +712,9 @@ void QPathSegments::addPath(const QPainterPath &path) { int firstSegment = m_segments.size(); + QRectF pathBounds = path.boundingRect(); + qreal invPathScale = 1 / qMax(pathBounds.width(), pathBounds.height()); + bool hasMoveTo = false; int lastMoveTo = 0; int last = 0; @@ -879,8 +749,26 @@ void QPathSegments::addPath(const QPainterPath &path) if (isLine(bezier)) { m_segments << Segment(m_pathId, last, current); } else { - m_segments << Segment(m_pathId, last, current, m_beziers.size()); - m_beziers << bezier; + QRectF bounds = bezier.bounds(); + + qreal segmentScale = qMax(bounds.width(), bounds.height()); + + // threshold based on same algorithm as in qtriangulatingstroker.cpp + int threshold = qMin(64, segmentScale * invPathScale * (512 * 3.14f / 6)); + if (threshold < 3) threshold = 3; + qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1); + + for (int t = 1; t < threshold - 1; ++t) { + currentPoint = bezier.pointAt(t * one_over_threshold_minus_1); + + int index = m_points.size(); + m_segments << Segment(m_pathId, last, index); + last = index; + + m_points << currentPoint; + } + + m_segments << Segment(m_pathId, last, current); } } last = current; @@ -896,24 +784,19 @@ void QPathSegments::addPath(const QPainterPath &path) m_segments << Segment(m_pathId, last, lastMoveTo); for (int i = firstSegment; i < m_segments.size(); ++i) { - const QBezier *bezier = bezierAt(i); - if (bezier) { - m_segments.at(i).bounds = bezier->bounds(); - } else { - const QLineF line = lineAt(i); + const QLineF line = lineAt(i); - qreal x1 = line.p1().x(); - qreal y1 = line.p1().y(); - qreal x2 = line.p2().x(); - qreal y2 = line.p2().y(); + qreal x1 = line.p1().x(); + qreal y1 = line.p1().y(); + qreal x2 = line.p2().x(); + qreal y2 = line.p2().y(); - if (x2 < x1) - qSwap(x1, x2); - if (y2 < y1) - qSwap(y1, y2); + if (x2 < x1) + qSwap(x1, x2); + if (y2 < y1) + qSwap(y1, y2); - m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1); - } + m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1); } ++m_pathId; @@ -948,28 +831,17 @@ static inline QPointF tangentAt(const QWingedEdge &list, int vi, int ei) const QPathEdge *ep = list.edge(ei); Q_ASSERT(ep); - qreal t; qreal sign; if (ep->first == vi) { - t = ep->t0; sign = 1; } else { - t = ep->t1; sign = -1; } - QPointF normal; - if (ep->bezier) { - normal = ep->bezier->derivedAt(t); - - if (qFuzzyIsNull(normal.x()) && qFuzzyIsNull(normal.y())) - normal = ep->bezier->secondDerivedAt(t); - } else { - const QPointF a = *list.vertex(ep->first); - const QPointF b = *list.vertex(ep->second); - normal = b - a; - } + const QPointF a = *list.vertex(ep->first); + const QPointF b = *list.vertex(ep->second); + QPointF normal = b - a; return normalize(sign * normal); } @@ -979,83 +851,9 @@ static inline QPointF midPoint(const QWingedEdge &list, int ei) const QPathEdge *ep = list.edge(ei); Q_ASSERT(ep); - if (ep->bezier) { - return ep->bezier->pointAt(0.5 * (ep->t0 + ep->t1)); - } else { - const QPointF a = *list.vertex(ep->first); - const QPointF b = *list.vertex(ep->second); - return a + 0.5 * (b - a); - } -} - -static QBezier transform(const QBezier &bezier, const QPointF &xAxis, const QPointF &yAxis, const QPointF &origin) -{ - QPointF points[4] = { - bezier.pt1(), - bezier.pt2(), - bezier.pt3(), - bezier.pt4() - }; - - for (int i = 0; i < 4; ++i) { - const QPointF p = points[i] - origin; - - points[i].rx() = dot(xAxis, p); - points[i].ry() = dot(yAxis, p); - } - - return QBezier::fromPoints(points[0], points[1], points[2], points[3]); -} - -static bool isLeftOf(const QWingedEdge &list, int vi, int ai, int bi) -{ - const QPathEdge *ap = list.edge(ai); - const QPathEdge *bp = list.edge(bi); - - Q_ASSERT(ap); - Q_ASSERT(bp); - - if (!(ap->bezier || bp->bezier)) - return false; - - const QPointF tangent = tangentAt(list, vi, ai); - const QPointF normal(tangent.y(), -tangent.x()); - - const QPointF origin = *list.vertex(vi); - - const QPointF dpA = midPoint(list, ai) - origin; - const QPointF dpB = midPoint(list, bi) - origin; - - qreal xA = dot(normal, dpA); - qreal xB = dot(normal, dpB); - - if (xA <= 0 && xB >= 0) - return true; - - if (xA >= 0 && xB <= 0) - return false; - - if (!ap->bezier) - return xB > 0; - - if (!bp->bezier) - return xA < 0; - - // both are beziers on the same side of the tangent - - // transform the beziers into the local coordinate system - // such that positive y is along the tangent, and positive x is along the normal - - QBezier bezierA = transform(*ap->bezier, normal, tangent, origin); - QBezier bezierB = transform(*bp->bezier, normal, tangent, origin); - - qreal y = qMin(bezierA.pointAt(0.5 * (ap->t0 + ap->t1)).y(), - bezierB.pointAt(0.5 * (bp->t0 + bp->t1)).y()); - - xA = bezierA.pointAt(bezierA.tForY(ap->t0, ap->t1, y)).x(); - xB = bezierB.pointAt(bezierB.tForY(bp->t0, bp->t1, y)).x(); - - return xA < xB; + const QPointF a = *list.vertex(ep->first); + const QPointF b = *list.vertex(ep->second); + return a + 0.5 * (b - a); } QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const @@ -1084,7 +882,6 @@ QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const status.flip(); Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi); - qreal d2 = delta(vi, ei, status.edge); #ifdef QDEBUG_CLIPPER @@ -1092,8 +889,7 @@ QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle; #endif - if (!(qFuzzyIsNull(d2) && isLeftOf(*this, vi, status.edge, ei)) - && (d2 < d || (qFuzzyCompare(d2, d) && isLeftOf(*this, vi, status.edge, position)))) { + if (d2 < d) { position = status.edge; d = d2; } @@ -1210,15 +1006,15 @@ static qreal computeAngle(const QPointF &v) #endif } -int QWingedEdge::addEdge(const QPointF &a, const QPointF &b, const QBezier *bezier, qreal t0, qreal t1) +int QWingedEdge::addEdge(const QPointF &a, const QPointF &b) { int fi = insert(a); int si = insert(b); - return addEdge(fi, si, bezier, t0, t1); + return addEdge(fi, si); } -int QWingedEdge::addEdge(int fi, int si, const QBezier *bezier, qreal t0, qreal t1) +int QWingedEdge::addEdge(int fi, int si) { if (fi == si) return -1; @@ -1236,29 +1032,11 @@ int QWingedEdge::addEdge(int fi, int si, const QBezier *bezier, qreal t0, qreal QPathEdge *ep = edge(ei); - ep->bezier = bezier; - ep->t0 = t0; - ep->t1 = t1; - - if (bezier) { - QPointF aTangent = bezier->derivedAt(t0); - QPointF bTangent = -bezier->derivedAt(t1); - - if (qFuzzyIsNull(aTangent.x()) && qFuzzyIsNull(aTangent.y())) - aTangent = bezier->secondDerivedAt(t0); - - if (qFuzzyIsNull(bTangent.x()) && qFuzzyIsNull(bTangent.y())) - bTangent = bezier->secondDerivedAt(t1); - - ep->angle = computeAngle(aTangent); - ep->invAngle = computeAngle(bTangent); - } else { - const QPointF tangent = QPointF(*sp) - QPointF(*fp); - ep->angle = computeAngle(tangent); - ep->invAngle = ep->angle + 64; - if (ep->invAngle >= 128) - ep->invAngle -= 128; - } + const QPointF tangent = QPointF(*sp) - QPointF(*fp); + ep->angle = computeAngle(tangent); + ep->invAngle = ep->angle + 64; + if (ep->invAngle >= 128) + ep->invAngle -= 128; QPathVertex *vertices[2] = { fp, sp }; QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward }; @@ -1313,74 +1091,6 @@ int QWingedEdge::addEdge(int fi, int si, const QBezier *bezier, qreal t0, qreal return ei; } -void QWingedEdge::addBezierEdge(const QBezier *bezier, int vertexA, int vertexB, qreal alphaA, qreal alphaB, int path) -{ - if (qFuzzyCompare(alphaA, alphaB)) - return; - - qreal alphaMid = (alphaA + alphaB) * 0.5; - - qreal s0 = 0; - qreal s1 = 1; - int count = bezier->stationaryYPoints(s0, s1); - - m_splitPoints.clear(); - m_splitPoints << alphaA; - m_splitPoints << alphaMid; - m_splitPoints << alphaB; - - if (count > 0 && !qFuzzyCompare(s0, alphaA) && !qFuzzyCompare(s0, alphaMid) && !qFuzzyCompare(s0, alphaB) && s0 > alphaA && s0 < alphaB) - m_splitPoints << s0; - - if (count > 1 && !qFuzzyCompare(s1, alphaA) && !qFuzzyCompare(s1, alphaMid) && !qFuzzyCompare(s1, alphaB) && s1 > alphaA && s1 < alphaB) - m_splitPoints << s1; - - if (count > 0) - qSort(m_splitPoints.begin(), m_splitPoints.end()); - - int last = vertexA; - for (int i = 0; i < m_splitPoints.size() - 1; ++i) { - const qreal t0 = m_splitPoints[i]; - const qreal t1 = m_splitPoints[i+1]; - - int current; - if ((i + 1) == (m_splitPoints.size() - 1)) { - current = vertexB; - } else { - current = insert(bezier->pointAt(t1)); - } - - QPathEdge *ep = edge(addEdge(last, current, bezier, t0, t1)); - - if (ep) { - const int dir = m_vertices.at(last).y < m_vertices.at(current).y ? 1 : -1; - if (path == 0) - ep->windingA += dir; - else - ep->windingB += dir; - } - - last = current; - } -} - -void QWingedEdge::addBezierEdge(const QBezier *bezier, const QPointF &a, const QPointF &b, qreal alphaA, qreal alphaB, int path) -{ - if (qFuzzyCompare(alphaA, alphaB)) - return; - - if (comparePoints(a, b)) { - int v = insert(a); - - addBezierEdge(bezier, v, v, alphaA, alphaB, path); - } else { - int va = insert(a); - int vb = insert(b); - - addBezierEdge(bezier, va, vb, alphaA, alphaB, path); - } -} - int QWingedEdge::insert(const QPathVertex &vertex) { if (!m_vertices.isEmpty()) { @@ -1429,37 +1139,12 @@ static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge status.traversal = traversal; status.direction = QPathEdge::Forward; - const QBezier *bezier = 0; - qreal t0 = 1; - qreal t1 = 0; - bool forward = true; - path.moveTo(*list.vertex(list.edge(edge)->first)); do { const QPathEdge *ep = list.edge(status.edge); - if (ep->bezier != bezier || (bezier && t0 != ep->t1 && t1 != ep->t0)) { - if (bezier) { - QBezier sub = bezier->bezierOnInterval(t0, t1); - - if (forward) - path.cubicTo(sub.pt2(), sub.pt3(), sub.pt4()); - else - path.cubicTo(sub.pt3(), sub.pt2(), sub.pt1()); - } - - bezier = ep->bezier; - t0 = 1; - t1 = 0; - forward = status.direction == QPathEdge::Forward; - } - - if (ep->bezier) { - t0 = qMin(t0, ep->t0); - t1 = qMax(t1, ep->t1); - } else - addLineTo(path, *list.vertex(ep->vertex(status.direction))); + addLineTo(path, *list.vertex(ep->vertex(status.direction))); if (status.traversal == QPathEdge::LeftTraversal) ep->flag &= ~16; @@ -1468,14 +1153,6 @@ static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge status = list.next(status); } while (status.edge != edge); - - if (bezier) { - QBezier sub = bezier->bezierOnInterval(t0, t1); - if (forward) - path.cubicTo(sub.pt2(), sub.pt3(), sub.pt4()); - else - path.cubicTo(sub.pt3(), sub.pt2(), sub.pt1()); - } } void QWingedEdge::simplify() @@ -1559,7 +1236,7 @@ bool QPathClipper::intersect() } } - return false; + return !clipPath.intersected(subjectPath).isEmpty(); } bool QPathClipper::contains() @@ -1596,7 +1273,7 @@ bool QPathClipper::contains() } } - return true; + return clipPath.subtracted(subjectPath).isEmpty(); } QPathClipper::QPathClipper(const QPainterPath &subject, @@ -1937,25 +1614,10 @@ bool QWingedEdge::isInside(qreal x, qreal y) const QPointF b = *vertex(ep->second); if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { - if (ep->bezier) { - qreal maxX = qMax(a.x(), qMax(b.x(), qMax(ep->bezier->x2, ep->bezier->x3))); - qreal minX = qMin(a.x(), qMin(b.x(), qMin(ep->bezier->x2, ep->bezier->x3))); - - if (minX > x) { - winding += w; - } else if (maxX > x) { - const qreal t = ep->bezier->tForY(ep->t0, ep->t1, y); - const qreal intersection = ep->bezier->pointAt(t).x(); - - if (intersection > x) - winding += w; - } - } else { - qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); + qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); - if (intersectionX > x) - winding += w; - } + if (intersectionX > x) + winding += w; } } @@ -1971,17 +1633,9 @@ static QVector findCrossings(const QWingedEdge &list, qreal y) QPointF b = *list.vertex(edge->second); if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { - if (edge->bezier) { - const qreal t = edge->bezier->tForY(edge->t0, edge->t1, y); - const qreal intersection = edge->bezier->pointAt(t).x(); - - const QCrossingEdge edge = { i, intersection }; - crossings << edge; - } else { - const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); - const QCrossingEdge edge = { i, intersection }; - crossings << edge; - } + const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); + const QCrossingEdge edge = { i, intersection }; + crossings << edge; } } return crossings; diff --git a/src/gui/painting/qpathclipper_p.h b/src/gui/painting/qpathclipper_p.h index b42dc1d..7962400 100644 --- a/src/gui/painting/qpathclipper_p.h +++ b/src/gui/painting/qpathclipper_p.h @@ -151,10 +151,6 @@ public: qreal angle; qreal invAngle; - const QBezier *bezier; - qreal t0; - qreal t1; - int next(Traversal traversal, Direction direction) const; void setNext(Traversal traversal, Direction direction, int next); @@ -182,9 +178,8 @@ public: }; struct Segment { - Segment(int pathId, int vertexA, int vertexB, int bezierIndex = -1) + Segment(int pathId, int vertexA, int vertexB) : path(pathId) - , bezier(bezierIndex) , va(vertexA) , vb(vertexB) , intersection(-1) @@ -192,7 +187,6 @@ public: } int path; - int bezier; // vertices int va; @@ -216,7 +210,6 @@ public: const Segment &segmentAt(int index) const; const QLineF lineAt(int index) const; - const QBezier *bezierAt(int index) const; const QRectF &elementBounds(int index) const; int pathId(int index) const; @@ -231,7 +224,6 @@ public: private: QDataBuffer m_points; QDataBuffer m_segments; - QDataBuffer m_beziers; QDataBuffer m_intersections; int m_pathId; @@ -272,8 +264,8 @@ public: TraversalStatus next(const TraversalStatus &status) const; - int addEdge(const QPointF &a, const QPointF &b, const QBezier *bezier = 0, qreal t0 = 0, qreal t1 = 1); - int addEdge(int vertexA, int vertexB, const QBezier *bezier = 0, qreal t0 = 0, qreal t1 = 1); + int addEdge(const QPointF &a, const QPointF &b); + int addEdge(int vertexA, int vertexB); bool isInside(qreal x, qreal y) const; @@ -285,11 +277,7 @@ private: void printNode(int i, FILE *handle); - QBezier bezierFromIndex(int index) const; - void removeEdge(int ei); - void addBezierEdge(const QBezier *bezier, const QPointF &a, const QPointF &b, qreal alphaA, qreal alphaB, int path); - void addBezierEdge(const QBezier *bezier, int vertexA, int vertexB, qreal alphaA, qreal alphaB, int path); int insert(const QPathVertex &vertex); TraversalStatus findInsertStatus(int vertex, int edge) const; @@ -312,9 +300,6 @@ inline QPathEdge::QPathEdge(int a, int b) , second(b) , angle(0) , invAngle(0) - , bezier(0) - , t0(0) - , t1(0) { m_next[0][0] = -1; m_next[1][0] = -1; @@ -396,15 +381,6 @@ inline const QLineF QPathSegments::lineAt(int index) const return QLineF(m_points.at(segment.va), m_points.at(segment.vb)); } -inline const QBezier *QPathSegments::bezierAt(int index) const -{ - const Segment &segment = m_segments.at(index); - if (segment.bezier >= 0) - return &m_beziers.at(segment.bezier); - else - return 0; -} - inline const QRectF &QPathSegments::elementBounds(int index) const { return m_segments.at(index).bounds; diff --git a/src/s60installs/bwins/QtGuiu.def b/src/s60installs/bwins/QtGuiu.def index a948f73..1bcc619 100644 --- a/src/s60installs/bwins/QtGuiu.def +++ b/src/s60installs/bwins/QtGuiu.def @@ -4417,8 +4417,8 @@ EXPORTS ?findData@QComboBox@@QBEHABVQVariant@@HV?$QFlags@W4MatchFlag@Qt@@@@@Z @ 4416 NONAME ; int QComboBox::findData(class QVariant const &, int, class QFlags) const ?findFont@QFontDatabase@@CAPAVQFontEngine@@HPBVQFontPrivate@@ABUQFontDef@@@Z @ 4417 NONAME ; class QFontEngine * QFontDatabase::findFont(int, class QFontPrivate const *, struct QFontDef const &) ?findInMask@QLineControl@@ABEHH_N0VQChar@@@Z @ 4418 NONAME ; int QLineControl::findInMask(int, bool, bool, class QChar) const - ?findIntersections@QBezier@@SA?AV?$QVector@U?$QPair@MM@@@@ABV1@0@Z @ 4419 NONAME ; class QVector > QBezier::findIntersections(class QBezier const &, class QBezier const &) - ?findIntersections@QBezier@@SA_NABV1@0PAV?$QVector@U?$QPair@MM@@@@@Z @ 4420 NONAME ; bool QBezier::findIntersections(class QBezier const &, class QBezier const &, class QVector > *) + ?findIntersections@QBezier@@SA?AV?$QVector@U?$QPair@MM@@@@ABV1@0@Z @ 4419 NONAME ABSENT ; class QVector > QBezier::findIntersections(class QBezier const &, class QBezier const &) + ?findIntersections@QBezier@@SA_NABV1@0PAV?$QVector@U?$QPair@MM@@@@@Z @ 4420 NONAME ABSENT ; bool QBezier::findIntersections(class QBezier const &, class QBezier const &, class QVector > *) ?findItem@QTextEngine@@QBEHH@Z @ 4421 NONAME ; int QTextEngine::findItem(int) const ?findItems@QListWidget@@QBE?AV?$QList@PAVQListWidgetItem@@@@ABVQString@@V?$QFlags@W4MatchFlag@Qt@@@@@Z @ 4422 NONAME ; class QList QListWidget::findItems(class QString const &, class QFlags) const ?findItems@QStandardItemModel@@QBE?AV?$QList@PAVQStandardItem@@@@ABVQString@@V?$QFlags@W4MatchFlag@Qt@@@@H@Z @ 4423 NONAME ; class QList QStandardItemModel::findItems(class QString const &, class QFlags, int) const @@ -10501,7 +10501,7 @@ EXPORTS ?speed@QMovie@@QBEHXZ @ 10500 NONAME ; int QMovie::speed(void) const ?split@QBezier@@QBEXPAV1@0@Z @ 10501 NONAME ; void QBezier::split(class QBezier *, class QBezier *) const ?split@QItemSelection@@SAXABVQItemSelectionRange@@0PAV1@@Z @ 10502 NONAME ; void QItemSelection::split(class QItemSelectionRange const &, class QItemSelectionRange const &, class QItemSelection *) - ?splitAtIntersections@QBezier@@QAE?AV?$QVector@V?$QList@VQBezier@@@@@@AAV1@@Z @ 10503 NONAME ; class QVector > QBezier::splitAtIntersections(class QBezier &) + ?splitAtIntersections@QBezier@@QAE?AV?$QVector@V?$QList@VQBezier@@@@@@AAV1@@Z @ 10503 NONAME ABSENT ; class QVector > QBezier::splitAtIntersections(class QBezier &) ?splitCell@QTextTable@@QAEXHHHH@Z @ 10504 NONAME ; void QTextTable::splitCell(int, int, int, int) ?splitDockWidget@QMainWindow@@QAEXPAVQDockWidget@@0W4Orientation@Qt@@@Z @ 10505 NONAME ; void QMainWindow::splitDockWidget(class QDockWidget *, class QDockWidget *, enum Qt::Orientation) ?splitItem@QTextEngine@@ABEXHH@Z @ 10506 NONAME ; void QTextEngine::splitItem(int, int) const diff --git a/src/s60installs/eabi/QtGuiu.def b/src/s60installs/eabi/QtGuiu.def index cadcf59..a735de1 100644 --- a/src/s60installs/eabi/QtGuiu.def +++ b/src/s60installs/eabi/QtGuiu.def @@ -5907,9 +5907,9 @@ EXPORTS _ZN7QActionD1Ev @ 5906 NONAME _ZN7QActionD2Ev @ 5907 NONAME _ZN7QBezier10fromPointsERK7QPointFS2_S2_S2_ @ 5908 NONAME - _ZN7QBezier17findIntersectionsERKS_S1_ @ 5909 NONAME - _ZN7QBezier17findIntersectionsERKS_S1_P7QVectorI5QPairIffEE @ 5910 NONAME - _ZN7QBezier20splitAtIntersectionsERS_ @ 5911 NONAME + _ZN7QBezier17findIntersectionsERKS_S1_ @ 5909 NONAME ABSENT + _ZN7QBezier17findIntersectionsERKS_S1_P7QVectorI5QPairIffEE @ 5910 NONAME ABSENT + _ZN7QBezier20splitAtIntersectionsERS_ @ 5911 NONAME ABSENT _ZN7QBitmap8fromDataERK5QSizePKhN6QImage6FormatE @ 5912 NONAME _ZN7QBitmap9fromImageERK6QImage6QFlagsIN2Qt19ImageConversionFlagEE @ 5913 NONAME _ZN7QBitmapC1ERK5QSize @ 5914 NONAME diff --git a/tests/auto/qpathclipper/tst_qpathclipper.cpp b/tests/auto/qpathclipper/tst_qpathclipper.cpp index db5a13e..4dc12cb 100644 --- a/tests/auto/qpathclipper/tst_qpathclipper.cpp +++ b/tests/auto/qpathclipper/tst_qpathclipper.cpp @@ -285,46 +285,6 @@ static QPainterPath samplePath10() return path; } -static QPainterPath samplePath11() -{ - QPainterPath path; - path.moveTo(QPointF(165.71429, 338.79076)); - path.lineTo(QPointF(227.74288, 338.79076)); - path.cubicTo(QPointF(232.95048, 338.79076), - QPointF(237.14288, 342.88102), - QPointF(237.14288, 347.96176)); - path.lineTo(QPointF(237.14288, 366.76261)); - path.cubicTo(QPointF(237.14288, 371.84335), - QPointF(232.95048, 375.93361), - QPointF(227.74288, 375.93361)); - path.lineTo(QPointF(165.7142905131896, 375.93361)); - path.lineTo(QPointF(165.71429, 338.79076)); - return path; -} -static QPainterPath samplePath12() -{ - QPainterPath path; - path.moveTo(QPointF(333.297085225735, 61.53486494396167)); - path.cubicTo(QPointF(339.851755668807, 65.26555884471786), - QPointF(346.7164458828328, 69.04482864715078), - QPointF(353.4159970843586, 72.56059416636147)); - path.cubicTo(QPointF(353.4166971116034, 72.56155590850551), - QPointF(353.4173961086004, 72.56251809989483), - QPointF(353.4180950127331, 72.56348028832946)); - path.cubicTo(QPointF(342.4340366381152, 76.42344228577481), - QPointF(317.0596805768079, 94.67086588954379), - QPointF(309.78055, 101.00195)); - path.cubicTo(QPointF(286.0370715501102, 121.6530659984711), - QPointF(272.7748256344584, 134.1525788344904), - QPointF(250.7436468364447, 150.4434491585085)); - path.lineTo(QPointF(247.03629, 146.56585)); - path.lineTo(QPointF(240.71086, 91.501867)); - path.cubicTo(QPointF(240.71086, 91.501867), - QPointF(305.6382515924416, 62.21715375368672), - QPointF(333.297085225735, 61.53486494396167)); - return path; -} - static QPainterPath samplePath13() { QPainterPath path; @@ -412,16 +372,6 @@ void tst_QPathClipper::clip_data() << QPathClipper::BoolAnd << samplePath10(); - QTest::newRow( "simple11" ) << Paths::frame2()*QTransform().translate(40, 235) - << Paths::frame1() - << QPathClipper::BoolAnd - << samplePath11(); - - QTest::newRow( "intersection_at_edge" ) << Paths::lips() - << Paths::mailbox()*QTransform().translate(-85, 34) - << QPathClipper::BoolAnd - << samplePath12(); - QTest::newRow( "simple_move_to1" ) << Paths::rect4() << Paths::rect2() * QTransform().translate(-20, 50) << QPathClipper::BoolAnd -- cgit v0.12