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

Last change on this file since 561 was 561, checked in by Dmitry A. Kuminov, 15 years ago

trunk: Merged in qt 4.6.1 sources.
File size: 41.2 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
4** All rights reserved.
5** Contact: Nokia Corporation (qt-info@nokia.com)
6**
7** This file is part of the QtGui module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial Usage
11** Licensees holding valid Qt Commercial licenses may use this file in
12** accordance with the Qt Commercial License Agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and Nokia.
15**
16** GNU Lesser General Public License Usage
17** Alternatively, this file may be used under the terms of the GNU Lesser
18** General Public License version 2.1 as published by the Free Software
19** Foundation and appearing in the file LICENSE.LGPL included in the
20** packaging of this file. Please review the following information to
21** ensure the GNU Lesser General Public License version 2.1 requirements
22** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
23**
24** In addition, as a special exception, Nokia gives you certain additional
25** rights. These rights are described in the Nokia Qt LGPL Exception
26** version 1.1, included in the file LGPL_EXCEPTION.txt in this 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 have questions regarding the use of this file, please contact
37** Nokia at qt-info@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(), QT_PREPEND_NAMESPACE(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 && QT_PREPEND_NAMESPACE(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 && QT_PREPEND_NAMESPACE(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 int newAlloc = qMax(size, 2 * m_alloc);
440 m_intersections = q_check_ptr((Intersection *)realloc(m_intersections, newAlloc * sizeof(Intersection)));
441 m_alloc = newAlloc;
442 }
443}
444
445inline void QScanConverter::mergeIntersection(Intersection *it, const Intersection &isect)
446{
447 Intersection *current = it;
448
449 while (isect.x != current->x) {
450 int &next = isect.x < current->x ? current->left : current->right;
451 if (next)
452 current += next;
453 else {
454 Intersection *last = m_intersections + m_size;
455 next = last - current;
456 *last = isect;
457 ++m_size;
458 return;
459 }
460 }
461
462 current->winding += isect.winding;
463}
464
465void QScanConverter::mergeCurve(const QT_FT_Vector &pa, const QT_FT_Vector &pb,
466 const QT_FT_Vector &pc, const QT_FT_Vector &pd)
467{
468 // make room for 32 splits
469 QT_FT_Vector beziers[4 + 3 * 32];
470
471 QT_FT_Vector *b = beziers;
472
473 b[0] = pa;
474 b[1] = pb;
475 b[2] = pc;
476 b[3] = pd;
477
478 const QT_FT_Pos flatness = 16;
479
480 while (b >= beziers) {
481 QT_FT_Vector delta = { b[3].x - b[0].x, b[3].y - b[0].y };
482 QT_FT_Pos l = qAbs(delta.x) + qAbs(delta.y);
483
484 bool belowThreshold;
485 if (l > 64) {
486 qlonglong d2 = qAbs(qlonglong(b[1].x-b[0].x) * qlonglong(delta.y) -
487 qlonglong(b[1].y-b[0].y) * qlonglong(delta.x));
488 qlonglong d3 = qAbs(qlonglong(b[2].x-b[0].x) * qlonglong(delta.y) -
489 qlonglong(b[2].y-b[0].y) * qlonglong(delta.x));
490
491 qlonglong d = d2 + d3;
492
493 belowThreshold = (d <= qlonglong(flatness) * qlonglong(l));
494 } else {
495 QT_FT_Pos d = qAbs(b[0].x-b[1].x) + qAbs(b[0].y-b[1].y) +
496 qAbs(b[0].x-b[2].x) + qAbs(b[0].y-b[2].y);
497
498 belowThreshold = (d <= flatness);
499 }
500
501 if (belowThreshold || b == beziers + 3 * 32) {
502 mergeLine(b[0], b[3]);
503 b -= 3;
504 continue;
505 }
506
507 split(b);
508 b += 3;
509 }
510}
511
512inline bool QScanConverter::clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 edgeFP, int winding)
513{
514 bool right = edgeFP == m_rightFP;
515
516 if (xFP == edgeFP) {
517 if ((slopeFP > 0) ^ right)
518 return false;
519 else {
520 Line line = { edgeFP, 0, iTop, iBottom, winding };
521 m_lines.add(line);
522 return true;
523 }
524 }
525
526 Q16Dot16 lastFP = xFP + slopeFP * (iBottom - iTop);
527
528 if (lastFP == edgeFP) {
529 if ((slopeFP < 0) ^ right)
530 return false;
531 else {
532 Line line = { edgeFP, 0, iTop, iBottom, winding };
533 m_lines.add(line);
534 return true;
535 }
536 }
537
538 // does line cross edge?
539 if ((lastFP < edgeFP) ^ (xFP < edgeFP)) {
540 Q16Dot16 deltaY = Q16Dot16((edgeFP - xFP) / Q16Dot16ToFloat(slopeFP));
541
542 if ((xFP < edgeFP) ^ right) {
543 // top segment needs to be clipped
544 int iHeight = Q16Dot16ToInt(deltaY + 1);
545 int iMiddle = iTop + iHeight;
546
547 Line line = { edgeFP, 0, iTop, iMiddle, winding };
548 m_lines.add(line);
549
550 if (iMiddle != iBottom) {
551 xFP += slopeFP * (iHeight + 1);
552 iTop = iMiddle + 1;
553 } else
554 return true;
555 } else {
556 // bottom segment needs to be clipped
557 int iHeight = Q16Dot16ToInt(deltaY);
558 int iMiddle = iTop + iHeight;
559
560 if (iMiddle != iBottom) {
561 Line line = { edgeFP, 0, iMiddle + 1, iBottom, winding };
562 m_lines.add(line);
563
564 iBottom = iMiddle;
565 }
566 }
567 return false;
568 } else if ((xFP < edgeFP) ^ right) {
569 Line line = { edgeFP, 0, iTop, iBottom, winding };
570 m_lines.add(line);
571 return true;
572 }
573
574 return false;
575}
576
577void QScanConverter::mergeLine(QT_FT_Vector a, QT_FT_Vector b)
578{
579 int winding = 1;
580
581 if (a.y > b.y) {
582 qSwap(a, b);
583 winding = -1;
584 }
585
586 a.x += COORD_OFFSET;
587 a.y += COORD_OFFSET;
588 b.x += COORD_OFFSET;
589 b.y += COORD_OFFSET;
590
591 int iTop = qMax(m_top, int((a.y + 32 - COORD_ROUNDING) >> 6));
592 int iBottom = qMin(m_bottom, int((b.y - 32 - COORD_ROUNDING) >> 6));
593
594 if (iTop <= iBottom) {
595 Q16Dot16 aFP = Q16Dot16Factor/2 + (a.x << 10) - COORD_ROUNDING;
596
597 if (b.x == a.x) {
598 Line line = { qBound(m_leftFP, aFP, m_rightFP), 0, iTop, iBottom, winding };
599 m_lines.add(line);
600 } else {
601 const qreal slope = (b.x - a.x) / qreal(b.y - a.y);
602
603 const Q16Dot16 slopeFP = FloatToQ16Dot16(slope);
604
605 Q16Dot16 xFP = aFP + Q16Dot16Multiply(slopeFP,
606 IntToQ16Dot16(iTop)
607 + Q16Dot16Factor/2 - (a.y << 10));
608
609 if (clip(xFP, iTop, iBottom, slopeFP, m_leftFP, winding))
610 return;
611
612 if (clip(xFP, iTop, iBottom, slopeFP, m_rightFP, winding))
613 return;
614
615 Q_ASSERT(xFP >= m_leftFP);
616
617 Line line = { xFP, slopeFP, iTop, iBottom, winding };
618 m_lines.add(line);
619 }
620 }
621}
622
623QRasterizer::QRasterizer()
624 : d(new QRasterizerPrivate)
625{
626}
627
628QRasterizer::~QRasterizer()
629{
630 delete d;
631}
632
633void QRasterizer::setAntialiased(bool antialiased)
634{
635 d->antialiased = antialiased;
636}
637
638void QRasterizer::initialize(ProcessSpans blend, void *data)
639{
640 d->blend = blend;
641 d->data = data;
642}
643
644void QRasterizer::setClipRect(const QRect &clipRect)
645{
646 d->clipRect = clipRect;
647}
648
649static Q16Dot16 intersectPixelFP(int x, Q16Dot16 top, Q16Dot16 bottom, Q16Dot16 leftIntersectX, Q16Dot16 rightIntersectX, Q16Dot16 slope, Q16Dot16 invSlope)
650{
651 Q16Dot16 leftX = IntToQ16Dot16(x);
652 Q16Dot16 rightX = IntToQ16Dot16(x) + Q16Dot16Factor;
653
654 Q16Dot16 leftIntersectY, rightIntersectY;
655 if (slope > 0) {
656 leftIntersectY = top + Q16Dot16Multiply(leftX - leftIntersectX, invSlope);
657 rightIntersectY = leftIntersectY + invSlope;
658 } else {
659 leftIntersectY = top + Q16Dot16Multiply(leftX - rightIntersectX, invSlope);
660 rightIntersectY = leftIntersectY + invSlope;
661 }
662
663 if (leftIntersectX >= leftX && rightIntersectX <= rightX) {
664 return Q16Dot16Multiply(bottom - top, leftIntersectX - leftX + ((rightIntersectX - leftIntersectX) >> 1));
665 } else if (leftIntersectX >= rightX) {
666 return bottom - top;
667 } else if (leftIntersectX >= leftX) {
668 if (slope > 0) {
669 return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, rightIntersectY - top);
670 } else {
671 return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, bottom - rightIntersectY);
672 }
673 } else if (rightIntersectX <= leftX) {
674 return 0;
675 } else if (rightIntersectX <= rightX) {
676 if (slope > 0) {
677 return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, bottom - leftIntersectY);
678 } else {
679 return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, leftIntersectY - top);
680 }
681 } else {
682 if (slope > 0) {
683 return (bottom - rightIntersectY) + ((rightIntersectY - leftIntersectY) >> 1);
684 } else {
685 return (rightIntersectY - top) + ((leftIntersectY - rightIntersectY) >> 1);
686 }
687 }
688}
689
690static inline bool q16Dot16Compare(qreal p1, qreal p2)
691{
692 return FloatToQ16Dot16(p2 - p1) == 0;
693}
694
695static inline qreal qFloorF(qreal v)
696{
697#ifdef QT_USE_MATH_H_FLOATS
698 if (sizeof(qreal) == sizeof(float))
699 return floorf(v);
700 else
701#endif
702 return floor(v);
703}
704
705void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap)
706{
707 if (a == b || width == 0 || d->clipRect.isEmpty())
708 return;
709
710 Q_ASSERT(width > 0.0);
711
712 QPointF pa = a;
713 QPointF pb = b;
714
715 QPointF offs = QPointF(qAbs(b.y() - a.y()), qAbs(b.x() - a.x())) * width * 0.5;
716 if (squareCap)
717 offs += QPointF(offs.y(), offs.x());
718 const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs);
719
720 if (!clip.contains(a) || !clip.contains(b)) {
721 qreal t1 = 0;
722 qreal t2 = 1;
723
724 const qreal o[2] = { a.x(), a.y() };
725 const qreal d[2] = { b.x() - a.x(), b.y() - a.y() };
726
727 const qreal low[2] = { clip.left(), clip.top() };
728 const qreal high[2] = { clip.right(), clip.bottom() };
729
730 for (int i = 0; i < 2; ++i) {
731 if (d[i] == 0) {
732 if (o[i] <= low[i] || o[i] >= high[i])
733 return;
734 continue;
735 }
736 const qreal d_inv = 1 / d[i];
737 qreal t_low = (low[i] - o[i]) * d_inv;
738 qreal t_high = (high[i] - o[i]) * d_inv;
739 if (t_low > t_high)
740 qSwap(t_low, t_high);
741 if (t1 < t_low)
742 t1 = t_low;
743 if (t2 > t_high)
744 t2 = t_high;
745 if (t1 >= t2)
746 return;
747 }
748 pa = a + (b - a) * t1;
749 pb = a + (b - a) * t2;
750 }
751
752 if (!d->antialiased) {
753 pa.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
754 pa.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
755 pb.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
756 pb.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
757 }
758
759 {
760 const qreal gridResolution = 64;
761 const qreal reciprocal = 1 / gridResolution;
762
763 // snap to grid to prevent large slopes
764 pa.rx() = qFloorF(pa.rx() * gridResolution) * reciprocal;
765 pa.ry() = qFloorF(pa.ry() * gridResolution) * reciprocal;
766 pb.rx() = qFloorF(pb.rx() * gridResolution) * reciprocal;
767 pb.ry() = qFloorF(pb.ry() * gridResolution) * reciprocal;
768
769 // old delta
770 const QPointF d0 = a - b;
771 const qreal w0 = d0.x() * d0.x() + d0.y() * d0.y();
772
773 // new delta
774 const QPointF d = pa - pb;
775 const qreal w = d.x() * d.x() + d.y() * d.y();
776
777 if (w == 0)
778 return;
779
780 // adjust width which is given relative to |b - a|
781 width *= sqrt(w0 / w);
782 }
783
784 QSpanBuffer buffer(d->blend, d->data, d->clipRect);
785
786 if (q16Dot16Compare(pa.y(), pb.y())) {
787 const qreal x = (pa.x() + pb.x()) * 0.5f;
788 const qreal dx = qAbs(pb.x() - pa.x()) * 0.5f;
789
790 const qreal y = pa.y();
791 const qreal dy = width * dx;
792
793 pa = QPointF(x, y - dy);
794 pb = QPointF(x, y + dy);
795
796 if (squareCap)
797 width = 1 / width + 1.0f;
798 else
799 width = 1 / width;
800
801 squareCap = false;
802 }
803
804 if (q16Dot16Compare(pa.x(), pb.x())) {
805 if (pa.y() > pb.y())
806 qSwap(pa, pb);
807
808 const qreal dy = pb.y() - pa.y();
809 const qreal halfWidth = 0.5f * width * dy;
810
811 if (squareCap) {
812 pa.ry() -= halfWidth;
813 pb.ry() += halfWidth;
814 }
815
816 qreal left = pa.x() - halfWidth;
817 qreal right = pa.x() + halfWidth;
818
819 left = qBound(qreal(d->clipRect.left()), left, qreal(d->clipRect.right() + 1));
820 right = qBound(qreal(d->clipRect.left()), right, qreal(d->clipRect.right() + 1));
821
822 pa.ry() = qBound(qreal(d->clipRect.top()), pa.y(), qreal(d->clipRect.bottom() + 1));
823 pb.ry() = qBound(qreal(d->clipRect.top()), pb.y(), qreal(d->clipRect.bottom() + 1));
824
825 if (q16Dot16Compare(left, right) || q16Dot16Compare(pa.y(), pb.y()))
826 return;
827
828 if (d->antialiased) {
829 const Q16Dot16 iLeft = int(left);
830 const Q16Dot16 iRight = int(right);
831 const Q16Dot16 leftWidth = IntToQ16Dot16(iLeft + 1)
832 - FloatToQ16Dot16(left);
833 const Q16Dot16 rightWidth = FloatToQ16Dot16(right)
834 - IntToQ16Dot16(iRight);
835
836 Q16Dot16 coverage[3];
837 int x[3];
838 int len[3];
839
840 int n = 1;
841 if (iLeft == iRight) {
842 coverage[0] = (leftWidth + rightWidth) * 255;
843 x[0] = iLeft;
844 len[0] = 1;
845 } else {
846 coverage[0] = leftWidth * 255;
847 x[0] = iLeft;
848 len[0] = 1;
849 if (leftWidth == Q16Dot16Factor) {
850 len[0] = iRight - iLeft;
851 } else if (iRight - iLeft > 1) {
852 coverage[1] = IntToQ16Dot16(255);
853 x[1] = iLeft + 1;
854 len[1] = iRight - iLeft - 1;
855 ++n;
856 }
857 if (rightWidth) {
858 coverage[n] = rightWidth * 255;
859 x[n] = iRight;
860 len[n] = 1;
861 ++n;
862 }
863 }
864
865 const Q16Dot16 iTopFP = IntToQ16Dot16(int(pa.y()));
866 const Q16Dot16 iBottomFP = IntToQ16Dot16(int(pb.y()));
867 const Q16Dot16 yPa = FloatToQ16Dot16(pa.y());
868 const Q16Dot16 yPb = FloatToQ16Dot16(pb.y());
869 for (Q16Dot16 yFP = iTopFP; yFP <= iBottomFP; yFP += Q16Dot16Factor) {
870 const Q16Dot16 rowHeight = qMin(yFP + Q16Dot16Factor, yPb)
871 - qMax(yFP, yPa);
872 const int y = Q16Dot16ToInt(yFP);
873 for (int i = 0; i < n; ++i) {
874 buffer.addSpan(x[i], len[i], y,
875 Q16Dot16ToInt(Q16Dot16Multiply(rowHeight, coverage[i])));
876 }
877 }
878 } else { // aliased
879 int iTop = int(pa.y() + 0.5f);
880 int iBottom = pb.y() < 0.5f ? -1 : int(pb.y() - 0.5f);
881 int iLeft = int(left + 0.5f);
882 int iRight = right < 0.5f ? -1 : int(right - 0.5f);
883
884 int iWidth = iRight - iLeft + 1;
885 for (int y = iTop; y <= iBottom; ++y)
886 buffer.addSpan(iLeft, iWidth, y, 255);
887 }
888 } else {
889 if (pa.y() > pb.y())
890 qSwap(pa, pb);
891
892 QPointF delta = pb - pa;
893 delta *= 0.5f * width;
894 const QPointF perp(delta.y(), -delta.x());
895
896 if (squareCap) {
897 pa -= delta;
898 pb += delta;
899 }
900
901 QPointF top;
902 QPointF left;
903 QPointF right;
904 QPointF bottom;
905
906 if (pa.x() < pb.x()) {
907 top = pa + perp;
908 left = pa - perp;
909 right = pb + perp;
910 bottom = pb - perp;
911 } else {
912 top = pa - perp;
913 left = pb - perp;
914 right = pa + perp;
915 bottom = pb + perp;
916 }
917
918 const qreal topBound = qBound(qreal(d->clipRect.top()), top.y(), qreal(d->clipRect.bottom()));
919 const qreal bottomBound = qBound(qreal(d->clipRect.top()), bottom.y(), qreal(d->clipRect.bottom()));
920
921 const qreal leftSlope = (left.x() - top.x()) / (left.y() - top.y());
922 const qreal rightSlope = -1.0f / leftSlope;
923
924 const Q16Dot16 leftSlopeFP = FloatToQ16Dot16(leftSlope);
925 const Q16Dot16 rightSlopeFP = FloatToQ16Dot16(rightSlope);
926
927 if (d->antialiased) {
928 const Q16Dot16 iTopFP = IntToQ16Dot16(int(topBound));
929 const Q16Dot16 iLeftFP = IntToQ16Dot16(int(left.y()));
930 const Q16Dot16 iRightFP = IntToQ16Dot16(int(right.y()));
931 const Q16Dot16 iBottomFP = IntToQ16Dot16(int(bottomBound));
932
933 Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * leftSlope);
934 Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * rightSlope);
935 Q16Dot16 leftIntersectBf = 0;
936 Q16Dot16 rightIntersectBf = 0;
937
938 if (iLeftFP < iTopFP)
939 leftIntersectBf = FloatToQ16Dot16(left.x() + (int(topBound) - left.y()) * rightSlope);
940
941 if (iRightFP < iTopFP)
942 rightIntersectBf = FloatToQ16Dot16(right.x() + (int(topBound) - right.y()) * leftSlope);
943
944 Q16Dot16 rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom;
945 Q16Dot16 topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf;
946 Q16Dot16 bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf;
947
948 int leftMin, leftMax, rightMin, rightMax;
949
950 const Q16Dot16 yTopFP = FloatToQ16Dot16(top.y());
951 const Q16Dot16 yLeftFP = FloatToQ16Dot16(left.y());
952 const Q16Dot16 yRightFP = FloatToQ16Dot16(right.y());
953 const Q16Dot16 yBottomFP = FloatToQ16Dot16(bottom.y());
954
955 rowTop = qMax(iTopFP, yTopFP);
956 topLeftIntersectAf = leftIntersectAf +
957 Q16Dot16Multiply(leftSlopeFP, rowTop - iTopFP);
958 topRightIntersectAf = rightIntersectAf +
959 Q16Dot16Multiply(rightSlopeFP, rowTop - iTopFP);
960
961 Q16Dot16 yFP = iTopFP;
962 while (yFP <= iBottomFP) {
963 rowBottomLeft = qMin(yFP + Q16Dot16Factor, yLeftFP);
964 rowBottomRight = qMin(yFP + Q16Dot16Factor, yRightFP);
965 rowTopLeft = qMax(yFP, yLeftFP);
966 rowTopRight = qMax(yFP, yRightFP);
967 rowBottom = qMin(yFP + Q16Dot16Factor, yBottomFP);
968
969 if (yFP == iLeftFP) {
970 const int y = Q16Dot16ToInt(yFP);
971 leftIntersectBf = FloatToQ16Dot16(left.x() + (y - left.y()) * rightSlope);
972 topLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowTopLeft - yFP);
973 bottomLeftIntersectAf = leftIntersectAf + Q16Dot16Multiply(leftSlopeFP, rowBottomLeft - yFP);
974 } else {
975 topLeftIntersectBf = leftIntersectBf;
976 bottomLeftIntersectAf = leftIntersectAf + leftSlopeFP;
977 }
978
979 if (yFP == iRightFP) {
980 const int y = Q16Dot16ToInt(yFP);
981 rightIntersectBf = FloatToQ16Dot16(right.x() + (y - right.y()) * leftSlope);
982 topRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowTopRight - yFP);
983 bottomRightIntersectAf = rightIntersectAf + Q16Dot16Multiply(rightSlopeFP, rowBottomRight - yFP);
984 } else {
985 topRightIntersectBf = rightIntersectBf;
986 bottomRightIntersectAf = rightIntersectAf + rightSlopeFP;
987 }
988
989 if (yFP == iBottomFP) {
990 bottomLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowBottom - yFP);
991 bottomRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowBottom - yFP);
992 } else {
993 bottomLeftIntersectBf = leftIntersectBf + rightSlopeFP;
994 bottomRightIntersectBf = rightIntersectBf + leftSlopeFP;
995 }
996
997 if (yFP < iLeftFP) {
998 leftMin = Q16Dot16ToInt(bottomLeftIntersectAf);
999 leftMax = Q16Dot16ToInt(topLeftIntersectAf);
1000 } else if (yFP == iLeftFP) {
1001 leftMin = Q16Dot16ToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf));
1002 leftMax = Q16Dot16ToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf));
1003 } else {
1004 leftMin = Q16Dot16ToInt(topLeftIntersectBf);
1005 leftMax = Q16Dot16ToInt(bottomLeftIntersectBf);
1006 }
1007
1008 leftMin = qBound(d->clipRect.left(), leftMin, d->clipRect.right());
1009 leftMax = qBound(d->clipRect.left(), leftMax, d->clipRect.right());
1010
1011 if (yFP < iRightFP) {
1012 rightMin = Q16Dot16ToInt(topRightIntersectAf);
1013 rightMax = Q16Dot16ToInt(bottomRightIntersectAf);
1014 } else if (yFP == iRightFP) {
1015 rightMin = Q16Dot16ToInt(qMin(topRightIntersectAf, bottomRightIntersectBf));
1016 rightMax = Q16Dot16ToInt(qMin(bottomRightIntersectAf, topRightIntersectBf));
1017 } else {
1018 rightMin = Q16Dot16ToInt(bottomRightIntersectBf);
1019 rightMax = Q16Dot16ToInt(topRightIntersectBf);
1020 }
1021
1022 rightMin = qBound(d->clipRect.left(), rightMin, d->clipRect.right());
1023 rightMax = qBound(d->clipRect.left(), rightMax, d->clipRect.right());
1024
1025 if (leftMax > rightMax)
1026 leftMax = rightMax;
1027 if (rightMin < leftMin)
1028 rightMin = leftMin;
1029
1030 Q16Dot16 rowHeight = rowBottom - rowTop;
1031
1032 int x = leftMin;
1033 while (x <= leftMax) {
1034 Q16Dot16 excluded = 0;
1035
1036 if (yFP <= iLeftFP)
1037 excluded += intersectPixelFP(x, rowTop, rowBottomLeft,
1038 bottomLeftIntersectAf, topLeftIntersectAf,
1039 leftSlopeFP, -rightSlopeFP);
1040 if (yFP >= iLeftFP)
1041 excluded += intersectPixelFP(x, rowTopLeft, rowBottom,
1042 topLeftIntersectBf, bottomLeftIntersectBf,
1043 rightSlopeFP, -leftSlopeFP);
1044
1045 if (x >= rightMin) {
1046 if (yFP <= iRightFP)
1047 excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
1048 topRightIntersectAf, bottomRightIntersectAf,
1049 rightSlopeFP, -leftSlopeFP);
1050 if (yFP >= iRightFP)
1051 excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
1052 bottomRightIntersectBf, topRightIntersectBf,
1053 leftSlopeFP, -rightSlopeFP);
1054 }
1055
1056 Q16Dot16 coverage = rowHeight - excluded;
1057 buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
1058 Q16Dot16ToInt(255 * coverage));
1059 ++x;
1060 }
1061 if (x < rightMin) {
1062 buffer.addSpan(x, rightMin - x, Q16Dot16ToInt(yFP),
1063 Q16Dot16ToInt(255 * rowHeight));
1064 x = rightMin;
1065 }
1066 while (x <= rightMax) {
1067 Q16Dot16 excluded = 0;
1068 if (yFP <= iRightFP)
1069 excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
1070 topRightIntersectAf, bottomRightIntersectAf,
1071 rightSlopeFP, -leftSlopeFP);
1072 if (yFP >= iRightFP)
1073 excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
1074 bottomRightIntersectBf, topRightIntersectBf,
1075 leftSlopeFP, -rightSlopeFP);
1076
1077 Q16Dot16 coverage = rowHeight - excluded;
1078 buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
1079 Q16Dot16ToInt(255 * coverage));
1080 ++x;
1081 }
1082
1083 leftIntersectAf += leftSlopeFP;
1084 leftIntersectBf += rightSlopeFP;
1085 rightIntersectAf += rightSlopeFP;
1086 rightIntersectBf += leftSlopeFP;
1087 topLeftIntersectAf = leftIntersectAf;
1088 topRightIntersectAf = rightIntersectAf;
1089
1090 yFP += Q16Dot16Factor;
1091 rowTop = yFP;
1092 }
1093 } else { // aliased
1094 int iTop = int(top.y() + 0.5f);
1095 int iLeft = left.y() < 0.5f ? -1 : int(left.y() - 0.5f);
1096 int iRight = right.y() < 0.5f ? -1 : int(right.y() - 0.5f);
1097 int iBottom = bottom.y() < 0.5f? -1 : int(bottom.y() - 0.5f);
1098 int iMiddle = qMin(iLeft, iRight);
1099
1100 Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + 0.5f + (iTop + 0.5f - top.y()) * leftSlope);
1101 Q16Dot16 leftIntersectBf = FloatToQ16Dot16(left.x() + 0.5f + (iLeft + 1.5f - left.y()) * rightSlope);
1102 Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() - 0.5f + (iTop + 0.5f - top.y()) * rightSlope);
1103 Q16Dot16 rightIntersectBf = FloatToQ16Dot16(right.x() - 0.5f + (iRight + 1.5f - right.y()) * leftSlope);
1104
1105 int ny;
1106 int y = iTop;
1107#define DO_SEGMENT(next, li, ri, ls, rs) \
1108 ny = qMin(next + 1, d->clipRect.top()); \
1109 if (y < ny) { \
1110 li += ls * (ny - y); \
1111 ri += rs * (ny - y); \
1112 y = ny; \
1113 } \
1114 if (next > d->clipRect.bottom()) \
1115 next = d->clipRect.bottom(); \
1116 for (; y <= next; ++y) { \
1117 const int x1 = qMax(Q16Dot16ToInt(li), d->clipRect.left()); \
1118 const int x2 = qMin(Q16Dot16ToInt(ri), d->clipRect.right()); \
1119 if (x2 >= x1) \
1120 buffer.addSpan(x1, x2 - x1 + 1, y, 255); \
1121 li += ls; \
1122 ri += rs; \
1123 }
1124
1125 DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, leftSlopeFP, rightSlopeFP)
1126 DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, rightSlopeFP, rightSlopeFP)
1127 DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, leftSlopeFP, leftSlopeFP)
1128 DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, rightSlopeFP, leftSlopeFP)
1129#undef DO_SEGMENT
1130 }
1131 }
1132}
1133
1134void QRasterizer::rasterize(const QT_FT_Outline *outline, Qt::FillRule fillRule)
1135{
1136 if (outline->n_points < 3 || outline->n_contours == 0)
1137 return;
1138
1139 const QT_FT_Vector *points = outline->points;
1140
1141 QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1142
1143 // ### QT_FT_Outline already has a bounding rect which is
1144 // ### precomputed at this point, so we should probably just be
1145 // ### using that instead...
1146 QT_FT_Pos min_y = points[0].y, max_y = points[0].y;
1147 for (int i = 1; i < outline->n_points; ++i) {
1148 const QT_FT_Vector &p = points[i];
1149 min_y = qMin(p.y, min_y);
1150 max_y = qMax(p.y, max_y);
1151 }
1152
1153 int iTopBound = qMax(d->clipRect.top(), int((min_y + 32 + COORD_OFFSET - COORD_ROUNDING) >> 6));
1154 int iBottomBound = qMin(d->clipRect.bottom(), int((max_y - 32 + COORD_OFFSET - COORD_ROUNDING) >> 6));
1155
1156 if (iTopBound > iBottomBound)
1157 return;
1158
1159 d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer);
1160
1161 int first = 0;
1162 for (int i = 0; i < outline->n_contours; ++i) {
1163 const int last = outline->contours[i];
1164 for (int j = first; j < last; ++j) {
1165 if (outline->tags[j+1] == QT_FT_CURVE_TAG_CUBIC) {
1166 Q_ASSERT(outline->tags[j+2] == QT_FT_CURVE_TAG_CUBIC);
1167 d->scanConverter.mergeCurve(points[j], points[j+1], points[j+2], points[j+3]);
1168 j += 2;
1169 } else {
1170 d->scanConverter.mergeLine(points[j], points[j+1]);
1171 }
1172 }
1173
1174 first = last + 1;
1175 }
1176
1177 d->scanConverter.end();
1178}
1179
1180static inline QT_FT_Vector PointToVector(const QPointF &p)
1181{
1182 QT_FT_Vector result = { QT_FT_Pos(p.x() * 64), QT_FT_Pos(p.y() * 64) };
1183 return result;
1184}
1185
1186void QRasterizer::rasterize(const QPainterPath &path, Qt::FillRule fillRule)
1187{
1188 if (path.isEmpty())
1189 return;
1190
1191 QSpanBuffer buffer(d->blend, d->data, d->clipRect);
1192
1193 QRectF bounds = path.controlPointRect();
1194
1195 int iTopBound = qMax(d->clipRect.top(), int(bounds.top() + 0.5 + (COORD_OFFSET - COORD_ROUNDING)/64.));
1196 int iBottomBound = qMin(d->clipRect.bottom(), int(bounds.bottom() - 0.5 + (COORD_OFFSET - COORD_ROUNDING)/64.));
1197
1198 if (iTopBound > iBottomBound)
1199 return;
1200
1201 d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer);
1202
1203 int subpathStart = 0;
1204 QT_FT_Vector last = { 0, 0 };
1205 for (int i = 0; i < path.elementCount(); ++i) {
1206 switch (path.elementAt(i).type) {
1207 case QPainterPath::LineToElement:
1208 {
1209 QT_FT_Vector p1 = last;
1210 QT_FT_Vector p2 = PointToVector(path.elementAt(i));
1211 d->scanConverter.mergeLine(p1, p2);
1212 last = p2;
1213 break;
1214 }
1215 case QPainterPath::MoveToElement:
1216 {
1217 if (i != 0) {
1218 QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));
1219 // close previous subpath
1220 if (first.x != last.x || first.y != last.y)
1221 d->scanConverter.mergeLine(last, first);
1222 }
1223 subpathStart = i;
1224 last = PointToVector(path.elementAt(i));
1225 break;
1226 }
1227 case QPainterPath::CurveToElement:
1228 {
1229 QT_FT_Vector p1 = last;
1230 QT_FT_Vector p2 = PointToVector(path.elementAt(i));
1231 QT_FT_Vector p3 = PointToVector(path.elementAt(++i));
1232 QT_FT_Vector p4 = PointToVector(path.elementAt(++i));
1233 d->scanConverter.mergeCurve(p1, p2, p3, p4);
1234 last = p4;
1235 break;
1236 }
1237 default:
1238 Q_ASSERT(false);
1239 break;
1240 }
1241 }
1242
1243 QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));
1244
1245 // close path
1246 if (first.x != last.x || first.y != last.y)
1247 d->scanConverter.mergeLine(last, first);
1248
1249 d->scanConverter.end();
1250}
1251
1252QT_END_NAMESPACE
Note: See TracBrowser for help on using the repository browser.