Home | History | Annotate | Download | only in gpu
      1 
      2 /*
      3  * Copyright 2012 Google Inc.
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 #include "GrReducedClip.h"
     10 
     11 typedef SkClipStack::Element Element;
     12 ////////////////////////////////////////////////////////////////////////////////
     13 
     14 namespace GrReducedClip {
     15 
     16 // helper function
     17 void reduced_stack_walker(const SkClipStack& stack,
     18                           const SkRect& queryBounds,
     19                           ElementList* result,
     20                           int32_t* resultGenID,
     21                           InitialState* initialState,
     22                           bool* requiresAA);
     23 
     24 /*
     25 There are plenty of optimizations that could be added here. Maybe flips could be folded into
     26 earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
     27 for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
     28 based on later intersect operations, and perhaps remove intersect-rects. We could optionally
     29 take a rect in case the caller knows a bound on what is to be drawn through this clip.
     30 */
     31 void ReduceClipStack(const SkClipStack& stack,
     32                      const SkIRect& queryBounds,
     33                      ElementList* result,
     34                      int32_t* resultGenID,
     35                      InitialState* initialState,
     36                      SkIRect* tighterBounds,
     37                      bool* requiresAA) {
     38     result->reset();
     39 
     40     // The clip established by the element list might be cached based on the last
     41     // generation id. When we make early returns, we do not know what was the generation
     42     // id that lead to the state. Make a conservative guess.
     43     *resultGenID = stack.getTopmostGenID();
     44 
     45     if (stack.isWideOpen()) {
     46         *initialState = kAllIn_InitialState;
     47         return;
     48     }
     49 
     50 
     51     // We initially look at whether the bounds alone is sufficient. We also use the stack bounds to
     52     // attempt to compute the tighterBounds.
     53 
     54     SkClipStack::BoundsType stackBoundsType;
     55     SkRect stackBounds;
     56     bool iior;
     57     stack.getBounds(&stackBounds, &stackBoundsType, &iior);
     58 
     59     const SkIRect* bounds = &queryBounds;
     60 
     61     SkRect scalarQueryBounds = SkRect::Make(queryBounds);
     62 
     63     if (iior) {
     64         SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
     65         SkRect isectRect;
     66         if (stackBounds.contains(scalarQueryBounds)) {
     67             *initialState = kAllIn_InitialState;
     68             if (NULL != tighterBounds) {
     69                 *tighterBounds = queryBounds;
     70             }
     71             if (NULL != requiresAA) {
     72                *requiresAA = false;
     73             }
     74         } else if (isectRect.intersect(stackBounds, scalarQueryBounds)) {
     75             // If the caller asked for tighter integer bounds we may be able to
     76             // return kAllIn and give the bounds with no elements
     77             if (NULL != tighterBounds) {
     78                 isectRect.roundOut(tighterBounds);
     79                 SkRect scalarTighterBounds = SkRect::Make(*tighterBounds);
     80                 if (scalarTighterBounds == isectRect) {
     81                     // the round-out didn't add any area outside the clip rect.
     82                     if (NULL != requiresAA) {
     83                         *requiresAA = false;
     84                     }
     85                     *initialState = kAllIn_InitialState;
     86                     return;
     87                 }
     88             }
     89             *initialState = kAllOut_InitialState;
     90             // iior should only be true if aa/non-aa status matches among all elements.
     91             SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
     92             bool doAA = iter.prev()->isAA();
     93             SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA));
     94             if (NULL != requiresAA) {
     95                 *requiresAA = doAA;
     96             }
     97         } else {
     98             *initialState = kAllOut_InitialState;
     99              if (NULL != requiresAA) {
    100                 *requiresAA = false;
    101              }
    102         }
    103         return;
    104     } else {
    105         if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
    106             if (!SkRect::Intersects(stackBounds, scalarQueryBounds)) {
    107                 *initialState = kAllOut_InitialState;
    108                 if (NULL != requiresAA) {
    109                    *requiresAA = false;
    110                 }
    111                 return;
    112             }
    113             if (NULL != tighterBounds) {
    114                 SkIRect stackIBounds;
    115                 stackBounds.roundOut(&stackIBounds);
    116                 tighterBounds->intersect(queryBounds, stackIBounds);
    117                 bounds = tighterBounds;
    118             }
    119         } else {
    120             if (stackBounds.contains(scalarQueryBounds)) {
    121                 *initialState = kAllOut_InitialState;
    122                 if (NULL != requiresAA) {
    123                    *requiresAA = false;
    124                 }
    125                 return;
    126             }
    127             if (NULL != tighterBounds) {
    128                 *tighterBounds = queryBounds;
    129             }
    130         }
    131     }
    132 
    133     SkRect scalarBounds = SkRect::Make(*bounds);
    134 
    135     // Now that we have determined the bounds to use and filtered out the trivial cases, call the
    136     // helper that actually walks the stack.
    137     reduced_stack_walker(stack, scalarBounds, result, resultGenID, initialState, requiresAA);
    138 
    139     // The list that was computed in this function may be cached based on the gen id of the last
    140     // element.
    141     SkASSERT(SkClipStack::kInvalidGenID != *resultGenID);
    142 }
    143 
    144 void reduced_stack_walker(const SkClipStack& stack,
    145                           const SkRect& queryBounds,
    146                           ElementList* result,
    147                           int32_t* resultGenID,
    148                           InitialState* initialState,
    149                           bool* requiresAA) {
    150 
    151     // walk backwards until we get to:
    152     //  a) the beginning
    153     //  b) an operation that is known to make the bounds all inside/outside
    154     //  c) a replace operation
    155 
    156     static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1);
    157     *initialState = kUnknown_InitialState;
    158 
    159     // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
    160     // TODO: track these per saved clip so that we can consider them on the forward pass.
    161     bool embiggens = false;
    162     bool emsmallens = false;
    163 
    164     SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
    165     int numAAElements = 0;
    166     while ((kUnknown_InitialState == *initialState)) {
    167         const Element* element = iter.prev();
    168         if (NULL == element) {
    169             *initialState = kAllIn_InitialState;
    170             break;
    171         }
    172         if (SkClipStack::kEmptyGenID == element->getGenID()) {
    173             *initialState = kAllOut_InitialState;
    174             break;
    175         }
    176         if (SkClipStack::kWideOpenGenID == element->getGenID()) {
    177             *initialState = kAllIn_InitialState;
    178             break;
    179         }
    180 
    181         bool skippable = false;
    182         bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
    183 
    184         switch (element->getOp()) {
    185             case SkRegion::kDifference_Op:
    186                 // check if the shape subtracted either contains the entire bounds (and makes
    187                 // the clip empty) or is outside the bounds and therefore can be skipped.
    188                 if (element->isInverseFilled()) {
    189                     if (element->contains(queryBounds)) {
    190                         skippable = true;
    191                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    192                         *initialState = kAllOut_InitialState;
    193                         skippable = true;
    194                     }
    195                 } else {
    196                     if (element->contains(queryBounds)) {
    197                         *initialState = kAllOut_InitialState;
    198                         skippable = true;
    199                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    200                         skippable = true;
    201                     }
    202                 }
    203                 if (!skippable) {
    204                     emsmallens = true;
    205                 }
    206                 break;
    207             case SkRegion::kIntersect_Op:
    208                 // check if the shape intersected contains the entire bounds and therefore can
    209                 // be skipped or it is outside the entire bounds and therefore makes the clip
    210                 // empty.
    211                 if (element->isInverseFilled()) {
    212                     if (element->contains(queryBounds)) {
    213                         *initialState = kAllOut_InitialState;
    214                         skippable = true;
    215                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    216                         skippable = true;
    217                     }
    218                 } else {
    219                     if (element->contains(queryBounds)) {
    220                         skippable = true;
    221                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    222                         *initialState = kAllOut_InitialState;
    223                         skippable = true;
    224                     }
    225                 }
    226                 if (!skippable) {
    227                     emsmallens = true;
    228                 }
    229                 break;
    230             case SkRegion::kUnion_Op:
    231                 // If the union-ed shape contains the entire bounds then after this element
    232                 // the bounds is entirely inside the clip. If the union-ed shape is outside the
    233                 // bounds then this op can be skipped.
    234                 if (element->isInverseFilled()) {
    235                     if (element->contains(queryBounds)) {
    236                         skippable = true;
    237                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    238                         *initialState = kAllIn_InitialState;
    239                         skippable = true;
    240                     }
    241                 } else {
    242                     if (element->contains(queryBounds)) {
    243                         *initialState = kAllIn_InitialState;
    244                         skippable = true;
    245                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    246                         skippable = true;
    247                     }
    248                 }
    249                 if (!skippable) {
    250                     embiggens = true;
    251                 }
    252                 break;
    253             case SkRegion::kXOR_Op:
    254                 // If the bounds is entirely inside the shape being xor-ed then the effect is
    255                 // to flip the inside/outside state of every point in the bounds. We may be
    256                 // able to take advantage of this in the forward pass. If the xor-ed shape
    257                 // doesn't intersect the bounds then it can be skipped.
    258                 if (element->isInverseFilled()) {
    259                     if (element->contains(queryBounds)) {
    260                         skippable = true;
    261                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    262                         isFlip = true;
    263                     }
    264                 } else {
    265                     if (element->contains(queryBounds)) {
    266                         isFlip = true;
    267                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    268                         skippable = true;
    269                     }
    270                 }
    271                 if (!skippable) {
    272                     emsmallens = embiggens = true;
    273                 }
    274                 break;
    275             case SkRegion::kReverseDifference_Op:
    276                 // When the bounds is entirely within the rev-diff shape then this behaves like xor
    277                 // and reverses every point inside the bounds. If the shape is completely outside
    278                 // the bounds then we know after this element is applied that the bounds will be
    279                 // all outside the current clip.B
    280                 if (element->isInverseFilled()) {
    281                     if (element->contains(queryBounds)) {
    282                         *initialState = kAllOut_InitialState;
    283                         skippable = true;
    284                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    285                         isFlip = true;
    286                     }
    287                 } else {
    288                     if (element->contains(queryBounds)) {
    289                         isFlip = true;
    290                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    291                         *initialState = kAllOut_InitialState;
    292                         skippable = true;
    293                     }
    294                 }
    295                 if (!skippable) {
    296                     emsmallens = embiggens = true;
    297                 }
    298                 break;
    299             case SkRegion::kReplace_Op:
    300                 // Replace will always terminate our walk. We will either begin the forward walk
    301                 // at the replace op or detect here than the shape is either completely inside
    302                 // or completely outside the bounds. In this latter case it can be skipped by
    303                 // setting the correct value for initialState.
    304                 if (element->isInverseFilled()) {
    305                     if (element->contains(queryBounds)) {
    306                         *initialState = kAllOut_InitialState;
    307                         skippable = true;
    308                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    309                         *initialState = kAllIn_InitialState;
    310                         skippable = true;
    311                     }
    312                 } else {
    313                     if (element->contains(queryBounds)) {
    314                         *initialState = kAllIn_InitialState;
    315                         skippable = true;
    316                     } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
    317                         *initialState = kAllOut_InitialState;
    318                         skippable = true;
    319                     }
    320                 }
    321                 if (!skippable) {
    322                     *initialState = kAllOut_InitialState;
    323                     embiggens = emsmallens = true;
    324                 }
    325                 break;
    326             default:
    327                 SkDEBUGFAIL("Unexpected op.");
    328                 break;
    329         }
    330         if (!skippable) {
    331             if (0 == result->count()) {
    332                 // This will be the last element. Record the stricter genID.
    333                 *resultGenID = element->getGenID();
    334             }
    335 
    336             // if it is a flip, change it to a bounds-filling rect
    337             if (isFlip) {
    338                 SkASSERT(SkRegion::kXOR_Op == element->getOp() ||
    339                          SkRegion::kReverseDifference_Op == element->getOp());
    340                 SkNEW_INSERT_AT_LLIST_HEAD(result,
    341                                            Element,
    342                                            (queryBounds, SkRegion::kReverseDifference_Op, false));
    343             } else {
    344                 Element* newElement = result->addToHead(*element);
    345                 if (newElement->isAA()) {
    346                     ++numAAElements;
    347                 }
    348                 // Intersecting an inverse shape is the same as differencing the non-inverse shape.
    349                 // Replacing with an inverse shape is the same as setting initialState=kAllIn and
    350                 // differencing the non-inverse shape.
    351                 bool isReplace = SkRegion::kReplace_Op == newElement->getOp();
    352                 if (newElement->isInverseFilled() &&
    353                     (SkRegion::kIntersect_Op == newElement->getOp() || isReplace)) {
    354                     newElement->invertShapeFillType();
    355                     newElement->setOp(SkRegion::kDifference_Op);
    356                     if (isReplace) {
    357                         SkASSERT(kAllOut_InitialState == *initialState);
    358                         *initialState = kAllIn_InitialState;
    359                     }
    360                 }
    361             }
    362         }
    363     }
    364 
    365     if ((kAllOut_InitialState == *initialState && !embiggens) ||
    366         (kAllIn_InitialState == *initialState && !emsmallens)) {
    367         result->reset();
    368     } else {
    369         Element* element = result->headIter().get();
    370         while (NULL != element) {
    371             bool skippable = false;
    372             switch (element->getOp()) {
    373                 case SkRegion::kDifference_Op:
    374                     // subtracting from the empty set yields the empty set.
    375                     skippable = kAllOut_InitialState == *initialState;
    376                     break;
    377                 case SkRegion::kIntersect_Op:
    378                     // intersecting with the empty set yields the empty set
    379                     if (kAllOut_InitialState == *initialState) {
    380                         skippable = true;
    381                     } else {
    382                         // We can clear to zero and then simply draw the clip element.
    383                         *initialState = kAllOut_InitialState;
    384                         element->setOp(SkRegion::kReplace_Op);
    385                     }
    386                     break;
    387                 case SkRegion::kUnion_Op:
    388                     if (kAllIn_InitialState == *initialState) {
    389                         // unioning the infinite plane with anything is a no-op.
    390                         skippable = true;
    391                     } else {
    392                         // unioning the empty set with a shape is the shape.
    393                         element->setOp(SkRegion::kReplace_Op);
    394                     }
    395                     break;
    396                 case SkRegion::kXOR_Op:
    397                     if (kAllOut_InitialState == *initialState) {
    398                         // xor could be changed to diff in the kAllIn case, not sure it's a win.
    399                         element->setOp(SkRegion::kReplace_Op);
    400                     }
    401                     break;
    402                 case SkRegion::kReverseDifference_Op:
    403                     if (kAllIn_InitialState == *initialState) {
    404                         // subtracting the whole plane will yield the empty set.
    405                         skippable = true;
    406                         *initialState = kAllOut_InitialState;
    407                     } else {
    408                         // this picks up flips inserted in the backwards pass.
    409                         skippable = element->isInverseFilled() ?
    410                             !SkRect::Intersects(element->getBounds(), queryBounds) :
    411                             element->contains(queryBounds);
    412                         if (skippable) {
    413                             *initialState = kAllIn_InitialState;
    414                         } else {
    415                             element->setOp(SkRegion::kReplace_Op);
    416                         }
    417                     }
    418                     break;
    419                 case SkRegion::kReplace_Op:
    420                     skippable = false; // we would have skipped it in the backwards walk if we
    421                                        // could've.
    422                     break;
    423                 default:
    424                     SkDEBUGFAIL("Unexpected op.");
    425                     break;
    426             }
    427             if (!skippable) {
    428                 break;
    429             } else {
    430                 if (element->isAA()) {
    431                     --numAAElements;
    432                 }
    433                 result->popHead();
    434                 element = result->headIter().get();
    435             }
    436         }
    437     }
    438     if (NULL != requiresAA) {
    439         *requiresAA = numAAElements > 0;
    440     }
    441 
    442     if (0 == result->count()) {
    443         if (*initialState == kAllIn_InitialState) {
    444             *resultGenID = SkClipStack::kWideOpenGenID;
    445         } else {
    446             *resultGenID = SkClipStack::kEmptyGenID;
    447         }
    448     }
    449 }
    450 } // namespace GrReducedClip
    451