new edgelist builder that chops segments into clip-sized coordinates, to avoid overflows

The change is conditional at the moment inside SkScan_Path.cpp, USE_NEW_BUILDER.

This chopping is meant to only pass in reasonable floats to the edgelist, so that we never
overflow when converting to fixed-point. It also has the side-effect of speeding up edges
to the left/right of the clip, since those become vertical lines, which are faster to
walk over than the original curve segment.

Future optimizations: throw away segments to the right of the clip, and tweak the edgelist
walker to not require an explicit matching right-edge for the current run.

5 files changed, 118 insertions, 10 deletions

diff --git a/include/core/SkEdgeClipper.h b/include/core/SkEdgeClipper.h
new file mode 100644
index 0000000..6720b9c
--- /dev/null
+++ b/include/core/SkEdgeClipper.h
@@ -0,0 +1,58 @@
+/*
+ * 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 SkEdgeClipper_DEFINED
+#define SkEdgeClipper_DEFINED
+
+#include "SkPath.h"
+
+/** This is basically an iterator. It is initialized with an edge and a clip,
+    and then next() is called until it returns kDone_Verb.
+ */
+class SkEdgeClipper {
+public:
+    bool clipQuad(const SkPoint pts[3], const SkRect& clip);
+    bool clipCubic(const SkPoint pts[4], const SkRect& clip);
+
+    SkPath::Verb next(SkPoint pts[]);
+    
+private:
+    SkPoint*        fCurrPoint;
+    SkPath::Verb*   fCurrVerb;
+    
+    enum {
+        kMaxVerbs = 13,
+        kMaxPoints = 32
+    };
+    SkPoint         fPoints[kMaxPoints];
+    SkPath::Verb    fVerbs[kMaxVerbs];
+
+    void clipMonoQuad(const SkPoint srcPts[3], const SkRect& clip);
+    void clipMonoCubic(const SkPoint srcPts[4], const SkRect& clip);
+    void appendVLine(SkScalar x, SkScalar y0, SkScalar y1, bool reverse);
+    void appendQuad(const SkPoint pts[3], bool reverse);
+    void appendCubic(const SkPoint pts[4], bool reverse);
+};
+
+#ifdef SK_DEBUG
+    void sk_assert_monotonic_x(const SkPoint pts[], int count);
+    void sk_assert_monotonic_y(const SkPoint pts[], int count);
+#else
+    #define sk_assert_monotonic_x(pts, count)
+    #define sk_assert_monotonic_y(pts, count)
+#endif
+
+#endif
diff --git a/include/core/SkGeometry.h b/include/core/SkGeometry.h
index c517855..853a7c3 100644
--- a/include/core/SkGeometry.h
+++ b/include/core/SkGeometry.h
@@ -57,11 +57,11 @@ int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]);
 /** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that
     the resulting beziers are monotonic in Y. This is called by the scan converter.
     Depending on what is returned, dst[] is treated as follows
-    1   dst[0..2] is the original quad
-    2   dst[0..2] and dst[2..4] are the two new quads
-    If dst == null, it is ignored and only the count is returned.
+    0   dst[0..2] is the original quad
+    1   dst[0..2] and dst[2..4] are the two new quads
 */
 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
+int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]);
 
 /** Given 3 points on a quadratic bezier, divide it into 2 quadratics
     if the point of maximum curvature exists on the quad segment.
@@ -110,12 +110,13 @@ int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar
 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
     the resulting beziers are monotonic in Y. This is called by the scan converter.
     Depending on what is returned, dst[] is treated as follows
-    1   dst[0..3] is the original cubic
-    2   dst[0..3] and dst[3..6] are the two new cubics
-    3   dst[0..3], dst[3..6], dst[6..9] are the three new cubics
+    0   dst[0..3] is the original cubic
+    1   dst[0..3] and dst[3..6] are the two new cubics
+    2   dst[0..3], dst[3..6], dst[6..9] are the three new cubics
     If dst == null, it is ignored and only the count is returned.
 */
 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
