qpainterpath.cpp

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

#define QT_BEZIER_C(bezier, coord) 3 * (- bezier.coord##1 \
                                        + bezier.coord##2)

#define QT_BEZIER_CHECK_T(bezier, t) \
    if (t >= 0 && t <= 1) { \
        QPointF p(b.pointAt(t)); \
        if (p.x() < minx) minx = p.x(); \
        else if (p.x() > maxx) maxx = p.x(); \
        if (p.y() < miny) miny = p.y(); \
        else if (p.y() > maxy) maxy = p.y(); \
    }


static QRectF qt_painterpath_bezier_extrema(const QBezier &b)
{
    qreal minx, miny, maxx, maxy;

    // initialize with end points
    if (b.x1 < b.x4) {
        minx = b.x1;
        maxx = b.x4;
    } else {
        minx = b.x4;
        maxx = b.x1;
    }
    if (b.y1 < b.y4) {
        miny = b.y1;
        maxy = b.y4;
    } else {
        miny = b.y4;
        maxy = b.y1;
    }

    // Update for the X extrema
    {
        qreal ax = QT_BEZIER_A(b, x);
        qreal bx = QT_BEZIER_B(b, x);
        qreal cx = QT_BEZIER_C(b, x);
        // specialcase quadratic curves to avoid div by zero
        if (qFuzzyCompare(ax, 0)) {

            // linear curves are covered by initialization.
            if (!qFuzzyCompare(bx, 0)) {
                qreal t = -cx / bx;
                QT_BEZIER_CHECK_T(b, t);
            }

        } else {
            qreal temp = qSqrt(bx * bx - 4 * ax * cx);
            qreal rcp = 1 / (2 * ax);
            qreal t1 = (-bx + temp) * rcp;
            QT_BEZIER_CHECK_T(b, t1);

            qreal t2 = (-bx - temp) * rcp;
            QT_BEZIER_CHECK_T(b, t2);
        }
    }

    // Update for the Y extrema
    {
        qreal ay = QT_BEZIER_A(b, y);
        qreal by = QT_BEZIER_B(b, y);
        qreal cy = QT_BEZIER_C(b, y);

        // specialcase quadratic curves to avoid div by zero
        if (qFuzzyCompare(ay, 0)) {

            // linear curves are covered by initialization.
            if (!qFuzzyCompare(by, 0)) {
                qreal t = -cy / by;
                QT_BEZIER_CHECK_T(b, t);
            }

        } else {
            qreal temp = qSqrt(by * by - 4 * ay * cy);
            qreal rcp = 1 / (2 * ay);
            qreal t1 = (-by + temp) * rcp;
            QT_BEZIER_CHECK_T(b, t1);

            qreal t2 = (-by - temp) * rcp;
            QT_BEZIER_CHECK_T(b, t2);
        }
    }
    return QRectF(minx, miny, maxx - minx, maxy - miny);
}

/*!
    Returns the bounding rectangle of this painter path as a rectangle with
    floating point precision.

    \sa controlPointRect()
*/
QRectF QPainterPath::boundingRect() const
{
    if (isEmpty())
        return QRectF();
    QPainterPathData *d = d_func();

    if (d->dirtyBounds)
        computeBoundingRect();
    return d->bounds;
}

/*!
    Returns the rectangle containing all the points and control points
    in this path.

    This function is significantly faster to compute than the exact
    boundingRect(), and the returned rectangle is always a superset of
    the rectangle returned by boundingRect().

    \sa boundingRect()
*/
QRectF QPainterPath::controlPointRect() const
{
    if (isEmpty())
        return QRectF();
    QPainterPathData *d = d_func();

    if (d->dirtyControlBounds)
        computeControlPointRect();
    return d->controlBounds;
}


/*!
    \fn bool QPainterPath::isEmpty() const

    Returns true if there are no elements in this path, otherwise
    returns false.

    \sa elementCount()
*/

