1
2 /*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8 #include "Test.h"
9 #if SK_SUPPORT_GPU
10 #include "GrReducedClip.h"
11 #endif
12 #include "SkClipStack.h"
13 #include "SkPath.h"
14 #include "SkRandom.h"
15 #include "SkRect.h"
16 #include "SkRegion.h"
17
18
test_assign_and_comparison(skiatest::Reporter * reporter)19 static void test_assign_and_comparison(skiatest::Reporter* reporter) {
20 SkClipStack s;
21 bool doAA = false;
22
23 REPORTER_ASSERT(reporter, 0 == s.getSaveCount());
24
25 // Build up a clip stack with a path, an empty clip, and a rect.
26 s.save();
27 REPORTER_ASSERT(reporter, 1 == s.getSaveCount());
28
29 SkPath p;
30 p.moveTo(5, 6);
31 p.lineTo(7, 8);
32 p.lineTo(5, 9);
33 p.close();
34 s.clipDevPath(p, SkRegion::kIntersect_Op, doAA);
35
36 s.save();
37 REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
38
39 SkRect r = SkRect::MakeLTRB(1, 2, 3, 4);
40 s.clipDevRect(r, SkRegion::kIntersect_Op, doAA);
41 r = SkRect::MakeLTRB(10, 11, 12, 13);
42 s.clipDevRect(r, SkRegion::kIntersect_Op, doAA);
43
44 s.save();
45 REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
46
47 r = SkRect::MakeLTRB(14, 15, 16, 17);
48 s.clipDevRect(r, SkRegion::kUnion_Op, doAA);
49
50 // Test that assignment works.
51 SkClipStack copy = s;
52 REPORTER_ASSERT(reporter, s == copy);
53
54 // Test that different save levels triggers not equal.
55 s.restore();
56 REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
57 REPORTER_ASSERT(reporter, s != copy);
58
59 // Test that an equal, but not copied version is equal.
60 s.save();
61 REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
62
63 r = SkRect::MakeLTRB(14, 15, 16, 17);
64 s.clipDevRect(r, SkRegion::kUnion_Op, doAA);
65 REPORTER_ASSERT(reporter, s == copy);
66
67 // Test that a different op on one level triggers not equal.
68 s.restore();
69 REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
70 s.save();
71 REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
72
73 r = SkRect::MakeLTRB(14, 15, 16, 17);
74 s.clipDevRect(r, SkRegion::kIntersect_Op, doAA);
75 REPORTER_ASSERT(reporter, s != copy);
76
77 // Test that different state (clip type) triggers not equal.
78 // NO LONGER VALID: if a path contains only a rect, we turn
79 // it into a bare rect for performance reasons (working
80 // around Chromium/JavaScript bad pattern).
81 /*
82 s.restore();
83 s.save();
84 SkPath rp;
85 rp.addRect(r);
86 s.clipDevPath(rp, SkRegion::kUnion_Op, doAA);
87 REPORTER_ASSERT(reporter, s != copy);
88 */
89
90 // Test that different rects triggers not equal.
91 s.restore();
92 REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
93 s.save();
94 REPORTER_ASSERT(reporter, 3 == s.getSaveCount());
95
96 r = SkRect::MakeLTRB(24, 25, 26, 27);
97 s.clipDevRect(r, SkRegion::kUnion_Op, doAA);
98 REPORTER_ASSERT(reporter, s != copy);
99
100 // Sanity check
101 s.restore();
102 REPORTER_ASSERT(reporter, 2 == s.getSaveCount());
103
104 copy.restore();
105 REPORTER_ASSERT(reporter, 2 == copy.getSaveCount());
106 REPORTER_ASSERT(reporter, s == copy);
107 s.restore();
108 REPORTER_ASSERT(reporter, 1 == s.getSaveCount());
109 copy.restore();
110 REPORTER_ASSERT(reporter, 1 == copy.getSaveCount());
111 REPORTER_ASSERT(reporter, s == copy);
112
113 // Test that different paths triggers not equal.
114 s.restore();
115 REPORTER_ASSERT(reporter, 0 == s.getSaveCount());
116 s.save();
117 REPORTER_ASSERT(reporter, 1 == s.getSaveCount());
118
119 p.addRect(r);
120 s.clipDevPath(p, SkRegion::kIntersect_Op, doAA);
121 REPORTER_ASSERT(reporter, s != copy);
122 }
123
assert_count(skiatest::Reporter * reporter,const SkClipStack & stack,int count)124 static void assert_count(skiatest::Reporter* reporter, const SkClipStack& stack,
125 int count) {
126 SkClipStack::B2TIter iter(stack);
127 int counter = 0;
128 while (iter.next()) {
129 counter += 1;
130 }
131 REPORTER_ASSERT(reporter, count == counter);
132 }
133
134 // Exercise the SkClipStack's bottom to top and bidirectional iterators
135 // (including the skipToTopmost functionality)
test_iterators(skiatest::Reporter * reporter)136 static void test_iterators(skiatest::Reporter* reporter) {
137 SkClipStack stack;
138
139 static const SkRect gRects[] = {
140 { 0, 0, 40, 40 },
141 { 60, 0, 100, 40 },
142 { 0, 60, 40, 100 },
143 { 60, 60, 100, 100 }
144 };
145
146 for (size_t i = 0; i < SK_ARRAY_COUNT(gRects); i++) {
147 // the union op will prevent these from being fused together
148 stack.clipDevRect(gRects[i], SkRegion::kUnion_Op, false);
149 }
150
151 assert_count(reporter, stack, 4);
152
153 // bottom to top iteration
154 {
155 const SkClipStack::Element* element = NULL;
156
157 SkClipStack::B2TIter iter(stack);
158 int i;
159
160 for (i = 0, element = iter.next(); element; ++i, element = iter.next()) {
161 REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
162 REPORTER_ASSERT(reporter, element->getRect() == gRects[i]);
163 }
164
165 SkASSERT(i == 4);
166 }
167
168 // top to bottom iteration
169 {
170 const SkClipStack::Element* element = NULL;
171
172 SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
173 int i;
174
175 for (i = 3, element = iter.prev(); element; --i, element = iter.prev()) {
176 REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
177 REPORTER_ASSERT(reporter, element->getRect() == gRects[i]);
178 }
179
180 SkASSERT(i == -1);
181 }
182
183 // skipToTopmost
184 {
185 const SkClipStack::Element* element = NULL;
186
187 SkClipStack::Iter iter(stack, SkClipStack::Iter::kBottom_IterStart);
188
189 element = iter.skipToTopmost(SkRegion::kUnion_Op);
190 REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
191 REPORTER_ASSERT(reporter, element->getRect() == gRects[3]);
192 }
193 }
194
195 // Exercise the SkClipStack's getConservativeBounds computation
test_bounds(skiatest::Reporter * reporter,bool useRects)196 static void test_bounds(skiatest::Reporter* reporter, bool useRects) {
197
198 static const int gNumCases = 20;
199 static const SkRect gAnswerRectsBW[gNumCases] = {
200 // A op B
201 { 40, 40, 50, 50 },
202 { 10, 10, 50, 50 },
203 { 10, 10, 80, 80 },
204 { 10, 10, 80, 80 },
205 { 40, 40, 80, 80 },
206
207 // invA op B
208 { 40, 40, 80, 80 },
209 { 0, 0, 100, 100 },
210 { 0, 0, 100, 100 },
211 { 0, 0, 100, 100 },
212 { 40, 40, 50, 50 },
213
214 // A op invB
215 { 10, 10, 50, 50 },
216 { 40, 40, 50, 50 },
217 { 0, 0, 100, 100 },
218 { 0, 0, 100, 100 },
219 { 0, 0, 100, 100 },
220
221 // invA op invB
222 { 0, 0, 100, 100 },
223 { 40, 40, 80, 80 },
224 { 0, 0, 100, 100 },
225 { 10, 10, 80, 80 },
226 { 10, 10, 50, 50 },
227 };
228
229 static const SkRegion::Op gOps[] = {
230 SkRegion::kIntersect_Op,
231 SkRegion::kDifference_Op,
232 SkRegion::kUnion_Op,
233 SkRegion::kXOR_Op,
234 SkRegion::kReverseDifference_Op
235 };
236
237 SkRect rectA, rectB;
238
239 rectA.iset(10, 10, 50, 50);
240 rectB.iset(40, 40, 80, 80);
241
242 SkPath clipA, clipB;
243
244 clipA.addRoundRect(rectA, SkIntToScalar(5), SkIntToScalar(5));
245 clipB.addRoundRect(rectB, SkIntToScalar(5), SkIntToScalar(5));
246
247 SkClipStack stack;
248 SkRect devClipBound;
249 bool isIntersectionOfRects = false;
250
251 int testCase = 0;
252 int numBitTests = useRects ? 1 : 4;
253 for (int invBits = 0; invBits < numBitTests; ++invBits) {
254 for (size_t op = 0; op < SK_ARRAY_COUNT(gOps); ++op) {
255
256 stack.save();
257 bool doInvA = SkToBool(invBits & 1);
258 bool doInvB = SkToBool(invBits & 2);
259
260 clipA.setFillType(doInvA ? SkPath::kInverseEvenOdd_FillType :
261 SkPath::kEvenOdd_FillType);
262 clipB.setFillType(doInvB ? SkPath::kInverseEvenOdd_FillType :
263 SkPath::kEvenOdd_FillType);
264
265 if (useRects) {
266 stack.clipDevRect(rectA, SkRegion::kIntersect_Op, false);
267 stack.clipDevRect(rectB, gOps[op], false);
268 } else {
269 stack.clipDevPath(clipA, SkRegion::kIntersect_Op, false);
270 stack.clipDevPath(clipB, gOps[op], false);
271 }
272
273 REPORTER_ASSERT(reporter, !stack.isWideOpen());
274
275 stack.getConservativeBounds(0, 0, 100, 100, &devClipBound,
276 &isIntersectionOfRects);
277
278 if (useRects) {
279 REPORTER_ASSERT(reporter, isIntersectionOfRects ==
280 (gOps[op] == SkRegion::kIntersect_Op));
281 } else {
282 REPORTER_ASSERT(reporter, !isIntersectionOfRects);
283 }
284
285 SkASSERT(testCase < gNumCases);
286 REPORTER_ASSERT(reporter, devClipBound == gAnswerRectsBW[testCase]);
287 ++testCase;
288
289 stack.restore();
290 }
291 }
292 }
293
294 // Test out 'isWideOpen' entry point
test_isWideOpen(skiatest::Reporter * reporter)295 static void test_isWideOpen(skiatest::Reporter* reporter) {
296
297 SkRect rectA, rectB;
298
299 rectA.iset(10, 10, 40, 40);
300 rectB.iset(50, 50, 80, 80);
301
302 // Stack should initially be wide open
303 {
304 SkClipStack stack;
305
306 REPORTER_ASSERT(reporter, stack.isWideOpen());
307 }
308
309 // Test out case where the user specifies a union that includes everything
310 {
311 SkClipStack stack;
312
313 SkPath clipA, clipB;
314
315 clipA.addRoundRect(rectA, SkIntToScalar(5), SkIntToScalar(5));
316 clipA.setFillType(SkPath::kInverseEvenOdd_FillType);
317
318 clipB.addRoundRect(rectB, SkIntToScalar(5), SkIntToScalar(5));
319 clipB.setFillType(SkPath::kInverseEvenOdd_FillType);
320
321 stack.clipDevPath(clipA, SkRegion::kReplace_Op, false);
322 stack.clipDevPath(clipB, SkRegion::kUnion_Op, false);
323
324 REPORTER_ASSERT(reporter, stack.isWideOpen());
325 }
326
327 // Test out union w/ a wide open clip
328 {
329 SkClipStack stack;
330
331 stack.clipDevRect(rectA, SkRegion::kUnion_Op, false);
332
333 REPORTER_ASSERT(reporter, stack.isWideOpen());
334 }
335
336 // Test out empty difference from a wide open clip
337 {
338 SkClipStack stack;
339
340 SkRect emptyRect;
341 emptyRect.setEmpty();
342
343 stack.clipDevRect(emptyRect, SkRegion::kDifference_Op, false);
344
345 REPORTER_ASSERT(reporter, stack.isWideOpen());
346 }
347
348 // Test out return to wide open
349 {
350 SkClipStack stack;
351
352 stack.save();
353
354 stack.clipDevRect(rectA, SkRegion::kReplace_Op, false);
355
356 REPORTER_ASSERT(reporter, !stack.isWideOpen());
357
358 stack.restore();
359
360 REPORTER_ASSERT(reporter, stack.isWideOpen());
361 }
362 }
363
count(const SkClipStack & stack)364 static int count(const SkClipStack& stack) {
365
366 SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
367
368 const SkClipStack::Element* element = NULL;
369 int count = 0;
370
371 for (element = iter.prev(); element; element = iter.prev(), ++count) {
372 ;
373 }
374
375 return count;
376 }
377
test_rect_inverse_fill(skiatest::Reporter * reporter)378 static void test_rect_inverse_fill(skiatest::Reporter* reporter) {
379 // non-intersecting rectangles
380 SkRect rect = SkRect::MakeLTRB(0, 0, 10, 10);
381
382 SkPath path;
383 path.addRect(rect);
384 path.toggleInverseFillType();
385 SkClipStack stack;
386 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
387
388 SkRect bounds;
389 SkClipStack::BoundsType boundsType;
390 stack.getBounds(&bounds, &boundsType);
391 REPORTER_ASSERT(reporter, SkClipStack::kInsideOut_BoundsType == boundsType);
392 REPORTER_ASSERT(reporter, bounds == rect);
393 }
394
395 // Test out SkClipStack's merging of rect clips. In particular exercise
396 // merging of aa vs. bw rects.
test_rect_merging(skiatest::Reporter * reporter)397 static void test_rect_merging(skiatest::Reporter* reporter) {
398
399 SkRect overlapLeft = SkRect::MakeLTRB(10, 10, 50, 50);
400 SkRect overlapRight = SkRect::MakeLTRB(40, 40, 80, 80);
401
402 SkRect nestedParent = SkRect::MakeLTRB(10, 10, 90, 90);
403 SkRect nestedChild = SkRect::MakeLTRB(40, 40, 60, 60);
404
405 SkRect bound;
406 SkClipStack::BoundsType type;
407 bool isIntersectionOfRects;
408
409 // all bw overlapping - should merge
410 {
411 SkClipStack stack;
412
413 stack.clipDevRect(overlapLeft, SkRegion::kReplace_Op, false);
414
415 stack.clipDevRect(overlapRight, SkRegion::kIntersect_Op, false);
416
417 REPORTER_ASSERT(reporter, 1 == count(stack));
418
419 stack.getBounds(&bound, &type, &isIntersectionOfRects);
420
421 REPORTER_ASSERT(reporter, isIntersectionOfRects);
422 }
423
424 // all aa overlapping - should merge
425 {
426 SkClipStack stack;
427
428 stack.clipDevRect(overlapLeft, SkRegion::kReplace_Op, true);
429
430 stack.clipDevRect(overlapRight, SkRegion::kIntersect_Op, true);
431
432 REPORTER_ASSERT(reporter, 1 == count(stack));
433
434 stack.getBounds(&bound, &type, &isIntersectionOfRects);
435
436 REPORTER_ASSERT(reporter, isIntersectionOfRects);
437 }
438
439 // mixed overlapping - should _not_ merge
440 {
441 SkClipStack stack;
442
443 stack.clipDevRect(overlapLeft, SkRegion::kReplace_Op, true);
444
445 stack.clipDevRect(overlapRight, SkRegion::kIntersect_Op, false);
446
447 REPORTER_ASSERT(reporter, 2 == count(stack));
448
449 stack.getBounds(&bound, &type, &isIntersectionOfRects);
450
451 REPORTER_ASSERT(reporter, !isIntersectionOfRects);
452 }
453
454 // mixed nested (bw inside aa) - should merge
455 {
456 SkClipStack stack;
457
458 stack.clipDevRect(nestedParent, SkRegion::kReplace_Op, true);
459
460 stack.clipDevRect(nestedChild, SkRegion::kIntersect_Op, false);
461
462 REPORTER_ASSERT(reporter, 1 == count(stack));
463
464 stack.getBounds(&bound, &type, &isIntersectionOfRects);
465
466 REPORTER_ASSERT(reporter, isIntersectionOfRects);
467 }
468
469 // mixed nested (aa inside bw) - should merge
470 {
471 SkClipStack stack;
472
473 stack.clipDevRect(nestedParent, SkRegion::kReplace_Op, false);
474
475 stack.clipDevRect(nestedChild, SkRegion::kIntersect_Op, true);
476
477 REPORTER_ASSERT(reporter, 1 == count(stack));
478
479 stack.getBounds(&bound, &type, &isIntersectionOfRects);
480
481 REPORTER_ASSERT(reporter, isIntersectionOfRects);
482 }
483
484 // reverse nested (aa inside bw) - should _not_ merge
485 {
486 SkClipStack stack;
487
488 stack.clipDevRect(nestedChild, SkRegion::kReplace_Op, false);
489
490 stack.clipDevRect(nestedParent, SkRegion::kIntersect_Op, true);
491
492 REPORTER_ASSERT(reporter, 2 == count(stack));
493
494 stack.getBounds(&bound, &type, &isIntersectionOfRects);
495
496 REPORTER_ASSERT(reporter, !isIntersectionOfRects);
497 }
498 }
499
test_quickContains(skiatest::Reporter * reporter)500 static void test_quickContains(skiatest::Reporter* reporter) {
501 SkRect testRect = SkRect::MakeLTRB(10, 10, 40, 40);
502 SkRect insideRect = SkRect::MakeLTRB(20, 20, 30, 30);
503 SkRect intersectingRect = SkRect::MakeLTRB(25, 25, 50, 50);
504 SkRect outsideRect = SkRect::MakeLTRB(0, 0, 50, 50);
505 SkRect nonIntersectingRect = SkRect::MakeLTRB(100, 100, 110, 110);
506
507 SkPath insideCircle;
508 insideCircle.addCircle(25, 25, 5);
509 SkPath intersectingCircle;
510 intersectingCircle.addCircle(25, 40, 10);
511 SkPath outsideCircle;
512 outsideCircle.addCircle(25, 25, 50);
513 SkPath nonIntersectingCircle;
514 nonIntersectingCircle.addCircle(100, 100, 5);
515
516 {
517 SkClipStack stack;
518 stack.clipDevRect(outsideRect, SkRegion::kDifference_Op, false);
519 // return false because quickContains currently does not care for kDifference_Op
520 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
521 }
522
523 // Replace Op tests
524 {
525 SkClipStack stack;
526 stack.clipDevRect(outsideRect, SkRegion::kReplace_Op, false);
527 REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
528 }
529
530 {
531 SkClipStack stack;
532 stack.clipDevRect(insideRect, SkRegion::kIntersect_Op, false);
533 stack.save(); // To prevent in-place substitution by replace OP
534 stack.clipDevRect(outsideRect, SkRegion::kReplace_Op, false);
535 REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
536 stack.restore();
537 }
538
539 {
540 SkClipStack stack;
541 stack.clipDevRect(outsideRect, SkRegion::kIntersect_Op, false);
542 stack.save(); // To prevent in-place substitution by replace OP
543 stack.clipDevRect(insideRect, SkRegion::kReplace_Op, false);
544 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
545 stack.restore();
546 }
547
548 // Verify proper traversal of multi-element clip
549 {
550 SkClipStack stack;
551 stack.clipDevRect(insideRect, SkRegion::kIntersect_Op, false);
552 // Use a path for second clip to prevent in-place intersection
553 stack.clipDevPath(outsideCircle, SkRegion::kIntersect_Op, false);
554 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
555 }
556
557 // Intersect Op tests with rectangles
558 {
559 SkClipStack stack;
560 stack.clipDevRect(outsideRect, SkRegion::kIntersect_Op, false);
561 REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
562 }
563
564 {
565 SkClipStack stack;
566 stack.clipDevRect(insideRect, SkRegion::kIntersect_Op, false);
567 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
568 }
569
570 {
571 SkClipStack stack;
572 stack.clipDevRect(intersectingRect, SkRegion::kIntersect_Op, false);
573 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
574 }
575
576 {
577 SkClipStack stack;
578 stack.clipDevRect(nonIntersectingRect, SkRegion::kIntersect_Op, false);
579 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
580 }
581
582 // Intersect Op tests with circle paths
583 {
584 SkClipStack stack;
585 stack.clipDevPath(outsideCircle, SkRegion::kIntersect_Op, false);
586 REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
587 }
588
589 {
590 SkClipStack stack;
591 stack.clipDevPath(insideCircle, SkRegion::kIntersect_Op, false);
592 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
593 }
594
595 {
596 SkClipStack stack;
597 stack.clipDevPath(intersectingCircle, SkRegion::kIntersect_Op, false);
598 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
599 }
600
601 {
602 SkClipStack stack;
603 stack.clipDevPath(nonIntersectingCircle, SkRegion::kIntersect_Op, false);
604 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
605 }
606
607 // Intersect Op tests with inverse filled rectangles
608 {
609 SkClipStack stack;
610 SkPath path;
611 path.addRect(outsideRect);
612 path.toggleInverseFillType();
613 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
614 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
615 }
616
617 {
618 SkClipStack stack;
619 SkPath path;
620 path.addRect(insideRect);
621 path.toggleInverseFillType();
622 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
623 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
624 }
625
626 {
627 SkClipStack stack;
628 SkPath path;
629 path.addRect(intersectingRect);
630 path.toggleInverseFillType();
631 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
632 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
633 }
634
635 {
636 SkClipStack stack;
637 SkPath path;
638 path.addRect(nonIntersectingRect);
639 path.toggleInverseFillType();
640 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
641 REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
642 }
643
644 // Intersect Op tests with inverse filled circles
645 {
646 SkClipStack stack;
647 SkPath path = outsideCircle;
648 path.toggleInverseFillType();
649 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
650 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
651 }
652
653 {
654 SkClipStack stack;
655 SkPath path = insideCircle;
656 path.toggleInverseFillType();
657 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
658 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
659 }
660
661 {
662 SkClipStack stack;
663 SkPath path = intersectingCircle;
664 path.toggleInverseFillType();
665 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
666 REPORTER_ASSERT(reporter, false == stack.quickContains(testRect));
667 }
668
669 {
670 SkClipStack stack;
671 SkPath path = nonIntersectingCircle;
672 path.toggleInverseFillType();
673 stack.clipDevPath(path, SkRegion::kIntersect_Op, false);
674 REPORTER_ASSERT(reporter, true == stack.quickContains(testRect));
675 }
676 }
677
678 ///////////////////////////////////////////////////////////////////////////////////////////////////
679
680 #if SK_SUPPORT_GPU
681 // Functions that add a shape to the clip stack. The shape is computed from a rectangle.
682 // AA is always disabled since the clip stack reducer can cause changes in aa rasterization of the
683 // stack. A fractional edge repeated in different elements may be rasterized fewer times using the
684 // reduced stack.
685 typedef void (*AddElementFunc) (const SkRect& rect,
686 bool invert,
687 SkRegion::Op op,
688 SkClipStack* stack);
689
add_round_rect(const SkRect & rect,bool invert,SkRegion::Op op,SkClipStack * stack)690 static void add_round_rect(const SkRect& rect, bool invert, SkRegion::Op op, SkClipStack* stack) {
691 SkPath path;
692 SkScalar rx = rect.width() / 10;
693 SkScalar ry = rect.height() / 20;
694 path.addRoundRect(rect, rx, ry);
695 if (invert) {
696 path.setFillType(SkPath::kInverseWinding_FillType);
697 }
698 stack->clipDevPath(path, op, false);
699 };
700
add_rect(const SkRect & rect,bool invert,SkRegion::Op op,SkClipStack * stack)701 static void add_rect(const SkRect& rect, bool invert, SkRegion::Op op, SkClipStack* stack) {
702 if (invert) {
703 SkPath path;
704 path.addRect(rect);
705 path.setFillType(SkPath::kInverseWinding_FillType);
706 stack->clipDevPath(path, op, false);
707 } else {
708 stack->clipDevRect(rect, op, false);
709 }
710 };
711
add_oval(const SkRect & rect,bool invert,SkRegion::Op op,SkClipStack * stack)712 static void add_oval(const SkRect& rect, bool invert, SkRegion::Op op, SkClipStack* stack) {
713 SkPath path;
714 path.addOval(rect);
715 if (invert) {
716 path.setFillType(SkPath::kInverseWinding_FillType);
717 }
718 stack->clipDevPath(path, op, false);
719 };
720
add_elem_to_stack(const SkClipStack::Element & element,SkClipStack * stack)721 static void add_elem_to_stack(const SkClipStack::Element& element, SkClipStack* stack) {
722 switch (element.getType()) {
723 case SkClipStack::Element::kRect_Type:
724 stack->clipDevRect(element.getRect(), element.getOp(), element.isAA());
725 break;
726 case SkClipStack::Element::kPath_Type:
727 stack->clipDevPath(element.getPath(), element.getOp(), element.isAA());
728 break;
729 case SkClipStack::Element::kEmpty_Type:
730 SkDEBUGFAIL("Why did the reducer produce an explicit empty.");
731 stack->clipEmpty();
732 break;
733 }
734 }
735
add_elem_to_region(const SkClipStack::Element & element,const SkIRect & bounds,SkRegion * region)736 static void add_elem_to_region(const SkClipStack::Element& element,
737 const SkIRect& bounds,
738 SkRegion* region) {
739 SkRegion elemRegion;
740 SkRegion boundsRgn(bounds);
741
742 switch (element.getType()) {
743 case SkClipStack::Element::kRect_Type: {
744 SkPath path;
745 path.addRect(element.getRect());
746 elemRegion.setPath(path, boundsRgn);
747 break;
748 }
749 case SkClipStack::Element::kPath_Type:
750 elemRegion.setPath(element.getPath(), boundsRgn);
751 break;
752 case SkClipStack::Element::kEmpty_Type:
753 //
754 region->setEmpty();
755 return;
756 }
757 region->op(elemRegion, element.getOp());
758 }
759
760 // This can assist with debugging the clip stack reduction code when the test below fails.
print_clip(const SkClipStack::Element & element)761 static inline void print_clip(const SkClipStack::Element& element) {
762 static const char* kOpStrs[] = {
763 "DF",
764 "IS",
765 "UN",
766 "XR",
767 "RD",
768 "RP",
769 };
770 if (SkClipStack::Element::kEmpty_Type != element.getType()) {
771 const SkRect& bounds = element.getBounds();
772 bool isRect = SkClipStack::Element::kRect_Type == element.getType();
773 SkDebugf("%s %s %s [%f %f] x [%f %f]\n",
774 kOpStrs[element.getOp()],
775 (isRect ? "R" : "P"),
776 (element.isInverseFilled() ? "I" : " "),
777 bounds.fLeft, bounds.fRight, bounds.fTop, bounds.fBottom);
778 } else {
779 SkDebugf("EM\n");
780 }
781 }
782
test_reduced_clip_stack(skiatest::Reporter * reporter)783 static void test_reduced_clip_stack(skiatest::Reporter* reporter) {
784 // We construct random clip stacks, reduce them, and then rasterize both versions to verify that
785 // they are equal.
786
787 // All the clip elements will be contained within these bounds.
788 static const SkRect kBounds = SkRect::MakeWH(100, 100);
789
790 enum {
791 kNumTests = 200,
792 kMinElemsPerTest = 1,
793 kMaxElemsPerTest = 50,
794 };
795
796 // min/max size of a clip element as a fraction of kBounds.
797 static const SkScalar kMinElemSizeFrac = SK_Scalar1 / 5;
798 static const SkScalar kMaxElemSizeFrac = SK_Scalar1;
799
800 static const SkRegion::Op kOps[] = {
801 SkRegion::kDifference_Op,
802 SkRegion::kIntersect_Op,
803 SkRegion::kUnion_Op,
804 SkRegion::kXOR_Op,
805 SkRegion::kReverseDifference_Op,
806 SkRegion::kReplace_Op,
807 };
808
809 // Replace operations short-circuit the optimizer. We want to make sure that we test this code
810 // path a little bit but we don't want it to prevent us from testing many longer traversals in
811 // the optimizer.
812 static const int kReplaceDiv = 4 * kMaxElemsPerTest;
813
814 // We want to test inverse fills. However, they are quite rare in practice so don't over do it.
815 static const SkScalar kFractionInverted = SK_Scalar1 / kMaxElemsPerTest;
816
817 static const AddElementFunc kElementFuncs[] = {
818 add_rect,
819 add_round_rect,
820 add_oval,
821 };
822
823 SkRandom r;
824
825 for (int i = 0; i < kNumTests; ++i) {
826 // Randomly generate a clip stack.
827 SkClipStack stack;
828 int numElems = r.nextRangeU(kMinElemsPerTest, kMaxElemsPerTest);
829 for (int e = 0; e < numElems; ++e) {
830 SkRegion::Op op = kOps[r.nextULessThan(SK_ARRAY_COUNT(kOps))];
831 if (op == SkRegion::kReplace_Op) {
832 if (r.nextU() % kReplaceDiv) {
833 --e;
834 continue;
835 }
836 }
837
838 // saves can change the clip stack behavior when an element is added.
839 bool doSave = r.nextBool();
840
841 SkSize size = SkSize::Make(
842 SkScalarFloorToScalar(SkScalarMul(kBounds.width(), r.nextRangeScalar(kMinElemSizeFrac, kMaxElemSizeFrac))),
843 SkScalarFloorToScalar(SkScalarMul(kBounds.height(), r.nextRangeScalar(kMinElemSizeFrac, kMaxElemSizeFrac))));
844
845 SkPoint xy = {SkScalarFloorToScalar(r.nextRangeScalar(kBounds.fLeft, kBounds.fRight - size.fWidth)),
846 SkScalarFloorToScalar(r.nextRangeScalar(kBounds.fTop, kBounds.fBottom - size.fHeight))};
847
848 SkRect rect = SkRect::MakeXYWH(xy.fX, xy.fY, size.fWidth, size.fHeight);
849
850 bool invert = r.nextBiasedBool(kFractionInverted);
851 kElementFuncs[r.nextULessThan(SK_ARRAY_COUNT(kElementFuncs))](rect, invert, op, &stack);
852 if (doSave) {
853 stack.save();
854 }
855 }
856
857 SkRect inflatedBounds = kBounds;
858 inflatedBounds.outset(kBounds.width() / 2, kBounds.height() / 2);
859 SkIRect inflatedIBounds;
860 inflatedBounds.roundOut(&inflatedIBounds);
861
862 typedef GrReducedClip::ElementList ElementList;
863 // Get the reduced version of the stack.
864 ElementList reducedClips;
865
866 GrReducedClip::InitialState initial;
867 SkIRect tBounds;
868 SkIRect* tightBounds = r.nextBool() ? &tBounds : NULL;
869 GrReducedClip::ReduceClipStack(stack,
870 inflatedIBounds,
871 &reducedClips,
872 &initial,
873 tightBounds);
874
875 // Build a new clip stack based on the reduced clip elements
876 SkClipStack reducedStack;
877 if (GrReducedClip::kAllOut_InitialState == initial) {
878 // whether the result is bounded or not, the whole plane should start outside the clip.
879 reducedStack.clipEmpty();
880 }
881 for (ElementList::Iter iter = reducedClips.headIter(); NULL != iter.get(); iter.next()) {
882 add_elem_to_stack(*iter.get(), &reducedStack);
883 }
884
885 // GrReducedClipStack assumes that the final result is clipped to the returned bounds
886 if (NULL != tightBounds) {
887 reducedStack.clipDevRect(*tightBounds, SkRegion::kIntersect_Op);
888 }
889
890 // convert both the original stack and reduced stack to SkRegions and see if they're equal
891 SkRegion region;
892 SkRegion reducedRegion;
893
894 region.setRect(inflatedIBounds);
895 const SkClipStack::Element* element;
896 SkClipStack::Iter iter(stack, SkClipStack::Iter::kBottom_IterStart);
897 while ((element = iter.next())) {
898 add_elem_to_region(*element, inflatedIBounds, ®ion);
899 }
900
901 reducedRegion.setRect(inflatedIBounds);
902 iter.reset(reducedStack, SkClipStack::Iter::kBottom_IterStart);
903 while ((element = iter.next())) {
904 add_elem_to_region(*element, inflatedIBounds, &reducedRegion);
905 }
906
907 REPORTER_ASSERT(reporter, region == reducedRegion);
908 }
909 }
910
911 #endif
912 ///////////////////////////////////////////////////////////////////////////////////////////////////
913
TestClipStack(skiatest::Reporter * reporter)914 static void TestClipStack(skiatest::Reporter* reporter) {
915 SkClipStack stack;
916
917 REPORTER_ASSERT(reporter, 0 == stack.getSaveCount());
918 assert_count(reporter, stack, 0);
919
920 static const SkIRect gRects[] = {
921 { 0, 0, 100, 100 },
922 { 25, 25, 125, 125 },
923 { 0, 0, 1000, 1000 },
924 { 0, 0, 75, 75 }
925 };
926 for (size_t i = 0; i < SK_ARRAY_COUNT(gRects); i++) {
927 stack.clipDevRect(gRects[i], SkRegion::kIntersect_Op);
928 }
929
930 // all of the above rects should have been intersected, leaving only 1 rect
931 SkClipStack::B2TIter iter(stack);
932 const SkClipStack::Element* element = iter.next();
933 SkRect answer;
934 answer.iset(25, 25, 75, 75);
935
936 REPORTER_ASSERT(reporter, NULL != element);
937 REPORTER_ASSERT(reporter, SkClipStack::Element::kRect_Type == element->getType());
938 REPORTER_ASSERT(reporter, SkRegion::kIntersect_Op == element->getOp());
939 REPORTER_ASSERT(reporter, element->getRect() == answer);
940 // now check that we only had one in our iterator
941 REPORTER_ASSERT(reporter, !iter.next());
942
943 stack.reset();
944 REPORTER_ASSERT(reporter, 0 == stack.getSaveCount());
945 assert_count(reporter, stack, 0);
946
947 test_assign_and_comparison(reporter);
948 test_iterators(reporter);
949 test_bounds(reporter, true); // once with rects
950 test_bounds(reporter, false); // once with paths
951 test_isWideOpen(reporter);
952 test_rect_merging(reporter);
953 test_rect_inverse_fill(reporter);
954 test_quickContains(reporter);
955 #if SK_SUPPORT_GPU
956 test_reduced_clip_stack(reporter);
957 #endif
958 }
959
960 #include "TestClassDef.h"
961 DEFINE_TESTCLASS("ClipStack", TestClipStackClass, TestClipStack)
962