qbezier.cpp

奇趣公司比较新的qt/emd版本

                    fabs((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(fabs((b.x3 - b.x2) - (b.x2 - b.x1)),
                    fabs((b.y3 - b.y2) - (b.y2 - b.y1)));
	QPointF lb2(fabs((b.x4 - b.x3) - (b.x3 - b.x2)),
                    fabs((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));

	RecursivelyIntersect(a, 0., 1., ra, b, 0., 1., rb, ta, tb);
    }

    //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 !ta.isEmpty();
}

static inline void splitBezierAt(const QBezier &bez, qreal t,
                                 QBezier *left, QBezier *right)
{
    left->x1 = bez.x1;
    left->y1 = bez.y1;

    left->x2 = bez.x1 + t * ( bez.x2 - bez.x1 );
    left->y2 = bez.y1 + t * ( bez.y2 - bez.y1 );

    left->x3 = bez.x2 + t * ( bez.x3 - bez.x2 ); // temporary holding spot
    left->y3 = bez.y2 + t * ( bez.y3 - bez.y2 ); // temporary holding spot

    right->x3 = bez.x3 + t * ( bez.x4 - bez.x3 );
    right->y3 = bez.y3 + t * ( bez.y4 - bez.y3 );

    right->x2 = left->x3 + t * ( right->x3 - left->x3);
    right->y2 = left->y3 + t * ( right->y3 - left->y3);

    left->x3 = left->x2 + t * ( left->x3 - left->x2 );
    left->y3 = left->y2 + t * ( left->y3 - left->y2 );

    left->x4 = right->x1 = left->x3 + t * (right->x2 - left->x3);
    left->y4 = right->y1 = left->y3 + t * (right->y2 - left->y3);

    right->x4 = bez.x4;
    right->y4 = bez.y4;
}

QVector< QList<QBezier> > QBezier::splitAtIntersections(QBezier &b)
{
    QVector< QList<QBezier> > curves(2);

    QVector< QList<qreal> > allInters = findIntersections(*this, b);

    QList<qreal> &inters1 = allInters[0];
    QList<qreal> &inters2 = allInters[1];

    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;

    addIfClose(&length, error);

    return length;
}

void QBezier::addIfClose(qreal *length, qreal error) const
{
    QBezier left, right;     /* bez poly splits */

    qreal len = 0.0;        /* arc length */
    qreal chord;            /* chord length */

    len = len + QLineF(QPointF(x1, y1),QPointF(x2, y2)).length();
    len = len + QLineF(QPointF(x2, y2),QPointF(x3, y3)).length();
    len = len + QLineF(QPointF(x3, y3),QPointF(x4, y4)).length();

    chord = QLineF(QPointF(x1, y1),QPointF(x4, y4)).length();

    if((len-chord) > error) {
        split(&left, &right);                 /* split in two */
        left.addIfClose(length, error);       /* try left side */
        right.addIfClose(length, error);      /* try right side */
        return;
    }

    *length = *length + len;

    return;
}

qreal QBezier::tForY(qreal t0, qreal t1, qreal y) const
{
    qreal py0 = pointAt(t0).y();
    qreal py1 = pointAt(t1).y();

    if (py0 > py1) {
        qSwap(py0, py1);
        qSwap(t0, t1);
    }

    Q_ASSERT(py0 <= py1);

    if (py0 >= y)
        return t0;
    else if (py1 <= y)
        return t1;

    Q_ASSERT(py0 < y && y < py1);

    do {
        qreal t = 0.5 * (t0 + t1);

        qreal a, b, c, d;
        QBezier::coefficients(t, a, b, c, d);
        qreal yt = a * y1 + b * y2 + c * y3 + d * y4;

        if (yt < y) {
            t0 = t;
            py0 = yt;
        } else {
            t1 = t;
            py1 = yt;
        }
    } while (qAbs(y - py0) > 0.0000001);

    return t0;
}

int QBezier::stationaryYPoints(qreal &t0, qreal &t1) const
{
    // y(t) = (1 - t)^3 * y1 + 3 * (1 - t)^2 * t * y2 + 3 * (1 - t) * t^2 * y3 + t^3 * y4
    // y'(t) = 3 * (-(1-2t+t^2) * y1 + (1 - 4 * t + 3 * t^2) * y2 + (2 * t - 3 * t^2) * y3 + t^2 * y4)
    // y'(t) = 3 * ((-y1 + 3 * y2 - 3 * y3 + y4)t^2 + (2 * y1 - 4 * y2 + 2 * y3)t + (-y1 + y2))

    const qreal a = -y1 + 3 * y2 - 3 * y3 + y4;
    const qreal b = 2 * y1 - 4 * y2 + 2 * y3;
    const qreal c = -y1 + y2;

    qreal reciprocal = b * b - 4 * a * c;

    QList<qreal> result;

    if (qFuzzyCompare(reciprocal, 0)) {
        t0 = -b / (2 * a);
        return 1;
    } else if (reciprocal > 0) {
        qreal temp = sqrt(reciprocal);

        t0 = (-b - temp)/(2*a);
        t1 = (-b + temp)/(2*a);

        if (t1 < t0)
            qSwap(t0, t1);

        int count = 0;
        qreal t[2] = { 0, 1 };

        if (t0 > 0 && t0 < 1)
            t[count++] = t0;
        if (t1 > 0 && t1 < 1)
            t[count++] = t1;

        t0 = t[0];
        t1 = t[1];

        return count;
    }

    return 0;
}

qreal QBezier::tAtLength(qreal l) const
{
    qreal len = length();
    qreal t   = 1.0;
    const qreal error = 0.01;
    if (l > len || qFuzzyCompare(l, len))
        return t;

    t *= 0.5;
    //int iters = 0;
    //qDebug()<<"LEN is "<<l<<len;
    qreal lastBigger = 1.;
    while (1) {
        //qDebug()<<"\tt is "<<t;
        QBezier right = *this;
        QBezier left;
        right.parameterSplitLeft(t, &left);
        qreal lLen = left.length();
        if (qAbs(lLen - l) < error)
            break;

        if (lLen < l) {
            t += (lastBigger - t)*.5;
        } else {
            lastBigger = t;
            t -= t*.5;
        }
        //++iters;
    }
    //qDebug()<<"number of iters is "<<iters;
    return t;
}

QBezier QBezier::bezierOnInterval(qreal t0, qreal t1) const
{
    if (t0 == 0 && t1 == 1)
        return *this;

    QBezier bezier = *this;

    QBezier result;
    bezier.parameterSplitLeft(t0, &result);
    qreal trueT = (t1-t0)/(1-t0);
    bezier.parameterSplitLeft(trueT, &result);

    return result;
}


static inline void bindInflectionPoint(const QBezier &bez, const qreal t,
                                       qreal *tMinus , qreal *tPlus)
{
    if (t <= 0) {
        *tMinus = *tPlus = -1;
        return;
    } else if (t >= 1) {
        *tMinus = *tPlus = 2;
        return;
    }

    QBezier left, right;
    splitBezierAt(bez, t, &left, &right);

    qreal ax = -right.x1 + 3*right.x2 - 3*right.x3 + right.x4;
    qreal ay = -right.y1 + 3*right.y2 - 3*right.y3 + right.y4;
    qreal ex = 3 * (right.x2 - right.x3);
    qreal ey = 3 * (right.y2 - right.y3);

    qreal s4 = qAbs(6 * (ey * ax - ex * ay) / qSqrt(ex * ex + ey * ey)) + 0.00001f;
    qreal tf = pow(qreal(9 * flatness / s4), qreal(1./3.));
    *tMinus = t - (1 - t) * tf;
    *tPlus  = t + (1 - t) * tf;
}

void QBezier::addToPolygonIterative(QPolygonF *p) const
{
    qreal t1, t2, tcusp;
    qreal t1min, t1plus, t2min, t2plus;

    qreal ax = -x1 + 3*x2 - 3*x3 + x4;
    qreal ay = -y1 + 3*y2 - 3*y3 + y4;
    qreal bx = 3*x1 - 6*x2 + 3*x3;
    qreal by = 3*y1 - 6*y2 + 3*y3;
    qreal cx = -3*x1 + 3*x2;
    qreal cy = -3*y1 + 2*y2;

    if (findInflections(6 * (ay * bx - ax * by),
                        6 * (ay * cx - ax * cy),
                        2 * (by * cx - bx * cy),
                        &t1, &t2, &tcusp)) {
        bindInflectionPoint(*this, t1, &t1min, &t1plus);
        bindInflectionPoint(*this, t2, &t2min, &t2plus);

        QBezier tmpBez = *this;
        QBezier left, right, bez1, bez2, bez3;
	if (t1min > 0) {
            if (t1min >= 1) {
                flattenBezierWithoutInflections(tmpBez, p);
            } else {
                splitBezierAt(tmpBez, t1min, &left, &right);
                flattenBezierWithoutInflections(left, p);
                p->append(tmpBez.pointAt(t1min));

                if (t2min < t1plus) {
                    if (tcusp < 1) {
                        p->append(tmpBez.pointAt(tcusp));
                    }
                    if (t2plus < 1) {
                        splitBezierAt(tmpBez, t2plus, &left, &right);
                        flattenBezierWithoutInflections(right, p);
                    }
                } else if (t1plus < 1) {
                    if (t2min < 1) {
                        splitBezierAt(tmpBez, t2min, &bez3, &right);
                        splitBezierAt(bez3, t1plus, &left, &bez2);

                        flattenBezierWithoutInflections(bez2, p);
                        p->append(tmpBez.pointAt(t2min));

                        if (t2plus < 1) {
                            splitBezierAt(tmpBez, t2plus, &left, &bez2);
                            flattenBezierWithoutInflections(bez2, p);
                        }
                    } else {
                        splitBezierAt(tmpBez, t1plus, &left, &bez2);
                        flattenBezierWithoutInflections(bez2, p);
                    }
                }
            }
	} else if (t1plus > 0) {
            p->append(QPointF(x1, y1));
            if (t2min < t1plus)	{
                if (tcusp < 1) {
                    p->append(tmpBez.pointAt(tcusp));
                }
                if (t2plus < 1) {
                    splitBezierAt(tmpBez, t2plus, &left, &bez2);
                    flattenBezierWithoutInflections(bez2, p);
                }
            } else if (t1plus < 1) {
                if (t2min < 1) {
                    splitBezierAt(tmpBez, t2min, &bez3, &right);
                    splitBezierAt(bez3, t1plus, &left, &bez2);

                    flattenBezierWithoutInflections(bez2, p);

                    p->append(tmpBez.pointAt(t2min));
                    if (t2plus < 1) {
                        splitBezierAt(tmpBez, t2plus, &left, &bez2);
                        flattenBezierWithoutInflections(bez2, p);
                    }
                } else {
                    splitBezierAt(tmpBez, t1plus, &left, &bez2);
                    flattenBezierWithoutInflections(bez2, p);
                }
            }
        } else if (t2min > 0) {
            if (t2min < 1) {
                splitBezierAt(tmpBez, t2min, &bez1, &right);
                flattenBezierWithoutInflections(bez1, p);
                p->append(tmpBez.pointAt(t2min));

                if (t2plus < 1) {
                    splitBezierAt(tmpBez, t2plus, &left, &bez2);
                    flattenBezierWithoutInflections(bez2, p);
                }
            } else {
                //### in here we should check whether the area of the
                //    triangle formed between pt1/pt2/pt3 is smaller
                //    or equal to 0 and then do iterative flattening
                //    if not we should fallback and do the recursive
                //    flattening.
                flattenBezierWithoutInflections(tmpBez, p);
            }
        } else if (t2plus > 0) {
            p->append(QPointF(x1, y1));
            if (t2plus < 1) {
                splitBezierAt(tmpBez, t2plus, &left, &bez2);
                flattenBezierWithoutInflections(bez2, p);
            }
        } else {
            flattenBezierWithoutInflections(tmpBez, p);
        }
    } else {
        QBezier bez = *this;
        flattenBezierWithoutInflections(bez, p);
    }

    p->append(QPointF(x4, y4));
}