qbezier.cpp

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

    }
    map[3] = np - 1;
    if (np == 1)
        return Discard;

    // We need to specialcase lines of 3 or 4 points due to numerical
    // instability in intersections below
    if (np > 2 && qbezier_is_line(points, np)) {
        QLineF l = qline_shifted(points[0], points[np-1], offset);
        *shifted = QBezier::fromPoints(l.p1(), l.pointAt(0.33), l.pointAt(0.66), l.p2());
        return Ok;
    }

    QRectF b = orig->bounds();
    if (np == 4 && b.width() < .1*offset && b.height() < .1*offset) {
        qreal l = (orig->x1 - orig->x2)*(orig->x1 - orig->x2) +
                  (orig->y1 - orig->y2)*(orig->y1 - orig->y1) *
                  (orig->x3 - orig->x4)*(orig->x3 - orig->x4) +
                  (orig->y3 - orig->y4)*(orig->y3 - orig->y4);
        qreal dot = (orig->x1 - orig->x2)*(orig->x3 - orig->x4) +
                    (orig->y1 - orig->y2)*(orig->y3 - orig->y4);
        if (dot < 0 && dot*dot < 0.8*l)
            // the points are close and reverse dirction. Approximate the whole
            // thing by a semi circle
            return Circle;
    }

    QPointF points_shifted[4];

    QLineF prev = QLineF(QPointF(), points[1] - points[0]);
    QPointF prev_normal = prev.normalVector().unitVector().p2();

    points_shifted[0] = points[0] + offset * prev_normal;

    for (int i = 1; i < np - 1; ++i) {
        QLineF next = QLineF(QPointF(), points[i + 1] - points[i]);
        QPointF next_normal = next.normalVector().unitVector().p2();

        QPointF normal_sum = prev_normal + next_normal;

        qreal r = 1.0 + prev_normal.x() * next_normal.x()
                  + prev_normal.y() * next_normal.y();

        if (qFuzzyCompare(r, (qreal)0.0)) {
            points_shifted[i] = points[i] + offset * prev_normal;
        } else {
            qreal k = offset / r;
            points_shifted[i] = points[i] + k * normal_sum;
        }

        prev_normal = next_normal;
    }

    points_shifted[np - 1] = points[np - 1] + offset * prev_normal;

    *shifted = QBezier::fromPoints(points_shifted[map[0]], points_shifted[map[1]],
                                   points_shifted[map[2]], points_shifted[map[3]]);

    return good_offset(orig, shifted, offset, threshold);
}

// This value is used to determine the length of control point vectors
// when approximating arc segments as curves. The factor is multiplied
// with the radius of the circle.
#define KAPPA 0.5522847498


static bool addCircle(const QBezier *b, qreal offset, QBezier *o)
{
    QPointF normals[3];

    normals[0] = QPointF(b->y2 - b->y1, b->x1 - b->x2);
    qreal dist = qSqrt(normals[0].x()*normals[0].x() + normals[0].y()*normals[0].y());
    if (qFuzzyCompare(dist, 0))
        return false;
    normals[0] /= dist;
    normals[2] = QPointF(b->y4 - b->y3, b->x3 - b->x4);
    dist = qSqrt(normals[2].x()*normals[2].x() + normals[2].y()*normals[2].y());
    if (qFuzzyCompare(dist, 0))
        return false;
    normals[2] /= dist;

    normals[1] = QPointF(b->x1 - b->x2 - b->x3 + b->x4, b->y1 - b->y2 - b->y3 + b->y4);
    normals[1] /= -1*qSqrt(normals[1].x()*normals[1].x() + normals[1].y()*normals[1].y());

    qreal angles[2];
    qreal sign = 1.;
    for (int i = 0; i < 2; ++i) {
        qreal cos_a = normals[i].x()*normals[i+1].x() + normals[i].y()*normals[i+1].y();
        if (cos_a > 1.)
            cos_a = 1.;
        if (cos_a < -1.)
            cos_a = -1;
        angles[i] = acos(cos_a)/Q_PI;
    }

    if (angles[0] + angles[1] > 1.) {
        // more than 180 degrees
        normals[1] = -normals[1];
        angles[0] = 1. - angles[0];
        angles[1] = 1. - angles[1];
        sign = -1.;

    }

    QPointF circle[3];
    circle[0] = QPointF(b->x1, b->y1) + normals[0]*offset;
    circle[1] = QPointF(0.5*(b->x1 + b->x4), 0.5*(b->y1 + b->y4)) + normals[1]*offset;
    circle[2] = QPointF(b->x4, b->y4) + normals[2]*offset;

    for (int i = 0; i < 2; ++i) {
        qreal kappa = 2.*KAPPA * sign * offset * angles[i];

        o->x1 = circle[i].x();
        o->y1 = circle[i].y();
        o->x2 = circle[i].x() - normals[i].y()*kappa;
        o->y2 = circle[i].y() + normals[i].x()*kappa;
        o->x3 = circle[i+1].x() + normals[i+1].y()*kappa;
        o->y3 = circle[i+1].y() - normals[i+1].x()*kappa;
        o->x4 = circle[i+1].x();
        o->y4 = circle[i+1].y();

        ++o;
    }
    return true;
}

