diff options
author | 2009-02-06 13:30:58 +0000 | |
---|---|---|
committer | 2009-02-06 13:30:58 +0000 | |
commit | c07d23a6e220c0aff36e3e4e06c1b685a440108e (patch) | |
tree | 7d4a82a92693d62d09516fde0864841075dbbce1 /src/core | |
parent | 3a859a00342ed078af683fd1901fd26c93dd40f0 (diff) |
Chop quads exactly on the clip bounds, so we don't spend CPU cycles walking them
when we're above or below the clip.
Still to do:
- chop in X to avoid 16.16. overflow in the edgelist
- apply the same logic for cubics (tho much harder math)
git-svn-id: http://skia.googlecode.com/svn/trunk@88 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'src/core')
-rw-r--r-- | src/core/SkEdge.cpp | 14 | ||||
-rw-r--r-- | src/core/SkEdge.h | 2 | ||||
-rw-r--r-- | src/core/SkQuadClipper.cpp | 92 | ||||
-rw-r--r-- | src/core/SkQuadClipper.h | 41 | ||||
-rw-r--r-- | src/core/SkScan_Path.cpp | 23 | ||||
-rw-r--r-- | src/core/core_files.mk | 1 |
6 files changed, 155 insertions, 18 deletions
diff --git a/src/core/SkEdge.cpp b/src/core/SkEdge.cpp index 6efe1bad39..f790d02a8b 100644 --- a/src/core/SkEdge.cpp +++ b/src/core/SkEdge.cpp @@ -173,7 +173,7 @@ static inline int diff_to_shift(SkFDot6 dx, SkFDot6 dy) return (32 - SkCLZ(dist)) >> 1; } -int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], const SkIRect* clip, int shift) +int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift) { SkFDot6 x0, y0, x1, y1, x2, y2; @@ -212,9 +212,6 @@ int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], const SkIRect* clip, int // are we a zero-height quad (line)? if (top == bot) return 0; - // are we completely above or below the clip? - if (clip && (top >= clip->fBottom || bot <= clip->fTop)) - return 0; // compute number of steps needed (1 << shift) { @@ -252,15 +249,6 @@ int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], const SkIRect* clip, int fQLastX = SkFDot6ToFixed(x2); fQLastY = SkFDot6ToFixed(y2); - if (clip) - { - do { - for (;!this->updateQuadratic();) - ; - } while (!this->intersectsClip(*clip)); - this->chopLineWithClip(*clip); - return 1; - } return this->updateQuadratic(); } diff --git a/src/core/SkEdge.h b/src/core/SkEdge.h index 5b0cc75d4c..eb50a4245a 100644 --- a/src/core/SkEdge.h +++ b/src/core/SkEdge.h @@ -75,7 +75,7 @@ struct SkQuadraticEdge : public SkEdge { SkFixed fQDDx, fQDDy; SkFixed fQLastX, fQLastY; - int setQuadratic(const SkPoint pts[3], const SkIRect* clip, int shiftUp); + int setQuadratic(const SkPoint pts[3], int shiftUp); int updateQuadratic(); }; diff --git a/src/core/SkQuadClipper.cpp b/src/core/SkQuadClipper.cpp new file mode 100644 index 0000000000..c6add69745 --- /dev/null +++ b/src/core/SkQuadClipper.cpp @@ -0,0 +1,92 @@ +/* + * Copyright (C) 2009 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "SkQuadClipper.h" +#include "SkGeometry.h" + +static bool chopMonoQuadAtY(SkPoint pts[3], SkScalar y, 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 roots[2]; // we only expect one, but make room for 2 for safety + int count = SkFindUnitQuadRoots(A, B, C, roots); + if (count) { + *t = roots[0]; + return true; + } + return false; +} + +SkQuadClipper::SkQuadClipper() {} + +void SkQuadClipper::setClip(const SkIRect& clip) { + // conver to scalars, since that's where we'll see the points + fClip.set(clip); +} + +/* If we somehow returned the fact that we had to flip the pts in Y, we could + communicate that to setQuadratic, and then avoid having to flip it back + here (only to have setQuadratic do the flip again) + */ +bool SkQuadClipper::clipQuad(const SkPoint srcPts[3], SkPoint dst[3]) { + bool reverse; + + // we need the data to be monotonically descending in Y + if (srcPts[0].fY > srcPts[2].fY) { + dst[0] = srcPts[2]; + dst[1] = srcPts[1]; + dst[2] = srcPts[0]; + reverse = true; + } else { + memcpy(dst, srcPts, 3 * sizeof(SkPoint)); + reverse = false; + } + + // are we completely above or below + const SkScalar ctop = fClip.fTop; + const SkScalar cbot = fClip.fBottom; + if (dst[2].fY <= ctop || dst[0].fY >= cbot) { + return false; + } + + SkScalar t; + SkPoint tmp[5]; // for SkChopQuadAt + + // are we partially above + if (dst[0].fY < ctop && chopMonoQuadAtY(dst, ctop, &t)) { + SkChopQuadAt(dst, tmp, t); + dst[0] = tmp[2]; + dst[1] = tmp[3]; + } + + // are we partially below + if (dst[2].fY > cbot && chopMonoQuadAtY(dst, cbot, &t)) { + SkChopQuadAt(dst, tmp, t); + dst[1] = tmp[1]; + dst[2] = tmp[2]; + } + + if (reverse) { + SkTSwap<SkPoint>(dst[0], dst[2]); + } + return true; +} + diff --git a/src/core/SkQuadClipper.h b/src/core/SkQuadClipper.h new file mode 100644 index 0000000000..fcb230f7fa --- /dev/null +++ b/src/core/SkQuadClipper.h @@ -0,0 +1,41 @@ +/* + * Copyright (C) 2009 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef SkQuadClipper_DEFINED +#define SkQuadClipper_DEFINED + +#include "SkPoint.h" +#include "SkRect.h" + +/** This class is initialized with a clip rectangle, and then can be fed quads, + which must already be monotonic in Y. + + In the future, it might return a series of segments, allowing it to clip + also in X, to ensure that all segments fit in a finite coordinate system. + */ +class SkQuadClipper { +public: + SkQuadClipper(); + + void setClip(const SkIRect& clip); + + bool clipQuad(const SkPoint src[3], SkPoint dst[3]); + +private: + SkRect fClip; +}; + +#endif diff --git a/src/core/SkScan_Path.cpp b/src/core/SkScan_Path.cpp index d8f779a32c..fcf1530c80 100644 --- a/src/core/SkScan_Path.cpp +++ b/src/core/SkScan_Path.cpp @@ -20,6 +20,7 @@ #include "SkEdge.h" #include "SkGeometry.h" #include "SkPath.h" +#include "SkQuadClipper.h" #include "SkRegion.h" #include "SkTemplates.h" @@ -306,6 +307,14 @@ static int build_edges(SkEdge edge[], const SkPath& path, SkPath::Iter iter(path, true); SkPoint pts[4]; SkPath::Verb verb; + + SkQuadClipper qclipper; + if (clipRect) { + SkIRect r; + r.set(clipRect->fLeft >> shiftUp, clipRect->fTop >> shiftUp, + clipRect->fRight >> shiftUp, clipRect->fBottom >> shiftUp); + qclipper.setClip(r); + } while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { switch (verb) { @@ -316,17 +325,23 @@ static int build_edges(SkEdge edge[], const SkPath& path, } break; case SkPath::kQuad_Verb: { - SkPoint tmp[5]; + SkPoint tmp[5], clippedPts[3]; SkPoint* p = tmp; int count = SkChopQuadAtYExtrema(pts, tmp); do { - if (((SkQuadraticEdge*)edge)->setQuadratic(p, clipRect, - shiftUp)) - { + const SkPoint* qpts = p; + if (clipRect) { + if (!qclipper.clipQuad(p, clippedPts)) { + goto NEXT_CHOPPED_QUAD; + } + qpts = clippedPts; + } + if (((SkQuadraticEdge*)edge)->setQuadratic(qpts, shiftUp)) { *list++ = edge; edge = (SkEdge*)((char*)edge + sizeof(SkQuadraticEdge)); } + NEXT_CHOPPED_QUAD: p += 2; } while (--count >= 0); break; diff --git a/src/core/core_files.mk b/src/core/core_files.mk index 93a68ae8b8..0200242239 100644 --- a/src/core/core_files.mk +++ b/src/core/core_files.mk @@ -58,6 +58,7 @@ SOURCE := \ SkPixelRef.cpp \ SkPoint.cpp \ SkPtrRecorder.cpp \ + SkQuadClipper.cpp \ SkRasterizer.cpp \ SkRect.cpp \ SkRefCnt.cpp \ |