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