special-case edge-building for polygons (paths with only lines)

makes the dashing bench faster (from 13.4 -> 11.5 ticks)
Review URL: https://codereview.appspot.com/6449080

git-svn-id: http://skia.googlecode.com/svn/trunk@4916 2bbb7eff-a529-9590-31e7-b0007b416f81

3 files changed, 102 insertions, 8 deletions

diff --git a/include/core/SkLineClipper.h b/include/core/SkLineClipper.h
index 1958395032..2c75e5e2d5 100644
--- a/include/core/SkLineClipper.h
+++ b/include/core/SkLineClipper.h
@@ -14,7 +14,8 @@
 class SkLineClipper {
 public:
     enum {
-        kMaxPoints = 4
+        kMaxPoints = 4,
+        kMaxClippedLineSegments = kMaxPoints - 1
     };
 
     /*  Clip the line pts[0]...pts[1] against clip, ignoring segments that
diff --git a/src/core/SkEdgeBuilder.cpp b/src/core/SkEdgeBuilder.cpp
index 7474ba9502..01a40f0f30 100644
--- a/src/core/SkEdgeBuilder.cpp
+++ b/src/core/SkEdgeBuilder.cpp
@@ -12,14 +12,16 @@
 #include "SkLineClipper.h"
 #include "SkGeometry.h"
 
-SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {}
-
 template <typename T> static T* typedAllocThrow(SkChunkAlloc& alloc) {
     return static_cast<T*>(alloc.allocThrow(sizeof(T)));
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
+SkEdgeBuilder::SkEdgeBuilder() : fAlloc(16*1024) {
+    fEdgeList = NULL;
+}
+
 void SkEdgeBuilder::addLine(const SkPoint pts[]) {
     SkEdge* edge = typedAllocThrow<SkEdge>(fAlloc);
     if (edge->setLine(pts[0], pts[1], NULL, fShiftUp)) {
@@ -77,12 +79,90 @@ static void setShiftedClip(SkRect* dst, const SkIRect& src, int shift) {
              SkIntToScalar(src.fBottom >> shift));
 }
 
+int SkEdgeBuilder::buildPoly(const SkPath& path, const SkIRect* iclip,
+                             int shiftUp) {
+    SkPath::Iter    iter(path, true);
+    SkPoint         pts[4];
+    SkPath::Verb    verb;
+    
+    int maxEdgeCount = path.countPoints();
+    if (iclip) {
+        // clipping can turn 1 line into (up to) kMaxClippedLineSegments, since
+        // we turn portions that are clipped out on the left/right into vertical
+        // segments.
+        maxEdgeCount *= SkLineClipper::kMaxClippedLineSegments;
+    }
+    size_t maxEdgeSize = maxEdgeCount * sizeof(SkEdge);
+    size_t maxEdgePtrSize = maxEdgeCount * sizeof(SkEdge*);
+
+    // lets store the edges and their pointers in the same block
+    char* storage = (char*)fAlloc.allocThrow(maxEdgeSize + maxEdgePtrSize);
+    SkEdge* edge = reinterpret_cast<SkEdge*>(storage);
+    SkEdge** edgePtr = reinterpret_cast<SkEdge**>(storage + maxEdgeSize);
+    // Record the beginning of our pointers, so we can return them to the caller
+    fEdgeList = edgePtr;
+
+    if (iclip) {
+        SkRect clip;
+        setShiftedClip(&clip, *iclip, shiftUp);
+        
+        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
+            switch (verb) {
+                case SkPath::kMove_Verb:
+                case SkPath::kClose_Verb:
+                    // we ignore these, and just get the whole segment from
+                    // the corresponding line/quad/cubic verbs
+                    break;
+                case SkPath::kLine_Verb: {
+                    SkPoint lines[SkLineClipper::kMaxPoints];
+                    int lineCount = SkLineClipper::ClipLine(pts, clip, lines);
+                    SkASSERT(lineCount <= SkLineClipper::kMaxClippedLineSegments);
+                    for (int i = 0; i < lineCount; i++) {
+                        if (edge->setLine(lines[i], lines[i + 1], NULL, shiftUp)) {
+                            *edgePtr++ = edge++;
+                        }
+                    }
+                    break;
+                }
+                default:
+                    SkDEBUGFAIL("unexpected verb");
+                    break;
+            }
+        }
+    } else {
+        while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
+            switch (verb) {
+                case SkPath::kMove_Verb:
+                case SkPath::kClose_Verb:
+                    // we ignore these, and just get the whole segment from
+                    // the corresponding line/quad/cubic verbs
+                    break;
+                case SkPath::kLine_Verb:
+                    if (edge->setLine(pts[0], pts[1], NULL, shiftUp)) {
+                        *edgePtr++ = edge++;
+                    }
+                    break;
+                default:
+                    SkDEBUGFAIL("unexpected verb");
+                    break;
+            }
+        }
+    }
+    SkASSERT((char*)edge <= (char*)fEdgeList);
+    SkASSERT(edgePtr - fEdgeList <= maxEdgeCount);
+    return edgePtr - fEdgeList;
+}
+
 int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
                          int shiftUp) {
     fAlloc.reset();
     fList.reset();
     fShiftUp = shiftUp;
 
+    if (SkPath::kLine_SegmentMask == path.getSegmentMasks()) {
+        return this->buildPoly(path, iclip, shiftUp);
+    }
+
     SkPath::Iter    iter(path, true);
     SkPoint         pts[4];
     SkPath::Verb    verb;
@@ -155,7 +235,7 @@ int SkEdgeBuilder::build(const SkPath& path, const SkIRect* iclip,
             }
         }
     }
+    fEdgeList = fList.begin();
     return fList.count();
 }
 
-
diff --git a/src/core/SkEdgeBuilder.h b/src/core/SkEdgeBuilder.h
index ae21f05b31..714e2b9c86 100644
--- a/src/core/SkEdgeBuilder.h
+++ b/src/core/SkEdgeBuilder.h
@@ -20,19 +20,32 @@ class SkEdgeBuilder {
 public:
     SkEdgeBuilder();
     
+    // returns the number of built edges. The array of those edge pointers
+    // is returned from edgeList().
     int build(const SkPath& path, const SkIRect* clip, int shiftUp);
-
-    SkEdge** edgeList() { return fList.begin(); }
-
+    
+    SkEdge** edgeList() { return fEdgeList; }
+    
 private:
     SkChunkAlloc        fAlloc;
     SkTDArray<SkEdge*>  fList;
-    int                 fShiftUp;
+    
+    /*
+     *  If we're in general mode, we allcoate the pointers in fList, and this
+     *  will point at fList.begin(). If we're in polygon mode, fList will be
+     *  empty, as we will have preallocated room for the pointers in fAlloc's
+     *  block, and fEdgeList will point into that.
+     */
+    SkEdge**            fEdgeList;
 
+    int                 fShiftUp;
+    
     void addLine(const SkPoint pts[]);
     void addQuad(const SkPoint pts[]);
     void addCubic(const SkPoint pts[]);
     void addClipper(SkEdgeClipper*);
+
+    int buildPoly(const SkPath& path, const SkIRect* clip, int shiftUp);
 };
 
 #endif