michael@0: 
michael@0: /*
michael@0:  * Copyright 2011 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: #ifndef SkClipStack_DEFINED
michael@0: #define SkClipStack_DEFINED
michael@0: 
michael@0: #include "SkDeque.h"
michael@0: #include "SkPath.h"
michael@0: #include "SkRect.h"
michael@0: #include "SkRRect.h"
michael@0: #include "SkRegion.h"
michael@0: #include "SkTDArray.h"
michael@0: #include "SkTLazy.h"
michael@0: 
michael@0: 
michael@0: // Because a single save/restore state can have multiple clips, this class
michael@0: // stores the stack depth (fSaveCount) and clips (fDeque) separately.
michael@0: // Each clip in fDeque stores the stack state to which it belongs
michael@0: // (i.e., the fSaveCount in force when it was added). Restores are thus
michael@0: // implemented by removing clips from fDeque that have an fSaveCount larger
michael@0: // then the freshly decremented count.
michael@0: class SK_API SkClipStack {
michael@0: public:
michael@0:     enum BoundsType {
michael@0:         // The bounding box contains all the pixels that can be written to
michael@0:         kNormal_BoundsType,
michael@0:         // The bounding box contains all the pixels that cannot be written to.
michael@0:         // The real bound extends out to infinity and all the pixels outside
michael@0:         // of the bound can be written to. Note that some of the pixels inside
michael@0:         // the bound may also be writeable but all pixels that cannot be
michael@0:         // written to are guaranteed to be inside.
michael@0:         kInsideOut_BoundsType
michael@0:     };
michael@0: 
michael@0:     class Element {
michael@0:     public:
michael@0:         enum Type {
michael@0:             //!< This element makes the clip empty (regardless of previous elements).
michael@0:             kEmpty_Type,
michael@0:             //!< This element combines a rect with the current clip using a set operation
michael@0:             kRect_Type,
michael@0:             //!< This element combines a round-rect with the current clip using a set operation
michael@0:             kRRect_Type,
michael@0:             //!< This element combines a path with the current clip using a set operation
michael@0:             kPath_Type,
michael@0:         };
michael@0: 
michael@0:         Element() {
michael@0:             this->initCommon(0, SkRegion::kReplace_Op, false);
michael@0:             this->setEmpty();
michael@0:         }
michael@0: 
michael@0:         Element(const Element&);
michael@0: 
michael@0:         Element(const SkRect& rect, SkRegion::Op op, bool doAA) {
michael@0:             this->initRect(0, rect, op, doAA);
michael@0:         }
michael@0: 
michael@0:         Element(const SkRRect& rrect, SkRegion::Op op, bool doAA) {
michael@0:             this->initRRect(0, rrect, op, doAA);
michael@0:         }
michael@0: 
michael@0:         Element(const SkPath& path, SkRegion::Op op, bool doAA) {
michael@0:             this->initPath(0, path, op, doAA);
michael@0:         }
michael@0: 
michael@0:         bool operator== (const Element& element) const;
michael@0:         bool operator!= (const Element& element) const { return !(*this == element); }
michael@0: 
michael@0:         //!< Call to get the type of the clip element.
michael@0:         Type getType() const { return fType; }
michael@0: 
michael@0:         //!< Call if getType() is kPath to get the path.
michael@0:         const SkPath& getPath() const { SkASSERT(kPath_Type == fType); return *fPath.get(); }
michael@0: 
michael@0:         //!< Call if getType() is kRRect to get the round-rect.
michael@0:         const SkRRect& getRRect() const { SkASSERT(kRRect_Type == fType); return fRRect; }
michael@0: 
michael@0:         //!< Call if getType() is kRect to get the rect.
michael@0:         const SkRect& getRect() const {
michael@0:             SkASSERT(kRect_Type == fType && (fRRect.isRect() || fRRect.isEmpty()));
michael@0:             return fRRect.getBounds();
michael@0:         }
michael@0: 
michael@0:         //!< Call if getType() is not kEmpty to get the set operation used to combine this element.
michael@0:         SkRegion::Op getOp() const { return fOp; }
michael@0: 
michael@0:         //!< Call to get the element as a path, regardless of its type.
michael@0:         void asPath(SkPath* path) const;
michael@0: 
michael@0:         /** If getType() is not kEmpty this indicates whether the clip shape should be anti-aliased
michael@0:             when it is rasterized. */
michael@0:         bool isAA() const { return fDoAA; }
michael@0: 
michael@0:         //!< Inverts the fill of the clip shape. Note that a kEmpty element remains kEmpty.
michael@0:         void invertShapeFillType();
michael@0: 
michael@0:         //!< Sets the set operation represented by the element.
michael@0:         void setOp(SkRegion::Op op) { fOp = op; }
michael@0: 
michael@0:         /** The GenID can be used by clip stack clients to cache representations of the clip. The
michael@0:             ID corresponds to the set of clip elements up to and including this element within the
michael@0:             stack not to the element itself. That is the same clip path in different stacks will
michael@0:             have a different ID since the elements produce different clip result in the context of
michael@0:             their stacks. */
michael@0:         int32_t getGenID() const { SkASSERT(kInvalidGenID != fGenID); return fGenID; }
michael@0: 
michael@0:         /**
michael@0:          * Gets the bounds of the clip element, either the rect or path bounds. (Whether the shape
michael@0:          * is inverse filled is not considered.)
michael@0:          */
michael@0:         const SkRect& getBounds() const {
michael@0:             static const SkRect kEmpty = { 0, 0, 0, 0 };
michael@0:             switch (fType) {
michael@0:                 case kRect_Type:  // fallthrough
michael@0:                 case kRRect_Type:
michael@0:                     return fRRect.getBounds();
michael@0:                 case kPath_Type:
michael@0:                     return fPath.get()->getBounds();
michael@0:                 case kEmpty_Type:
michael@0:                     return kEmpty;
michael@0:                 default:
michael@0:                     SkDEBUGFAIL("Unexpected type.");
michael@0:                     return kEmpty;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         /**
michael@0:          * Conservatively checks whether the clip shape contains the rect param. (Whether the shape
michael@0:          * is inverse filled is not considered.)
michael@0:          */
michael@0:         bool contains(const SkRect& rect) const {
michael@0:             switch (fType) {
michael@0:                 case kRect_Type:
michael@0:                     return this->getRect().contains(rect);
michael@0:                 case kRRect_Type:
michael@0:                     return fRRect.contains(rect);
michael@0:                 case kPath_Type:
michael@0:                     return fPath.get()->conservativelyContainsRect(rect);
michael@0:                 case kEmpty_Type:
michael@0:                     return false;
michael@0:                 default:
michael@0:                     SkDEBUGFAIL("Unexpected type.");
michael@0:                     return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         /**
michael@0:          * Is the clip shape inverse filled.
michael@0:          */
michael@0:         bool isInverseFilled() const {
michael@0:             return kPath_Type == fType && fPath.get()->isInverseFillType();
michael@0:         }
michael@0: 
michael@0:     private:
michael@0:         friend class SkClipStack;
michael@0: 
michael@0:         SkTLazy<SkPath> fPath;
michael@0:         SkRRect         fRRect;
michael@0:         int             fSaveCount; // save count of stack when this element was added.
michael@0:         SkRegion::Op    fOp;
michael@0:         Type            fType;
michael@0:         bool            fDoAA;
michael@0: 
michael@0:         /* fFiniteBoundType and fFiniteBound are used to incrementally update the clip stack's
michael@0:            bound. When fFiniteBoundType is kNormal_BoundsType, fFiniteBound represents the
michael@0:            conservative bounding box of the pixels that aren't clipped (i.e., any pixels that can be
michael@0:            drawn to are inside the bound). When fFiniteBoundType is kInsideOut_BoundsType (which
michael@0:            occurs when a clip is inverse filled), fFiniteBound represents the conservative bounding
michael@0:            box of the pixels that _are_ clipped (i.e., any pixels that cannot be drawn to are inside
michael@0:            the bound). When fFiniteBoundType is kInsideOut_BoundsType the actual bound is the
michael@0:            infinite plane. This behavior of fFiniteBoundType and fFiniteBound is required so that we
michael@0:            can capture the cancelling out of the extensions to infinity when two inverse filled
michael@0:            clips are Booleaned together. */
michael@0:         SkClipStack::BoundsType fFiniteBoundType;
michael@0:         SkRect                  fFiniteBound;
michael@0: 
michael@0:         // When element is applied to the previous elements in the stack is the result known to be
michael@0:         // equivalent to a single rect intersection? IIOW, is the clip effectively a rectangle.
michael@0:         bool                    fIsIntersectionOfRects;
michael@0: 
michael@0:         int                     fGenID;
michael@0: 
michael@0:         Element(int saveCount) {
michael@0:             this->initCommon(saveCount, SkRegion::kReplace_Op, false);
michael@0:             this->setEmpty();
michael@0:         }
michael@0: 
michael@0:         Element(int saveCount, const SkRRect& rrect, SkRegion::Op op, bool doAA) {
michael@0:             this->initRRect(saveCount, rrect, op, doAA);
michael@0:         }
michael@0: 
michael@0:         Element(int saveCount, const SkRect& rect, SkRegion::Op op, bool doAA) {
michael@0:             this->initRect(saveCount, rect, op, doAA);
michael@0:         }
michael@0: 
michael@0:         Element(int saveCount, const SkPath& path, SkRegion::Op op, bool doAA) {
michael@0:             this->initPath(saveCount, path, op, doAA);
michael@0:         }
michael@0: 
michael@0:         void initCommon(int saveCount, SkRegion::Op op, bool doAA) {
michael@0:             fSaveCount = saveCount;
michael@0:             fOp = op;
michael@0:             fDoAA = doAA;
michael@0:             // A default of inside-out and empty bounds means the bounds are effectively void as it
michael@0:             // indicates that nothing is known to be outside the clip.
michael@0:             fFiniteBoundType = kInsideOut_BoundsType;
michael@0:             fFiniteBound.setEmpty();
michael@0:             fIsIntersectionOfRects = false;
michael@0:             fGenID = kInvalidGenID;
michael@0:         }
michael@0: 
michael@0:         void initRect(int saveCount, const SkRect& rect, SkRegion::Op op, bool doAA) {
michael@0:             fRRect.setRect(rect);
michael@0:             fType = kRect_Type;
michael@0:             this->initCommon(saveCount, op, doAA);
michael@0:         }
michael@0: 
michael@0:         void initRRect(int saveCount, const SkRRect& rrect, SkRegion::Op op, bool doAA) {
michael@0:             SkRRect::Type type = rrect.getType();
michael@0:             fRRect = rrect;
michael@0:             if (SkRRect::kRect_Type == type || SkRRect::kEmpty_Type == type) {
michael@0:                 fType = kRect_Type;
michael@0:             } else {
michael@0:                 fType = kRRect_Type;
michael@0:             }
michael@0:             this->initCommon(saveCount, op, doAA);
michael@0:         }
michael@0: 
michael@0:         void initPath(int saveCount, const SkPath& path, SkRegion::Op op, bool doAA);
michael@0: 
michael@0:         void setEmpty();
michael@0: 
michael@0:         // All Element methods below are only used within SkClipStack.cpp
michael@0:         inline void checkEmpty() const;
michael@0:         inline bool canBeIntersectedInPlace(int saveCount, SkRegion::Op op) const;
michael@0:         /* This method checks to see if two rect clips can be safely merged into one. The issue here
michael@0:           is that to be strictly correct all the edges of the resulting rect must have the same
michael@0:           anti-aliasing. */
michael@0:         bool rectRectIntersectAllowed(const SkRect& newR, bool newAA) const;
michael@0:         /** Determines possible finite bounds for the Element given the previous element of the
michael@0:             stack */
michael@0:         void updateBoundAndGenID(const Element* prior);
michael@0:         // The different combination of fill & inverse fill when combining bounding boxes
michael@0:         enum FillCombo {
michael@0:             kPrev_Cur_FillCombo,
michael@0:             kPrev_InvCur_FillCombo,
michael@0:             kInvPrev_Cur_FillCombo,
michael@0:             kInvPrev_InvCur_FillCombo
michael@0:         };
michael@0:         // per-set operation functions used by updateBoundAndGenID().
michael@0:         inline void combineBoundsDiff(FillCombo combination, const SkRect& prevFinite);
michael@0:         inline void combineBoundsXOR(int combination, const SkRect& prevFinite);
michael@0:         inline void combineBoundsUnion(int combination, const SkRect& prevFinite);
michael@0:         inline void combineBoundsIntersection(int combination, const SkRect& prevFinite);
michael@0:         inline void combineBoundsRevDiff(int combination, const SkRect& prevFinite);
michael@0:     };
michael@0: 
michael@0:     SkClipStack();
michael@0:     SkClipStack(const SkClipStack& b);
michael@0:     explicit SkClipStack(const SkRect& r);
michael@0:     explicit SkClipStack(const SkIRect& r);
michael@0:     ~SkClipStack();
michael@0: 
michael@0:     SkClipStack& operator=(const SkClipStack& b);
michael@0:     bool operator==(const SkClipStack& b) const;
michael@0:     bool operator!=(const SkClipStack& b) const { return !(*this == b); }
michael@0: 
michael@0:     void reset();
michael@0: 
michael@0:     int getSaveCount() const { return fSaveCount; }
michael@0:     void save();
michael@0:     void restore();
michael@0: 
michael@0:     /**
michael@0:      * getBounds places the current finite bound in its first parameter. In its
michael@0:      * second, it indicates which kind of bound is being returned. If
michael@0:      * 'canvFiniteBound' is a normal bounding box then it encloses all writeable
michael@0:      * pixels. If 'canvFiniteBound' is an inside out bounding box then it
michael@0:      * encloses all the un-writeable pixels and the true/normal bound is the
michael@0:      * infinite plane. isIntersectionOfRects is an optional parameter
michael@0:      * that is true if 'canvFiniteBound' resulted from an intersection of rects.
michael@0:      */
michael@0:     void getBounds(SkRect* canvFiniteBound,
michael@0:                    BoundsType* boundType,
michael@0:                    bool* isIntersectionOfRects = NULL) const;
michael@0: 
michael@0:     /**
michael@0:      * Takes an input rect in device space and conservatively clips it to the
michael@0:      * clip-stack. If false is returned then the rect does not intersect the
michael@0:      * clip and is unmodified.
michael@0:      */
michael@0:     bool intersectRectWithClip(SkRect* devRect) const;
michael@0: 
michael@0:     /**
michael@0:      * Returns true if the input rect in device space is entirely contained
michael@0:      * by the clip. A return value of false does not guarantee that the rect
michael@0:      * is not contained by the clip.
michael@0:      */
michael@0:     bool quickContains(const SkRect& devRect) const;
michael@0: 
michael@0:     void clipDevRect(const SkIRect& ir, SkRegion::Op op) {
michael@0:         SkRect r;
michael@0:         r.set(ir);
michael@0:         this->clipDevRect(r, op, false);
michael@0:     }
michael@0:     void clipDevRect(const SkRect&, SkRegion::Op, bool doAA);
michael@0:     void clipDevRRect(const SkRRect&, SkRegion::Op, bool doAA);
michael@0:     void clipDevPath(const SkPath&, SkRegion::Op, bool doAA);
michael@0:     // An optimized version of clipDevRect(emptyRect, kIntersect, ...)
michael@0:     void clipEmpty();
michael@0: 
michael@0:     /**
michael@0:      * isWideOpen returns true if the clip state corresponds to the infinite
michael@0:      * plane (i.e., draws are not limited at all)
michael@0:      */
michael@0:     bool isWideOpen() const;
michael@0: 
michael@0:     /**
michael@0:      * The generation ID has three reserved values to indicate special
michael@0:      * (potentially ignorable) cases
michael@0:      */
michael@0:     static const int32_t kInvalidGenID = 0;     //!< Invalid id that is never returned by
michael@0:                                                 //!< SkClipStack. Useful when caching clips
michael@0:                                                 //!< based on GenID.
michael@0:     static const int32_t kEmptyGenID = 1;       // no pixels writeable
michael@0:     static const int32_t kWideOpenGenID = 2;    // all pixels writeable
michael@0: 
michael@0:     int32_t getTopmostGenID() const;
michael@0: 
michael@0: public:
michael@0:     class Iter {
michael@0:     public:
michael@0:         enum IterStart {
michael@0:             kBottom_IterStart = SkDeque::Iter::kFront_IterStart,
michael@0:             kTop_IterStart = SkDeque::Iter::kBack_IterStart
michael@0:         };
michael@0: 
michael@0:         /**
michael@0:          * Creates an uninitialized iterator. Must be reset()
michael@0:          */
michael@0:         Iter();
michael@0: 
michael@0:         Iter(const SkClipStack& stack, IterStart startLoc);
michael@0: 
michael@0:         /**
michael@0:          *  Return the clip element for this iterator. If next()/prev() returns NULL, then the
michael@0:          *  iterator is done.
michael@0:          */
michael@0:         const Element* next();
michael@0:         const Element* prev();
michael@0: 
michael@0:         /**
michael@0:          * Moves the iterator to the topmost element with the specified RegionOp and returns that
michael@0:          * element. If no clip element with that op is found, the first element is returned.
michael@0:          */
michael@0:         const Element* skipToTopmost(SkRegion::Op op);
michael@0: 
michael@0:         /**
michael@0:          * Restarts the iterator on a clip stack.
michael@0:          */
michael@0:         void reset(const SkClipStack& stack, IterStart startLoc);
michael@0: 
michael@0:     private:
michael@0:         const SkClipStack* fStack;
michael@0:         SkDeque::Iter      fIter;
michael@0:     };
michael@0: 
michael@0:     /**
michael@0:      * The B2TIter iterates from the bottom of the stack to the top.
michael@0:      * It inherits privately from Iter to prevent access to reverse iteration.
michael@0:      */
michael@0:     class B2TIter : private Iter {
michael@0:     public:
michael@0:         B2TIter() {}
michael@0: 
michael@0:         /**
michael@0:          * Wrap Iter's 2 parameter ctor to force initialization to the
michael@0:          * beginning of the deque/bottom of the stack
michael@0:          */
michael@0:         B2TIter(const SkClipStack& stack)
michael@0:         : INHERITED(stack, kBottom_IterStart) {
michael@0:         }
michael@0: 
michael@0:         using Iter::next;
michael@0: 
michael@0:         /**
michael@0:          * Wrap Iter::reset to force initialization to the
michael@0:          * beginning of the deque/bottom of the stack
michael@0:          */
michael@0:         void reset(const SkClipStack& stack) {
michael@0:             this->INHERITED::reset(stack, kBottom_IterStart);
michael@0:         }
michael@0: 
michael@0:     private:
michael@0: 
michael@0:         typedef Iter INHERITED;
michael@0:     };
michael@0: 
michael@0:     /**
michael@0:      * GetConservativeBounds returns a conservative bound of the current clip.
michael@0:      * Since this could be the infinite plane (if inverse fills were involved) the
michael@0:      * maxWidth and maxHeight parameters can be used to limit the returned bound
michael@0:      * to the expected drawing area. Similarly, the offsetX and offsetY parameters
michael@0:      * allow the caller to offset the returned bound to account for translated
michael@0:      * drawing areas (i.e., those resulting from a saveLayer). For finite bounds,
michael@0:      * the translation (+offsetX, +offsetY) is applied before the clamp to the
michael@0:      * maximum rectangle: [0,maxWidth) x [0,maxHeight).
michael@0:      * isIntersectionOfRects is an optional parameter that is true when
michael@0:      * 'devBounds' is the result of an intersection of rects. In this case
michael@0:      * 'devBounds' is the exact answer/clip.
michael@0:      */
michael@0:     void getConservativeBounds(int offsetX,
michael@0:                                int offsetY,
michael@0:                                int maxWidth,
michael@0:                                int maxHeight,
michael@0:                                SkRect* devBounds,
michael@0:                                bool* isIntersectionOfRects = NULL) const;
michael@0: 
michael@0: private:
michael@0:     friend class Iter;
michael@0: 
michael@0:     SkDeque fDeque;
michael@0:     int     fSaveCount;
michael@0: 
michael@0:     // Generation ID for the clip stack. This is incremented for each
michael@0:     // clipDevRect and clipDevPath call. 0 is reserved to indicate an
michael@0:     // invalid ID.
michael@0:     static int32_t     gGenID;
michael@0: 
michael@0:     /**
michael@0:      * Helper for clipDevPath, etc.
michael@0:      */
michael@0:     void pushElement(const Element& element);
michael@0: 
michael@0:     /**
michael@0:      * Restore the stack back to the specified save count.
michael@0:      */
michael@0:     void restoreTo(int saveCount);
michael@0: 
michael@0:     /**
michael@0:      * Return the next unique generation ID.
michael@0:      */
michael@0:     static int32_t GetNextGenID();
michael@0: };
michael@0: 
michael@0: #endif