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 #ifndef SkClipStack_DEFINED 9 #define SkClipStack_DEFINED 10 11 #include "../private/SkMessageBus.h" 12 #include "SkCanvas.h" 13 #include "SkClipOpPriv.h" 14 #include "SkDeque.h" 15 #include "SkPath.h" 16 #include "SkRRect.h" 17 #include "SkRect.h" 18 #include "SkRegion.h" 19 #include "SkTLazy.h" 20 21 #if SK_SUPPORT_GPU 22 #include "GrResourceKey.h" 23 #endif 24 25 // Because a single save/restore state can have multiple clips, this class 26 // stores the stack depth (fSaveCount) and clips (fDeque) separately. 27 // Each clip in fDeque stores the stack state to which it belongs 28 // (i.e., the fSaveCount in force when it was added). Restores are thus 29 // implemented by removing clips from fDeque that have an fSaveCount larger 30 // then the freshly decremented count. 31 class SkClipStack { 32 public: 33 enum BoundsType { 34 // The bounding box contains all the pixels that can be written to 35 kNormal_BoundsType, 36 // The bounding box contains all the pixels that cannot be written to. 37 // The real bound extends out to infinity and all the pixels outside 38 // of the bound can be written to. Note that some of the pixels inside 39 // the bound may also be writeable but all pixels that cannot be 40 // written to are guaranteed to be inside. 41 kInsideOut_BoundsType 42 }; 43 44 /** 45 * An element of the clip stack. It represents a shape combined with the prevoius clip using a 46 * set operator. Each element can be antialiased or not. 47 */ 48 class Element { 49 public: 50 /** This indicates the shape type of the clip element in device space. */ 51 enum class DeviceSpaceType { 52 //!< This element makes the clip empty (regardless of previous elements). 53 kEmpty, 54 //!< This element combines a device space rect with the current clip. 55 kRect, 56 //!< This element combines a device space round-rect with the current clip. 57 kRRect, 58 //!< This element combines a device space path with the current clip. 59 kPath, 60 61 kLastType = kPath 62 }; 63 static const int kTypeCnt = (int)DeviceSpaceType::kLastType + 1; 64 65 Element() { 66 this->initCommon(0, kReplace_SkClipOp, false); 67 this->setEmpty(); 68 } 69 70 Element(const Element&); 71 72 Element(const SkRect& rect, const SkMatrix& m, SkClipOp op, bool doAA) { 73 this->initRect(0, rect, m, op, doAA); 74 } 75 76 Element(const SkRRect& rrect, const SkMatrix& m, SkClipOp op, bool doAA) { 77 this->initRRect(0, rrect, m, op, doAA); 78 } 79 80 Element(const SkPath& path, const SkMatrix& m, SkClipOp op, bool doAA) { 81 this->initPath(0, path, m, op, doAA); 82 } 83 84 ~Element() { 85 #if SK_SUPPORT_GPU 86 for (int i = 0; i < fMessages.count(); ++i) { 87 SkMessageBus<GrUniqueKeyInvalidatedMessage>::Post(*fMessages[i]); 88 } 89 #endif 90 } 91 92 bool operator== (const Element& element) const; 93 bool operator!= (const Element& element) const { return !(*this == element); } 94 95 //!< Call to get the type of the clip element. 96 DeviceSpaceType getDeviceSpaceType() const { return fDeviceSpaceType; } 97 98 //!< Call to get the save count associated with this clip element. 99 int getSaveCount() const { return fSaveCount; } 100 101 //!< Call if getDeviceSpaceType() is kPath to get the path. 102 const SkPath& getDeviceSpacePath() const { 103 SkASSERT(DeviceSpaceType::kPath == fDeviceSpaceType); 104 return *fDeviceSpacePath.get(); 105 } 106 107 //!< Call if getDeviceSpaceType() is kRRect to get the round-rect. 108 const SkRRect& getDeviceSpaceRRect() const { 109 SkASSERT(DeviceSpaceType::kRRect == fDeviceSpaceType); 110 return fDeviceSpaceRRect; 111 } 112 113 //!< Call if getDeviceSpaceType() is kRect to get the rect. 114 const SkRect& getDeviceSpaceRect() const { 115 SkASSERT(DeviceSpaceType::kRect == fDeviceSpaceType && 116 (fDeviceSpaceRRect.isRect() || fDeviceSpaceRRect.isEmpty())); 117 return fDeviceSpaceRRect.getBounds(); 118 } 119 120 //!< Call if getDeviceSpaceType() is not kEmpty to get the set operation used to combine 121 //!< this element. 122 SkClipOp getOp() const { return fOp; } 123 124 //!< Call to get the element as a path, regardless of its type. 125 void asDeviceSpacePath(SkPath* path) const; 126 127 //!< Call if getType() is not kPath to get the element as a round rect. 128 const SkRRect& asDeviceSpaceRRect() const { 129 SkASSERT(DeviceSpaceType::kPath != fDeviceSpaceType); 130 return fDeviceSpaceRRect; 131 } 132 133 /** If getType() is not kEmpty this indicates whether the clip shape should be anti-aliased 134 when it is rasterized. */ 135 bool isAA() const { return fDoAA; } 136 137 //!< Inverts the fill of the clip shape. Note that a kEmpty element remains kEmpty. 138 void invertShapeFillType(); 139 140 //!< Sets the set operation represented by the element. 141 void setOp(SkClipOp op) { fOp = op; } 142 143 /** The GenID can be used by clip stack clients to cache representations of the clip. The 144 ID corresponds to the set of clip elements up to and including this element within the 145 stack not to the element itself. That is the same clip path in different stacks will 146 have a different ID since the elements produce different clip result in the context of 147 their stacks. */ 148 uint32_t getGenID() const { SkASSERT(kInvalidGenID != fGenID); return fGenID; } 149 150 /** 151 * Gets the bounds of the clip element, either the rect or path bounds. (Whether the shape 152 * is inverse filled is not considered.) 153 */ 154 const SkRect& getBounds() const; 155 156 /** 157 * Conservatively checks whether the clip shape contains the rect/rrect. (Whether the shape 158 * is inverse filled is not considered.) 159 */ 160 bool contains(const SkRect& rect) const; 161 bool contains(const SkRRect& rrect) const; 162 163 /** 164 * Is the clip shape inverse filled. 165 */ 166 bool isInverseFilled() const { 167 return DeviceSpaceType::kPath == fDeviceSpaceType && 168 fDeviceSpacePath.get()->isInverseFillType(); 169 } 170 171 #ifdef SK_DEBUG 172 /** 173 * Dumps the element to SkDebugf. This is intended for Skia development debugging 174 * Don't rely on the existence of this function or the formatting of its output. 175 */ 176 void dump() const; 177 #endif 178 179 #if SK_SUPPORT_GPU 180 /** 181 * This is used to purge any GPU resource cache items that become unreachable when 182 * the element is destroyed because their key is based on this element's gen ID. 183 */ 184 void addResourceInvalidationMessage( 185 std::unique_ptr<GrUniqueKeyInvalidatedMessage> msg) const { 186 fMessages.emplace_back(std::move(msg)); 187 } 188 #endif 189 190 private: 191 friend class SkClipStack; 192 193 SkTLazy<SkPath> fDeviceSpacePath; 194 SkRRect fDeviceSpaceRRect; 195 int fSaveCount; // save count of stack when this element was added. 196 SkClipOp fOp; 197 DeviceSpaceType fDeviceSpaceType; 198 bool fDoAA; 199 200 /* fFiniteBoundType and fFiniteBound are used to incrementally update the clip stack's 201 bound. When fFiniteBoundType is kNormal_BoundsType, fFiniteBound represents the 202 conservative bounding box of the pixels that aren't clipped (i.e., any pixels that can be 203 drawn to are inside the bound). When fFiniteBoundType is kInsideOut_BoundsType (which 204 occurs when a clip is inverse filled), fFiniteBound represents the conservative bounding 205 box of the pixels that _are_ clipped (i.e., any pixels that cannot be drawn to are inside 206 the bound). When fFiniteBoundType is kInsideOut_BoundsType the actual bound is the 207 infinite plane. This behavior of fFiniteBoundType and fFiniteBound is required so that we 208 can capture the cancelling out of the extensions to infinity when two inverse filled 209 clips are Booleaned together. */ 210 SkClipStack::BoundsType fFiniteBoundType; 211 SkRect fFiniteBound; 212 213 // When element is applied to the previous elements in the stack is the result known to be 214 // equivalent to a single rect intersection? IIOW, is the clip effectively a rectangle. 215 bool fIsIntersectionOfRects; 216 217 uint32_t fGenID; 218 #if SK_SUPPORT_GPU 219 mutable SkTArray<std::unique_ptr<GrUniqueKeyInvalidatedMessage>> fMessages; 220 #endif 221 Element(int saveCount) { 222 this->initCommon(saveCount, kReplace_SkClipOp, false); 223 this->setEmpty(); 224 } 225 226 Element(int saveCount, const SkRRect& rrect, const SkMatrix& m, SkClipOp op, bool doAA) { 227 this->initRRect(saveCount, rrect, m, op, doAA); 228 } 229 230 Element(int saveCount, const SkRect& rect, const SkMatrix& m, SkClipOp op, bool doAA) { 231 this->initRect(saveCount, rect, m, op, doAA); 232 } 233 234 Element(int saveCount, const SkPath& path, const SkMatrix& m, SkClipOp op, bool doAA) { 235 this->initPath(saveCount, path, m, op, doAA); 236 } 237 238 void initCommon(int saveCount, SkClipOp op, bool doAA); 239 void initRect(int saveCount, const SkRect&, const SkMatrix&, SkClipOp, bool doAA); 240 void initRRect(int saveCount, const SkRRect&, const SkMatrix&, SkClipOp, bool doAA); 241 void initPath(int saveCount, const SkPath&, const SkMatrix&, SkClipOp, bool doAA); 242 void initAsPath(int saveCount, const SkPath&, const SkMatrix&, SkClipOp, bool doAA); 243 244 void setEmpty(); 245 246 // All Element methods below are only used within SkClipStack.cpp 247 inline void checkEmpty() const; 248 inline bool canBeIntersectedInPlace(int saveCount, SkClipOp op) const; 249 /* This method checks to see if two rect clips can be safely merged into one. The issue here 250 is that to be strictly correct all the edges of the resulting rect must have the same 251 anti-aliasing. */ 252 bool rectRectIntersectAllowed(const SkRect& newR, bool newAA) const; 253 /** Determines possible finite bounds for the Element given the previous element of the 254 stack */ 255 void updateBoundAndGenID(const Element* prior); 256 // The different combination of fill & inverse fill when combining bounding boxes 257 enum FillCombo { 258 kPrev_Cur_FillCombo, 259 kPrev_InvCur_FillCombo, 260 kInvPrev_Cur_FillCombo, 261 kInvPrev_InvCur_FillCombo 262 }; 263 // per-set operation functions used by updateBoundAndGenID(). 264 inline void combineBoundsDiff(FillCombo combination, const SkRect& prevFinite); 265 inline void combineBoundsXOR(int combination, const SkRect& prevFinite); 266 inline void combineBoundsUnion(int combination, const SkRect& prevFinite); 267 inline void combineBoundsIntersection(int combination, const SkRect& prevFinite); 268 inline void combineBoundsRevDiff(int combination, const SkRect& prevFinite); 269 }; 270 271 SkClipStack(); 272 SkClipStack(void* storage, size_t size); 273 SkClipStack(const SkClipStack& b); 274 ~SkClipStack(); 275 276 SkClipStack& operator=(const SkClipStack& b); 277 bool operator==(const SkClipStack& b) const; 278 bool operator!=(const SkClipStack& b) const { return !(*this == b); } 279 280 void reset(); 281 282 int getSaveCount() const { return fSaveCount; } 283 void save(); 284 void restore(); 285 286 class AutoRestore { 287 public: 288 AutoRestore(SkClipStack* cs, bool doSave) 289 : fCS(cs), fSaveCount(cs->getSaveCount()) 290 { 291 if (doSave) { 292 fCS->save(); 293 } 294 } 295 ~AutoRestore() { 296 SkASSERT(fCS->getSaveCount() >= fSaveCount); // no underflow 297 while (fCS->getSaveCount() > fSaveCount) { 298 fCS->restore(); 299 } 300 } 301 302 private: 303 SkClipStack* fCS; 304 const int fSaveCount; 305 }; 306 307 /** 308 * getBounds places the current finite bound in its first parameter. In its 309 * second, it indicates which kind of bound is being returned. If 310 * 'canvFiniteBound' is a normal bounding box then it encloses all writeable 311 * pixels. If 'canvFiniteBound' is an inside out bounding box then it 312 * encloses all the un-writeable pixels and the true/normal bound is the 313 * infinite plane. isIntersectionOfRects is an optional parameter 314 * that is true if 'canvFiniteBound' resulted from an intersection of rects. 315 */ 316 void getBounds(SkRect* canvFiniteBound, 317 BoundsType* boundType, 318 bool* isIntersectionOfRects = nullptr) const; 319 320 SkRect bounds(const SkIRect& deviceBounds) const; 321 bool isEmpty(const SkIRect& deviceBounds) const; 322 323 /** 324 * Returns true if the input (r)rect in device space is entirely contained 325 * by the clip. A return value of false does not guarantee that the (r)rect 326 * is not contained by the clip. 327 */ 328 bool quickContains(const SkRect& devRect) const { 329 return this->isWideOpen() || this->internalQuickContains(devRect); 330 } 331 332 bool quickContains(const SkRRect& devRRect) const { 333 return this->isWideOpen() || this->internalQuickContains(devRRect); 334 } 335 336 /** 337 * Flattens the clip stack into a single SkPath. Returns true if any of 338 * the clip stack components requires anti-aliasing. 339 */ 340 bool asPath(SkPath* path) const; 341 342 void clipDevRect(const SkIRect& ir, SkClipOp op) { 343 SkRect r; 344 r.set(ir); 345 this->clipRect(r, SkMatrix::I(), op, false); 346 } 347 void clipRect(const SkRect&, const SkMatrix& matrix, SkClipOp, bool doAA); 348 void clipRRect(const SkRRect&, const SkMatrix& matrix, SkClipOp, bool doAA); 349 void clipPath(const SkPath&, const SkMatrix& matrix, SkClipOp, bool doAA); 350 // An optimized version of clipDevRect(emptyRect, kIntersect, ...) 351 void clipEmpty(); 352 void setDeviceClipRestriction(const SkIRect& rect) { 353 fClipRestrictionRect = SkRect::Make(rect); 354 } 355 356 /** 357 * isWideOpen returns true if the clip state corresponds to the infinite 358 * plane (i.e., draws are not limited at all) 359 */ 360 bool isWideOpen() const { return this->getTopmostGenID() == kWideOpenGenID; } 361 362 /** 363 * This method quickly and conservatively determines whether the entire stack is equivalent to 364 * intersection with a rrect given a bounds, where the rrect must not contain the entire bounds. 365 * 366 * @param bounds A bounds on what will be drawn through the clip. The clip only need be 367 * equivalent to a intersection with a rrect for draws within the bounds. The 368 * returned rrect must intersect the bounds but need not be contained by the 369 * bounds. 370 * @param rrect If return is true rrect will contain the rrect equivalent to the stack. 371 * @param aa If return is true aa will indicate whether the equivalent rrect clip is 372 * antialiased. 373 * @return true if the stack is equivalent to a single rrect intersect clip, false otherwise. 374 */ 375 bool isRRect(const SkRect& bounds, SkRRect* rrect, bool* aa) const; 376 377 /** 378 * The generation ID has three reserved values to indicate special 379 * (potentially ignorable) cases 380 */ 381 static const uint32_t kInvalidGenID = 0; //!< Invalid id that is never returned by 382 //!< SkClipStack. Useful when caching clips 383 //!< based on GenID. 384 static const uint32_t kEmptyGenID = 1; // no pixels writeable 385 static const uint32_t kWideOpenGenID = 2; // all pixels writeable 386 387 uint32_t getTopmostGenID() const; 388 389 #ifdef SK_DEBUG 390 /** 391 * Dumps the contents of the clip stack to SkDebugf. This is intended for Skia development 392 * debugging. Don't rely on the existence of this function or the formatting of its output. 393 */ 394 void dump() const; 395 #endif 396 397 public: 398 class Iter { 399 public: 400 enum IterStart { 401 kBottom_IterStart = SkDeque::Iter::kFront_IterStart, 402 kTop_IterStart = SkDeque::Iter::kBack_IterStart 403 }; 404 405 /** 406 * Creates an uninitialized iterator. Must be reset() 407 */ 408 Iter(); 409 410 Iter(const SkClipStack& stack, IterStart startLoc); 411 412 /** 413 * Return the clip element for this iterator. If next()/prev() returns NULL, then the 414 * iterator is done. 415 */ 416 const Element* next(); 417 const Element* prev(); 418 419 /** 420 * Moves the iterator to the topmost element with the specified RegionOp and returns that 421 * element. If no clip element with that op is found, the first element is returned. 422 */ 423 const Element* skipToTopmost(SkClipOp op); 424 425 /** 426 * Restarts the iterator on a clip stack. 427 */ 428 void reset(const SkClipStack& stack, IterStart startLoc); 429 430 private: 431 const SkClipStack* fStack; 432 SkDeque::Iter fIter; 433 }; 434 435 /** 436 * The B2TIter iterates from the bottom of the stack to the top. 437 * It inherits privately from Iter to prevent access to reverse iteration. 438 */ 439 class B2TIter : private Iter { 440 public: 441 B2TIter() {} 442 443 /** 444 * Wrap Iter's 2 parameter ctor to force initialization to the 445 * beginning of the deque/bottom of the stack 446 */ 447 B2TIter(const SkClipStack& stack) 448 : INHERITED(stack, kBottom_IterStart) { 449 } 450 451 using Iter::next; 452 453 /** 454 * Wrap Iter::reset to force initialization to the 455 * beginning of the deque/bottom of the stack 456 */ 457 void reset(const SkClipStack& stack) { 458 this->INHERITED::reset(stack, kBottom_IterStart); 459 } 460 461 private: 462 463 typedef Iter INHERITED; 464 }; 465 466 /** 467 * GetConservativeBounds returns a conservative bound of the current clip. 468 * Since this could be the infinite plane (if inverse fills were involved) the 469 * maxWidth and maxHeight parameters can be used to limit the returned bound 470 * to the expected drawing area. Similarly, the offsetX and offsetY parameters 471 * allow the caller to offset the returned bound to account for translated 472 * drawing areas (i.e., those resulting from a saveLayer). For finite bounds, 473 * the translation (+offsetX, +offsetY) is applied before the clamp to the 474 * maximum rectangle: [0,maxWidth) x [0,maxHeight). 475 * isIntersectionOfRects is an optional parameter that is true when 476 * 'devBounds' is the result of an intersection of rects. In this case 477 * 'devBounds' is the exact answer/clip. 478 */ 479 void getConservativeBounds(int offsetX, 480 int offsetY, 481 int maxWidth, 482 int maxHeight, 483 SkRect* devBounds, 484 bool* isIntersectionOfRects = nullptr) const; 485 486 private: 487 friend class Iter; 488 489 SkDeque fDeque; 490 int fSaveCount; 491 492 // Generation ID for the clip stack. This is incremented for each 493 // clipDevRect and clipDevPath call. 0 is reserved to indicate an 494 // invalid ID. 495 static int32_t gGenID; 496 SkRect fClipRestrictionRect = SkRect::MakeEmpty(); 497 498 bool internalQuickContains(const SkRect& devRect) const; 499 bool internalQuickContains(const SkRRect& devRRect) const; 500 501 /** 502 * Helper for clipDevPath, etc. 503 */ 504 void pushElement(const Element& element); 505 506 /** 507 * Restore the stack back to the specified save count. 508 */ 509 void restoreTo(int saveCount); 510 511 inline bool hasClipRestriction(SkClipOp op) { 512 return op >= kUnion_SkClipOp && !fClipRestrictionRect.isEmpty(); 513 } 514 515 /** 516 * Return the next unique generation ID. 517 */ 518 static uint32_t GetNextGenID(); 519 }; 520 521 #endif 522