qpathclipper.cpp

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

    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
            path.lineTo(*list.vertex(ep->vertex(status.direction)));

        if (status.traversal == QPathEdge::LeftTraversal)
            ep->flag &= ~16;
        else
            ep->flag &= ~32;

        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()
{
    for (int i = 0; i < edgeCount(); ++i) {
        const QPathEdge *ep = edge(i);

        // if both sides are part of the inside then we can collapse the edge
        int flag = 0x3 << 4;
        if ((ep->flag & flag) == flag) {
            removeEdge(i);

            ep->flag &= ~flag;
        }
    }
}

QPainterPath QWingedEdge::toPath() const
{
    QPainterPath path;

    for (int i = 0; i < edgeCount(); ++i) {
        const QPathEdge *ep = edge(i);

        if (ep->flag & 16) {
            add(path, *this, i, QPathEdge::LeftTraversal);
        }

        if (ep->flag & 32)
            add(path, *this, i, QPathEdge::RightTraversal);
    }

    return path;
}

class QPathClipper::Private
{
public:
    Private()
    {
    }

    Private(const QPainterPath &s,
            const QPainterPath &c)
        : subjectPath(s)
        , clipPath(c)
    {
    }

    ~Private()
    {
    }

    void handleCrossingEdges(QWingedEdge &list, qreal y);

    bool areIntersecting()
    {
        QRectF subjControl = subjectPath.controlPointRect();
        QRectF clipControl = clipPath.controlPointRect();

        QRectF r1 = subjControl.normalized();
        QRectF r2 = clipControl.normalized();
        if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) ||
            qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) {
            // no way we could intersect
            return false;
        }

        QPathSegments subjectSegments;
        subjectSegments.setPath(subjectPath);
        QPathSegments clipSegments;
        clipSegments.setPath(clipPath);

        QDataBuffer<QIntersection> intersections;
        QIntersectionFinder finder(&intersections);

        for (int i = 0; i < subjectSegments.segments(); ++i) {
            finder.addIntersections(&subjectSegments, &clipSegments, i, true);

            if (finder.hasIntersections())
                return true;
        }

        return false;
    }

    QPainterPath subjectPath;
    QPainterPath clipPath;
    Operation    op;
};

QPathClipper::QPathClipper(const QPainterPath &subject,
                           const QPainterPath &clip)
    : d(new Private)
{
    d->subjectPath = subject;
    d->clipPath = clip;
}

QPathClipper::~QPathClipper()
{
    delete d;
}

template <typename Iterator, typename Equality>
Iterator qRemoveDuplicates(Iterator begin, Iterator end, Equality eq)
{
    if (begin == end)
        return end;

    Iterator last = begin;
    ++begin;
    Iterator insert = begin;
    for (Iterator it = begin; it != end; ++it) {
        if (!eq(*it, *last))
            *insert++ = *it;

        last = it;
    }

    return insert;
}

static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal)
{
    QWingedEdge::TraversalStatus status;
    status.edge = edge;
    status.traversal = traversal;
    status.direction = QPathEdge::Forward;

    do {
        if (status.traversal == QPathEdge::LeftTraversal)
            list.edge(status.edge)->flag |= 1;
        else
            list.edge(status.edge)->flag |= 2;

        status = list.next(status);
    } while (status.edge != edge);
}

template <typename InputIterator>
InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val)
{
    while (first != last && !qFuzzyCompare(qreal(*first), qreal(val)))
        ++first;
    return first;
}

static bool fuzzyCompare(qreal a, qreal b)
{
    return qFuzzyCompare(a, b);
}

QPainterPath QPathClipper::clip(Operation op)
{
    d->op = op;

    if (d->subjectPath == d->clipPath)
        return op == BoolSub ? QPainterPath() : d->subjectPath;

    QWingedEdge list(d->subjectPath, d->clipPath);

    QVector<qreal> y_coords;
    y_coords.reserve(list.vertexCount());
    for (int i = 0; i < list.vertexCount(); ++i)
        y_coords << list.vertex(i)->y;

    qSort(y_coords.begin(), y_coords.end());
    y_coords.resize(qRemoveDuplicates(y_coords.begin(), y_coords.end(), fuzzyCompare) - y_coords.begin());

#ifdef QDEBUG_CLIPPER
    printf("sorted y coords:\n");
    for (int i = 0; i < y_coords.size(); ++i) {
        printf("%.9f\n", y_coords[i]);
    }
#endif

    bool found;
    do {
        found = false;
        int index = 0;
        qreal maxHeight = 0;
        for (int i = 0; i < list.edgeCount(); ++i) {
            QPathEdge *edge = list.edge(i);

            // have both sides of this edge already been handled?
            if ((edge->flag & 0x3) == 0x3)
                continue;

            QPathVertex *a = list.vertex(edge->first);
            QPathVertex *b = list.vertex(edge->second);

            if (qFuzzyCompare(a->y, b->y))
                continue;

            found = true;

            qreal height = qAbs(a->y - b->y);
            if (height > maxHeight) {
                index = i;
                maxHeight = height;
            }
        }

        if (found) {
            QPathEdge *edge = list.edge(index);

            QPathVertex *a = list.vertex(edge->first);
            QPathVertex *b = list.vertex(edge->second);

            // FIXME: this can be optimized by using binary search
            const int first = qFuzzyFind(y_coords.begin(), y_coords.end(), qMin(a->y, b->y)) - y_coords.begin();
            const int last = qFuzzyFind(y_coords.begin() + first, y_coords.end(), qMax(a->y, b->y)) - y_coords.begin();

            Q_ASSERT(first < y_coords.size() - 1);
            Q_ASSERT(last < y_coords.size());

            qreal bestY = 0.5 * (y_coords[first] + y_coords[first+1]);
            qreal biggestGap = y_coords[first+1] - y_coords[first];

            for (int i = first + 1; i < last - 1; ++i) {
                qreal gap = y_coords[i+1] - y_coords[i];

                if (gap > biggestGap) {
                    bestY = 0.5 * (y_coords[i] + y_coords[i+1]);
                    biggestGap = gap;
                }
            }

#ifdef QDEBUG_CLIPPER
            printf("y: %.9f, gap: %.9f\n", bestY, biggestGap);
#endif

            d->handleCrossingEdges(list, bestY);
            edge->flag |= 0x3;
        }
    } while (found);

    list.simplify();

    QPainterPath path = list.toPath();
    return path;
}

