KisBezierUtils::BezierSegment Class Reference

Public Member Functions
	BezierSegment (int degree=0, QPointF *p=0)
int	degree () const
QPointF	evaluate (qreal t, BezierSegment *left, BezierSegment *right) const
int	isFlat (qreal tolerance) const
QPointF	point (int index) const
void	printDebug () const
QList< qreal >	roots (int depth=0) const
void	setDegree (int degree)
void	setPoint (int index, const QPointF &p)

Static Public Member Functions
static uint	controlPolygonZeros (const QList< QPointF > &controlPoints)

Private Attributes
const qreal	FlatnessTolerance = ldexp(1.0,-MaxRecursionDepth-1)
	Flatness tolerance for finding root params.
const int	MaxRecursionDepth = 64
	Maximal recursion depth for finding root params.
QList< QPointF >	points

Detailed Description

Definition at line 84 of file KisBezierUtils.cpp.

Constructor & Destructor Documentation

BezierSegment()

KisBezierUtils::BezierSegment::BezierSegment ( int degree = 0, QPointF * p = 0 )

inline

Definition at line 93 of file KisBezierUtils.cpp.

    {
        if (degree) {
            for (int i = 0; i <= degree; ++i)
                points.append(p[i]);
        }
    }

References degree(), p, and points.

Member Function Documentation

controlPolygonZeros()

static uint KisBezierUtils::BezierSegment::controlPolygonZeros ( const QList< QPointF > & controlPoints )

inlinestatic

Definition at line 212 of file KisBezierUtils.cpp.

    {
        int controlPointCount = controlPoints.count();
        if (controlPointCount < 2)
            return 0;
 
        int signChanges = 0;
 
        int currSign = controlPoints[0].y() < 0.0 ? -1 : 1;
        int oldSign;
 
        for (short i = 1; i < controlPointCount; ++i) {
            oldSign = currSign;
            currSign = controlPoints[i].y() < 0.0 ? -1 : 1;
 
            if (currSign != oldSign) {
                ++signChanges;
            }
        }
 
 
        return signChanges;
    }

degree()

int KisBezierUtils::BezierSegment::degree ( ) const

inline

Definition at line 110 of file KisBezierUtils.cpp.

    {
        return points.count() - 1;
    }

References points.

evaluate()

QPointF KisBezierUtils::BezierSegment::evaluate ( qreal t, BezierSegment * left, BezierSegment * right ) const

inline

Definition at line 131 of file KisBezierUtils.cpp.

    {
        int deg = degree();
        if (! deg)
            return QPointF();
 
        QVector<QVector<QPointF> > Vtemp(deg + 1);
        for (int i = 0; i <= deg; ++i)
            Vtemp[i].resize(deg + 1);
 
        /* Copy control points  */
        for (int j = 0; j <= deg; j++) {
            Vtemp[0][j] = points[j];
        }
 
        /* Triangle computation */
        for (int i = 1; i <= deg; i++) {
            for (int j =0 ; j <= deg - i; j++) {
                Vtemp[i][j].rx() = (1.0 - t) * Vtemp[i-1][j].x() + t * Vtemp[i-1][j+1].x();
                Vtemp[i][j].ry() = (1.0 - t) * Vtemp[i-1][j].y() + t * Vtemp[i-1][j+1].y();
            }
        }
 
        if (left) {
            left->setDegree(deg);
            for (int j = 0; j <= deg; j++) {
                left->setPoint(j, Vtemp[j][0]);
            }
        }
        if (right) {
            right->setDegree(deg);
            for (int j = 0; j <= deg; j++) {
                right->setPoint(j, Vtemp[deg-j][j]);
            }
        }
 
        return (Vtemp[deg][0]);
    }

References degree(), points, setDegree(), and setPoint().

isFlat()

int KisBezierUtils::BezierSegment::isFlat ( qreal tolerance ) const

inline

