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 <QtTest/QtTest>
42 #include <QCoreApplication>
43 #include <QVector>
44 #include <qdebug.h>
45 #include <qpolygon.h>
46 #include <qmatrix.h>
47
48 #include "oldtessellator.h"
49 #include "testtessellator.h"
50 #include "utils.h"
51 #include "simple.h"
52 #include "arc.h"
53
54 #include "math.h"
55
56 //TESTED_CLASS=
57 //TESTED_FILES=
58
59 class tst_QTessellator : public QObject
60 {
61 Q_OBJECT
62
63 public:
tst_QTessellator()64 tst_QTessellator() {
65 }
66
67 private slots:
68 void testStandardSet();
69 void testRandom();
70 void testArc();
71 void testRects();
72 void testConvexRects();
73 void testConvex();
74 };
75
76
creatPoint()77 QPointF creatPoint()
78 {
79 qreal x = int(20.0 * (rand() / (RAND_MAX + 1.0)));
80 qreal y = int(20.0 * (rand() / (RAND_MAX + 1.0)));
81 return QPointF(x, y);
82 }
83
test(const QPointF * pg,int pgSize,bool winding,tessellate_function tessellate=test_tesselate_polygon,qreal maxDiff=0.005)84 bool test(const QPointF *pg, int pgSize, bool winding, tessellate_function tessellate = test_tesselate_polygon, qreal maxDiff = 0.005)
85 {
86 QVector<XTrapezoid> traps;
87 qreal area1 = 0;
88 qreal area2 = 0;
89
90 old_tesselate_polygon(&traps, pg, pgSize, winding);
91 area1 = compute_area_for_x(traps);
92
93 traps.clear();
94
95 tessellate(&traps, pg, pgSize, winding);
96 area2 = compute_area_for_x(traps);
97
98 bool result = (qAbs(area2 - area1) < maxDiff);
99 if (!result && area1)
100 result = (qAbs(area1 - area2)/area1 < maxDiff);
101
102 if (!result)
103 qDebug() << area1 << area2;
104
105 return result;
106 }
107
108
simplifyTestFailure(QVector<QPointF> failure,bool winding)109 void simplifyTestFailure(QVector<QPointF> failure, bool winding)
110 {
111 int i = 1;
112 while (i < failure.size() - 1) {
113 QVector<QPointF> t = failure;
114 t.remove(i);
115 if (test(t.data(), t.size(), winding)) {
116 ++i;
117 continue;
118 }
119 failure = t;
120 i = 1;
121 }
122
123 for (int x = 0; x < failure.size(); ++x) {
124 fprintf(stderr, "%lf,%lf, ", failure[x].x(), failure[x].y());
125 }
126 fprintf(stderr, "\n\n");
127 }
128
testStandardSet()129 void tst_QTessellator::testStandardSet()
130 {
131 QVector<FullData> sampleSet;
132 sampleSet.append(simpleData());
133
134 foreach(FullData data, sampleSet) {
135 for (int i = 0; i < data.size(); ++i) {
136 if (!test(data[i].data(), data[i].size(), false)) {
137 simplifyTestFailure(data[i], false);
138 QCOMPARE(true, false);
139 }
140 if (!test(data[i].data(), data[i].size(), true)) {
141 simplifyTestFailure(data[i], true);
142 QCOMPARE(true, false);
143 }
144 }
145 }
146 }
147
148
149
fillRandomVec(QVector<QPointF> & vec)150 void fillRandomVec(QVector<QPointF> &vec)
151 {
152 int size = vec.size(); --size;
153 for (int i = 0; i < size; ++i) {
154 vec[i] = creatPoint();
155 }
156 vec[size] = vec[0];
157 }
158
testRandom()159 void tst_QTessellator::testRandom()
160 {
161 int failures = 0;
162 for (int i = 5; i < 12; ++i) {
163 QVector<QPointF> vec(i);
164 #ifdef QT_ARCH_ARM
165 int k = 200;
166 #else
167 int k = 5000;
168 #endif
169 while (--k) {
170 fillRandomVec(vec);
171 if (!test(vec.data(), vec.size(), false)) {
172 simplifyTestFailure(vec, false);
173 ++failures;
174 }
175 if (!test(vec.data(), vec.size(), true)) {
176 simplifyTestFailure(vec, true);
177 ++failures;
178 }
179 }
180 }
181 QVERIFY(failures == 0);
182 }
183
184
185 // we need a higher threshold for failure here than in the above tests, as this basically draws
186 // a very thin outline, where the discretization in the new tesselator shows
test_arc(const QPolygonF & poly,bool winding)187 bool test_arc(const QPolygonF &poly, bool winding)
188 {
189 QVector<XTrapezoid> traps;
190 qreal area1 = 0;
191 qreal area2 = 0;
192
193 old_tesselate_polygon(&traps, poly.data(), poly.size(), winding);
194 area1 = compute_area_for_x(traps);
195
196 traps.clear();
197
198 test_tesselate_polygon(&traps, poly.data(), poly.size(), winding);
199 area2 = compute_area_for_x(traps);
200
201 bool result = (area2 - area1 < .02);
202 if (!result && area1)
203 result = (qAbs(area1 - area2)/area1 < .02);
204
205 return result;
206 }
207
208
209
testArc()210 void tst_QTessellator::testArc()
211 {
212 FullData arc = arcData();
213
214 QMatrix mat;
215 #ifdef QT_ARCH_ARM
216 const int stop = 5;
217 #else
218 const int stop = 1000;
219 #endif
220 for (int i = 0; i < stop; ++i) {
221 mat.rotate(qreal(.01));
222 mat.scale(qreal(.99), qreal(.99));
223 QPolygonF poly = arc.at(0);
224 QPolygonF vec = poly * mat;
225 QVERIFY(test_arc(vec, true));
226 QVERIFY(test_arc(vec, false));
227 }
228 }
229
isConvex(const QVector<QPointF> & v)230 static bool isConvex(const QVector<QPointF> &v)
231 {
232 int nPoints = v.size() - 1;
233
234 qreal lastCross = 0;
235 for (int i = 0; i < nPoints; ++i) {
236 QPointF a = v[i];
237 QPointF b = v[(i + 1) % nPoints];
238
239 QPointF d1 = b - a;
240
241 for (int j = 0; j < nPoints; ++j) {
242 if (j == i || j == i + 1)
243 continue;
244
245 QPointF p = v[j];
246 QPointF d2 = p - a;
247
248 qreal cross = d1.x() * d2.y() - d1.y() * d2.x();
249
250 if (!qFuzzyCompare(cross + 1, 1)
251 && !qFuzzyCompare(cross + 1, 1)
252 && (lastCross > 0) != (cross > 0))
253 return false;
254
255 lastCross = cross;
256 }
257 }
258
259 return true;
260 }
261
fillRectVec(QVector<QPointF> & v)262 static void fillRectVec(QVector<QPointF> &v)
263 {
264 int numRects = v.size() / 5;
265
266 int first = 0;
267 v[first++] = QPointF(0, 0);
268 v[first++] = QPointF(10, 0);
269 v[first++] = QPointF(10, 10);
270 v[first++] = QPointF(0, 10);
271 v[first++] = QPointF(0, 0);
272
273 v[first++] = QPointF(0, 0);
274 v[first++] = QPointF(2, 2);
275 v[first++] = QPointF(4, 0);
276 v[first++] = QPointF(2, -2);
277 v[first++] = QPointF(0, 0);
278
279 v[first++] = QPointF(0, 0);
280 v[first++] = QPointF(4, 4);
281 v[first++] = QPointF(6, 2);
282 v[first++] = QPointF(2, -2);
283 v[first++] = QPointF(0, 0);
284
285 for (int i = first / 5; i < numRects; ++i) {
286 QPointF a = creatPoint();
287 QPointF b = creatPoint();
288
289 QPointF delta = a - b;
290 QPointF perp(delta.y(), -delta.x());
291
292 perp *= ((int)(20.0 * rand() / (RAND_MAX + 1.0))) / 20.0;
293
294 int j = 5 * i;
295 v[j++] = a + perp;
296 v[j++] = a - perp;
297 v[j++] = b - perp;
298 v[j++] = b + perp;
299 v[j++] = a + perp;
300 }
301 }
302
303 #ifdef QT_ARCH_ARM
304 const int numRects = 500;
305 #else
306 const int numRects = 5000;
307 #endif
308
testConvexRects()309 void tst_QTessellator::testConvexRects()
310 {
311 return;
312 int failures = 0;
313 QVector<QPointF> vec(numRects * 5);
314 fillRectVec(vec);
315 for (int rect = 0; rect < numRects; ++rect) {
316 QVector<QPointF> v(5);
317 for (int i = 0; i < 5; ++i)
318 v[i] = vec[5 * rect + i];
319 if (!test(v.data(), v.size(), false, test_tessellate_polygon_convex)) {
320 simplifyTestFailure(v, false);
321 ++failures;
322 }
323 if (!test(v.data(), v.size(), true, test_tessellate_polygon_convex)) {
324 simplifyTestFailure(v, true);
325 ++failures;
326 }
327 }
328 QVERIFY(failures == 0);
329 }
330
testConvex()331 void tst_QTessellator::testConvex()
332 {
333 int failures = 0;
334 for (int i = 4; i < 10; ++i) {
335 QVector<QPointF> vec(i);
336 int k = 5000;
337 while (k--) {
338 fillRandomVec(vec);
339 if (!isConvex(vec))
340 continue;
341 if (!test(vec.data(), vec.size(), false, test_tessellate_polygon_convex)) {
342 simplifyTestFailure(vec, false);
343 ++failures;
344 }
345 if (!test(vec.data(), vec.size(), true, test_tessellate_polygon_convex)) {
346 simplifyTestFailure(vec, true);
347 ++failures;
348 }
349 }
350 }
351 QVERIFY(failures == 0);
352 }
353
354
testRects()355 void tst_QTessellator::testRects()
356 {
357 int failures = 0;
358 QVector<QPointF> vec(numRects * 5);
359 fillRectVec(vec);
360 for (int rect = 0; rect < numRects; ++rect) {
361 QVector<QPointF> v(5);
362 for (int i = 0; i < 5; ++i)
363 v[i] = vec[5 * rect + i];
364 if (!test(v.data(), v.size(), false, test_tessellate_polygon_rect, qreal(0.05))) {
365 simplifyTestFailure(v, false);
366 ++failures;
367 }
368 if (!test(v.data(), v.size(), true, test_tessellate_polygon_rect, qreal(0.05))) {
369 simplifyTestFailure(v, true);
370 ++failures;
371 }
372 }
373 QVERIFY(failures == 0);
374 }
375
376
377 QTEST_MAIN(tst_QTessellator)
378 #include "tst_tessellator.moc"
379