Faster edge re-sort, drop trailing edges

src/core/SkScan_Path.cpp

 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkScanPriv.h"
 #include "SkBlitter.h"
 #include "SkEdge.h"
@@ skipping 27 matching lines @@
     }
 #else
     #define validate_sort(edge)
 #endif
 
 static inline void remove_edge(SkEdge* edge) {
     edge->fPrev->fNext = edge->fNext;
     edge->fNext->fPrev = edge->fPrev;
 }
 
-static inline void swap_edges(SkEdge* prev, SkEdge* next) {
-    SkASSERT(prev->fNext == next && next->fPrev == prev);
-
-    // remove prev from the list
-    prev->fPrev->fNext = next;
-    next->fPrev = prev->fPrev;
-
-    // insert prev after next
-    prev->fNext = next->fNext;
-    next->fNext->fPrev = prev;
-    next->fNext = prev;
-    prev->fPrev = next;
+static inline void insert_edge_after(SkEdge* edge, SkEdge* afterMe) {
+    edge->fPrev = afterMe;
+    edge->fNext = afterMe->fNext;
+    afterMe->fNext->fPrev = edge;
+    afterMe->fNext = edge;
 }
 
 static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, curr_y)) {
     SkFixed x = edge->fX;
 
-    for (;;) {
-        SkEdge* prev = edge->fPrev;
-
-        // add 1 to curr_y since we may have added new edges (built from curves)
-        // that start on the next scanline
-        SkASSERT(prev && prev->fFirstY <= curr_y + 1);
-
-        if (prev->fX <= x) {
-            break;
-        }
-        swap_edges(prev, edge);
+    SkEdge* prev = edge->fPrev;
+    while (prev->fX > x) {
+        prev = prev->fPrev;
+    }
+    if (prev->fNext != edge) {
+        remove_edge(edge);
+        insert_edge_after(edge, prev);
     }
 }
 
 static void insert_new_edges(SkEdge* newEdge, int curr_y) {
     SkASSERT(newEdge->fFirstY >= curr_y);
 
     while (newEdge->fFirstY == curr_y) {
         SkEdge* next = newEdge->fNext;
         backward_insert_edge_based_on_x(newEdge  SkPARAM(curr_y));
         newEdge = next;
@@ skipping 20 matching lines @@
 #pragma warning ( push )
 #pragma warning ( disable : 4701 )
 #endif
 
 typedef void (*PrePostProc)(SkBlitter* blitter, int y, bool isStartOfScanline);
 #define PREPOST_START   true
 #define PREPOST_END     false
 
 static void walk_edges(SkEdge* prevHead, SkPath::FillType fillType,
                        SkBlitter* blitter, int start_y, int stop_y,
-                       PrePostProc proc) {
+                       PrePostProc proc, int rightClip) {
     validate_sort(prevHead->fNext);
 
     int curr_y = start_y;
     // returns 1 for evenodd, -1 for winding, regardless of inverse-ness
     int windingMask = (fillType & 1) ? 1 : -1;
 
     for (;;) {
         int     w = 0;
         int     left SK_INIT_TO_AVOID_WARNING;
         bool    in_interval = false;
@@ skipping 49 matching lines @@
                 if (newX < prevX) { // ripple currE backwards until it is x-sorted
                     backward_insert_edge_based_on_x(currE  SkPARAM(curr_y));
                 } else {
                     prevX = newX;
                 }
             }
             currE = next;
             SkASSERT(currE);
         }
 
+        // was our right-edge culled away?
+        if (in_interval) {
+            int width = rightClip - left;
+            if (width > 0) {
+                blitter->blitH(left, curr_y, width);
+            }
+        }
+
         if (proc) {
             proc(blitter, curr_y, PREPOST_END);    // post-proc
         }
 
         curr_y += 1;
         if (curr_y >= stop_y) {
             break;
         }
         // now currE points to the first edge with a Yint larger than curr_y
         insert_new_edges(currE, curr_y);
@@ skipping 227 matching lines @@
     *last = list[count - 1];
     return list[0];
 }
 
 // clipRect may be null, even though we always have a clip. This indicates that
 // the path is contained in the clip, and so we can ignore it during the blit
 //
 // clipRect (if no null) has already been shifted up
 //
 void sk_fill_path(const SkPath& path, const SkIRect* clipRect, SkBlitter* blitter,
-                  int start_y, int stop_y, int shiftEdgesUp,
-                  const SkRegion& clipRgn) {
+                  int start_y, int stop_y, int shiftEdgesUp, const SkRegion& clipRgn) {
     SkASSERT(blitter);
 
     SkEdgeBuilder   builder;
 
-    int count = builder.build(path, clipRect, shiftEdgesUp);
+    // If we're convex, then we need both edges, even the right edge is past the clip
+    const bool cullToTheRight = !path.isConvex();
+
+    int count = builder.build(path, clipRect, shiftEdgesUp, cullToTheRight);
     SkEdge**    list = builder.edgeList();
 
     if (count < 2) {
         if (path.isInverseFillType()) {
             /*
              *  Since we are in inverse-fill, our caller has already drawn above
              *  our top (start_y) and will draw below our bottom (stop_y). Thus
              *  we need to restrict our drawing to the intersection of the clip
              *  and those two limits.
              */
@@ skipping 46 matching lines @@
 
     if (path.isInverseFillType()) {
         ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp);
         blitter = &ib;
         proc = PrePostInverseBlitterProc;
     }
 
     if (path.isConvex() && (NULL == proc)) {
         walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, NULL);
     } else {
-        walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc);
+        int rightEdge;
+        if (clipRect) {
+            rightEdge = clipRect->right();
+        } else {
+            rightEdge = SkScalarRoundToInt(path.getBounds().right()) << shiftEdgesUp;
+        }
+        
+        walk_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, proc, rightEdge);
     }
 }
 
 void sk_blit_above(SkBlitter* blitter, const SkIRect& ir, const SkRegion& clip) {
     const SkIRect& cr = clip.getBounds();
     SkIRect tmp;
 
     tmp.fLeft = cr.fLeft;
     tmp.fRight = cr.fRight;
     tmp.fTop = cr.fTop;
@@ skipping 207 matching lines @@
         clipRgn = &wrap.getRgn();
         blitter = wrap.getBlitter();
     }
 
     SkScanClipper clipper(blitter, clipRgn, ir);
     blitter = clipper.getBlitter();
     if (blitter) {
         sk_fill_triangle(pts, clipper.getClipRect(), blitter, ir);
     }
 }