static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal)
{
    QWingedEdge::TraversalStatus status;
    status.edge = edge;
    status.traversal = traversal;
    status.direction = QPathEdge::Forward;

    do {
        int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2;

        QPathEdge *ep = list.edge(status.edge);

        ep->flag |= (flag | (flag << 4));

#ifdef QDEBUG_CLIPPER
        qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag;
#endif

        status = list.next(status);
    } while (status.edge != edge);
}

struct QCrossingEdge
{
    int edge;
    qreal x;

    bool operator<(const QCrossingEdge &edge) const
    {
        return x < edge.x;
    }
};

static bool bool_op(bool a, bool b, QPathClipper::Operation op)
{
    switch (op) {
    case QPathClipper::BoolAnd:
        return a && b;
    case QPathClipper::BoolOr:
        return a || b;
    case QPathClipper::BoolSub:
        return a && !b;
    default:
        Q_ASSERT(false);
        return false;
    }
}

bool QWingedEdge::isInside(qreal x, qreal y) const
{
    int winding = 0;
    for (int i = 0; i < edgeCount(); ++i) {
        const QPathEdge *ep = edge(i);

        // left xor right
        int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1;

        if (!w)
            continue;

        QPointF a = *vertex(ep->first);
        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());

                if (intersectionX > x)
                    winding += w;
            }
        }
    }

    return winding & 1;
}

static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y)
{
    QVector<QCrossingEdge> crossings;
    for (int i = 0; i < list.edgeCount(); ++i) {
        const QPathEdge *edge = list.edge(i);
        QPointF a = *list.vertex(edge->first);
        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;
            }
        }
    }
    return crossings;
}

void QPathClipper::Private::handleCrossingEdges(QWingedEdge &list, qreal y)
{
    QVector<QCrossingEdge> crossings = findCrossings(list, y);

    Q_ASSERT(!crossings.isEmpty());
    qSort(crossings.begin(), crossings.end());

    int windingA = 0;
    int windingB = 0;

    int windingD = 0;

    const int aMask = subjectPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;
    const int bMask = clipPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1;

#ifdef QDEBUG_CLIPPER
    qDebug() << "crossings:" << crossings.size();
#endif
    for (int i = 0; i < crossings.size() - 1; ++i) {
        int ei = crossings.at(i).edge;
        const QPathEdge *edge = list.edge(ei);

        windingA += edge->windingA;
        windingB += edge->windingB;

        const bool hasLeft = (edge->flag >> 4) & 1;
        const bool hasRight = (edge->flag >> 4) & 2;

        windingD += hasLeft ^ hasRight;

        const bool inA = (windingA & aMask) != 0;
        const bool inB = (windingB & bMask) != 0;
        const bool inD = (windingD & 0x1) != 0;

        const bool inside = bool_op(inA, inB, op);
        const bool add = inD ^ inside;

#ifdef QDEBUG_CLIPPER
        printf("y %f, x %f, inA: %d, inB: %d, inD: %d, inside: %d, flag: %x, bezier: %p, edge: %d\n", y, crossings.at(i).x, inA, inB, inD, inside, edge->flag, edge->bezier, ei);
#endif

        if (add) {
            qreal y0 = list.vertex(edge->first)->y;
            qreal y1 = list.vertex(edge->second)->y;

            if (y0 < y1) {
                if (!(edge->flag & 1))
                    traverse(list, ei, QPathEdge::LeftTraversal);

                if (!(edge->flag & 2))
                    clear(list, ei, QPathEdge::RightTraversal);
            } else {
                if (!(edge->flag & 1))
                    clear(list, ei, QPathEdge::LeftTraversal);

                if (!(edge->flag & 2))
                    traverse(list, ei, QPathEdge::RightTraversal);
            }

            ++windingD;
        } else {
            if (!(edge->flag & 1))
                clear(list, ei, QPathEdge::LeftTraversal);

            if (!(edge->flag & 2))
                clear(list, ei, QPathEdge::RightTraversal);
        }
    }
}

bool QPathClipper::intersect()
{
    return d->areIntersecting();
}

bool QPathClipper::contains()
{
    bool intersect = d->areIntersecting();

    //we have an intersection clearly we can't be fully contained
    if (intersect)
        return false;

    //if there's no intersections the path is already completely outside
    //or fully inside. if the first element of the clip is inside then
    //due to no intersections, the rest will be inside as well...
    return d->subjectPath.contains(d->clipPath.elementAt(0));
}