• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
8 #include "GrReducedClip.h"
9 
10 typedef SkClipStack::Element Element;
11 
reduced_stack_walker(const SkClipStack & stack,const SkRect & queryBounds,GrReducedClip::ElementList * result,int32_t * resultGenID,GrReducedClip::InitialState * initialState,bool * requiresAA)12 static void reduced_stack_walker(const SkClipStack& stack,
13                                  const SkRect& queryBounds,
14                                  GrReducedClip::ElementList* result,
15                                  int32_t* resultGenID,
16                                  GrReducedClip::InitialState* initialState,
17                                  bool* requiresAA) {
18 
19     // walk backwards until we get to:
20     //  a) the beginning
21     //  b) an operation that is known to make the bounds all inside/outside
22     //  c) a replace operation
23 
24     static const GrReducedClip::InitialState kUnknown_InitialState =
25         static_cast<GrReducedClip::InitialState>(-1);
26     *initialState = kUnknown_InitialState;
27 
28     // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
29     // TODO: track these per saved clip so that we can consider them on the forward pass.
30     bool embiggens = false;
31     bool emsmallens = false;
32 
33     SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
34     int numAAElements = 0;
35     while ((kUnknown_InitialState == *initialState)) {
36         const Element* element = iter.prev();
37         if (nullptr == element) {
38             *initialState = GrReducedClip::kAllIn_InitialState;
39             break;
40         }
41         if (SkClipStack::kEmptyGenID == element->getGenID()) {
42             *initialState = GrReducedClip::kAllOut_InitialState;
43             break;
44         }
45         if (SkClipStack::kWideOpenGenID == element->getGenID()) {
46             *initialState = GrReducedClip::kAllIn_InitialState;
47             break;
48         }
49 
50         bool skippable = false;
51         bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
52 
53         switch (element->getOp()) {
54             case SkRegion::kDifference_Op:
55                 // check if the shape subtracted either contains the entire bounds (and makes
56                 // the clip empty) or is outside the bounds and therefore can be skipped.
57                 if (element->isInverseFilled()) {
58                     if (element->contains(queryBounds)) {
59                         skippable = true;
60                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
61                         *initialState = GrReducedClip::kAllOut_InitialState;
62                         skippable = true;
63                     }
64                 } else {
65                     if (element->contains(queryBounds)) {
66                         *initialState = GrReducedClip::kAllOut_InitialState;
67                         skippable = true;
68                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
69                         skippable = true;
70                     }
71                 }
72                 if (!skippable) {
73                     emsmallens = true;
74                 }
75                 break;
76             case SkRegion::kIntersect_Op:
77                 // check if the shape intersected contains the entire bounds and therefore can
78                 // be skipped or it is outside the entire bounds and therefore makes the clip
79                 // empty.
80                 if (element->isInverseFilled()) {
81                     if (element->contains(queryBounds)) {
82                         *initialState = GrReducedClip::kAllOut_InitialState;
83                         skippable = true;
84                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
85                         skippable = true;
86                     }
87                 } else {
88                     if (element->contains(queryBounds)) {
89                         skippable = true;
90                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
91                         *initialState = GrReducedClip::kAllOut_InitialState;
92                         skippable = true;
93                     }
94                 }
95                 if (!skippable) {
96                     emsmallens = true;
97                 }
98                 break;
99             case SkRegion::kUnion_Op:
100                 // If the union-ed shape contains the entire bounds then after this element
101                 // the bounds is entirely inside the clip. If the union-ed shape is outside the
102                 // bounds then this op can be skipped.
103                 if (element->isInverseFilled()) {
104                     if (element->contains(queryBounds)) {
105                         skippable = true;
106                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
107                         *initialState = GrReducedClip::kAllIn_InitialState;
108                         skippable = true;
109                     }
110                 } else {
111                     if (element->contains(queryBounds)) {
112                         *initialState = GrReducedClip::kAllIn_InitialState;
113                         skippable = true;
114                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
115                         skippable = true;
116                     }
117                 }
118                 if (!skippable) {
119                     embiggens = true;
120                 }
121                 break;
122             case SkRegion::kXOR_Op:
123                 // If the bounds is entirely inside the shape being xor-ed then the effect is
124                 // to flip the inside/outside state of every point in the bounds. We may be
125                 // able to take advantage of this in the forward pass. If the xor-ed shape
126                 // doesn't intersect the bounds then it can be skipped.
127                 if (element->isInverseFilled()) {
128                     if (element->contains(queryBounds)) {
129                         skippable = true;
130                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
131                         isFlip = true;
132                     }
133                 } else {
134                     if (element->contains(queryBounds)) {
135                         isFlip = true;
136                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
137                         skippable = true;
138                     }
139                 }
140                 if (!skippable) {
141                     emsmallens = embiggens = true;
142                 }
143                 break;
144             case SkRegion::kReverseDifference_Op:
145                 // When the bounds is entirely within the rev-diff shape then this behaves like xor
146                 // and reverses every point inside the bounds. If the shape is completely outside
147                 // the bounds then we know after this element is applied that the bounds will be
148                 // all outside the current clip.B
149                 if (element->isInverseFilled()) {
150                     if (element->contains(queryBounds)) {
151                         *initialState = GrReducedClip::kAllOut_InitialState;
152                         skippable = true;
153                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
154                         isFlip = true;
155                     }
156                 } else {
157                     if (element->contains(queryBounds)) {
158                         isFlip = true;
159                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
160                         *initialState = GrReducedClip::kAllOut_InitialState;
161                         skippable = true;
162                     }
163                 }
164                 if (!skippable) {
165                     emsmallens = embiggens = true;
166                 }
167                 break;
168             case SkRegion::kReplace_Op:
169                 // Replace will always terminate our walk. We will either begin the forward walk
170                 // at the replace op or detect here than the shape is either completely inside
171                 // or completely outside the bounds. In this latter case it can be skipped by
172                 // setting the correct value for initialState.
173                 if (element->isInverseFilled()) {
174                     if (element->contains(queryBounds)) {
175                         *initialState = GrReducedClip::kAllOut_InitialState;
176                         skippable = true;
177                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
178                         *initialState = GrReducedClip::kAllIn_InitialState;
179                         skippable = true;
180                     }
181                 } else {
182                     if (element->contains(queryBounds)) {
183                         *initialState = GrReducedClip::kAllIn_InitialState;
184                         skippable = true;
185                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
186                         *initialState = GrReducedClip::kAllOut_InitialState;
187                         skippable = true;
188                     }
189                 }
190                 if (!skippable) {
191                     *initialState = GrReducedClip::kAllOut_InitialState;
192                     embiggens = emsmallens = true;
193                 }
194                 break;
195             default:
196                 SkDEBUGFAIL("Unexpected op.");
197                 break;
198         }
199         if (!skippable) {
200             if (0 == result->count()) {
201                 // This will be the last element. Record the stricter genID.
202                 *resultGenID = element->getGenID();
203             }
204 
205             // if it is a flip, change it to a bounds-filling rect
206             if (isFlip) {
207                 SkASSERT(SkRegion::kXOR_Op == element->getOp() ||
208                          SkRegion::kReverseDifference_Op == element->getOp());
209                 result->addToHead(queryBounds, SkRegion::kReverseDifference_Op, false);
210             } else {
211                 Element* newElement = result->addToHead(*element);
212                 if (newElement->isAA()) {
213                     ++numAAElements;
214                 }
215                 // Intersecting an inverse shape is the same as differencing the non-inverse shape.
216                 // Replacing with an inverse shape is the same as setting initialState=kAllIn and
217                 // differencing the non-inverse shape.
218                 bool isReplace = SkRegion::kReplace_Op == newElement->getOp();
219                 if (newElement->isInverseFilled() &&
220                     (SkRegion::kIntersect_Op == newElement->getOp() || isReplace)) {
221                     newElement->invertShapeFillType();
222                     newElement->setOp(SkRegion::kDifference_Op);
223                     if (isReplace) {
224                         SkASSERT(GrReducedClip::kAllOut_InitialState == *initialState);
225                         *initialState = GrReducedClip::kAllIn_InitialState;
226                     }
227                 }
228             }
229         }
230     }
231 
232     if ((GrReducedClip::kAllOut_InitialState == *initialState && !embiggens) ||
233         (GrReducedClip::kAllIn_InitialState == *initialState && !emsmallens)) {
234         result->reset();
235     } else {
236         Element* element = result->headIter().get();
237         while (element) {
238             bool skippable = false;
239             switch (element->getOp()) {
240                 case SkRegion::kDifference_Op:
241                     // subtracting from the empty set yields the empty set.
242                     skippable = GrReducedClip::kAllOut_InitialState == *initialState;
243                     break;
244                 case SkRegion::kIntersect_Op:
245                     // intersecting with the empty set yields the empty set
246                     if (GrReducedClip::kAllOut_InitialState == *initialState) {
247                         skippable = true;
248                     } else {
249                         // We can clear to zero and then simply draw the clip element.
250                         *initialState = GrReducedClip::kAllOut_InitialState;
251                         element->setOp(SkRegion::kReplace_Op);
252                     }
253                     break;
254                 case SkRegion::kUnion_Op:
255                     if (GrReducedClip::kAllIn_InitialState == *initialState) {
256                         // unioning the infinite plane with anything is a no-op.
257                         skippable = true;
258                     } else {
259                         // unioning the empty set with a shape is the shape.
260                         element->setOp(SkRegion::kReplace_Op);
261                     }
262                     break;
263                 case SkRegion::kXOR_Op:
264                     if (GrReducedClip::kAllOut_InitialState == *initialState) {
265                         // xor could be changed to diff in the kAllIn case, not sure it's a win.
266                         element->setOp(SkRegion::kReplace_Op);
267                     }
268                     break;
269                 case SkRegion::kReverseDifference_Op:
270                     if (GrReducedClip::kAllIn_InitialState == *initialState) {
271                         // subtracting the whole plane will yield the empty set.
272                         skippable = true;
273                         *initialState = GrReducedClip::kAllOut_InitialState;
274                     } else {
275                         // this picks up flips inserted in the backwards pass.
276                         skippable = element->isInverseFilled() ?
277                             !SkRect::Intersects(element->getBounds(), queryBounds) :
278                             element->contains(queryBounds);
279                         if (skippable) {
280                             *initialState = GrReducedClip::kAllIn_InitialState;
281                         } else {
282                             element->setOp(SkRegion::kReplace_Op);
283                         }
284                     }
285                     break;
286                 case SkRegion::kReplace_Op:
287                     skippable = false; // we would have skipped it in the backwards walk if we
288                                        // could've.
289                     break;
290                 default:
291                     SkDEBUGFAIL("Unexpected op.");
292                     break;
293             }
294             if (!skippable) {
295                 break;
296             } else {
297                 if (element->isAA()) {
298                     --numAAElements;
299                 }
300                 result->popHead();
301                 element = result->headIter().get();
302             }
303         }
304     }
305     if (requiresAA) {
306         *requiresAA = numAAElements > 0;
307     }
308 
309     if (0 == result->count()) {
310         if (*initialState == GrReducedClip::kAllIn_InitialState) {
311             *resultGenID = SkClipStack::kWideOpenGenID;
312         } else {
313             *resultGenID = SkClipStack::kEmptyGenID;
314         }
315     }
316 }
317 
318 /*
319 There are plenty of optimizations that could be added here. Maybe flips could be folded into
320 earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
321 for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
322 based on later intersect operations, and perhaps remove intersect-rects. We could optionally
323 take a rect in case the caller knows a bound on what is to be drawn through this clip.
324 */
ReduceClipStack(const SkClipStack & stack,const SkIRect & queryBounds,ElementList * result,int32_t * resultGenID,InitialState * initialState,SkIRect * tighterBounds,bool * requiresAA)325 void GrReducedClip::ReduceClipStack(const SkClipStack& stack,
326                                     const SkIRect& queryBounds,
327                                     ElementList* result,
328                                     int32_t* resultGenID,
329                                     InitialState* initialState,
330                                     SkIRect* tighterBounds,
331                                     bool* requiresAA) {
332     result->reset();
333 
334     // The clip established by the element list might be cached based on the last
335     // generation id. When we make early returns, we do not know what was the generation
336     // id that lead to the state. Make a conservative guess.
337     *resultGenID = stack.getTopmostGenID();
338 
339     if (stack.isWideOpen()) {
340         *initialState = kAllIn_InitialState;
341         return;
342     }
343 
344 
345     // We initially look at whether the bounds alone is sufficient. We also use the stack bounds to
346     // attempt to compute the tighterBounds.
347 
348     SkClipStack::BoundsType stackBoundsType;
349     SkRect stackBounds;
350     bool iior;
351     stack.getBounds(&stackBounds, &stackBoundsType, &iior);
352 
353     const SkIRect* bounds = &queryBounds;
354 
355     SkRect scalarQueryBounds = SkRect::Make(queryBounds);
356 
357     if (iior) {
358         SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
359         SkRect isectRect;
360         if (stackBounds.contains(scalarQueryBounds)) {
361             *initialState = GrReducedClip::kAllIn_InitialState;
362             if (tighterBounds) {
363                 *tighterBounds = queryBounds;
364             }
365             if (requiresAA) {
366                *requiresAA = false;
367             }
368         } else if (isectRect.intersect(stackBounds, scalarQueryBounds)) {
369             // If the caller asked for tighter integer bounds we may be able to
370             // return kAllIn and give the bounds with no elements
371             if (tighterBounds) {
372                 isectRect.roundOut(tighterBounds);
373                 SkRect scalarTighterBounds = SkRect::Make(*tighterBounds);
374                 if (scalarTighterBounds == isectRect) {
375                     // the round-out didn't add any area outside the clip rect.
376                     if (requiresAA) {
377                         *requiresAA = false;
378                     }
379                     *initialState = GrReducedClip::kAllIn_InitialState;
380                     return;
381                 }
382             }
383             *initialState = kAllOut_InitialState;
384             // iior should only be true if aa/non-aa status matches among all elements.
385             SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
386             bool doAA = iter.prev()->isAA();
387             result->addToHead(isectRect, SkRegion::kReplace_Op, doAA);
388             if (requiresAA) {
389                 *requiresAA = doAA;
390             }
391         } else {
392             *initialState = kAllOut_InitialState;
393              if (requiresAA) {
394                 *requiresAA = false;
395              }
396         }
397         return;
398     } else {
399         if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
400             if (!SkRect::Intersects(stackBounds, scalarQueryBounds)) {
401                 *initialState = kAllOut_InitialState;
402                 if (requiresAA) {
403                    *requiresAA = false;
404                 }
405                 return;
406             }
407             if (tighterBounds) {
408                 SkIRect stackIBounds;
409                 stackBounds.roundOut(&stackIBounds);
410                 if (!tighterBounds->intersect(queryBounds, stackIBounds)) {
411                     SkASSERT(0);
412                     tighterBounds->setEmpty();
413                 }
414                 bounds = tighterBounds;
415             }
416         } else {
417             if (stackBounds.contains(scalarQueryBounds)) {
418                 *initialState = kAllOut_InitialState;
419                 // We know that the bounding box contains all the pixels that are outside the clip,
420                 // but we don't know that *all* the pixels in the box are outside the clip. So
421                 // proceed to walking the stack.
422             }
423             if (tighterBounds) {
424                 *tighterBounds = queryBounds;
425             }
426         }
427     }
428 
429     SkRect scalarBounds = SkRect::Make(*bounds);
430 
431     // Now that we have determined the bounds to use and filtered out the trivial cases, call the
432     // helper that actually walks the stack.
433     reduced_stack_walker(stack, scalarBounds, result, resultGenID, initialState, requiresAA);
434 
435     // The list that was computed in this function may be cached based on the gen id of the last
436     // element.
437     SkASSERT(SkClipStack::kInvalidGenID != *resultGenID);
438 }
439