GrReducedClip.cpp revision 45a15f551b5b3c6c747d8eaf6466b7d3b76a8fae
1170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 2170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com/* 3170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com * Copyright 2012 Google Inc. 4170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com * 5170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com * Use of this source code is governed by a BSD-style license that can be 6170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com * found in the LICENSE file. 7170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com */ 8170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 9170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com#include "GrReducedClip.h" 10170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 11170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.comtypedef SkClipStack::Element Element; 12170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com//////////////////////////////////////////////////////////////////////////////// 13170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 14170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.comnamespace GrReducedClip { 15170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 1634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com// helper function 1734cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.comvoid reduced_stack_walker(const SkClipStack& stack, 1834cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com const SkRect& queryBounds, 1934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com ElementList* result, 2034cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com InitialState* initialState, 2134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com bool* requiresAA); 2234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com 23170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com/* 24c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.comThere are plenty of optimizations that could be added here. Maybe flips could be folded into 25170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.comearlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps 26170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.comfor the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations 27170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.combased on later intersect operations, and perhaps remove intersect-rects. We could optionally 28170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.comtake a rect in case the caller knows a bound on what is to be drawn through this clip. 29170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com*/ 3034cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.comvoid ReduceClipStack(const SkClipStack& stack, 3134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com const SkIRect& queryBounds, 3234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com ElementList* result, 3334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com InitialState* initialState, 3434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com SkIRect* tighterBounds, 3534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com bool* requiresAA) { 36170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com result->reset(); 37170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 38170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (stack.isWideOpen()) { 39170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 40170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com return; 41170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 42170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 4334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com 4434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com // We initially look at whether the bounds alone is sufficient. We also use the stack bounds to 4534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com // attempt to compute the tighterBounds. 4634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com 47170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkClipStack::BoundsType stackBoundsType; 48170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkRect stackBounds; 49170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com bool iior; 50170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com stack.getBounds(&stackBounds, &stackBoundsType, &iior); 51170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 5234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com const SkIRect* bounds = &queryBounds; 5334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com 5434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com SkRect scalarQueryBounds = SkRect::MakeFromIRect(queryBounds); 5534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com 56170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (iior) { 57170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType); 58170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkRect isectRect; 5934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (stackBounds.contains(scalarQueryBounds)) { 60170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 6134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != tighterBounds) { 6234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *tighterBounds = queryBounds; 6334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 6434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != requiresAA) { 6534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *requiresAA = false; 6634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 6734cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } else if (isectRect.intersect(stackBounds, scalarQueryBounds)) { 6834cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != tighterBounds) { 6934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com isectRect.roundOut(tighterBounds); 7034cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com SkRect scalarTighterBounds = SkRect::MakeFromIRect(*tighterBounds); 7134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (scalarTighterBounds == isectRect) { 7234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com // the round-out didn't add any area outside the clip rect. 7334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *requiresAA = false; 7434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *initialState = kAllIn_InitialState; 7534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com return; 7634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 7734cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *initialState = kAllOut_InitialState; 7834cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com // iior should only be true if aa/non-aa status matches among all elements. 7934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart); 8034cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com bool doAA = iter.prev()->isAA(); 8134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA)); 8234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != requiresAA) { 8334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *requiresAA = doAA; 8434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 8534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 86170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 87170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 8834cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != requiresAA) { 8934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *requiresAA = false; 9034cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 91170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 92170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com return; 93170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 94170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (SkClipStack::kNormal_BoundsType == stackBoundsType) { 9534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (!SkRect::Intersects(stackBounds, scalarQueryBounds)) { 96170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 9734cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != requiresAA) { 9834cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *requiresAA = false; 9934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 100170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com return; 101170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 10234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != tighterBounds) { 10334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com SkIRect stackIBounds; 10434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com stackBounds.roundOut(&stackIBounds); 10534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com tighterBounds->intersect(queryBounds, stackIBounds); 10634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com bounds = tighterBounds; 10734cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 108170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 10934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (stackBounds.contains(scalarQueryBounds)) { 110170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 11134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != requiresAA) { 11234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *requiresAA = false; 11334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 114170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com return; 115170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 11634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != tighterBounds) { 11734cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *tighterBounds = queryBounds; 11834cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 119170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 120170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 121170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 12234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com SkRect scalarBounds = SkRect::MakeFromIRect(*bounds); 123d21444aab7128c97f4e0eb5e9bf05111d5037292skia.committer@gmail.com 12434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com // Now that we have determined the bounds to use and filtered out the trivial cases, call the 12534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com // helper that actually walks the stack. 12634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com reduced_stack_walker(stack, scalarBounds, result, initialState, requiresAA); 12734cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com} 12834cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com 12934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.comvoid reduced_stack_walker(const SkClipStack& stack, 13034cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com const SkRect& queryBounds, 13134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com ElementList* result, 13234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com InitialState* initialState, 13334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com bool* requiresAA) { 13434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com 135170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // walk backwards until we get to: 136170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // a) the beginning 137170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // b) an operation that is known to make the bounds all inside/outside 138170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // c) a replace operation 139170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 140170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1); 141170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kUnknown_InitialState; 142170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 143170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // During our backwards walk, track whether we've seen ops that either grow or shrink the clip. 144170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // TODO: track these per saved clip so that we can consider them on the forward pass. 145170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com bool embiggens = false; 146170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com bool emsmallens = false; 147170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 148170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart); 14934cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com int numAAElements = 0; 150170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com while ((kUnknown_InitialState == *initialState)) { 151170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com const Element* element = iter.prev(); 152170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (NULL == element) { 153170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 154170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 155170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 156170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (SkClipStack::kEmptyGenID == element->getGenID()) { 157170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 158170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 159170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 160170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (SkClipStack::kWideOpenGenID == element->getGenID()) { 161170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 162170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 163170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 164170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 165170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com bool skippable = false; 166170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com bool isFlip = false; // does this op just flip the in/out state of every point in the bounds 167170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 168170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com switch (element->getOp()) { 169170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kDifference_Op: 170170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // check if the shape subtracted either contains the entire bounds (and makes 171170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // the clip empty) or is outside the bounds and therefore can be skipped. 172170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->isInverseFilled()) { 173170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 174170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 175170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 176170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 177170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 178170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 179170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 180170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 181170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 182170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 183170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 184170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 185170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 186170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 187170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 188170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com emsmallens = true; 189170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 190170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 191170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kIntersect_Op: 192170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // check if the shape intersected contains the entire bounds and therefore can 193170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // be skipped or it is outside the entire bounds and therefore makes the clip 194170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // empty. 195170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->isInverseFilled()) { 196170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 197170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 198170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 199170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 200170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 201170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 202170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 203170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 204170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 205170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 206170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 207170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 208170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 209170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 210170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 211170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com emsmallens = true; 212170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 213170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 214170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kUnion_Op: 215170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // If the union-ed shape contains the entire bounds then after this element 216170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // the bounds is entirely inside the clip. If the union-ed shape is outside the 217170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // bounds then this op can be skipped. 218170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->isInverseFilled()) { 219170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 220170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 221170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 222170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 223170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 224170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 225170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 226170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 227170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 228170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 229170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 230170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 231170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 232170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 233170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 234170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com embiggens = true; 235170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 236170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 237170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kXOR_Op: 238170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // If the bounds is entirely inside the shape being xor-ed then the effect is 239170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // to flip the inside/outside state of every point in the bounds. We may be 240170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // able to take advantage of this in the forward pass. If the xor-ed shape 241170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // doesn't intersect the bounds then it can be skipped. 242170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->isInverseFilled()) { 243170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 244170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 245170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 246170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com isFlip = true; 247170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 248170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 249170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 250170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com isFlip = true; 251170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 252170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 253170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 254170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 255170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 256170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com emsmallens = embiggens = true; 257170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 258170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 259170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kReverseDifference_Op: 260170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // When the bounds is entirely within the rev-diff shape then this behaves like xor 261170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // and reverses every point inside the bounds. If the shape is completely outside 262170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // the bounds then we know after this element is applied that the bounds will be 263170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // all outside the current clip.B 264170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->isInverseFilled()) { 265170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 266170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 267170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 268170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 269170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com isFlip = true; 270170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 271170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 272170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 273170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com isFlip = true; 274170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 275170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 276170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 277170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 278170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 279170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 280170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com emsmallens = embiggens = true; 281170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 282170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 283170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kReplace_Op: 284170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // Replace will always terminate our walk. We will either begin the forward walk 285170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // at the replace op or detect here than the shape is either completely inside 286170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // or completely outside the bounds. In this latter case it can be skipped by 287170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // setting the correct value for initialState. 288170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->isInverseFilled()) { 289170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 290170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 291170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 292170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 293170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 294170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 295170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 296170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 297170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (element->contains(queryBounds)) { 298170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 299170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 300170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) { 301170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 302170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 303170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 304170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 305170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 306170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 307170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com embiggens = emsmallens = true; 308170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 309170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 310170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com default: 311170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkDEBUGFAIL("Unexpected op."); 312170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 313170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 314170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 315170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // if it is a flip, change it to a bounds-filling rect 316170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (isFlip) { 317170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkASSERT(SkRegion::kXOR_Op == element->getOp() || 318170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkRegion::kReverseDifference_Op == element->getOp()); 319170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkNEW_INSERT_AT_LLIST_HEAD(result, 320170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com Element, 321170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com (queryBounds, SkRegion::kReverseDifference_Op, false)); 322170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 323c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com Element* newElement = result->addToHead(*element); 324c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com if (newElement->isAA()) { 32534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com ++numAAElements; 32634cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 327c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com // Intersecting an inverse shape is the same as differencing the non-inverse shape. 32845a15f551b5b3c6c747d8eaf6466b7d3b76a8faebsalomon@google.com // Replacing with an inverse shape is the same as setting initialState=kAllIn and 329c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com // differencing the non-inverse shape. 330c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com bool isReplace = SkRegion::kReplace_Op == newElement->getOp(); 331c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com if (newElement->isInverseFilled() && 332c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com (SkRegion::kIntersect_Op == newElement->getOp() || isReplace)) { 333c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com newElement->invertShapeFillType(); 334c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com newElement->setOp(SkRegion::kDifference_Op); 335c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com if (isReplace) { 336c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com SkASSERT(kAllOut_InitialState == *initialState); 337c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com *initialState = kAllIn_InitialState; 338c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com } 339c6b3e48cb3a22d83ba3f4b9a614a5a35b05958a0bsalomon@google.com } 340170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 341170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 342170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 343170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com 344170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if ((kAllOut_InitialState == *initialState && !embiggens) || 345170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com (kAllIn_InitialState == *initialState && !emsmallens)) { 346170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com result->reset(); 347170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 348170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com Element* element = result->headIter().get(); 349170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com while (NULL != element) { 350170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com bool skippable = false; 351170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com switch (element->getOp()) { 352170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kDifference_Op: 353170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // subtracting from the empty set yields the empty set. 354170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = kAllOut_InitialState == *initialState; 355170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 356170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kIntersect_Op: 357170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // intersecting with the empty set yields the empty set 358170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = kAllOut_InitialState == *initialState; 359170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 360170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kUnion_Op: 361170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (kAllIn_InitialState == *initialState) { 362170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // unioning the infinite plane with anything is a no-op. 363170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 364170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 365170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // unioning the empty set with a shape is the shape. 366170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com element->setOp(SkRegion::kReplace_Op); 367170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 368170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 369170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kXOR_Op: 370170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (kAllOut_InitialState == *initialState) { 371170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // xor could be changed to diff in the kAllIn case, not sure it's a win. 372170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com element->setOp(SkRegion::kReplace_Op); 373170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 374170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 375170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kReverseDifference_Op: 376170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (kAllIn_InitialState == *initialState) { 377170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // subtracting the whole plane will yield the empty set. 378170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = true; 379170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllOut_InitialState; 380170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 381170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // this picks up flips inserted in the backwards pass. 382170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = element->isInverseFilled() ? 383170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com !SkRect::Intersects(element->getBounds(), queryBounds) : 384170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com element->contains(queryBounds); 385170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (skippable) { 386170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com *initialState = kAllIn_InitialState; 387170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 388170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com element->setOp(SkRegion::kReplace_Op); 389170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 390170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 391170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 392170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com case SkRegion::kReplace_Op: 393170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com skippable = false; // we would have skipped it in the backwards walk if we 394170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com // could've. 395170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 396170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com default: 397170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com SkDEBUGFAIL("Unexpected op."); 398170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 399170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 400170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com if (!skippable) { 401170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com break; 402170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } else { 40334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (element->isAA()) { 40434cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com --numAAElements; 40534cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 406170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com result->popHead(); 407170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com element = result->headIter().get(); 408170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 409170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 410170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com } 41134cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com if (NULL != requiresAA) { 41234cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com *requiresAA = numAAElements > 0; 41334cd70a5810b3cf37b44de1ce080a911a8b342c8bsalomon@google.com } 414170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com} 415170bd792e17469769d145b7dc15dea6cd01b7966bsalomon@google.com} // namespace GrReducedClip 416