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 */ 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 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
