source: trunk/src/gui/painting/qrasterizer.cpp@ 376

Last change on this file since 376 was 2, checked in by Dmitry A. Kuminov, 16 years ago

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