int QBezier::shifted(QBezier *curveSegments, int maxSegments, qreal offset, float threshold) const
{
    Q_ASSERT(curveSegments);
    Q_ASSERT(maxSegments > 0);

    if (x1 == x2 && x1 == x3 && x1 == x4 &&
        y1 == y2 && y1 == y3 && y1 == y4)
        return 0;

    --maxSegments;
    QBezier beziers[10];
redo:
    beziers[0] = *this;
    QBezier *b = beziers;
    QBezier *o = curveSegments;

    while (b >= beziers) {
        int stack_segments = b - beziers + 1;
        if ((stack_segments == 10) || (o - curveSegments == maxSegments - stack_segments)) {
            threshold *= 1.5;
            if (threshold > 2.)
                goto give_up;
            goto redo;
        }
        ShiftResult res = shift(b, o, offset, threshold);
        if (res == Discard) {
            --b;
        } else if (res == Ok) {
            ++o;
            --b;
            continue;
        } else if (res == Circle && maxSegments - (o - curveSegments) >= 2) {
            // add semi circle
            if (addCircle(b, offset, o))
                o += 2;
            --b;
        } else {
            b->split(b+1, b);
            ++b;
        }
    }

give_up:
    while (b >= beziers) {
        ShiftResult res = shift(b, o, offset, threshold);

        // if res isn't Ok or Split then *o is undefined
        if (res == Ok || res == Split)
            ++o;

        --b;
    }

    Q_ASSERT(o - curveSegments <= maxSegments);
    return o - curveSegments;
}

#if 0
static inline bool IntersectBB(const QBezier &a, const QBezier &b)
{
    return a.bounds().intersects(b.bounds());
}
#else
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)
{
    dbg <<"["<<bz.x1<<", "<<bz.y1<<"], "
        <<"["<<bz.x2<<", "<<bz.y2<<"], "
        <<"["<<bz.x3<<", "<<bz.y3<<"], "
        <<"["<<bz.x4<<", "<<bz.y4<<"]";
    return dbg;
}
#endif

static void RecursivelyIntersect(const QBezier &a, qreal t0, qreal t1, int deptha,
                                 const QBezier &b, qreal u0, qreal u1, int depthb,
                                 QVector<qreal> &ta, QVector<qreal> &tb)
{
#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);
		RecursivelyIntersect(A[0], t0, tmid, deptha,
				     B[0], u0, umid, depthb,
				     ta, tb);
            }
	    if (IntersectBB(A[1], B[0])) {
                //fprintf(stderr, "\t 2 from %d\n", currentD);
		RecursivelyIntersect(A[1], tmid, t1, deptha,
                                     B[0], u0, umid, depthb,
                                     ta, tb);
            }
	    if (IntersectBB(A[0], B[1])) {
                //fprintf(stderr, "\t 3 from %d\n", currentD);
		RecursivelyIntersect(A[0], t0, tmid, deptha,
                                     B[1], umid, u1, depthb,
                                     ta, tb);
            }
	    if (IntersectBB(A[1], B[1])) {
                //fprintf(stderr, "\t 4 from %d\n", currentD);
		RecursivelyIntersect(A[1], tmid, t1, deptha,
				     B[1], umid, u1, depthb,
				     ta, tb);
            }
        } else {
	    if (IntersectBB(A[0], b)) {
                //fprintf(stderr, "\t 5 from %d\n", currentD);
		RecursivelyIntersect(A[0], t0, tmid, deptha,
				     b, u0, u1, depthb,
				     ta, tb);
            }
	    if (IntersectBB(A[1], b)) {
                //fprintf(stderr, "\t 6 from %d\n", currentD);
		RecursivelyIntersect(A[1], tmid, t1, deptha,
                                     b, u0, u1, depthb,
                                     ta, tb);
            }
        }
    } 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);
		RecursivelyIntersect(a, t0, t1, deptha,
                                     B[0], u0, umid, depthb,
                                     ta, tb);
            }
	    if (IntersectBB(a, B[1])) {
                //fprintf(stderr, "\t 8 from %d\n", currentD);
		RecursivelyIntersect(a, t0, t1, deptha,
                                     B[1], umid, u1, depthb,
                                     ta, tb);
            }
        }
	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;
            } else {
                qreal detinv = 1.0 / det;
                qreal s = (xnm * ymk - ynm *xmk) * detinv;
                qreal t = (xlk * ymk - ylk * xmk) * detinv;
                if ((s < 0.0) || (s > 1.0) || (t < 0.0) || (t > 1.0))
                    return;

                ta << t0 + s * (t1 - t0);
                tb << u0 + t * (u1 - u0);
            }
        }
    }
}

QVector< QList<qreal> > QBezier::findIntersections(const QBezier &a, const QBezier &b)
{
    QVector< QList<qreal> > v(2);

    QVector<qreal> ta;
    QVector<qreal> tb;

    findIntersections(a, b, ta, tb);

    Q_ASSERT(ta.size() == tb.size());

    for (int i = 0; i < ta.size(); ++i) {
        v[0] << ta[i];
        v[1] << tb[i];
    }

    return v;
}

bool QBezier::findIntersections(const QBezier &a, const QBezier &b,
                                QVector<qreal> &ta, QVector<qreal> &tb)
{
    if (IntersectBB(a, b)) {
        QPointF la1(fabs((a.x3 - a.x2) - (a.x2 - a.x1)),
                    fabs((a.y3 - a.y2) - (a.y2 - a.y1)));
	QPointF la2(fabs((a.x4 - a.x3) - (a.x3 - a.x2)),