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

1 files changed, 0 insertions, 305 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<QPair<qreal, qreal> > *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)"<<A[0];
-        //qDebug()<<"\t2)"<<A[1];
-	deptha--;
-	if (depthb > 0) {
-	    QBezier B[2];
-            b.split(&B[0], &B[1]);
-            //qDebug()<<"\t3)"<<B[0];
-            //qDebug()<<"\t4)"<<B[1];
-	    qreal umid = (u0+u1)*0.5;
-	    depthb--;
-	    if (IntersectBB(A[0], B[0])) {
-                //fprintf(stderr, "\t 1 from %d\n", currentD);
-		if (RecursivelyIntersect(A[0], t0, tmid, deptha,
-				     B[0], u0, umid, depthb,
-				     t) && !t)
-                    return true;
-            }
-	    if (IntersectBB(A[1], B[0])) {
-                //fprintf(stderr, "\t 2 from %d\n", currentD);
-		if (RecursivelyIntersect(A[1], tmid, t1, deptha,
-                                     B[0], u0, umid, depthb,
-                                     t) && !t)
-                    return true;
-            }
-	    if (IntersectBB(A[0], B[1])) {
-                //fprintf(stderr, "\t 3 from %d\n", currentD);
-		if (RecursivelyIntersect(A[0], t0, tmid, deptha,
-                                     B[1], umid, u1, depthb,
-                                     t) && !t)
-                    return true;
-            }
-	    if (IntersectBB(A[1], B[1])) {
-                //fprintf(stderr, "\t 4 from %d\n", currentD);
-		if (RecursivelyIntersect(A[1], tmid, t1, deptha,
-				     B[1], umid, u1, depthb,
-				     t) && !t)
-                    return true;
-            }
-            return t ? !t->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<qreal, qreal> > QBezier::findIntersections(const QBezier &a, const QBezier &b)
-{
-    QVector< QPair<qreal, qreal> > v(2);
-    findIntersections(a, b, &v);
-    return v;
-}
-
-bool QBezier::findIntersections(const QBezier &a, const QBezier &b,
-                                QVector<QPair<qreal, qreal> > *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<qreal>());
-    //qSort(parameters[1].begin(), parameters[1].end(), qLess<qreal>());
-
-    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> > QBezier::splitAtIntersections(QBezier &b)
-{
-    QVector< QList<QBezier> > curves(2);
-
-    QVector< QPair<qreal, qreal> > allInters = findIntersections(*this, b);
-
-    QList<qreal> inters1;
-    QList<qreal> inters2;
-
-    for (int i = 0; i < allInters.size(); ++i) {
-        inters1 << allInters[i].first;
-        inters2 << allInters[i].second;
-    }
-
-    qSort(inters1.begin(), inters1.end(), qLess<qreal>());
-    qSort(inters2.begin(), inters2.end(), qLess<qreal>());
-
-    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;