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

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 \