Definition at line 236 of file KisBezierUtils.cpp.

    {
        int deg = degree();
 
        // Find the  perpendicular distance from each interior control point to
        // the line connecting points[0] and points[degree]
        qreal *distance = new qreal[deg + 1];
 
        // Derive the implicit equation for line connecting first and last control points
        qreal a = points[0].y() - points[deg].y();
        qreal b = points[deg].x() - points[0].x();
        qreal c = points[0].x() * points[deg].y() - points[deg].x() * points[0].y();
 
        qreal abSquared = (a * a) + (b * b);
 
        for (int i = 1; i < deg; i++) {
            // Compute distance from each of the points to that line
            distance[i] = a * points[i].x() + b * points[i].y() + c;
            if (distance[i] > 0.0) {
                distance[i] = (distance[i] * distance[i]) / abSquared;
            }
            if (distance[i] < 0.0) {
                distance[i] = -((distance[i] * distance[i]) / abSquared);
            }
        }
 
 
        // Find the largest distance
        qreal max_distance_above = 0.0;
        qreal max_distance_below = 0.0;
        for (int i = 1; i < deg; i++) {
            if (distance[i] < 0.0) {
                max_distance_below = qMin(max_distance_below, distance[i]);
            }
            if (distance[i] > 0.0) {
                max_distance_above = qMax(max_distance_above, distance[i]);
            }
        }
        delete [] distance;
 
        // Implicit equation for zero line
        qreal a1 = 0.0;
        qreal b1 = 1.0;
        qreal c1 = 0.0;
 
        // Implicit equation for "above" line
        qreal a2 = a;
        qreal b2 = b;
        qreal c2 = c + max_distance_above;
 
        qreal det = a1 * b2 - a2 * b1;
        qreal dInv = 1.0/det;
 
        qreal intercept_1 = (b1 * c2 - b2 * c1) * dInv;
 
        // Implicit equation for "below" line
        a2 = a;
        b2 = b;
        c2 = c + max_distance_below;
 
        det = a1 * b2 - a2 * b1;
        dInv = 1.0/det;
 
        qreal intercept_2 = (b1 * c2 - b2 * c1) * dInv;
 
        // Compute intercepts of bounding box
        qreal left_intercept = qMin(intercept_1, intercept_2);
        qreal right_intercept = qMax(intercept_1, intercept_2);
 
        qreal error = 0.5 * (right_intercept-left_intercept);
 
        return (error < tolerance);
    }

References degree(), distance(), and points.

point()

QPointF KisBezierUtils::BezierSegment::point ( int index ) const

inline

Definition at line 115 of file KisBezierUtils.cpp.

    {
        if (static_cast<int>(index) > degree())
            return QPointF();
 
        return points[index];
    }

References degree(), and points.

printDebug()

void KisBezierUtils::BezierSegment::printDebug ( ) const

inline

Definition at line 311 of file KisBezierUtils.cpp.

    {
        int index = 0;
        Q_FOREACH (const QPointF &p, points) {
            qDebug() << QString("P%1 ").arg(index++) << p;
        }
    }

References p, and points.

roots()

QList< qreal > KisBezierUtils::BezierSegment::roots ( int depth = 0 ) const

inline

Definition at line 170 of file KisBezierUtils.cpp.

    {
        QList<qreal> rootParams;
 
        if (! degree())
            return rootParams;
 
        // Calculate how often the control polygon crosses the x-axis
        // This is the upper limit for the number of roots.
        int xAxisCrossings = controlPolygonZeros(points);
 
        if (! xAxisCrossings) {
            // No solutions.
            return rootParams;
        }
        else if (xAxisCrossings == 1) {
            // Exactly one solution.
 
            // Stop recursion when the tree is deep enough
            if (depth >= MaxRecursionDepth) {
                // if deep enough, return 1 solution at midpoint
                rootParams.append((points.first().x() + points.last().x()) / 2.0);
                return rootParams;
            }
            else if (isFlat(FlatnessTolerance)) {
                // Calculate intersection of chord with x-axis.
                QPointF chord = points.last() - points.first();
                QPointF segStart = points.first();
                rootParams.append((chord.x() * segStart.y() - chord.y() * segStart.x()) / - chord.y());
                return rootParams;
            }
        }
 
        // Many solutions. Do recursive midpoint subdivision.
        BezierSegment left, right;
        evaluate(0.5, &left, &right);
        rootParams += left.roots(depth+1);
        rootParams += right.roots(depth+1);
 
        return rootParams;
    }

References controlPolygonZeros(), degree(), evaluate(), FlatnessTolerance, isFlat(), MaxRecursionDepth, points, and roots().

setDegree()

void KisBezierUtils::BezierSegment::setDegree ( int degree )

inline

Definition at line 101 of file KisBezierUtils.cpp.

    {
        points.clear();
        if (degree) {
            for (int i = 0; i <= degree; ++i)
                points.append(QPointF());
        }
    }

References degree(), and points.

setPoint()

void KisBezierUtils::BezierSegment::setPoint ( int index, const QPointF & p )

inline

Definition at line 123 of file KisBezierUtils.cpp.

    {
        if (static_cast<int>(index) > degree())
            return;
 
        points[index] = p;
    }

References degree(), p, and points.

Member Data Documentation

FlatnessTolerance

const qreal KisBezierUtils::BezierSegment::FlatnessTolerance = ldexp(1.0,-MaxRecursionDepth-1)

private

Flatness tolerance for finding root params.

Definition at line 90 of file KisBezierUtils.cpp.

MaxRecursionDepth

const int KisBezierUtils::BezierSegment::MaxRecursionDepth = 64

private

Maximal recursion depth for finding root params.

Definition at line 88 of file KisBezierUtils.cpp.

points

QList<QPointF> KisBezierUtils::BezierSegment::points

private

Definition at line 321 of file KisBezierUtils.cpp.

---

The documentation for this class was generated from the following file:

• libs/global/KisBezierUtils.cpp