qbezier.cpp

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

/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the QtGui module of the Qt Toolkit.
**
** This file may be used under the terms of the GNU General Public
** License version 2.0 as published by the Free Software Foundation
** and appearing in the file LICENSE.GPL included in the packaging of
** this file.  Please review the following information to ensure GNU
** General Public Licensing requirements will be met:
** http://trolltech.com/products/qt/licenses/licensing/opensource/
**
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
** or contact the sales department at [e-mail].
**
** In addition, as a special exception, Trolltech gives you certain
** additional rights. These rights are described in the Trolltech GPL
** Exception version 1.0, which can be found at
** http://www.trolltech.com/products/qt/gplexception/ and in the file
** GPL_EXCEPTION.txt in this package.
**
** In addition, as a special exception, Trolltech, as the sole copyright
** holder for Qt Designer, grants users of the Qt/Eclipse Integration
** plug-in the right for the Qt/Eclipse Integration to link to
** functionality provided by Qt Designer and its related libraries.
**
** Trolltech reserves all rights not expressly granted herein.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/

#include "qbezier_p.h"
#include <qdebug.h>
#include <qline.h>
#include <qpolygon.h>
#include <qvector.h>
#include <qlist.h>

#include <private/qnumeric_p.h>
#include <private/qmath_p.h>

//#define QDEBUG_BEZIER

#ifdef FLOAT_ACCURACY
#define INV_EPS (1L<<23)
#else
/* The value of 1.0 / (1L<<14) is enough for most applications */
#define INV_EPS (1L<<14)
#endif

#ifndef M_SQRT2
#define M_SQRT2	1.41421356237309504880
#endif

#define log2(x) (qLog(x)/qLog(2.))

static inline qreal log4(qreal x)
{
    return qreal(0.5) * log2(x);
}

/*!
  \internal
*/
QBezier QBezier::fromPoints(const QPointF &p1, const QPointF &p2,
                            const QPointF &p3, const QPointF &p4)
{
    QBezier b;
    b.x1 = p1.x();
    b.y1 = p1.y();
    b.x2 = p2.x();
    b.y2 = p2.y();
    b.x3 = p3.x();
    b.y3 = p3.y();
    b.x4 = p4.x();
    b.y4 = p4.y();
    return b;
}

/*!
  \internal
*/
QPolygonF QBezier::toPolygon() const
{
    // flattening is done by splitting the bezier until we can replace the segment by a straight
    // line. We split further until the control points are close enough to the line connecting the
    // boundary points.
    //
    // the Distance of a point p from a line given by the points (a,b) is given by:
    //
    // d = abs( (bx - ax)(ay - py) - (by - ay)(ax - px) ) / line_length
    //
    // We can stop splitting if both control points are close enough to the line.
    // To make the algorithm faster we use the manhattan length of the line.

    QPolygonF polygon;
    polygon.append(QPointF(x1, y1));
    addToPolygon(&polygon);
    return polygon;
}

//0.5 is really low
static const qreal flatness = 0.5;

//based on "Fast, precise flattening of cubic Bezier path and offset curves"
//      by T. F. Hain, A. L. Ahmad, S. V. R. Racherla and D. D. Langan
static inline void flattenBezierWithoutInflections(QBezier &bez,
                                                   QPolygonF *&p)
{
    QBezier left;

    while (1) {
        qreal dx = bez.x2 - bez.x1;
        qreal dy = bez.y2 - bez.y1;

        qreal normalized = qSqrt(dx * dx + dy * dy);
        if (qFuzzyCompare(normalized, 0))
           break;

        qreal d = qAbs(dx * (bez.y3 - bez.y2) - dy * (bez.x3 - bez.x2));

        qreal t = qSqrt(4. / 3. * normalized * flatness / d);
        if (t > 1 || qFuzzyCompare(t, (qreal)1.))
            break;
        bez.parameterSplitLeft(t, &left);
        p->append(bez.pt1());
    }
}


