QScanConverter Class Reference

Classes
struct	Intersection
struct	Line

Public Functions
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)
	QScanConverter ()
	~QScanConverter ()

Private Functions
void	allocate (int size)
bool	clip (Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding)
void	emitNode (const Intersection *node)
void	emitSpans (int chunk)
void	mergeIntersection (Intersection *head, const Intersection &isect)
void	prepareChunk ()

Properties
QDataBuffer< Line * >	m_active
int	m_alloc
int	m_bottom
int	m_fillRuleMask
Intersection *	m_intersections
Q16Dot16	m_leftFP
QDataBuffer< Line >	m_lines
Q16Dot16	m_rightFP
int	m_size
QSpanBuffer *	m_spanBuffer
int	m_top
int	m_winding
int	m_x
int	m_y

Friends
template<typename T >
void	qScanConvert (QScanConverter &d, T allVertical)

Detailed Description

Definition at line 125 of file qrasterizer.cpp.

Constructors and Destructors

QScanConverter()

QScanConverter::QScanConverter

(

)

Definition at line 206 of file qrasterizer.cpp.

   : m_lines(0)
   , m_alloc(0)
   , m_size(0)
   , m_intersections(0)
   , m_active(0)
{
}

~QScanConverter()

QScanConverter::~QScanConverter

(

)

Definition at line 215 of file qrasterizer.cpp.

{
    if (m_intersections)
        free(m_intersections);
}

Functions

allocate()

void QScanConverter::allocate ( int  size )

inlineprivate

Definition at line 448 of file qrasterizer.cpp.

Referenced by end(), and prepareChunk().

{
    if (m_alloc < size) {
        int newAlloc = qMax(size, 2 * m_alloc);
        m_intersections = q_check_ptr((Intersection *)realloc(m_intersections, newAlloc * sizeof(Intersection)));
        m_alloc = newAlloc;
    }
}

begin()

void QScanConverter::begin	(	int	top,
		int	bottom,
		int	left,
		int	right,
		Qt::FillRule	fillRule,
		QSpanBuffer *	spanBuffer
	)

Definition at line 221 of file qrasterizer.cpp.

Referenced by QRasterizer::rasterize().

{
    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;
}

clip()

bool QScanConverter::clip ( Q16Dot16 &  xFP, int &  iTop, int &  iBottom, Q16Dot16  slopeFP, Q16Dot16  edgeFP, int  winding  )

inlineprivate

Definition at line 524 of file qrasterizer.cpp.

Referenced by mergeLine().

{
    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;
}

emitNode()

void QScanConverter::emitNode ( const Intersection *  node )

private

Definition at line 243 of file qrasterizer.cpp.

Referenced by emitSpans().

{
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;
    }
}

emitSpans()

void QScanConverter::emitSpans ( int  chunk )

private

Definition at line 261 of file qrasterizer.cpp.

Referenced by end().

{
    for (int dy = 0; dy < CHUNK_SIZE; ++dy) {
        m_x = 0;
        m_y = chunk + dy;
        m_winding = 0;

        emitNode(&m_intersections[dy]);
    }
}

end()

void QScanConverter::end

(

)

Definition at line 381 of file qrasterizer.cpp.

Referenced by QRasterizer::rasterize().

{
    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);
}

mergeCurve()

void QScanConverter::mergeCurve	(	const QT_FT_Vector &	a,
		const QT_FT_Vector &	b,
		const QT_FT_Vector &	c,
		const QT_FT_Vector &	d
	)

Definition at line 477 of file qrasterizer.cpp.

Referenced by QRasterizer::rasterize().

{
    // 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;
    }
}

mergeIntersection()

void QScanConverter::mergeIntersection ( Intersection *  head, const Intersection &  isect  )

inlineprivate

Definition at line 457 of file qrasterizer.cpp.

Referenced by end().

{
    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;
}

mergeLine()

void QScanConverter::mergeLine	(	QT_FT_Vector	a,
		QT_FT_Vector	b
	)

Definition at line 589 of file qrasterizer.cpp.

Referenced by mergeCurve(), and QRasterizer::rasterize().

{
    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);
        }
    }
}

prepareChunk()

void QScanConverter::prepareChunk ( )

private

Definition at line 235 of file qrasterizer.cpp.

Referenced by end().

{
    m_size = CHUNK_SIZE;

    allocate(CHUNK_SIZE);
    memset(m_intersections, 0, CHUNK_SIZE * sizeof(Intersection));
}

Friends and Related Functions

qScanConvert

template<typename T >

void qScanConvert ( QScanConverter &  d, T  allVertical  )

friend

Definition at line 319 of file qrasterizer.cpp.

Referenced by end().

{
    if (!d.m_lines.size()) {
        d.m_active.reset();
        return;
    }
    qSort(d.m_lines.data(), d.m_lines.data() + d.m_lines.size(), QT_PREPEND_NAMESPACE(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 && QT_PREPEND_NAMESPACE(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 && QT_PREPEND_NAMESPACE(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();
}

Properties

m_active

QDataBuffer<Line *> QScanConverter::m_active

private

Definition at line 189 of file qrasterizer.cpp.

Referenced by qScanConvert().

m_alloc

int QScanConverter::m_alloc

private

Definition at line 170 of file qrasterizer.cpp.

Referenced by allocate(), and end().

m_bottom

int QScanConverter::m_bottom

private

Definition at line 174 of file qrasterizer.cpp.

Referenced by begin(), end(), mergeLine(), and qScanConvert().

m_fillRuleMask

int QScanConverter::m_fillRuleMask

private

Definition at line 179 of file qrasterizer.cpp.

Referenced by begin(), emitNode(), and qScanConvert().

m_intersections

Intersection* QScanConverter::m_intersections

private

Definition at line 185 of file qrasterizer.cpp.

Referenced by allocate(), emitSpans(), end(), mergeIntersection(), prepareChunk(), and ~QScanConverter().

m_leftFP

Q16Dot16 QScanConverter::m_leftFP

private

Definition at line 176 of file qrasterizer.cpp.

Referenced by begin(), and mergeLine().

m_lines

QDataBuffer<Line> QScanConverter::m_lines

private

Definition at line 168 of file qrasterizer.cpp.

Referenced by begin(), clip(), end(), mergeLine(), and qScanConvert().

m_rightFP

Q16Dot16 QScanConverter::m_rightFP

private

Definition at line 177 of file qrasterizer.cpp.

Referenced by begin(), clip(), and mergeLine().

m_size

int QScanConverter::m_size

private

Definition at line 171 of file qrasterizer.cpp.

Referenced by end(), mergeIntersection(), and prepareChunk().

m_spanBuffer

QSpanBuffer* QScanConverter::m_spanBuffer

private

Definition at line 187 of file qrasterizer.cpp.

Referenced by begin(), emitNode(), and qScanConvert().

m_top

int QScanConverter::m_top

private

Definition at line 173 of file qrasterizer.cpp.

Referenced by begin(), end(), and mergeLine().

m_winding

int QScanConverter::m_winding

private

Definition at line 183 of file qrasterizer.cpp.

Referenced by emitNode(), and emitSpans().

m_x

int QScanConverter::m_x

private

Definition at line 181 of file qrasterizer.cpp.

Referenced by emitNode(), and emitSpans().

m_y

int QScanConverter::m_y

private

Definition at line 182 of file qrasterizer.cpp.

Referenced by emitNode(), and emitSpans().

---

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

• /src/gui/painting/qrasterizer.cpp