michael@0: 
michael@0: /*
michael@0:  * Copyright 2012 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: 
michael@0: #include "GrReducedClip.h"
michael@0: 
michael@0: typedef SkClipStack::Element Element;
michael@0: ////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: namespace GrReducedClip {
michael@0: 
michael@0: // helper function
michael@0: void reduced_stack_walker(const SkClipStack& stack,
michael@0:                           const SkRect& queryBounds,
michael@0:                           ElementList* result,
michael@0:                           int32_t* resultGenID,
michael@0:                           InitialState* initialState,
michael@0:                           bool* requiresAA);
michael@0: 
michael@0: /*
michael@0: There are plenty of optimizations that could be added here. Maybe flips could be folded into
michael@0: earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
michael@0: for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
michael@0: based on later intersect operations, and perhaps remove intersect-rects. We could optionally
michael@0: take a rect in case the caller knows a bound on what is to be drawn through this clip.
michael@0: */
michael@0: void ReduceClipStack(const SkClipStack& stack,
michael@0:                      const SkIRect& queryBounds,
michael@0:                      ElementList* result,
michael@0:                      int32_t* resultGenID,
michael@0:                      InitialState* initialState,
michael@0:                      SkIRect* tighterBounds,
michael@0:                      bool* requiresAA) {
michael@0:     result->reset();
michael@0: 
michael@0:     // The clip established by the element list might be cached based on the last
michael@0:     // generation id. When we make early returns, we do not know what was the generation
michael@0:     // id that lead to the state. Make a conservative guess.
michael@0:     *resultGenID = stack.getTopmostGenID();
michael@0: 
michael@0:     if (stack.isWideOpen()) {
michael@0:         *initialState = kAllIn_InitialState;
michael@0:         return;
michael@0:     }
michael@0: 
michael@0: 
michael@0:     // We initially look at whether the bounds alone is sufficient. We also use the stack bounds to
michael@0:     // attempt to compute the tighterBounds.
michael@0: 
michael@0:     SkClipStack::BoundsType stackBoundsType;
michael@0:     SkRect stackBounds;
michael@0:     bool iior;
michael@0:     stack.getBounds(&stackBounds, &stackBoundsType, &iior);
michael@0: 
michael@0:     const SkIRect* bounds = &queryBounds;
michael@0: 
michael@0:     SkRect scalarQueryBounds = SkRect::Make(queryBounds);
michael@0: 
michael@0:     if (iior) {
michael@0:         SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
michael@0:         SkRect isectRect;
michael@0:         if (stackBounds.contains(scalarQueryBounds)) {
michael@0:             *initialState = kAllIn_InitialState;
michael@0:             if (NULL != tighterBounds) {
michael@0:                 *tighterBounds = queryBounds;
michael@0:             }
michael@0:             if (NULL != requiresAA) {
michael@0:                *requiresAA = false;
michael@0:             }
michael@0:         } else if (isectRect.intersect(stackBounds, scalarQueryBounds)) {
michael@0:             // If the caller asked for tighter integer bounds we may be able to
michael@0:             // return kAllIn and give the bounds with no elements
michael@0:             if (NULL != tighterBounds) {
michael@0:                 isectRect.roundOut(tighterBounds);
michael@0:                 SkRect scalarTighterBounds = SkRect::Make(*tighterBounds);
michael@0:                 if (scalarTighterBounds == isectRect) {
michael@0:                     // the round-out didn't add any area outside the clip rect.
michael@0:                     if (NULL != requiresAA) {
michael@0:                         *requiresAA = false;
michael@0:                     }
michael@0:                     *initialState = kAllIn_InitialState;
michael@0:                     return;
michael@0:                 }
michael@0:             }
michael@0:             *initialState = kAllOut_InitialState;
michael@0:             // iior should only be true if aa/non-aa status matches among all elements.
michael@0:             SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
michael@0:             bool doAA = iter.prev()->isAA();
michael@0:             SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA));
michael@0:             if (NULL != requiresAA) {
michael@0:                 *requiresAA = doAA;
michael@0:             }
michael@0:         } else {
michael@0:             *initialState = kAllOut_InitialState;
michael@0:              if (NULL != requiresAA) {
michael@0:                 *requiresAA = false;
michael@0:              }
michael@0:         }
michael@0:         return;
michael@0:     } else {
michael@0:         if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
michael@0:             if (!SkRect::Intersects(stackBounds, scalarQueryBounds)) {
michael@0:                 *initialState = kAllOut_InitialState;
michael@0:                 if (NULL != requiresAA) {
michael@0:                    *requiresAA = false;
michael@0:                 }
michael@0:                 return;
michael@0:             }
michael@0:             if (NULL != tighterBounds) {
michael@0:                 SkIRect stackIBounds;
michael@0:                 stackBounds.roundOut(&stackIBounds);
michael@0:                 tighterBounds->intersect(queryBounds, stackIBounds);
michael@0:                 bounds = tighterBounds;
michael@0:             }
michael@0:         } else {
michael@0:             if (stackBounds.contains(scalarQueryBounds)) {
michael@0:                 *initialState = kAllOut_InitialState;
michael@0:                 if (NULL != requiresAA) {
michael@0:                    *requiresAA = false;
michael@0:                 }
michael@0:                 return;
michael@0:             }
michael@0:             if (NULL != tighterBounds) {
michael@0:                 *tighterBounds = queryBounds;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     SkRect scalarBounds = SkRect::Make(*bounds);
michael@0: 
michael@0:     // Now that we have determined the bounds to use and filtered out the trivial cases, call the
michael@0:     // helper that actually walks the stack.
michael@0:     reduced_stack_walker(stack, scalarBounds, result, resultGenID, initialState, requiresAA);
michael@0: 
michael@0:     // The list that was computed in this function may be cached based on the gen id of the last
michael@0:     // element.
michael@0:     SkASSERT(SkClipStack::kInvalidGenID != *resultGenID);
michael@0: }
michael@0: 
michael@0: void reduced_stack_walker(const SkClipStack& stack,
michael@0:                           const SkRect& queryBounds,
michael@0:                           ElementList* result,
michael@0:                           int32_t* resultGenID,
michael@0:                           InitialState* initialState,
michael@0:                           bool* requiresAA) {
michael@0: 
michael@0:     // walk backwards until we get to:
michael@0:     //  a) the beginning
michael@0:     //  b) an operation that is known to make the bounds all inside/outside
michael@0:     //  c) a replace operation
michael@0: 
michael@0:     static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1);
michael@0:     *initialState = kUnknown_InitialState;
michael@0: 
michael@0:     // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
michael@0:     // TODO: track these per saved clip so that we can consider them on the forward pass.
michael@0:     bool embiggens = false;
michael@0:     bool emsmallens = false;
michael@0: 
michael@0:     SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
michael@0:     int numAAElements = 0;
michael@0:     while ((kUnknown_InitialState == *initialState)) {
michael@0:         const Element* element = iter.prev();
michael@0:         if (NULL == element) {
michael@0:             *initialState = kAllIn_InitialState;
michael@0:             break;
michael@0:         }
michael@0:         if (SkClipStack::kEmptyGenID == element->getGenID()) {
michael@0:             *initialState = kAllOut_InitialState;
michael@0:             break;
michael@0:         }
michael@0:         if (SkClipStack::kWideOpenGenID == element->getGenID()) {
michael@0:             *initialState = kAllIn_InitialState;
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         bool skippable = false;
michael@0:         bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
michael@0: 
michael@0:         switch (element->getOp()) {
michael@0:             case SkRegion::kDifference_Op:
michael@0:                 // check if the shape subtracted either contains the entire bounds (and makes
michael@0:                 // the clip empty) or is outside the bounds and therefore can be skipped.
michael@0:                 if (element->isInverseFilled()) {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 } else {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 }
michael@0:                 if (!skippable) {
michael@0:                     emsmallens = true;
michael@0:                 }
michael@0:                 break;
michael@0:             case SkRegion::kIntersect_Op:
michael@0:                 // check if the shape intersected contains the entire bounds and therefore can
michael@0:                 // be skipped or it is outside the entire bounds and therefore makes the clip
michael@0:                 // empty.
michael@0:                 if (element->isInverseFilled()) {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 } else {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 }
michael@0:                 if (!skippable) {
michael@0:                     emsmallens = true;
michael@0:                 }
michael@0:                 break;
michael@0:             case SkRegion::kUnion_Op:
michael@0:                 // If the union-ed shape contains the entire bounds then after this element
michael@0:                 // the bounds is entirely inside the clip. If the union-ed shape is outside the
michael@0:                 // bounds then this op can be skipped.
michael@0:                 if (element->isInverseFilled()) {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         *initialState = kAllIn_InitialState;
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 } else {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         *initialState = kAllIn_InitialState;
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 }
michael@0:                 if (!skippable) {
michael@0:                     embiggens = true;
michael@0:                 }
michael@0:                 break;
michael@0:             case SkRegion::kXOR_Op:
michael@0:                 // If the bounds is entirely inside the shape being xor-ed then the effect is
michael@0:                 // to flip the inside/outside state of every point in the bounds. We may be
michael@0:                 // able to take advantage of this in the forward pass. If the xor-ed shape
michael@0:                 // doesn't intersect the bounds then it can be skipped.
michael@0:                 if (element->isInverseFilled()) {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         isFlip = true;
michael@0:                     }
michael@0:                 } else {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         isFlip = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 }
michael@0:                 if (!skippable) {
michael@0:                     emsmallens = embiggens = true;
michael@0:                 }
michael@0:                 break;
michael@0:             case SkRegion::kReverseDifference_Op:
michael@0:                 // When the bounds is entirely within the rev-diff shape then this behaves like xor
michael@0:                 // and reverses every point inside the bounds. If the shape is completely outside
michael@0:                 // the bounds then we know after this element is applied that the bounds will be
michael@0:                 // all outside the current clip.B
michael@0:                 if (element->isInverseFilled()) {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         isFlip = true;
michael@0:                     }
michael@0:                 } else {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         isFlip = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 }
michael@0:                 if (!skippable) {
michael@0:                     emsmallens = embiggens = true;
michael@0:                 }
michael@0:                 break;
michael@0:             case SkRegion::kReplace_Op:
michael@0:                 // Replace will always terminate our walk. We will either begin the forward walk
michael@0:                 // at the replace op or detect here than the shape is either completely inside
michael@0:                 // or completely outside the bounds. In this latter case it can be skipped by
michael@0:                 // setting the correct value for initialState.
michael@0:                 if (element->isInverseFilled()) {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         *initialState = kAllIn_InitialState;
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 } else {
michael@0:                     if (element->contains(queryBounds)) {
michael@0:                         *initialState = kAllIn_InitialState;
michael@0:                         skippable = true;
michael@0:                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         skippable = true;
michael@0:                     }
michael@0:                 }
michael@0:                 if (!skippable) {
michael@0:                     *initialState = kAllOut_InitialState;
michael@0:                     embiggens = emsmallens = true;
michael@0:                 }
michael@0:                 break;
michael@0:             default:
michael@0:                 SkDEBUGFAIL("Unexpected op.");
michael@0:                 break;
michael@0:         }
michael@0:         if (!skippable) {
michael@0:             if (0 == result->count()) {
michael@0:                 // This will be the last element. Record the stricter genID.
michael@0:                 *resultGenID = element->getGenID();
michael@0:             }
michael@0: 
michael@0:             // if it is a flip, change it to a bounds-filling rect
michael@0:             if (isFlip) {
michael@0:                 SkASSERT(SkRegion::kXOR_Op == element->getOp() ||
michael@0:                          SkRegion::kReverseDifference_Op == element->getOp());
michael@0:                 SkNEW_INSERT_AT_LLIST_HEAD(result,
michael@0:                                            Element,
michael@0:                                            (queryBounds, SkRegion::kReverseDifference_Op, false));
michael@0:             } else {
michael@0:                 Element* newElement = result->addToHead(*element);
michael@0:                 if (newElement->isAA()) {
michael@0:                     ++numAAElements;
michael@0:                 }
michael@0:                 // Intersecting an inverse shape is the same as differencing the non-inverse shape.
michael@0:                 // Replacing with an inverse shape is the same as setting initialState=kAllIn and
michael@0:                 // differencing the non-inverse shape.
michael@0:                 bool isReplace = SkRegion::kReplace_Op == newElement->getOp();
michael@0:                 if (newElement->isInverseFilled() &&
michael@0:                     (SkRegion::kIntersect_Op == newElement->getOp() || isReplace)) {
michael@0:                     newElement->invertShapeFillType();
michael@0:                     newElement->setOp(SkRegion::kDifference_Op);
michael@0:                     if (isReplace) {
michael@0:                         SkASSERT(kAllOut_InitialState == *initialState);
michael@0:                         *initialState = kAllIn_InitialState;
michael@0:                     }
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if ((kAllOut_InitialState == *initialState && !embiggens) ||
michael@0:         (kAllIn_InitialState == *initialState && !emsmallens)) {
michael@0:         result->reset();
michael@0:     } else {
michael@0:         Element* element = result->headIter().get();
michael@0:         while (NULL != element) {
michael@0:             bool skippable = false;
michael@0:             switch (element->getOp()) {
michael@0:                 case SkRegion::kDifference_Op:
michael@0:                     // subtracting from the empty set yields the empty set.
michael@0:                     skippable = kAllOut_InitialState == *initialState;
michael@0:                     break;
michael@0:                 case SkRegion::kIntersect_Op:
michael@0:                     // intersecting with the empty set yields the empty set
michael@0:                     if (kAllOut_InitialState == *initialState) {
michael@0:                         skippable = true;
michael@0:                     } else {
michael@0:                         // We can clear to zero and then simply draw the clip element.
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                         element->setOp(SkRegion::kReplace_Op);
michael@0:                     }
michael@0:                     break;
michael@0:                 case SkRegion::kUnion_Op:
michael@0:                     if (kAllIn_InitialState == *initialState) {
michael@0:                         // unioning the infinite plane with anything is a no-op.
michael@0:                         skippable = true;
michael@0:                     } else {
michael@0:                         // unioning the empty set with a shape is the shape.
michael@0:                         element->setOp(SkRegion::kReplace_Op);
michael@0:                     }
michael@0:                     break;
michael@0:                 case SkRegion::kXOR_Op:
michael@0:                     if (kAllOut_InitialState == *initialState) {
michael@0:                         // xor could be changed to diff in the kAllIn case, not sure it's a win.
michael@0:                         element->setOp(SkRegion::kReplace_Op);
michael@0:                     }
michael@0:                     break;
michael@0:                 case SkRegion::kReverseDifference_Op:
michael@0:                     if (kAllIn_InitialState == *initialState) {
michael@0:                         // subtracting the whole plane will yield the empty set.
michael@0:                         skippable = true;
michael@0:                         *initialState = kAllOut_InitialState;
michael@0:                     } else {
michael@0:                         // this picks up flips inserted in the backwards pass.
michael@0:                         skippable = element->isInverseFilled() ?
michael@0:                             !SkRect::Intersects(element->getBounds(), queryBounds) :
michael@0:                             element->contains(queryBounds);
michael@0:                         if (skippable) {
michael@0:                             *initialState = kAllIn_InitialState;
michael@0:                         } else {
michael@0:                             element->setOp(SkRegion::kReplace_Op);
michael@0:                         }
michael@0:                     }
michael@0:                     break;
michael@0:                 case SkRegion::kReplace_Op:
michael@0:                     skippable = false; // we would have skipped it in the backwards walk if we
michael@0:                                        // could've.
michael@0:                     break;
michael@0:                 default:
michael@0:                     SkDEBUGFAIL("Unexpected op.");
michael@0:                     break;
michael@0:             }
michael@0:             if (!skippable) {
michael@0:                 break;
michael@0:             } else {
michael@0:                 if (element->isAA()) {
michael@0:                     --numAAElements;
michael@0:                 }
michael@0:                 result->popHead();
michael@0:                 element = result->headIter().get();
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     if (NULL != requiresAA) {
michael@0:         *requiresAA = numAAElements > 0;
michael@0:     }
michael@0: 
michael@0:     if (0 == result->count()) {
michael@0:         if (*initialState == kAllIn_InitialState) {
michael@0:             *resultGenID = SkClipStack::kWideOpenGenID;
michael@0:         } else {
michael@0:             *resultGenID = SkClipStack::kEmptyGenID;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: } // namespace GrReducedClip