diff -r 000000000000 -r 6474c204b198 gfx/skia/trunk/src/gpu/GrReducedClip.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/gfx/skia/trunk/src/gpu/GrReducedClip.cpp Wed Dec 31 06:09:35 2014 +0100 @@ -0,0 +1,450 @@ + +/* + * 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(-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