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