1 /* 2 * Copyright 2011 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 "SkAtomics.h" 9 #include "SkCanvas.h" 10 #include "SkClipStack.h" 11 #include "SkPath.h" 12 #include "SkPathOps.h" 13 #include "SkClipOpPriv.h" 14 15 #include <new> 16 17 18 // 0-2 are reserved for invalid, empty & wide-open 19 static const int32_t kFirstUnreservedGenID = 3; 20 int32_t SkClipStack::gGenID = kFirstUnreservedGenID; 21 22 SkClipStack::Element::Element(const Element& that) { 23 switch (that.getDeviceSpaceType()) { 24 case DeviceSpaceType::kEmpty: 25 fDeviceSpaceRRect.setEmpty(); 26 fDeviceSpacePath.reset(); 27 break; 28 case DeviceSpaceType::kRect: // Rect uses rrect 29 case DeviceSpaceType::kRRect: 30 fDeviceSpacePath.reset(); 31 fDeviceSpaceRRect = that.fDeviceSpaceRRect; 32 break; 33 case DeviceSpaceType::kPath: 34 fDeviceSpacePath.set(that.getDeviceSpacePath()); 35 break; 36 } 37 38 fSaveCount = that.fSaveCount; 39 fOp = that.fOp; 40 fDeviceSpaceType = that.fDeviceSpaceType; 41 fDoAA = that.fDoAA; 42 fFiniteBoundType = that.fFiniteBoundType; 43 fFiniteBound = that.fFiniteBound; 44 fIsIntersectionOfRects = that.fIsIntersectionOfRects; 45 fGenID = that.fGenID; 46 } 47 48 bool SkClipStack::Element::operator== (const Element& element) const { 49 if (this == &element) { 50 return true; 51 } 52 if (fOp != element.fOp || fDeviceSpaceType != element.fDeviceSpaceType || 53 fDoAA != element.fDoAA || fSaveCount != element.fSaveCount) { 54 return false; 55 } 56 switch (fDeviceSpaceType) { 57 case DeviceSpaceType::kPath: 58 return this->getDeviceSpacePath() == element.getDeviceSpacePath(); 59 case DeviceSpaceType::kRRect: 60 return fDeviceSpaceRRect == element.fDeviceSpaceRRect; 61 case DeviceSpaceType::kRect: 62 return this->getDeviceSpaceRect() == element.getDeviceSpaceRect(); 63 case DeviceSpaceType::kEmpty: 64 return true; 65 default: 66 SkDEBUGFAIL("Unexpected type."); 67 return false; 68 } 69 } 70 71 const SkRect& SkClipStack::Element::getBounds() const { 72 static const SkRect kEmpty = {0, 0, 0, 0}; 73 switch (fDeviceSpaceType) { 74 case DeviceSpaceType::kRect: // fallthrough 75 case DeviceSpaceType::kRRect: 76 return fDeviceSpaceRRect.getBounds(); 77 case DeviceSpaceType::kPath: 78 return fDeviceSpacePath.get()->getBounds(); 79 case DeviceSpaceType::kEmpty: 80 return kEmpty; 81 default: 82 SkDEBUGFAIL("Unexpected type."); 83 return kEmpty; 84 } 85 } 86 87 bool SkClipStack::Element::contains(const SkRect& rect) const { 88 switch (fDeviceSpaceType) { 89 case DeviceSpaceType::kRect: 90 return this->getDeviceSpaceRect().contains(rect); 91 case DeviceSpaceType::kRRect: 92 return fDeviceSpaceRRect.contains(rect); 93 case DeviceSpaceType::kPath: 94 return fDeviceSpacePath.get()->conservativelyContainsRect(rect); 95 case DeviceSpaceType::kEmpty: 96 return false; 97 default: 98 SkDEBUGFAIL("Unexpected type."); 99 return false; 100 } 101 } 102 103 bool SkClipStack::Element::contains(const SkRRect& rrect) const { 104 switch (fDeviceSpaceType) { 105 case DeviceSpaceType::kRect: 106 return this->getDeviceSpaceRect().contains(rrect.getBounds()); 107 case DeviceSpaceType::kRRect: 108 // We don't currently have a generalized rrect-rrect containment. 109 return fDeviceSpaceRRect.contains(rrect.getBounds()) || rrect == fDeviceSpaceRRect; 110 case DeviceSpaceType::kPath: 111 return fDeviceSpacePath.get()->conservativelyContainsRect(rrect.getBounds()); 112 case DeviceSpaceType::kEmpty: 113 return false; 114 default: 115 SkDEBUGFAIL("Unexpected type."); 116 return false; 117 } 118 } 119 120 void SkClipStack::Element::invertShapeFillType() { 121 switch (fDeviceSpaceType) { 122 case DeviceSpaceType::kRect: 123 fDeviceSpacePath.init(); 124 fDeviceSpacePath.get()->addRect(this->getDeviceSpaceRect()); 125 fDeviceSpacePath.get()->setFillType(SkPath::kInverseEvenOdd_FillType); 126 fDeviceSpaceType = DeviceSpaceType::kPath; 127 break; 128 case DeviceSpaceType::kRRect: 129 fDeviceSpacePath.init(); 130 fDeviceSpacePath.get()->addRRect(fDeviceSpaceRRect); 131 fDeviceSpacePath.get()->setFillType(SkPath::kInverseEvenOdd_FillType); 132 fDeviceSpaceType = DeviceSpaceType::kPath; 133 break; 134 case DeviceSpaceType::kPath: 135 fDeviceSpacePath.get()->toggleInverseFillType(); 136 break; 137 case DeviceSpaceType::kEmpty: 138 // Should this set to an empty, inverse filled path? 139 break; 140 } 141 } 142 143 void SkClipStack::Element::initCommon(int saveCount, SkClipOp op, bool doAA) { 144 fSaveCount = saveCount; 145 fOp = op; 146 fDoAA = doAA; 147 // A default of inside-out and empty bounds means the bounds are effectively void as it 148 // indicates that nothing is known to be outside the clip. 149 fFiniteBoundType = kInsideOut_BoundsType; 150 fFiniteBound.setEmpty(); 151 fIsIntersectionOfRects = false; 152 fGenID = kInvalidGenID; 153 } 154 155 void SkClipStack::Element::initRect(int saveCount, const SkRect& rect, const SkMatrix& m, 156 SkClipOp op, bool doAA) { 157 if (m.rectStaysRect()) { 158 SkRect devRect; 159 m.mapRect(&devRect, rect); 160 fDeviceSpaceRRect.setRect(devRect); 161 fDeviceSpaceType = DeviceSpaceType::kRect; 162 this->initCommon(saveCount, op, doAA); 163 return; 164 } 165 SkPath path; 166 path.addRect(rect); 167 path.setIsVolatile(true); 168 this->initAsPath(saveCount, path, m, op, doAA); 169 } 170 171 void SkClipStack::Element::initRRect(int saveCount, const SkRRect& rrect, const SkMatrix& m, 172 SkClipOp op, bool doAA) { 173 if (rrect.transform(m, &fDeviceSpaceRRect)) { 174 SkRRect::Type type = fDeviceSpaceRRect.getType(); 175 if (SkRRect::kRect_Type == type || SkRRect::kEmpty_Type == type) { 176 fDeviceSpaceType = DeviceSpaceType::kRect; 177 } else { 178 fDeviceSpaceType = DeviceSpaceType::kRRect; 179 } 180 this->initCommon(saveCount, op, doAA); 181 return; 182 } 183 SkPath path; 184 path.addRRect(rrect); 185 path.setIsVolatile(true); 186 this->initAsPath(saveCount, path, m, op, doAA); 187 } 188 189 void SkClipStack::Element::initPath(int saveCount, const SkPath& path, const SkMatrix& m, 190 SkClipOp op, bool doAA) { 191 if (!path.isInverseFillType()) { 192 SkRect r; 193 if (path.isRect(&r)) { 194 this->initRect(saveCount, r, m, op, doAA); 195 return; 196 } 197 SkRect ovalRect; 198 if (path.isOval(&ovalRect)) { 199 SkRRect rrect; 200 rrect.setOval(ovalRect); 201 this->initRRect(saveCount, rrect, m, op, doAA); 202 return; 203 } 204 } 205 this->initAsPath(saveCount, path, m, op, doAA); 206 } 207 208 void SkClipStack::Element::initAsPath(int saveCount, const SkPath& path, const SkMatrix& m, 209 SkClipOp op, bool doAA) { 210 path.transform(m, fDeviceSpacePath.init()); 211 fDeviceSpacePath.get()->setIsVolatile(true); 212 fDeviceSpaceType = DeviceSpaceType::kPath; 213 this->initCommon(saveCount, op, doAA); 214 } 215 216 void SkClipStack::Element::asDeviceSpacePath(SkPath* path) const { 217 switch (fDeviceSpaceType) { 218 case DeviceSpaceType::kEmpty: 219 path->reset(); 220 path->setIsVolatile(true); 221 break; 222 case DeviceSpaceType::kRect: 223 path->reset(); 224 path->addRect(this->getDeviceSpaceRect()); 225 path->setIsVolatile(true); 226 break; 227 case DeviceSpaceType::kRRect: 228 path->reset(); 229 path->addRRect(fDeviceSpaceRRect); 230 path->setIsVolatile(true); 231 break; 232 case DeviceSpaceType::kPath: 233 *path = *fDeviceSpacePath.get(); 234 break; 235 } 236 path->setIsVolatile(true); 237 } 238 239 void SkClipStack::Element::setEmpty() { 240 fDeviceSpaceType = DeviceSpaceType::kEmpty; 241 fFiniteBound.setEmpty(); 242 fFiniteBoundType = kNormal_BoundsType; 243 fIsIntersectionOfRects = false; 244 fDeviceSpaceRRect.setEmpty(); 245 fDeviceSpacePath.reset(); 246 fGenID = kEmptyGenID; 247 SkDEBUGCODE(this->checkEmpty();) 248 } 249 250 void SkClipStack::Element::checkEmpty() const { 251 SkASSERT(fFiniteBound.isEmpty()); 252 SkASSERT(kNormal_BoundsType == fFiniteBoundType); 253 SkASSERT(!fIsIntersectionOfRects); 254 SkASSERT(kEmptyGenID == fGenID); 255 SkASSERT(fDeviceSpaceRRect.isEmpty()); 256 SkASSERT(!fDeviceSpacePath.isValid()); 257 } 258 259 bool SkClipStack::Element::canBeIntersectedInPlace(int saveCount, SkClipOp op) const { 260 if (DeviceSpaceType::kEmpty == fDeviceSpaceType && 261 (kDifference_SkClipOp == op || kIntersect_SkClipOp == op)) { 262 return true; 263 } 264 // Only clips within the same save/restore frame (as captured by 265 // the save count) can be merged 266 return fSaveCount == saveCount && 267 kIntersect_SkClipOp == op && 268 (kIntersect_SkClipOp == fOp || kReplace_SkClipOp == fOp); 269 } 270 271 bool SkClipStack::Element::rectRectIntersectAllowed(const SkRect& newR, bool newAA) const { 272 SkASSERT(DeviceSpaceType::kRect == fDeviceSpaceType); 273 274 if (fDoAA == newAA) { 275 // if the AA setting is the same there is no issue 276 return true; 277 } 278 279 if (!SkRect::Intersects(this->getDeviceSpaceRect(), newR)) { 280 // The calling code will correctly set the result to the empty clip 281 return true; 282 } 283 284 if (this->getDeviceSpaceRect().contains(newR)) { 285 // if the new rect carves out a portion of the old one there is no 286 // issue 287 return true; 288 } 289 290 // So either the two overlap in some complex manner or newR contains oldR. 291 // In the first, case the edges will require different AA. In the second, 292 // the AA setting that would be carried forward is incorrect (e.g., oldR 293 // is AA while newR is BW but since newR contains oldR, oldR will be 294 // drawn BW) since the new AA setting will predominate. 295 return false; 296 } 297 298 // a mirror of combineBoundsRevDiff 299 void SkClipStack::Element::combineBoundsDiff(FillCombo combination, const SkRect& prevFinite) { 300 switch (combination) { 301 case kInvPrev_InvCur_FillCombo: 302 // In this case the only pixels that can remain set 303 // are inside the current clip rect since the extensions 304 // to infinity of both clips cancel out and whatever 305 // is outside of the current clip is removed 306 fFiniteBoundType = kNormal_BoundsType; 307 break; 308 case kInvPrev_Cur_FillCombo: 309 // In this case the current op is finite so the only pixels 310 // that aren't set are whatever isn't set in the previous 311 // clip and whatever this clip carves out 312 fFiniteBound.join(prevFinite); 313 fFiniteBoundType = kInsideOut_BoundsType; 314 break; 315 case kPrev_InvCur_FillCombo: 316 // In this case everything outside of this clip's bound 317 // is erased, so the only pixels that can remain set 318 // occur w/in the intersection of the two finite bounds 319 if (!fFiniteBound.intersect(prevFinite)) { 320 fFiniteBound.setEmpty(); 321 fGenID = kEmptyGenID; 322 } 323 fFiniteBoundType = kNormal_BoundsType; 324 break; 325 case kPrev_Cur_FillCombo: 326 // The most conservative result bound is that of the 327 // prior clip. This could be wildly incorrect if the 328 // second clip either exactly matches the first clip 329 // (which should yield the empty set) or reduces the 330 // size of the prior bound (e.g., if the second clip 331 // exactly matched the bottom half of the prior clip). 332 // We ignore these two possibilities. 333 fFiniteBound = prevFinite; 334 break; 335 default: 336 SkDEBUGFAIL("SkClipStack::Element::combineBoundsDiff Invalid fill combination"); 337 break; 338 } 339 } 340 341 void SkClipStack::Element::combineBoundsXOR(int combination, const SkRect& prevFinite) { 342 343 switch (combination) { 344 case kInvPrev_Cur_FillCombo: // fall through 345 case kPrev_InvCur_FillCombo: 346 // With only one of the clips inverted the result will always 347 // extend to infinity. The only pixels that may be un-writeable 348 // lie within the union of the two finite bounds 349 fFiniteBound.join(prevFinite); 350 fFiniteBoundType = kInsideOut_BoundsType; 351 break; 352 case kInvPrev_InvCur_FillCombo: 353 // The only pixels that can survive are within the 354 // union of the two bounding boxes since the extensions 355 // to infinity of both clips cancel out 356 // fall through! 357 case kPrev_Cur_FillCombo: 358 // The most conservative bound for xor is the 359 // union of the two bounds. If the two clips exactly overlapped 360 // the xor could yield the empty set. Similarly the xor 361 // could reduce the size of the original clip's bound (e.g., 362 // if the second clip exactly matched the bottom half of the 363 // first clip). We ignore these two cases. 364 fFiniteBound.join(prevFinite); 365 fFiniteBoundType = kNormal_BoundsType; 366 break; 367 default: 368 SkDEBUGFAIL("SkClipStack::Element::combineBoundsXOR Invalid fill combination"); 369 break; 370 } 371 } 372 373 // a mirror of combineBoundsIntersection 374 void SkClipStack::Element::combineBoundsUnion(int combination, const SkRect& prevFinite) { 375 376 switch (combination) { 377 case kInvPrev_InvCur_FillCombo: 378 if (!fFiniteBound.intersect(prevFinite)) { 379 fFiniteBound.setEmpty(); 380 fGenID = kWideOpenGenID; 381 } 382 fFiniteBoundType = kInsideOut_BoundsType; 383 break; 384 case kInvPrev_Cur_FillCombo: 385 // The only pixels that won't be drawable are inside 386 // the prior clip's finite bound 387 fFiniteBound = prevFinite; 388 fFiniteBoundType = kInsideOut_BoundsType; 389 break; 390 case kPrev_InvCur_FillCombo: 391 // The only pixels that won't be drawable are inside 392 // this clip's finite bound 393 break; 394 case kPrev_Cur_FillCombo: 395 fFiniteBound.join(prevFinite); 396 break; 397 default: 398 SkDEBUGFAIL("SkClipStack::Element::combineBoundsUnion Invalid fill combination"); 399 break; 400 } 401 } 402 403 // a mirror of combineBoundsUnion 404 void SkClipStack::Element::combineBoundsIntersection(int combination, const SkRect& prevFinite) { 405 406 switch (combination) { 407 case kInvPrev_InvCur_FillCombo: 408 // The only pixels that aren't writable in this case 409 // occur in the union of the two finite bounds 410 fFiniteBound.join(prevFinite); 411 fFiniteBoundType = kInsideOut_BoundsType; 412 break; 413 case kInvPrev_Cur_FillCombo: 414 // In this case the only pixels that will remain writeable 415 // are within the current clip 416 break; 417 case kPrev_InvCur_FillCombo: 418 // In this case the only pixels that will remain writeable 419 // are with the previous clip 420 fFiniteBound = prevFinite; 421 fFiniteBoundType = kNormal_BoundsType; 422 break; 423 case kPrev_Cur_FillCombo: 424 if (!fFiniteBound.intersect(prevFinite)) { 425 this->setEmpty(); 426 } 427 break; 428 default: 429 SkDEBUGFAIL("SkClipStack::Element::combineBoundsIntersection Invalid fill combination"); 430 break; 431 } 432 } 433 434 // a mirror of combineBoundsDiff 435 void SkClipStack::Element::combineBoundsRevDiff(int combination, const SkRect& prevFinite) { 436 437 switch (combination) { 438 case kInvPrev_InvCur_FillCombo: 439 // The only pixels that can survive are in the 440 // previous bound since the extensions to infinity in 441 // both clips cancel out 442 fFiniteBound = prevFinite; 443 fFiniteBoundType = kNormal_BoundsType; 444 break; 445 case kInvPrev_Cur_FillCombo: 446 if (!fFiniteBound.intersect(prevFinite)) { 447 this->setEmpty(); 448 } else { 449 fFiniteBoundType = kNormal_BoundsType; 450 } 451 break; 452 case kPrev_InvCur_FillCombo: 453 fFiniteBound.join(prevFinite); 454 fFiniteBoundType = kInsideOut_BoundsType; 455 break; 456 case kPrev_Cur_FillCombo: 457 // Fall through - as with the kDifference_Op case, the 458 // most conservative result bound is the bound of the 459 // current clip. The prior clip could reduce the size of this 460 // bound (as in the kDifference_Op case) but we are ignoring 461 // those cases. 462 break; 463 default: 464 SkDEBUGFAIL("SkClipStack::Element::combineBoundsRevDiff Invalid fill combination"); 465 break; 466 } 467 } 468 469 void SkClipStack::Element::updateBoundAndGenID(const Element* prior) { 470 // We set this first here but we may overwrite it later if we determine that the clip is 471 // either wide-open or empty. 472 fGenID = GetNextGenID(); 473 474 // First, optimistically update the current Element's bound information 475 // with the current clip's bound 476 fIsIntersectionOfRects = false; 477 switch (fDeviceSpaceType) { 478 case DeviceSpaceType::kRect: 479 fFiniteBound = this->getDeviceSpaceRect(); 480 fFiniteBoundType = kNormal_BoundsType; 481 482 if (kReplace_SkClipOp == fOp || (kIntersect_SkClipOp == fOp && nullptr == prior) || 483 (kIntersect_SkClipOp == fOp && prior->fIsIntersectionOfRects && 484 prior->rectRectIntersectAllowed(this->getDeviceSpaceRect(), fDoAA))) { 485 fIsIntersectionOfRects = true; 486 } 487 break; 488 case DeviceSpaceType::kRRect: 489 fFiniteBound = fDeviceSpaceRRect.getBounds(); 490 fFiniteBoundType = kNormal_BoundsType; 491 break; 492 case DeviceSpaceType::kPath: 493 fFiniteBound = fDeviceSpacePath.get()->getBounds(); 494 495 if (fDeviceSpacePath.get()->isInverseFillType()) { 496 fFiniteBoundType = kInsideOut_BoundsType; 497 } else { 498 fFiniteBoundType = kNormal_BoundsType; 499 } 500 break; 501 case DeviceSpaceType::kEmpty: 502 SkDEBUGFAIL("We shouldn't get here with an empty element."); 503 break; 504 } 505 506 if (!fDoAA) { 507 fFiniteBound.set(SkScalarRoundToScalar(fFiniteBound.fLeft), 508 SkScalarRoundToScalar(fFiniteBound.fTop), 509 SkScalarRoundToScalar(fFiniteBound.fRight), 510 SkScalarRoundToScalar(fFiniteBound.fBottom)); 511 } 512 513 // Now determine the previous Element's bound information taking into 514 // account that there may be no previous clip 515 SkRect prevFinite; 516 SkClipStack::BoundsType prevType; 517 518 if (nullptr == prior) { 519 // no prior clip means the entire plane is writable 520 prevFinite.setEmpty(); // there are no pixels that cannot be drawn to 521 prevType = kInsideOut_BoundsType; 522 } else { 523 prevFinite = prior->fFiniteBound; 524 prevType = prior->fFiniteBoundType; 525 } 526 527 FillCombo combination = kPrev_Cur_FillCombo; 528 if (kInsideOut_BoundsType == fFiniteBoundType) { 529 combination = (FillCombo) (combination | 0x01); 530 } 531 if (kInsideOut_BoundsType == prevType) { 532 combination = (FillCombo) (combination | 0x02); 533 } 534 535 SkASSERT(kInvPrev_InvCur_FillCombo == combination || 536 kInvPrev_Cur_FillCombo == combination || 537 kPrev_InvCur_FillCombo == combination || 538 kPrev_Cur_FillCombo == combination); 539 540 // Now integrate with clip with the prior clips 541 switch (fOp) { 542 case kDifference_SkClipOp: 543 this->combineBoundsDiff(combination, prevFinite); 544 break; 545 case kXOR_SkClipOp: 546 this->combineBoundsXOR(combination, prevFinite); 547 break; 548 case kUnion_SkClipOp: 549 this->combineBoundsUnion(combination, prevFinite); 550 break; 551 case kIntersect_SkClipOp: 552 this->combineBoundsIntersection(combination, prevFinite); 553 break; 554 case kReverseDifference_SkClipOp: 555 this->combineBoundsRevDiff(combination, prevFinite); 556 break; 557 case kReplace_SkClipOp: 558 // Replace just ignores everything prior 559 // The current clip's bound information is already filled in 560 // so nothing to do 561 break; 562 default: 563 SkDebugf("SkClipOp error\n"); 564 SkASSERT(0); 565 break; 566 } 567 } 568 569 // This constant determines how many Element's are allocated together as a block in 570 // the deque. As such it needs to balance allocating too much memory vs. 571 // incurring allocation/deallocation thrashing. It should roughly correspond to 572 // the deepest save/restore stack we expect to see. 573 static const int kDefaultElementAllocCnt = 8; 574 575 SkClipStack::SkClipStack() 576 : fDeque(sizeof(Element), kDefaultElementAllocCnt) 577 , fSaveCount(0) { 578 } 579 580 SkClipStack::SkClipStack(void* storage, size_t size) 581 : fDeque(sizeof(Element), storage, size, kDefaultElementAllocCnt) 582 , fSaveCount(0) { 583 } 584 585 SkClipStack::SkClipStack(const SkClipStack& b) 586 : fDeque(sizeof(Element), kDefaultElementAllocCnt) { 587 *this = b; 588 } 589 590 SkClipStack::~SkClipStack() { 591 reset(); 592 } 593 594 SkClipStack& SkClipStack::operator=(const SkClipStack& b) { 595 if (this == &b) { 596 return *this; 597 } 598 reset(); 599 600 fSaveCount = b.fSaveCount; 601 SkDeque::F2BIter recIter(b.fDeque); 602 for (const Element* element = (const Element*)recIter.next(); 603 element != nullptr; 604 element = (const Element*)recIter.next()) { 605 new (fDeque.push_back()) Element(*element); 606 } 607 608 return *this; 609 } 610 611 bool SkClipStack::operator==(const SkClipStack& b) const { 612 if (this->getTopmostGenID() == b.getTopmostGenID()) { 613 return true; 614 } 615 if (fSaveCount != b.fSaveCount || 616 fDeque.count() != b.fDeque.count()) { 617 return false; 618 } 619 SkDeque::F2BIter myIter(fDeque); 620 SkDeque::F2BIter bIter(b.fDeque); 621 const Element* myElement = (const Element*)myIter.next(); 622 const Element* bElement = (const Element*)bIter.next(); 623 624 while (myElement != nullptr && bElement != nullptr) { 625 if (*myElement != *bElement) { 626 return false; 627 } 628 myElement = (const Element*)myIter.next(); 629 bElement = (const Element*)bIter.next(); 630 } 631 return myElement == nullptr && bElement == nullptr; 632 } 633 634 void SkClipStack::reset() { 635 // We used a placement new for each object in fDeque, so we're responsible 636 // for calling the destructor on each of them as well. 637 while (!fDeque.empty()) { 638 Element* element = (Element*)fDeque.back(); 639 element->~Element(); 640 fDeque.pop_back(); 641 } 642 643 fSaveCount = 0; 644 } 645 646 void SkClipStack::save() { 647 fSaveCount += 1; 648 } 649 650 void SkClipStack::restore() { 651 fSaveCount -= 1; 652 restoreTo(fSaveCount); 653 } 654 655 void SkClipStack::restoreTo(int saveCount) { 656 while (!fDeque.empty()) { 657 Element* element = (Element*)fDeque.back(); 658 if (element->fSaveCount <= saveCount) { 659 break; 660 } 661 element->~Element(); 662 fDeque.pop_back(); 663 } 664 } 665 666 SkRect SkClipStack::bounds(const SkIRect& deviceBounds) const { 667 // TODO: optimize this. 668 SkRect r; 669 SkClipStack::BoundsType bounds; 670 this->getBounds(&r, &bounds); 671 if (bounds == SkClipStack::kInsideOut_BoundsType) { 672 return SkRect::Make(deviceBounds); 673 } 674 return r.intersect(SkRect::Make(deviceBounds)) ? r : SkRect::MakeEmpty(); 675 } 676 677 // TODO: optimize this. 678 bool SkClipStack::isEmpty(const SkIRect& r) const { return this->bounds(r).isEmpty(); } 679 680 void SkClipStack::getBounds(SkRect* canvFiniteBound, 681 BoundsType* boundType, 682 bool* isIntersectionOfRects) const { 683 SkASSERT(canvFiniteBound && boundType); 684 685 Element* element = (Element*)fDeque.back(); 686 687 if (nullptr == element) { 688 // the clip is wide open - the infinite plane w/ no pixels un-writeable 689 canvFiniteBound->setEmpty(); 690 *boundType = kInsideOut_BoundsType; 691 if (isIntersectionOfRects) { 692 *isIntersectionOfRects = false; 693 } 694 return; 695 } 696 697 *canvFiniteBound = element->fFiniteBound; 698 *boundType = element->fFiniteBoundType; 699 if (isIntersectionOfRects) { 700 *isIntersectionOfRects = element->fIsIntersectionOfRects; 701 } 702 } 703 704 bool SkClipStack::internalQuickContains(const SkRect& rect) const { 705 706 Iter iter(*this, Iter::kTop_IterStart); 707 const Element* element = iter.prev(); 708 while (element != nullptr) { 709 if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp()) 710 return false; 711 if (element->isInverseFilled()) { 712 // Part of 'rect' could be trimmed off by the inverse-filled clip element 713 if (SkRect::Intersects(element->getBounds(), rect)) { 714 return false; 715 } 716 } else { 717 if (!element->contains(rect)) { 718 return false; 719 } 720 } 721 if (kReplace_SkClipOp == element->getOp()) { 722 break; 723 } 724 element = iter.prev(); 725 } 726 return true; 727 } 728 729 bool SkClipStack::internalQuickContains(const SkRRect& rrect) const { 730 731 Iter iter(*this, Iter::kTop_IterStart); 732 const Element* element = iter.prev(); 733 while (element != nullptr) { 734 if (kIntersect_SkClipOp != element->getOp() && kReplace_SkClipOp != element->getOp()) 735 return false; 736 if (element->isInverseFilled()) { 737 // Part of 'rrect' could be trimmed off by the inverse-filled clip element 738 if (SkRect::Intersects(element->getBounds(), rrect.getBounds())) { 739 return false; 740 } 741 } else { 742 if (!element->contains(rrect)) { 743 return false; 744 } 745 } 746 if (kReplace_SkClipOp == element->getOp()) { 747 break; 748 } 749 element = iter.prev(); 750 } 751 return true; 752 } 753 754 bool SkClipStack::asPath(SkPath *path) const { 755 bool isAA = false; 756 757 path->reset(); 758 path->setFillType(SkPath::kInverseEvenOdd_FillType); 759 760 SkClipStack::Iter iter(*this, SkClipStack::Iter::kBottom_IterStart); 761 while (const SkClipStack::Element* element = iter.next()) { 762 SkPath operand; 763 if (element->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kEmpty) { 764 element->asDeviceSpacePath(&operand); 765 } 766 767 SkClipOp elementOp = element->getOp(); 768 if (elementOp == kReplace_SkClipOp) { 769 *path = operand; 770 } else { 771 Op(*path, operand, (SkPathOp)elementOp, path); 772 } 773 774 // if the prev and curr clips disagree about aa -vs- not, favor the aa request. 775 // perhaps we need an API change to avoid this sort of mixed-signals about 776 // clipping. 777 isAA = (isAA || element->isAA()); 778 } 779 780 return isAA; 781 } 782 783 void SkClipStack::pushElement(const Element& element) { 784 // Use reverse iterator instead of back because Rect path may need previous 785 SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart); 786 Element* prior = (Element*) iter.prev(); 787 788 if (prior) { 789 if (prior->canBeIntersectedInPlace(fSaveCount, element.getOp())) { 790 switch (prior->fDeviceSpaceType) { 791 case Element::DeviceSpaceType::kEmpty: 792 SkDEBUGCODE(prior->checkEmpty();) 793 return; 794 case Element::DeviceSpaceType::kRect: 795 if (Element::DeviceSpaceType::kRect == element.getDeviceSpaceType()) { 796 if (prior->rectRectIntersectAllowed(element.getDeviceSpaceRect(), 797 element.isAA())) { 798 SkRect isectRect; 799 if (!isectRect.intersect(prior->getDeviceSpaceRect(), 800 element.getDeviceSpaceRect())) { 801 prior->setEmpty(); 802 return; 803 } 804 805 prior->fDeviceSpaceRRect.setRect(isectRect); 806 prior->fDoAA = element.isAA(); 807 Element* priorPrior = (Element*) iter.prev(); 808 prior->updateBoundAndGenID(priorPrior); 809 return; 810 } 811 break; 812 } 813 // fallthrough 814 default: 815 if (!SkRect::Intersects(prior->getBounds(), element.getBounds())) { 816 prior->setEmpty(); 817 return; 818 } 819 break; 820 } 821 } else if (kReplace_SkClipOp == element.getOp()) { 822 this->restoreTo(fSaveCount - 1); 823 prior = (Element*) fDeque.back(); 824 } 825 } 826 Element* newElement = new (fDeque.push_back()) Element(element); 827 newElement->updateBoundAndGenID(prior); 828 } 829 830 void SkClipStack::clipRRect(const SkRRect& rrect, const SkMatrix& matrix, SkClipOp op, 831 bool doAA) { 832 Element element(fSaveCount, rrect, matrix, op, doAA); 833 this->pushElement(element); 834 if (this->hasClipRestriction(op)) { 835 Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp, 836 false); 837 this->pushElement(restriction); 838 } 839 } 840 841 void SkClipStack::clipRect(const SkRect& rect, const SkMatrix& matrix, SkClipOp op, 842 bool doAA) { 843 Element element(fSaveCount, rect, matrix, op, doAA); 844 this->pushElement(element); 845 if (this->hasClipRestriction(op)) { 846 Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp, 847 false); 848 this->pushElement(restriction); 849 } 850 } 851 852 void SkClipStack::clipPath(const SkPath& path, const SkMatrix& matrix, SkClipOp op, 853 bool doAA) { 854 Element element(fSaveCount, path, matrix, op, doAA); 855 this->pushElement(element); 856 if (this->hasClipRestriction(op)) { 857 Element restriction(fSaveCount, fClipRestrictionRect, SkMatrix::I(), kIntersect_SkClipOp, 858 false); 859 this->pushElement(restriction); 860 } 861 } 862 863 void SkClipStack::clipEmpty() { 864 Element* element = (Element*) fDeque.back(); 865 866 if (element && element->canBeIntersectedInPlace(fSaveCount, kIntersect_SkClipOp)) { 867 element->setEmpty(); 868 } 869 new (fDeque.push_back()) Element(fSaveCount); 870 871 ((Element*)fDeque.back())->fGenID = kEmptyGenID; 872 } 873 874 /////////////////////////////////////////////////////////////////////////////// 875 876 SkClipStack::Iter::Iter() : fStack(nullptr) { 877 } 878 879 SkClipStack::Iter::Iter(const SkClipStack& stack, IterStart startLoc) 880 : fStack(&stack) { 881 this->reset(stack, startLoc); 882 } 883 884 const SkClipStack::Element* SkClipStack::Iter::next() { 885 return (const SkClipStack::Element*)fIter.next(); 886 } 887 888 const SkClipStack::Element* SkClipStack::Iter::prev() { 889 return (const SkClipStack::Element*)fIter.prev(); 890 } 891 892 const SkClipStack::Element* SkClipStack::Iter::skipToTopmost(SkClipOp op) { 893 894 if (nullptr == fStack) { 895 return nullptr; 896 } 897 898 fIter.reset(fStack->fDeque, SkDeque::Iter::kBack_IterStart); 899 900 const SkClipStack::Element* element = nullptr; 901 902 for (element = (const SkClipStack::Element*) fIter.prev(); 903 element; 904 element = (const SkClipStack::Element*) fIter.prev()) { 905 906 if (op == element->fOp) { 907 // The Deque's iterator is actually one pace ahead of the 908 // returned value. So while "element" is the element we want to 909 // return, the iterator is actually pointing at (and will 910 // return on the next "next" or "prev" call) the element 911 // in front of it in the deque. Bump the iterator forward a 912 // step so we get the expected result. 913 if (nullptr == fIter.next()) { 914 // The reverse iterator has run off the front of the deque 915 // (i.e., the "op" clip is the first clip) and can't 916 // recover. Reset the iterator to start at the front. 917 fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart); 918 } 919 break; 920 } 921 } 922 923 if (nullptr == element) { 924 // There were no "op" clips 925 fIter.reset(fStack->fDeque, SkDeque::Iter::kFront_IterStart); 926 } 927 928 return this->next(); 929 } 930 931 void SkClipStack::Iter::reset(const SkClipStack& stack, IterStart startLoc) { 932 fStack = &stack; 933 fIter.reset(stack.fDeque, static_cast<SkDeque::Iter::IterStart>(startLoc)); 934 } 935 936 // helper method 937 void SkClipStack::getConservativeBounds(int offsetX, 938 int offsetY, 939 int maxWidth, 940 int maxHeight, 941 SkRect* devBounds, 942 bool* isIntersectionOfRects) const { 943 SkASSERT(devBounds); 944 945 devBounds->setLTRB(0, 0, 946 SkIntToScalar(maxWidth), SkIntToScalar(maxHeight)); 947 948 SkRect temp; 949 SkClipStack::BoundsType boundType; 950 951 // temp starts off in canvas space here 952 this->getBounds(&temp, &boundType, isIntersectionOfRects); 953 if (SkClipStack::kInsideOut_BoundsType == boundType) { 954 return; 955 } 956 957 // but is converted to device space here 958 temp.offset(SkIntToScalar(offsetX), SkIntToScalar(offsetY)); 959 960 if (!devBounds->intersect(temp)) { 961 devBounds->setEmpty(); 962 } 963 } 964 965 bool SkClipStack::isRRect(const SkRect& bounds, SkRRect* rrect, bool* aa) const { 966 // We limit to 5 elements. This means the back element will be bounds checked at most 4 times if 967 // it is an rrect. 968 int cnt = fDeque.count(); 969 if (!cnt || cnt > 5) { 970 return false; 971 } 972 const Element* back = static_cast<const Element*>(fDeque.back()); 973 if (back->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kRect && 974 back->getDeviceSpaceType() != SkClipStack::Element::DeviceSpaceType::kRRect) { 975 return false; 976 } 977 if (back->getOp() == kReplace_SkClipOp) { 978 *rrect = back->asDeviceSpaceRRect(); 979 *aa = back->isAA(); 980 return true; 981 } 982 983 if (back->getOp() == kIntersect_SkClipOp) { 984 SkRect backBounds; 985 if (!backBounds.intersect(bounds, back->asDeviceSpaceRRect().rect())) { 986 return false; 987 } 988 if (cnt > 1) { 989 SkDeque::Iter iter(fDeque, SkDeque::Iter::kBack_IterStart); 990 SkAssertResult(static_cast<const Element*>(iter.prev()) == back); 991 while (const Element* prior = (const Element*)iter.prev()) { 992 if ((prior->getOp() != kIntersect_SkClipOp && 993 prior->getOp() != kReplace_SkClipOp) || 994 !prior->contains(backBounds)) { 995 return false; 996 } 997 if (prior->getOp() == kReplace_SkClipOp) { 998 break; 999 } 1000 } 1001 } 1002 *rrect = back->asDeviceSpaceRRect(); 1003 *aa = back->isAA(); 1004 return true; 1005 } 1006 return false; 1007 } 1008 1009 uint32_t SkClipStack::GetNextGenID() { 1010 uint32_t id; 1011 do { 1012 id = static_cast<uint32_t>(sk_atomic_inc(&gGenID)); 1013 } while (id < kFirstUnreservedGenID); 1014 return id; 1015 } 1016 1017 uint32_t SkClipStack::getTopmostGenID() const { 1018 if (fDeque.empty()) { 1019 return kWideOpenGenID; 1020 } 1021 1022 const Element* back = static_cast<const Element*>(fDeque.back()); 1023 if (kInsideOut_BoundsType == back->fFiniteBoundType && back->fFiniteBound.isEmpty()) { 1024 return kWideOpenGenID; 1025 } 1026 1027 return back->getGenID(); 1028 } 1029 1030 #ifdef SK_DEBUG 1031 void SkClipStack::Element::dump() const { 1032 static const char* kTypeStrings[] = { 1033 "empty", 1034 "rect", 1035 "rrect", 1036 "path" 1037 }; 1038 static_assert(0 == static_cast<int>(DeviceSpaceType::kEmpty), "enum mismatch"); 1039 static_assert(1 == static_cast<int>(DeviceSpaceType::kRect), "enum mismatch"); 1040 static_assert(2 == static_cast<int>(DeviceSpaceType::kRRect), "enum mismatch"); 1041 static_assert(3 == static_cast<int>(DeviceSpaceType::kPath), "enum mismatch"); 1042 static_assert(SK_ARRAY_COUNT(kTypeStrings) == kTypeCnt, "enum mismatch"); 1043 1044 static const char* kOpStrings[] = { 1045 "difference", 1046 "intersect", 1047 "union", 1048 "xor", 1049 "reverse-difference", 1050 "replace", 1051 }; 1052 static_assert(0 == static_cast<int>(kDifference_SkClipOp), "enum mismatch"); 1053 static_assert(1 == static_cast<int>(kIntersect_SkClipOp), "enum mismatch"); 1054 static_assert(2 == static_cast<int>(kUnion_SkClipOp), "enum mismatch"); 1055 static_assert(3 == static_cast<int>(kXOR_SkClipOp), "enum mismatch"); 1056 static_assert(4 == static_cast<int>(kReverseDifference_SkClipOp), "enum mismatch"); 1057 static_assert(5 == static_cast<int>(kReplace_SkClipOp), "enum mismatch"); 1058 static_assert(SK_ARRAY_COUNT(kOpStrings) == SkRegion::kOpCnt, "enum mismatch"); 1059 1060 SkDebugf("Type: %s, Op: %s, AA: %s, Save Count: %d\n", kTypeStrings[(int)fDeviceSpaceType], 1061 kOpStrings[static_cast<int>(fOp)], (fDoAA ? "yes" : "no"), fSaveCount); 1062 switch (fDeviceSpaceType) { 1063 case DeviceSpaceType::kEmpty: 1064 SkDebugf("\n"); 1065 break; 1066 case DeviceSpaceType::kRect: 1067 this->getDeviceSpaceRect().dump(); 1068 SkDebugf("\n"); 1069 break; 1070 case DeviceSpaceType::kRRect: 1071 this->getDeviceSpaceRRect().dump(); 1072 SkDebugf("\n"); 1073 break; 1074 case DeviceSpaceType::kPath: 1075 this->getDeviceSpacePath().dump(nullptr, true, false); 1076 break; 1077 } 1078 } 1079 1080 void SkClipStack::dump() const { 1081 B2TIter iter(*this); 1082 const Element* e; 1083 while ((e = iter.next())) { 1084 e->dump(); 1085 SkDebugf("\n"); 1086 } 1087 } 1088 #endif 1089
