1/*
2 * Copyright 2011 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
8#include "SkRandom.h"
9#include "SkRegion.h"
10#include "Test.h"
11
12static void Union(SkRegion* rgn, const SkIRect& rect) {
13    rgn->op(rect, SkRegion::kUnion_Op);
14}
15
16#define TEST_NO_INTERSECT(rgn, rect)    REPORTER_ASSERT(reporter, !rgn.intersects(rect))
17#define TEST_INTERSECT(rgn, rect)       REPORTER_ASSERT(reporter, rgn.intersects(rect))
18#define TEST_NO_CONTAINS(rgn, rect)     REPORTER_ASSERT(reporter, !rgn.contains(rect))
19
20// inspired by http://code.google.com/p/skia/issues/detail?id=958
21//
22static void test_fromchrome(skiatest::Reporter* reporter) {
23    SkRegion r;
24    Union(&r, SkIRect::MakeXYWH(0, 0, 1, 1));
25    TEST_NO_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 0, 0));
26    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 2, 2));
27    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 0, 2, 2));
28    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2));
29    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 2, 2));
30    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 3, 3));
31
32    Union(&r, SkIRect::MakeXYWH(0, 0, 3, 3));
33    Union(&r, SkIRect::MakeXYWH(10, 0, 3, 3));
34    Union(&r, SkIRect::MakeXYWH(0, 10, 13, 3));
35    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2));
36    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 2, 2));
37    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 2, 2, 2));
38    TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 2, 2, 2));
39
40    TEST_INTERSECT(r, SkIRect::MakeXYWH(9, -1, 2, 2));
41    TEST_INTERSECT(r, SkIRect::MakeXYWH(12, -1, 2, 2));
42    TEST_INTERSECT(r, SkIRect::MakeXYWH(12, 2, 2, 2));
43    TEST_INTERSECT(r, SkIRect::MakeXYWH(9, 2, 2, 2));
44
45    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 13, 5));
46    TEST_INTERSECT(r, SkIRect::MakeXYWH(1, -1, 11, 5));
47    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 9, 5));
48    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 8, 5));
49    TEST_INTERSECT(r, SkIRect::MakeXYWH(3, -1, 8, 5));
50
51    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 1));
52    TEST_INTERSECT(r, SkIRect::MakeXYWH(1, 1, 11, 1));
53    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 9, 1));
54    TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 8, 1));
55    TEST_INTERSECT(r, SkIRect::MakeXYWH(3, 1, 8, 1));
56
57    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 13, 13));
58    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 11));
59    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 9));
60    TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 8));
61
62
63    // These test SkRegion::contains(Rect) and SkRegion::contains(Region)
64
65    SkRegion container;
66    Union(&container, SkIRect::MakeXYWH(0, 0, 40, 20));
67    Union(&container, SkIRect::MakeXYWH(30, 20, 10, 20));
68    TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(0, 0, 10, 39));
69    TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(29, 0, 10, 39));
70
71    {
72        SkRegion rgn;
73        Union(&rgn, SkIRect::MakeXYWH(0, 0, 10, 10));
74        Union(&rgn, SkIRect::MakeLTRB(5, 10, 20, 20));
75        TEST_INTERSECT(rgn, SkIRect::MakeXYWH(15, 0, 5, 11));
76    }
77}
78
79static void test_empties(skiatest::Reporter* reporter) {
80    SkRegion valid(SkIRect::MakeWH(10, 10));
81    SkRegion empty, empty2;
82
83    REPORTER_ASSERT(reporter, empty.isEmpty());
84    REPORTER_ASSERT(reporter, !valid.isEmpty());
85
86    // test intersects
87    REPORTER_ASSERT(reporter, !empty.intersects(empty2));
88    REPORTER_ASSERT(reporter, !valid.intersects(empty));
89
90    // test contains
91    REPORTER_ASSERT(reporter, !empty.contains(empty2));
92    REPORTER_ASSERT(reporter, !valid.contains(empty));
93    REPORTER_ASSERT(reporter, !empty.contains(valid));
94}
95
96enum {
97    W = 256,
98    H = 256
99};
100
101static SkIRect randRect(SkRandom& rand) {
102    int x = rand.nextU() % W;
103    int y = rand.nextU() % H;
104    int w = rand.nextU() % W;
105    int h = rand.nextU() % H;
106    return SkIRect::MakeXYWH(x, y, w >> 1, h >> 1);
107}
108
109static void randRgn(SkRandom& rand, SkRegion* rgn, int n) {
110    rgn->setEmpty();
111    for (int i = 0; i < n; ++i) {
112        rgn->op(randRect(rand), SkRegion::kUnion_Op);
113    }
114}
115
116static bool slow_contains(const SkRegion& outer, const SkRegion& inner) {
117    SkRegion tmp;
118    tmp.op(outer, inner, SkRegion::kUnion_Op);
119    return outer == tmp;
120}
121
122static bool slow_contains(const SkRegion& outer, const SkIRect& r) {
123    SkRegion tmp;
124    tmp.op(outer, SkRegion(r), SkRegion::kUnion_Op);
125    return outer == tmp;
126}
127
128static bool slow_intersects(const SkRegion& outer, const SkRegion& inner) {
129    SkRegion tmp;
130    return tmp.op(outer, inner, SkRegion::kIntersect_Op);
131}
132
133static void test_contains_iter(skiatest::Reporter* reporter, const SkRegion& rgn) {
134    SkRegion::Iterator iter(rgn);
135    while (!iter.done()) {
136        SkIRect r = iter.rect();
137        REPORTER_ASSERT(reporter, rgn.contains(r));
138        r.inset(-1, -1);
139        REPORTER_ASSERT(reporter, !rgn.contains(r));
140        iter.next();
141    }
142}
143
144static void contains_proc(skiatest::Reporter* reporter,
145                          const SkRegion& a, const SkRegion& b) {
146    // test rgn
147    bool c0 = a.contains(b);
148    bool c1 = slow_contains(a, b);
149    REPORTER_ASSERT(reporter, c0 == c1);
150
151    // test rect
152    SkIRect r = a.getBounds();
153    r.inset(r.width()/4, r.height()/4);
154    c0 = a.contains(r);
155    c1 = slow_contains(a, r);
156    REPORTER_ASSERT(reporter, c0 == c1);
157
158    test_contains_iter(reporter, a);
159    test_contains_iter(reporter, b);
160}
161
162static void test_intersects_iter(skiatest::Reporter* reporter, const SkRegion& rgn) {
163    SkRegion::Iterator iter(rgn);
164    while (!iter.done()) {
165        SkIRect r = iter.rect();
166        REPORTER_ASSERT(reporter, rgn.intersects(r));
167        r.inset(-1, -1);
168        REPORTER_ASSERT(reporter, rgn.intersects(r));
169        iter.next();
170    }
171}
172
173static void intersects_proc(skiatest::Reporter* reporter,
174                          const SkRegion& a, const SkRegion& b) {
175    bool c0 = a.intersects(b);
176    bool c1 = slow_intersects(a, b);
177    REPORTER_ASSERT(reporter, c0 == c1);
178
179    test_intersects_iter(reporter, a);
180    test_intersects_iter(reporter, b);
181}
182
183static void test_proc(skiatest::Reporter* reporter,
184                      void (*proc)(skiatest::Reporter*,
185                                   const SkRegion& a, const SkRegion&)) {
186    SkRandom rand;
187    for (int i = 0; i < 10000; ++i) {
188        SkRegion outer;
189        randRgn(rand, &outer, 8);
190        SkRegion inner;
191        randRgn(rand, &inner, 2);
192        proc(reporter, outer, inner);
193    }
194}
195
196static void rand_rect(SkIRect* rect, SkRandom& rand) {
197    int bits = 6;
198    int shift = 32 - bits;
199    rect->set(rand.nextU() >> shift, rand.nextU() >> shift,
200              rand.nextU() >> shift, rand.nextU() >> shift);
201    rect->sort();
202}
203
204static bool test_rects(const SkIRect rect[], int count) {
205    SkRegion rgn0, rgn1;
206
207    for (int i = 0; i < count; i++) {
208        rgn0.op(rect[i], SkRegion::kUnion_Op);
209    }
210    rgn1.setRects(rect, count);
211
212    if (rgn0 != rgn1) {
213        SkDebugf("\n");
214        for (int i = 0; i < count; i++) {
215            SkDebugf(" { %d, %d, %d, %d },\n",
216                     rect[i].fLeft, rect[i].fTop,
217                     rect[i].fRight, rect[i].fBottom);
218        }
219        SkDebugf("\n");
220        return false;
221    }
222    return true;
223}
224
225DEF_TEST(Region, reporter) {
226    const SkIRect r2[] = {
227        { 0, 0, 1, 1 },
228        { 2, 2, 3, 3 },
229    };
230    REPORTER_ASSERT(reporter, test_rects(r2, SK_ARRAY_COUNT(r2)));
231
232    const SkIRect rects[] = {
233        { 0, 0, 1, 2 },
234        { 2, 1, 3, 3 },
235        { 4, 0, 5, 1 },
236        { 6, 0, 7, 4 },
237    };
238    REPORTER_ASSERT(reporter, test_rects(rects, SK_ARRAY_COUNT(rects)));
239
240    SkRandom rand;
241    for (int i = 0; i < 1000; i++) {
242        SkRegion rgn0, rgn1;
243
244        const int N = 8;
245        SkIRect rect[N];
246        for (int j = 0; j < N; j++) {
247            rand_rect(&rect[j], rand);
248        }
249        REPORTER_ASSERT(reporter, test_rects(rect, N));
250    }
251
252    test_proc(reporter, contains_proc);
253    test_proc(reporter, intersects_proc);
254    test_empties(reporter);
255    test_fromchrome(reporter);
256}
257