diff options
Diffstat (limited to 'src/gui/painting/qrasterizer.cpp')
| -rw-r--r-- | src/gui/painting/qrasterizer.cpp | 1249 |
1 files changed, 1249 insertions, 0 deletions
diff --git a/src/gui/painting/qrasterizer.cpp b/src/gui/painting/qrasterizer.cpp new file mode 100644 index 0000000..583885c --- /dev/null +++ b/src/gui/painting/qrasterizer.cpp @@ -0,0 +1,1249 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, 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.0, 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. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qrasterizer_p.h" + +#include <QPoint> +#include <QRect> + +#include <private/qmath_p.h> +#include <private/qdatabuffer_p.h> +#include <private/qdrawhelper_p.h> + +QT_BEGIN_NAMESPACE + +typedef int Q16Dot16; +#define Q16Dot16ToFloat(i) ((i)/65536.) +#define FloatToQ16Dot16(i) (int)((i) * 65536.) +#define IntToQ16Dot16(i) ((i) << 16) +#define Q16Dot16ToInt(i) ((i) >> 16) +#define Q16Dot16Factor 65536 + +#define Q16Dot16Multiply(x, y) (int)((qlonglong(x) * qlonglong(y)) >> 16) +#define Q16Dot16FastMultiply(x, y) (((x) * (y)) >> 16) + +#define SPAN_BUFFER_SIZE 256 + +#define COORD_ROUNDING 1 // 0: round up, 1: round down +#define COORD_OFFSET 32 // 26.6, 32 is half a pixel + +class QSpanBuffer { +public: + QSpanBuffer(ProcessSpans blend, void *data, const QRect &clipRect) + : m_spanCount(0) + , m_blend(blend) + , m_data(data) + , m_clipRect(clipRect) + { + } + + ~QSpanBuffer() + { + flushSpans(); + } + + void addSpan(int x, unsigned int len, int y, unsigned char coverage) + { + if (!coverage || !len) + return; + + Q_ASSERT(y >= m_clipRect.top()); + Q_ASSERT(y <= m_clipRect.bottom()); + Q_ASSERT(x >= m_clipRect.left()); + Q_ASSERT(x + int(len) - 1 <= m_clipRect.right()); + + m_spans[m_spanCount].x = x; + m_spans[m_spanCount].len = len; + m_spans[m_spanCount].y = y; + m_spans[m_spanCount].coverage = coverage; + + if (++m_spanCount == SPAN_BUFFER_SIZE) + flushSpans(); + } + +private: + void flushSpans() + { + m_blend(m_spanCount, m_spans, m_data); + m_spanCount = 0; + } + + QT_FT_Span m_spans[SPAN_BUFFER_SIZE]; + int m_spanCount; + + ProcessSpans m_blend; + void *m_data; + + QRect m_clipRect; +}; + +#define CHUNK_SIZE 64 +class QScanConverter +{ +public: + QScanConverter(); + ~QScanConverter(); + + void begin(int top, int bottom, int left, int right, + Qt::FillRule fillRule, QSpanBuffer *spanBuffer); + void end(); + + void mergeCurve(const QT_FT_Vector &a, const QT_FT_Vector &b, + const QT_FT_Vector &c, const QT_FT_Vector &d); + void mergeLine(QT_FT_Vector a, QT_FT_Vector b); + + struct Line + { + Q16Dot16 x; + Q16Dot16 delta; + + int top, bottom; + + int winding; + }; + +private: + struct Intersection + { + int x; + int winding; + + int left, right; + }; + + inline bool clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding); + inline void mergeIntersection(Intersection *head, const Intersection &isect); + + void prepareChunk(); + + void emitNode(const Intersection *node); + void emitSpans(int chunk); + + inline void allocate(int size); + + QDataBuffer<Line> m_lines; + + int m_alloc; + int m_size; + + int m_top; + int m_bottom; + + Q16Dot16 m_leftFP; + Q16Dot16 m_rightFP; + + int m_fillRuleMask; + + int m_x; + int m_y; + int m_winding; + + Intersection *m_intersections; + + QSpanBuffer *m_spanBuffer; + + QDataBuffer<Line *> m_active; + + template <typename T> + friend void qScanConvert(QScanConverter &d, T allVertical); +}; + +class QRasterizerPrivate +{ +public: + bool antialiased; + ProcessSpans blend; + void *data; + QRect clipRect; + + QScanConverter scanConverter; +}; + +QScanConverter::QScanConverter() + : m_alloc(0) + , m_size(0) + , m_intersections(0) +{ +} + +QScanConverter::~QScanConverter() +{ + if (m_intersections) + free(m_intersections); +} + +void QScanConverter::begin(int top, int bottom, int left, int right, + Qt::FillRule fillRule, QSpanBuffer *spanBuffer) +{ + m_top = top; + m_bottom = bottom; + m_leftFP = IntToQ16Dot16(left); + m_rightFP = IntToQ16Dot16(right + 1); + + m_lines.reset(); + + m_fillRuleMask = fillRule == Qt::WindingFill ? ~0x0 : 0x1; + m_spanBuffer = spanBuffer; +} + +void QScanConverter::prepareChunk() +{ + m_size = CHUNK_SIZE; + + allocate(CHUNK_SIZE); + memset(m_intersections, 0, CHUNK_SIZE * sizeof(Intersection)); +} + +void QScanConverter::emitNode(const Intersection *node) +{ +tail_call: + if (node->left) + emitNode(node + node->left); + + if (m_winding & m_fillRuleMask) + m_spanBuffer->addSpan(m_x, node->x - m_x, m_y, 0xff); + + m_x = node->x; + m_winding += node->winding; + + if (node->right) { + node += node->right; + goto tail_call; + } +} + +void QScanConverter::emitSpans(int chunk) +{ + for (int dy = 0; dy < CHUNK_SIZE; ++dy) { + m_x = 0; + m_y = chunk + dy; + m_winding = 0; + + emitNode(&m_intersections[dy]); + } +} + +// split control points b[0] ... b[3] into +// left (b[0] ... b[3]) and right (b[3] ... b[6]) +static void split(QT_FT_Vector *b) +{ + b[6] = b[3]; + + { + const QT_FT_Pos temp = (b[1].x + b[2].x)/2; + + b[1].x = (b[0].x + b[1].x)/2; + b[5].x = (b[2].x + b[3].x)/2; + b[2].x = (b[1].x + temp)/2; + b[4].x = (b[5].x + temp)/2; + b[3].x = (b[2].x + b[4].x)/2; + } + { + const QT_FT_Pos temp = (b[1].y + b[2].y)/2; + + b[1].y = (b[0].y + b[1].y)/2; + b[5].y = (b[2].y + b[3].y)/2; + b[2].y = (b[1].y + temp)/2; + b[4].y = (b[5].y + temp)/2; + b[3].y = (b[2].y + b[4].y)/2; + } +} + +static inline bool topOrder(const QScanConverter::Line &a, const QScanConverter::Line &b) +{ + return a.top < b.top; +} + +static inline bool xOrder(const QScanConverter::Line *a, const QScanConverter::Line *b) +{ + return a->x < b->x; +} + +template <bool B> +struct QBoolToType +{ + inline bool operator()() const + { + return B; + } +}; + +// should be a member function but VC6 doesn't support member template functions +template <typename T> +void qScanConvert(QScanConverter &d, T allVertical) +{ + qSort(d.m_lines.data(), d.m_lines.data() + d.m_lines.size(), topOrder); + int line = 0; + for (int y = d.m_lines.first().top; y <= d.m_bottom; ++y) { + for (; line < d.m_lines.size() && d.m_lines.at(line).top == y; ++line) { + // add node to active list + if (allVertical()) { + QScanConverter::Line *l = &d.m_lines.at(line); + d.m_active.resize(d.m_active.size() + 1); + int j; + for (j = d.m_active.size() - 2; j >= 0 && xOrder(l, d.m_active.at(j)); --j) + d.m_active.at(j+1) = d.m_active.at(j); + d.m_active.at(j+1) = l; + } else { + d.m_active << &d.m_lines.at(line); + } + } + + int numActive = d.m_active.size(); + if (!allVertical()) { + // use insertion sort instead of qSort, as the active edge list is quite small + // and in the average case already sorted + for (int i = 1; i < numActive; ++i) { + QScanConverter::Line *l = d.m_active.at(i); + int j; + for (j = i-1; j >= 0 && xOrder(l, d.m_active.at(j)); --j) + d.m_active.at(j+1) = d.m_active.at(j); + d.m_active.at(j+1) = l; + } + } + + int x = 0; + int winding = 0; + for (int i = 0; i < numActive; ++i) { + QScanConverter::Line *node = d.m_active.at(i); + + const int current = Q16Dot16ToInt(node->x); + if (winding & d.m_fillRuleMask) + d.m_spanBuffer->addSpan(x, current - x, y, 0xff); + + x = current; + winding += node->winding; + + if (node->bottom == y) { + // remove node from active list + for (int j = i; j < numActive - 1; ++j) + d.m_active.at(j) = d.m_active.at(j+1); + + d.m_active.resize(--numActive); + --i; + } else if (!allVertical()) + node->x += node->delta; + } + } + d.m_active.reset(); +} + +void QScanConverter::end() +{ + if (m_lines.isEmpty()) + return; + + if (m_lines.size() <= 32) { + bool allVertical = true; + for (int i = 0; i < m_lines.size(); ++i) { + if (m_lines.at(i).delta) { + allVertical = false; + break; + } + } + if (allVertical) + qScanConvert(*this, QBoolToType<true>()); + else + qScanConvert(*this, QBoolToType<false>()); + } else { + for (int chunkTop = m_top; chunkTop <= m_bottom; chunkTop += CHUNK_SIZE) { + prepareChunk(); + + Intersection isect = { 0, 0, 0, 0 }; + + const int chunkBottom = chunkTop + CHUNK_SIZE; + for (int i = 0; i < m_lines.size(); ++i) { + Line &line = m_lines.at(i); + + if ((line.bottom < chunkTop) || (line.top > chunkBottom)) + continue; + + const int top = qMax(0, line.top - chunkTop); + const int bottom = qMin(CHUNK_SIZE, line.bottom + 1 - chunkTop); + allocate(m_size + bottom - top); + + isect.winding = line.winding; + + Intersection *it = m_intersections + top; + Intersection *end = m_intersections + bottom; + + if (line.delta) { + for (; it != end; ++it) { + isect.x = Q16Dot16ToInt(line.x); + line.x += line.delta; + mergeIntersection(it, isect); + } + } else { + isect.x = Q16Dot16ToInt(line.x); + for (; it != end; ++it) + mergeIntersection(it, isect); + } + } + + emitSpans(chunkTop); + } + } + + if (m_alloc > 1024) { + free(m_intersections); + m_alloc = 0; + m_size = 0; + m_intersections = 0; + } + + if (m_lines.size() > 1024) + m_lines.shrink(1024); +} + +inline void QScanConverter::allocate(int size) +{ + if (m_alloc < size) { + m_alloc = qMax(size, 2 * m_alloc); + m_intersections = (Intersection *)realloc(m_intersections, m_alloc * sizeof(Intersection)); + } +} + +inline void QScanConverter::mergeIntersection(Intersection *it, const Intersection &isect) +{ + Intersection *current = it; + + while (isect.x != current->x) { + int &next = isect.x < current->x ? current->left : current->right; + if (next) + current += next; + else { + Intersection *last = m_intersections + m_size; + next = last - current; + *last = isect; + ++m_size; + return; + } + } + + current->winding += isect.winding; +} + +void QScanConverter::mergeCurve(const QT_FT_Vector &pa, const QT_FT_Vector &pb, + const QT_FT_Vector &pc, const QT_FT_Vector &pd) +{ + // make room for 32 splits + QT_FT_Vector beziers[4 + 3 * 32]; + + QT_FT_Vector *b = beziers; + + b[0] = pa; + b[1] = pb; + b[2] = pc; + b[3] = pd; + + const QT_FT_Pos flatness = 16; + + while (b >= beziers) { + QT_FT_Vector delta = { b[3].x - b[0].x, b[3].y - b[0].y }; + QT_FT_Pos l = qAbs(delta.x) + qAbs(delta.y); + + bool belowThreshold; + if (l > 64) { + qlonglong d2 = qAbs(qlonglong(b[1].x-b[0].x) * qlonglong(delta.y) - + qlonglong(b[1].y-b[0].y) * qlonglong(delta.x)); + qlonglong d3 = qAbs(qlonglong(b[2].x-b[0].x) * qlonglong(delta.y) - + qlonglong(b[2].y-b[0].y) * qlonglong(delta.x)); + + qlonglong d = d2 + d3; + + belowThreshold = (d <= qlonglong(flatness) * qlonglong(l)); + } else { + QT_FT_Pos d = qAbs(b[0].x-b[1].x) + qAbs(b[0].y-b[1].y) + + qAbs(b[0].x-b[2].x) + qAbs(b[0].y-b[2].y); + + belowThreshold = (d <= flatness); + } + + if (belowThreshold || b == beziers + 3 * 32) { + mergeLine(b[0], b[3]); + b -= 3; + continue; + } + + split(b); + b += 3; + } +} + +inline bool QScanConverter::clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding) +{ + bool right = edgeFP == m_rightFP; + + if (xFP == edgeFP) { + if ((slopeFP > 0) ^ right) + return false; + else { + Line line = { edgeFP, 0, iTop, iBottom, winding }; + m_lines.add(line); + return true; + } + } + + Q16Dot16 lastFP = xFP + slopeFP * (iBottom - iTop); + + if (lastFP == edgeFP) { + if ((slopeFP < 0) ^ right) + return false; + else { + Line line = { edgeFP, 0, iTop, iBottom, winding }; + m_lines.add(line); + return true; + } + } + + // does line cross edge? + if ((lastFP < edgeFP) ^ (xFP < edgeFP)) { + Q16Dot16 deltaY = Q16Dot16((edgeFP - xFP) / Q16Dot16ToFloat(slopeFP)); + + if ((xFP < edgeFP) ^ right) { + // top segment needs to be clipped + int iHeight = Q16Dot16ToInt(deltaY + 1); + int iMiddle = iTop + iHeight; + + Line line = { edgeFP, 0, iTop, iMiddle, winding }; + m_lines.add(line); + + if (iMiddle != iBottom) { + xFP += slopeFP * (iHeight + 1); + iTop = iMiddle + 1; + } else + return true; + } else { + // bottom segment needs to be clipped + int iHeight = Q16Dot16ToInt(deltaY); + int iMiddle = iTop + iHeight; + + if (iMiddle != iBottom) { + Line line = { edgeFP, 0, iMiddle + 1, iBottom, winding }; + m_lines.add(line); + + iBottom = iMiddle; + } + } + return false; + } else if ((xFP < edgeFP) ^ right) { + Line line = { edgeFP, 0, iTop, iBottom, winding }; + m_lines.add(line); + return true; + } + + return false; +} + +void QScanConverter::mergeLine(QT_FT_Vector a, QT_FT_Vector b) +{ + int winding = 1; + + if (a.y > b.y) { + qSwap(a, b); + winding = -1; + } + + a.x += COORD_OFFSET; + a.y += COORD_OFFSET; + b.x += COORD_OFFSET; + b.y += COORD_OFFSET; + + int iTop = qMax(m_top, int((a.y + 32 - COORD_ROUNDING) >> 6)); + int iBottom = qMin(m_bottom, int((b.y - 32 - COORD_ROUNDING) >> 6)); + + if (iTop <= iBottom) { + Q16Dot16 aFP = Q16Dot16Factor/2 + (a.x << 10) - COORD_ROUNDING; + + if (b.x == a.x) { + Line line = { qBound(m_leftFP, aFP, m_rightFP), 0, iTop, iBottom, winding }; + m_lines.add(line); + } else { + const qreal slope = (b.x - a.x) / qreal(b.y - a.y); + + const Q16Dot16 slopeFP = FloatToQ16Dot16(slope); + + Q16Dot16 xFP = aFP + Q16Dot16Multiply(slopeFP, + IntToQ16Dot16(iTop) + + Q16Dot16Factor/2 - (a.y << 10)); + + if (clip(xFP, iTop, iBottom, slopeFP, m_leftFP, winding)) + return; + + if (clip(xFP, iTop, iBottom, slopeFP, m_rightFP, winding)) + return; + + Q_ASSERT(xFP >= m_leftFP); + + Line line = { xFP, slopeFP, iTop, iBottom, winding }; + m_lines.add(line); + } + } +} + +QRasterizer::QRasterizer() + : d(new QRasterizerPrivate) +{ +} + +QRasterizer::~QRasterizer() +{ + delete d; +} + +void QRasterizer::setAntialiased(bool antialiased) +{ + d->antialiased = antialiased; +} + +void QRasterizer::initialize(ProcessSpans blend, void *data) +{ + d->blend = blend; + d->data = data; +} + +void QRasterizer::setClipRect(const QRect &clipRect) +{ + d->clipRect = clipRect; +} + +static Q16Dot16 intersectPixelFP(int x, Q16Dot16 top, Q16Dot16 bottom, Q16Dot16 leftIntersectX, Q16Dot16 rightIntersectX, Q16Dot16 slope, Q16Dot16 invSlope) +{ + Q16Dot16 leftX = IntToQ16Dot16(x); + Q16Dot16 rightX = IntToQ16Dot16(x) + Q16Dot16Factor; + + Q16Dot16 leftIntersectY, rightIntersectY; + if (slope > 0) { + leftIntersectY = top + Q16Dot16Multiply(leftX - leftIntersectX, invSlope); + rightIntersectY = leftIntersectY + invSlope; + } else { + leftIntersectY = top + Q16Dot16Multiply(leftX - rightIntersectX, invSlope); + rightIntersectY = leftIntersectY + invSlope; + } + + if (leftIntersectX >= leftX && rightIntersectX <= rightX) { + return Q16Dot16Multiply(bottom - top, leftIntersectX - leftX + ((rightIntersectX - leftIntersectX) >> 1)); + } else if (leftIntersectX >= rightX) { + return bottom - top; + } else if (leftIntersectX >= leftX) { + if (slope > 0) { + return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, rightIntersectY - top); + } else { + return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, bottom - rightIntersectY); + } + } else if (rightIntersectX <= leftX) { + return 0; + } else if (rightIntersectX <= rightX) { + if (slope > 0) { + return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, bottom - leftIntersectY); + } else { + return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, leftIntersectY - top); + } + } else { + if (slope > 0) { + return (bottom - rightIntersectY) + ((rightIntersectY - leftIntersectY) >> 1); + } else { + return (rightIntersectY - top) + ((leftIntersectY - rightIntersectY) >> 1); + } + } +} + +static inline bool q16Dot16Compare(qreal p1, qreal p2) +{ + return FloatToQ16Dot16(p2 - p1) == 0; +} + +static inline qreal qRoundF(qreal v) +{ +#ifdef QT_USE_MATH_H_FLOATS + if (sizeof(qreal) == sizeof(float)) + return floorf(v + 0.5); + else +#endif + return floor(v + 0.5); +} + +void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap) +{ + if (a == b || width == 0) + return; + + QPointF pa = a; + QPointF pb = b; + + QPointF offs = QPointF(qAbs(b.y() - a.y()), qAbs(b.x() - a.x())) * width * 0.5; + if (squareCap) + offs += QPointF(offs.y(), offs.x()); + const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs); + + if (!clip.contains(a) || !clip.contains(b)) { + qreal t1 = 0; + qreal t2 = 1; + + const qreal o[2] = { a.x(), a.y() }; + const qreal d[2] = { b.x() - a.x(), b.y() - a.y() }; + + const qreal low[2] = { clip.left(), clip.top() }; + const qreal high[2] = { clip.right(), clip.bottom() }; + + for (int i = 0; i < 2; ++i) { + if (d[i] == 0) { + if (o[i] <= low[i] || o[i] >= high[i]) + return; + continue; + } + const qreal d_inv = 1 / d[i]; + qreal t_low = (low[i] - o[i]) * d_inv; + qreal t_high = (high[i] - o[i]) * d_inv; + if (t_low > t_high) + qSwap(t_low, t_high); + if (t1 < t_low) + t1 = t_low; + if (t2 > t_high) + t2 = t_high; + if (t1 >= t2) + return; + } + pa = a + (b - a) * t1; + pb = a + (b - a) * t2; + } + + if (!d->antialiased) { + pa.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.; + pa.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.; + pb.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.; + pb.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.; + } + + { + const qreal gridResolution = 64; + const qreal reciprocal = 1 / gridResolution; + + // snap to grid to prevent large slopes + pa.rx() = qRoundF(pa.rx() * gridResolution) * reciprocal; + pa.ry() = qRoundF(pa.ry() * gridResolution) * reciprocal; + pb.rx() = qRoundF(pb.rx() * gridResolution) * reciprocal; + pb.ry() = qRoundF(pb.ry() * gridResolution) * reciprocal; + + // old delta + const QPointF d0 = a - b; + const qreal w0 = d0.x() * d0.x() + d0.y() * d0.y(); + + // new delta + const QPointF d = pa - pb; + const qreal w = d.x() * d.x() + d.y() * d.y(); + + if (w == 0) + return; + + // adjust width which is given relative to |b - a| + width *= sqrt(w0 / w); + } + + QSpanBuffer buffer(d->blend, d->data, d->clipRect); + + if (q16Dot16Compare(pa.y(), pb.y())) { + const qreal x = (pa.x() + pb.x()) * 0.5f; + const qreal dx = qAbs(pb.x() - pa.x()) * 0.5f; + + const qreal y = pa.y(); + const qreal dy = width * dx; + + pa = QPointF(x, y - dy); + pb = QPointF(x, y + dy); + + if (squareCap) + width = 1 / width + 1.0f; + else + width = 1 / width; + + squareCap = false; + } + + if (q16Dot16Compare(pa.x(), pb.x())) { + if (pa.y() > pb.y()) + qSwap(pa, pb); + + const qreal dy = pb.y() - pa.y(); + const qreal halfWidth = 0.5f * width * dy; + + if (squareCap) { + pa.ry() -= halfWidth; + pb.ry() += halfWidth; + } + + qreal left = pa.x() - halfWidth; + qreal right = pa.x() + halfWidth; + + left = qBound(qreal(d->clipRect.left()), left, qreal(d->clipRect.right() + 1)); + right = qBound(qreal(d->clipRect.left()), right, qreal(d->clipRect.right() + 1)); + + pa.ry() = qBound(qreal(d->clipRect.top()), pa.y(), qreal(d->clipRect.bottom() + 1)); + pb.ry() = qBound(qreal(d->clipRect.top()), pb.y(), qreal(d->clipRect.bottom() + 1)); + + if (q16Dot16Compare(left, right) || q16Dot16Compare(pa.y(), pb.y())) + return; + + if (d->antialiased) { + const Q16Dot16 iLeft = int(left); + const Q16Dot16 iRight = int(right); + const Q16Dot16 leftWidth = IntToQ16Dot16(iLeft + 1) + - FloatToQ16Dot16(left); + const Q16Dot16 rightWidth = FloatToQ16Dot16(right) + - IntToQ16Dot16(iRight); + + Q16Dot16 coverage[3]; + int x[3]; + int len[3]; + + int n = 1; + if (iLeft == iRight) { + coverage[0] = (leftWidth + rightWidth) * 255; + x[0] = iLeft; + len[0] = 1; + } else { + coverage[0] = leftWidth * 255; + x[0] = iLeft; + len[0] = 1; + if (leftWidth == Q16Dot16Factor) { + len[0] = iRight - iLeft; + } else if (iRight - iLeft > 1) { + coverage[1] = IntToQ16Dot16(255); + x[1] = iLeft + 1; + len[1] = iRight - iLeft - 1; + ++n; + } + if (rightWidth) { + coverage[n] = rightWidth * 255; + x[n] = iRight; + len[n] = 1; + ++n; + } + } + + const Q16Dot16 iTopFP = IntToQ16Dot16(int(pa.y())); + const Q16Dot16 iBottomFP = IntToQ16Dot16(int(pb.y())); + const Q16Dot16 yPa = FloatToQ16Dot16(pa.y()); + const Q16Dot16 yPb = FloatToQ16Dot16(pb.y()); + for (Q16Dot16 yFP = iTopFP; yFP <= iBottomFP; yFP += Q16Dot16Factor) { + const Q16Dot16 rowHeight = qMin(yFP + Q16Dot16Factor, yPb) + - qMax(yFP, yPa); + const int y = Q16Dot16ToInt(yFP); + for (int i = 0; i < n; ++i) { + buffer.addSpan(x[i], len[i], y, + Q16Dot16ToInt(Q16Dot16Multiply(rowHeight, coverage[i]))); + } + } + } else { // aliased + int iTop = int(pa.y() + 0.5f); + int iBottom = pb.y() < 0.5f ? -1 : int(pb.y() - 0.5f); + int iLeft = int(left + 0.5f); + int iRight = right < 0.5f ? -1 : int(right - 0.5f); + + int iWidth = iRight - iLeft + 1; + for (int y = iTop; y <= iBottom; ++y) + buffer.addSpan(iLeft, iWidth, y, 255); + } + } else { + if (pa.y() > pb.y()) + qSwap(pa, pb); + + QPointF delta = pb - pa; + delta *= 0.5f * width; + const QPointF perp(delta.y(), -delta.x()); + + if (squareCap) { + pa -= delta; + pb += delta; + } + + QPointF top; + QPointF left; + QPointF right; + QPointF bottom; + + if (pa.x() < pb.x()) { + top = pa + perp; + left = pa - perp; + right = pb + perp; + bottom = pb - perp; + } else { + top = pa - perp; + left = pb - perp; + right = pa + perp; + bottom = pb + perp; + } + + const qreal topBound = qBound(qreal(d->clipRect.top()), top.y(), qreal(d->clipRect.bottom())); + const qreal bottomBound = qBound(qreal(d->clipRect.top()), bottom.y(), qreal(d->clipRect.bottom())); + + const qreal leftSlope = (left.x() - top.x()) / (left.y() - top.y()); + const qreal rightSlope = -1.0f / leftSlope; + + const Q16Dot16 leftSlopeFP = FloatToQ16Dot16(leftSlope); + const Q16Dot16 rightSlopeFP = FloatToQ16Dot16(rightSlope); + + if (d->antialiased) { + const Q16Dot16 iTopFP = IntToQ16Dot16(int(topBound)); + const Q16Dot16 iLeftFP = IntToQ16Dot16(int(left.y())); + const Q16Dot16 iRightFP = IntToQ16Dot16(int(right.y())); + const Q16Dot16 iBottomFP = IntToQ16Dot16(int(bottomBound)); + + Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * leftSlope); + Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * rightSlope); + Q16Dot16 leftIntersectBf = 0; + Q16Dot16 rightIntersectBf = 0; + + if (iLeftFP < iTopFP) + leftIntersectBf = FloatToQ16Dot16(left.x() + (int(topBound) - left.y()) * rightSlope); + + if (iRightFP < iTopFP) + rightIntersectBf = FloatToQ16Dot16(right.x() + (int(topBound) - right.y()) * leftSlope); + + Q16Dot16 rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom; + Q16Dot16 topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf; + Q16Dot16 bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf; + + int leftMin, leftMax, rightMin, rightMax; + + const Q16Dot16 yTopFP = FloatToQ16Dot16(top.y()); + const Q16Dot16 yLeftFP = FloatToQ16Dot16(left.y()); + const Q16Dot16 yRightFP = FloatToQ16Dot16(right.y()); + const Q16Dot16 yBottomFP = FloatToQ16Dot16(bottom.y()); + + rowTop = qMax(iTopFP, yTopFP); + topLeftIntersectAf = leftIntersectAf + + Q16Dot16Multiply(leftSlopeFP, rowTop - iTopFP); + topRightIntersectAf = rightIntersectAf + + Q16Dot16Multiply(rightSlopeFP, rowTop - iTopFP); + + Q16Dot16 yFP = iTopFP; + while (yFP <= iBottomFP) { + rowBottomLeft = qMin(yFP + Q16Dot16Factor, yLeftFP); + rowBottomRight = qMin(yFP + Q16Dot16Factor, yRightFP); + rowTopLeft = qMax(yFP, yLeftFP); + rowTopRight = qMax(yFP, yRightFP); + rowBottom = qMin(yFP + Q16Dot16Factor, yBottomFP); + + if (yFP == iLeftFP) { + const int y = Q16Dot16ToInt(yFP); + leftIntersectBf = FloatToQ16Dot16(left.x() + (y - left.y()) * rightSlope); + topLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowTopLeft - yFP); + bottomLeftIntersectAf = leftIntersectAf + Q16Dot16Multiply(leftSlopeFP, rowBottomLeft - yFP); + } else { + topLeftIntersectBf = leftIntersectBf; + bottomLeftIntersectAf = leftIntersectAf + leftSlopeFP; + } + + if (yFP == iRightFP) { + const int y = Q16Dot16ToInt(yFP); + rightIntersectBf = FloatToQ16Dot16(right.x() + (y - right.y()) * leftSlope); + topRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowTopRight - yFP); + bottomRightIntersectAf = rightIntersectAf + Q16Dot16Multiply(rightSlopeFP, rowBottomRight - yFP); + } else { + topRightIntersectBf = rightIntersectBf; + bottomRightIntersectAf = rightIntersectAf + rightSlopeFP; + } + + if (yFP == iBottomFP) { + bottomLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowBottom - yFP); + bottomRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowBottom - yFP); + } else { + bottomLeftIntersectBf = leftIntersectBf + rightSlopeFP; + bottomRightIntersectBf = rightIntersectBf + leftSlopeFP; + } + + if (yFP < iLeftFP) { + leftMin = Q16Dot16ToInt(bottomLeftIntersectAf); + leftMax = Q16Dot16ToInt(topLeftIntersectAf); + } else if (yFP == iLeftFP) { + leftMin = Q16Dot16ToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf)); + leftMax = Q16Dot16ToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf)); + } else { + leftMin = Q16Dot16ToInt(topLeftIntersectBf); + leftMax = Q16Dot16ToInt(bottomLeftIntersectBf); + } + + leftMin = qBound(d->clipRect.left(), leftMin, d->clipRect.right()); + leftMax = qBound(d->clipRect.left(), leftMax, d->clipRect.right()); + + if (yFP < iRightFP) { + rightMin = Q16Dot16ToInt(topRightIntersectAf); + rightMax = Q16Dot16ToInt(bottomRightIntersectAf); + } else if (yFP == iRightFP) { + rightMin = Q16Dot16ToInt(qMin(topRightIntersectAf, bottomRightIntersectBf)); + rightMax = Q16Dot16ToInt(qMin(bottomRightIntersectAf, topRightIntersectBf)); + } else { + rightMin = Q16Dot16ToInt(bottomRightIntersectBf); + rightMax = Q16Dot16ToInt(topRightIntersectBf); + } + + rightMin = qBound(d->clipRect.left(), rightMin, d->clipRect.right()); + rightMax = qBound(d->clipRect.left(), rightMax, d->clipRect.right()); + + if (leftMax > rightMax) + leftMax = rightMax; + if (rightMin < leftMin) + rightMin = leftMin; + + Q16Dot16 rowHeight = rowBottom - rowTop; + + int x = leftMin; + while (x <= leftMax) { + Q16Dot16 excluded = 0; + + if (yFP <= iLeftFP) + excluded += intersectPixelFP(x, rowTop, rowBottomLeft, + bottomLeftIntersectAf, topLeftIntersectAf, + leftSlopeFP, -rightSlopeFP); + if (yFP >= iLeftFP) + excluded += intersectPixelFP(x, rowTopLeft, rowBottom, + topLeftIntersectBf, bottomLeftIntersectBf, + rightSlopeFP, -leftSlopeFP); + + if (x >= rightMin) { + if (yFP <= iRightFP) + excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight, + topRightIntersectAf, bottomRightIntersectAf, + rightSlopeFP, -leftSlopeFP); + if (yFP >= iRightFP) + excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom, + bottomRightIntersectBf, topRightIntersectBf, + leftSlopeFP, -rightSlopeFP); + } + + Q16Dot16 coverage = rowHeight - excluded; + buffer.addSpan(x, 1, Q16Dot16ToInt(yFP), + Q16Dot16ToInt(255 * coverage)); + ++x; + } + if (x < rightMin) { + buffer.addSpan(x, rightMin - x, Q16Dot16ToInt(yFP), + Q16Dot16ToInt(255 * rowHeight)); + x = rightMin; + } + while (x <= rightMax) { + Q16Dot16 excluded = 0; + if (yFP <= iRightFP) + excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight, + topRightIntersectAf, bottomRightIntersectAf, + rightSlopeFP, -leftSlopeFP); + if (yFP >= iRightFP) + excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom, + bottomRightIntersectBf, topRightIntersectBf, + leftSlopeFP, -rightSlopeFP); + + Q16Dot16 coverage = rowHeight - excluded; + buffer.addSpan(x, 1, Q16Dot16ToInt(yFP), + Q16Dot16ToInt(255 * coverage)); + ++x; + } + + leftIntersectAf += leftSlopeFP; + leftIntersectBf += rightSlopeFP; + rightIntersectAf += rightSlopeFP; + rightIntersectBf += leftSlopeFP; + topLeftIntersectAf = leftIntersectAf; + topRightIntersectAf = rightIntersectAf; + + yFP += Q16Dot16Factor; + rowTop = yFP; + } + } else { // aliased + int iTop = int(top.y() + 0.5f); + int iLeft = left.y() < 0.5f ? -1 : int(left.y() - 0.5f); + int iRight = right.y() < 0.5f ? -1 : int(right.y() - 0.5f); + int iBottom = bottom.y() < 0.5f? -1 : int(bottom.y() - 0.5f); + int iMiddle = qMin(iLeft, iRight); + + Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + 0.5f + (iTop + 0.5f - top.y()) * leftSlope); + Q16Dot16 leftIntersectBf = FloatToQ16Dot16(left.x() + 0.5f + (iLeft + 1.5f - left.y()) * rightSlope); + Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() - 0.5f + (iTop + 0.5f - top.y()) * rightSlope); + Q16Dot16 rightIntersectBf = FloatToQ16Dot16(right.x() - 0.5f + (iRight + 1.5f - right.y()) * leftSlope); + + int ny; + int y = iTop; +#define DO_SEGMENT(next, li, ri, ls, rs) \ + ny = qMin(next + 1, d->clipRect.top()); \ + if (y < ny) { \ + li += ls * (ny - y); \ + ri += rs * (ny - y); \ + y = ny; \ + } \ + if (next > d->clipRect.bottom()) \ + next = d->clipRect.bottom(); \ + for (; y <= next; ++y) { \ + const int x1 = qMax(Q16Dot16ToInt(li), d->clipRect.left()); \ + const int x2 = qMin(Q16Dot16ToInt(ri), d->clipRect.right()); \ + if (x2 >= x1) \ + buffer.addSpan(x1, x2 - x1 + 1, y, 255); \ + li += ls; \ + ri += rs; \ + } + + DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, leftSlopeFP, rightSlopeFP) + DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, rightSlopeFP, rightSlopeFP) + DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, leftSlopeFP, leftSlopeFP) + DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, rightSlopeFP, leftSlopeFP) +#undef DO_SEGMENT + } + } +} + +void QRasterizer::rasterize(const QT_FT_Outline *outline, Qt::FillRule fillRule) +{ + if (outline->n_points < 3 || outline->n_contours == 0) + return; + + const QT_FT_Vector *points = outline->points; + + QSpanBuffer buffer(d->blend, d->data, d->clipRect); + + // ### QT_FT_Outline already has a bounding rect which is + // ### precomputed at this point, so we should probably just be + // ### using that instead... + QT_FT_Pos min_y = points[0].y, max_y = points[0].y; + for (int i = 1; i < outline->n_points; ++i) { + const QT_FT_Vector &p = points[i]; + min_y = qMin(p.y, min_y); + max_y = qMax(p.y, max_y); + } + + int iTopBound = qMax(d->clipRect.top(), int((min_y + 32 + COORD_OFFSET - COORD_ROUNDING) >> 6)); + int iBottomBound = qMin(d->clipRect.bottom(), int((max_y - 32 + COORD_OFFSET - COORD_ROUNDING) >> 6)); + + if (iTopBound > iBottomBound) + return; + + d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer); + + int first = 0; + for (int i = 0; i < outline->n_contours; ++i) { + const int last = outline->contours[i]; + for (int j = first; j < last; ++j) { + if (outline->tags[j+1] == QT_FT_CURVE_TAG_CUBIC) { + Q_ASSERT(outline->tags[j+2] == QT_FT_CURVE_TAG_CUBIC); + d->scanConverter.mergeCurve(points[j], points[j+1], points[j+2], points[j+3]); + j += 2; + } else { + d->scanConverter.mergeLine(points[j], points[j+1]); + } + } + + first = last + 1; + } + + d->scanConverter.end(); +} + +static inline QT_FT_Vector PointToVector(const QPointF &p) +{ + QT_FT_Vector result = { QT_FT_Pos(p.x() * 64), QT_FT_Pos(p.y() * 64) }; + return result; +} + +void QRasterizer::rasterize(const QPainterPath &path, Qt::FillRule fillRule) +{ + if (path.isEmpty()) + return; + + QSpanBuffer buffer(d->blend, d->data, d->clipRect); + + QRectF bounds = path.controlPointRect(); + + int iTopBound = qMax(d->clipRect.top(), int(bounds.top() + 0.5 + (COORD_OFFSET - COORD_ROUNDING)/64.)); + int iBottomBound = qMin(d->clipRect.bottom(), int(bounds.bottom() - 0.5 + (COORD_OFFSET - COORD_ROUNDING)/64.)); + + if (iTopBound > iBottomBound) + return; + + d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer); + + int subpathStart = 0; + QT_FT_Vector last = { 0, 0 }; + for (int i = 0; i < path.elementCount(); ++i) { + switch (path.elementAt(i).type) { + case QPainterPath::LineToElement: + { + QT_FT_Vector p1 = last; + QT_FT_Vector p2 = PointToVector(path.elementAt(i)); + d->scanConverter.mergeLine(p1, p2); + last = p2; + break; + } + case QPainterPath::MoveToElement: + { + if (i != 0) { + QT_FT_Vector first = PointToVector(path.elementAt(subpathStart)); + // close previous subpath + if (first.x != last.x || first.y != last.y) + d->scanConverter.mergeLine(last, first); + } + subpathStart = i; + last = PointToVector(path.elementAt(i)); + break; + } + case QPainterPath::CurveToElement: + { + QT_FT_Vector p1 = last; + QT_FT_Vector p2 = PointToVector(path.elementAt(i)); + QT_FT_Vector p3 = PointToVector(path.elementAt(++i)); + QT_FT_Vector p4 = PointToVector(path.elementAt(++i)); + d->scanConverter.mergeCurve(p1, p2, p3, p4); + last = p4; + break; + } + default: + Q_ASSERT(false); + break; + } + } + + QT_FT_Vector first = PointToVector(path.elementAt(subpathStart)); + + // close path + if (first.x != last.x || first.y != last.y) + d->scanConverter.mergeLine(last, first); + + d->scanConverter.end(); +} + +QT_END_NAMESPACE |