1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the test suite 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 http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://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 2.1 or version 3 as published by the Free
20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and
21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the
22 ** following information to ensure the GNU Lesser General Public License
23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 **
26 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** GNU General Public License Usage
31 ** Alternatively, this file may be used under the terms of the GNU
32 ** General Public License version 3.0 as published by the Free Software
33 ** Foundation and appearing in the file LICENSE.GPL included in the
34 ** packaging of this file. Please review the following information to
35 ** ensure the GNU General Public License version 3.0 requirements will be
36 ** met: http://www.gnu.org/copyleft/gpl.html.
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41 #include "oldtessellator.h"
42 #include <QPointF>
43 #include <QVector>
44 #include <QList>
45 #include <QVariant>
46 #include <QVarLengthArray>
47 #include <qdebug.h>
48
49 #include "limits.h"
50 #include "utils.h"
51
52 #include "qnum.h"
53 #include "XrenderFake.h"
54
55 /*
56 * Polygon tesselator - can probably be optimized a bit more
57 */
58
59 //#define QT_DEBUG_TESSELATOR
60 #define FloatToXFixed(i) (int)((i) * 65536)
61 #define IntToXFixed(i) ((i) << 16)
62
63 //inline int qrealToXFixed(qreal f)
64 //{ return f << 8; }
65
66 struct QEdge {
QEdgeQEdge67 inline QEdge()
68 {}
QEdgeQEdge69 inline QEdge(const QPointF &pt1,
70 const QPointF &pt2)
71 {
72 p1.x = XDoubleToFixed(pt1.x());
73 p1.y = XDoubleToFixed(pt1.y());
74 p2.x = XDoubleToFixed(pt2.x());
75 p2.y = XDoubleToFixed(pt2.y());
76 m = (pt1.x() - pt2.x()) ? (pt1.y() - pt2.y()) / (pt1.x() - pt2.x()) : 0;
77 im = m ? 1/m : 0;
78 b = pt1.y() - m * pt1.x();
79 vertical = p1.x == p2.x;
80 horizontal = p1.y == p2.y;
81 }
82
83 QPointF pf1, pf2;
84 XPointFixed p1, p2;
85 qreal m;
86 qreal im;
87 qreal b;
88 qreal intersection;
89 signed short winding;
90 bool vertical;
91 bool horizontal;
92 };
93
94 struct QVrtx {
95 typedef QList<QEdge> Edges;
96 XPointFixed coords;
97 Edges startingEdges;
98 Edges endingEdges;
99 Edges intersectingEdges;
100 };
101
102 struct QIntersectionPoint {
103 qreal x;
104 const QEdge *edge;
105 };
106
107 QT_BEGIN_NAMESPACE
108 Q_DECLARE_TYPEINFO(QEdge, Q_PRIMITIVE_TYPE);
109 Q_DECLARE_TYPEINFO(QVrtx, Q_PRIMITIVE_TYPE);
110 Q_DECLARE_TYPEINFO(QIntersectionPoint, Q_PRIMITIVE_TYPE);
111 QT_END_NAMESPACE
112
113
114 // used by the edge point sort algorithm
115 static qreal currentY = 0.f;
116
compareEdges(const QEdge * e1,const QEdge * e2)117 static inline bool compareEdges(const QEdge *e1, const QEdge *e2)
118 {
119 return e1->p1.y < e2->p1.y;
120 }
121
isEqual(const XPointFixed & p1,const XPointFixed & p2)122 static inline bool isEqual(const XPointFixed &p1, const XPointFixed &p2)
123 {
124 return ((p1.x == p2.x) && (p1.y == p2.y));
125 }
126
compareIntersections(const QIntersectionPoint & i1,const QIntersectionPoint & i2)127 static inline bool compareIntersections(const QIntersectionPoint &i1, const QIntersectionPoint &i2)
128 {
129 if (qAbs(i1.x - i2.x) > 0.01) { // x != other.x in 99% of the cases
130 return i1.x < i2.x;
131 } else {
132 qreal x1 = (i1.edge->p1.x != i1.edge->p2.x) ?
133 ((currentY+1 - i1.edge->b)*i1.edge->m) : XFixedToDouble(i1.edge->p1.x);
134 qreal x2 = (i2.edge->p1.x != i2.edge->p2.x) ?
135 ((currentY+1 - i2.edge->b)*i2.edge->m) : XFixedToDouble(i2.edge->p1.x);
136 // qDebug() << ">>>" << currentY << i1.edge << i2.edge << x1 << x2;
137 return x1 < x2;
138 }
139 }
140
141 #ifdef QT_USE_FIXED_POINT
qrealToXFixed(qreal f)142 inline int qrealToXFixed(qreal f)
143 { return f.value() << 8; }
144 #else
145 #define qrealToXFixed FloatToXFixed
146 #endif
147
toXTrapezoid(XFixed y1,XFixed y2,const QEdge & left,const QEdge & right)148 static XTrapezoid QT_FASTCALL toXTrapezoid(XFixed y1, XFixed y2, const QEdge &left, const QEdge &right)
149 {
150 XTrapezoid trap;
151 trap.top = y1;
152 trap.bottom = y2;
153 trap.left.p1.y = left.p1.y;
154 trap.left.p2.y = left.p2.y;
155 trap.right.p1.y = right.p1.y;
156 trap.right.p2.y = right.p2.y;
157 trap.left.p1.x = left.p1.x;
158 trap.left.p2.x = left.p2.x;
159 trap.right.p1.x = right.p1.x;
160 trap.right.p2.x = right.p2.x;
161 return trap;
162 }
163
164 #ifdef QT_DEBUG_TESSELATOR
dump_edges(const QList<const QEdge * > & et)165 static void dump_edges(const QList<const QEdge *> &et)
166 {
167 for (int x = 0; x < et.size(); ++x) {
168 qDebug() << "edge#" << x << et.at(x) << "("
169 << XFixedToDouble(et.at(x)->p1.x)
170 << XFixedToDouble(et.at(x)->p1.y)
171 << ") ("
172 << XFixedToDouble(et.at(x)->p2.x)
173 << XFixedToDouble(et.at(x)->p2.y)
174 << ") b: " << et.at(x)->b << "m:" << et.at(x)->m;
175 }
176 }
177
dump_trap(const XTrapezoid & t)178 static void dump_trap(const XTrapezoid &t)
179 {
180 qDebug() << "trap# t=" << t.top/65536.0 << "b=" << t.bottom/65536.0 << "h="
181 << XFixedToDouble(t.bottom - t.top) << "\tleft p1: ("
182 << XFixedToDouble(t.left.p1.x) << ","<< XFixedToDouble(t.left.p1.y)
183 << ")" << "\tleft p2: (" << XFixedToDouble(t.left.p2.x) << ","
184 << XFixedToDouble(t.left.p2.y) << ")" << "\n\t\t\t\tright p1:("
185 << XFixedToDouble(t.right.p1.x) << "," << XFixedToDouble(t.right.p1.y) << ")"
186 << "\tright p2:(" << XFixedToDouble(t.right.p2.x) << ","
187 << XFixedToDouble(t.right.p2.y) << ")";
188 }
189 #endif
190
191
192 typedef int Q27Dot5;
193 #define Q27Dot5ToDouble(i) (i/32.)
194 #define FloatToQ27Dot5(i) (int)((i) * 32)
195 #define IntToQ27Dot5(i) ((i) << 5)
196 #define Q27Dot5ToXFixed(i) ((i) << 11)
197 #define Q27Dot5Factor 32
198
old_tesselate_polygon(QVector<XTrapezoid> * traps,const QPointF * pg,int pgSize,bool winding)199 void old_tesselate_polygon(QVector<XTrapezoid> *traps, const QPointF *pg, int pgSize,
200 bool winding)
201 {
202 QVector<QEdge> edges;
203 edges.reserve(128);
204 qreal ymin(INT_MAX/256);
205 qreal ymax(INT_MIN/256);
206
207 //painter.begin(pg, pgSize);
208 if (pg[0] != pg[pgSize-1])
209 qWarning() << Q_FUNC_INFO << "Malformed polygon (first and last points must be identical)";
210 // generate edge table
211 // qDebug() << "POINTS:";
212 for (int x = 0; x < pgSize-1; ++x) {
213 QEdge edge;
214 QPointF p1(Q27Dot5ToDouble(FloatToQ27Dot5(pg[x].x())),
215 Q27Dot5ToDouble(FloatToQ27Dot5(pg[x].y())));
216 QPointF p2(Q27Dot5ToDouble(FloatToQ27Dot5(pg[x+1].x())),
217 Q27Dot5ToDouble(FloatToQ27Dot5(pg[x+1].y())));
218
219 // qDebug() << " "
220 // << p1;
221 edge.winding = p1.y() > p2.y() ? 1 : -1;
222 if (edge.winding > 0)
223 qSwap(p1, p2);
224 edge.p1.x = XDoubleToFixed(p1.x());
225 edge.p1.y = XDoubleToFixed(p1.y());
226 edge.p2.x = XDoubleToFixed(p2.x());
227 edge.p2.y = XDoubleToFixed(p2.y());
228
229 edge.m = (p1.y() - p2.y()) / (p1.x() - p2.x()); // line derivative
230 edge.b = p1.y() - edge.m * p1.x(); // intersection with y axis
231 edge.m = edge.m != 0.0 ? 1.0 / edge.m : 0.0; // inverted derivative
232 edges.append(edge);
233 ymin = qMin(ymin, qreal(XFixedToDouble(edge.p1.y)));
234 ymax = qMax(ymax, qreal(XFixedToDouble(edge.p2.y)));
235 }
236
237 QList<const QEdge *> et; // edge list
238 for (int i = 0; i < edges.size(); ++i)
239 et.append(&edges.at(i));
240
241 // sort edge table by min y value
242 qSort(et.begin(), et.end(), compareEdges);
243
244 // eliminate shared edges
245 for (int i = 0; i < et.size(); ++i) {
246 for (int k = i+1; k < et.size(); ++k) {
247 const QEdge *edgeI = et.at(i);
248 const QEdge *edgeK = et.at(k);
249 if (edgeK->p1.y > edgeI->p1.y)
250 break;
251 if (edgeI->winding != edgeK->winding &&
252 isEqual(edgeI->p1, edgeK->p1) && isEqual(edgeI->p2, edgeK->p2)
253 ) {
254 et.removeAt(k);
255 et.removeAt(i);
256 --i;
257 break;
258 }
259 }
260 }
261
262 if (ymax <= ymin)
263 return;
264 QList<const QEdge *> aet; // edges that intersects the current scanline
265
266 // if (ymin < 0)
267 // ymin = 0;
268 // if (paintEventClipRegion) // don't scan more lines than we have to
269 // ymax = paintEventClipRegion->boundingRect().height();
270
271 #ifdef QT_DEBUG_TESSELATOR
272 qDebug("==> ymin = %f, ymax = %f", ymin, ymax);
273 #endif // QT_DEBUG_TESSELATOR
274
275 currentY = ymin; // used by the less than op
276 for (qreal y = ymin; y < ymax;) {
277 // fill active edge table with edges that intersect the current line
278 for (int i = 0; i < et.size(); ++i) {
279 const QEdge *edge = et.at(i);
280 if (edge->p1.y > XDoubleToFixed(y))
281 break;
282 aet.append(edge);
283 et.removeAt(i);
284 --i;
285 }
286
287 // remove processed edges from active edge table
288 for (int i = 0; i < aet.size(); ++i) {
289 if (aet.at(i)->p2.y <= XDoubleToFixed(y)) {
290 aet.removeAt(i);
291 --i;
292 }
293 }
294 if (aet.size()%2 != 0) {
295 #ifndef QT_NO_DEBUG
296 qWarning("QX11PaintEngine: aet out of sync - this should not happen.");
297 #endif
298 return;
299 }
300
301 // done?
302 if (!aet.size()) {
303 if (!et.size()) {
304 break;
305 } else {
306 y = currentY = XFixedToDouble(et.at(0)->p1.y);
307 continue;
308 }
309 }
310
311 // calculate the next y where we have to start a new set of trapezoids
312 qreal next_y(INT_MAX/256);
313 for (int i = 0; i < aet.size(); ++i) {
314 const QEdge *edge = aet.at(i);
315 if (XFixedToDouble(edge->p2.y) < next_y)
316 next_y = XFixedToDouble(edge->p2.y);
317 }
318
319 if (et.size() && next_y > XFixedToDouble(et.at(0)->p1.y))
320 next_y = XFixedToDouble(et.at(0)->p1.y);
321
322 int aetSize = aet.size();
323 for (int i = 0; i < aetSize; ++i) {
324 for (int k = i+1; k < aetSize; ++k) {
325 const QEdge *edgeI = aet.at(i);
326 const QEdge *edgeK = aet.at(k);
327 qreal m1 = edgeI->m;
328 qreal b1 = edgeI->b;
329 qreal m2 = edgeK->m;
330 qreal b2 = edgeK->b;
331
332 if (qAbs(m1 - m2) < 0.001)
333 continue;
334
335 // ### intersect is not calculated correctly when optimized with -O2 (gcc)
336 volatile qreal intersect = 0;
337 if (!qIsFinite(b1))
338 intersect = (1.f / m2) * XFixedToDouble(edgeI->p1.x) + b2;
339 else if (!qIsFinite(b2))
340 intersect = (1.f / m1) * XFixedToDouble(edgeK->p1.x) + b1;
341 else
342 intersect = (b1*m1 - b2*m2) / (m1 - m2);
343
344 if (intersect > y && intersect < next_y)
345 next_y = intersect;
346 }
347 }
348
349 XFixed yf, next_yf;
350 yf = qrealToXFixed(y);
351 next_yf = qrealToXFixed(next_y);
352
353 if (yf == next_yf) {
354 y = currentY = next_y;
355 continue;
356 }
357
358 #ifdef QT_DEBUG_TESSELATOR
359 qDebug("###> y = %f, next_y = %f, %d active edges", y, next_y, aet.size());
360 qDebug("===> edges");
361 dump_edges(et);
362 qDebug("===> active edges");
363 dump_edges(aet);
364 #endif
365 // calc intersection points
366 QVarLengthArray<QIntersectionPoint> isects(aet.size()+1);
367 for (int i = 0; i < isects.size()-1; ++i) {
368 const QEdge *edge = aet.at(i);
369 isects[i].x = (edge->p1.x != edge->p2.x) ?
370 ((y - edge->b)*edge->m) : XFixedToDouble(edge->p1.x);
371 isects[i].edge = edge;
372 }
373
374 if (isects.size()%2 != 1)
375 qFatal("%s: number of intersection points must be odd", Q_FUNC_INFO);
376
377 // sort intersection points
378 qSort(&isects[0], &isects[isects.size()-1], compareIntersections);
379 // qDebug() << "INTERSECTION_POINTS:";
380 // for (int i = 0; i < isects.size(); ++i)
381 // qDebug() << isects[i].edge << isects[i].x;
382
383 if (winding) {
384 // winding fill rule
385 for (int i = 0; i < isects.size()-1;) {
386 int winding = 0;
387 const QEdge *left = isects[i].edge;
388 const QEdge *right = 0;
389 winding += isects[i].edge->winding;
390 for (++i; i < isects.size()-1 && winding != 0; ++i) {
391 winding += isects[i].edge->winding;
392 right = isects[i].edge;
393 }
394 if (!left || !right)
395 break;
396 //painter.addTrapezoid(&toXTrapezoid(yf, next_yf, *left, *right));
397 traps->append(toXTrapezoid(yf, next_yf, *left, *right));
398 }
399 } else {
400 // odd-even fill rule
401 for (int i = 0; i < isects.size()-2; i += 2) {
402 //painter.addTrapezoid(&toXTrapezoid(yf, next_yf, *isects[i].edge, *isects[i+1].edge));
403 traps->append(toXTrapezoid(yf, next_yf, *isects[i].edge, *isects[i+1].edge));
404 }
405 }
406 y = currentY = next_y;
407 }
408
409 #ifdef QT_DEBUG_TESSELATOR
410 qDebug("==> number of trapezoids: %d - edge table size: %d\n", traps->size(), et.size());
411
412 for (int i = 0; i < traps->size(); ++i)
413 dump_trap(traps->at(i));
414 #endif
415
416 // optimize by unifying trapezoids that share left/right lines
417 // and have a common top/bottom edge
418 // for (int i = 0; i < tps.size(); ++i) {
419 // for (int k = i+1; k < tps.size(); ++k) {
420 // if (i != k && tps.at(i).right == tps.at(k).right
421 // && tps.at(i).left == tps.at(k).left
422 // && (tps.at(i).top == tps.at(k).bottom
423 // || tps.at(i).bottom == tps.at(k).top))
424 // {
425 // tps[i].bottom = tps.at(k).bottom;
426 // tps.removeAt(k);
427 // i = 0;
428 // break;
429 // }
430 // }
431 // }
432 //static int i = 0;
433 //QImage img = painter.end();
434 //img.save(QString("res%1.png").arg(i++), "PNG");
435 }
436