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 (NULL == 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 SkNEW_INSERT_AT_LLIST_HEAD(result,
210 Element,
211 (queryBounds, SkRegion::kReverseDifference_Op, false));
212 } else {
213 Element* newElement = result->addToHead(*element);
214 if (newElement->isAA()) {
215 ++numAAElements;
216 }
217 // Intersecting an inverse shape is the same as differencing the non-inverse shape.
218 // Replacing with an inverse shape is the same as setting initialState=kAllIn and
219 // differencing the non-inverse shape.
220 bool isReplace = SkRegion::kReplace_Op == newElement->getOp();
221 if (newElement->isInverseFilled() &&
222 (SkRegion::kIntersect_Op == newElement->getOp() || isReplace)) {
223 newElement->invertShapeFillType();
224 newElement->setOp(SkRegion::kDifference_Op);
225 if (isReplace) {
226 SkASSERT(GrReducedClip::kAllOut_InitialState == *initialState);
227 *initialState = GrReducedClip::kAllIn_InitialState;
228 }
229 }
230 }
231 }
232 }
233
234 if ((GrReducedClip::kAllOut_InitialState == *initialState && !embiggens) ||
235 (GrReducedClip::kAllIn_InitialState == *initialState && !emsmallens)) {
236 result->reset();
237 } else {
238 Element* element = result->headIter().get();
239 while (element) {
240 bool skippable = false;
241 switch (element->getOp()) {
242 case SkRegion::kDifference_Op:
243 // subtracting from the empty set yields the empty set.
244 skippable = GrReducedClip::kAllOut_InitialState == *initialState;
245 break;
246 case SkRegion::kIntersect_Op:
247 // intersecting with the empty set yields the empty set
248 if (GrReducedClip::kAllOut_InitialState == *initialState) {
249 skippable = true;
250 } else {
251 // We can clear to zero and then simply draw the clip element.
252 *initialState = GrReducedClip::kAllOut_InitialState;
253 element->setOp(SkRegion::kReplace_Op);
254 }
255 break;
256 case SkRegion::kUnion_Op:
257 if (GrReducedClip::kAllIn_InitialState == *initialState) {
258 // unioning the infinite plane with anything is a no-op.
259 skippable = true;
260 } else {
261 // unioning the empty set with a shape is the shape.
262 element->setOp(SkRegion::kReplace_Op);
263 }
264 break;
265 case SkRegion::kXOR_Op:
266 if (GrReducedClip::kAllOut_InitialState == *initialState) {
267 // xor could be changed to diff in the kAllIn case, not sure it's a win.
268 element->setOp(SkRegion::kReplace_Op);
269 }
270 break;
271 case SkRegion::kReverseDifference_Op:
272 if (GrReducedClip::kAllIn_InitialState == *initialState) {
273 // subtracting the whole plane will yield the empty set.
274 skippable = true;
275 *initialState = GrReducedClip::kAllOut_InitialState;
276 } else {
277 // this picks up flips inserted in the backwards pass.
278 skippable = element->isInverseFilled() ?
279 !SkRect::Intersects(element->getBounds(), queryBounds) :
280 element->contains(queryBounds);
281 if (skippable) {
282 *initialState = GrReducedClip::kAllIn_InitialState;
283 } else {
284 element->setOp(SkRegion::kReplace_Op);
285 }
286 }
287 break;
288 case SkRegion::kReplace_Op:
289 skippable = false; // we would have skipped it in the backwards walk if we
290 // could've.
291 break;
292 default:
293 SkDEBUGFAIL("Unexpected op.");
294 break;
295 }
296 if (!skippable) {
297 break;
298 } else {
299 if (element->isAA()) {
300 --numAAElements;
301 }
302 result->popHead();
303 element = result->headIter().get();
304 }
305 }
306 }
307 if (requiresAA) {
308 *requiresAA = numAAElements > 0;
309 }
310
311 if (0 == result->count()) {
312 if (*initialState == GrReducedClip::kAllIn_InitialState) {
313 *resultGenID = SkClipStack::kWideOpenGenID;
314 } else {
315 *resultGenID = SkClipStack::kEmptyGenID;
316 }
317 }
318 }
319
320 /*
321 There are plenty of optimizations that could be added here. Maybe flips could be folded into
322 earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
323 for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
324 based on later intersect operations, and perhaps remove intersect-rects. We could optionally
325 take a rect in case the caller knows a bound on what is to be drawn through this clip.
326 */
ReduceClipStack(const SkClipStack & stack,const SkIRect & queryBounds,ElementList * result,int32_t * resultGenID,InitialState * initialState,SkIRect * tighterBounds,bool * requiresAA)327 void GrReducedClip::ReduceClipStack(const SkClipStack& stack,
328 const SkIRect& queryBounds,
329 ElementList* result,
330 int32_t* resultGenID,
331 InitialState* initialState,
332 SkIRect* tighterBounds,
333 bool* requiresAA) {
334 result->reset();
335
336 // The clip established by the element list might be cached based on the last
337 // generation id. When we make early returns, we do not know what was the generation
338 // id that lead to the state. Make a conservative guess.
339 *resultGenID = stack.getTopmostGenID();
340
341 if (stack.isWideOpen()) {
342 *initialState = kAllIn_InitialState;
343 return;
344 }
345
346
347 // We initially look at whether the bounds alone is sufficient. We also use the stack bounds to
348 // attempt to compute the tighterBounds.
349
350 SkClipStack::BoundsType stackBoundsType;
351 SkRect stackBounds;
352 bool iior;
353 stack.getBounds(&stackBounds, &stackBoundsType, &iior);
354
355 const SkIRect* bounds = &queryBounds;
356
357 SkRect scalarQueryBounds = SkRect::Make(queryBounds);
358
359 if (iior) {
360 SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
361 SkRect isectRect;
362 if (stackBounds.contains(scalarQueryBounds)) {
363 *initialState = GrReducedClip::kAllIn_InitialState;
364 if (tighterBounds) {
365 *tighterBounds = queryBounds;
366 }
367 if (requiresAA) {
368 *requiresAA = false;
369 }
370 } else if (isectRect.intersect(stackBounds, scalarQueryBounds)) {
371 // If the caller asked for tighter integer bounds we may be able to
372 // return kAllIn and give the bounds with no elements
373 if (tighterBounds) {
374 isectRect.roundOut(tighterBounds);
375 SkRect scalarTighterBounds = SkRect::Make(*tighterBounds);
376 if (scalarTighterBounds == isectRect) {
377 // the round-out didn't add any area outside the clip rect.
378 if (requiresAA) {
379 *requiresAA = false;
380 }
381 *initialState = GrReducedClip::kAllIn_InitialState;
382 return;
383 }
384 }
385 *initialState = kAllOut_InitialState;
386 // iior should only be true if aa/non-aa status matches among all elements.
387 SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
388 bool doAA = iter.prev()->isAA();
389 SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA));
390 if (requiresAA) {
391 *requiresAA = doAA;
392 }
393 } else {
394 *initialState = kAllOut_InitialState;
395 if (requiresAA) {
396 *requiresAA = false;
397 }
398 }
399 return;
400 } else {
401 if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
402 if (!SkRect::Intersects(stackBounds, scalarQueryBounds)) {
403 *initialState = kAllOut_InitialState;
404 if (requiresAA) {
405 *requiresAA = false;
406 }
407 return;
408 }
409 if (tighterBounds) {
410 SkIRect stackIBounds;
411 stackBounds.roundOut(&stackIBounds);
412 if (!tighterBounds->intersect(queryBounds, stackIBounds)) {
413 SkASSERT(0);
414 tighterBounds->setEmpty();
415 }
416 bounds = tighterBounds;
417 }
418 } else {
419 if (stackBounds.contains(scalarQueryBounds)) {
420 *initialState = kAllOut_InitialState;
421 if (requiresAA) {
422 *requiresAA = false;
423 }
424 return;
425 }
426 if (tighterBounds) {
427 *tighterBounds = queryBounds;
428 }
429 }
430 }
431
432 SkRect scalarBounds = SkRect::Make(*bounds);
433
434 // Now that we have determined the bounds to use and filtered out the trivial cases, call the
435 // helper that actually walks the stack.
436 reduced_stack_walker(stack, scalarBounds, result, resultGenID, initialState, requiresAA);
437
438 // The list that was computed in this function may be cached based on the gen id of the last
439 // element.
440 SkASSERT(SkClipStack::kInvalidGenID != *resultGenID);
441 }
442