1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrReducedClip.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,450 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2012 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +#include "GrReducedClip.h"
1.13 +
1.14 +typedef SkClipStack::Element Element;
1.15 +////////////////////////////////////////////////////////////////////////////////
1.16 +
1.17 +namespace GrReducedClip {
1.18 +
1.19 +// helper function
1.20 +void reduced_stack_walker(const SkClipStack& stack,
1.21 + const SkRect& queryBounds,
1.22 + ElementList* result,
1.23 + int32_t* resultGenID,
1.24 + InitialState* initialState,
1.25 + bool* requiresAA);
1.26 +
1.27 +/*
1.28 +There are plenty of optimizations that could be added here. Maybe flips could be folded into
1.29 +earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
1.30 +for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
1.31 +based on later intersect operations, and perhaps remove intersect-rects. We could optionally
1.32 +take a rect in case the caller knows a bound on what is to be drawn through this clip.
1.33 +*/
1.34 +void ReduceClipStack(const SkClipStack& stack,
1.35 + const SkIRect& queryBounds,
1.36 + ElementList* result,
1.37 + int32_t* resultGenID,
1.38 + InitialState* initialState,
1.39 + SkIRect* tighterBounds,
1.40 + bool* requiresAA) {
1.41 + result->reset();
1.42 +
1.43 + // The clip established by the element list might be cached based on the last
1.44 + // generation id. When we make early returns, we do not know what was the generation
1.45 + // id that lead to the state. Make a conservative guess.
1.46 + *resultGenID = stack.getTopmostGenID();
1.47 +
1.48 + if (stack.isWideOpen()) {
1.49 + *initialState = kAllIn_InitialState;
1.50 + return;
1.51 + }
1.52 +
1.53 +
1.54 + // We initially look at whether the bounds alone is sufficient. We also use the stack bounds to
1.55 + // attempt to compute the tighterBounds.
1.56 +
1.57 + SkClipStack::BoundsType stackBoundsType;
1.58 + SkRect stackBounds;
1.59 + bool iior;
1.60 + stack.getBounds(&stackBounds, &stackBoundsType, &iior);
1.61 +
1.62 + const SkIRect* bounds = &queryBounds;
1.63 +
1.64 + SkRect scalarQueryBounds = SkRect::Make(queryBounds);
1.65 +
1.66 + if (iior) {
1.67 + SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
1.68 + SkRect isectRect;
1.69 + if (stackBounds.contains(scalarQueryBounds)) {
1.70 + *initialState = kAllIn_InitialState;
1.71 + if (NULL != tighterBounds) {
1.72 + *tighterBounds = queryBounds;
1.73 + }
1.74 + if (NULL != requiresAA) {
1.75 + *requiresAA = false;
1.76 + }
1.77 + } else if (isectRect.intersect(stackBounds, scalarQueryBounds)) {
1.78 + // If the caller asked for tighter integer bounds we may be able to
1.79 + // return kAllIn and give the bounds with no elements
1.80 + if (NULL != tighterBounds) {
1.81 + isectRect.roundOut(tighterBounds);
1.82 + SkRect scalarTighterBounds = SkRect::Make(*tighterBounds);
1.83 + if (scalarTighterBounds == isectRect) {
1.84 + // the round-out didn't add any area outside the clip rect.
1.85 + if (NULL != requiresAA) {
1.86 + *requiresAA = false;
1.87 + }
1.88 + *initialState = kAllIn_InitialState;
1.89 + return;
1.90 + }
1.91 + }
1.92 + *initialState = kAllOut_InitialState;
1.93 + // iior should only be true if aa/non-aa status matches among all elements.
1.94 + SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
1.95 + bool doAA = iter.prev()->isAA();
1.96 + SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA));
1.97 + if (NULL != requiresAA) {
1.98 + *requiresAA = doAA;
1.99 + }
1.100 + } else {
1.101 + *initialState = kAllOut_InitialState;
1.102 + if (NULL != requiresAA) {
1.103 + *requiresAA = false;
1.104 + }
1.105 + }
1.106 + return;
1.107 + } else {
1.108 + if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
1.109 + if (!SkRect::Intersects(stackBounds, scalarQueryBounds)) {
1.110 + *initialState = kAllOut_InitialState;
1.111 + if (NULL != requiresAA) {
1.112 + *requiresAA = false;
1.113 + }
1.114 + return;
1.115 + }
1.116 + if (NULL != tighterBounds) {
1.117 + SkIRect stackIBounds;
1.118 + stackBounds.roundOut(&stackIBounds);
1.119 + tighterBounds->intersect(queryBounds, stackIBounds);
1.120 + bounds = tighterBounds;
1.121 + }
1.122 + } else {
1.123 + if (stackBounds.contains(scalarQueryBounds)) {
1.124 + *initialState = kAllOut_InitialState;
1.125 + if (NULL != requiresAA) {
1.126 + *requiresAA = false;
1.127 + }
1.128 + return;
1.129 + }
1.130 + if (NULL != tighterBounds) {
1.131 + *tighterBounds = queryBounds;
1.132 + }
1.133 + }
1.134 + }
1.135 +
1.136 + SkRect scalarBounds = SkRect::Make(*bounds);
1.137 +
1.138 + // Now that we have determined the bounds to use and filtered out the trivial cases, call the
1.139 + // helper that actually walks the stack.
1.140 + reduced_stack_walker(stack, scalarBounds, result, resultGenID, initialState, requiresAA);
1.141 +
1.142 + // The list that was computed in this function may be cached based on the gen id of the last
1.143 + // element.
1.144 + SkASSERT(SkClipStack::kInvalidGenID != *resultGenID);
1.145 +}
1.146 +
1.147 +void reduced_stack_walker(const SkClipStack& stack,
1.148 + const SkRect& queryBounds,
1.149 + ElementList* result,
1.150 + int32_t* resultGenID,
1.151 + InitialState* initialState,
1.152 + bool* requiresAA) {
1.153 +
1.154 + // walk backwards until we get to:
1.155 + // a) the beginning
1.156 + // b) an operation that is known to make the bounds all inside/outside
1.157 + // c) a replace operation
1.158 +
1.159 + static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1);
1.160 + *initialState = kUnknown_InitialState;
1.161 +
1.162 + // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
1.163 + // TODO: track these per saved clip so that we can consider them on the forward pass.
1.164 + bool embiggens = false;
1.165 + bool emsmallens = false;
1.166 +
1.167 + SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
1.168 + int numAAElements = 0;
1.169 + while ((kUnknown_InitialState == *initialState)) {
1.170 + const Element* element = iter.prev();
1.171 + if (NULL == element) {
1.172 + *initialState = kAllIn_InitialState;
1.173 + break;
1.174 + }
1.175 + if (SkClipStack::kEmptyGenID == element->getGenID()) {
1.176 + *initialState = kAllOut_InitialState;
1.177 + break;
1.178 + }
1.179 + if (SkClipStack::kWideOpenGenID == element->getGenID()) {
1.180 + *initialState = kAllIn_InitialState;
1.181 + break;
1.182 + }
1.183 +
1.184 + bool skippable = false;
1.185 + bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
1.186 +
1.187 + switch (element->getOp()) {
1.188 + case SkRegion::kDifference_Op:
1.189 + // check if the shape subtracted either contains the entire bounds (and makes
1.190 + // the clip empty) or is outside the bounds and therefore can be skipped.
1.191 + if (element->isInverseFilled()) {
1.192 + if (element->contains(queryBounds)) {
1.193 + skippable = true;
1.194 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.195 + *initialState = kAllOut_InitialState;
1.196 + skippable = true;
1.197 + }
1.198 + } else {
1.199 + if (element->contains(queryBounds)) {
1.200 + *initialState = kAllOut_InitialState;
1.201 + skippable = true;
1.202 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.203 + skippable = true;
1.204 + }
1.205 + }
1.206 + if (!skippable) {
1.207 + emsmallens = true;
1.208 + }
1.209 + break;
1.210 + case SkRegion::kIntersect_Op:
1.211 + // check if the shape intersected contains the entire bounds and therefore can
1.212 + // be skipped or it is outside the entire bounds and therefore makes the clip
1.213 + // empty.
1.214 + if (element->isInverseFilled()) {
1.215 + if (element->contains(queryBounds)) {
1.216 + *initialState = kAllOut_InitialState;
1.217 + skippable = true;
1.218 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.219 + skippable = true;
1.220 + }
1.221 + } else {
1.222 + if (element->contains(queryBounds)) {
1.223 + skippable = true;
1.224 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.225 + *initialState = kAllOut_InitialState;
1.226 + skippable = true;
1.227 + }
1.228 + }
1.229 + if (!skippable) {
1.230 + emsmallens = true;
1.231 + }
1.232 + break;
1.233 + case SkRegion::kUnion_Op:
1.234 + // If the union-ed shape contains the entire bounds then after this element
1.235 + // the bounds is entirely inside the clip. If the union-ed shape is outside the
1.236 + // bounds then this op can be skipped.
1.237 + if (element->isInverseFilled()) {
1.238 + if (element->contains(queryBounds)) {
1.239 + skippable = true;
1.240 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.241 + *initialState = kAllIn_InitialState;
1.242 + skippable = true;
1.243 + }
1.244 + } else {
1.245 + if (element->contains(queryBounds)) {
1.246 + *initialState = kAllIn_InitialState;
1.247 + skippable = true;
1.248 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.249 + skippable = true;
1.250 + }
1.251 + }
1.252 + if (!skippable) {
1.253 + embiggens = true;
1.254 + }
1.255 + break;
1.256 + case SkRegion::kXOR_Op:
1.257 + // If the bounds is entirely inside the shape being xor-ed then the effect is
1.258 + // to flip the inside/outside state of every point in the bounds. We may be
1.259 + // able to take advantage of this in the forward pass. If the xor-ed shape
1.260 + // doesn't intersect the bounds then it can be skipped.
1.261 + if (element->isInverseFilled()) {
1.262 + if (element->contains(queryBounds)) {
1.263 + skippable = true;
1.264 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.265 + isFlip = true;
1.266 + }
1.267 + } else {
1.268 + if (element->contains(queryBounds)) {
1.269 + isFlip = true;
1.270 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.271 + skippable = true;
1.272 + }
1.273 + }
1.274 + if (!skippable) {
1.275 + emsmallens = embiggens = true;
1.276 + }
1.277 + break;
1.278 + case SkRegion::kReverseDifference_Op:
1.279 + // When the bounds is entirely within the rev-diff shape then this behaves like xor
1.280 + // and reverses every point inside the bounds. If the shape is completely outside
1.281 + // the bounds then we know after this element is applied that the bounds will be
1.282 + // all outside the current clip.B
1.283 + if (element->isInverseFilled()) {
1.284 + if (element->contains(queryBounds)) {
1.285 + *initialState = kAllOut_InitialState;
1.286 + skippable = true;
1.287 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.288 + isFlip = true;
1.289 + }
1.290 + } else {
1.291 + if (element->contains(queryBounds)) {
1.292 + isFlip = true;
1.293 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.294 + *initialState = kAllOut_InitialState;
1.295 + skippable = true;
1.296 + }
1.297 + }
1.298 + if (!skippable) {
1.299 + emsmallens = embiggens = true;
1.300 + }
1.301 + break;
1.302 + case SkRegion::kReplace_Op:
1.303 + // Replace will always terminate our walk. We will either begin the forward walk
1.304 + // at the replace op or detect here than the shape is either completely inside
1.305 + // or completely outside the bounds. In this latter case it can be skipped by
1.306 + // setting the correct value for initialState.
1.307 + if (element->isInverseFilled()) {
1.308 + if (element->contains(queryBounds)) {
1.309 + *initialState = kAllOut_InitialState;
1.310 + skippable = true;
1.311 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.312 + *initialState = kAllIn_InitialState;
1.313 + skippable = true;
1.314 + }
1.315 + } else {
1.316 + if (element->contains(queryBounds)) {
1.317 + *initialState = kAllIn_InitialState;
1.318 + skippable = true;
1.319 + } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
1.320 + *initialState = kAllOut_InitialState;
1.321 + skippable = true;
1.322 + }
1.323 + }
1.324 + if (!skippable) {
1.325 + *initialState = kAllOut_InitialState;
1.326 + embiggens = emsmallens = true;
1.327 + }
1.328 + break;
1.329 + default:
1.330 + SkDEBUGFAIL("Unexpected op.");
1.331 + break;
1.332 + }
1.333 + if (!skippable) {
1.334 + if (0 == result->count()) {
1.335 + // This will be the last element. Record the stricter genID.
1.336 + *resultGenID = element->getGenID();
1.337 + }
1.338 +
1.339 + // if it is a flip, change it to a bounds-filling rect
1.340 + if (isFlip) {
1.341 + SkASSERT(SkRegion::kXOR_Op == element->getOp() ||
1.342 + SkRegion::kReverseDifference_Op == element->getOp());
1.343 + SkNEW_INSERT_AT_LLIST_HEAD(result,
1.344 + Element,
1.345 + (queryBounds, SkRegion::kReverseDifference_Op, false));
1.346 + } else {
1.347 + Element* newElement = result->addToHead(*element);
1.348 + if (newElement->isAA()) {
1.349 + ++numAAElements;
1.350 + }
1.351 + // Intersecting an inverse shape is the same as differencing the non-inverse shape.
1.352 + // Replacing with an inverse shape is the same as setting initialState=kAllIn and
1.353 + // differencing the non-inverse shape.
1.354 + bool isReplace = SkRegion::kReplace_Op == newElement->getOp();
1.355 + if (newElement->isInverseFilled() &&
1.356 + (SkRegion::kIntersect_Op == newElement->getOp() || isReplace)) {
1.357 + newElement->invertShapeFillType();
1.358 + newElement->setOp(SkRegion::kDifference_Op);
1.359 + if (isReplace) {
1.360 + SkASSERT(kAllOut_InitialState == *initialState);
1.361 + *initialState = kAllIn_InitialState;
1.362 + }
1.363 + }
1.364 + }
1.365 + }
1.366 + }
1.367 +
1.368 + if ((kAllOut_InitialState == *initialState && !embiggens) ||
1.369 + (kAllIn_InitialState == *initialState && !emsmallens)) {
1.370 + result->reset();
1.371 + } else {
1.372 + Element* element = result->headIter().get();
1.373 + while (NULL != element) {
1.374 + bool skippable = false;
1.375 + switch (element->getOp()) {
1.376 + case SkRegion::kDifference_Op:
1.377 + // subtracting from the empty set yields the empty set.
1.378 + skippable = kAllOut_InitialState == *initialState;
1.379 + break;
1.380 + case SkRegion::kIntersect_Op:
1.381 + // intersecting with the empty set yields the empty set
1.382 + if (kAllOut_InitialState == *initialState) {
1.383 + skippable = true;
1.384 + } else {
1.385 + // We can clear to zero and then simply draw the clip element.
1.386 + *initialState = kAllOut_InitialState;
1.387 + element->setOp(SkRegion::kReplace_Op);
1.388 + }
1.389 + break;
1.390 + case SkRegion::kUnion_Op:
1.391 + if (kAllIn_InitialState == *initialState) {
1.392 + // unioning the infinite plane with anything is a no-op.
1.393 + skippable = true;
1.394 + } else {
1.395 + // unioning the empty set with a shape is the shape.
1.396 + element->setOp(SkRegion::kReplace_Op);
1.397 + }
1.398 + break;
1.399 + case SkRegion::kXOR_Op:
1.400 + if (kAllOut_InitialState == *initialState) {
1.401 + // xor could be changed to diff in the kAllIn case, not sure it's a win.
1.402 + element->setOp(SkRegion::kReplace_Op);
1.403 + }
1.404 + break;
1.405 + case SkRegion::kReverseDifference_Op:
1.406 + if (kAllIn_InitialState == *initialState) {
1.407 + // subtracting the whole plane will yield the empty set.
1.408 + skippable = true;
1.409 + *initialState = kAllOut_InitialState;
1.410 + } else {
1.411 + // this picks up flips inserted in the backwards pass.
1.412 + skippable = element->isInverseFilled() ?
1.413 + !SkRect::Intersects(element->getBounds(), queryBounds) :
1.414 + element->contains(queryBounds);
1.415 + if (skippable) {
1.416 + *initialState = kAllIn_InitialState;
1.417 + } else {
1.418 + element->setOp(SkRegion::kReplace_Op);
1.419 + }
1.420 + }
1.421 + break;
1.422 + case SkRegion::kReplace_Op:
1.423 + skippable = false; // we would have skipped it in the backwards walk if we
1.424 + // could've.
1.425 + break;
1.426 + default:
1.427 + SkDEBUGFAIL("Unexpected op.");
1.428 + break;
1.429 + }
1.430 + if (!skippable) {
1.431 + break;
1.432 + } else {
1.433 + if (element->isAA()) {
1.434 + --numAAElements;
1.435 + }
1.436 + result->popHead();
1.437 + element = result->headIter().get();
1.438 + }
1.439 + }
1.440 + }
1.441 + if (NULL != requiresAA) {
1.442 + *requiresAA = numAAElements > 0;
1.443 + }
1.444 +
1.445 + if (0 == result->count()) {
1.446 + if (*initialState == kAllIn_InitialState) {
1.447 + *resultGenID = SkClipStack::kWideOpenGenID;
1.448 + } else {
1.449 + *resultGenID = SkClipStack::kEmptyGenID;
1.450 + }
1.451 + }
1.452 +}
1.453 +} // namespace GrReducedClip
