qpathclipper.cpp

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

                    Line line(QLineF(last, path.elementAt(i+2)));
                    m_lines << line;
                } else {
                    m_beziers << bezier;
                }
            }
            last = path.elementAt(i + 2);
            i += 2;
            break;
        default:
            Q_ASSERT(false);
            break;
        }
    }

    if (hasMoveTo && last != lastMoveTo) {
        Line line(QLineF(last, lastMoveTo), true);
        m_lines << line;
    }
}

qreal QWingedEdge::delta(int vertex, int a, int b) const
{
    const QPathEdge *ap = edge(a);
    const QPathEdge *bp = edge(b);

    qreal a_angle = ap->angle;
    qreal b_angle = bp->angle;

    if (vertex == ap->second)
        a_angle = ap->invAngle;

    if (vertex == bp->second)
        b_angle = bp->invAngle;

    qreal result = b_angle - a_angle;

    if (qFuzzyCompare(result, qreal(0)) || qFuzzyCompare(result, qreal(128)))
        return 0;

    if (result < 0)
        return result + 128.;
    else
        return result;
}

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 (normal == QPointF())
            normal = ep->bezier->secondDerivedAt(t);
    } else {
        const QPointF a = *list.vertex(ep->first);
        const QPointF b = *list.vertex(ep->second);
        normal = b - a;
    }

    return normalize(sign * normal);
}

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);

    // shouldn't have two line segments with same normal
    // (they should have been merged during winged edge construction)
    Q_ASSERT(ap->bezier || bp->bezier);

    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;
}

QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const
{
    const QPathVertex *vp = vertex(vi);

    Q_ASSERT(vp);
    Q_ASSERT(ei >= 0);
    Q_ASSERT(vp->edge >= 0);

    int position = vp->edge;
    qreal d = 128.;

    TraversalStatus status;
    status.direction = edge(vp->edge)->directionTo(vi);
    status.traversal = QPathEdge::RightTraversal;
    status.edge = vp->edge;

#ifdef QDEBUG_CLIPPER
    const QPathEdge *ep = edge(ei);
    qDebug() << "Finding insert status for edge" << ei << "at vertex" << QPointF(*vp) << ", angles: " << ep->angle << ep->invAngle;
#endif

    do {
        status = next(status);
        status.flip();

        Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);

        qreal d2 = delta(vi, ei, status.edge);

#ifdef QDEBUG_CLIPPER
        const QPathEdge *op = edge(status.edge);
        qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle;
#endif

        if (!(qFuzzyCompare(d2, 0) && isLeftOf(*this, vi, status.edge, ei))
            && (d2 < d || qFuzzyCompare(d2, d) && isLeftOf(*this, vi, status.edge, position))) {
            position = status.edge;
            d = d2;
        }
    } while (status.edge != vp->edge);

    status.traversal = QPathEdge::LeftTraversal;
    status.direction = QPathEdge::Forward;
    status.edge = position;

    if (edge(status.edge)->vertex(status.direction) != vi)
        status.flip();

#ifdef QDEBUG_CLIPPER
    qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge;
#endif

    Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi);

    return status;
}

void QWingedEdge::removeEdge(int ei)
{
    QPathEdge *ep = edge(ei);

    TraversalStatus status;
    status.direction = QPathEdge::Forward;
    status.traversal = QPathEdge::RightTraversal;
    status.edge = ei;

    TraversalStatus forwardRight = next(status);
    forwardRight.flipDirection();

    status.traversal = QPathEdge::LeftTraversal;
    TraversalStatus forwardLeft = next(status);
    forwardLeft.flipDirection();

    status.direction = QPathEdge::Backward;
    TraversalStatus backwardLeft = next(status);
    backwardLeft.flipDirection();

    status.traversal = QPathEdge::RightTraversal;
    TraversalStatus backwardRight = next(status);
    backwardRight.flipDirection();

    edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge);
    edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge);

    edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge);
    edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge);

    ep->setNext(QPathEdge::Forward, ei);
    ep->setNext(QPathEdge::Backward, ei);

    QPathVertex *a = vertex(ep->first);
    QPathVertex *b = vertex(ep->second);

    a->edge = backwardRight.edge;
    b->edge = forwardRight.edge;
}

static int commonEdge(const QWingedEdge &list, int a, int b)
{
    const QPathVertex *ap = list.vertex(a);
    Q_ASSERT(ap);

    const QPathVertex *bp = list.vertex(b);
    Q_ASSERT(bp);

    if (ap->edge < 0 || bp->edge < 0)
        return -1;

    QWingedEdge::TraversalStatus status;
    status.edge = ap->edge;
    status.direction = list.edge(status.edge)->directionTo(a);
    status.traversal = QPathEdge::RightTraversal;

    do {
        const QPathEdge *ep = list.edge(status.edge);

        if (ep->first == a && ep->second == b ||
            ep->first == b && ep->second == a)
            return status.edge;

        status = list.next(status);
        status.flip();
    } while (status.edge != ap->edge);

    return -1;
}

