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
diff --git a/samplecode/SamplePathClip.cpp b/samplecode/SamplePathClip.cpp
new file mode 100644
index 0000000..f4dd032
--- /dev/null
+++ b/samplecode/SamplePathClip.cpp
@@ -0,0 +1,85 @@
+#include "SampleCode.h"
+#include "SkView.h"
+#include "SkCanvas.h"
+#include "SkGradientShader.h"
+#include "SkGraphics.h"
+#include "SkImageDecoder.h"
+#include "SkPath.h"
+#include "SkPorterDuff.h"
+#include "SkRegion.h"
+#include "SkShader.h"
+#include "SkUtils.h"
+#include "SkXfermode.h"
+#include "SkColorPriv.h"
+#include "SkColorFilter.h"
+#include "SkTime.h"
+#include "SkTypeface.h"
+
+class PathClipView : public SkView {
+public:
+ SkRect fOval;
+ SkPoint fCenter;
+
+ PathClipView() {
+ fOval.set(0, 0, SkIntToScalar(200), SkIntToScalar(50));
+ fCenter.set(SkIntToScalar(250), SkIntToScalar(250));
+ }
+
+ virtual ~PathClipView() {}
+
+protected:
+ // overrides from SkEventSink
+ virtual bool onQuery(SkEvent* evt) {
+ if (SampleCode::TitleQ(*evt)) {
+ SampleCode::TitleR(evt, "PathClip");
+ return true;
+ }
+ return this->INHERITED::onQuery(evt);
+ }
+
+ void drawBG(SkCanvas* canvas) {
+ canvas->drawColor(SK_ColorWHITE);
+ }
+
+ virtual void onDraw(SkCanvas* canvas) {
+ this->drawBG(canvas);
+
+ SkRect oval = fOval;
+ oval.offset(fCenter.fX - oval.centerX(), fCenter.fY - oval.centerY());
+
+ SkPaint p;
+ p.setAntiAlias(true);
+
+ p.setStyle(SkPaint::kStroke_Style);
+ canvas->drawOval(oval, p);
+
+ SkRect r;
+ r.set(SkIntToScalar(200), SkIntToScalar(200),
+ SkIntToScalar(300), SkIntToScalar(300));
+ canvas->clipRect(r);
+
+ p.setStyle(SkPaint::kFill_Style);
+ p.setColor(SK_ColorRED);
+ canvas->drawRect(r, p);
+
+ p.setColor(0x800000FF);
+ r.set(SkIntToScalar(150), SkIntToScalar(10),
+ SkIntToScalar(250), SkIntToScalar(400));
+ canvas->drawOval(oval, p);
+ }
+
+ virtual SkView::Click* onFindClickHandler(SkScalar x, SkScalar y) {
+ fCenter.set(x, y);
+ this->inval(NULL);
+ return NULL;
+ }
+
+private:
+ typedef SkView INHERITED;
+};
+
+//////////////////////////////////////////////////////////////////////////////
+
+static SkView* MyFactory() { return new PathClipView; }
+static SkViewRegister reg(MyFactory);
+
diff --git a/src/core/SkEdge.cpp b/src/core/SkEdge.cpp
index 6efe1ba..f790d02 100644
--- a/src/core/SkEdge.cpp
+++ b/src/core/SkEdge.cpp
@@ -173,7 +173,7 @@
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 @@
// 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 @@
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 5b0cc75..eb50a42 100644
--- a/src/core/SkEdge.h
+++ b/src/core/SkEdge.h
@@ -75,7 +75,7 @@
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 0000000..c6add69
--- /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 0000000..fcb230f
--- /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 d8f779a..fcf1530 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 @@
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 @@
}
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 93a68ae..0200242 100644
--- a/src/core/core_files.mk
+++ b/src/core/core_files.mk
@@ -58,6 +58,7 @@
SkPixelRef.cpp \
SkPoint.cpp \
SkPtrRecorder.cpp \
+ SkQuadClipper.cpp \
SkRasterizer.cpp \
SkRect.cpp \
SkRefCnt.cpp \
diff --git a/xcode/core/core.xcodeproj/project.pbxproj b/xcode/core/core.xcodeproj/project.pbxproj
index 2e8b069..74a431a 100644
--- a/xcode/core/core.xcodeproj/project.pbxproj
+++ b/xcode/core/core.xcodeproj/project.pbxproj
@@ -125,6 +125,7 @@
005F25E60EF94F7900582A90 /* SkWriter32.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 005F256D0EF94F7900582A90 /* SkWriter32.cpp */; };
005F25E70EF94F7900582A90 /* SkXfermode.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 005F256E0EF94F7900582A90 /* SkXfermode.cpp */; };
005F26960EF955D400582A90 /* SkComposeShader.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 005F26950EF955D400582A90 /* SkComposeShader.cpp */; };
+ 007C786A0F3B4D5F0004B142 /* SkQuadClipper.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 007C78690F3B4D5F0004B142 /* SkQuadClipper.cpp */; };
/* End PBXBuildFile section */
/* Begin PBXFileReference section */
@@ -246,6 +247,7 @@
005F256D0EF94F7900582A90 /* SkWriter32.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SkWriter32.cpp; path = ../../src/core/SkWriter32.cpp; sourceTree = SOURCE_ROOT; };
005F256E0EF94F7900582A90 /* SkXfermode.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SkXfermode.cpp; path = ../../src/core/SkXfermode.cpp; sourceTree = SOURCE_ROOT; };
005F26950EF955D400582A90 /* SkComposeShader.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SkComposeShader.cpp; path = ../../src/core/SkComposeShader.cpp; sourceTree = SOURCE_ROOT; };
+ 007C78690F3B4D5F0004B142 /* SkQuadClipper.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SkQuadClipper.cpp; path = ../../src/core/SkQuadClipper.cpp; sourceTree = SOURCE_ROOT; };
D2AAC046055464E500DB518D /* libcore.a */ = {isa = PBXFileReference; explicitFileType = archive.ar; includeInIndex = 0; path = libcore.a; sourceTree = BUILT_PRODUCTS_DIR; };
/* End PBXFileReference section */
@@ -273,6 +275,7 @@
08FB7795FE84155DC02AAC07 /* src */ = {
isa = PBXGroup;
children = (
+ 007C78690F3B4D5F0004B142 /* SkQuadClipper.cpp */,
002884D40EFAB8F80083E387 /* SkStream.cpp */,
002884C70EFAB8B90083E387 /* SkMMapStream.cpp */,
005F26950EF955D400582A90 /* SkComposeShader.cpp */,
@@ -580,6 +583,7 @@
005F26960EF955D400582A90 /* SkComposeShader.cpp in Sources */,
002884C80EFAB8B90083E387 /* SkMMapStream.cpp in Sources */,
002884D50EFAB8F80083E387 /* SkStream.cpp in Sources */,
+ 007C786A0F3B4D5F0004B142 /* SkQuadClipper.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
diff --git a/xcode/sampleapp/SampleApp.xcodeproj/project.pbxproj b/xcode/sampleapp/SampleApp.xcodeproj/project.pbxproj
index 1df5c61f0..5ecdcc2 100644
--- a/xcode/sampleapp/SampleApp.xcodeproj/project.pbxproj
+++ b/xcode/sampleapp/SampleApp.xcodeproj/project.pbxproj
@@ -64,6 +64,7 @@
007A7CBF0F01658C00A2D6EE /* SampleTypeface.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 007A7CB00F01658C00A2D6EE /* SampleTypeface.cpp */; };
007A7CC00F01658C00A2D6EE /* SampleVertices.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 007A7CB10F01658C00A2D6EE /* SampleVertices.cpp */; };
007A7CC10F01658C00A2D6EE /* SampleXfermodes.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 007A7CB20F01658C00A2D6EE /* SampleXfermodes.cpp */; };
+ 007C785E0F3B4C230004B142 /* SamplePathClip.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 007C785D0F3B4C230004B142 /* SamplePathClip.cpp */; };
00A41E4B0EFC312F00C9CBEB /* SampleArc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 00A41E4A0EFC312F00C9CBEB /* SampleArc.cpp */; };
0156F80407C56A3000C6122B /* Foundation.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 0156F80307C56A3000C6122B /* Foundation.framework */; };
01FC44D507BD3BB800D228F4 /* Quartz.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 01FC44D407BD3BB800D228F4 /* Quartz.framework */; };
@@ -176,6 +177,7 @@
007A7CB00F01658C00A2D6EE /* SampleTypeface.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SampleTypeface.cpp; path = ../../samplecode/SampleTypeface.cpp; sourceTree = SOURCE_ROOT; };
007A7CB10F01658C00A2D6EE /* SampleVertices.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SampleVertices.cpp; path = ../../samplecode/SampleVertices.cpp; sourceTree = SOURCE_ROOT; };
007A7CB20F01658C00A2D6EE /* SampleXfermodes.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SampleXfermodes.cpp; path = ../../samplecode/SampleXfermodes.cpp; sourceTree = SOURCE_ROOT; };
+ 007C785D0F3B4C230004B142 /* SamplePathClip.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SamplePathClip.cpp; path = ../../samplecode/SamplePathClip.cpp; sourceTree = SOURCE_ROOT; };
00A41E4A0EFC312F00C9CBEB /* SampleArc.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = SampleArc.cpp; path = ../../samplecode/SampleArc.cpp; sourceTree = SOURCE_ROOT; };
0156F80307C56A3000C6122B /* Foundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Foundation.framework; path = /System/Library/Frameworks/Foundation.framework; sourceTree = "<absolute>"; };
01FC44D407BD3BB800D228F4 /* Quartz.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Quartz.framework; path = /System/Library/Frameworks/Quartz.framework; sourceTree = "<absolute>"; };
@@ -246,6 +248,7 @@
00A41E4A0EFC312F00C9CBEB /* SampleArc.cpp */,
00003C620EFC22A8000FF73A /* SampleApp.cpp */,
00003C640EFC22A8000FF73A /* SamplePath.cpp */,
+ 007C785D0F3B4C230004B142 /* SamplePathClip.cpp */,
00003C650EFC22A8000FF73A /* SamplePathEffects.cpp */,
);
name = samples;
@@ -505,6 +508,7 @@
007A7CC10F01658C00A2D6EE /* SampleXfermodes.cpp in Sources */,
0041CE3C0F00A12400695E8C /* SampleEncode.cpp in Sources */,
007A7CB60F01658C00A2D6EE /* SampleRegion.cpp in Sources */,
+ 007C785E0F3B4C230004B142 /* SamplePathClip.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};