diff options
-rw-r--r-- | include/core/SkClipStack.h | 37 | ||||
-rw-r--r-- | src/core/SkClipStack.cpp | 345 | ||||
-rw-r--r-- | src/gpu/SkGpuDevice.cpp | 59 | ||||
-rw-r--r-- | tests/ClipStackTest.cpp | 82 |
4 files changed, 512 insertions, 11 deletions
diff --git a/include/core/SkClipStack.h b/include/core/SkClipStack.h index daeb82629a..fbdcb36c84 100644 --- a/include/core/SkClipStack.h +++ b/include/core/SkClipStack.h @@ -30,6 +30,27 @@ public: void save(); void restore(); + enum BoundsType { + // The bounding box contains all the pixels that can be written to + kNormal_BoundsType, + // The bounding box contains all the pixels that cannot be written to. + // The real bound extends out to infinity and all the pixels outside + // of the bound can be written to. Note that some of the pixels inside + // the bound may also be writeable but all pixels that cannot be + // written to are guaranteed to be inside. + kInsideOut_BoundsType + }; + + /** + * getBounds places the current finite bound in its first parameter. In its + * second, it indicates which kind of bound is being returned. If + * 'finiteBound' is a normal bounding box then it encloses are writeable + * pixels. If 'finiteBound' is an inside out bounding box then it + * encloses all the un-writeable pixels and the true/normal bound is the + * infinite plane. + */ + void getBounds(SkRect* finiteBound, BoundsType* boundType) const; + void clipDevRect(const SkIRect& ir, SkRegion::Op op) { SkRect r; r.set(ir); @@ -135,6 +156,22 @@ public: typedef Iter INHERITED; }; + /** + * GetConservativeBounds returns a conservative bound of the current clip. + * Since this could be the infinite plane (if inverse fills were involved) the + * maxWidth and maxHeight parameters can be used to limit the returned bound + * to the expected drawing area. Similarly, the offsetX and offsetY parameters + * allow the caller to offset the returned bound to account for translated + * drawing areas (i.e., those resulting from a saveLayer). For finite bounds, + * the translation (+offsetX, +offsetY) is applied before the clamp to the + * maximum rectangle: [0,maxWidth) x [0,maxHeight). + */ + void getConservativeBounds(int offsetX, + int offsetY, + int maxWidth, + int maxHeight, + SkRect* bounds) const; + private: friend class Iter; diff --git a/src/core/SkClipStack.cpp b/src/core/SkClipStack.cpp index 4212ba56e6..2676f3b078 100644 --- a/src/core/SkClipStack.cpp +++ b/src/core/SkClipStack.cpp @@ -9,6 +9,7 @@ #include "SkPath.h" #include <new> + struct SkClipStack::Rec { enum State { kEmpty_State, @@ -23,6 +24,22 @@ struct SkClipStack::Rec { State fState; bool fDoAA; + // fFiniteBoundType and fFiniteBound are used to incrementally update + // the clip stack's bound. When fFiniteBoundType is kNormal_BoundsType, + // fFiniteBound represents the conservative bounding box of the pixels + // that aren't clipped (i.e., any pixels that can be drawn to are inside + // the bound). When fFiniteBoundType is kInsideOut_BoundsType (which occurs + // when a clip is inverse filled), fFiniteBound represents the + // conservative bounding box of the pixels that _are_ clipped (i.e., any + // pixels that cannot be drawn to are inside the bound). When + // fFiniteBoundType is kInsideOut_BoundsType the actual bound is + // the infinite plane. This behavior of fFiniteBoundType and + // fFiniteBound is required so that we can capture the cancelling out + // of the extensions to infinity when two inverse filled clips are + // Booleaned together. + SkClipStack::BoundsType fFiniteBoundType; + SkRect fFiniteBound; + Rec(int saveCount, const SkRect& rect, SkRegion::Op op, bool doAA) : fRect(rect) { fSaveCount = saveCount; fOp = op; @@ -72,6 +89,271 @@ struct SkClipStack::Rec { SkRegion::kIntersect_Op == fOp && SkRegion::kIntersect_Op == op; } + + /** + * The different combination of fill & inverse fill when combining + * bounding boxes + */ + enum FillCombo { + kPrev_Cur_FillCombo, + kPrev_InvCur_FillCombo, + kInvPrev_Cur_FillCombo, + kInvPrev_InvCur_FillCombo + }; + + // a mirror of CombineBoundsRevDiff + void CombineBoundsDiff(FillCombo combination, const SkRect& prevFinite) { + switch (combination) { + case kInvPrev_InvCur_FillCombo: + // In this case the only pixels that can remain set + // are inside the current clip rect since the extensions + // to infinity of both clips cancel out and whatever + // is outside of the current clip is removed + fFiniteBoundType = kNormal_BoundsType; + break; + case kInvPrev_Cur_FillCombo: + // In this case the current op is finite so the only pixels + // that aren't set are whatever isn't set in the previous + // clip and whatever this clip carves out + fFiniteBound.join(prevFinite); + fFiniteBoundType = kInsideOut_BoundsType; + break; + case kPrev_InvCur_FillCombo: + // In this case everything outside of this clip's bound + // is erased, so the only pixels that can remain set + // occur w/in the intersection of the two finite bounds + if (!fFiniteBound.intersect(prevFinite)) { + fFiniteBound.setEmpty(); + } + fFiniteBoundType = kNormal_BoundsType; + break; + case kPrev_Cur_FillCombo: + // The most conservative result bound is that of the + // prior clip. This could be wildly incorrect if the + // second clip either exactly matches the first clip + // (which should yield the empty set) or reduces the + // size of the prior bound (e.g., if the second clip + // exactly matched the bottom half of the prior clip). + // We ignore these two possibilities. + fFiniteBound = prevFinite; + break; + default: + SkDEBUGFAIL("SkClipStack::Rec::CombineBoundsDiff Invalid fill combination"); + break; + } + } + + void CombineBoundsXOR(int combination, const SkRect& prevFinite) { + + switch (combination) { + case kInvPrev_Cur_FillCombo: // fall through + case kPrev_InvCur_FillCombo: + // With only one of the clips inverted the result will always + // extend to infinity. The only pixels that may be un-writeable + // lie within the union of the two finite bounds + fFiniteBound.join(prevFinite); + fFiniteBoundType = kInsideOut_BoundsType; + break; + case kInvPrev_InvCur_FillCombo: + // The only pixels that can survive are within the + // union of the two bounding boxes since the extensions + // to infinity of both clips cancel out + // fall through! + case kPrev_Cur_FillCombo: + // The most conservative bound for xor is the + // union of the two bounds. If the two clips exactly overlapped + // the xor could yield the empty set. Similarly the xor + // could reduce the size of the original clip's bound (e.g., + // if the second clip exactly matched the bottom half of the + // first clip). We ignore these two cases. + fFiniteBound.join(prevFinite); + fFiniteBoundType = kNormal_BoundsType; + break; + default: + SkDEBUGFAIL("SkClipStack::Rec::CombineBoundsXOR Invalid fill combination"); + break; + } + } + + // a mirror of CombineBoundsIntersection + void CombineBoundsUnion(int combination, const SkRect& prevFinite) { + + switch (combination) { + case kInvPrev_InvCur_FillCombo: + if (!fFiniteBound.intersect(prevFinite)) { + fFiniteBound.setEmpty(); + } + fFiniteBoundType = kInsideOut_BoundsType; + break; + case kInvPrev_Cur_FillCombo: + // The only pixels that won't be drawable are inside + // the prior clip's finite bound + fFiniteBound = prevFinite; + fFiniteBoundType = kInsideOut_BoundsType; + break; + case kPrev_InvCur_FillCombo: + // The only pixels that won't be drawable are inside + // this clip's finite bound + break; + case kPrev_Cur_FillCombo: + fFiniteBound.join(prevFinite); + break; + default: + SkDEBUGFAIL("SkClipStack::Rec::CombineBoundsUnion Invalid fill combination"); + break; + } + } + + // a mirror of CombineBoundsUnion + void CombineBoundsIntersection(int combination, const SkRect& prevFinite) { + + switch (combination) { + case kInvPrev_InvCur_FillCombo: + // The only pixels that aren't writable in this case + // occur in the union of the two finite bounds + fFiniteBound.join(prevFinite); + fFiniteBoundType = kInsideOut_BoundsType; + break; + case kInvPrev_Cur_FillCombo: + // In this case the only pixels that will remain writeable + // are within the current clip + break; + case kPrev_InvCur_FillCombo: + // In this case the only pixels that will remain writeable + // are with the previous clip + fFiniteBound = prevFinite; + fFiniteBoundType = kNormal_BoundsType; + break; + case kPrev_Cur_FillCombo: + if (!fFiniteBound.intersect(prevFinite)) { + fFiniteBound.setEmpty(); + } + break; + default: + SkDEBUGFAIL("SkClipStack::Rec::CombineBoundsIntersection Invalid fill combination"); + break; + } + } + + // a mirror of CombineBoundsDiff + void CombineBoundsRevDiff(int combination, const SkRect& prevFinite) { + + switch (combination) { + case kInvPrev_InvCur_FillCombo: + // The only pixels that can survive are in the + // previous bound since the extensions to infinity in + // both clips cancel out + fFiniteBound = prevFinite; + fFiniteBoundType = kNormal_BoundsType; + break; + case kInvPrev_Cur_FillCombo: + if (!fFiniteBound.intersect(prevFinite)) { + fFiniteBound.setEmpty(); + } + fFiniteBoundType = kNormal_BoundsType; + break; + case kPrev_InvCur_FillCombo: + fFiniteBound.join(prevFinite); + fFiniteBoundType = kInsideOut_BoundsType; + break; + case kPrev_Cur_FillCombo: + // Fall through - as with the kDifference_Op case, the + // most conservative result bound is the bound of the + // current clip. The prior clip could reduce the size of this + // bound (as in the kDifference_Op case) but we are ignoring + // those cases. + break; + default: + SkDEBUGFAIL("SkClipStack::Rec::CombineBoundsRevDiff Invalid fill combination"); + break; + } + } + + void updateBound(const Rec* prior) { + + // First, optimistically update the current Rec's bound information + // with the current clip's bound + if (kRect_State == fState) { + fFiniteBound = fRect; + fFiniteBoundType = kNormal_BoundsType; + } else { + fFiniteBound = fPath.getBounds(); + + if (fPath.isInverseFillType()) { + fFiniteBoundType = kInsideOut_BoundsType; + } else { + fFiniteBoundType = kNormal_BoundsType; + } + } + + if (!fDoAA) { + // Here we mimic a non-anti-aliased scanline system. If there is + // no anti-aliasing we can integerize the bounding box to exclude + // fractional parts that won't be rendered. + // Note: the left edge is handled slightly differently below. We + // are a bit more generous in the rounding since we don't want to + // risk missing the left pixels when fLeft is very close to .5 + fFiniteBound.set(SkIntToScalar(SkScalarFloorToInt(fFiniteBound.fLeft+0.45f)), + SkIntToScalar(SkScalarRound(fFiniteBound.fTop)), + SkIntToScalar(SkScalarRound(fFiniteBound.fRight)), + SkIntToScalar(SkScalarRound(fFiniteBound.fBottom))); + } + + // Now set up the previous Rec's bound information taking into + // account that there may be no previous clip + SkRect prevFinite; + SkClipStack::BoundsType prevType; + + if (NULL == prior) { + // no prior clip means the entire plane is writable + prevFinite.setEmpty(); // there are no pixels that cannot be drawn to + prevType = kInsideOut_BoundsType; + } else { + prevFinite = prior->fFiniteBound; + prevType = prior->fFiniteBoundType; + } + + FillCombo combination = kPrev_Cur_FillCombo; + if (kInsideOut_BoundsType == fFiniteBoundType) { + combination = (FillCombo) (combination | 0x01); + } + if (kInsideOut_BoundsType == prevType) { + combination = (FillCombo) (combination | 0x02); + } + + SkASSERT(kInvPrev_InvCur_FillCombo == combination || + kInvPrev_Cur_FillCombo == combination || + kPrev_InvCur_FillCombo == combination || + kPrev_Cur_FillCombo == combination); + + // Now integrate with clip with the prior clips + switch (fOp) { + case SkRegion::kDifference_Op: + this->CombineBoundsDiff(combination, prevFinite); + break; + case SkRegion::kXOR_Op: + this->CombineBoundsXOR(combination, prevFinite); + break; + case SkRegion::kUnion_Op: + this->CombineBoundsUnion(combination, prevFinite); + break; + case SkRegion::kIntersect_Op: + this->CombineBoundsIntersection(combination, prevFinite); + break; + case SkRegion::kReverseDifference_Op: + this->CombineBoundsRevDiff(combination, prevFinite); + break; + case SkRegion::kReplace_Op: + // Replace just ignores everything prior + // The current clip's bound information is already filled in + // so nothing to do + break; + default: + SkDebugf("SkRegion::Op error/n"); + SkASSERT(0); + break; + } + } }; SkClipStack::SkClipStack() : fDeque(sizeof(Rec)) { @@ -95,8 +377,8 @@ SkClipStack& SkClipStack::operator=(const SkClipStack& b) { fSaveCount = b.fSaveCount; SkDeque::F2BIter recIter(b.fDeque); for (const Rec* rec = (const Rec*)recIter.next(); - rec != NULL; - rec = (const Rec*)recIter.next()) { + rec != NULL; + rec = (const Rec*)recIter.next()) { new (fDeque.push_back()) Rec(*rec); } @@ -150,26 +432,52 @@ void SkClipStack::restore() { } } +void SkClipStack::getBounds(SkRect* finiteBound, BoundsType* boundType) const { + SkASSERT(NULL != finiteBound && NULL != boundType); + + Rec* rec = (Rec*)fDeque.back(); + + if (NULL == rec) { + // the clip is wide open - the infinite plane w/ no pixels un-writeable + finiteBound->setEmpty(); + *boundType = kInsideOut_BoundsType; + return; + } + + *finiteBound = rec->fFiniteBound; + *boundType = rec->fFiniteBoundType; +} + void SkClipStack::clipDevRect(const SkRect& rect, SkRegion::Op op, bool doAA) { Rec* rec = (Rec*)fDeque.back(); if (rec && rec->canBeIntersected(fSaveCount, op)) { switch (rec->fState) { case Rec::kEmpty_State: + SkASSERT(rec->fFiniteBound.isEmpty()); + SkASSERT(kNormal_BoundsType == rec->fFiniteBoundType); return; case Rec::kRect_State: if (!rec->fRect.intersect(rect)) { rec->fState = Rec::kEmpty_State; + rec->fFiniteBound.setEmpty(); + rec->fFiniteBoundType = kNormal_BoundsType; + return; } + + rec->updateBound(NULL); return; case Rec::kPath_State: if (!SkRect::Intersects(rec->fPath.getBounds(), rect)) { rec->fState = Rec::kEmpty_State; + rec->fFiniteBound.setEmpty(); + rec->fFiniteBoundType = kNormal_BoundsType; return; } break; } } new (fDeque.push_back()) Rec(fSaveCount, rect, op, doAA); + ((Rec*) fDeque.back())->updateBound(rec); } void SkClipStack::clipDevPath(const SkPath& path, SkRegion::Op op, bool doAA) { @@ -182,22 +490,29 @@ void SkClipStack::clipDevPath(const SkPath& path, SkRegion::Op op, bool doAA) { const SkRect& pathBounds = path.getBounds(); switch (rec->fState) { case Rec::kEmpty_State: + SkASSERT(rec->fFiniteBound.isEmpty()); + SkASSERT(kNormal_BoundsType == rec->fFiniteBoundType); return; case Rec::kRect_State: if (!SkRect::Intersects(rec->fRect, pathBounds)) { rec->fState = Rec::kEmpty_State; + rec->fFiniteBound.setEmpty(); + rec->fFiniteBoundType = kNormal_BoundsType; return; } break; case Rec::kPath_State: if (!SkRect::Intersects(rec->fPath.getBounds(), pathBounds)) { rec->fState = Rec::kEmpty_State; + rec->fFiniteBound.setEmpty(); + rec->fFiniteBoundType = kNormal_BoundsType; return; } break; } } new (fDeque.push_back()) Rec(fSaveCount, path, op, doAA); + ((Rec*) fDeque.back())->updateBound(rec); } /////////////////////////////////////////////////////////////////////////////// @@ -306,3 +621,29 @@ void SkClipStack::Iter::reset(const SkClipStack& stack, IterStart startLoc) { fStack = &stack; fIter.reset(stack.fDeque, static_cast<SkDeque::Iter::IterStart>(startLoc)); } + +// helper method +void SkClipStack::getConservativeBounds(int offsetX, + int offsetY, + int maxWidth, + int maxHeight, + SkRect* bounds) const { + SkASSERT(NULL != bounds); + + bounds->setLTRB(0, 0, + SkIntToScalar(maxWidth), SkIntToScalar(maxHeight)); + + SkRect temp; + SkClipStack::BoundsType boundType; + + this->getBounds(&temp, &boundType); + if (SkClipStack::kInsideOut_BoundsType == boundType) { + return; + } + + temp.offset(SkIntToScalar(offsetX), SkIntToScalar(offsetY)); + + if (!bounds->intersect(temp)) { + bounds->setEmpty(); + } +} diff --git a/src/gpu/SkGpuDevice.cpp b/src/gpu/SkGpuDevice.cpp index bd92089cc7..1da5a0a0a4 100644 --- a/src/gpu/SkGpuDevice.cpp +++ b/src/gpu/SkGpuDevice.cpp @@ -361,22 +361,60 @@ void SkGpuDevice::onDetachFromCanvas() { fClipStack = NULL; } +#ifdef SK_DEBUG +static void check_bounds(const SkClipStack& clipStack, + const SkRegion& clipRegion, + const SkIPoint& origin, + int renderTargetWidth, + int renderTargetHeight) { + + SkIRect bound; + SkClipStack::BoundsType boundType; + SkRect temp; + + bound.setLTRB(0, 0, renderTargetWidth, renderTargetHeight); + + clipStack.getBounds(&temp, &boundType); + if (SkClipStack::kNormal_BoundsType == boundType) { + SkIRect temp2; + + temp.roundOut(&temp2); + + temp2.offset(-origin.fX, -origin.fY); + + if (!bound.intersect(temp2)) { + bound.setEmpty(); + } + } + +// GrAssert(bound.contains(clipRegion.getBounds())); +} +#endif + /////////////////////////////////////////////////////////////////////////////// static void convert_matrixclip(GrContext* context, const SkMatrix& matrix, const SkClipStack& clipStack, const SkRegion& clipRegion, - const SkIPoint& origin) { + const SkIPoint& origin, + int renderTargetWidth, int renderTargetHeight) { context->setMatrix(matrix); SkGrClipIterator iter; iter.reset(clipStack); - const SkIRect& skBounds = clipRegion.getBounds(); - GrRect bounds; - bounds.setLTRB(GrIntToScalar(skBounds.fLeft), - GrIntToScalar(skBounds.fTop), - GrIntToScalar(skBounds.fRight), - GrIntToScalar(skBounds.fBottom)); + +#ifdef SK_DEBUG + check_bounds(clipStack, clipRegion, origin, + renderTargetWidth, renderTargetHeight); +#endif + + SkRect bounds; + clipStack.getConservativeBounds(-origin.fX, + -origin.fY, + renderTargetWidth, + renderTargetHeight, + &bounds); + GrClip grc(&iter, GrIntToScalar(-origin.x()), GrIntToScalar(-origin.y()), bounds); context->setClip(grc); @@ -392,8 +430,10 @@ void SkGpuDevice::prepareRenderTarget(const SkDraw& draw) { fContext->setRenderTarget(fRenderTarget); SkASSERT(draw.fClipStack && draw.fClipStack == fClipStack); + convert_matrixclip(fContext, *draw.fMatrix, - *fClipStack, *draw.fClip, this->getOrigin()); + *fClipStack, *draw.fClip, this->getOrigin(), + fRenderTarget->width(), fRenderTarget->height()); fNeedPrepareRenderTarget = false; } } @@ -413,7 +453,8 @@ void SkGpuDevice::gainFocus(const SkMatrix& matrix, const SkRegion& clip) { this->INHERITED::gainFocus(matrix, clip); - convert_matrixclip(fContext, matrix, *fClipStack, clip, this->getOrigin()); + convert_matrixclip(fContext, matrix, *fClipStack, clip, this->getOrigin(), + fRenderTarget->width(), fRenderTarget->height()); DO_DEFERRED_CLEAR; } diff --git a/tests/ClipStackTest.cpp b/tests/ClipStackTest.cpp index 85a999797a..e5001f1100 100644 --- a/tests/ClipStackTest.cpp +++ b/tests/ClipStackTest.cpp @@ -183,6 +183,87 @@ static void test_iterators(skiatest::Reporter* reporter) { } } +static void test_bounds(skiatest::Reporter* reporter) { + + static const int gNumCases = 20; + static const SkRect gAnswerRectsBW[gNumCases] = { + // A op B + { 40, 40, 50, 50 }, + { 10, 10, 50, 50 }, + { 10, 10, 80, 80 }, + { 10, 10, 80, 80 }, + { 40, 40, 80, 80 }, + + // invA op B + { 40, 40, 80, 80 }, + { 0, 0, 100, 100 }, + { 0, 0, 100, 100 }, + { 0, 0, 100, 100 }, + { 40, 40, 50, 50 }, + + // A op invB + { 10, 10, 50, 50 }, + { 40, 40, 50, 50 }, + { 0, 0, 100, 100 }, + { 0, 0, 100, 100 }, + { 0, 0, 100, 100 }, + + // invA op invB + { 0, 0, 100, 100 }, + { 40, 40, 80, 80 }, + { 0, 0, 100, 100 }, + { 10, 10, 80, 80 }, + { 10, 10, 50, 50 }, + }; + + static const SkRegion::Op gOps[] = { + SkRegion::kIntersect_Op, + SkRegion::kDifference_Op, + SkRegion::kUnion_Op, + SkRegion::kXOR_Op, + SkRegion::kReverseDifference_Op + }; + + SkRect rectA, rectB; + + rectA.iset(10, 10, 50, 50); + rectB.iset(40, 40, 80, 80); + + SkPath clipA, clipB; + + clipA.addRoundRect(rectA, SkIntToScalar(5), SkIntToScalar(5)); + clipB.addRoundRect(rectB, SkIntToScalar(5), SkIntToScalar(5)); + + SkClipStack stack; + SkRect bound; + + int testCase = 0; + for (int invBits = 0; invBits < 4; ++invBits) { + for (size_t op = 0; op < SK_ARRAY_COUNT(gOps); ++op) { + + stack.save(); + bool doInvA = SkToBool(invBits & 1); + bool doInvB = SkToBool(invBits & 2); + + clipA.setFillType(doInvA ? SkPath::kInverseEvenOdd_FillType : + SkPath::kEvenOdd_FillType); + clipB.setFillType(doInvB ? SkPath::kInverseEvenOdd_FillType : + SkPath::kEvenOdd_FillType); + + stack.clipDevPath(clipA, SkRegion::kIntersect_Op, false); + stack.clipDevPath(clipB, gOps[op], false); + + stack.getConservativeBounds(0, 0, 100, 100, &bound); + + SkASSERT(testCase < gNumCases); + SkASSERT(bound == gAnswerRectsBW[testCase]); + ++testCase; + + stack.restore(); + } + } +} + static void TestClipStack(skiatest::Reporter* reporter) { SkClipStack stack; @@ -219,6 +300,7 @@ static void TestClipStack(skiatest::Reporter* reporter) { test_assign_and_comparison(reporter); test_iterators(reporter); + test_bounds(reporter); } #include "TestClassDef.h" |