+int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]);
 
 /** Given a cubic bezier, return 0, 1, or 2 t-values that represent the
     inflection points.
diff --git a/include/core/SkLineClipper.h b/include/core/SkLineClipper.h
new file mode 100644
index 0000000..4c23781
--- /dev/null
+++ b/include/core/SkLineClipper.h
@@ -0,0 +1,40 @@
+#ifndef SkLineClipper_DEFINED
+#define SkLineClipper_DEFINED
+
+#include "SkRect.h"
+#include "SkPoint.h"
+
+class SkLineClipper {
+public:
+    enum {
+        kMaxPoints = 4
+    };
+
+    /*  Clip the line pts[0]...pts[1] against clip, ignoring segments that
+        lie completely above or below the clip. For portions to the left or
+        right, turn those into vertical line segments that are aligned to the
+        edge of the clip.
+         
+        Return the number of line segments that result, and store the end-points
+        of those segments sequentially in lines as follows:
+            1st segment: lines[0]..lines[1]
+            2nd segment: lines[1]..lines[2]
+            3rd segment: lines[2]..lines[3]
+     */
+    static int ClipLine(const SkPoint pts[2], const SkRect& clip,
+                        SkPoint lines[kMaxPoints]);
+
+    /*  Intersect the line segment against the rect. If there is a non-empty
+        resulting segment, return true and set dst[] to that segment. If not,
+        return false and ignore dst[].
+     
+        ClipLine is specialized for scan-conversion, as it adds vertical
+        segments on the sides to show where the line extended beyond the
+        left or right sides. IntersectLine does not.
+     */
+    static bool IntersectLine(const SkPoint src[2], const SkRect& clip,
+                              SkPoint dst[2]);
+};
+
+#endif
+
diff --git a/include/core/SkUtils.h b/include/core/SkUtils.h
index 9f3b1d6..0700aeb 100644
--- a/include/core/SkUtils.h
+++ b/include/core/SkUtils.h
@@ -27,6 +27,8 @@
     @param count    The number of times value should be copied into the buffer.
 */
 void sk_memset16_portable(uint16_t dst[], uint16_t value, int count);
+typedef void (*SkMemset16Proc)(uint16_t dst[], uint16_t value, int count);
+SkMemset16Proc SkMemset16GetPlatformProc();
 
 /** Similar to memset(), but it assigns a 32bit value into the buffer.
     @param buffer   The memory to have value copied into it
@@ -34,6 +36,8 @@ void sk_memset16_portable(uint16_t dst[], uint16_t value, int count);
     @param count    The number of times value should be copied into the buffer.
 */
 void sk_memset32_portable(uint32_t dst[], uint32_t value, int count);
+typedef void (*SkMemset32Proc)(uint32_t dst[], uint32_t value, int count);
+SkMemset32Proc SkMemset32GetPlatformProc();
 
 #ifdef ANDROID
     #include "cutils/memory.h"
@@ -43,14 +47,13 @@ void sk_memset32_portable(uint32_t dst[], uint32_t value, int count);
 #endif
 
 #ifndef sk_memset16
-    #define sk_memset16(dst, value, count)  sk_memset16_portable(dst, value, count)
+extern SkMemset16Proc sk_memset16;
 #endif
 
 #ifndef sk_memset32
-    #define sk_memset32(dst, value, count)  sk_memset32_portable(dst, value, count)
+extern SkMemset32Proc sk_memset32;
 #endif
 
-
 ///////////////////////////////////////////////////////////////////////////
 
 #define kMaxBytesInUTF8Sequence     4
diff --git a/include/views/SkView.h b/include/views/SkView.h
index 1bdd0b6..f3b729f 100644
--- a/include/views/SkView.h
+++ b/include/views/SkView.h
@@ -314,7 +314,13 @@ protected:
 
     /** Override this if you might handle the click
     */
-    virtual Click*  onFindClickHandler(SkScalar x, SkScalar y);
+    virtual Click* onFindClickHandler(SkScalar x, SkScalar y);
+    /** Override this to decide if your children are targets for a click.
+        The default returns true, in which case your children views will be
+        candidates for onFindClickHandler. Returning false wil skip the children
+        and just call your onFindClickHandler.
+     */
+    virtual bool onSendClickToChildren(SkScalar x, SkScalar y);
     /** Override this to track clicks, returning true as long as you want to track
         the pen/mouse.
     */