1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "EdgeWalker_Test.h"
8#include "Intersection_Tests.h"
9#include "SkBitmap.h"
10
11static SkBitmap bitmap;
12
13static void testSimplifyCoincidentInner() {
14    SkPath path, out;
15    path.setFillType(SkPath::kWinding_FillType);
16    path.addRect(10, 10, 60, 60, SkPath::kCCW_Direction);
17    path.addRect(20, 20, 50, 50, SkPath::kCW_Direction);
18    path.addRect(20, 30, 40, 40, SkPath::kCW_Direction);
19    testSimplify(path, true, out, bitmap);
20}
21
22static void testSimplifyCoincidentVertical() {
23    SkPath path, out;
24    path.setFillType(SkPath::kWinding_FillType);
25    path.addRect(10, 10, 30, 30);
26    path.addRect(10, 30, 30, 40);
27    simplify(path, true, out);
28    SkRect rect;
29    if (!out.isRect(&rect)) {
30        SkDebugf("%s expected rect\n", __FUNCTION__);
31    }
32    if (rect != SkRect::MakeLTRB(10, 10, 30, 40)) {
33        SkDebugf("%s expected union\n", __FUNCTION__);
34    }
35}
36
37static void testSimplifyCoincidentHorizontal() {
38    SkPath path, out;
39    path.setFillType(SkPath::kWinding_FillType);
40    path.addRect(10, 10, 30, 30);
41    path.addRect(30, 10, 40, 30);
42    simplify(path, true, out);
43    SkRect rect;
44    if (!out.isRect(&rect)) {
45        SkDebugf("%s expected rect\n", __FUNCTION__);
46    }
47    if (rect != SkRect::MakeLTRB(10, 10, 40, 30)) {
48        SkDebugf("%s expected union\n", __FUNCTION__);
49    }
50}
51
52static void testSimplifyMulti() {
53    SkPath path, out;
54    path.setFillType(SkPath::kWinding_FillType);
55    path.addRect(10, 10, 30, 30);
56    path.addRect(20, 20, 40, 40);
57    simplify(path, true, out);
58    SkPath expected;
59    expected.setFillType(SkPath::kEvenOdd_FillType);
60    expected.moveTo(10,10); // two cutout corners
61    expected.lineTo(10,30);
62    expected.lineTo(20,30);
63    expected.lineTo(20,40);
64    expected.lineTo(40,40);
65    expected.lineTo(40,20);
66    expected.lineTo(30,20);
67    expected.lineTo(30,10);
68    expected.lineTo(10,10);
69    expected.close();
70    if (out != expected) {
71        SkDebugf("%s expected equal\n", __FUNCTION__);
72    }
73
74    path = out;
75    path.addRect(30, 10, 40, 20);
76    path.addRect(10, 30, 20, 40);
77    simplify(path, true, out);
78    SkRect rect;
79    if (!out.isRect(&rect)) {
80        SkDebugf("%s expected rect\n", __FUNCTION__);
81    }
82    if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) {
83        SkDebugf("%s expected union\n", __FUNCTION__);
84    }
85
86    path = out;
87    path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction);
88    simplify(path, true, out);
89    if (!out.isEmpty()) {
90        SkDebugf("%s expected empty\n", __FUNCTION__);
91    }
92}
93
94static void testSimplifyAddL() {
95    SkPath path, out;
96    path.moveTo(10,10); // 'L' shape
97    path.lineTo(10,40);
98    path.lineTo(40,40);
99    path.lineTo(40,20);
100    path.lineTo(30,20);
101    path.lineTo(30,10);
102    path.lineTo(10,10);
103    path.close();
104    path.addRect(30, 10, 40, 20); // missing notch of 'L'
105    simplify(path, true, out);
106    SkRect rect;
107    if (!out.isRect(&rect)) {
108        SkDebugf("%s expected rect\n", __FUNCTION__);
109    }
110    if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) {
111        SkDebugf("%s expected union\n", __FUNCTION__);
112    }
113}
114
115static void testSimplifyCoincidentCCW() {
116    SkPath path, out;
117    path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction);
118    path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction);
119    simplify(path, true, out);
120    SkRect rect;
121    if (!out.isRect(&rect)) {
122        SkDebugf("%s expected rect\n", __FUNCTION__);
123    }
124    if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) {
125        SkDebugf("%s expected union\n", __FUNCTION__);
126    }
127}
128
129static void testSimplifyCoincidentCW() {
130    SkPath path, out;
131    path.addRect(10, 10, 40, 40, SkPath::kCCW_Direction);
132    path.addRect(10, 10, 40, 40, SkPath::kCW_Direction);
133    simplify(path, true, out);
134    if (!out.isEmpty()) {
135        SkDebugf("%s expected empty\n", __FUNCTION__);
136    }
137}
138
139static void testSimplifyCorner() {
140    SkPath path, out;
141    path.addRect(10, 10, 20, 20, SkPath::kCCW_Direction);
142    path.addRect(20, 20, 40, 40, SkPath::kCW_Direction);
143    simplify(path, true, out);
144    SkTDArray<SkRect> boundsArray;
145    contourBounds(out, boundsArray);
146    if (boundsArray.count() != 2) {
147        SkDebugf("%s expected 2 contours\n", __FUNCTION__);
148        return;
149    }
150    SkRect one = SkRect::MakeLTRB(10, 10, 20, 20);
151    SkRect two = SkRect::MakeLTRB(20, 20, 40, 40);
152    if ((boundsArray[0] != one && boundsArray[0] != two)
153            || (boundsArray[1] != one && boundsArray[1] != two)) {
154        SkDebugf("%s expected match\n", __FUNCTION__);
155    }
156}
157
158static void testSimplifyDiagonal() {
159    SkRect rect2 = SkRect::MakeXYWH(10, 10, 10, 10);
160    for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) {
161        for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) {
162            for (int x = 0; x <= 20; x += 20) {
163                for (int y = 0; y <= 20; y += 20) {
164                    SkPath path, out;
165                    SkRect rect1 = SkRect::MakeXYWH(x, y, 10, 10);
166                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
167                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
168                    simplify(path, true, out);
169                    SkPath::Iter iter(out, false);
170                    SkPoint pts[4], lastLine[2];
171                    SkPath::Verb verb;
172                    SkRect bounds[2];
173                    bounds[0].setEmpty();
174                    bounds[1].setEmpty();
175                    SkRect* boundsPtr = bounds;
176                    int count = 0, segments = 0;
177                    bool lastLineSet = false;
178                    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
179                        switch (verb) {
180                            case SkPath::kMove_Verb:
181                                if (!boundsPtr->isEmpty()) {
182                                    SkASSERT(boundsPtr == bounds);
183                                    ++boundsPtr;
184                                }
185                                boundsPtr->set(pts[0].fX, pts[0].fY, pts[0].fX, pts[0].fY);
186                                count = 0;
187                                lastLineSet = false;
188                                break;
189                            case SkPath::kLine_Verb:
190                                if (lastLineSet) {
191                                    SkASSERT((lastLine[1].fX - lastLine[0].fX) *
192                                        (pts[1].fY - lastLine[0].fY) !=
193                                        (lastLine[1].fY - lastLine[0].fY) *
194                                        (pts[1].fX - lastLine[0].fX));
195                                }
196                                lastLineSet = true;
197                                lastLine[0] = pts[0];
198                                lastLine[1] = pts[1];
199                                count = 1;
200                                ++segments;
201                                break;
202                            case SkPath::kClose_Verb:
203                                count = 0;
204                                break;
205                            default:
206                                SkDEBUGFAIL("bad verb");
207                                return;
208                        }
209                        for (int i = 1; i <= count; ++i) {
210                            boundsPtr->growToInclude(pts[i].fX, pts[i].fY);
211                        }
212                    }
213                    if (boundsPtr != bounds) {
214                        SkASSERT((bounds[0] == rect1 || bounds[1] == rect1)
215                                && (bounds[0] == rect2 || bounds[1] == rect2));
216                    } else {
217                        SkASSERT(segments == 8);
218                    }
219                }
220            }
221        }
222    }
223}
224
225static void assertOneContour(const SkPath& out, bool edge, bool extend) {
226    SkPath::Iter iter(out, false);
227    SkPoint pts[4];
228    SkPath::Verb verb;
229    SkRect bounds;
230    bounds.setEmpty();
231    int count = 0;
232    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
233        switch (verb) {
234            case SkPath::kMove_Verb:
235                SkASSERT(count == 0);
236                break;
237            case SkPath::kLine_Verb:
238                SkASSERT(pts[0].fX == pts[1].fX || pts[0].fY == pts[1].fY);
239                ++count;
240                break;
241            case SkPath::kClose_Verb:
242                break;
243            default:
244                SkDEBUGFAIL("bad verb");
245                return;
246        }
247    }
248    SkASSERT(count == (extend ? 4 : edge ? 6 : 8));
249}
250
251static void testSimplifyCoincident() {
252    // outside to inside, outside to right, outside to outside
253    // left to inside, left to right, left to outside
254    // inside to right, inside to outside
255    // repeat above for left, right, bottom
256    SkScalar start[] = { 0, 10, 20 };
257    size_t startCount = sizeof(start) / sizeof(start[0]);
258    SkScalar stop[] = { 30, 40, 50 };
259    size_t stopCount = sizeof(stop) / sizeof(stop[0]);
260    SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30);
261    for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) {
262        for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) {
263            for (size_t startIndex = 0; startIndex < startCount; ++startIndex) {
264                for (size_t stopIndex = 0; stopIndex < stopCount; ++stopIndex) {
265                    bool extend = start[startIndex] == rect2.fLeft && stop[stopIndex] == rect2.fRight;
266                    bool edge = start[startIndex] == rect2.fLeft || stop[stopIndex] == rect2.fRight;
267                    SkRect rect1 = SkRect::MakeLTRB(start[startIndex], 0, stop[stopIndex], 10);
268                    SkPath path, out;
269                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
270                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
271                    simplify(path, true, out);
272                    assertOneContour(out, edge, extend);
273
274                    path.reset();
275                    rect1 = SkRect::MakeLTRB(start[startIndex], 40, stop[stopIndex], 50);
276                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
277                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
278                    simplify(path, true, out);
279                    assertOneContour(out, edge, extend);
280
281                    path.reset();
282                    rect1 = SkRect::MakeLTRB(0, start[startIndex], 10, stop[stopIndex]);
283                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
284                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
285                    simplify(path, true, out);
286                    assertOneContour(out, edge, extend);
287
288                    path.reset();
289                    rect1 = SkRect::MakeLTRB(40, start[startIndex], 50, stop[stopIndex]);
290                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
291                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
292                    simplify(path, true, out);
293                    assertOneContour(out, edge, extend);
294                }
295            }
296        }
297    }
298}
299
300static void testSimplifyOverlap() {
301    SkScalar start[] = { 0, 10, 20 };
302    size_t startCount = sizeof(start) / sizeof(start[0]);
303    SkScalar stop[] = { 30, 40, 50 };
304    size_t stopCount = sizeof(stop) / sizeof(stop[0]);
305    SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30);
306    for (size_t dir = SkPath::kCW_Direction; dir <= SkPath::kCCW_Direction; ++dir) {
307        for (size_t lefty = 0; lefty < startCount; ++lefty) {
308            for (size_t righty = 0; righty < stopCount; ++righty) {
309                for (size_t toppy = 0; toppy < startCount; ++toppy) {
310                    for (size_t botty = 0; botty < stopCount; ++botty) {
311                        SkRect rect1 = SkRect::MakeLTRB(start[lefty], start[toppy],
312                                stop[righty], stop[botty]);
313                        SkPath path, out;
314                        path.addRect(rect1, static_cast<SkPath::Direction>(dir));
315                        path.addRect(rect2, static_cast<SkPath::Direction>(dir));
316                        testSimplify(path, true, out, bitmap);
317                    }
318                }
319            }
320        }
321    }
322}
323
324static void testSimplifyOverlapTiny() {
325    SkScalar start[] = { 0, 1, 2 };
326    size_t startCount = sizeof(start) / sizeof(start[0]);
327    SkScalar stop[] = { 3, 4, 5 };
328    size_t stopCount = sizeof(stop) / sizeof(stop[0]);
329    SkRect rect2 = SkRect::MakeXYWH(1, 1, 3, 3);
330    for (size_t dir = SkPath::kCW_Direction; dir <= SkPath::kCCW_Direction; ++dir) {
331        for (size_t lefty = 0; lefty < startCount; ++lefty) {
332            for (size_t righty = 0; righty < stopCount; ++righty) {
333                for (size_t toppy = 0; toppy < startCount; ++toppy) {
334                    for (size_t botty = 0; botty < stopCount; ++botty) {
335                        SkRect rect1 = SkRect::MakeLTRB(start[lefty], start[toppy],
336                                stop[righty], stop[botty]);
337                        SkPath path, out;
338                        path.addRect(rect1, static_cast<SkPath::Direction>(dir));
339                        path.addRect(rect2, static_cast<SkPath::Direction>(dir));
340                        simplify(path, true, out);
341                        comparePathsTiny(path, out);
342                    }
343                }
344            }
345        }
346    }
347}
348
349static void testSimplifyDegenerate() {
350    SkScalar start[] = { 0, 10, 20 };
351    size_t startCount = sizeof(start) / sizeof(start[0]);
352    SkScalar stop[] = { 30, 40, 50 };
353    size_t stopCount = sizeof(stop) / sizeof(stop[0]);
354    SkRect rect2 = SkRect::MakeXYWH(10, 10, 30, 30);
355    for (size_t outDir = SkPath::kCW_Direction; outDir <= SkPath::kCCW_Direction; ++outDir) {
356        for (size_t inDir = SkPath::kCW_Direction; inDir <= SkPath::kCCW_Direction; ++inDir) {
357            for (size_t startIndex = 0; startIndex < startCount; ++startIndex) {
358                for (size_t stopIndex = 0; stopIndex < stopCount; ++stopIndex) {
359                    SkRect rect1 = SkRect::MakeLTRB(start[startIndex], 0, stop[stopIndex], 0);
360                    SkPath path, out;
361                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
362                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
363                    simplify(path, true, out);
364                    SkRect rect;
365                    if (!out.isRect(&rect)) {
366                        SkDebugf("%s 1 expected rect\n", __FUNCTION__);
367                    }
368                    if (rect != rect2) {
369                        SkDebugf("%s 1 expected union\n", __FUNCTION__);
370                    }
371
372                    path.reset();
373                    rect1 = SkRect::MakeLTRB(start[startIndex], 40, stop[stopIndex], 40);
374                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
375                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
376                    simplify(path, true, out);
377                    if (!out.isRect(&rect)) {
378                        SkDebugf("%s 2 expected rect\n", __FUNCTION__);
379                    }
380                    if (rect != rect2) {
381                        SkDebugf("%s 2 expected union\n", __FUNCTION__);
382                    }
383
384                    path.reset();
385                    rect1 = SkRect::MakeLTRB(0, start[startIndex], 0, stop[stopIndex]);
386                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
387                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
388                    simplify(path, true, out);
389                    if (!out.isRect(&rect)) {
390                        SkDebugf("%s 3 expected rect\n", __FUNCTION__);
391                    }
392                    if (rect != rect2) {
393                        SkDebugf("%s 3 expected union\n", __FUNCTION__);
394                    }
395
396                    path.reset();
397                    rect1 = SkRect::MakeLTRB(40, start[startIndex], 40, stop[stopIndex]);
398                    path.addRect(rect1, static_cast<SkPath::Direction>(outDir));
399                    path.addRect(rect2, static_cast<SkPath::Direction>(inDir));
400                    simplify(path, true, out);
401                    if (!out.isRect(&rect)) {
402                        SkDebugf("%s 4 expected rect\n", __FUNCTION__);
403                    }
404                    if (rect != rect2) {
405                        SkDebugf("%s 4 expected union\n", __FUNCTION__);
406                    }
407                }
408            }
409        }
410    }
411}
412
413static void testSimplifyDegenerate1() {
414    SkPath path, out;
415    path.setFillType(SkPath::kWinding_FillType);
416    path.addRect( 0,  0,  0, 30);
417    path.addRect(10, 10, 40, 40);
418    simplify(path, true, out);
419    SkRect rect;
420    if (!out.isRect(&rect)) {
421        SkDebugf("%s expected rect\n", __FUNCTION__);
422    }
423    if (rect != SkRect::MakeLTRB(10, 10, 40, 40)) {
424        SkDebugf("%s expected union\n", __FUNCTION__);
425    }
426}
427
428static void (*simplifyTests[])() = {
429    testSimplifyCoincidentInner,
430    testSimplifyOverlapTiny,
431    testSimplifyDegenerate1,
432    testSimplifyCorner,
433    testSimplifyDegenerate,
434    testSimplifyOverlap,
435    testSimplifyDiagonal,
436    testSimplifyCoincident,
437    testSimplifyCoincidentCW,
438    testSimplifyCoincidentCCW,
439    testSimplifyCoincidentVertical,
440    testSimplifyCoincidentHorizontal,
441    testSimplifyAddL,
442    testSimplifyMulti,
443};
444
445static size_t simplifyTestsCount = sizeof(simplifyTests) / sizeof(simplifyTests[0]);
446
447static void (*firstTest)() = 0;
448
449void SimplifyRectangularPaths_Test() {
450    size_t index = 0;
451    if (firstTest) {
452        while (index < simplifyTestsCount && simplifyTests[index] != firstTest) {
453            ++index;
454        }
455    }
456    for ( ; index < simplifyTestsCount; ++index) {
457        if (simplifyTests[index] == testSimplifyCorner) {
458            // testSimplifyCorner fails because it expects two contours, where
459            // only one is returned. Both results are reasonable, but if two
460            // contours are desirable, or if we provide an option to choose
461            // between longer contours and more contours, turn this back on. For
462            // the moment, testSimplifyDiagonal also checks the test case, and
463            // permits either two rects or one non-crossing poly as valid
464            // unreported results.
465            continue;
466        }
467        (*simplifyTests[index])();
468    }
469}
470