/*!
    Creates and returns a reversed copy of the path.

    It is the order of the elements that is reversed: If a
    QPainterPath is composed by calling the moveTo(), lineTo() and
    cubicTo() functions in the specified order, the reversed copy is
    composed by calling cubicTo(), lineTo() and moveTo().
*/
QPainterPath QPainterPath::toReversed() const
{
    Q_D(const QPainterPath);
    QPainterPath rev;

    if (isEmpty()) {
        rev = *this;
        return rev;
    }

    rev.moveTo(d->elements.at(d->elements.size()-1).x, d->elements.at(d->elements.size()-1).y);

    for (int i=d->elements.size()-1; i>=1; --i) {
        const QPainterPath::Element &elm = d->elements.at(i);
        const QPainterPath::Element &prev = d->elements.at(i-1);
        switch (elm.type) {
        case LineToElement:
            rev.lineTo(prev.x, prev.y);
            break;
        case MoveToElement:
            rev.moveTo(prev.x, prev.y);
            break;
        case CurveToDataElement:
            {
                Q_ASSERT(i>=3);
                const QPainterPath::Element &cp1 = d->elements.at(i-2);
                const QPainterPath::Element &sp = d->elements.at(i-3);
                Q_ASSERT(prev.type == CurveToDataElement);
                Q_ASSERT(cp1.type == CurveToElement);
                rev.cubicTo(prev.x, prev.y, cp1.x, cp1.y, sp.x, sp.y);
                i -= 2;
                break;
            }
        default:
            Q_ASSERT(!"qt_reversed_path");
            break;
        }
    }
    //qt_debug_path(rev);
    return rev;
}

/*!
    Converts the path into a list of polygons using the QTransform
    \a matrix, and returns the list.

    This function creates one polygon for each subpath regardless of
    intersecting subpaths (i.e. overlapping bounding rectangles). To
    make sure that such overlapping subpaths are filled correctly, use
    the toFillPolygons() function instead.

    \sa toFillPolygons(), toFillPolygon(), {QPainterPath#QPainterPath
    Conversion}{QPainterPath Conversion}
*/
QList<QPolygonF> QPainterPath::toSubpathPolygons(const QTransform &matrix) const
{

    Q_D(const QPainterPath);
    QList<QPolygonF> flatCurves;
    if (isEmpty())
        return flatCurves;

    QPolygonF current;
    for (int i=0; i<elementCount(); ++i) {
        const QPainterPath::Element &e = d->elements.at(i);
        switch (e.type) {
        case QPainterPath::MoveToElement:
            if (current.size() > 1)
                flatCurves += current;
            current.clear();
            current.reserve(16);
            current += QPointF(e.x, e.y) * matrix;
            break;
        case QPainterPath::LineToElement:
            current += QPointF(e.x, e.y) * matrix;
            break;
        case QPainterPath::CurveToElement: {
            Q_ASSERT(d->elements.at(i+1).type == QPainterPath::CurveToDataElement);
            Q_ASSERT(d->elements.at(i+2).type == QPainterPath::CurveToDataElement);
            QBezier bezier = QBezier::fromPoints(QPointF(d->elements.at(i-1).x, d->elements.at(i-1).y) * matrix,
                                       QPointF(e.x, e.y) * matrix,
                                       QPointF(d->elements.at(i+1).x, d->elements.at(i+1).y) * matrix,
                                                 QPointF(d->elements.at(i+2).x, d->elements.at(i+2).y) * matrix);
            bezier.addToPolygon(&current);
            i+=2;
            break;
        }
        case QPainterPath::CurveToDataElement:
            Q_ASSERT(!"QPainterPath::toSubpathPolygons(), bad element type");
            break;
        }
    }

    if (current.size()>1)
        flatCurves += current;

    return flatCurves;
}

/*!
  \overload
 */
QList<QPolygonF> QPainterPath::toSubpathPolygons(const QMatrix &matrix) const
{
    return toSubpathPolygons(QTransform(matrix));
}

static inline bool rect_intersects(const QRectF &r1, const QRectF &r2)
{
    return qMax(r1.left(), r2.left()) <= qMin(r1.right(), r2.right())
        && qMax(r1.top(), r2.top()) <= qMin(r1.bottom(), r2.bottom());
}

