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