batch merge new edges
Find where newly introduced edges go in the edge list once,
then stitch all of them into the edge list.
R=reed@google.com
BUG=573166
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1647223002
Committed: https://skia.googlesource.com/skia/+/ae658e15477df86d1a864feb48d0274af2784f40
Review URL: https://codereview.chromium.org/1647223002
diff --git a/src/core/SkScan_Path.cpp b/src/core/SkScan_Path.cpp
index 804148d..077d9a0 100644
--- a/src/core/SkScan_Path.cpp
+++ b/src/core/SkScan_Path.cpp
@@ -61,7 +61,21 @@
}
}
+#ifndef SK_SUPPORT_LEGACY_INSERT_NEW_EDGES
+// Start from the right side, searching backwards for the point to begin the new edge list
+// insertion, marching forwards from here. The implementation could have started from the left
+// of the prior insertion, and search to the right, or with some additional caching, binary
+// search the starting point. More work could be done to determine optimal new edge insertion.
+static SkEdge* backward_insert_start(SkEdge* prev, SkFixed x) {
+ while (prev->fX > x) {
+ prev = prev->fPrev;
+ }
+ return prev;
+}
+#endif
+
static void insert_new_edges(SkEdge* newEdge, int curr_y) {
+#ifdef SK_SUPPORT_LEGACY_INSERT_NEW_EDGES
SkASSERT(newEdge->fFirstY >= curr_y);
while (newEdge->fFirstY == curr_y) {
@@ -69,6 +83,36 @@
backward_insert_edge_based_on_x(newEdge SkPARAM(curr_y));
newEdge = next;
}
+#else
+ if (newEdge->fFirstY != curr_y) {
+ return;
+ }
+ SkEdge* prev = newEdge->fPrev;
+ if (prev->fX <= newEdge->fX) {
+ return;
+ }
+ // find first x pos to insert
+ SkEdge* start = backward_insert_start(prev, newEdge->fX);
+ // insert the lot, fixing up the links as we go
+ do {
+ SkEdge* next = newEdge->fNext;
+ do {
+ if (start->fNext == newEdge) {
+ goto nextEdge;
+ }
+ SkEdge* after = start->fNext;
+ if (after->fX >= newEdge->fX) {
+ break;
+ }
+ start = after;
+ } while (true);
+ remove_edge(newEdge);
+ insert_edge_after(newEdge, start);
+nextEdge:
+ start = newEdge;
+ newEdge = next;
+ } while (newEdge->fFirstY == curr_y);
+#endif
}
#ifdef SK_DEBUG