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 "SkAutoMalloc.h"
9 #include "SkPath.h"
10 #include "SkRandom.h"
11 #include "SkRegion.h"
12 #include "Test.h"
13
Union(SkRegion * rgn,const SkIRect & rect)14 static void Union(SkRegion* rgn, const SkIRect& rect) {
15 rgn->op(rect, SkRegion::kUnion_Op);
16 }
17
18 #define TEST_NO_INTERSECT(rgn, rect) REPORTER_ASSERT(reporter, !rgn.intersects(rect))
19 #define TEST_INTERSECT(rgn, rect) REPORTER_ASSERT(reporter, rgn.intersects(rect))
20 #define TEST_NO_CONTAINS(rgn, rect) REPORTER_ASSERT(reporter, !rgn.contains(rect))
21
22 // inspired by http://code.google.com/p/skia/issues/detail?id=958
23 //
test_fromchrome(skiatest::Reporter * reporter)24 static void test_fromchrome(skiatest::Reporter* reporter) {
25 SkRegion r;
26 Union(&r, SkIRect::MakeXYWH(0, 0, 1, 1));
27 TEST_NO_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 0, 0));
28 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 2, 2));
29 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 0, 2, 2));
30 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2));
31 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 2, 2));
32 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 3, 3));
33
34 Union(&r, SkIRect::MakeXYWH(0, 0, 3, 3));
35 Union(&r, SkIRect::MakeXYWH(10, 0, 3, 3));
36 Union(&r, SkIRect::MakeXYWH(0, 10, 13, 3));
37 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, -1, 2, 2));
38 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 2, 2));
39 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 2, 2, 2));
40 TEST_INTERSECT(r, SkIRect::MakeXYWH(-1, 2, 2, 2));
41
42 TEST_INTERSECT(r, SkIRect::MakeXYWH(9, -1, 2, 2));
43 TEST_INTERSECT(r, SkIRect::MakeXYWH(12, -1, 2, 2));
44 TEST_INTERSECT(r, SkIRect::MakeXYWH(12, 2, 2, 2));
45 TEST_INTERSECT(r, SkIRect::MakeXYWH(9, 2, 2, 2));
46
47 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, -1, 13, 5));
48 TEST_INTERSECT(r, SkIRect::MakeXYWH(1, -1, 11, 5));
49 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 9, 5));
50 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, -1, 8, 5));
51 TEST_INTERSECT(r, SkIRect::MakeXYWH(3, -1, 8, 5));
52
53 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 1));
54 TEST_INTERSECT(r, SkIRect::MakeXYWH(1, 1, 11, 1));
55 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 9, 1));
56 TEST_INTERSECT(r, SkIRect::MakeXYWH(2, 1, 8, 1));
57 TEST_INTERSECT(r, SkIRect::MakeXYWH(3, 1, 8, 1));
58
59 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 0, 13, 13));
60 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 1, 13, 11));
61 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 9));
62 TEST_INTERSECT(r, SkIRect::MakeXYWH(0, 2, 13, 8));
63
64
65 // These test SkRegion::contains(Rect) and SkRegion::contains(Region)
66
67 SkRegion container;
68 Union(&container, SkIRect::MakeXYWH(0, 0, 40, 20));
69 Union(&container, SkIRect::MakeXYWH(30, 20, 10, 20));
70 TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(0, 0, 10, 39));
71 TEST_NO_CONTAINS(container, SkIRect::MakeXYWH(29, 0, 10, 39));
72
73 {
74 SkRegion rgn;
75 Union(&rgn, SkIRect::MakeXYWH(0, 0, 10, 10));
76 Union(&rgn, SkIRect::MakeLTRB(5, 10, 20, 20));
77 TEST_INTERSECT(rgn, SkIRect::MakeXYWH(15, 0, 5, 11));
78 }
79 }
80
test_empties(skiatest::Reporter * reporter)81 static void test_empties(skiatest::Reporter* reporter) {
82 SkRegion valid(SkIRect::MakeWH(10, 10));
83 SkRegion empty, empty2;
84
85 REPORTER_ASSERT(reporter, empty.isEmpty());
86 REPORTER_ASSERT(reporter, !valid.isEmpty());
87
88 // test intersects
89 REPORTER_ASSERT(reporter, !empty.intersects(empty2));
90 REPORTER_ASSERT(reporter, !valid.intersects(empty));
91
92 // test contains
93 REPORTER_ASSERT(reporter, !empty.contains(empty2));
94 REPORTER_ASSERT(reporter, !valid.contains(empty));
95 REPORTER_ASSERT(reporter, !empty.contains(valid));
96
97 SkPath emptyPath;
98 emptyPath.moveTo(1, 5);
99 emptyPath.close();
100 SkRegion openClip;
101 openClip.setRect(-16000, -16000, 16000, 16000);
102 empty.setPath(emptyPath, openClip); // should not assert
103 }
104
105 enum {
106 W = 256,
107 H = 256
108 };
109
randRect(SkRandom & rand)110 static SkIRect randRect(SkRandom& rand) {
111 int x = rand.nextU() % W;
112 int y = rand.nextU() % H;
113 int w = rand.nextU() % W;
114 int h = rand.nextU() % H;
115 return SkIRect::MakeXYWH(x, y, w >> 1, h >> 1);
116 }
117
randRgn(SkRandom & rand,SkRegion * rgn,int n)118 static void randRgn(SkRandom& rand, SkRegion* rgn, int n) {
119 rgn->setEmpty();
120 for (int i = 0; i < n; ++i) {
121 rgn->op(randRect(rand), SkRegion::kUnion_Op);
122 }
123 }
124
slow_contains(const SkRegion & outer,const SkRegion & inner)125 static bool slow_contains(const SkRegion& outer, const SkRegion& inner) {
126 SkRegion tmp;
127 tmp.op(outer, inner, SkRegion::kUnion_Op);
128 return outer == tmp;
129 }
130
slow_contains(const SkRegion & outer,const SkIRect & r)131 static bool slow_contains(const SkRegion& outer, const SkIRect& r) {
132 SkRegion tmp;
133 tmp.op(outer, SkRegion(r), SkRegion::kUnion_Op);
134 return outer == tmp;
135 }
136
slow_intersects(const SkRegion & outer,const SkRegion & inner)137 static bool slow_intersects(const SkRegion& outer, const SkRegion& inner) {
138 SkRegion tmp;
139 return tmp.op(outer, inner, SkRegion::kIntersect_Op);
140 }
141
test_contains_iter(skiatest::Reporter * reporter,const SkRegion & rgn)142 static void test_contains_iter(skiatest::Reporter* reporter, const SkRegion& rgn) {
143 SkRegion::Iterator iter(rgn);
144 while (!iter.done()) {
145 SkIRect r = iter.rect();
146 REPORTER_ASSERT(reporter, rgn.contains(r));
147 r.inset(-1, -1);
148 REPORTER_ASSERT(reporter, !rgn.contains(r));
149 iter.next();
150 }
151 }
152
contains_proc(skiatest::Reporter * reporter,const SkRegion & a,const SkRegion & b)153 static void contains_proc(skiatest::Reporter* reporter,
154 const SkRegion& a, const SkRegion& b) {
155 // test rgn
156 bool c0 = a.contains(b);
157 bool c1 = slow_contains(a, b);
158 REPORTER_ASSERT(reporter, c0 == c1);
159
160 // test rect
161 SkIRect r = a.getBounds();
162 r.inset(r.width()/4, r.height()/4);
163 c0 = a.contains(r);
164 c1 = slow_contains(a, r);
165 REPORTER_ASSERT(reporter, c0 == c1);
166
167 test_contains_iter(reporter, a);
168 test_contains_iter(reporter, b);
169 }
170
test_intersects_iter(skiatest::Reporter * reporter,const SkRegion & rgn)171 static void test_intersects_iter(skiatest::Reporter* reporter, const SkRegion& rgn) {
172 SkRegion::Iterator iter(rgn);
173 while (!iter.done()) {
174 SkIRect r = iter.rect();
175 REPORTER_ASSERT(reporter, rgn.intersects(r));
176 r.inset(-1, -1);
177 REPORTER_ASSERT(reporter, rgn.intersects(r));
178 iter.next();
179 }
180 }
181
intersects_proc(skiatest::Reporter * reporter,const SkRegion & a,const SkRegion & b)182 static void intersects_proc(skiatest::Reporter* reporter,
183 const SkRegion& a, const SkRegion& b) {
184 bool c0 = a.intersects(b);
185 bool c1 = slow_intersects(a, b);
186 REPORTER_ASSERT(reporter, c0 == c1);
187
188 test_intersects_iter(reporter, a);
189 test_intersects_iter(reporter, b);
190 }
191
test_proc(skiatest::Reporter * reporter,void (* proc)(skiatest::Reporter *,const SkRegion & a,const SkRegion &))192 static void test_proc(skiatest::Reporter* reporter,
193 void (*proc)(skiatest::Reporter*,
194 const SkRegion& a, const SkRegion&)) {
195 SkRandom rand;
196 for (int i = 0; i < 10000; ++i) {
197 SkRegion outer;
198 randRgn(rand, &outer, 8);
199 SkRegion inner;
200 randRgn(rand, &inner, 2);
201 proc(reporter, outer, inner);
202 }
203 }
204
rand_rect(SkIRect * rect,SkRandom & rand)205 static void rand_rect(SkIRect* rect, SkRandom& rand) {
206 int bits = 6;
207 int shift = 32 - bits;
208 rect->set(rand.nextU() >> shift, rand.nextU() >> shift,
209 rand.nextU() >> shift, rand.nextU() >> shift);
210 rect->sort();
211 }
212
test_rects(const SkIRect rect[],int count)213 static bool test_rects(const SkIRect rect[], int count) {
214 SkRegion rgn0, rgn1;
215
216 for (int i = 0; i < count; i++) {
217 rgn0.op(rect[i], SkRegion::kUnion_Op);
218 }
219 rgn1.setRects(rect, count);
220
221 if (rgn0 != rgn1) {
222 SkDebugf("\n");
223 for (int i = 0; i < count; i++) {
224 SkDebugf(" { %d, %d, %d, %d },\n",
225 rect[i].fLeft, rect[i].fTop,
226 rect[i].fRight, rect[i].fBottom);
227 }
228 SkDebugf("\n");
229 return false;
230 }
231 return true;
232 }
233
DEF_TEST(Region,reporter)234 DEF_TEST(Region, reporter) {
235 const SkIRect r2[] = {
236 { 0, 0, 1, 1 },
237 { 2, 2, 3, 3 },
238 };
239 REPORTER_ASSERT(reporter, test_rects(r2, SK_ARRAY_COUNT(r2)));
240
241 const SkIRect rects[] = {
242 { 0, 0, 1, 2 },
243 { 2, 1, 3, 3 },
244 { 4, 0, 5, 1 },
245 { 6, 0, 7, 4 },
246 };
247 REPORTER_ASSERT(reporter, test_rects(rects, SK_ARRAY_COUNT(rects)));
248
249 SkRandom rand;
250 for (int i = 0; i < 1000; i++) {
251 SkRegion rgn0, rgn1;
252
253 const int N = 8;
254 SkIRect rect[N];
255 for (int j = 0; j < N; j++) {
256 rand_rect(&rect[j], rand);
257 }
258 REPORTER_ASSERT(reporter, test_rects(rect, N));
259 }
260
261 test_proc(reporter, contains_proc);
262 test_proc(reporter, intersects_proc);
263 test_empties(reporter);
264 test_fromchrome(reporter);
265 }
266
267 // Test that writeToMemory reports the same number of bytes whether there was a
268 // buffer to write to or not.
test_write(const SkRegion & region,skiatest::Reporter * r)269 static void test_write(const SkRegion& region, skiatest::Reporter* r) {
270 const size_t bytesNeeded = region.writeToMemory(nullptr);
271 SkAutoMalloc storage(bytesNeeded);
272 const size_t bytesWritten = region.writeToMemory(storage.get());
273 REPORTER_ASSERT(r, bytesWritten == bytesNeeded);
274
275 // Also check that the bytes are meaningful.
276 SkRegion copy;
277 REPORTER_ASSERT(r, copy.readFromMemory(storage.get(), bytesNeeded));
278 REPORTER_ASSERT(r, region == copy);
279 }
280
DEF_TEST(Region_writeToMemory,r)281 DEF_TEST(Region_writeToMemory, r) {
282 // Test an empty region.
283 SkRegion region;
284 REPORTER_ASSERT(r, region.isEmpty());
285 test_write(region, r);
286
287 // Test a rectangular region
288 bool nonEmpty = region.setRect(0, 0, 50, 50);
289 REPORTER_ASSERT(r, nonEmpty);
290 REPORTER_ASSERT(r, region.isRect());
291 test_write(region, r);
292
293 // Test a complex region
294 nonEmpty = region.op(50, 50, 100, 100, SkRegion::kUnion_Op);
295 REPORTER_ASSERT(r, nonEmpty);
296 REPORTER_ASSERT(r, region.isComplex());
297 test_write(region, r);
298
299 SkRegion complexRegion;
300 Union(&complexRegion, SkIRect::MakeXYWH(0, 0, 1, 1));
301 Union(&complexRegion, SkIRect::MakeXYWH(0, 0, 3, 3));
302 Union(&complexRegion, SkIRect::MakeXYWH(10, 0, 3, 3));
303 Union(&complexRegion, SkIRect::MakeXYWH(0, 10, 13, 3));
304 test_write(complexRegion, r);
305
306 Union(&complexRegion, SkIRect::MakeXYWH(10, 20, 3, 3));
307 Union(&complexRegion, SkIRect::MakeXYWH(0, 20, 3, 3));
308 test_write(complexRegion, r);
309 }
310
DEF_TEST(Region_readFromMemory_bad,r)311 DEF_TEST(Region_readFromMemory_bad, r) {
312 // These assume what our binary format is: conceivably we could change it
313 // and might need to remove or change some of these tests.
314 SkRegion region;
315
316 {
317 // invalid boundary rectangle
318 int32_t data[5] = {0, 4, 4, 8, 2};
319 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
320 }
321 // Region Layout, Serialized Format:
322 // COUNT LEFT TOP RIGHT BOTTOM Y_SPAN_COUNT TOTAL_INTERVAL_COUNT
323 // Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel
324 {
325 // Example of valid data
326 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10,
327 2147483647, 2147483647};
328 REPORTER_ASSERT(r, 0 != region.readFromMemory(data, sizeof(data)));
329 }
330 {
331 // Example of valid data with 4 intervals
332 int32_t data[] = {19, 0, 0, 30, 30, 3, 4, 0, 10, 2, 0, 10, 20, 30,
333 2147483647, 20, 0, 2147483647, 30, 2, 0, 10, 20, 30,
334 2147483647, 2147483647};
335 REPORTER_ASSERT(r, 0 != region.readFromMemory(data, sizeof(data)));
336 }
337 {
338 // Short count
339 int32_t data[] = {8, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10,
340 2147483647, 2147483647};
341 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
342 }
343 {
344 // bounds don't match
345 int32_t data[] = {9, 0, 0, 10, 11, 1, 2, 0, 10, 2, 0, 4, 6, 10,
346 2147483647, 2147483647};
347 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
348 }
349 {
350 // bad yspan count
351 int32_t data[] = {9, 0, 0, 10, 10, 2, 2, 0, 10, 2, 0, 4, 6, 10,
352 2147483647, 2147483647};
353 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
354 }
355 {
356 // bad int count
357 int32_t data[] = {9, 0, 0, 10, 10, 1, 3, 0, 10, 2, 0, 4, 6, 10,
358 2147483647, 2147483647};
359 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
360 }
361 {
362 // bad final sentinal
363 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10,
364 2147483647, -1};
365 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
366 }
367 {
368 // bad row sentinal
369 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 0, 4, 6, 10,
370 -1, 2147483647};
371 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
372 }
373 {
374 // starts with empty yspan
375 int32_t data[] = {12, 0, 0, 10, 10, 2, 2, -5, 0, 0, 2147483647, 10,
376 2, 0, 4, 6, 10, 2147483647, 2147483647};
377 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
378 }
379 {
380 // ends with empty yspan
381 int32_t data[] = {12, 0, 0, 10, 10, 2, 2, 0, 10, 2, 0, 4, 6, 10,
382 2147483647, 15, 0, 2147483647, 2147483647};
383 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
384 }
385 {
386 // y intervals out of order
387 int32_t data[] = {19, 0, -20, 30, 10, 3, 4, 0, 10, 2, 0, 10, 20, 30,
388 2147483647, -20, 0, 2147483647, -10, 2, 0, 10, 20, 30,
389 2147483647, 2147483647};
390 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
391 }
392 {
393 // x intervals out of order
394 int32_t data[] = {9, 0, 0, 10, 10, 1, 2, 0, 10, 2, 6, 10, 0, 4,
395 2147483647, 2147483647};
396 REPORTER_ASSERT(r, 0 == region.readFromMemory(data, sizeof(data)));
397 }
398 }
399