diff options
author | reed@android.com <reed@android.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2009-11-17 18:47:52 +0000 |
---|---|---|
committer | reed@android.com <reed@android.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2009-11-17 18:47:52 +0000 |
commit | 77f0ef726f1f8b6769ed2509171afce8bac00b23 (patch) | |
tree | 4c2506498fc0506fd1df67ce49a706f12b90b4b1 /src/core/SkQuadClipper.cpp | |
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/core/SkQuadClipper.cpp')
-rw-r--r-- | src/core/SkQuadClipper.cpp | 229 |
1 files changed, 225 insertions, 4 deletions
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; +} + |