static qreal computeAngle(const QPointF &v)
{
#if 1
    if (v.x() == 0) {
        return v.y() <= 0 ? 0 : 64.;
    } else if (v.y() == 0) {
        return v.x() <= 0 ? 32. : 96.;
    }

    QPointF nv = normalize(v);
    if (nv.y() < 0) {
        if (nv.x() < 0) { // 0 - 32
            return -32. * nv.x();
        } else { // 96 - 128
            return 128. - 32. * nv.x();
        }
    } else { // 32 - 96
        return 64. + 32 * nv.x();
    }
#else
    // doesn't seem to be robust enough
    return atan2(v.x(), v.y()) + Q_PI;
#endif
}

int QWingedEdge::addEdge(const QPointF &a, const QPointF &b, const QBezier *bezier, qreal t0, qreal t1)
{
    int fi = insert(a);
    int si = insert(b);

    if (fi == si)
        return -1;

    int common = commonEdge(*this, fi, si);
    if (common >= 0)
        return common;

    m_edges << QPathEdge(fi, si);

    int ei = m_edges.size() - 1;

    QPathVertex *fp = vertex(fi);
    QPathVertex *sp = vertex(si);

    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 (aTangent == QPointF())
            aTangent = bezier->secondDerivedAt(t0);

        if (bTangent == QPointF())
            bTangent = bezier->secondDerivedAt(t1);

        ep->angle = computeAngle(aTangent);
        ep->invAngle = computeAngle(-bTangent);
    } else {
        const QPointF tangent = b - a;
        ep->angle = computeAngle(tangent);
        ep->invAngle = computeAngle(-tangent);
    }

    QPathVertex *vertices[2] = { fp, sp };
    QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward };

#ifdef QDEBUG_CLIPPER
    qDebug() << "** Adding edge" << ei << "/ vertices:" << a << b;
#endif

    for (int i = 0; i < 2; ++i) {
        QPathVertex *vp = vertices[i];
        if (vp->edge < 0) {
            vp->edge = ei;
            ep->setNext(dirs[i], ei);
        } else {
            int vi = ep->vertex(dirs[i]);
            Q_ASSERT(vertex(vi) == vertices[i]);

            TraversalStatus os = findInsertStatus(vi, ei);
            QPathEdge *op = edge(os.edge);

            Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]);

            TraversalStatus ns = next(os);
            ns.flipDirection();
            QPathEdge *np = edge(ns.edge);

            op->setNext(os.traversal, os.direction, ei);
            np->setNext(ns.traversal, ns.direction, ei);

            int oe = os.edge;
            int ne = ns.edge;

            os = next(os);
            ns = next(ns);

            os.flipDirection();
            ns.flipDirection();

            Q_ASSERT(os.edge == ei);
            Q_ASSERT(ns.edge == ei);

            ep->setNext(os.traversal, os.direction, oe);
            ep->setNext(ns.traversal, ns.direction, ne);
        }
    }

    Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Forward) >= 0);
    Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Backward) >= 0);
    Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Forward) >= 0);
    Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0);

    return ei;
}

void QWingedEdge::addBezierEdge(const QBezier *bezier, const QPointF &a, const QPointF &b, 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());

    QPointF pa = a;
    for (int i = 0; i < m_splitPoints.size() - 1; ++i) {
        const qreal t0 = m_splitPoints[i];
        const qreal t1 = m_splitPoints[i+1];

        const QPointF pb = (i + 1) == (m_splitPoints.size() - 1) ? b : bezier->pointAt(t1);

        QPathEdge *ep = edge(addEdge(pa, pb, bezier, t0, t1));

        if (ep) {
            const int dir = pa.y() < pb.y() ? 1 : -1;
            if (path == 0)
                ep->windingA += dir;
            else
                ep->windingB += dir;
        }

        pa = pb;
    }
}

int QWingedEdge::insert(const QPathVertex &vertex)
{
    if (!m_vertices.isEmpty()) {
        const QPathVertex &last = m_vertices.last();
        if (vertex.x == last.x && vertex.y == last.y)
            return m_vertices.size() - 1;

        for (int i = 0; i < m_vertices.size(); ++i) {
            const QPathVertex &v = m_vertices.at(i);
            if (qFuzzyCompare(v.x, vertex.x) && qFuzzyCompare(v.y, vertex.y)) {
                return i;
            }
        }
    }

    m_vertices << vertex;
    return m_vertices.size() - 1;
}

static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
{
    QWingedEdge::TraversalStatus status;
    status.edge = edge;
    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));