1	/****************************************************************************
2	**
3	** Copyright (C) 2016 The Qt Company Ltd.
4	** Contact: https://www.qt.io/licensing/
5	**
6	** This file is part of the QtGui module of the Qt Toolkit.
7	**
8	** $QT_BEGIN_LICENSE:LGPL$
9	** Commercial License Usage
10	** Licensees holding valid commercial Qt licenses may use this file in
11	** accordance with the commercial license agreement provided with the
12	** Software or, alternatively, in accordance with the terms contained in
13	** a written agreement between you and The Qt Company. For licensing terms
14	** and conditions see https://www.qt.io/terms-conditions. For further
15	** information use the contact form at https://www.qt.io/contact-us.
16	**
17	** GNU Lesser General Public License Usage
18	** Alternatively, this file may be used under the terms of the GNU Lesser
19	** General Public License version 3 as published by the Free Software
20	** Foundation and appearing in the file LICENSE.LGPL3 included in the
21	** packaging of this file. Please review the following information to
22	** ensure the GNU Lesser General Public License version 3 requirements
23	** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24	**
25	** GNU General Public License Usage
26	** Alternatively, this file may be used under the terms of the GNU
27	** General Public License version 2.0 or (at your option) the GNU General
28	** Public license version 3 or any later version approved by the KDE Free
29	** Qt Foundation. The licenses are as published by the Free Software
30	** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31	** included in the packaging of this file. Please review the following
32	** information to ensure the GNU General Public License requirements will
33	** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34	** https://www.gnu.org/licenses/gpl-3.0.html.
35	**
36	** $QT_END_LICENSE$
37	**
38	****************************************************************************/
39
40	#include "qrasterizer_p.h"
41
42	#include <QPoint>
43	#include <QRect>
44
45	#include <private/qmath_p.h>
46	#include <private/qdatabuffer_p.h>
47	#include <private/qdrawhelper_p.h>
48
49	#include <QtGui/qpainterpath.h>
50
51	#include <algorithm>
52
53	QT_BEGIN_NAMESPACE
54
55	typedef int Q16Dot16;
56	#define Q16Dot16ToFloat(i) ((i)/65536.)
57	#define FloatToQ16Dot16(i) (int)((i) * 65536.)
58	#define IntToQ16Dot16(i) ((i) * (1 << 16))
59	#define Q16Dot16ToInt(i) ((i) >> 16)
60	#define Q16Dot16Factor 65536
61
62	#define Q16Dot16Multiply(x, y) (int)((qlonglong(x) * qlonglong(y)) >> 16)
63	#define Q16Dot16FastMultiply(x, y) (((x) * (y)) >> 16)
64
65	#define SPAN_BUFFER_SIZE 256
66
67	#define COORD_ROUNDING 1 // 0: round up, 1: round down
68	#define COORD_OFFSET 32 // 26.6, 32 is half a pixel
69
70	static inline QT_FT_Vector PointToVector(const QPointF &p)
71	{
72	QT_FT_Vector result = { .x: QT_FT_Pos(p.x() * 64), .y: QT_FT_Pos(p.y() * 64) };
73	return result;
74	}
75
76	class QSpanBuffer {
77	public:
78	QSpanBuffer(ProcessSpans blend, void *data, const QRect &clipRect)
79	: m_spanCount(0)
80	, m_blend(blend)
81	, m_data(data)
82	, m_clipRect(clipRect)
83	{
84	}
85
86	~QSpanBuffer()
87	{
88	flushSpans();
89	}
90
91	void addSpan(int x, unsigned int len, int y, unsigned char coverage)
92	{
93	if (!coverage || !len)
94	return;
95
96	Q_ASSERT(y >= m_clipRect.top());
97	Q_ASSERT(y <= m_clipRect.bottom());
98	Q_ASSERT(x >= m_clipRect.left());
99	Q_ASSERT(x + int(len) - 1 <= m_clipRect.right());
100
101	m_spans[m_spanCount].x = x;
102	m_spans[m_spanCount].len = len;
103	m_spans[m_spanCount].y = y;
104	m_spans[m_spanCount].coverage = coverage;
105
106	if (++m_spanCount == SPAN_BUFFER_SIZE)
107	flushSpans();
108	}
109
110	private:
111	void flushSpans()
112	{
113	m_blend(m_spanCount, m_spans, m_data);
114	m_spanCount = 0;
115	}
116
117	QT_FT_Span m_spans[SPAN_BUFFER_SIZE];
118	int m_spanCount;
119
120	ProcessSpans m_blend;
121	void *m_data;
122
123	QRect m_clipRect;
124	};
125
126	#define CHUNK_SIZE 64
127	class QScanConverter
128	{
129	public:
130	QScanConverter();
131	~QScanConverter();
132
133	void begin(int top, int bottom, int left, int right,
134	Qt::FillRule fillRule, bool legacyRounding, QSpanBuffer *spanBuffer);
135	void end();
136
137	void mergeCurve(const QT_FT_Vector &a, const QT_FT_Vector &b,
138	const QT_FT_Vector &c, const QT_FT_Vector &d);
139	void mergeLine(QT_FT_Vector a, QT_FT_Vector b);
140
141	struct Line
142	{
143	Q16Dot16 x;
144	Q16Dot16 delta;
145
146	int top, bottom;
147
148	int winding;
149	};
150
151	private:
152	struct Intersection
153	{
154	int x;
155	int winding;
156
157	int left, right;
158	};
159
160	inline bool clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding);
161	inline void mergeIntersection(Intersection *head, const Intersection &isect);
162
163	void prepareChunk();
164
165	void emitNode(const Intersection *node);
166	void emitSpans(int chunk);
167
168	inline void allocate(int size);
169
170	QDataBuffer<Line> m_lines;
171
172	int m_alloc;
173	int m_size;
174
175	int m_top;
176	int m_bottom;
177
178	Q16Dot16 m_leftFP;
179	Q16Dot16 m_rightFP;
180
181	int m_fillRuleMask;
182	bool m_legacyRounding;
183
184	int m_x;
185	int m_y;
186	int m_winding;
187
188	Intersection *m_intersections;
189
190	QSpanBuffer *m_spanBuffer;
191
192	QDataBuffer<Line *> m_active;
193
194	template <typename T>
195	friend void qScanConvert(QScanConverter &d, T allVertical);
196	};
197
198	class QRasterizerPrivate
199	{
200	public:
201	bool antialiased;
202	bool legacyRounding;
203	ProcessSpans blend;
204	void *data;
205	QRect clipRect;
206
207	QScanConverter scanConverter;
208	};
209
210	QScanConverter::QScanConverter()
211	: m_lines(0)
212	, m_alloc(0)
213	, m_size(0)
214	, m_intersections(nullptr)
215	, m_active(0)
216	{
217	}
218
219	QScanConverter::~QScanConverter()
220	{
221	if (m_intersections)
222	free(ptr: m_intersections);
223	}
224
225	void QScanConverter::begin(int top, int bottom, int left, int right,
226	Qt::FillRule fillRule, bool legacyRounding,
227	QSpanBuffer *spanBuffer)
228	{
229	m_top = top;
230	m_bottom = bottom;
231	m_leftFP = IntToQ16Dot16(left);
232	m_rightFP = IntToQ16Dot16(right + 1);
233
234	m_lines.reset();
235
236	m_fillRuleMask = fillRule == Qt::WindingFill ? ~0x0 : 0x1;
237	m_legacyRounding = legacyRounding;
238	m_spanBuffer = spanBuffer;
239	}
240
241	void QScanConverter::prepareChunk()
242	{
243	m_size = CHUNK_SIZE;
244
245	allocate(CHUNK_SIZE);
246	memset(s: m_intersections, c: 0, CHUNK_SIZE * sizeof(Intersection));
247	}
248
249	void QScanConverter::emitNode(const Intersection *node)
250	{
251	tail_call:
252	if (node->left)
253	emitNode(node: node + node->left);
254
255	if (m_winding & m_fillRuleMask)
256	m_spanBuffer->addSpan(x: m_x, len: node->x - m_x, y: m_y, coverage: 0xff);
257
258	m_x = node->x;
259	m_winding += node->winding;
260
261	if (node->right) {
262	node += node->right;
263	goto tail_call;
264	}
265	}
266
267	void QScanConverter::emitSpans(int chunk)
268	{
269	for (int dy = 0; dy < CHUNK_SIZE; ++dy) {
270	m_x = 0;
271	m_y = chunk + dy;
272	m_winding = 0;
273
274	emitNode(node: &m_intersections[dy]);
275	}
276	}
277
278	// split control points b[0] ... b[3] into
279	// left (b[0] ... b[3]) and right (b[3] ... b[6])
280	static void split(QT_FT_Vector *b)
281	{
282	b[6] = b[3];
283
284	{
285	const QT_FT_Pos temp = (b[1].x + b[2].x)/2;
286
287	b[1].x = (b[0].x + b[1].x)/2;
288	b[5].x = (b[2].x + b[3].x)/2;
289	b[2].x = (b[1].x + temp)/2;
290	b[4].x = (b[5].x + temp)/2;
291	b[3].x = (b[2].x + b[4].x)/2;
292	}
293	{
294	const QT_FT_Pos temp = (b[1].y + b[2].y)/2;
295
296	b[1].y = (b[0].y + b[1].y)/2;
297	b[5].y = (b[2].y + b[3].y)/2;
298	b[2].y = (b[1].y + temp)/2;
299	b[4].y = (b[5].y + temp)/2;
300	b[3].y = (b[2].y + b[4].y)/2;
301	}
302	}
303
304	static inline bool topOrder(const QScanConverter::Line &a, const QScanConverter::Line &b)
305	{
306	return a.top < b.top;
307	}
308
309	static inline bool xOrder(const QScanConverter::Line *a, const QScanConverter::Line *b)
310	{
311	return a->x < b->x;
312	}
313
314	template <bool B>
315	struct QBoolToType
316	{
317	inline bool operator()() const
318	{
319	return B;
320	}
321	};
322
323	// should be a member function but VC6 doesn't support member template functions
324	template <typename T>
325	void qScanConvert(QScanConverter &d, T allVertical)
326	{
327	if (!d.m_lines.size()) {
328	d.m_active.reset();
329	return;
330	}
331	std::sort(first: d.m_lines.data(), last: d.m_lines.data() + d.m_lines.size(), QT_PREPEND_NAMESPACE(topOrder));
332	int line = 0;
333	for (int y = d.m_lines.first().top; y <= d.m_bottom; ++y) {
334	for (; line < d.m_lines.size() && d.m_lines.at(i: line).top == y; ++line) {
335	// add node to active list
336	if (allVertical()) {
337	QScanConverter::Line *l = &d.m_lines.at(i: line);
338	d.m_active.resize(size: d.m_active.size() + 1);
339	int j;
340	for (j = d.m_active.size() - 2; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(a: l, b: d.m_active.at(i: j)); --j)
341	d.m_active.at(i: j+1) = d.m_active.at(i: j);
342	d.m_active.at(i: j+1) = l;
343	} else {
344	d.m_active << &d.m_lines.at(i: line);
345	}
346	}
347
348	int numActive = d.m_active.size();
349	if (!allVertical()) {
350	// use insertion sort instead of qSort, as the active edge list is quite small
351	// and in the average case already sorted
352	for (int i = 1; i < numActive; ++i) {
353	QScanConverter::Line *l = d.m_active.at(i);
354	int j;
355	for (j = i-1; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(a: l, b: d.m_active.at(i: j)); --j)
356	d.m_active.at(i: j+1) = d.m_active.at(i: j);
357	d.m_active.at(i: j+1) = l;
358	}
359	}
360
361	int x = 0;
362	int winding = 0;
363	for (int i = 0; i < numActive; ++i) {
364	QScanConverter::Line *node = d.m_active.at(i);
365
366	const int current = Q16Dot16ToInt(node->x);
367	if (winding & d.m_fillRuleMask)
368	d.m_spanBuffer->addSpan(x, len: current - x, y, coverage: 0xff);
369
370	x = current;
371	winding += node->winding;
372
373	if (node->bottom == y) {
374	// remove node from active list
375	for (int j = i; j < numActive - 1; ++j)
376	d.m_active.at(i: j) = d.m_active.at(i: j+1);
377
378	d.m_active.resize(size: --numActive);
379	--i;
380	} else if (!allVertical())
381	node->x += node->delta;
382	}
383	}
384	d.m_active.reset();
385	}
386
387	void QScanConverter::end()
388	{
389	if (m_lines.isEmpty())
390	return;
391
392	if (m_lines.size() <= 32) {
393	bool allVertical = true;
394	for (int i = 0; i < m_lines.size(); ++i) {
395	if (m_lines.at(i).delta) {
396	allVertical = false;
397	break;
398	}
399	}
400	if (allVertical)
401	qScanConvert(d&: *this, allVertical: QBoolToType<true>());
402	else
403	qScanConvert(d&: *this, allVertical: QBoolToType<false>());
404	} else {
405	for (int chunkTop = m_top; chunkTop <= m_bottom; chunkTop += CHUNK_SIZE) {
406	prepareChunk();
407
408	Intersection isect = { .x: 0, .winding: 0, .left: 0, .right: 0 };
409
410	const int chunkBottom = chunkTop + CHUNK_SIZE;
411	for (int i = 0; i < m_lines.size(); ++i) {
412	Line &line = m_lines.at(i);
413
414	if ((line.bottom < chunkTop) || (line.top > chunkBottom))
415	continue;
416
417	const int top = qMax(a: 0, b: line.top - chunkTop);
418	const int bottom = qMin(CHUNK_SIZE, b: line.bottom + 1 - chunkTop);
419	allocate(size: m_size + bottom - top);
420
421	isect.winding = line.winding;
422
423	Intersection *it = m_intersections + top;
424	Intersection *end = m_intersections + bottom;
425
426	if (line.delta) {
427	for (; it != end; ++it) {
428	isect.x = Q16Dot16ToInt(line.x);
429	line.x += line.delta;
430	mergeIntersection(head: it, isect);
431	}
432	} else {
433	isect.x = Q16Dot16ToInt(line.x);
434	for (; it != end; ++it)
435	mergeIntersection(head: it, isect);
436	}
437	}
438
439	emitSpans(chunk: chunkTop);
440	}
441	}
442
443	if (m_alloc > 1024) {
444	free(ptr: m_intersections);
445	m_alloc = 0;
446	m_size = 0;
447	m_intersections = nullptr;
448	}
449
450	if (m_lines.size() > 1024)
451	m_lines.shrink(size: 1024);
452	}
453
454	inline void QScanConverter::allocate(int size)
455	{
456	if (m_alloc < size) {
457	int newAlloc = qMax(a: size, b: 2 * m_alloc);
458	m_intersections = q_check_ptr(p: (Intersection *)realloc(ptr: m_intersections, size: newAlloc * sizeof(Intersection)));
459	m_alloc = newAlloc;
460	}
461	}
462
463	inline void QScanConverter::mergeIntersection(Intersection *it, const Intersection &isect)
464	{
465	Intersection *current = it;
466
467	while (isect.x != current->x) {
468	int &next = isect.x < current->x ? current->left : current->right;
469	if (next)
470	current += next;
471	else {
472	Intersection *last = m_intersections + m_size;
473	next = last - current;
474	*last = isect;
475	++m_size;
476	return;
477	}
478	}
479
480	current->winding += isect.winding;
481	}
482
483	void QScanConverter::mergeCurve(const QT_FT_Vector &pa, const QT_FT_Vector &pb,
484	const QT_FT_Vector &pc, const QT_FT_Vector &pd)
485	{
486	// make room for 32 splits
487	QT_FT_Vector beziers[4 + 3 * 32];
488
489	QT_FT_Vector *b = beziers;
490
491	b[0] = pa;
492	b[1] = pb;
493	b[2] = pc;
494	b[3] = pd;
495
496	const QT_FT_Pos flatness = 16;
497
498	while (b >= beziers) {
499	QT_FT_Vector delta = { .x: b[3].x - b[0].x, .y: b[3].y - b[0].y };
500	QT_FT_Pos l = qAbs(t: delta.x) + qAbs(t: delta.y);
501
502	bool belowThreshold;
503	if (l > 64) {
504	qlonglong d2 = qAbs(t: qlonglong(b[1].x-b[0].x) * qlonglong(delta.y) -
505	qlonglong(b[1].y-b[0].y) * qlonglong(delta.x));
506	qlonglong d3 = qAbs(t: qlonglong(b[2].x-b[0].x) * qlonglong(delta.y) -
507	qlonglong(b[2].y-b[0].y) * qlonglong(delta.x));
508
509	qlonglong d = d2 + d3;
510
511	belowThreshold = (d <= qlonglong(flatness) * qlonglong(l));
512	} else {
513	QT_FT_Pos d = qAbs(t: b[0].x-b[1].x) + qAbs(t: b[0].y-b[1].y) +
514	qAbs(t: b[0].x-b[2].x) + qAbs(t: b[0].y-b[2].y);
515
516	belowThreshold = (d <= flatness);
517	}
518
519	if (belowThreshold || b == beziers + 3 * 32) {
520	mergeLine(a: b[0], b: b[3]);
521	b -= 3;
522	continue;
523	}
524
525	split(b);
526	b += 3;
527	}
528	}
529
530	inline bool QScanConverter::clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding)
531	{
532	bool right = edgeFP == m_rightFP;
533
534	if (xFP == edgeFP) {
535	if ((slopeFP > 0) ^ right)
536	return false;
537	else {
538	Line line = { .x: edgeFP, .delta: 0, .top: iTop, .bottom: iBottom, .winding: winding };
539	m_lines.add(t: line);
540	return true;
541	}
542	}
543
544	Q16Dot16 lastFP = xFP + slopeFP * (iBottom - iTop);
545
546	if (lastFP == edgeFP) {
547	if ((slopeFP < 0) ^ right)
548	return false;
549	else {
550	Line line = { .x: edgeFP, .delta: 0, .top: iTop, .bottom: iBottom, .winding: winding };
551	m_lines.add(t: line);
552	return true;
553	}
554	}
555
556	// does line cross edge?
557	if ((lastFP < edgeFP) ^ (xFP < edgeFP)) {
558	Q16Dot16 deltaY = Q16Dot16((edgeFP - xFP) / Q16Dot16ToFloat(slopeFP));
559
560	if ((xFP < edgeFP) ^ right) {
561	// top segment needs to be clipped
562	int iHeight = Q16Dot16ToInt(deltaY + 1);
563	int iMiddle = iTop + iHeight;
564
565	Line line = { .x: edgeFP, .delta: 0, .top: iTop, .bottom: iMiddle, .winding: winding };
566	m_lines.add(t: line);
567
568	if (iMiddle != iBottom) {
569	xFP += slopeFP * (iHeight + 1);
570	iTop = iMiddle + 1;
571	} else
572	return true;
573	} else {
574	// bottom segment needs to be clipped
575	int iHeight = Q16Dot16ToInt(deltaY);
576	int iMiddle = iTop + iHeight;
577
578	if (iMiddle != iBottom) {
579	Line line = { .x: edgeFP, .delta: 0, .top: iMiddle + 1, .bottom: iBottom, .winding: winding };
580	m_lines.add(t: line);
581
582	iBottom = iMiddle;
583	}
584	}
585	return false;
586	} else if ((xFP < edgeFP) ^ right) {
587	Line line = { .x: edgeFP, .delta: 0, .top: iTop, .bottom: iBottom, .winding: winding };
588	m_lines.add(t: line);
589	return true;
590	}
591
592	return false;
593	}
594
595	void QScanConverter::mergeLine(QT_FT_Vector a, QT_FT_Vector b)
596	{
597	int winding = 1;
598
599	if (a.y > b.y) {
600	qSwap(value1&: a, value2&: b);
601	winding = -1;
602	}
603
604	if (m_legacyRounding) {
605	a.x += COORD_OFFSET;
606	a.y += COORD_OFFSET;
607	b.x += COORD_OFFSET;
608	b.y += COORD_OFFSET;
609	}
610
611	int rounding = m_legacyRounding ? COORD_ROUNDING : 0;
612
613	int iTop = qMax(a: m_top, b: int((a.y + 32 - rounding) >> 6));
614	int iBottom = qMin(a: m_bottom, b: int((b.y - 32 - rounding) >> 6));
615
616	if (iTop <= iBottom) {
617	Q16Dot16 aFP = Q16Dot16Factor/2 + (a.x * (1 << 10)) - rounding;
618
619	if (b.x == a.x) {
620	Line line = { .x: qBound(min: m_leftFP, val: aFP, max: m_rightFP), .delta: 0, .top: iTop, .bottom: iBottom, .winding: winding };
621	m_lines.add(t: line);
622	} else {
623	const qreal slope = (b.x - a.x) / qreal(b.y - a.y);
624
625	const Q16Dot16 slopeFP = FloatToQ16Dot16(slope);
626
627	Q16Dot16 xFP = aFP + Q16Dot16Multiply(slopeFP,
628	IntToQ16Dot16(iTop)
629	+ Q16Dot16Factor/2 - (a.y * (1 << 10)));
630
631	if (clip(xFP, iTop, iBottom, slopeFP, edgeFP: m_leftFP, winding))
632	return;
633
634	if (clip(xFP, iTop, iBottom, slopeFP, edgeFP: m_rightFP, winding))
635	return;
636
637	Q_ASSERT(xFP >= m_leftFP);
638
639	Line line = { .x: xFP, .delta: slopeFP, .top: iTop, .bottom: iBottom, .winding: winding };
640	m_lines.add(t: line);
641	}
642	}
643	}
644
645	QRasterizer::QRasterizer()
646	: d(new QRasterizerPrivate)
647	{
648	d->legacyRounding = false;
649	}
650
651	QRasterizer::~QRasterizer()
652	{
653	delete d;
654	}
655
656	void QRasterizer::setAntialiased(bool antialiased)
657	{
658	d->antialiased = antialiased;
659	}
660
661	void QRasterizer::initialize(ProcessSpans blend, void *data)
662	{
663	d->blend = blend;
664	d->data = data;
665	}
666
667	void QRasterizer::setClipRect(const QRect &clipRect)
668	{
669	d->clipRect = clipRect;
670	}
671
672	void QRasterizer::setLegacyRoundingEnabled(bool legacyRoundingEnabled)
673	{
674	d->legacyRounding = legacyRoundingEnabled;
675	}
676
677	static Q16Dot16 intersectPixelFP(int x, Q16Dot16 top, Q16Dot16 bottom, Q16Dot16 leftIntersectX, Q16Dot16 rightIntersectX, Q16Dot16 slope, Q16Dot16 invSlope)
678	{
679	Q16Dot16 leftX = IntToQ16Dot16(x);
680	Q16Dot16 rightX = IntToQ16Dot16(x) + Q16Dot16Factor;
681
682	Q16Dot16 leftIntersectY, rightIntersectY;
683	if (slope > 0) {
684	leftIntersectY = top + Q16Dot16Multiply(leftX - leftIntersectX, invSlope);
685	rightIntersectY = leftIntersectY + invSlope;
686	} else {
687	leftIntersectY = top + Q16Dot16Multiply(leftX - rightIntersectX, invSlope);
688	rightIntersectY = leftIntersectY + invSlope;
689	}
690
691	if (leftIntersectX >= leftX && rightIntersectX <= rightX) {
692	return Q16Dot16Multiply(bottom - top, leftIntersectX - leftX + ((rightIntersectX - leftIntersectX) >> 1));
693	} else if (leftIntersectX >= rightX) {
694	return bottom - top;
695	} else if (leftIntersectX >= leftX) {
696	if (slope > 0) {
697	return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, rightIntersectY - top);
698	} else {
699	return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, bottom - rightIntersectY);
700	}
701	} else if (rightIntersectX <= leftX) {
702	return 0;
703	} else if (rightIntersectX <= rightX) {
704	if (slope > 0) {
705	return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, bottom - leftIntersectY);
706	} else {
707	return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, leftIntersectY - top);
708	}
709	} else {
710	if (slope > 0) {
711	return (bottom - rightIntersectY) + ((rightIntersectY - leftIntersectY) >> 1);
712	} else {
713	return (rightIntersectY - top) + ((leftIntersectY - rightIntersectY) >> 1);
714	}
715	}
716	}
717
718	static inline bool q26Dot6Compare(qreal p1, qreal p2)
719	{
720	return int((p2 - p1) * 64.) == 0;
721	}
722
723	static inline QPointF snapTo26Dot6Grid(const QPointF &p)
724	{
725	return QPointF(std::floor(x: p.x() * 64) * (1 / qreal(64)),
726	std::floor(x: p.y() * 64) * (1 / qreal(64)));
727	}
728
729	/*
730	The rasterize line function relies on some div by zero which should
731	result in +/-inf values. However, when floating point exceptions are
732	enabled, this will cause crashes, so we return high numbers instead.
733	As the returned value is used in further arithmetic, returning
734	FLT_MAX/DBL_MAX will also cause values, so instead return a value
735	that is well outside the int-range.
736	*/
737	static inline qreal qSafeDivide(qreal x, qreal y)
738	{
739	if (y == 0)
740	return x > 0 ? 1e20 : -1e20;
741	return x / y;
742	}
743
744	/* Conversion to int fails if the value is too large to fit into INT_MAX or
745	too small to fit into INT_MIN, so we need this slightly safer conversion
746	when floating point exceptions are enabled
747	*/
748	static inline int qSafeFloatToQ16Dot16(qreal x)
749	{
750	qreal tmp = x * 65536.;
751	if (tmp > qreal(INT_MAX))
752	return INT_MAX;
753	else if (tmp < qreal(INT_MIN))
754	return -INT_MAX;
755	return int(tmp);
756	}
757
758	void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap)
759	{
760	if (a == b || !(width > 0.0) || d->clipRect.isEmpty())
761	return;
762
763	QPointF pa = a;
764	QPointF pb = b;
765
766	if (squareCap) {
767	QPointF delta = pb - pa;
768	pa -= (0.5f * width) * delta;
769	pb += (0.5f * width) * delta;
770	}
771
772	QPointF offs = QPointF(qAbs(t: b.y() - a.y()), qAbs(t: b.x() - a.x())) * width * 0.5;
773	const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs);
774
775	if (!clip.contains(p: pa) || !clip.contains(p: pb)) {
776	qreal t1 = 0;
777	qreal t2 = 1;
778
779	const qreal o[2] = { pa.x(), pa.y() };
780	const qreal d[2] = { pb.x() - pa.x(), pb.y() - pa.y() };
781
782	const qreal low[2] = { clip.left(), clip.top() };
783	const qreal high[2] = { clip.right(), clip.bottom() };
784
785	for (int i = 0; i < 2; ++i) {
786	if (d[i] == 0) {
787	if (o[i] <= low[i] || o[i] >= high[i])
788	return;
789	continue;
790	}
791	const qreal d_inv = 1 / d[i];
792	qreal t_low = (low[i] - o[i]) * d_inv;
793	qreal t_high = (high[i] - o[i]) * d_inv;
794	if (t_low > t_high)
795	qSwap(value1&: t_low, value2&: t_high);
796	if (t1 < t_low)
797	t1 = t_low;
798	if (t2 > t_high)
799	t2 = t_high;
800	if (t1 >= t2)
801	return;
802	}
803
804	QPointF npa = pa + (pb - pa) * t1;
805	QPointF npb = pa + (pb - pa) * t2;
806
807	pa = npa;
808	pb = npb;
809	}
810
811	if (!d->antialiased && d->legacyRounding) {
812	pa.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
813	pa.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
814	pb.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
815	pb.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
816	}
817
818	{
819	// old delta
820	const QPointF d0 = a - b;
821	const qreal w0 = d0.x() * d0.x() + d0.y() * d0.y();
822
823	// new delta
824	const QPointF d = pa - pb;
825	const qreal w = d.x() * d.x() + d.y() * d.y();
826
827	if (w == 0)
828	return;
829
830	// adjust width which is given relative to |b - a|
831	width *= qSqrt(v: w0 / w);
832	}
833
834	QSpanBuffer buffer(d->blend, d->data, d->clipRect);
835
836	if (q26Dot6Compare(p1: pa.y(), p2: pb.y())) {
837	const qreal x = (pa.x() + pb.x()) * 0.5f;
838	const qreal dx = qAbs(t: pb.x() - pa.x()) * 0.5f;
839
840	const qreal y = pa.y();
841	const qreal dy = width * dx;
842
843	pa = QPointF(x, y - dy);
844	pb = QPointF(x, y + dy);
845
846	width = 1 / width;
847	}
848
849	if (q26Dot6Compare(p1: pa.x(), p2: pb.x())) {
850	if (pa.y() > pb.y())
851	qSwap(value1&: pa, value2&: pb);
852
853	const qreal dy = pb.y() - pa.y();
854	const qreal halfWidth = 0.5f * width * dy;
855
856	qreal left = pa.x() - halfWidth;
857	qreal right = pa.x() + halfWidth;
858
859	left = qBound(min: qreal(d->clipRect.left()), val: left, max: qreal(d->clipRect.right() + 1));
860	right = qBound(min: qreal(d->clipRect.left()), val: right, max: qreal(d->clipRect.right() + 1));
861
862	pa.ry() = qBound(min: qreal(d->clipRect.top()), val: pa.y(), max: qreal(d->clipRect.bottom() + 1));
863	pb.ry() = qBound(min: qreal(d->clipRect.top()), val: pb.y(), max: qreal(d->clipRect.bottom() + 1));
864
865	if (q26Dot6Compare(p1: left, p2: right) || q26Dot6Compare(p1: pa.y(), p2: pb.y()))
866	return;
867
868	if (d->antialiased) {
869	const Q16Dot16 iLeft = int(left);
870	const Q16Dot16 iRight = int(right);
871	const Q16Dot16 leftWidth = IntToQ16Dot16(iLeft + 1)
872	- qSafeFloatToQ16Dot16(x: left);
873	const Q16Dot16 rightWidth = qSafeFloatToQ16Dot16(x: right)
874	- IntToQ16Dot16(iRight);
875
876	Q16Dot16 coverage[3];
877	int x[3];
878	int len[3];
879
880	int n = 1;
881	if (iLeft == iRight) {
882	coverage[0] = (leftWidth + rightWidth) * 255;
883	x[0] = iLeft;
884	len[0] = 1;
885	} else {
886	coverage[0] = leftWidth * 255;
887	x[0] = iLeft;
888	len[0] = 1;
889	if (leftWidth == Q16Dot16Factor) {
890	len[0] = iRight - iLeft;
891	} else if (iRight - iLeft > 1) {
892	coverage[1] = IntToQ16Dot16(255);
893	x[1] = iLeft + 1;
894	len[1] = iRight - iLeft - 1;
895	++n;
896	}
897	if (rightWidth) {
898	coverage[n] = rightWidth * 255;
899	x[n] = iRight;
900	len[n] = 1;
901	++n;
902	}
903	}
904
905	const Q16Dot16 iTopFP = IntToQ16Dot16(int(pa.y()));
906	const Q16Dot16 iBottomFP = IntToQ16Dot16(int(pb.y()));
907	const Q16Dot16 yPa = qSafeFloatToQ16Dot16(x: pa.y());
908	const Q16Dot16 yPb = qSafeFloatToQ16Dot16(x: pb.y());
909	for (Q16Dot16 yFP = iTopFP; yFP <= iBottomFP; yFP += Q16Dot16Factor) {
910	const Q16Dot16 rowHeight = qMin(a: yFP + Q16Dot16Factor, b: yPb)
911	- qMax(a: yFP, b: yPa);
912	const int y = Q16Dot16ToInt(yFP);
913	if (y > d->clipRect.bottom())
914	break;
915	for (int i = 0; i < n; ++i) {
916	buffer.addSpan(x: x[i], len: len[i], y,
917	Q16Dot16ToInt(Q16Dot16Multiply(rowHeight, coverage[i])));
918	}
919	}
920	} else { // aliased
921	int iTop = int(pa.y() + 0.5f);
922	int iBottom = pb.y() < 0.5f ? -1 : int(pb.y() - 0.5f);
923	int iLeft = int(left + 0.5f);
924	int iRight = right < 0.5f ? -1 : int(right - 0.5f);
925
926	int iWidth = iRight - iLeft + 1;
927	for (int y = iTop; y <= iBottom; ++y)
928	buffer.addSpan(x: iLeft, len: iWidth, y, coverage: 255);
929	}
930	} else {
931	if (pa.y() > pb.y())
932	qSwap(value1&: pa, value2&: pb);
933
934	QPointF delta = pb - pa;
935	delta *= 0.5f * width;
936	const QPointF perp(delta.y(), -delta.x());
937
938	QPointF top;
939	QPointF left;
940	QPointF right;
941	QPointF bottom;
942
943	if (pa.x() < pb.x()) {
944	top = pa + perp;
945	left = pa - perp;
946	right = pb + perp;
947	bottom = pb - perp;
948	} else {
949	top = pa - perp;
950	left = pb - perp;
951	right = pa + perp;
952	bottom = pb + perp;
953	}
954
955	top = snapTo26Dot6Grid(p: top);
956	bottom = snapTo26Dot6Grid(p: bottom);
957	left = snapTo26Dot6Grid(p: left);
958	right = snapTo26Dot6Grid(p: right);
959
960	const qreal topBound = qBound(min: qreal(d->clipRect.top()), val: top.y(), max: qreal(d->clipRect.bottom()));
961	const qreal bottomBound = qBound(min: qreal(d->clipRect.top()), val: bottom.y(), max: qreal(d->clipRect.bottom()));
962
963	const QPointF topLeftEdge = left - top;
964	const QPointF topRightEdge = right - top;
965	const QPointF bottomLeftEdge = bottom - left;
966	const QPointF bottomRightEdge = bottom - right;
967
968	const qreal topLeftSlope = qSafeDivide(x: topLeftEdge.x(), y: topLeftEdge.y());
969	const qreal bottomLeftSlope = qSafeDivide(x: bottomLeftEdge.x(), y: bottomLeftEdge.y());
970
971	const qreal topRightSlope = qSafeDivide(x: topRightEdge.x(), y: topRightEdge.y());
972	const qreal bottomRightSlope = qSafeDivide(x: bottomRightEdge.x(), y: bottomRightEdge.y());
973
974	const Q16Dot16 topLeftSlopeFP = qSafeFloatToQ16Dot16(x: topLeftSlope);
975	const Q16Dot16 topRightSlopeFP = qSafeFloatToQ16Dot16(x: topRightSlope);
976
977	const Q16Dot16 bottomLeftSlopeFP = qSafeFloatToQ16Dot16(x: bottomLeftSlope);
978	const Q16Dot16 bottomRightSlopeFP = qSafeFloatToQ16Dot16(x: bottomRightSlope);
979
980	const Q16Dot16 invTopLeftSlopeFP = qSafeFloatToQ16Dot16(x: qSafeDivide(x: 1, y: topLeftSlope));
981	const Q16Dot16 invTopRightSlopeFP = qSafeFloatToQ16Dot16(x: qSafeDivide(x: 1, y: topRightSlope));
982
983	const Q16Dot16 invBottomLeftSlopeFP = qSafeFloatToQ16Dot16(x: qSafeDivide(x: 1, y: bottomLeftSlope));
984	const Q16Dot16 invBottomRightSlopeFP = qSafeFloatToQ16Dot16(x: qSafeDivide(x: 1, y: bottomRightSlope));
985
986	if (d->antialiased) {
987	const Q16Dot16 iTopFP = IntToQ16Dot16(int(topBound));
988	const Q16Dot16 iLeftFP = IntToQ16Dot16(int(left.y()));
989	const Q16Dot16 iRightFP = IntToQ16Dot16(int(right.y()));
990	const Q16Dot16 iBottomFP = IntToQ16Dot16(int(bottomBound));
991
992	Q16Dot16 leftIntersectAf = qSafeFloatToQ16Dot16(x: top.x() + (int(topBound) - top.y()) * topLeftSlope);
993	Q16Dot16 rightIntersectAf = qSafeFloatToQ16Dot16(x: top.x() + (int(topBound) - top.y()) * topRightSlope);
994	Q16Dot16 leftIntersectBf = 0;
995	Q16Dot16 rightIntersectBf = 0;
996
997	if (iLeftFP < iTopFP)
998	leftIntersectBf = qSafeFloatToQ16Dot16(x: left.x() + (int(topBound) - left.y()) * bottomLeftSlope);
999
1000	if (iRightFP < iTopFP)
1001	rightIntersectBf = qSafeFloatToQ16Dot16(x: right.x() + (int(topBound) - right.y()) * bottomRightSlope);
1002
1003	Q16Dot16 rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom;
1004	Q16Dot16 topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf;
1005	Q16Dot16 bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf;
1006
1007	int leftMin, leftMax, rightMin, rightMax;
1008
1009	const Q16Dot16 yTopFP = qSafeFloatToQ16Dot16(x: top.y());
1010	const Q16Dot16 yLeftFP = qSafeFloatToQ16Dot16(x: left.y());
1011	const Q16Dot16 yRightFP = qSafeFloatToQ16Dot16(x: right.y());
1012	const Q16Dot16 yBottomFP = qSafeFloatToQ16Dot16(x: bottom.y());
1013
1014	rowTop = qMax(a: iTopFP, b: yTopFP);
1015	topLeftIntersectAf = leftIntersectAf +
1016	Q16Dot16Multiply(topLeftSlopeFP, rowTop - iTopFP);
1017	topRightIntersectAf = rightIntersectAf +
1018	Q16Dot16Multiply(topRightSlopeFP, rowTop - iTopFP);
1019
1020	Q16Dot16 yFP = iTopFP;
1021	while (yFP <= iBottomFP) {
1022	rowBottomLeft = qMin(a: yFP + Q16Dot16Factor, b: yLeftFP);
1023	rowBottomRight = qMin(a: yFP + Q16Dot16Factor, b: yRightFP);
1024	rowTopLeft = qMax(a: yFP, b: yLeftFP);
1025	rowTopRight = qMax(a: yFP, b: yRightFP);
1026	rowBottom = qMin(a: yFP + Q16Dot16Factor, b: yBottomFP);
1027
1028	if (yFP == iLeftFP) {
1029	const int y = Q16Dot16ToInt(yFP);
1030	leftIntersectBf = qSafeFloatToQ16Dot16(x: left.x() + (y - left.y()) * bottomLeftSlope);
1031	topLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(bottomLeftSlopeFP, rowTopLeft - yFP);
1032	bottomLeftIntersectAf = leftIntersectAf + Q16Dot16Multiply(topLeftSlopeFP, rowBottomLeft - yFP);
1033	} else {
1034	topLeftIntersectBf = leftIntersectBf;
1035	bottomLeftIntersectAf = leftIntersectAf + topLeftSlopeFP;
1036	}
1037
1038	if (yFP == iRightFP) {
1039	const int y = Q16Dot16ToInt(yFP);
1040	rightIntersectBf = qSafeFloatToQ16Dot16(x: right.x() + (y - right.y()) * bottomRightSlope);
1041	topRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(bottomRightSlopeFP, rowTopRight - yFP);
1042	bottomRightIntersectAf = rightIntersectAf + Q16Dot16Multiply(topRightSlopeFP, rowBottomRight - yFP);
1043	} else {
1044	topRightIntersectBf = rightIntersectBf;
1045	bottomRightIntersectAf = rightIntersectAf + topRightSlopeFP;
1046	}
1047
1048	if (yFP == iBottomFP) {
1049	bottomLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(bottomLeftSlopeFP, rowBottom - yFP);
1050	bottomRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(bottomRightSlopeFP, rowBottom - yFP);
1051	} else {
1052	bottomLeftIntersectBf = leftIntersectBf + bottomLeftSlopeFP;
1053	bottomRightIntersectBf = rightIntersectBf + bottomRightSlopeFP;
1054	}
1055
1056	if (yFP < iLeftFP) {
1057	leftMin = Q16Dot16ToInt(bottomLeftIntersectAf);
1058	leftMax = Q16Dot16ToInt(topLeftIntersectAf);
1059	} else if (yFP == iLeftFP) {
1060	leftMin = Q16Dot16ToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf));
1061	leftMax = Q16Dot16ToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf));
1062	} else {
1063	leftMin = Q16Dot16ToInt(topLeftIntersectBf);
1064	leftMax = Q16Dot16ToInt(bottomLeftIntersectBf);
1065	}
1066
1067	leftMin = qBound(min: d->clipRect.left(), val: leftMin, max: d->clipRect.right());
1068	leftMax = qBound(min: d->clipRect.left(), val: leftMax, max: d->clipRect.right());
1069
1070	if (yFP < iRightFP) {
1071	rightMin = Q16Dot16ToInt(topRightIntersectAf);
1072	rightMax = Q16Dot16ToInt(bottomRightIntersectAf);
1073	} else if (yFP == iRightFP) {
1074	rightMin = Q16Dot16ToInt(qMin(topRightIntersectAf, bottomRightIntersectBf));
1075	rightMax = Q16Dot16ToInt(qMin(bottomRightIntersectAf, topRightIntersectBf));
1076	} else {
1077	rightMin = Q16Dot16ToInt(bottomRightIntersectBf);
1078	rightMax = Q16Dot16ToInt(topRightIntersectBf);
1079	}
1080
1081	rightMin = qBound(min: d->clipRect.left(), val: rightMin, max: d->clipRect.right());
1082	rightMax = qBound(min: d->clipRect.left(), val: rightMax, max: d->clipRect.right());
1083
1084	if (leftMax > rightMax)
1085	leftMax = rightMax;
1086	if (rightMin < leftMin)
1087	rightMin = leftMin;
1088
1089	Q16Dot16 rowHeight = rowBottom - rowTop;
1090
1091	int x = leftMin;
1092	while (x <= leftMax) {
1093	Q16Dot16 excluded = 0;
1094
1095	if (yFP <= iLeftFP)
1096	excluded += intersectPixelFP(x, top: rowTop, bottom: rowBottomLeft,
1097	leftIntersectX: bottomLeftIntersectAf, rightIntersectX: topLeftIntersectAf,
1098	slope: topLeftSlopeFP, invSlope: invTopLeftSlopeFP);
1099	if (yFP >= iLeftFP)
1100	excluded += intersectPixelFP(x, top: rowTopLeft, bottom: rowBottom,
1101	leftIntersectX: topLeftIntersectBf, rightIntersectX: bottomLeftIntersectBf,
1102	slope: bottomLeftSlopeFP, invSlope: invBottomLeftSlopeFP);
1103
1104	if (x >= rightMin) {
1105	if (yFP <= iRightFP)
1106	excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, top: rowTop, bottom: rowBottomRight,
1107	leftIntersectX: topRightIntersectAf, rightIntersectX: bottomRightIntersectAf,
1108	slope: topRightSlopeFP, invSlope: invTopRightSlopeFP);
1109	if (yFP >= iRightFP)
1110	excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, top: rowTopRight, bottom: rowBottom,
1111	leftIntersectX: bottomRightIntersectBf, rightIntersectX: topRightIntersectBf,
1112	slope: bottomRightSlopeFP, invSlope: invBottomRightSlopeFP);
1113	}
1114
1115	Q16Dot16 coverage = rowHeight - excluded;
1116	buffer.addSpan(x, len: 1, Q16Dot16ToInt(yFP),
1117	Q16Dot16ToInt(255 * coverage));
1118	++x;
1119	}
1120	if (x < rightMin) {
1121	buffer.addSpan(x, len: rightMin - x, Q16Dot16ToInt(yFP),
1122	Q16Dot16ToInt(255 * rowHeight));
1123	x = rightMin;
1124	}
1125	while (x <= rightMax) {
1126	Q16Dot16 excluded = 0;
1127	if (yFP <= iRightFP)
1128	excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, top: rowTop, bottom: rowBottomRight,
1129	leftIntersectX: topRightIntersectAf, rightIntersectX: bottomRightIntersectAf,
1130	slope: topRightSlopeFP, invSlope: invTopRightSlopeFP);
1131	if (yFP >= iRightFP)
1132	excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, top: rowTopRight, bottom: rowBottom,
1133	leftIntersectX: bottomRightIntersectBf, rightIntersectX: topRightIntersectBf,
1134	slope: bottomRightSlopeFP, invSlope: invBottomRightSlopeFP);
1135
1136	Q16Dot16 coverage = rowHeight - excluded;
1137	buffer.addSpan(x, len: 1, Q16Dot16ToInt(yFP),
1138	Q16Dot16ToInt(255 * coverage));
1139	++x;
1140	}
1141
1142	leftIntersectAf += topLeftSlopeFP;
1143	leftIntersectBf += bottomLeftSlopeFP;
1144	rightIntersectAf += topRightSlopeFP;
1145	rightIntersectBf += bottomRightSlopeFP;
1146	topLeftIntersectAf = leftIntersectAf;
1147	topRightIntersectAf = rightIntersectAf;
1148
1149	yFP += Q16Dot16Factor;
1150	rowTop = yFP;
1151	}
1152	} else { // aliased
1153	int iTop = int(top.y() + 0.5f);
1154	int iLeft = left.y() < 0.5f ? -1 : int(left.y() - 0.5f);
1155	int iRight = right.y() < 0.5f ? -1 : int(right.y() - 0.5f);
1156	int iBottom = bottom.y() < 0.5f? -1 : int(bottom.y() - 0.5f);
1157	int iMiddle = qMin(a: iLeft, b: iRight);
1158
1159	Q16Dot16 leftIntersectAf = qSafeFloatToQ16Dot16(x: top.x() + 0.5f + (iTop + 0.5f - top.y()) * topLeftSlope);
1160	Q16Dot16 leftIntersectBf = qSafeFloatToQ16Dot16(x: left.x() + 0.5f + (iLeft + 1.5f - left.y()) * bottomLeftSlope);
1161	Q16Dot16 rightIntersectAf = qSafeFloatToQ16Dot16(x: top.x() - 0.5f + (iTop + 0.5f - top.y()) * topRightSlope);
1162	Q16Dot16 rightIntersectBf = qSafeFloatToQ16Dot16(x: right.x() - 0.5f + (iRight + 1.5f - right.y()) * bottomRightSlope);
1163
1164	int ny;
1165	int y = iTop;
1166	#define DO_SEGMENT(next, li, ri, ls, rs) \
1167	ny = qMin(next + 1, d->clipRect.top()); \
1168	if (y < ny) { \
1169	li += ls * (ny - y); \
1170	ri += rs * (ny - y); \
1171	y = ny; \
1172	} \
1173	if (next > d->clipRect.bottom()) \
1174	next = d->clipRect.bottom(); \
1175	for (; y <= next; ++y) { \
1176	const int x1 = qMax(Q16Dot16ToInt(li), d->clipRect.left()); \
1177	const int x2 = qMin(Q16Dot16ToInt(ri), d->clipRect.right()); \
1178	if (x2 >= x1) \
1179	buffer.addSpan(x1, x2 - x1 + 1, y, 255); \
1180	li += ls; \
1181	ri += rs; \
1182	}
1183
1184	DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, topLeftSlopeFP, topRightSlopeFP)
1185	DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, bottomLeftSlopeFP, topRightSlopeFP)
1186	DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, topLeftSlopeFP, bottomRightSlopeFP);
1187	DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, bottomLeftSlopeFP, bottomRightSlopeFP);
1188	#undef DO_SEGMENT
1189	}
1190	}
1191	}
1192
1193	void QRasterizer::rasterize(const QT_FT_Outline *outline, Qt::FillRule fillRule)
1194	{
1195	if (outline->n_points < 3 || outline->n_contours == 0)
1196	return;
1197
1198	const QT_FT_Vector *points = outline->points;
1199
1200	QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1201
1202	// ### QT_FT_Outline already has a bounding rect which is
1203	// ### precomputed at this point, so we should probably just be
1204	// ### using that instead...
1205	QT_FT_Pos min_y = points[0].y, max_y = points[0].y;
1206	for (int i = 1; i < outline->n_points; ++i) {
1207	const QT_FT_Vector &p = points[i];
1208	min_y = qMin(a: p.y, b: min_y);
1209	max_y = qMax(a: p.y, b: max_y);
1210	}
1211
1212	int rounding = d->legacyRounding ? COORD_OFFSET - COORD_ROUNDING : 0;
1213
1214	int iTopBound = qMax(a: d->clipRect.top(), b: int((min_y + 32 + rounding) >> 6));
1215	int iBottomBound = qMin(a: d->clipRect.bottom(), b: int((max_y - 32 + rounding) >> 6));
1216
1217	if (iTopBound > iBottomBound)
1218	return;
1219
1220	d->scanConverter.begin(top: iTopBound, bottom: iBottomBound, left: d->clipRect.left(), right: d->clipRect.right(), fillRule, legacyRounding: d->legacyRounding, spanBuffer: &buffer);
1221
1222	int first = 0;
1223	for (int i = 0; i < outline->n_contours; ++i) {
1224	const int last = outline->contours[i];
1225	for (int j = first; j < last; ++j) {
1226	if (outline->tags[j+1] == QT_FT_CURVE_TAG_CUBIC) {
1227	Q_ASSERT(outline->tags[j+2] == QT_FT_CURVE_TAG_CUBIC);
1228	d->scanConverter.mergeCurve(pa: points[j], pb: points[j+1], pc: points[j+2], pd: points[j+3]);
1229	j += 2;
1230	} else {
1231	d->scanConverter.mergeLine(a: points[j], b: points[j+1]);
1232	}
1233	}
1234
1235	first = last + 1;
1236	}
1237
1238	d->scanConverter.end();
1239	}
1240
1241	void QRasterizer::rasterize(const QPainterPath &path, Qt::FillRule fillRule)
1242	{
1243	if (path.isEmpty())
1244	return;
1245
1246	QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1247
1248	QRectF bounds = path.controlPointRect();
1249
1250	double rounding = d->legacyRounding ? (COORD_OFFSET - COORD_ROUNDING) / 64. : 0.0;
1251
1252	int iTopBound = qMax(a: d->clipRect.top(), b: int(bounds.top() + 0.5 + rounding));
1253	int iBottomBound = qMin(a: d->clipRect.bottom(), b: int(bounds.bottom() - 0.5 + rounding));
1254
1255	if (iTopBound > iBottomBound)
1256	return;
1257
1258	d->scanConverter.begin(top: iTopBound, bottom: iBottomBound, left: d->clipRect.left(), right: d->clipRect.right(), fillRule, legacyRounding: d->legacyRounding, spanBuffer: &buffer);
1259
1260	int subpathStart = 0;
1261	QT_FT_Vector last = { .x: 0, .y: 0 };
1262	for (int i = 0; i < path.elementCount(); ++i) {
1263	switch (path.elementAt(i).type) {
1264	case QPainterPath::LineToElement:
1265	{
1266	QT_FT_Vector p1 = last;
1267	QT_FT_Vector p2 = PointToVector(p: path.elementAt(i));
1268	d->scanConverter.mergeLine(a: p1, b: p2);
1269	last = p2;
1270	break;
1271	}
1272	case QPainterPath::MoveToElement:
1273	{
1274	if (i != 0) {
1275	QT_FT_Vector first = PointToVector(p: path.elementAt(i: subpathStart));
1276	// close previous subpath
1277	if (first.x != last.x || first.y != last.y)
1278	d->scanConverter.mergeLine(a: last, b: first);
1279	}
1280	subpathStart = i;
1281	last = PointToVector(p: path.elementAt(i));
1282	break;
1283	}
1284	case QPainterPath::CurveToElement:
1285	{
1286	QT_FT_Vector p1 = last;
1287	QT_FT_Vector p2 = PointToVector(p: path.elementAt(i));
1288	QT_FT_Vector p3 = PointToVector(p: path.elementAt(i: ++i));
1289	QT_FT_Vector p4 = PointToVector(p: path.elementAt(i: ++i));
1290	d->scanConverter.mergeCurve(pa: p1, pb: p2, pc: p3, pd: p4);
1291	last = p4;
1292	break;
1293	}
1294	default:
1295	Q_ASSERT(false);
1296	break;
1297	}
1298	}
1299
1300	QT_FT_Vector first = PointToVector(p: path.elementAt(i: subpathStart));
1301
1302	// close path
1303	if (first.x != last.x || first.y != last.y)
1304	d->scanConverter.mergeLine(a: last, b: first);
1305
1306	d->scanConverter.end();
1307	}
1308
1309	QT_END_NAMESPACE
1310