static inline int quadraticRoots(qreal a, qreal b, qreal c,
                                 qreal *x1, qreal *x2)
{
    if (qFuzzyCompare(a, 0)) {
        if (qFuzzyCompare(b, 0))
            return 0;
        *x1 = *x2 = (-c / b);
        return 1;
    } else {
        const qreal det = b * b - 4 * a * c;
        if (qFuzzyCompare(det, 0)) {
            *x1 = *x2 = -b / (2 * a);
            return 1;
        }
        if (det > 0) {
            if (qFuzzyCompare(b, 0)) {
                *x2 = qSqrt(-c / a);
                *x1 = -(*x2);
                return 2;
            }
            const qreal stableA = b / (2 * a);
            const qreal stableB = c / (a * stableA * stableA);
            const qreal stableC = -1 - qSqrt(1 - stableB);
            *x2 = stableA * stableC;
            *x1 = (stableA * stableB) / stableC;
            return 2;
        } else
            return 0;
    }
}

static inline bool findInflections(qreal a, qreal b, qreal c,
                                   qreal *t1 , qreal *t2, qreal *tCups)
{
    qreal r1 = 0, r2 = 0;

    short rootsCount = quadraticRoots(a, b, c, &r1, &r2);

    if (rootsCount >= 1) {
        if (r1 < r2) {
            *t1 = r1;
            *t2 = r2;
        } else {
            *t1 = r2;
            *t2 = r1;
        }
        if (!qFuzzyCompare(a, 0))
            *tCups = 0.5 * (-b / a);
        else
            *tCups = 2;

        return true;
    }

    return false;
}


void QBezier::addToPolygon(QPolygonF *polygon) const
{
    QBezier beziers[32];
    beziers[0] = *this;
    QBezier *b = beziers;

    while (b >= beziers) {
        // check if we can pop the top bezier curve from the stack
        qreal y4y1 = b->y4 - b->y1;
        qreal x4x1 = b->x4 - b->x1;
        qreal l = qAbs(x4x1) + qAbs(y4y1);
        qreal d;
        if (l > 1.) {
            d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )
                + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );
        } else {
            d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
                qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
            l = 1.;
        }
        if (d < flatness*l || b == beziers + 31) {
            // good enough, we pop it off and add the endpoint
            polygon->append(QPointF(b->x4, b->y4));
            --b;
        } else {
            // split, second half of the polygon goes lower into the stack
            b->split(b+1, b);
            ++b;
        }
    }
}

void QBezier::addToPolygonMixed(QPolygonF *polygon) const
{
    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;
    qreal a = 6 * (ay * bx - ax * by);
    qreal b = 6 * (ay * cx - ax * cy);
    qreal c = 2 * (by * cx - bx * cy);

    if ((qFuzzyCompare(a, 0) && qFuzzyCompare(b, 0)) ||
        (b * b - 4 * a *c) < 0) {
        QBezier bez(*this);
        flattenBezierWithoutInflections(bez, polygon);
        polygon->append(QPointF(x4, y4));
    } else {
        QBezier beziers[32];
        beziers[0] = *this;
        QBezier *b = beziers;

        while (b >= beziers) {
            // check if we can pop the top bezier curve from the stack
            qreal y4y1 = b->y4 - b->y1;
            qreal x4x1 = b->x4 - b->x1;
            qreal l = qAbs(x4x1) + qAbs(y4y1);
            qreal d;
            if (l > 1.) {
                d = qAbs( (x4x1)*(b->y1 - b->y2) - (y4y1)*(b->x1 - b->x2) )
                    + qAbs( (x4x1)*(b->y1 - b->y3) - (y4y1)*(b->x1 - b->x3) );
            } else {
                d = qAbs(b->x1 - b->x2) + qAbs(b->y1 - b->y2) +
                    qAbs(b->x1 - b->x3) + qAbs(b->y1 - b->y3);
                l = 1.;
            }
            if (d < .5*l || b == beziers + 31) {
                // good enough, we pop it off and add the endpoint
                polygon->append(QPointF(b->x4, b->y4));
                --b;
            } else {
                // split, second half of the polygon goes lower into the stack
                b->split(b+1, b);
                ++b;
            }
        }
    }
}