/*!
    Converts the path into a list of polygons using the 
    QTransform \a matrix, and returns the list.

    The function differs from the toFillPolygon() function in that it
    creates several polygons. It is provided because it is usually
    faster to draw several small polygons than to draw one large
    polygon, even though the total number of points drawn is the same.

    The toFillPolygons() function differs from the toSubpathPolygons()
    function in that it create only polygon for subpaths that have
    overlapping bounding rectangles.

    Like the toFillPolygon() function, this function uses a rewinding
    technique to make sure that overlapping subpaths can be filled
    using the correct fill rule. Note that rewinding inserts addition
    lines in the polygons so the outline of the fill polygon does not
    match the outline of the path.

    \sa toSubpathPolygons(), toFillPolygon(),
    {QPainterPath#QPainterPath Conversion}{QPainterPath Conversion}
*/
QList<QPolygonF> QPainterPath::toFillPolygons(const QTransform &matrix) const
{

    QList<QPolygonF> polys;

    QList<QPolygonF> subpaths = toSubpathPolygons(matrix);
    int count = subpaths.size();

    if (count == 0)
        return polys;

    QList<QRectF> bounds;
    for (int i=0; i<count; ++i)
        bounds += subpaths.at(i).boundingRect();

#ifdef QPP_FILLPOLYGONS_DEBUG
    printf("QPainterPath::toFillPolygons, subpathCount=%d\n", count);
    for (int i=0; i<bounds.size(); ++i)
        qDebug() << " bounds" << i << bounds.at(i);
#endif

    QVector< QList<int> > isects;
    isects.resize(count);

    // find all intersections
    for (int j=0; j<count; ++j) {
        if (subpaths.at(j).size() <= 2)
            continue;
        QRectF cbounds = bounds.at(j);
        for (int i=0; i<count; ++i) {
            if (rect_intersects(cbounds, bounds.at(i))) {
                isects[j] << i;
            }
        }
    }

#ifdef QPP_FILLPOLYGONS_DEBUG
    printf("Intersections before flattening:\n");
    for (int i = 0; i < count; ++i) {
        printf("%d: ", i);
        for (int j = 0; j < isects[i].size(); ++j) {
            printf("%d ", isects[i][j]);
        }
        printf("\n");
    }
#endif

    // flatten the sets of intersections
    for (int i=0; i<count; ++i) {
        const QList<int> &current_isects = isects.at(i);
        for (int j=0; j<current_isects.size(); ++j) {
            int isect_j = current_isects.at(j);
            if (isect_j == i)
                continue;
            for (int k=0; k<isects[isect_j].size(); ++k) {
                int isect_k = isects[isect_j][k];
                if (isect_k != i && !isects.at(i).contains(isect_k)) {
                    isects[i] += isect_k;
                }
            }
            isects[isect_j].clear();
        }
    }

#ifdef QPP_FILLPOLYGONS_DEBUG
    printf("Intersections after flattening:\n");
    for (int i = 0; i < count; ++i) {
        printf("%d: ", i);
        for (int j = 0; j < isects[i].size(); ++j) {
            printf("%d ", isects[i][j]);
        }
        printf("\n");
    }
#endif

    // Join the intersected subpaths as rewinded polygons
    for (int i=0; i<count; ++i) {
        const QList<int> &subpath_list = isects[i];
        if (!subpath_list.isEmpty()) {
            QPolygonF buildUp;
            for (int j=0; j<subpath_list.size(); ++j) {
                buildUp += subpaths.at(subpath_list.at(j));
                if (!buildUp.isClosed())
                    buildUp += buildUp.first();
            }
            polys += buildUp;
        }
    }

    return polys;
}

/*!
  \overload
 */
QList<QPolygonF> QPainterPath::toFillPolygons(const QMatrix &matrix) const
{
    return toFillPolygons(QTransform(matrix));
}

//same as qt_polygon_isect_line in qpolygon.cpp
static void qt_painterpath_isect_line(const QPointF &p1,
				      const QPointF &p2,
				      const QPointF &pos,
                                      int *winding)
{
    qreal x1 = p1.x();
    qreal y1 = p1.y();
    qreal x2 = p2.x();
    qreal y2 = p2.y();
    qreal y = pos.y();

    int dir = 1;

    if (qFuzzyCompare(y1, y2)) {
        // ignore horizontal lines according to scan conversion rule
        return;
    } else if (y2 < y1) {
        qreal x_tmp = x2; x2 = x1; x1 = x_tmp;
        qreal y_tmp = y2; y2 = y1; y1 = y_tmp;
        dir = -1;
    }

    if (y >= y1 && y < y2) {
        qreal x = x1 + ((x2 - x1) / (y2 - y1)) * (y - y1);

        // count up the winding number if we're
        if (x<=pos.x()) {
            (*winding) += dir;
        }
    }
}

static void qt_painterpath_isect_curve(const QBezier &bezier, const QPointF &pt,
                                       int *winding)
{
    qreal y = pt.y();
    qreal x = pt.x();
    QRectF bounds = bezier.bounds();

    // potential intersection, divide and try again...
    // Please note that a sideeffect of the bottom exclusion is that
    // horizontal lines are dropped, but this is correct according to
    // scan conversion rules.
    if (y >= bounds.y() && y < bounds.y() + bounds.height()) {

        // hit lower limit... This is a rough threshold, but its a
        // tradeoff between speed and precision.
        const qreal lower_bound = .001;
        if (bounds.width() < lower_bound && bounds.height() < lower_bound) {
            // We make the assumption here that the curve starts to
            // approximate a line after while (i.e. that it doesn't
            // change direction drastically during its slope)
            if (bezier.pt1().x() <= x) {
                (*winding) += (bezier.pt4().y() > bezier.pt1().y() ? 1 : -1);