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