QRectF QBezier::bounds() const
{
    qreal xmin = x1;
    qreal xmax = x1;
    if (x2 < xmin)
        xmin = x2;
    else if (x2 > xmax)
        xmax = x2;
    if (x3 < xmin)
        xmin = x3;
    else if (x3 > xmax)
        xmax = x3;
    if (x4 < xmin)
        xmin = x4;
    else if (x4 > xmax)
        xmax = x4;

    qreal ymin = y1;
    qreal ymax = y1;
    if (y2 < ymin)
        ymin = y2;
    else if (y2 > ymax)
        ymax = y2;
    if (y3 < ymin)
        ymin = y3;
    else if (y3 > ymax)
        ymax = y3;
    if (y4 < ymin)
        ymin = y4;
    else if (y4 > ymax)
        ymax = y4;
    return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
}


enum ShiftResult {
    Ok,
    Discard,
    Split,
    Circle
};

static ShiftResult good_offset(const QBezier *b1, const QBezier *b2, qreal offset, qreal threshold)
{
    const qreal o2 = offset*offset;
    const qreal max_dist_line = threshold*offset*offset;
    const qreal max_dist_normal = threshold*offset;
    const qreal spacing = 0.25;
    for (qreal i = spacing; i < 0.99; i += spacing) {
        QPointF p1 = b1->pointAt(i);
        QPointF p2 = b2->pointAt(i);
        qreal d = (p1.x() - p2.x())*(p1.x() - p2.x()) + (p1.y() - p2.y())*(p1.y() - p2.y());
        if (qAbs(d - o2) > max_dist_line)
            return Split;

        QPointF normalPoint = b1->normalVector(i);
        qreal l = qAbs(normalPoint.x()) + qAbs(normalPoint.y());
        if (l != 0.) {
            d = qAbs( normalPoint.x()*(p1.y() - p2.y()) - normalPoint.y()*(p1.x() - p2.x()) ) / l;
            if (d > max_dist_normal)
                return Split;
        }
    }
    return Ok;
}

static inline QLineF qline_shifted(const QPointF &p1, const QPointF &p2, qreal offset)
{
    QLineF l(p1, p2);
    QLineF ln = l.normalVector().unitVector();
    l.translate(ln.dx() * offset, ln.dy() * offset);
    return l;
}

static bool qbezier_is_line(QPointF *points, int pointCount)
{
    Q_ASSERT(pointCount > 2);

    qreal dx13 = points[2].x() - points[0].x();
    qreal dy13 = points[2].y() - points[0].y();

    qreal dx12 = points[1].x() - points[0].x();
    qreal dy12 = points[1].y() - points[0].y();

    if (pointCount == 3) {
        if (dx13 * dx12 != 0)
            return qFuzzyCompare(dy12 / dx12, dy13 / dx13);
        else
            return qFuzzyCompare(dx12 / dy12, dx13 / dy13);

    } else if (pointCount == 4) {
        qreal dx14 = points[3].x() - points[0].x();
        qreal dy14 = points[3].y() - points[0].y();

        if (dx14*dx13*dx12 != 0) {
            qreal b14 = dy14 / dx14;
            qreal b13 = dy13 / dx13;
            qreal b12 = dy12 / dx12;
            return qFuzzyCompare(b14, b13) && qFuzzyCompare(b14, b12);

        } else {
            qreal a14 = dx14 / dy14;
            qreal a13 = dx13 / dy13;
            qreal a12 = dx12 / dy12;
            return qFuzzyCompare(a14, a13) && qFuzzyCompare(a14, a12);
        }
    }

    return false;
}

static ShiftResult shift(const QBezier *orig, QBezier *shifted, qreal offset, qreal threshold)
{
    int map[4];
    bool p1_p2_equal = (orig->x1 == orig->x2 && orig->y1 == orig->y2);
    bool p2_p3_equal = (orig->x2 == orig->x3 && orig->y2 == orig->y3);
    bool p3_p4_equal = (orig->x3 == orig->x4 && orig->y3 == orig->y4);

    QPointF points[4];
    int np = 0;
    points[np] = QPointF(orig->x1, orig->y1);
    map[0] = 0;
    ++np;
    if (!p1_p2_equal) {
        points[np] = QPointF(orig->x2, orig->y2);
        ++np;
    }
    map[1] = np - 1;
    if (!p2_p3_equal) {
        points[np] = QPointF(orig->x3, orig->y3);
        ++np;
    }
    map[2] = np - 1;
    if (!p3_p4_equal) {
        points[np] = QPointF(orig->x4, orig->y4);
        ++np;