WIP: GPU-accelerated trapezoidal path renderer.

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"
 #include "SkEdgeBuilder.h"
 #include "SkGeometry.h"
 #include "SkPath.h"
 #include "SkQuadClipper.h"
 #include "SkRasterClip.h"
 #include "SkRegion.h"
+#include "SkStroke.h"
 #include "SkTemplates.h"
 #include "SkTSort.h"
 
+#include <stdio.h> // FIXME
+
+static bool dumping;
+
 #define kEDGE_HEAD_Y    SK_MinS32
 #define kEDGE_TAIL_Y    SK_MaxS32
 
 #ifdef SK_DEBUG
     static void validate_sort(const SkEdge* edge) {
         int y = kEDGE_HEAD_Y;
 
         while (edge->fFirstY != SK_MaxS32) {
             edge->validate();
             SkASSERT(y <= edge->fFirstY);
@@ skipping 11 matching lines @@
     edge->fNext->fPrev = edge->fPrev;
 }
 
 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 emit_wireframe_triangle(SkPoint t[3], SkTDArray<SkPoint>* points) {
+    SkPoint *p = points->append(6);
+    p[0] = t[0];
+    p[1] = t[1];
+    p[2] = t[1];
+    p[3] = t[2];
+    p[4] = t[2];
+    p[5] = t[0];
+}
+
+static void emit_trapezoid(SkEdge* left, SkEdge* right, float top, float bottom, SkTDArray<SkPoint>* points)
+{
+    // If this edge was already neutered by its partner, don't emit.
+    if (top > bottom) {
+        return;
+    }
+
+    if (!left || !right) {
+        return;
+    }
+
+    float top_left = left->fFirstXf;
+    float top_right = right->fFirstXf;
+    float bottom_left = left->fFirstXf + SkFixedToFloat(left->fDX * (bottom - top));
+    float bottom_right = right->fFirstXf + SkFixedToFloat(right->fDX * (bottom - top));
+    if (dumping) {
+        printf("top %g bot %g tl %g tr %g bl %g br %g\n",
+               top, bottom, left->fFirstXf, right->fFirstXf, bottom_left, bottom_right);
+    }
+    if (SkScan::gWireframe) {
+        if (top_left == top_right) {
+            SkPoint p[3];
+            p[0] = SkPoint::Make(top_right,    top);
+            p[1] = SkPoint::Make(bottom_right, bottom);
+            p[2] = SkPoint::Make(bottom_left , bottom);
+            emit_wireframe_triangle(p, points);
+        } else if (bottom_left == bottom_right) {
+            SkPoint p[3];
+            p[0] = SkPoint::Make(top_left,     top);
+            p[1] = SkPoint::Make(top_right,    top);
+            p[2] = SkPoint::Make(bottom_left,  bottom);
+            emit_wireframe_triangle(p, points);
+        } else {
+            SkPoint p[3];
+            p[0] = SkPoint::Make(top_left,     top);
+            p[1] = SkPoint::Make(top_right,    top);
+            p[2] = SkPoint::Make(bottom_left , bottom);
+            emit_wireframe_triangle(p, points);
+            p[0] = SkPoint::Make(top_right,    top);
+            p[1] = SkPoint::Make(bottom_right, bottom);
+            p[2] = SkPoint::Make(bottom_left , bottom);
+            emit_wireframe_triangle(p, points);
+        }
+    } else {
+        if (top_left == top_right) {
+            SkPoint *p = points->append(3);
+            p[0] = SkPoint::Make(top_right,    top);
+            p[1] = SkPoint::Make(bottom_right, bottom);
+            p[2] = SkPoint::Make(bottom_left , bottom);
+        } else if (bottom_left == bottom_right) {
+            SkPoint *p = points->append(3);
+            p[0] = SkPoint::Make(top_left,     top);
+            p[1] = SkPoint::Make(top_right,    top);
+            p[2] = SkPoint::Make(bottom_left,  bottom);
+        } else {
+            SkPoint *p = points->append(6);
+            p[0] = SkPoint::Make(top_left,     top);
+            p[1] = SkPoint::Make(top_right,    top);
+            p[2] = SkPoint::Make(bottom_left , bottom);
+            p[3] = SkPoint::Make(top_right,    top);
+            p[4] = SkPoint::Make(bottom_right, bottom);
+            p[5] = SkPoint::Make(bottom_left , bottom);
+        }
+    }
+    left->fFirstXf = bottom_left;
+    left->fFirstYf = bottom;
+    right->fFirstXf = bottom_right;
+    right->fFirstYf = bottom;
+}
+
+static void emit_all_trapezoids(SkEdge* start, int windingMask, int curr_y, SkTDArray<SkPoint>* points)
+{
+    int w = 0;
+    SkEdge* left = NULL;
+    for (SkEdge* edge = start; edge != NULL && edge->fFirstY < curr_y && edge->fFirstYf < curr_y; edge = edge->fNext) {
+        w += edge->fWinding;
+        if ((w & windingMask) == 0) {
+            SkASSERT(left);
+            emit_trapezoid(left, edge, left->fFirstYf, curr_y, points);
+            left = NULL;
+        } else if (!left) {
+            left = edge;
+        } else {
+            edge->fFirstXf += SkFixedToFloat(edge->fDX * (curr_y - edge->fFirstYf));
+            edge->fFirstYf = (float) curr_y;
+        }
+    }
+}
+
 static void backward_insert_edge_based_on_x(SkEdge* edge SkDECLAREPARAM(int, curr_y)) {
     SkFixed x = edge->fX;
 
     SkEdge* prev = edge->fPrev;
     while (prev->fX > x) {
         prev = prev->fPrev;
     }
     if (prev->fNext != edge) {
         remove_edge(edge);
         insert_edge_after(edge, prev);
@@ skipping 29 matching lines @@
 #if defined _WIN32 && _MSC_VER >= 1300  // disable warning : local variable used without having been initialized
 #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, int rightClip) {
+                       SkBlitter* blitter, SkTDArray<SkPoint>* points,
+                       int start_y, int stop_y, 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;
         SkEdge* currE = prevHead->fNext;
         SkFixed prevX = prevHead->fX;
 
         validate_edges_for_y(currE, curr_y);
 
-        if (proc) {
+        if (proc && blitter) {
             proc(blitter, curr_y, PREPOST_START);    // pre-proc
         }
 
         while (currE->fFirstY <= curr_y) {
             SkASSERT(currE->fLastY >= curr_y);
 
             int x = SkFixedRoundToInt(currE->fX);
             w += currE->fWinding;
             if ((w & windingMask) == 0) { // we finished an interval
                 SkASSERT(in_interval);
                 int width = x - left;
                 SkASSERT(width >= 0);
-                if (width)
-                    blitter->blitH(left, curr_y, width);
+                if (width) {
+                    if (blitter) {
+                        blitter->blitH(left, curr_y, width);
+                    }
+                }
                 in_interval = false;
             } else if (!in_interval) {
                 left = x;
                 in_interval = true;
             }
 
             SkEdge* next = currE->fNext;
             SkFixed newX;
 
             if (currE->fLastY == curr_y) {    // are we done with this edge?
+                if (points) emit_all_trapezoids(prevHead->fNext, windingMask, curr_y + 1, points);
                 if (currE->fCurveCount < 0) {
                     if (((SkCubicEdge*)currE)->updateCubic()) {
                         SkASSERT(currE->fFirstY == curr_y + 1);
 
                         newX = currE->fX;
                         goto NEXT_X;
                     }
                 } else if (currE->fCurveCount > 0) {
                     if (((SkQuadraticEdge*)currE)->updateQuadratic()) {
                         newX = currE->fX;
                         goto NEXT_X;
                     }
                 }
                 remove_edge(currE);
             } else {
                 SkASSERT(currE->fLastY > curr_y);
                 newX = currE->fX + currE->fDX;
                 currE->fX = newX;
             NEXT_X:
                 if (newX < prevX) { // ripple currE backwards until it is x-sorted
+                    if (points) emit_all_trapezoids(prevHead->fNext, windingMask, curr_y + 1, points);
                     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) {
+        if (in_interval && blitter) {
             int width = rightClip - left;
             if (width > 0) {
                 blitter->blitH(left, curr_y, width);
             }
         }
 
-        if (proc) {
+        if (proc && blitter) {
             proc(blitter, curr_y, PREPOST_END);    // post-proc
         }
 
         curr_y += 1;
         if (curr_y >= stop_y) {
             break;
         }
+        if (points && currE->fFirstY == curr_y) {
+            emit_all_trapezoids(prevHead->fNext, windingMask, curr_y, points);
+        }
         // now currE points to the first edge with a Yint larger than curr_y
         insert_new_edges(currE, curr_y);
     }
 }
 
 // return true if we're done with this edge
 static bool update_edge(SkEdge* edge, int last_y) {
     SkASSERT(edge->fLastY >= last_y);
     if (last_y == edge->fLastY) {
         if (edge->fCurveCount < 0) {
             if (((SkCubicEdge*)edge)->updateCubic()) {
                 SkASSERT(edge->fFirstY == last_y + 1);
                 return false;
             }
         } else if (edge->fCurveCount > 0) {
             if (((SkQuadraticEdge*)edge)->updateQuadratic()) {
                 SkASSERT(edge->fFirstY == last_y + 1);
                 return false;
             }
         }
         return true;
     }
     return false;
 }
 
 static void walk_convex_edges(SkEdge* prevHead, SkPath::FillType,
-                              SkBlitter* blitter, int start_y, int stop_y,
+                              SkBlitter* blitter, SkTDArray<SkPoint>* points,
+                              int start_y, int stop_y,
                               PrePostProc proc) {
     validate_sort(prevHead->fNext);
 
     SkEdge* leftE = prevHead->fNext;
     SkEdge* riteE = leftE->fNext;
     SkEdge* currE = riteE->fNext;
 
 #if 0
     int local_top = leftE->fFirstY;
     SkASSERT(local_top == riteE->fFirstY);
@@ skipping 16 matching lines @@
         int local_bot = SkMin32(leftE->fLastY, riteE->fLastY);
         local_bot = SkMin32(local_bot, stop_y - 1);
         SkASSERT(local_top <= local_bot);
 
         SkFixed left = leftE->fX;
         SkFixed dLeft = leftE->fDX;
         SkFixed rite = riteE->fX;
         SkFixed dRite = riteE->fDX;
         int count = local_bot - local_top;
         SkASSERT(count >= 0);
-        if (0 == (dLeft | dRite)) {
+        if (points) {
+            emit_trapezoid(leftE, riteE, (float) local_top, (float) (local_bot + 1), points);
+            if (left < rite) {
+                count += 1;
+                left += count * dLeft;
+                rite += count * dRite;
+            }
+            local_top = local_bot + 1;
+        } else if (0 == (dLeft | dRite)) {
             int L = SkFixedRoundToInt(left);
             int R = SkFixedRoundToInt(rite);
             if (L < R) {
                 count += 1;
                 blitter->blitRect(L, local_top, R - L, count);
+                left += count * dLeft;
+                rite += count * dRite;
             }
             local_top = local_bot + 1;
         } else {
             do {
                 int L = SkFixedRoundToInt(left);
                 int R = SkFixedRoundToInt(rite);
                 if (L < R) {
                     blitter->blitH(L, local_top, R - L);
                 }
                 left += dLeft;
@@ skipping 121 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) {
-    SkASSERT(blitter);
+void sk_fill_path(const SkPath& path, const SkIRect* clipRect,
+                  SkBlitter* blitter, SkTDArray<SkPoint>* points,
+                  int start_y, int stop_y, int shiftEdgesUp,
+                  const SkRegion& clipRgn) {
+    SkASSERT(blitter || points);
 
     SkEdgeBuilder   builder;
 
     // If we're convex, then we need both edges, even the right edge is past the clip
-    const bool canCullToTheRight = !path.isConvex();
+    const bool canCullToTheRight = !path.isConvex() && !points;
 
     int count = builder.build(path, clipRect, shiftEdgesUp, canCullToTheRight);
     SkASSERT(count >= 0);
 
     SkEdge**    list = builder.edgeList();
 
     if (0 == count) {
         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.
              */
             SkIRect rect = clipRgn.getBounds();
             if (rect.fTop < start_y) {
                 rect.fTop = start_y;
             }
             if (rect.fBottom > stop_y) {
                 rect.fBottom = stop_y;
             }
             if (!rect.isEmpty()) {
-                blitter->blitRect(rect.fLeft << shiftEdgesUp,
-                                  rect.fTop << shiftEdgesUp,
-                                  rect.width() << shiftEdgesUp,
-                                  rect.height() << shiftEdgesUp);
+                if (blitter) {
+                    blitter->blitRect(rect.fLeft << shiftEdgesUp,
+                                      rect.fTop << shiftEdgesUp,
+                                      rect.width() << shiftEdgesUp,
+                                      rect.height() << shiftEdgesUp);
+                } else {
+                    SkRect r = SkRect::Make(rect);
+                    r.toQuad(points->append(4));
+                }
             }
         }
+
         return;
     }
 
     SkEdge headEdge, tailEdge, *last;
     // this returns the first and last edge after they're sorted into a dlink list
     SkEdge* edge = sort_edges(list, count, &last);
+    if (dumping) {
+        printf("sorted into %d edges:\n", count);
+        SkEdge* e = edge;
+        for (int i = 0; i < count; i++) {
+            printf("edge %p fFirstXf %g fFirstYf %g fLastY %d fDX %g\n", e, e->fFirstXf, e->fFirstYf, e->fLastY, e->fDX / 65536.0);
+            e = e->fNext;
+        }
+    }
 
     headEdge.fPrev = nullptr;
     headEdge.fNext = edge;
     headEdge.fFirstY = kEDGE_HEAD_Y;
     headEdge.fX = SK_MinS32;
     edge->fPrev = &headEdge;
 
     tailEdge.fPrev = last;
     tailEdge.fNext = nullptr;
     tailEdge.fFirstY = kEDGE_TAIL_Y;
     last->fNext = &tailEdge;
 
     // now edge is the head of the sorted linklist
 
     start_y <<= shiftEdgesUp;
     stop_y <<= shiftEdgesUp;
     if (clipRect && start_y < clipRect->fTop) {
         start_y = clipRect->fTop;
     }
     if (clipRect && stop_y > clipRect->fBottom) {
         stop_y = clipRect->fBottom;
     }
 
     InverseBlitter  ib;
     PrePostProc     proc = nullptr;
 
-    if (path.isInverseFillType()) {
+    if (path.isInverseFillType() && blitter) {
         ib.setBlitter(blitter, clipRgn.getBounds(), shiftEdgesUp);
         blitter = &ib;
         proc = PrePostInverseBlitterProc;
     }
 
-    if (path.isConvex() && (nullptr == proc)) {
+    if (path.isConvex() && (nullptr == proc) && blitter) {
         SkASSERT(count >= 2);   // convex walker does not handle missing right edges
-        walk_convex_edges(&headEdge, path.getFillType(), blitter, start_y, stop_y, nullptr);
+        walk_convex_edges(&headEdge, path.getFillType(), blitter, points, start_y, stop_y, NULL);
     } else {
         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);
+
+        walk_edges(&headEdge, path.getFillType(), blitter, points, 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 99 matching lines @@
 
     SkScanClipper clipper(blitter, clipPtr, ir, path.isInverseFillType());
 
     blitter = clipper.getBlitter();
     if (blitter) {
         // we have to keep our calls to blitter in sorted order, so we
         // must blit the above section first, then the middle, then the bottom.
         if (path.isInverseFillType()) {
             sk_blit_above(blitter, ir, *clipPtr);
         }
-        sk_fill_path(path, clipper.getClipRect(), blitter, ir.fTop, ir.fBottom,
+        sk_fill_path(path, clipper.getClipRect(), blitter, NULL, ir.fTop, ir.fBottom,
                      0, *clipPtr);
         if (path.isInverseFillType()) {
             sk_blit_below(blitter, ir, *clipPtr);
         }
     } else {
         // what does it mean to not have a blitter if path.isInverseFillType???
     }
 }
 
 void SkScan::FillPath(const SkPath& path, const SkIRect& ir,
@@ skipping 53 matching lines @@
 
     // now edge is the head of the sorted linklist
     int stop_y = ir.fBottom;
     if (clipRect && stop_y > clipRect->fBottom) {
         stop_y = clipRect->fBottom;
     }
     int start_y = ir.fTop;
     if (clipRect && start_y < clipRect->fTop) {
         start_y = clipRect->fTop;
     }
-    walk_convex_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr);
-//    walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, nullptr);
+    walk_convex_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, nullptr, start_y, stop_y, nullptr);
+//    walk_edges(&headEdge, SkPath::kEvenOdd_FillType, blitter, start_y, stop_y, NULL);
 }
 
 void SkScan::FillTriangle(const SkPoint pts[], const SkRasterClip& clip,
                           SkBlitter* blitter) {
     if (clip.isEmpty()) {
         return;
     }
 
     SkRect  r;
     SkIRect ir;
@@ skipping 12 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);
     }
 }
+
+void SkScan::PathToTriangles(const SkPath& path, const SkIRect& clipBounds,
+                             bool antiAlias, SkTDArray<SkPoint>* points) {
+//    dumping = true;
+//    printf("*** SkScan::PathToTriangles start\n");
+    points->setReserve(path.countPoints());
+    SkPath localPath = path;
+    SkIRect localClipBounds = clipBounds;
+    if (antiAlias) {
+        // Stroke 1-pix wide around path.
+        SkStroke stroker;
+        stroker.setJoin(SkPaint::kMiter_Join);
+        stroker.setWidth(5);
+        SkPath strokedPath;
+        // We want even open paths to become closed, so we can fill them.
+        stroker.setAutoClose(true);
+        // Don't reverse the inner path direction, since want the interior to be filled.
+        stroker.setReverseInner(false);
+        stroker.strokePath(localPath, &strokedPath);
+        localPath = strokedPath;
+    }
+    SkRect pathBounds = localPath.getBounds();
+    SkRegion clipRgn(localClipBounds);
+    if (localPath.isInverseFillType()) {
+        localPath.addRect(SkRect::Make(localClipBounds), SkPath::kCCW_Direction);
+        sk_fill_path(localPath, &localClipBounds, NULL, points,
+                     localClipBounds.top(), localClipBounds.bottom(), 0,
+                     clipRgn);
+    } else {
+        sk_fill_path(localPath, &localClipBounds, NULL, points,
+                     pathBounds.top() - 1, pathBounds.bottom() + 1, 0,
+                     clipRgn);
+    }
+//    printf("*** SkScan::PathToTriangles end\n");
+//    dumping = false;
+}