diff options
author | Kim Motoyoshi Kalland <kim.kalland@nokia.com> | 2011-07-14 15:55:29 +0200 |
---|---|---|
committer | Qt by Nokia <qt-info@nokia.com> | 2011-07-20 06:57:44 +0200 |
commit | 0e743ee1691509f1c6b7a740de8a4f381114168a (patch) | |
tree | 3efe527d239c85f13ea57dfa155ef49943ce164f /src/declarative/scenegraph | |
parent | a9b1594576579044c26ef325191a79ffe1df7e27 (diff) |
Improved the performance of distance-field generation.
Change-Id: Ie17650196c7e4531cbc6f760905e41d95808efcd
Reviewed-on: http://codereview.qt.nokia.com/1675
Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com>
Reviewed-by: Samuel Rødal <samuel.rodal@nokia.com>
Diffstat (limited to 'src/declarative/scenegraph')
-rw-r--r-- | src/declarative/scenegraph/qsgdistancefieldglyphcache.cpp | 914 | ||||
-rw-r--r-- | src/declarative/scenegraph/qsgpathsimplifier.cpp | 1673 | ||||
-rw-r--r-- | src/declarative/scenegraph/qsgpathsimplifier_p.h | 68 | ||||
-rw-r--r-- | src/declarative/scenegraph/scenegraph.pri | 6 |
4 files changed, 2327 insertions, 334 deletions
diff --git a/src/declarative/scenegraph/qsgdistancefieldglyphcache.cpp b/src/declarative/scenegraph/qsgdistancefieldglyphcache.cpp index 1e714471f4..2cd3db4074 100644 --- a/src/declarative/scenegraph/qsgdistancefieldglyphcache.cpp +++ b/src/declarative/scenegraph/qsgdistancefieldglyphcache.cpp @@ -42,7 +42,7 @@ #include "qsgdistancefieldglyphcache_p.h" #include <qmath.h> -#include <private/qtriangulator_p.h> +#include <private/qsgpathsimplifier_p.h> #include <private/qdeclarativeglobal_p.h> #include <qglshaderprogram.h> #include <private/qglengineshadersource_p.h> @@ -86,403 +86,652 @@ static inline int qt_next_power_of_two(int v) return v; } -struct DFPoint -{ - float x, y; -}; - -struct DFVertex -{ - DFPoint p; - float d; -}; - -static void drawRectangle(float *bits, int width, int height, const DFVertex *v1, const DFVertex *v2, const DFVertex *v3, const DFVertex *v4) -{ - float minY = qMin(qMin(v1->p.y, v2->p.y), qMin(v3->p.y, v4->p.y)); - if (v2->p.y == minY) { - const DFVertex *tmp = v1; - v1 = v2; - v2 = v3; - v3 = v4; - v4 = tmp; - } else if (v3->p.y == minY) { - const DFVertex *tmp1 = v1; - const DFVertex *tmp2 = v2; - v1 = v3; - v2 = v4; - v3 = tmp1; - v4 = tmp2; - } else if (v4->p.y == minY) { - const DFVertex *tmp = v4; - v4 = v3; - v3 = v2; - v2 = v1; - v1 = tmp; - } - - /* - v1 - / \ - v4 v2 - \ / - v3 - */ - - int fromY = qMax(0, qCeil(v1->p.y)); - int midY1 = qMin(height, qCeil(qMin(v2->p.y, v4->p.y))); - int midY2 = qMin(height, qCeil(qMax(v2->p.y, v4->p.y))); - int toY = qMin(height, qCeil(v3->p.y)); +namespace +{ + enum FillHDir + { + LeftToRight, + RightToLeft + }; - if (toY <= fromY) - return; + enum FillVDir + { + TopDown, + BottomUp + }; - bits += width * fromY; - int y = fromY; + enum FillClip + { + NoClip, + Clip + }; +} - float leftDx = (v4->p.x - v1->p.x) / (v4->p.y - v1->p.y); - float leftDd = (v4->d - v1->d) / (v4->p.y - v1->p.y); - float leftX = v1->p.x + (fromY - v1->p.y) * leftDx; - float leftD = v1->d + (fromY - v1->p.y) * leftDd; +template <FillClip clip, FillHDir dir> +inline void fillLine(qint32 *, int, int, int, qint32, qint32) +{ +} - float rightDx = (v2->p.x - v1->p.x) / (v2->p.y - v1->p.y); - float rightDd = (v2->d - v1->d) / (v2->p.y - v1->p.y); - float rightX = v1->p.x + (fromY - v1->p.y) * rightDx; - float rightD = v1->d + (fromY - v1->p.y) * rightDd; +template <> +inline void fillLine<Clip, LeftToRight>(qint32 *line, int width, int lx, int rx, qint32 d, qint32 dd) +{ + int fromX = qMax(0, lx >> 8); + int toX = qMin(width, rx >> 8); + int x = toX - fromX; + if (x <= 0) + return; + qint32 val = d + (((fromX << 8) + 0xff - lx) * dd >> 8); + line += fromX; + do { + *line = abs(val) < abs(*line) ? val : *line; + val += dd; + ++line; + } while (--x); +} - float dd = ((v2->d - v1->d) * (v3->p.y - v1->p.y) - (v2->p.y - v1->p.y) * (v3->d - v1->d)) - / ((v2->p.x - v1->p.x) * (v3->p.y - v1->p.y) - (v2->p.y - v1->p.y) * (v3->p.x - v1->p.x)); +template <> +inline void fillLine<Clip, RightToLeft>(qint32 *line, int width, int lx, int rx, qint32 d, qint32 dd) +{ + int fromX = qMax(0, lx >> 8); + int toX = qMin(width, rx >> 8); + int x = toX - fromX; + if (x <= 0) + return; + qint32 val = d + (((toX << 8) + 0xff - rx) * dd >> 8); + line += toX; + do { + val -= dd; + --line; + *line = abs(val) < abs(*line) ? val : *line; + } while (--x); +} - for (; y < midY1; ++y, leftX += leftDx, leftD += leftDd, rightX += rightDx, rightD += rightDd, bits += width) { - int fromX = qMax(0, qCeil(leftX)); - int toX = qMin(width, qCeil(rightX)); - if (toX <= fromX) - continue; - float d = leftD + (fromX - leftX) * dd; - for (int x = fromX; x < toX; ++x, d += dd) { - if (abs(d) < abs(bits[x])) - bits[x] = d; - } - } +template <> +inline void fillLine<NoClip, LeftToRight>(qint32 *line, int, int lx, int rx, qint32 d, qint32 dd) +{ + int fromX = lx >> 8; + int toX = rx >> 8; + int x = toX - fromX; + if (x <= 0) + return; + qint32 val = d + ((~lx & 0xff) * dd >> 8); + line += fromX; + do { + *line = abs(val) < abs(*line) ? val : *line; + val += dd; + ++line; + } while (--x); +} - if (midY1 == toY) +template <> +inline void fillLine<NoClip, RightToLeft>(qint32 *line, int, int lx, int rx, qint32 d, qint32 dd) +{ + int fromX = lx >> 8; + int toX = rx >> 8; + int x = toX - fromX; + if (x <= 0) return; + qint32 val = d + ((~rx & 0xff) * dd >> 8); + line += toX; + do { + val -= dd; + --line; + *line = abs(val) < abs(*line) ? val : *line; + } while (--x); +} - if (v2->p.y > v4->p.y) { - // Long right edge. - leftDx = (v3->p.x - v4->p.x) / (v3->p.y - v4->p.y); - leftDd = (v3->d - v4->d) / (v3->p.y - v4->p.y); - leftX = v4->p.x + (midY1 - v4->p.y) * leftDx; - leftD = v4->d + (midY1 - v4->p.y) * leftDd; +template <FillClip clip, FillVDir vDir, FillHDir hDir> +inline void fillLines(qint32 *bits, int width, int height, int upperY, int lowerY, + int &lx, int ldx, int &rx, int rdx, qint32 &d, qint32 ddy, qint32 ddx) +{ + Q_UNUSED(height); + Q_ASSERT(upperY < lowerY); + int y = lowerY - upperY; + if (vDir == TopDown) { + qint32 *line = bits + upperY * width; + do { + fillLine<clip, hDir>(line, width, lx, rx, d, ddx); + lx += ldx; + d += ddy; + rx += rdx; + line += width; + } while (--y); } else { - // Long left edge. - rightDx = (v3->p.x - v2->p.x) / (v3->p.y - v2->p.y); - rightDd = (v3->d - v2->d) / (v3->p.y - v2->p.y); - rightX = v2->p.x + (midY1 - v2->p.y) * rightDx; - rightD = v2->d + (midY1 - v2->p.y) * rightDd; + qint32 *line = bits + lowerY * width; + do { + lx -= ldx; + d -= ddy; + rx -= rdx; + line -= width; + fillLine<clip, hDir>(line, width, lx, rx, d, ddx); + } while (--y); } +} - for (; y < midY2; ++y, leftX += leftDx, leftD += leftDd, rightX += rightDx, rightD += rightDd, bits += width) { - int fromX = qMax(0, qCeil(leftX)); - int toX = qMin(width, qCeil(rightX)); - if (toX <= fromX) - continue; - float d = leftD + (fromX - leftX) * dd; - for (int x = fromX; x < toX; ++x, d += dd) { - if (abs(d) < abs(bits[x])) - bits[x] = d; - } +template <FillClip clip> +void drawTriangle(qint32 *bits, int width, int height, const QPoint *center, + const QPoint *v1, const QPoint *v2, qint32 value) +{ + const int y1 = clip == Clip ? qBound(0, v1->y() >> 8, height) : v1->y() >> 8; + const int y2 = clip == Clip ? qBound(0, v2->y() >> 8, height) : v2->y() >> 8; + const int yC = clip == Clip ? qBound(0, center->y() >> 8, height) : center->y() >> 8; + + const int v1Frac = clip == Clip ? (y1 << 8) + 0xff - v1->y() : ~v2->y() & 0xff; + const int v2Frac = clip == Clip ? (y2 << 8) + 0xff - v2->y() : ~v1->y() & 0xff; + const int centerFrac = clip == Clip ? (yC << 8) + 0xff - center->y() : ~center->y() & 0xff; + + int dx1, x1, dx2, x2; + qint32 dd1, d1, dd2, d2; + if (v1->y() != center->y()) { + dx1 = ((v1->x() - center->x()) << 8) / (v1->y() - center->y()); + x1 = center->x() + centerFrac * (v1->x() - center->x()) / (v1->y() - center->y()); } - - if (midY2 == toY) - return; - - if (v2->p.y > v4->p.y) { - // Long left edge. - rightDx = (v3->p.x - v2->p.x) / (v3->p.y - v2->p.y); - rightDd = (v3->d - v2->d) / (v3->p.y - v2->p.y); - rightX = v2->p.x + (midY2 - v2->p.y) * rightDx; - rightD = v2->d + (midY2 - v2->p.y) * rightDd; - } else { - // Long right edge. - leftDx = (v3->p.x - v4->p.x) / (v3->p.y - v4->p.y); - leftDd = (v3->d - v4->d) / (v3->p.y - v4->p.y); - leftX = v4->p.x + (midY2 - v4->p.y) * leftDx; - leftD = v4->d + (midY2 - v4->p.y) * leftDd; + if (v2->y() != center->y()) { + dx2 = ((v2->x() - center->x()) << 8) / (v2->y() - center->y()); + x2 = center->x() + centerFrac * (v2->x() - center->x()) / (v2->y() - center->y()); } - for (; y < toY; ++y, leftX += leftDx, leftD += leftDd, rightX += rightDx, rightD += rightDd, bits += width) { - int fromX = qMax(0, qCeil(leftX)); - int toX = qMin(width, qCeil(rightX)); - if (toX <= fromX) - continue; - float d = leftD + (fromX - leftX) * dd; - for (int x = fromX; x < toX; ++x, d += dd) { - if (abs(d) < abs(bits[x])) - bits[x] = d; + const qint32 div = (v2->x() - center->x()) * (v1->y() - center->y()) + - (v2->y() - center->y()) * (v1->x() - center->x()); + const qint32 dd = div ? qint32((qint64(value * (v1->y() - v2->y())) << 8) / div) : 0; + + if (y2 < yC) { + if (y1 < yC) { + // Center at the bottom. + if (y2 < y1) { + // y2 < y1 < yC + // Long right edge. + d1 = centerFrac * value / (v1->y() - center->y()); + dd1 = ((value << 8) / (v1->y() - center->y())); + fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y1, yC, x1, dx1, + x2, dx2, d1, dd1, dd); + dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y()); + x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y()); + fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, y1, x1, dx1, + x2, dx2, value, 0, dd); + } else { + // y1 <= y2 < yC + // Long left edge. + d2 = centerFrac * value / (v2->y() - center->y()); + dd2 = ((value << 8) / (v2->y() - center->y())); + fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y2, yC, x1, dx1, + x2, dx2, d2, dd2, dd); + if (y1 != y2) { + dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y()); + x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y()); + fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, y2, x1, dx1, + x2, dx2, value, 0, dd); + } + } + } else { + // y2 < yC <= y1 + // Center to the right. + int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y()); + int xUp, xDn; + xUp = xDn = v2->x() + (clip == Clip ? (yC << 8) + 0xff - v2->y() + : (center->y() | 0xff) - v2->y()) + * (v1->x() - v2->x()) / (v1->y() - v2->y()); + fillLines<clip, BottomUp, LeftToRight>(bits, width, height, y2, yC, xUp, dx, + x2, dx2, value, 0, dd); + if (yC != y1) + fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y1, xDn, dx, + x1, dx1, value, 0, dd); + } + } else { + if (y1 < yC) { + // y1 < yC <= y2 + // Center to the left. + int dx = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y()); + int xUp, xDn; + xUp = xDn = v1->x() + (clip == Clip ? (yC << 8) + 0xff - v1->y() + : (center->y() | 0xff) - v1->y()) + * (v1->x() - v2->x()) / (v1->y() - v2->y()); + fillLines<clip, BottomUp, RightToLeft>(bits, width, height, y1, yC, x1, dx1, + xUp, dx, value, 0, dd); + if (yC != y2) + fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y2, x2, dx2, + xDn, dx, value, 0, dd); + } else { + // Center at the top. + if (y2 < y1) { + // yC <= y2 < y1 + // Long right edge. + if (yC != y2) { + d2 = centerFrac * value / (v2->y() - center->y()); + dd2 = ((value << 8) / (v2->y() - center->y())); + fillLines<clip, TopDown, LeftToRight>(bits, width, height, yC, y2, x2, dx2, + x1, dx1, d2, dd2, dd); + } + dx2 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y()); + x2 = v2->x() + v2Frac * (v1->x() - v2->x()) / (v1->y() - v2->y()); + fillLines<clip, TopDown, LeftToRight>(bits, width, height, y2, y1, x2, dx2, + x1, dx1, value, 0, dd); + } else { + // Long left edge. + // yC <= y1 <= y2 + if (yC != y1) { + d1 = centerFrac * value / (v1->y() - center->y()); + dd1 = ((value << 8) / (v1->y() - center->y())); + fillLines<clip, TopDown, RightToLeft>(bits, width, height, yC, y1, x2, dx2, + x1, dx1, d1, dd1, dd); + } + if (y1 != y2) { + dx1 = ((v1->x() - v2->x()) << 8) / (v1->y() - v2->y()); + x1 = v1->x() + v1Frac * (v1->x() - v2->x()) / (v1->y() - v2->y()); + fillLines<clip, TopDown, RightToLeft>(bits, width, height, y1, y2, x2, dx2, + x1, dx1, value, 0, dd); + } + } } } } -static void drawTriangle(float *bits, int width, int height, const DFVertex *v1, const DFVertex *v2, const DFVertex *v3) +template <FillClip clip> +void drawRectangle(qint32 *bits, int width, int height, + const QPoint *int1, const QPoint *center1, const QPoint *ext1, + const QPoint *int2, const QPoint *center2, const QPoint *ext2, + qint32 extValue) { - float minY = qMin(qMin(v1->p.y, v2->p.y), v3->p.y); - if (v2->p.y == minY) { - const DFVertex *tmp = v1; - v1 = v2; - v2 = v3; - v3 = tmp; - } else if (v3->p.y == minY) { - const DFVertex *tmp = v3; - v3 = v2; - v2 = v1; - v1 = tmp; + if (center1->y() > center2->y()) { + qSwap(center1, center2); + qSwap(int1, ext2); + qSwap(ext1, int2); + extValue = -extValue; } - /* - v1 - / \ - v3--v2 - */ - - int fromY = qMax(0, qCeil(v1->p.y)); - int midY = qMin(height, qCeil(qMin(v2->p.y, v3->p.y))); - int toY = qMin(height, qCeil(qMax(v2->p.y, v3->p.y))); - - if (toY <= fromY) - return; - - float leftDx = (v3->p.x - v1->p.x) / (v3->p.y - v1->p.y); - float leftDd = (v3->d - v1->d) / (v3->p.y - v1->p.y); - float leftX = v1->p.x + (fromY - v1->p.y) * leftDx; - float leftD = v1->d + (fromY - v1->p.y) * leftDd; - - float rightDx = (v2->p.x - v1->p.x) / (v2->p.y - v1->p.y); - float rightDd = (v2->d - v1->d) / (v2->p.y - v1->p.y); - float rightX = v1->p.x + (fromY - v1->p.y) * rightDx; - float rightD = v1->d + (fromY - v1->p.y) * rightDd; - - float dd = ((v2->d - v1->d) * (v3->p.y - v1->p.y) - (v2->p.y - v1->p.y) * (v3->d - v1->d)) - / ((v2->p.x - v1->p.x) * (v3->p.y - v1->p.y) - (v2->p.y - v1->p.y) * (v3->p.x - v1->p.x)); - - bits += width * fromY; - int y = fromY; - for (; y < midY; ++y, leftX += leftDx, leftD += leftDd, rightX += rightDx, rightD += rightDd, bits += width) { - int fromX = qMax(0, qCeil(leftX)); - int toX = qMin(width, qCeil(rightX)); - if (toX <= fromX) - continue; - float d = leftD + (fromX - leftX) * dd; - for (int x = fromX; x < toX; ++x, d += dd) { - if (abs(d) < abs(bits[x])) - bits[x] = d; - } + Q_ASSERT(ext1->x() - center1->x() == center1->x() - int1->x()); + Q_ASSERT(ext1->y() - center1->y() == center1->y() - int1->y()); + Q_ASSERT(ext2->x() - center2->x() == center2->x() - int2->x()); + Q_ASSERT(ext2->y() - center2->y() == center2->y() - int2->y()); + + const int yc1 = clip == Clip ? qBound(0, center1->y() >> 8, height) : center1->y() >> 8; + const int yc2 = clip == Clip ? qBound(0, center2->y() >> 8, height) : center2->y() >> 8; + const int yi1 = clip == Clip ? qBound(0, int1->y() >> 8, height) : int1->y() >> 8; + const int yi2 = clip == Clip ? qBound(0, int2->y() >> 8, height) : int2->y() >> 8; + const int ye1 = clip == Clip ? qBound(0, ext1->y() >> 8, height) : ext1->y() >> 8; + const int ye2 = clip == Clip ? qBound(0, ext2->y() >> 8, height) : ext2->y() >> 8; + + const int center1Frac = clip == Clip ? (yc1 << 8) + 0xff - center1->y() : ~center1->y() & 0xff; + const int center2Frac = clip == Clip ? (yc2 << 8) + 0xff - center2->y() : ~center2->y() & 0xff; + const int int1Frac = clip == Clip ? (yi1 << 8) + 0xff - int1->y() : ~int1->y() & 0xff; + const int ext1Frac = clip == Clip ? (ye1 << 8) + 0xff - ext1->y() : ~ext1->y() & 0xff; + + int dxC, dxE; // cap slope, edge slope + qint32 ddC; + if (ext1->y() != int1->y()) { + dxC = ((ext1->x() - int1->x()) << 8) / (ext1->y() - int1->y()); + ddC = (extValue << 9) / (ext1->y() - int1->y()); } - - if (midY == toY) - return; - - if (v2->p.y > v3->p.y) { - // Long right edge. - leftDx = (v2->p.x - v3->p.x) / (v2->p.y - v3->p.y); - leftDd = (v2->d - v3->d) / (v2->p.y - v3->p.y); - leftX = v3->p.x + (midY - v3->p.y) * leftDx; - leftD = v3->d + (midY - v3->p.y) * leftDd; + if (ext1->y() != ext2->y()) + dxE = ((ext1->x() - ext2->x()) << 8) / (ext1->y() - ext2->y()); + + const qint32 div = (ext1->x() - int1->x()) * (ext2->y() - int1->y()) + - (ext1->y() - int1->y()) * (ext2->x() - int1->x()); + const qint32 dd = div ? qint32((qint64(extValue * (ext2->y() - ext1->y())) << 9) / div) : 0; + + int xe1, xe2, xc1, xc2; + qint32 d; + + qint32 intValue = -extValue; + + if (center2->x() < center1->x()) { + // Leaning to the right. '/' + if (int1->y() < ext2->y()) { + // Mostly vertical. + Q_ASSERT(ext1->y() != ext2->y()); + xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + if (ye1 != yi1) { + xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc2 += (ye1 - yc1) * dxC; + fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, yi1, xe1, dxE, + xc2, dxC, extValue, 0, dd); + } + if (yi1 != ye2) + fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi1, ye2, xe1, dxE, + xe2, dxE, extValue, 0, dd); + if (ye2 != yi2) { + xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc1 += (ye2 - yc2) * dxC; + fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye2, yi2, xc1, dxC, + xe2, dxE, intValue, 0, dd); + } + } else { + // Mostly horizontal. + Q_ASSERT(ext1->y() != int1->y()); + xc1 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc2 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc1 += (ye2 - yc2) * dxC; + xc2 += (ye1 - yc1) * dxC; + if (ye1 != ye2) { + xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE, + xc2, dxC, extValue, 0, dd); + } + if (ye2 != yi1) { + d = (clip == Clip ? (ye2 << 8) + 0xff - center2->y() + : (ext2->y() | 0xff) - center2->y()) + * 2 * extValue / (ext1->y() - int1->y()); + fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye2, yi1, xc1, dxC, + xc2, dxC, d, ddC, dd); + } + if (yi1 != yi2) { + xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC, + xe2, dxE, intValue, 0, dd); + } + } } else { - // Long left edge. - rightDx = (v3->p.x - v2->p.x) / (v3->p.y - v2->p.y); - rightDd = (v3->d - v2->d) / (v3->p.y - v2->p.y); - rightX = v2->p.x + (midY - v2->p.y) * rightDx; - rightD = v2->d + (midY - v2->p.y) * rightDd; + // Leaning to the left. '\' + if (ext1->y() < int2->y()) { + // Mostly vertical. + Q_ASSERT(ext1->y() != ext2->y()); + xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + if (yi1 != ye1) { + xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc1 += (yi1 - yc1) * dxC; + fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, ye1, xc1, dxC, + xe2, dxE, intValue, 0, dd); + } + if (ye1 != yi2) + fillLines<clip, TopDown, RightToLeft>(bits, width, height, ye1, yi2, xe1, dxE, + xe2, dxE, intValue, 0, dd); + if (yi2 != ye2) { + xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc2 += (yi2 - yc2) * dxC; + fillLines<clip, TopDown, LeftToRight>(bits, width, height, yi2, ye2, xe1, dxE, + xc2, dxC, extValue, 0, dd); + } + } else { + // Mostly horizontal. + Q_ASSERT(ext1->y() != int1->y()); + xc1 = center1->x() + center1Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc2 = center2->x() + center2Frac * (ext1->x() - int1->x()) / (ext1->y() - int1->y()); + xc1 += (yi1 - yc1) * dxC; + xc2 += (yi2 - yc2) * dxC; + if (yi1 != yi2) { + xe2 = int1->x() + int1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi1, yi2, xc1, dxC, + xe2, dxE, intValue, 0, dd); + } + if (yi2 != ye1) { + d = (clip == Clip ? (yi2 << 8) + 0xff - center2->y() + : (int2->y() | 0xff) - center2->y()) + * 2 * extValue / (ext1->y() - int1->y()); + fillLines<clip, TopDown, RightToLeft>(bits, width, height, yi2, ye1, xc1, dxC, + xc2, dxC, d, ddC, dd); + } + if (ye1 != ye2) { + xe1 = ext1->x() + ext1Frac * (ext1->x() - ext2->x()) / (ext1->y() - ext2->y()); + fillLines<clip, TopDown, LeftToRight>(bits, width, height, ye1, ye2, xe1, dxE, + xc2, dxC, extValue, 0, dd); + } + } } +} - for (; y < toY; ++y, leftX += leftDx, leftD += leftDd, rightX += rightDx, rightD += rightDd, bits += width) { - int fromX = qMax(0, qCeil(leftX)); - int toX = qMin(width, qCeil(rightX)); - if (toX <= fromX) +static void drawPolygons(qint32 *bits, int width, int height, const QPoint *vertices, + const quint32 *indices, int indexCount, qint32 value) +{ + Q_ASSERT(indexCount != 0); + Q_ASSERT(height <= 128); + QVarLengthArray<quint8, 16> scans[128]; + int first = 0; + for (int i = 1; i < indexCount; ++i) { + quint32 idx1 = indices[i - 1]; + quint32 idx2 = indices[i]; + Q_ASSERT(idx1 != quint32(-1)); + if (idx2 == quint32(-1)) { + idx2 = indices[first]; + Q_ASSERT(idx2 != quint32(-1)); + first = ++i; + } + const QPoint *v1 = &vertices[idx1]; + const QPoint *v2 = &vertices[idx2]; + if (v2->y() < v1->y()) + qSwap(v1, v2); + int fromY = qMax(0, v1->y() >> 8); + int toY = qMin(height, v2->y() >> 8); + if (fromY >= toY) continue; - float d = leftD + (fromX - leftX) * dd; - for (int x = fromX; x < toX; ++x, d += dd) { - if (abs(d) < abs(bits[x])) - bits[x] = d; + int dx = ((v2->x() - v1->x()) << 8) / (v2->y() - v1->y()); + int x = v1->x() + ((fromY << 8) + 0xff - v1->y()) * (v2->x() - v1->x()) / (v2->y() - v1->y()); + for (int y = fromY; y < toY; ++y) { + quint32 c = quint32(x >> 8); + if (c < quint32(width)) + scans[y].append(quint8(c)); + x += dx; + } + } + for (int i = 0; i < height; ++i) { + quint8 *scanline = scans[i].data(); + int size = scans[i].size(); + for (int j = 1; j < size; ++j) { + int k = j; + quint8 value = scanline[k]; + for (; k != 0 && value < scanline[k - 1]; --k) + scanline[k] = scanline[k - 1]; + scanline[k] = value; + } + qint32 *line = bits + i * width; + int j = 0; + for (; j + 1 < size; j += 2) { + for (quint8 x = scanline[j]; x < scanline[j + 1]; ++x) + line[x] = value; + } + if (j < size) { + for (int x = scanline[j]; x < width; ++x) + line[x] = value; } } } -static QImage makeDistanceField(int imgSize, const QPainterPath &path, int dfScale, float offs) +static QImage makeDistanceField(int imgSize, const QPainterPath &path, int dfScale, int offs) { - QImage image(imgSize, imgSize, QImage::Format_ARGB32_Premultiplied); + QImage image(imgSize, imgSize, QImage::Format_Indexed8); if (path.isEmpty()) { image.fill(0); return image; } - QPolylineSet polys = qPolyline(path); + QTransform transform; + transform.translate(offs, offs); + transform.scale(qreal(1) / dfScale, qreal(1) / dfScale); + + QDataBuffer<quint32> pathIndices(0); + QDataBuffer<QPoint> pathVertices(0); + qSimplifyPath(path, pathVertices, pathIndices, transform); + + const qint32 interiorColor = -0x7f80; // 8:8 signed format, -127.5 + const qint32 exteriorColor = 0x7f80; // 8:8 signed format, 127.5 + + QScopedArrayPointer<qint32> bits(new qint32[imgSize * imgSize]); + for (int i = 0; i < imgSize * imgSize; ++i) + bits[i] = exteriorColor; + + const qreal angleStep = qreal(15 * 3.141592653589793238 / 180); + const QPoint rotation(qRound(cos(angleStep) * 0x4000), + qRound(sin(angleStep) * 0x4000)); // 2:14 signed + + const quint32 *indices = pathIndices.data(); + QVarLengthArray<QPoint> normals; + QVarLengthArray<QPoint> vertices; + QVarLengthArray<bool> isConvex; + QVarLengthArray<bool> needsClipping; + + drawPolygons(bits.data(), imgSize, imgSize, pathVertices.data(), indices, pathIndices.size(), + interiorColor); - union Pacific { - float value; - QRgb color; - }; - Pacific interior; - Pacific exterior; - interior.value = 127; - exterior.value = -127; - - image.fill(exterior.color); - - QPainter p(&image); - p.setCompositionMode(QPainter::CompositionMode_Source); - p.translate(offs, offs); - p.scale(1 / qreal(dfScale), 1 / qreal(dfScale)); - p.fillPath(path, QColor::fromRgba(interior.color)); - p.end(); - - float *bits = (float *)image.bits(); - const float angleStep = 15 * 3.141592653589793238f / 180; - const DFPoint rotation = { cos(angleStep), sin(angleStep) }; - - bool isShortData = polys.indices.type() == QVertexIndexVector::UnsignedShort; - const void *indices = polys.indices.data(); int index = 0; - QVarLengthArray<DFPoint> normals(polys.vertices.count()); - QVarLengthArray<DFVertex> vertices(polys.vertices.count()); - while (index < polys.indices.size()) { + while (index < pathIndices.size()) { normals.clear(); vertices.clear(); + needsClipping.clear(); // Find end of polygon. int end = index; - if (isShortData) { - while (((quint16 *)indices)[end] != quint16(-1)) - ++end; - } else { - while (((quint32 *)indices)[end] != quint32(-1)) - ++end; - } + while (indices[end] != quint32(-1)) + ++end; // Calculate vertex normals. for (int next = index, prev = end - 1; next < end; prev = next++) { - quint32 fromVertexIndex = isShortData ? (quint32)((quint16 *)indices)[prev] : ((quint32 *)indices)[prev]; - quint32 toVertexIndex = isShortData ? (quint32)((quint16 *)indices)[next] : ((quint32 *)indices)[next]; - const qreal *from = &polys.vertices.at(fromVertexIndex * 2); - const qreal *to = &polys.vertices.at(toVertexIndex * 2); - DFPoint n; - n.x = float(to[1] - from[1]); - n.y = float(from[0] - to[0]); - if (n.x == 0 && n.y == 0) + quint32 fromVertexIndex = indices[prev]; + quint32 toVertexIndex = indices[next]; + + const QPoint &from = pathVertices.at(fromVertexIndex); + const QPoint &to = pathVertices.at(toVertexIndex); + + QPoint n(to.y() - from.y(), from.x() - to.x()); + if (n.x() == 0 && n.y() == 0) continue; - float scale = offs / sqrt(n.x * n.x + n.y * n.y); - n.x *= scale; - n.y *= scale; + int scale = qRound((offs << 16) / sqrt(qreal(n.x() * n.x() + n.y() * n.y()))); // 8:16 + n.rx() = n.x() * scale >> 8; + n.ry() = n.y() * scale >> 8; normals.append(n); - - DFVertex v; - v.p.x = float(to[0] / dfScale) + offs - 0.5f; - v.p.y = float(to[1] / dfScale) + offs - 0.5f; - v.d = 0.0f; + QPoint v(to.x() + 0x7f, to.y() + 0x7f); vertices.append(v); + needsClipping.append((to.x() < offs << 8) || (to.x() >= (imgSize - offs) << 8) + || (to.y() < offs << 8) || (to.y() >= (imgSize - offs) << 8)); } - QVarLengthArray<bool> isConvex(normals.count()); - for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) - isConvex[prev] = (normals.at(prev).x * normals.at(next).y - normals.at(prev).y * normals.at(next).x > 0); + isConvex.resize(normals.count()); + for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) { + isConvex[prev] = normals.at(prev).x() * normals.at(next).y() + - normals.at(prev).y() * normals.at(next).x() < 0; + } // Draw quads. for (int next = 0, prev = normals.count() - 1; next < normals.count(); prev = next++) { - DFPoint n = normals.at(next); - DFVertex intPrev = vertices.at(prev); - DFVertex extPrev = vertices.at(prev); - DFVertex intNext = vertices.at(next); - DFVertex extNext = vertices.at(next); - - extPrev.p.x += n.x; - extPrev.p.y += n.y; - intPrev.p.x -= n.x; - intPrev.p.y -= n.y; - extNext.p.x += n.x; - extNext.p.y += n.y; - intNext.p.x -= n.x; - intNext.p.y -= n.y; - extPrev.d = 127; - extNext.d = 127; - intPrev.d = -127; - intNext.d = -127; - - drawRectangle(bits, image.width(), image.height(), - &vertices.at(prev), &extPrev, &extNext, &vertices.at(next)); - - drawRectangle(bits, image.width(), image.height(), - &intPrev, &vertices.at(prev), &vertices.at(next), &intNext); + QPoint n = normals.at(next); + QPoint intPrev = vertices.at(prev); + QPoint extPrev = vertices.at(prev); + QPoint intNext = vertices.at(next); + QPoint extNext = vertices.at(next); + + extPrev.rx() -= n.x(); + extPrev.ry() -= n.y(); + intPrev.rx() += n.x(); + intPrev.ry() += n.y(); + extNext.rx() -= n.x(); + extNext.ry() -= n.y(); + intNext.rx() += n.x(); + intNext.ry() += n.y(); + + if (needsClipping[prev] || needsClipping[next]) { + drawRectangle<Clip>(bits.data(), imgSize, imgSize, + &intPrev, &vertices.at(prev), &extPrev, + &intNext, &vertices.at(next), &extNext, + exteriorColor); + } else { + drawRectangle<NoClip>(bits.data(), imgSize, imgSize, + &intPrev, &vertices.at(prev), &extPrev, + &intNext, &vertices.at(next), &extNext, + exteriorColor); + } if (isConvex.at(prev)) { - DFVertex v = extPrev; - for (;;) { - DFPoint rn = { n.x * rotation.x + n.y * rotation.y, - n.y * rotation.x - n.x * rotation.y }; - n = rn; - if (n.x * normals.at(prev).y - n.y * normals.at(prev).x >= -0.001) { - v.p.x = vertices.at(prev).p.x + normals.at(prev).x; - v.p.y = vertices.at(prev).p.y + normals.at(prev).y; - drawTriangle(bits, image.width(), image.height(), &vertices.at(prev), &v, &extPrev); - break; + QPoint p = extPrev; + if (needsClipping[prev]) { + for (;;) { + QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14, + (n.y() * rotation.x() + n.x() * rotation.y()) >> 14); + n = rn; + if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) { + p.rx() = vertices.at(prev).x() - normals.at(prev).x(); + p.ry() = vertices.at(prev).y() - normals.at(prev).y(); + drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &extPrev, &p, exteriorColor); + break; + } + + p.rx() = vertices.at(prev).x() - n.x(); + p.ry() = vertices.at(prev).y() - n.y(); + drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &extPrev, &p, exteriorColor); + extPrev = p; + } + } else { + for (;;) { + QPoint rn((n.x() * rotation.x() - n.y() * rotation.y()) >> 14, + (n.y() * rotation.x() + n.x() * rotation.y()) >> 14); + n = rn; + if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() <= 0) { + p.rx() = vertices.at(prev).x() - normals.at(prev).x(); + p.ry() = vertices.at(prev).y() - normals.at(prev).y(); + drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &extPrev, &p, exteriorColor); + break; + } + + p.rx() = vertices.at(prev).x() - n.x(); + p.ry() = vertices.at(prev).y() - n.y(); + drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &extPrev, &p, exteriorColor); + extPrev = p; } - - v.p.x = vertices.at(prev).p.x + n.x; - v.p.y = vertices.at(prev).p.y + n.y; - drawTriangle(bits, image.width(), image.height(), &vertices.at(prev), &v, &extPrev); - extPrev = v; } } else { - DFVertex v = intPrev; - for (;;) { - DFPoint rn = { n.x * rotation.x - n.y * rotation.y, - n.y * rotation.x + n.x * rotation.y }; - n = rn; - if (n.x * normals.at(prev).y - n.y * normals.at(prev).x <= 0.001) { - v.p.x = vertices.at(prev).p.x - normals.at(prev).x; - v.p.y = vertices.at(prev).p.y - normals.at(prev).y; - drawTriangle(bits, image.width(), image.height(), &vertices.at(prev), &intPrev, &v); - break; + QPoint p = intPrev; + if (needsClipping[prev]) { + for (;;) { + QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14, + (n.y() * rotation.x() - n.x() * rotation.y()) >> 14); + n = rn; + if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) { + p.rx() = vertices.at(prev).x() + normals.at(prev).x(); + p.ry() = vertices.at(prev).y() + normals.at(prev).y(); + drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &p, &intPrev, interiorColor); + break; + } + + p.rx() = vertices.at(prev).x() + n.x(); + p.ry() = vertices.at(prev).y() + n.y(); + drawTriangle<Clip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &p, &intPrev, interiorColor); + intPrev = p; + } + } else { + for (;;) { + QPoint rn((n.x() * rotation.x() + n.y() * rotation.y()) >> 14, + (n.y() * rotation.x() - n.x() * rotation.y()) >> 14); + n = rn; + if (n.x() * normals.at(prev).y() - n.y() * normals.at(prev).x() >= 0) { + p.rx() = vertices.at(prev).x() + normals.at(prev).x(); + p.ry() = vertices.at(prev).y() + normals.at(prev).y(); + drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &p, &intPrev, interiorColor); + break; + } + + p.rx() = vertices.at(prev).x() + n.x(); + p.ry() = vertices.at(prev).y() + n.y(); + drawTriangle<NoClip>(bits.data(), imgSize, imgSize, &vertices.at(prev), + &p, &intPrev, interiorColor); + intPrev = p; } - - v.p.x = vertices.at(prev).p.x - n.x; - v.p.y = vertices.at(prev).p.y - n.y; - drawTriangle(bits, image.width(), image.height(), &vertices.at(prev), &intPrev, &v); - intPrev = v; } } } + index = end + 1; } - for (int y = 0; y < image.height(); ++y) { - QRgb *iLine = (QRgb *)image.scanLine(y); - float *fLine = (float *)iLine; - for (int x = 0; x < image.width(); ++x) - iLine[x] = QRgb(fLine[x] + 127.5) << 24; + const qint32 *inLine = bits.data(); + uchar *outLine = image.bits(); + int padding = image.bytesPerLine() - image.width(); + for (int y = 0; y < imgSize; ++y) { + for (int x = 0; x < imgSize; ++x, ++inLine, ++outLine) + *outLine = uchar((0x7f80 - *inLine) >> 8); + outLine += padding; } return image; } -static void convert_to_Format_Alpha(QImage *image) -{ - const int width = image->width(); - const int height = image->height(); - uchar *data = image->bits(); - const uint *src = (const uint *) data; - int stride = image->bytesPerLine() / sizeof(uint); - - for (int i = 0; i < height; ++i) { - uchar *o = data + i * width; - for (int x = 0; x < width; ++x) - o[x] = (uchar)qAlpha(src[x]); - src += stride; - } -} - static bool fontHasNarrowOutlines(const QRawFont &f) { QRawFont font = f; @@ -665,7 +914,7 @@ QImage QSGDistanceFieldGlyphCache::renderDistanceFieldGlyph(glyph_t glyph) const QImage im = makeDistanceField(QT_DISTANCEFIELD_TILESIZE, path, QT_DISTANCEFIELD_SCALE, - QT_DISTANCEFIELD_RADIUS / qreal(QT_DISTANCEFIELD_SCALE)); + QT_DISTANCEFIELD_RADIUS / QT_DISTANCEFIELD_SCALE); return im; } @@ -754,7 +1003,7 @@ void QSGDistanceFieldGlyphCache::derefGlyphs(int count, const glyph_t *glyphs) void QSGDistanceFieldGlyphCache::createTexture(int width, int height) { if (ctx->d_ptr->workaround_brokenFBOReadBack && m_textureData->image.isNull()) - m_textureData->image = QImage(width, height, QImage::Format_ARGB32_Premultiplied); + m_textureData->image = QImage(width, height, QImage::Format_Indexed8); while (glGetError() != GL_NO_ERROR) { } @@ -797,7 +1046,6 @@ void QSGDistanceFieldGlyphCache::resizeTexture(int width, int height) if (ctx->d_ptr->workaround_brokenFBOReadBack) { m_textureData->image = m_textureData->image.copy(0, 0, width, height); QImage copy = m_textureData->image.copy(0, 0, oldWidth, oldHeight); - convert_to_Format_Alpha(©); glTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, oldWidth, oldHeight, GL_ALPHA, GL_UNSIGNED_BYTE, copy.constBits()); glDeleteTextures(1, &oldTexture); return; @@ -952,13 +1200,15 @@ void QSGDistanceFieldGlyphCache::updateCache() QImage glyph = renderDistanceFieldGlyph(glyphIndex); if (ctx->d_ptr->workaround_brokenFBOReadBack) { - QPainter p(&m_textureData->image); - p.setCompositionMode(QPainter::CompositionMode_Source); - p.drawImage(c.x, c.y, glyph); - p.end(); + uchar *inBits = glyph.scanLine(0); + uchar *outBits = m_textureData->image.scanLine(int(c.y)) + int(c.x); + for (int y = 0; y < glyph.height(); ++y) { + qMemCopy(outBits, inBits, glyph.width()); + inBits += glyph.bytesPerLine(); + outBits += m_textureData->image.bytesPerLine(); + } } - convert_to_Format_Alpha(&glyph); glTexSubImage2D(GL_TEXTURE_2D, 0, c.x, c.y, glyph.width(), glyph.height(), GL_ALPHA, GL_UNSIGNED_BYTE, glyph.constBits()); if (cacheDistanceFields) { diff --git a/src/declarative/scenegraph/qsgpathsimplifier.cpp b/src/declarative/scenegraph/qsgpathsimplifier.cpp new file mode 100644 index 0000000000..5fac564e21 --- /dev/null +++ b/src/declarative/scenegraph/qsgpathsimplifier.cpp @@ -0,0 +1,1673 @@ +/**************************************************************************** +** +** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtDeclarative module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** This file may be used under the terms of the GNU Lesser General Public +** License version 2.1 as published by the Free Software Foundation and +** appearing in the file LICENSE.LGPL included in the packaging of this +** file. Please review the following information to ensure the GNU Lesser +** General Public License version 2.1 requirements will be met: +** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU General +** Public License version 3.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 the GNU General +** Public License version 3.0 requirements will be met: +** http://www.gnu.org/copyleft/gpl.html. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qsgpathsimplifier_p.h" + +#include <QtCore/qvarlengtharray.h> +#include <QtCore/qglobal.h> +#include <QtCore/qpoint.h> +#include <QtCore/qalgorithms.h> + +#include <math.h> + +#include <private/qgl_p.h> +#include <private/qrbtree_p.h> + +QT_BEGIN_NAMESPACE + +#define Q_FIXED_POINT_SCALE 256 +#define Q_TRIANGULATE_END_OF_POLYGON quint32(-1) + + +namespace { + +//============================================================================// +// QPoint // +//============================================================================// + +inline bool operator < (const QPoint &a, const QPoint &b) +{ + return a.y() < b.y() || (a.y() == b.y() && a.x() < b.x()); +} + +inline bool operator > (const QPoint &a, const QPoint &b) +{ + return b < a; +} + +inline bool operator <= (const QPoint &a, const QPoint &b) +{ + return !(a > b); +} + +inline bool operator >= (const QPoint &a, const QPoint &b) +{ + return !(a < b); +} + +inline int cross(const QPoint &u, const QPoint &v) +{ + return u.x() * v.y() - u.y() * v.x(); +} + +inline int dot(const QPoint &u, const QPoint &v) +{ + return u.x() * v.x() + u.y() * v.y(); +} + +//============================================================================// +// Fraction // +//============================================================================// + +// Fraction must be in the range [0, 1) +struct Fraction +{ + bool isValid() const { return denominator != 0; } + + // numerator and denominator must not have common denominators. + unsigned int numerator, denominator; +}; + +inline unsigned int gcd(unsigned int x, unsigned int y) +{ + while (y != 0) { + unsigned int z = y; + y = x % y; + x = z; + } + return x; +} + +// Fraction must be in the range [0, 1) +// Assume input is valid. +Fraction fraction(unsigned int n, unsigned int d) { + Fraction result; + if (n == 0) { + result.numerator = 0; + result.denominator = 1; + } else { + unsigned int g = gcd(n, d); + result.numerator = n / g; + result.denominator = d / g; + } + return result; +} + +//============================================================================// +// Rational // +//============================================================================// + +struct Rational +{ + bool isValid() const { return fraction.isValid(); } + int integer; + Fraction fraction; +}; + +//============================================================================// +// IntersectionPoint // +//============================================================================// + +struct IntersectionPoint +{ + bool isValid() const { return x.fraction.isValid() && y.fraction.isValid(); } + QPoint round() const; + bool isAccurate() const { return x.fraction.numerator == 0 && y.fraction.numerator == 0; } + + Rational x; // 8:8 signed, 32/32 + Rational y; // 8:8 signed, 32/32 +}; + +QPoint IntersectionPoint::round() const +{ + QPoint result(x.integer, y.integer); + if (2 * x.fraction.numerator >= x.fraction.denominator) + ++result.rx(); + if (2 * y.fraction.numerator >= y.fraction.denominator) + ++result.ry(); + return result; +} + +// Return positive value if 'p' is to the right of the line 'v1'->'v2', negative if left of the +// line and zero if exactly on the line. +// The returned value is the z-component of the qCross product between 'v2-v1' and 'p-v1', +// which is twice the signed area of the triangle 'p'->'v1'->'v2' (positive for CW order). +inline int pointDistanceFromLine(const QPoint &p, const QPoint &v1, const QPoint &v2) +{ + return cross(v2 - v1, p - v1); +} + +IntersectionPoint intersectionPoint(const QPoint &u1, const QPoint &u2, + const QPoint &v1, const QPoint &v2) +{ + IntersectionPoint result = {{0, {0, 0}}, {0, {0, 0}}}; + + QPoint u = u2 - u1; + QPoint v = v2 - v1; + int d1 = cross(u, v1 - u1); + int d2 = cross(u, v2 - u1); + int det = d2 - d1; + int d3 = cross(v, u1 - v1); + int d4 = d3 - det; //qCross(v, u2 - v1); + + // Check that the math is correct. + Q_ASSERT(d4 == cross(v, u2 - v1)); + + // The intersection point can be expressed as: + // v1 - v * d1/det + // v2 - v * d2/det + // u1 + u * d3/det + // u2 + u * d4/det + + // I'm only interested in lines that are crossing, so ignore parallel lines even if they overlap. + if (det == 0) + return result; + + if (det < 0) { + det = -det; + d1 = -d1; + d2 = -d2; + d3 = -d3; + d4 = -d4; + } + + // I'm only interested in lines intersecting at their interior, not at their end points. + // The lines intersect at their interior if and only if 'd1 < 0', 'd2 > 0', 'd3 < 0' and 'd4 > 0'. + if (d1 >= 0 || d2 <= 0 || d3 <= 0 || d4 >= 0) + return result; + + // Calculate the intersection point as follows: + // v1 - v * d1/det | v1 <= v2 (component-wise) + // v2 - v * d2/det | v2 < v1 (component-wise) + + // Assuming 16 bits per vector component. + if (v.x() >= 0) { + result.x.integer = v1.x() + int(qint64(-v.x()) * d1 / det); + result.x.fraction = fraction((unsigned int)(qint64(-v.x()) * d1 % det), (unsigned int)det); + } else { + result.x.integer = v2.x() + int(qint64(-v.x()) * d2 / det); + result.x.fraction = fraction((unsigned int)(qint64(-v.x()) * d2 % det), (unsigned int)det); + } + + if (v.y() >= 0) { + result.y.integer = v1.y() + int(qint64(-v.y()) * d1 / det); + result.y.fraction = fraction((unsigned int)(qint64(-v.y()) * d1 % det), (unsigned int)det); + } else { + result.y.integer = v2.y() + int(qint64(-v.y()) * d2 / det); + result.y.fraction = fraction((unsigned int)(qint64(-v.y()) * d2 % det), (unsigned int)det); + } + + Q_ASSERT(result.x.fraction.isValid()); + Q_ASSERT(result.y.fraction.isValid()); + return result; +} + +//============================================================================// +// PathSimplifier // +//============================================================================// + +class PathSimplifier +{ +public: + PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices, + QDataBuffer<quint32> &indices, const QTransform &matrix); + +private: + struct Element; + + class BoundingVolumeHierarchy + { + public: + struct Node + { + enum Type + { + Leaf, + Split + }; + Type type; + QPoint minimum; + QPoint maximum; + union { + Element *element; // type == Leaf + Node *left; // type == Split + }; + Node *right; + }; + + BoundingVolumeHierarchy(); + ~BoundingVolumeHierarchy(); + void allocate(int nodeCount); + void free(); + Node *newNode(); + + Node *root; + private: + void freeNode(Node *n); + + Node *nodeBlock; + int blockSize; + int firstFree; + }; + + struct Element + { + enum Degree + { + Line = 1, + Quadratic = 2, + Cubic = 3 + }; + + quint32 &upperIndex() { return indices[pointingUp ? degree : 0]; } + quint32 &lowerIndex() { return indices[pointingUp ? 0 : degree]; } + quint32 upperIndex() const { return indices[pointingUp ? degree : 0]; } + quint32 lowerIndex() const { return indices[pointingUp ? 0 : degree]; } + void flip(); + + QPoint middle; + quint32 indices[4]; // index to points + Element *next, *previous; // used in connectElements() + int winding; // used in connectElements() + union { + QRBTree<Element *>::Node *edgeNode; // used in connectElements() + BoundingVolumeHierarchy::Node *bvhNode; + }; + Degree degree : 8; + uint processed : 1; // initially false, true when the element has been checked for intersections. + uint pointingUp : 1; // used in connectElements() + uint originallyPointingUp : 1; // used in connectElements() + }; + + class ElementAllocator + { + public: + ElementAllocator(); + ~ElementAllocator(); + void allocate(int count); + Element *newElement(); + private: + struct ElementBlock + { + ElementBlock *next; + int blockSize; + int firstFree; + Element elements[1]; + } *blocks; + }; + + struct Event + { + enum Type { Upper, Lower }; + bool operator < (const Event &other) const; + + QPoint point; + Type type; + Element *element; + }; + + typedef QRBTree<Element *>::Node RBNode; + typedef BoundingVolumeHierarchy::Node BVHNode; + + void initElements(const QVectorPath &path, const QTransform &matrix); + void removeIntersections(); + void connectElements(); + void fillIndices(); + BVHNode *buildTree(Element **elements, int elementCount); + bool intersectNodes(QDataBuffer<Element *> &elements, BVHNode *elementNode, BVHNode *treeNode); + bool equalElements(const Element *e1, const Element *e2); + bool splitLineAt(QDataBuffer<Element *> &elements, BVHNode *node, quint32 pointIndex, bool processAgain); + void appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes, Element *element); + QPair<int, int> calculateSeparatingAxisRange(const QPoint &axis, Element *element); + void splitCurve(QDataBuffer<Element *> &elements, BVHNode *node); + bool setElementToQuadratic(Element *element, quint32 pointIndex1, const QPoint &ctrl, quint32 pointIndex2); + bool setElementToCubic(Element *element, quint32 pointIndex1, const QPoint &ctrl1, const QPoint &ctrl2, quint32 pointIndex2); + void setElementToCubicAndSimplify(Element *element, quint32 pointIndex1, const QPoint &ctrl1, const QPoint &ctrl2, quint32 pointIndex2); + RBNode *findElementLeftOf(const Element *element, const QPair<RBNode *, RBNode *> &bounds); + bool elementIsLeftOf(const Element *left, const Element *right); + QPair<RBNode *, RBNode *> outerBounds(const QPoint &point); + static bool flattenQuadratic(const QPoint &u, const QPoint &v, const QPoint &w); + static bool flattenCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q); + static bool splitQuadratic(const QPoint &u, const QPoint &v, const QPoint &w, QPoint *result); + static bool splitCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q, QPoint *result); + void subDivQuadratic(const QPoint &u, const QPoint &v, const QPoint &w); + void subDivCubic(const QPoint &u, const QPoint &v, const QPoint &w, const QPoint &q); + static void sortEvents(Event *events, int count); + + ElementAllocator m_elementAllocator; + QDataBuffer<Element *> m_elements; + QDataBuffer<QPoint> *m_points; + BoundingVolumeHierarchy m_bvh; + QDataBuffer<quint32> *m_indices; + QRBTree<Element *> m_elementList; + uint m_hints; +}; + +inline PathSimplifier::BoundingVolumeHierarchy::BoundingVolumeHierarchy() + : root(0) + , nodeBlock(0) + , blockSize(0) + , firstFree(0) +{ +} + +inline PathSimplifier::BoundingVolumeHierarchy::~BoundingVolumeHierarchy() +{ + free(); +} + +inline void PathSimplifier::BoundingVolumeHierarchy::allocate(int nodeCount) +{ + Q_ASSERT(nodeBlock == 0); + Q_ASSERT(firstFree == 0); + nodeBlock = new Node[blockSize = nodeCount]; +} + +inline void PathSimplifier::BoundingVolumeHierarchy::free() +{ + freeNode(root); + delete[] nodeBlock; + nodeBlock = 0; + firstFree = blockSize = 0; + root = 0; +} + +inline PathSimplifier::BVHNode *PathSimplifier::BoundingVolumeHierarchy::newNode() +{ + if (firstFree < blockSize) + return &nodeBlock[firstFree++]; + return new Node; +} + +inline void PathSimplifier::BoundingVolumeHierarchy::freeNode(Node *n) +{ + if (!n) + return; + Q_ASSERT(n->type == Node::Split || n->type == Node::Leaf); + if (n->type == Node::Split) { + freeNode(n->left); + freeNode(n->right); + } + if (!(n >= nodeBlock && n < nodeBlock + blockSize)) + delete n; +} + +inline PathSimplifier::ElementAllocator::ElementAllocator() + : blocks(0) +{ +} + +inline PathSimplifier::ElementAllocator::~ElementAllocator() +{ + while (blocks) { + ElementBlock *block = blocks; + blocks = blocks->next; + qFree(block); + } +} + +inline void PathSimplifier::ElementAllocator::allocate(int count) +{ + Q_ASSERT(blocks == 0); + Q_ASSERT(count > 0); + blocks = (ElementBlock *)qMalloc(sizeof(ElementBlock) + (count - 1) * sizeof(Element)); + blocks->blockSize = count; + blocks->next = 0; + blocks->firstFree = 0; +} + +inline PathSimplifier::Element *PathSimplifier::ElementAllocator::newElement() +{ + Q_ASSERT(blocks); + if (blocks->firstFree < blocks->blockSize) + return &blocks->elements[blocks->firstFree++]; + ElementBlock *oldBlock = blocks; + blocks = (ElementBlock *)qMalloc(sizeof(ElementBlock) + (oldBlock->blockSize - 1) * sizeof(Element)); + blocks->blockSize = oldBlock->blockSize; + blocks->next = oldBlock; + blocks->firstFree = 0; + return &blocks->elements[blocks->firstFree++]; +} + + +inline bool PathSimplifier::Event::operator < (const Event &other) const +{ + if (point == other.point) + return type < other.type; + return other.point < point; +} + +inline void PathSimplifier::Element::flip() +{ + for (int i = 0; i < (degree + 1) >> 1; ++i) { + Q_ASSERT(degree >= Line && degree <= Cubic); + Q_ASSERT(i >= 0 && i < degree); + qSwap(indices[i], indices[degree - i]); + } + pointingUp = !pointingUp; + Q_ASSERT(next == 0 && previous == 0); +} + +PathSimplifier::PathSimplifier(const QVectorPath &path, QDataBuffer<QPoint> &vertices, + QDataBuffer<quint32> &indices, const QTransform &matrix) + : m_elements(0) + , m_points(&vertices) + , m_indices(&indices) +{ + m_points->reset(); + m_indices->reset(); + initElements(path, matrix); + if (!m_elements.isEmpty()) { + removeIntersections(); + connectElements(); + fillIndices(); + } +} + +void PathSimplifier::initElements(const QVectorPath &path, const QTransform &matrix) +{ + m_hints = path.hints(); + int pathElementCount = path.elementCount(); + if (pathElementCount == 0) + return; + m_elements.reserve(2 * pathElementCount); + m_elementAllocator.allocate(2 * pathElementCount); + m_points->reserve(2 * pathElementCount); + const QPainterPath::ElementType *e = path.elements(); + const qreal *p = path.points(); + if (e) { + qreal x, y; + quint32 moveToIndex = 0; + quint32 previousIndex = 0; + for (int i = 0; i < pathElementCount; ++i, ++e, p += 2) { + switch (*e) { + case QPainterPath::MoveToElement: + { + if (!m_points->isEmpty()) { + const QPoint &from = m_points->at(previousIndex); + const QPoint &to = m_points->at(moveToIndex); + if (from != to) { + Element *element = m_elementAllocator.newElement(); + element->degree = Element::Line; + element->indices[0] = previousIndex; + element->indices[1] = moveToIndex; + element->middle.rx() = (from.x() + to.x()) >> 1; + element->middle.ry() = (from.y() + to.y()) >> 1; + m_elements.add(element); + } + } + previousIndex = moveToIndex = m_points->size(); + matrix.map(p[0], p[1], &x, &y); + QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE)); + m_points->add(to); + } + break; + case QPainterPath::LineToElement: + Q_ASSERT(!m_points->isEmpty()); + { + matrix.map(p[0], p[1], &x, &y); + QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE)); + const QPoint &from = m_points->last(); + if (to != from) { + Element *element = m_elementAllocator.newElement(); + element->degree = Element::Line; + element->indices[0] = previousIndex; + element->indices[1] = quint32(m_points->size()); + element->middle.rx() = (from.x() + to.x()) >> 1; + element->middle.ry() = (from.y() + to.y()) >> 1; + m_elements.add(element); + previousIndex = m_points->size(); + m_points->add(to); + } + } + break; + case QPainterPath::CurveToElement: + Q_ASSERT(i + 2 < pathElementCount); + Q_ASSERT(!m_points->isEmpty()); + Q_ASSERT(e[1] == QPainterPath::CurveToDataElement); + Q_ASSERT(e[2] == QPainterPath::CurveToDataElement); + { + quint32 startPointIndex = previousIndex; + matrix.map(p[4], p[5], &x, &y); + QPoint end(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE)); + previousIndex = m_points->size(); + m_points->add(end); + + // See if this cubic bezier is really quadratic. + qreal x1 = p[-2] + qreal(1.5) * (p[0] - p[-2]); + qreal y1 = p[-1] + qreal(1.5) * (p[1] - p[-1]); + qreal x2 = p[4] + qreal(1.5) * (p[2] - p[4]); + qreal y2 = p[5] + qreal(1.5) * (p[3] - p[5]); + + Element *element = m_elementAllocator.newElement(); + if (qAbs(x1 - x2) < qreal(1e-3) && qAbs(y1 - y2) < qreal(1e-3)) { + // The bezier curve is quadratic. + matrix.map(x1, y1, &x, &y); + QPoint ctrl(qRound(x * Q_FIXED_POINT_SCALE), + qRound(y * Q_FIXED_POINT_SCALE)); + setElementToQuadratic(element, startPointIndex, ctrl, previousIndex); + } else { + // The bezier curve is cubic. + matrix.map(p[0], p[1], &x, &y); + QPoint ctrl1(qRound(x * Q_FIXED_POINT_SCALE), + qRound(y * Q_FIXED_POINT_SCALE)); + matrix.map(p[2], p[3], &x, &y); + QPoint ctrl2(qRound(x * Q_FIXED_POINT_SCALE), + qRound(y * Q_FIXED_POINT_SCALE)); + setElementToCubicAndSimplify(element, startPointIndex, ctrl1, ctrl2, + previousIndex); + } + m_elements.add(element); + } + i += 2; + e += 2; + p += 4; + + break; + default: + Q_ASSERT_X(0, "QSGPathSimplifier::initialize", "Unexpected element type."); + break; + } + } + if (!m_points->isEmpty()) { + const QPoint &from = m_points->at(previousIndex); + const QPoint &to = m_points->at(moveToIndex); + if (from != to) { + Element *element = m_elementAllocator.newElement(); + element->degree = Element::Line; + element->indices[0] = previousIndex; + element->indices[1] = moveToIndex; + element->middle.rx() = (from.x() + to.x()) >> 1; + element->middle.ry() = (from.y() + to.y()) >> 1; + m_elements.add(element); + } + } + } else { + qreal x, y; + + for (int i = 0; i < pathElementCount; ++i, p += 2) { + matrix.map(p[0], p[1], &x, &y); + QPoint to(qRound(x * Q_FIXED_POINT_SCALE), qRound(y * Q_FIXED_POINT_SCALE)); + if (to != m_points->last()) + m_points->add(to); + } + + while (!m_points->isEmpty() && m_points->last() == m_points->first()) + m_points->pop_back(); + + if (m_points->isEmpty()) + return; + + quint32 prev = quint32(m_points->size() - 1); + for (int i = 0; i < m_points->size(); ++i) { + QPoint &to = m_points->at(i); + QPoint &from = m_points->at(prev); + Element *element = m_elementAllocator.newElement(); + element->degree = Element::Line; + element->indices[0] = prev; + element->indices[1] = quint32(i); + element->middle.rx() = (from.x() + to.x()) >> 1; + element->middle.ry() = (from.y() + to.y()) >> 1; + m_elements.add(element); + prev = i; + } + } + + for (int i = 0; i < m_elements.size(); ++i) + m_elements.at(i)->processed = false; +} + +void PathSimplifier::removeIntersections() +{ + Q_ASSERT(!m_elements.isEmpty()); + QDataBuffer<Element *> elements(m_elements.size()); + for (int i = 0; i < m_elements.size(); ++i) + elements.add(m_elements.at(i)); + m_bvh.allocate(2 * m_elements.size()); + m_bvh.root = buildTree(elements.data(), elements.size()); + + elements.reset(); + for (int i = 0; i < m_elements.size(); ++i) + elements.add(m_elements.at(i)); + + while (!elements.isEmpty()) { + Element *element = elements.last(); + elements.pop_back(); + BVHNode *node = element->bvhNode; + Q_ASSERT(node->type == BVHNode::Leaf); + Q_ASSERT(node->element == element); + if (!element->processed) { + if (!intersectNodes(elements, node, m_bvh.root)) + element->processed = true; + } + } + + m_bvh.free(); // The bounding volume hierarchy is not needed anymore. +} + +void PathSimplifier::connectElements() +{ + Q_ASSERT(!m_elements.isEmpty()); + QDataBuffer<Event> events(m_elements.size() * 2); + for (int i = 0; i < m_elements.size(); ++i) { + Element *element = m_elements.at(i); + element->next = element->previous = 0; + element->winding = 0; + element->edgeNode = 0; + const QPoint &u = m_points->at(element->indices[0]); + const QPoint &v = m_points->at(element->indices[element->degree]); + if (u != v) { + element->pointingUp = element->originallyPointingUp = v < u; + + Event event; + event.element = element; + event.point = u; + event.type = element->pointingUp ? Event::Lower : Event::Upper; + events.add(event); + event.point = v; + event.type = element->pointingUp ? Event::Upper : Event::Lower; + events.add(event); + } + } + QVarLengthArray<Element *, 8> orderedElements; + if (!events.isEmpty()) + sortEvents(events.data(), events.size()); + while (!events.isEmpty()) { + const Event *event = &events.last(); + QPoint eventPoint = event->point; + + // Find all elements passing through the event point. + QPair<RBNode *, RBNode *> bounds = outerBounds(eventPoint); + + // Special case: single element above and single element below event point. + int eventCount = events.size(); + if (event->type == Event::Lower && eventCount > 2) { + QPair<RBNode *, RBNode *> range; + range.first = bounds.first ? m_elementList.next(bounds.first) + : m_elementList.front(m_elementList.root); + range.second = bounds.second ? m_elementList.previous(bounds.second) + : m_elementList.back(m_elementList.root); + + const Event *event2 = &events.at(eventCount - 2); + const Event *event3 = &events.at(eventCount - 3); + Q_ASSERT(event2->point == eventPoint); // There are always at least two events at a point. + if (range.first == range.second && event2->type == Event::Upper && event3->point != eventPoint) { + Element *element = event->element; + Element *element2 = event2->element; + element->edgeNode->data = event2->element; + element2->edgeNode = element->edgeNode; + element->edgeNode = 0; + + events.pop_back(); + events.pop_back(); + + if (element2->pointingUp != element->pointingUp) + element2->flip(); + element2->winding = element->winding; + int winding = element->winding; + if (element->originallyPointingUp) + ++winding; + if (winding == 0 || winding == 1) { + if (element->pointingUp) { + element->previous = event2->element; + element2->next = event->element; + } else { + element->next = event2->element; + element2->previous = event->element; + } + } + continue; + } + } + orderedElements.clear(); + + // First, find the ones above the event point. + if (m_elementList.root) { + RBNode *current = bounds.first ? m_elementList.next(bounds.first) + : m_elementList.front(m_elementList.root); + while (current != bounds.second) { + Element *element = current->data; + Q_ASSERT(element->edgeNode == current); + int winding = element->winding; + if (element->originallyPointingUp) + ++winding; + const QPoint &lower = m_points->at(element->lowerIndex()); + if (lower == eventPoint) { + if (winding == 0 || winding == 1) + orderedElements.append(current->data); + } else { + // The element is passing through 'event.point'. + Q_ASSERT(m_points->at(element->upperIndex()) != eventPoint); + Q_ASSERT(element->degree == Element::Line); + // Split the line. + Element *eventElement = event->element; + int indexIndex = (event->type == Event::Upper) == eventElement->pointingUp + ? eventElement->degree : 0; + quint32 pointIndex = eventElement->indices[indexIndex]; + Q_ASSERT(eventPoint == m_points->at(pointIndex)); + + Element *upperElement = m_elementAllocator.newElement(); + *upperElement = *element; + upperElement->lowerIndex() = element->upperIndex() = pointIndex; + upperElement->edgeNode = 0; + element->next = element->previous = 0; + if (upperElement->next) + upperElement->next->previous = upperElement; + else if (upperElement->previous) + upperElement->previous->next = upperElement; + if (element->pointingUp != element->originallyPointingUp) + element->flip(); + if (winding == 0 || winding == 1) + orderedElements.append(upperElement); + m_elements.add(upperElement); + } + current = m_elementList.next(current); + } + } + while (!events.isEmpty() && events.last().point == eventPoint) { + event = &events.last(); + if (event->type == Event::Upper) { + Q_ASSERT(event->point == m_points->at(event->element->upperIndex())); + RBNode *left = findElementLeftOf(event->element, bounds); + RBNode *node = m_elementList.newNode(); + node->data = event->element; + Q_ASSERT(event->element->edgeNode == 0); + event->element->edgeNode = node; + m_elementList.attachAfter(left, node); + } else { + Q_ASSERT(event->type == Event::Lower); + Q_ASSERT(event->point == m_points->at(event->element->lowerIndex())); + Element *element = event->element; + Q_ASSERT(element->edgeNode); + m_elementList.deleteNode(element->edgeNode); + Q_ASSERT(element->edgeNode == 0); + } + events.pop_back(); + } + + if (m_elementList.root) { + RBNode *current = bounds.first ? m_elementList.next(bounds.first) + : m_elementList.front(m_elementList.root); + int winding = bounds.first ? bounds.first->data->winding : 0; + + // Calculate winding numbers and flip elements if necessary. + while (current != bounds.second) { + Element *element = current->data; + Q_ASSERT(element->edgeNode == current); + int ccw = winding & 1; + Q_ASSERT(element->pointingUp == element->originallyPointingUp); + if (element->originallyPointingUp) { + --winding; + } else { + ++winding; + ccw ^= 1; + } + element->winding = winding; + if (ccw == 0) + element->flip(); + current = m_elementList.next(current); + } + + // Pick elements with correct winding number. + current = bounds.second ? m_elementList.previous(bounds.second) + : m_elementList.back(m_elementList.root); + while (current != bounds.first) { + Element *element = current->data; + Q_ASSERT(element->edgeNode == current); + Q_ASSERT(m_points->at(element->upperIndex()) == eventPoint); + int winding = element->winding; + if (element->originallyPointingUp) + ++winding; + if (winding == 0 || winding == 1) + orderedElements.append(current->data); + current = m_elementList.previous(current); + } + } + + if (!orderedElements.isEmpty()) { + Q_ASSERT((orderedElements.size() & 1) == 0); + int i = 0; + Element *firstElement = orderedElements.at(0); + if (m_points->at(firstElement->indices[0]) != eventPoint) { + orderedElements.append(firstElement); + i = 1; + } + for (; i < orderedElements.size(); i += 2) { + Q_ASSERT(i + 1 < orderedElements.size()); + Element *next = orderedElements.at(i); + Element *previous = orderedElements.at(i + 1); + Q_ASSERT(next->previous == 0); + Q_ASSERT(previous->next == 0); + next->previous = previous; + previous->next = next; + } + } + } +#ifndef QT_NO_DEBUG + for (int i = 0; i < m_elements.size(); ++i) { + const Element *element = m_elements.at(i); + Q_ASSERT(element->next == 0 || element->next->previous == element); + Q_ASSERT(element->previous == 0 || element->previous->next == element); + Q_ASSERT((element->next == 0) == (element->previous == 0)); + } +#endif +} + +void PathSimplifier::fillIndices() +{ + for (int i = 0; i < m_elements.size(); ++i) + m_elements.at(i)->processed = false; + for (int i = 0; i < m_elements.size(); ++i) { + Element *element = m_elements.at(i); + if (element->processed || element->next == 0) + continue; + do { + m_indices->add(element->indices[0]); + switch (element->degree) { + case Element::Quadratic: + { + QPoint pts[] = { + m_points->at(element->indices[0]), + m_points->at(element->indices[1]), + m_points->at(element->indices[2]) + }; + subDivQuadratic(pts[0], pts[1], pts[2]); + } + break; + case Element::Cubic: + { + QPoint pts[] = { + m_points->at(element->indices[0]), + m_points->at(element->indices[1]), + m_points->at(element->indices[2]), + m_points->at(element->indices[3]) + }; + subDivCubic(pts[0], pts[1], pts[2], pts[3]); + } + break; + default: + break; + } + Q_ASSERT(element->next); + element->processed = true; + element = element->next; + } while (element != m_elements.at(i)); + m_indices->add(Q_TRIANGULATE_END_OF_POLYGON); + } +} + +PathSimplifier::BVHNode *PathSimplifier::buildTree(Element **elements, int elementCount) +{ + Q_ASSERT(elementCount > 0); + BVHNode *node = m_bvh.newNode(); + if (elementCount == 1) { + Element *element = *elements; + element->bvhNode = node; + node->type = BVHNode::Leaf; + node->element = element; + node->minimum = node->maximum = m_points->at(element->indices[0]); + for (int i = 1; i <= element->degree; ++i) { + const QPoint &p = m_points->at(element->indices[i]); + node->minimum.rx() = qMin(node->minimum.x(), p.x()); + node->minimum.ry() = qMin(node->minimum.y(), p.y()); + node->maximum.rx() = qMax(node->maximum.x(), p.x()); + node->maximum.ry() = qMax(node->maximum.y(), p.y()); + } + return node; + } + + node->type = BVHNode::Split; + + QPoint minimum, maximum; + minimum = maximum = elements[0]->middle; + + for (int i = 1; i < elementCount; ++i) { + const QPoint &p = elements[i]->middle; + minimum.rx() = qMin(minimum.x(), p.x()); + minimum.ry() = qMin(minimum.y(), p.y()); + maximum.rx() = qMax(maximum.x(), p.x()); + maximum.ry() = qMax(maximum.y(), p.y()); + } + + int comp, pivot; + if (maximum.x() - minimum.x() > maximum.y() - minimum.y()) { + comp = 0; + pivot = (maximum.x() + minimum.x()) >> 1; + } else { + comp = 1; + pivot = (maximum.y() + minimum.y()) >> 1; + } + + int lo = 0; + int hi = elementCount - 1; + while (lo < hi) { + while (lo < hi && (&elements[lo]->middle.rx())[comp] <= pivot) + ++lo; + while (lo < hi && (&elements[hi]->middle.rx())[comp] > pivot) + --hi; + if (lo < hi) + qSwap(elements[lo], elements[hi]); + } + + if (lo == elementCount) { + // All points are the same. + Q_ASSERT(minimum.x() == maximum.x() && minimum.y() == maximum.y()); + lo = elementCount >> 1; + } + + node->left = buildTree(elements, lo); + node->right = buildTree(elements + lo, elementCount - lo); + + const BVHNode *left = node->left; + const BVHNode *right = node->right; + node->minimum.rx() = qMin(left->minimum.x(), right->minimum.x()); + node->minimum.ry() = qMin(left->minimum.y(), right->minimum.y()); + node->maximum.rx() = qMax(left->maximum.x(), right->maximum.x()); + node->maximum.ry() = qMax(left->maximum.y(), right->maximum.y()); + + return node; +} + +bool PathSimplifier::intersectNodes(QDataBuffer<Element *> &elements, BVHNode *elementNode, + BVHNode *treeNode) +{ + if (elementNode->minimum.x() >= treeNode->maximum.x() + || elementNode->minimum.y() >= treeNode->maximum.y() + || elementNode->maximum.x() <= treeNode->minimum.x() + || elementNode->maximum.y() <= treeNode->minimum.y()) + { + return false; + } + + Q_ASSERT(elementNode->type == BVHNode::Leaf); + Element *element = elementNode->element; + Q_ASSERT(!element->processed); + + if (treeNode->type == BVHNode::Leaf) { + Element *nodeElement = treeNode->element; + if (!nodeElement->processed) + return false; + + if (treeNode->element == elementNode->element) + return false; + + if (equalElements(treeNode->element, elementNode->element)) + return false; // element doesn't split itself. + + if (element->degree == Element::Line && nodeElement->degree == Element::Line) { + const QPoint &u1 = m_points->at(element->indices[0]); + const QPoint &u2 = m_points->at(element->indices[1]); + const QPoint &v1 = m_points->at(nodeElement->indices[0]); + const QPoint &v2 = m_points->at(nodeElement->indices[1]); + IntersectionPoint intersection = intersectionPoint(u1, u2, v1, v2); + if (!intersection.isValid()) + return false; + + Q_ASSERT(intersection.x.integer >= qMin(u1.x(), u2.x())); + Q_ASSERT(intersection.y.integer >= qMin(u1.y(), u2.y())); + Q_ASSERT(intersection.x.integer >= qMin(v1.x(), v2.x())); + Q_ASSERT(intersection.y.integer >= qMin(v1.y(), v2.y())); + + Q_ASSERT(intersection.x.integer <= qMax(u1.x(), u2.x())); + Q_ASSERT(intersection.y.integer <= qMax(u1.y(), u2.y())); + Q_ASSERT(intersection.x.integer <= qMax(v1.x(), v2.x())); + Q_ASSERT(intersection.y.integer <= qMax(v1.y(), v2.y())); + + m_points->add(intersection.round()); + splitLineAt(elements, treeNode, m_points->size() - 1, !intersection.isAccurate()); + return splitLineAt(elements, elementNode, m_points->size() - 1, false); + } else { + QVarLengthArray<QPoint, 12> axes; + appendSeparatingAxes(axes, elementNode->element); + appendSeparatingAxes(axes, treeNode->element); + for (int i = 0; i < axes.size(); ++i) { + QPair<int, int> range1 = calculateSeparatingAxisRange(axes.at(i), elementNode->element); + QPair<int, int> range2 = calculateSeparatingAxisRange(axes.at(i), treeNode->element); + if (range1.first >= range2.second || range1.second <= range2.first) { + return false; // Separating axis found. + } + } + // Bounding areas overlap. + if (nodeElement->degree > Element::Line) + splitCurve(elements, treeNode); + if (element->degree > Element::Line) { + splitCurve(elements, elementNode); + } else { + // The element was not split, so it can be processed further. + if (intersectNodes(elements, elementNode, treeNode->left)) + return true; + if (intersectNodes(elements, elementNode, treeNode->right)) + return true; + return false; + } + return true; + } + } else { + if (intersectNodes(elements, elementNode, treeNode->left)) + return true; + if (intersectNodes(elements, elementNode, treeNode->right)) + return true; + return false; + } +} + +bool PathSimplifier::equalElements(const Element *e1, const Element *e2) +{ + Q_ASSERT(e1 != e2); + if (e1->degree != e2->degree) + return false; + + // Possibly equal and in the same direction. + bool equalSame = true; + for (int i = 0; i <= e1->degree; ++i) + equalSame &= m_points->at(e1->indices[i]) == m_points->at(e2->indices[i]); + + // Possibly equal and in opposite directions. + bool equalOpposite = true; + for (int i = 0; i <= e1->degree; ++i) + equalOpposite &= m_points->at(e1->indices[e1->degree - i]) == m_points->at(e2->indices[i]); + + return equalSame || equalOpposite; +} + +bool PathSimplifier::splitLineAt(QDataBuffer<Element *> &elements, BVHNode *node, + quint32 pointIndex, bool processAgain) +{ + Q_ASSERT(node->type == BVHNode::Leaf); + Element *element = node->element; + Q_ASSERT(element->degree == Element::Line); + const QPoint &u = m_points->at(element->indices[0]); + const QPoint &v = m_points->at(element->indices[1]); + const QPoint &p = m_points->at(pointIndex); + if (u == p || v == p) + return false; // No split needed. + + if (processAgain) + element->processed = false; // Needs to be processed again. + + Element *first = node->element; + Element *second = m_elementAllocator.newElement(); + *second = *first; + first->indices[1] = second->indices[0] = pointIndex; + first->middle.rx() = (u.x() + p.x()) >> 1; + first->middle.ry() = (u.y() + p.y()) >> 1; + second->middle.rx() = (v.x() + p.x()) >> 1; + second->middle.ry() = (v.y() + p.y()) >> 1; + m_elements.add(second); + + BVHNode *left = m_bvh.newNode(); + BVHNode *right = m_bvh.newNode(); + left->type = right->type = BVHNode::Leaf; + left->element = first; + right->element = second; + left->minimum = right->minimum = node->minimum; + left->maximum = right->maximum = node->maximum; + if (u.x() < v.x()) + left->maximum.rx() = right->minimum.rx() = p.x(); + else + left->minimum.rx() = right->maximum.rx() = p.x(); + if (u.y() < v.y()) + left->maximum.ry() = right->minimum.ry() = p.y(); + else + left->minimum.ry() = right->maximum.ry() = p.y(); + left->element->bvhNode = left; + right->element->bvhNode = right; + + node->type = BVHNode::Split; + node->left = left; + node->right = right; + + if (!first->processed) { + elements.add(left->element); + elements.add(right->element); + } + return true; +} + +void PathSimplifier::appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes, Element *element) +{ + switch (element->degree) { + case Element::Cubic: + { + const QPoint &u = m_points->at(element->indices[0]); + const QPoint &v = m_points->at(element->indices[1]); + const QPoint &w = m_points->at(element->indices[2]); + const QPoint &q = m_points->at(element->indices[3]); + QPoint ns[] = { + QPoint(u.y() - v.y(), v.x() - u.x()), + QPoint(v.y() - w.y(), w.x() - v.x()), + QPoint(w.y() - q.y(), q.x() - w.x()), + QPoint(q.y() - u.y(), u.x() - q.x()), + QPoint(u.y() - w.y(), w.x() - u.x()), + QPoint(v.y() - q.y(), q.x() - v.x()) + }; + for (int i = 0; i < 6; ++i) { + if (ns[i].x() || ns[i].y()) + axes.append(ns[i]); + } + } + break; + case Element::Quadratic: + { + const QPoint &u = m_points->at(element->indices[0]); + const QPoint &v = m_points->at(element->indices[1]); + const QPoint &w = m_points->at(element->indices[2]); + QPoint ns[] = { + QPoint(u.y() - v.y(), v.x() - u.x()), + QPoint(v.y() - w.y(), w.x() - v.x()), + QPoint(w.y() - u.y(), u.x() - w.x()) + }; + for (int i = 0; i < 3; ++i) { + if (ns[i].x() || ns[i].y()) + axes.append(ns[i]); + } + } + break; + case Element::Line: + { + const QPoint &u = m_points->at(element->indices[0]); + const QPoint &v = m_points->at(element->indices[1]); + QPoint n(u.y() - v.y(), v.x() - u.x()); + if (n.x() || n.y()) + axes.append(n); + } + break; + default: + Q_ASSERT_X(0, "QSGPathSimplifier::appendSeparatingAxes", "Unexpected element type."); + break; + } +} + +QPair<int, int> PathSimplifier::calculateSeparatingAxisRange(const QPoint &axis, Element *element) +{ + QPair<int, int> range(0x7fffffff, -0x7fffffff); + for (int i = 0; i <= element->degree; ++i) { + const QPoint &p = m_points->at(element->indices[i]); + int dist = dot(axis, p); + range.first = qMin(range.first, dist); + range.second = qMax(range.second, dist); + } + return range; +} + +void PathSimplifier::splitCurve(QDataBuffer<Element *> &elements, BVHNode *node) +{ + Q_ASSERT(node->type == BVHNode::Leaf); + + Element *first = node->element; + Element *second = m_elementAllocator.newElement(); + *second = *first; + m_elements.add(second); + Q_ASSERT(first->degree > Element::Line); + + bool accurate = true; + const QPoint &u = m_points->at(first->indices[0]); + const QPoint &v = m_points->at(first->indices[1]); + const QPoint &w = m_points->at(first->indices[2]); + + if (first->degree == Element::Quadratic) { + QPoint pts[3]; + accurate = splitQuadratic(u, v, w, pts); + int pointIndex = m_points->size(); + m_points->add(pts[1]); + accurate &= setElementToQuadratic(first, first->indices[0], pts[0], pointIndex); + accurate &= setElementToQuadratic(second, pointIndex, pts[2], second->indices[2]); + } else { + Q_ASSERT(first->degree == Element::Cubic); + const QPoint &q = m_points->at(first->indices[3]); + QPoint pts[5]; + accurate = splitCubic(u, v, w, q, pts); + int pointIndex = m_points->size(); + m_points->add(pts[2]); + accurate &= setElementToCubic(first, first->indices[0], pts[0], pts[1], pointIndex); + accurate &= setElementToCubic(second, pointIndex, pts[3], pts[4], second->indices[3]); + } + + if (!accurate) + first->processed = second->processed = false; // Needs to be processed again. + + BVHNode *left = m_bvh.newNode(); + BVHNode *right = m_bvh.newNode(); + left->type = right->type = BVHNode::Leaf; + left->element = first; + right->element = second; + + left->minimum.rx() = left->minimum.ry() = right->minimum.rx() = right->minimum.ry() = INT_MAX; + left->maximum.rx() = left->maximum.ry() = right->maximum.rx() = right->maximum.ry() = INT_MIN; + + for (int i = 0; i <= first->degree; ++i) { + QPoint &p = m_points->at(first->indices[i]); + left->minimum.rx() = qMin(left->minimum.x(), p.x()); + left->minimum.ry() = qMin(left->minimum.y(), p.y()); + left->maximum.rx() = qMax(left->maximum.x(), p.x()); + left->maximum.ry() = qMax(left->maximum.y(), p.y()); + } + for (int i = 0; i <= second->degree; ++i) { + QPoint &p = m_points->at(second->indices[i]); + right->minimum.rx() = qMin(right->minimum.x(), p.x()); + right->minimum.ry() = qMin(right->minimum.y(), p.y()); + right->maximum.rx() = qMax(right->maximum.x(), p.x()); + right->maximum.ry() = qMax(right->maximum.y(), p.y()); + } + left->element->bvhNode = left; + right->element->bvhNode = right; + + node->type = BVHNode::Split; + node->left = left; + node->right = right; + + if (!first->processed) { + elements.add(left->element); + elements.add(right->element); + } +} + +bool PathSimplifier::setElementToQuadratic(Element *element, quint32 pointIndex1, + const QPoint &ctrl, quint32 pointIndex2) +{ + const QPoint &p1 = m_points->at(pointIndex1); + const QPoint &p2 = m_points->at(pointIndex2); + if (flattenQuadratic(p1, ctrl, p2)) { + // Insert line. + element->degree = Element::Line; + element->indices[0] = pointIndex1; + element->indices[1] = pointIndex2; + element->middle.rx() = (p1.x() + p2.x()) >> 1; + element->middle.ry() = (p1.y() + p2.y()) >> 1; + return false; + } else { + // Insert bezier. + element->degree = Element::Quadratic; + element->indices[0] = pointIndex1; + element->indices[1] = m_points->size(); + element->indices[2] = pointIndex2; + element->middle.rx() = (p1.x() + ctrl.x() + p2.x()) / 3; + element->middle.ry() = (p1.y() + ctrl.y() + p2.y()) / 3; + m_points->add(ctrl); + return true; + } +} + +bool PathSimplifier::setElementToCubic(Element *element, quint32 pointIndex1, const QPoint &v, + const QPoint &w, quint32 pointIndex2) +{ + const QPoint &u = m_points->at(pointIndex1); + const QPoint &q = m_points->at(pointIndex2); + if (flattenCubic(u, v, w, q)) { + // Insert line. + element->degree = Element::Line; + element->indices[0] = pointIndex1; + element->indices[1] = pointIndex2; + element->middle.rx() = (u.x() + q.x()) >> 1; + element->middle.ry() = (u.y() + q.y()) >> 1; + return false; + } else { + // Insert bezier. + element->degree = Element::Cubic; + element->indices[0] = pointIndex1; + element->indices[1] = m_points->size(); + element->indices[2] = m_points->size() + 1; + element->indices[3] = pointIndex2; + element->middle.rx() = (u.x() + v.x() + w.x() + q.x()) >> 2; + element->middle.ry() = (u.y() + v.y() + w.y() + q.y()) >> 2; + m_points->add(v); + m_points->add(w); + return true; + } +} + +void PathSimplifier::setElementToCubicAndSimplify(Element *element, quint32 pointIndex1, + const QPoint &v, const QPoint &w, + quint32 pointIndex2) +{ + const QPoint &u = m_points->at(pointIndex1); + const QPoint &q = m_points->at(pointIndex2); + if (flattenCubic(u, v, w, q)) { + // Insert line. + element->degree = Element::Line; + element->indices[0] = pointIndex1; + element->indices[1] = pointIndex2; + element->middle.rx() = (u.x() + q.x()) >> 1; + element->middle.ry() = (u.y() + q.y()) >> 1; + return; + } + + bool intersecting = (u == q) || intersectionPoint(u, v, w, q).isValid(); + if (!intersecting) { + // Insert bezier. + element->degree = Element::Cubic; + element->indices[0] = pointIndex1; + element->indices[1] = m_points->size(); + element->indices[2] = m_points->size() + 1; + element->indices[3] = pointIndex2; + element->middle.rx() = (u.x() + v.x() + w.x() + q.x()) >> 2; + element->middle.ry() = (u.y() + v.y() + w.y() + q.y()) >> 2; + m_points->add(v); + m_points->add(w); + return; + } + + QPoint pts[5]; + splitCubic(u, v, w, q, pts); + int pointIndex = m_points->size(); + m_points->add(pts[2]); + Element *element2 = m_elementAllocator.newElement(); + m_elements.add(element2); + setElementToCubicAndSimplify(element, pointIndex1, pts[0], pts[1], pointIndex); + setElementToCubicAndSimplify(element2, pointIndex, pts[3], pts[4], pointIndex2); +} + +PathSimplifier::RBNode *PathSimplifier::findElementLeftOf(const Element *element, + const QPair<RBNode *, RBNode *> &bounds) +{ + if (!m_elementList.root) + return 0; + RBNode *current = bounds.first; + Q_ASSERT(!current || !elementIsLeftOf(element, current->data)); + if (!current) + current = m_elementList.front(m_elementList.root); + Q_ASSERT(current); + RBNode *result = 0; + while (current != bounds.second && !elementIsLeftOf(element, current->data)) { + result = current; + current = m_elementList.next(current); + } + return result; +} + +bool PathSimplifier::elementIsLeftOf(const Element *left, const Element *right) +{ + const QPoint &leftU = m_points->at(left->upperIndex()); + const QPoint &leftL = m_points->at(left->lowerIndex()); + const QPoint &rightU = m_points->at(right->upperIndex()); + const QPoint &rightL = m_points->at(right->lowerIndex()); + Q_ASSERT(leftL >= rightU && rightL >= leftU); + if (leftU.x() < qMin(rightL.x(), rightU.x())) + return true; + if (leftU.x() > qMax(rightL.x(), rightU.x())) + return false; + int d = pointDistanceFromLine(leftU, rightL, rightU); + // d < 0: left, d > 0: right, d == 0: on top + if (d == 0) { + d = pointDistanceFromLine(leftL, rightL, rightU); + if (d == 0) { + if (right->degree > Element::Line) { + d = pointDistanceFromLine(leftL, rightL, m_points->at(right->indices[1])); + if (d == 0) + d = pointDistanceFromLine(leftL, rightL, m_points->at(right->indices[2])); + } else if (left->degree > Element::Line) { + d = pointDistanceFromLine(m_points->at(left->indices[1]), rightL, rightU); + if (d == 0) + d = pointDistanceFromLine(m_points->at(left->indices[2]), rightL, rightU); + } + } + } + return d < 0; +} + +QPair<PathSimplifier::RBNode *, PathSimplifier::RBNode *> PathSimplifier::outerBounds(const QPoint &point) +{ + RBNode *current = m_elementList.root; + QPair<RBNode *, RBNode *> result(0, 0); + + while (current) { + const Element *element = current->data; + Q_ASSERT(element->edgeNode == current); + const QPoint &v1 = m_points->at(element->lowerIndex()); + const QPoint &v2 = m_points->at(element->upperIndex()); + Q_ASSERT(point >= v2 && point <= v1); + if (point == v1 || point == v2) + break; + int d = pointDistanceFromLine(point, v1, v2); + if (d == 0) { + if (element->degree == Element::Line) + break; + d = pointDistanceFromLine(point, v1, m_points->at(element->indices[1])); + if (d == 0) + d = pointDistanceFromLine(point, v1, m_points->at(element->indices[2])); + Q_ASSERT(d != 0); + } + if (d < 0) { + result.second = current; + current = current->left; + } else { + result.first = current; + current = current->right; + } + } + + if (!current) + return result; + + RBNode *mid = current; + + current = mid->left; + while (current) { + const Element *element = current->data; + Q_ASSERT(element->edgeNode == current); + const QPoint &v1 = m_points->at(element->lowerIndex()); + const QPoint &v2 = m_points->at(element->upperIndex()); + Q_ASSERT(point >= v2 && point <= v1); + bool equal = (point == v1 || point == v2); + if (!equal) { + int d = pointDistanceFromLine(point, v1, v2); + Q_ASSERT(d >= 0); + equal = (d == 0 && element->degree == Element::Line); + } + if (equal) { + current = current->left; + } else { + result.first = current; + current = current->right; + } + } + + current = mid->right; + while (current) { + const Element *element = current->data; + Q_ASSERT(element->edgeNode == current); + const QPoint &v1 = m_points->at(element->lowerIndex()); + const QPoint &v2 = m_points->at(element->upperIndex()); + Q_ASSERT(point >= v2 && point <= v1); + bool equal = (point == v1 || point == v2); + if (!equal) { + int d = pointDistanceFromLine(point, v1, v2); + Q_ASSERT(d <= 0); + equal = (d == 0 && element->degree == Element::Line); + } + if (equal) { + current = current->right; + } else { + result.second = current; + current = current->left; + } + } + + return result; +} + +inline bool PathSimplifier::flattenQuadratic(const QPoint &u, const QPoint &v, const QPoint &w) +{ + QPoint deltas[2] = { v - u, w - v }; + int d = qAbs(cross(deltas[0], deltas[1])); + int l = qAbs(deltas[0].x()) + qAbs(deltas[0].y()) + qAbs(deltas[1].x()) + qAbs(deltas[1].y()); + return d < (Q_FIXED_POINT_SCALE * Q_FIXED_POINT_SCALE * 3 / 2) || l <= Q_FIXED_POINT_SCALE * 2; +} + +inline bool PathSimplifier::flattenCubic(const QPoint &u, const QPoint &v, + const QPoint &w, const QPoint &q) +{ + QPoint deltas[] = { v - u, w - v, q - w, q - u }; + int d = qAbs(cross(deltas[0], deltas[1])) + qAbs(cross(deltas[1], deltas[2])) + + qAbs(cross(deltas[0], deltas[3])) + qAbs(cross(deltas[3], deltas[2])); + int l = qAbs(deltas[0].x()) + qAbs(deltas[0].y()) + qAbs(deltas[1].x()) + qAbs(deltas[1].y()) + + qAbs(deltas[2].x()) + qAbs(deltas[2].y()); + return d < (Q_FIXED_POINT_SCALE * Q_FIXED_POINT_SCALE * 3) || l <= Q_FIXED_POINT_SCALE * 2; +} + +inline bool PathSimplifier::splitQuadratic(const QPoint &u, const QPoint &v, + const QPoint &w, QPoint *result) +{ + result[0] = u + v; + result[2] = v + w; + result[1] = result[0] + result[2]; + bool accurate = ((result[0].x() | result[0].y() | result[2].x() | result[2].y()) & 1) == 0 + && ((result[1].x() | result[1].y()) & 3) == 0; + result[0].rx() >>= 1; + result[0].ry() >>= 1; + result[1].rx() >>= 2; + result[1].ry() >>= 2; + result[2].rx() >>= 1; + result[2].ry() >>= 1; + return accurate; +} + +inline bool PathSimplifier::splitCubic(const QPoint &u, const QPoint &v, + const QPoint &w, const QPoint &q, QPoint *result) +{ + result[0] = u + v; + result[2] = v + w; + result[4] = w + q; + result[1] = result[0] + result[2]; + result[3] = result[2] + result[4]; + result[2] = result[1] + result[3]; + bool accurate = ((result[0].x() | result[0].y() | result[4].x() | result[4].y()) & 1) == 0 + && ((result[1].x() | result[1].y() | result[3].x() | result[3].y()) & 3) == 0 + && ((result[2].x() | result[2].y()) & 7) == 0; + result[0].rx() >>= 1; + result[0].ry() >>= 1; + result[1].rx() >>= 2; + result[1].ry() >>= 2; + result[2].rx() >>= 3; + result[2].ry() >>= 3; + result[3].rx() >>= 2; + result[3].ry() >>= 2; + result[4].rx() >>= 1; + result[4].ry() >>= 1; + return accurate; +} + +inline void PathSimplifier::subDivQuadratic(const QPoint &u, const QPoint &v, const QPoint &w) +{ + if (flattenQuadratic(u, v, w)) + return; + QPoint pts[3]; + splitQuadratic(u, v, w, pts); + subDivQuadratic(u, pts[0], pts[1]); + m_indices->add(m_points->size()); + m_points->add(pts[1]); + subDivQuadratic(pts[1], pts[2], w); +} + +inline void PathSimplifier::subDivCubic(const QPoint &u, const QPoint &v, + const QPoint &w, const QPoint &q) +{ + if (flattenCubic(u, v, w, q)) + return; + QPoint pts[5]; + splitCubic(u, v, w, q, pts); + subDivCubic(u, pts[0], pts[1], pts[2]); + m_indices->add(m_points->size()); + m_points->add(pts[2]); + subDivCubic(pts[2], pts[3], pts[4], q); +} + +void PathSimplifier::sortEvents(Event *events, int count) +{ + // Bucket sort + insertion sort. + Q_ASSERT(count > 0); + QDataBuffer<Event> buffer(count); + buffer.resize(count); + QScopedArrayPointer<int> bins(new int[count]); + int counts[0x101]; + memset(counts, 0, sizeof(counts)); + + int minimum, maximum; + minimum = maximum = events[0].point.y(); + for (int i = 1; i < count; ++i) { + minimum = qMin(minimum, events[i].point.y()); + maximum = qMax(maximum, events[i].point.y()); + } + + for (int i = 0; i < count; ++i) { + bins[i] = ((maximum - events[i].point.y()) << 8) / (maximum - minimum + 1); + Q_ASSERT(bins[i] >= 0 && bins[i] < 0x100); + ++counts[bins[i]]; + } + + for (int i = 1; i < 0x100; ++i) + counts[i] += counts[i - 1]; + counts[0x100] = counts[0xff]; + Q_ASSERT(counts[0x100] == count); + + for (int i = 0; i < count; ++i) + buffer.at(--counts[bins[i]]) = events[i]; + + int j = 0; + for (int i = 0; i < 0x100; ++i) { + for (; j < counts[i + 1]; ++j) { + int k = j; + while (k > 0 && (buffer.at(j) < events[k - 1])) { + events[k] = events[k - 1]; + --k; + } + events[k] = buffer.at(j); + } + } +} + +} // end anonymous namespace + + +void qSimplifyPath(const QVectorPath &path, QDataBuffer<QPoint> &vertices, + QDataBuffer<quint32> &indices, const QTransform &matrix) +{ + PathSimplifier(path, vertices, indices, matrix); +} + +void qSimplifyPath(const QPainterPath &path, QDataBuffer<QPoint> &vertices, + QDataBuffer<quint32> &indices, const QTransform &matrix) +{ + qSimplifyPath(qtVectorPathForPath(path), vertices, indices, matrix); +} + + +QT_END_NAMESPACE diff --git a/src/declarative/scenegraph/qsgpathsimplifier_p.h b/src/declarative/scenegraph/qsgpathsimplifier_p.h new file mode 100644 index 0000000000..0639c4f622 --- /dev/null +++ b/src/declarative/scenegraph/qsgpathsimplifier_p.h @@ -0,0 +1,68 @@ +/**************************************************************************** +** +** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtDeclarative module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** This file may be used under the terms of the GNU Lesser General Public +** License version 2.1 as published by the Free Software Foundation and +** appearing in the file LICENSE.LGPL included in the packaging of this +** file. Please review the following information to ensure the GNU Lesser +** General Public License version 2.1 requirements will be met: +** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU General +** Public License version 3.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 the GNU General +** Public License version 3.0 requirements will be met: +** http://www.gnu.org/copyleft/gpl.html. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QSGPATHSIMPLIFIER_P_H +#define QSGPATHSIMPLIFIER_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtGui/qpainterpath.h> +#include <QtGui/private/qdatabuffer_p.h> +#include <QtGui/private/qvectorpath_p.h> + +QT_BEGIN_NAMESPACE + +// The returned vertices are in 8:8 fixed point format. The path is assumed to be in the range (-128, 128)x(-128, 128). +void qSimplifyPath(const QVectorPath &path, QDataBuffer<QPoint> &vertices, QDataBuffer<quint32> &indices, const QTransform &matrix = QTransform()); +void qSimplifyPath(const QPainterPath &path, QDataBuffer<QPoint> &vertices, QDataBuffer<quint32> &indices, const QTransform &matrix = QTransform()); + +QT_END_NAMESPACE + +#endif diff --git a/src/declarative/scenegraph/scenegraph.pri b/src/declarative/scenegraph/scenegraph.pri index 3a2a7fafee..aa9d2bc6b2 100644 --- a/src/declarative/scenegraph/scenegraph.pri +++ b/src/declarative/scenegraph/scenegraph.pri @@ -62,7 +62,8 @@ HEADERS += \ $$PWD/qsgdefaultglyphnode_p_p.h \ $$PWD/qsgdefaultimagenode_p.h \ $$PWD/qsgdefaultrectanglenode_p.h \ - $$PWD/qsgflashnode_p.h + $$PWD/qsgflashnode_p.h \ + $$PWD/qsgpathsimplifier_p.h SOURCES += \ $$PWD/qsgadaptationlayer.cpp \ @@ -75,4 +76,5 @@ SOURCES += \ $$PWD/qsgdistancefieldglyphnode_p.cpp \ $$PWD/qsgdefaultimagenode.cpp \ $$PWD/qsgdefaultrectanglenode.cpp \ - $$PWD/qsgflashnode.cpp + $$PWD/qsgflashnode.cpp \ + $$PWD/qsgpathsimplifier.cpp |