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