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