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