diff options
author | 2009-11-17 18:47:52 +0000 | |
---|---|---|
committer | 2009-11-17 18:47:52 +0000 | |
commit | 77f0ef726f1f8b6769ed2509171afce8bac00b23 (patch) | |
tree | 4c2506498fc0506fd1df67ce49a706f12b90b4b1 /src | |
parent | 4e753558fc8cc2f77cbcd46fba80d8612e836a1e (diff) |
add quadclipping utility, plus sample test
git-svn-id: http://skia.googlecode.com/svn/trunk@429 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'src')
-rw-r--r-- | src/core/SkGeometry.cpp | 47 | ||||
-rw-r--r-- | src/core/SkQuadClipper.cpp | 229 | ||||
-rw-r--r-- | src/core/SkQuadClipper.h | 33 |
3 files changed, 288 insertions, 21 deletions
diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp index 2775543919..483c08e35b 100644 --- a/src/core/SkGeometry.cpp +++ b/src/core/SkGeometry.cpp @@ -260,22 +260,14 @@ static inline void flatten_double_quad_extrema(SkScalar coords[14]) coords[2] = coords[6] = coords[4]; } -static inline void force_quad_monotonic_in_y(SkPoint pts[3]) -{ - // zap pts[1].fY to the nearest value - SkScalar ab = SkScalarAbs(pts[0].fY - pts[1].fY); - SkScalar bc = SkScalarAbs(pts[1].fY - pts[2].fY); - pts[1].fY = ab < bc ? pts[0].fY : pts[2].fY; -} - /* Returns 0 for 1 quad, and 1 for two quads, either way the answer is - stored in dst[]. Guarantees that the 1/2 quads will be monotonic. -*/ + stored in dst[]. Guarantees that the 1/2 quads will be monotonic. + */ int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) { SkASSERT(src); SkASSERT(dst); - + #if 0 static bool once = true; if (once) @@ -288,11 +280,11 @@ int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) SkDebugf("chop=%d, Y=[%x %x %x %x %x %x]\n", n, d[0].fY, d[1].fY, d[2].fY, d[3].fY, d[4].fY, d[5].fY); } #endif - + SkScalar a = src[0].fY; SkScalar b = src[1].fY; SkScalar c = src[2].fY; - + if (is_not_monotonic(a, b, c)) { SkScalar tValue; @@ -312,6 +304,35 @@ int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) return 0; } +/* Returns 0 for 1 quad, and 1 for two quads, either way the answer is + stored in dst[]. Guarantees that the 1/2 quads will be monotonic. + */ +int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) +{ + SkASSERT(src); + SkASSERT(dst); + + SkScalar a = src[0].fX; + SkScalar b = src[1].fX; + SkScalar c = src[2].fX; + + if (is_not_monotonic(a, b, c)) { + SkScalar tValue; + if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { + SkChopQuadAt(src, dst, tValue); + flatten_double_quad_extrema(&dst[0].fX); + return 1; + } + // if we get here, we need to force dst to be monotonic, even though + // we couldn't compute a unit_divide value (probably underflow). + b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; + } + dst[0].set(a, src[0].fY); + dst[1].set(b, src[1].fY); + dst[2].set(c, src[2].fY); + return 0; +} + // F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2 // F'(t) = 2 (b - a) + 2 (a - 2b + c) t // F''(t) = 2 (a - 2b + c) diff --git a/src/core/SkQuadClipper.cpp b/src/core/SkQuadClipper.cpp index 7521bdc7fd..9d76298cae 100644 --- a/src/core/SkQuadClipper.cpp +++ b/src/core/SkQuadClipper.cpp @@ -17,14 +17,15 @@ #include "SkQuadClipper.h" #include "SkGeometry.h" -static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { +static bool chopMonoQuadAt(SkScalar c0, SkScalar c1, SkScalar c2, + SkScalar target, SkScalar* t) { /* Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2 * We solve for t, using quadratic equation, hence we have to rearrange * our cooefficents to look like At^2 + Bt + C */ - SkScalar A = pts[0].fY - pts[1].fY - pts[1].fY + pts[2].fY; - SkScalar B = 2*(pts[1].fY - pts[0].fY); - SkScalar C = pts[0].fY - y; + SkScalar A = c0 - c1 - c1 + c2; + SkScalar B = 2*(c1 - c0); + SkScalar C = c0 - target; SkScalar roots[2]; // we only expect one, but make room for 2 for safety int count = SkFindUnitQuadRoots(A, B, C, roots); @@ -35,6 +36,14 @@ static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { return false; } +static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, SkScalar* t) { + return chopMonoQuadAt(pts[0].fY, pts[1].fY, pts[2].fY, y, t); +} + +static bool chopMonoQuadAtX(SkPoint pts[3], SkScalar x, SkScalar* t) { + return chopMonoQuadAt(pts[0].fX, pts[1].fX, pts[2].fX, x, t); +} + SkQuadClipper::SkQuadClipper() {} void SkQuadClipper::setClip(const SkIRect& clip) { @@ -111,3 +120,215 @@ bool SkQuadClipper::clipQuad(const SkPoint srcPts[3], SkPoint dst[3]) { return true; } +/////////////////////////////////////////////////////////////////////////////// + +// Modify pts[] in place so that it is clipped in Y to the clip rect +static void chop_quad_in_Y(SkPoint pts[3], const SkRect& clip) { + SkScalar t; + SkPoint tmp[5]; // for SkChopQuadAt + + // are we partially above + if (pts[0].fY < clip.fTop) { + if (chopMonoQuadAtY(pts, clip.fTop, &t)) { + // take the 2nd chopped quad + SkChopQuadAt(pts, tmp, t); + pts[0] = tmp[2]; + pts[1] = tmp[3]; + } else { + // if chopMonoQuadAtY failed, then we may have hit inexact numerics + // so we just clamp against the top + for (int i = 0; i < 3; i++) { + if (pts[i].fY < clip.fTop) { + pts[i].fY = clip.fTop; + } + } + } + } + + // are we partially below + if (pts[2].fY > clip.fBottom) { + if (chopMonoQuadAtY(pts, clip.fBottom, &t)) { + SkChopQuadAt(pts, tmp, t); + pts[1] = tmp[1]; + pts[2] = tmp[2]; + } else { + // if chopMonoQuadAtY failed, then we may have hit inexact numerics + // so we just clamp against the bottom + for (int i = 0; i < 3; i++) { + if (pts[i].fY > clip.fBottom) { + pts[i].fY = clip.fBottom; + } + } + } + } +} + +/* src[] must be monotonic in Y. This routine copies src into dst, and sorts + it to be increasing in Y. If it had to reverse the order of the points, + it returns true, otherwise it returns false + */ +static bool sort_increasing_Y(SkPoint dst[], const SkPoint src[]) { + // we need the data to be monotonically increasing in Y + if (src[0].fY > src[2].fY) { + SkASSERT(src[0].fY >= src[1].fY); + SkASSERT(src[1].fY >= src[2].fY); + dst[0] = src[2]; + dst[1] = src[1]; + dst[2] = src[0]; + return true; + } else { + SkASSERT(src[2].fY >= src[1].fY); + SkASSERT(src[1].fY >= src[0].fY); + memcpy(dst, src, 3 * sizeof(SkPoint)); + return false; + } +} + +// srcPts[] must be monotonic in X and Y +void SkQuadClipper2::clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip) { + SkPoint pts[3]; + bool reverse = sort_increasing_Y(pts, srcPts); + + // are we completely above or below + if (pts[2].fY <= clip.fTop || pts[0].fY >= clip.fBottom) { + return; + } + + // Now chop so that pts is contained within clip in Y + chop_quad_in_Y(pts, clip); + + if (pts[0].fX > pts[2].fX) { + SkTSwap<SkPoint>(pts[0], pts[2]); + reverse = !reverse; + } + SkASSERT(pts[0].fX <= pts[1].fX); + SkASSERT(pts[1].fX <= pts[2].fX); + + // Now chop in X has needed, and record the segments + + if (pts[2].fX <= clip.fLeft) { // wholly to the left + this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); + return; + } + if (pts[0].fX >= clip.fRight) { // wholly to the right + this->appendVLine(clip.fRight, pts[0].fY, pts[2].fY, reverse); + return; + } + + SkScalar t; + SkPoint tmp[5]; // for SkChopQuadAt + + // are we partially to the left + if (pts[0].fX < clip.fLeft) { + if (chopMonoQuadAtX(pts, clip.fLeft, &t)) { + SkChopQuadAt(pts, tmp, t); + this->appendVLine(clip.fLeft, tmp[0].fY, tmp[2].fY, reverse); + pts[0] = tmp[2]; + pts[1] = tmp[3]; + } else { + // if chopMonoQuadAtY failed, then we may have hit inexact numerics + // so we just clamp against the left + this->appendVLine(clip.fLeft, pts[0].fY, pts[2].fY, reverse); + } + } + + // are we partially to the right + if (pts[2].fX > clip.fRight) { + if (chopMonoQuadAtX(pts, clip.fRight, &t)) { + SkChopQuadAt(pts, tmp, t); + this->appendQuad(tmp, reverse); + this->appendVLine(clip.fRight, tmp[2].fY, tmp[4].fY, reverse); + } else { + // if chopMonoQuadAtY failed, then we may have hit inexact numerics + // so we just clamp against the right + this->appendVLine(clip.fRight, pts[0].fY, pts[3].fY, reverse); + } + } else { // wholly inside the clip + this->appendQuad(pts, reverse); + } +} + +static bool quick_reject_quad(const SkPoint srcPts[3], const SkRect& clip) { + return (srcPts[0].fY <= clip.fTop && + srcPts[1].fY <= clip.fTop && + srcPts[2].fY <= clip.fTop) + || + (srcPts[0].fY >= clip.fBottom && + srcPts[1].fY >= clip.fBottom && + srcPts[2].fY >= clip.fBottom); +} + +bool SkQuadClipper2::clipQuad(const SkPoint srcPts[3], const SkRect& clip) { + fCurrPoint = fPoints; + fCurrVerb = fVerbs; + + if (!quick_reject_quad(srcPts, clip)) { + SkPoint monoY[5]; + int countY = SkChopQuadAtYExtrema(srcPts, monoY); + for (int y = 0; y <= countY; y++) { + SkPoint monoX[5]; + int countX = SkChopQuadAtXExtrema(&monoY[y * 2], monoX); + SkASSERT(countY + countX <= 3); + for (int x = 0; x <= countX; x++) { + this->clipMonoQuad(&monoX[x * 2], clip); + SkASSERT(fCurrVerb - fVerbs < kMaxVerbs); + SkASSERT(fCurrPoint - fPoints <= kMaxPoints); + } + } + } + + *fCurrVerb = SkPath::kDone_Verb; + fCurrPoint = fPoints; + fCurrVerb = fVerbs; + return SkPath::kDone_Verb != fVerbs[0]; +} + +void SkQuadClipper2::appendVLine(SkScalar x, SkScalar y0, SkScalar y1, + bool reverse) { + *fCurrVerb++ = SkPath::kLine_Verb; + + if (reverse) { + SkTSwap<SkScalar>(y0, y1); + } + fCurrPoint[0].set(x, y0); + fCurrPoint[1].set(x, y1); + fCurrPoint += 2; +} + +void SkQuadClipper2::appendQuad(const SkPoint pts[3], bool reverse) { + *fCurrVerb++ = SkPath::kQuad_Verb; + + if (reverse) { + fCurrPoint[0] = pts[2]; + fCurrPoint[2] = pts[0]; + } else { + fCurrPoint[0] = pts[0]; + fCurrPoint[2] = pts[2]; + } + fCurrPoint[1] = pts[1]; + fCurrPoint += 3; +} + +SkPath::Verb SkQuadClipper2::next(SkPoint pts[]) { + SkPath::Verb verb = *fCurrVerb; + + switch (verb) { + case SkPath::kLine_Verb: + memcpy(pts, fCurrPoint, 2 * sizeof(SkPoint)); + fCurrPoint += 2; + fCurrVerb += 1; + break; + case SkPath::kQuad_Verb: + memcpy(pts, fCurrPoint, 3 * sizeof(SkPoint)); + fCurrPoint += 3; + fCurrVerb += 1; + break; + case SkPath::kDone_Verb: + break; + default: + SkASSERT(!"unexpected verb in quadclippper2 iter"); + break; + } + return verb; +} + diff --git a/src/core/SkQuadClipper.h b/src/core/SkQuadClipper.h index fcb230f7fa..9f9a6d5bae 100644 --- a/src/core/SkQuadClipper.h +++ b/src/core/SkQuadClipper.h @@ -17,8 +17,7 @@ #ifndef SkQuadClipper_DEFINED #define SkQuadClipper_DEFINED -#include "SkPoint.h" -#include "SkRect.h" +#include "SkPath.h" /** This class is initialized with a clip rectangle, and then can be fed quads, which must already be monotonic in Y. @@ -31,11 +30,37 @@ public: SkQuadClipper(); void setClip(const SkIRect& clip); - - bool clipQuad(const SkPoint src[3], SkPoint dst[3]); + bool clipQuad(const SkPoint src[3], SkPoint dst[3]); + private: SkRect fClip; }; +/** Iterator that returns the clipped segements of a quad clipped to a rect. + The segments will be either lines or quads (based on SkPath::Verb), and + will all be monotonic in Y + */ +class SkQuadClipper2 { +public: + bool clipQuad(const SkPoint pts[3], const SkRect& clip); + + SkPath::Verb next(SkPoint pts[]); + +private: + SkPoint* fCurrPoint; + SkPath::Verb* fCurrVerb; + + enum { + kMaxVerbs = 10, + kMaxPoints = 21 + }; + SkPoint fPoints[kMaxPoints]; + SkPath::Verb fVerbs[kMaxVerbs]; + + void clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip); + void appendVLine(SkScalar x, SkScalar y0, SkScalar y1, bool reverse); + void appendQuad(const SkPoint pts[3], bool reverse); +}; + #endif |