Tessellator: stop copying vertices into Polys and Monotones.

The vertices which are produced by stage 5 of the
tesselator are copied into the Polys and MonotonePolys it
produces. This is necessary because each vertex may have an
arbitrary valence, since it may participate in an arbitrary
number of Polys, so we can't use the vertex's prev/next
pointers to represent all the Monotones of which this
vertex may be a member.

However, each Edge can only be a member of two Polys (one
on each side of the edge). So by adding two prev/next
pointer pairs to each Edge, we can represent each Monotone
as a list of edges instead. Then we no longer need to copy
the vertices.

One wrinkle is that the ear-clipping stage (6) of the
tessellator does require prev/next pointers, in order to
remove vertices as their ears are clipped. So we convert
the edge list into a vertex list during Monotone::emit(),
using the prev/next pointers temporarily for that monotone.

This change improves performance by 7-20% on a non-caching
version of the tessellator, and reduces memory use.

Other notes:

1) Polys are initially constructed empty (no edges), but
with the top vertex, which is needed for splitting
Polys. Edges are added to Polys only after their bottom
vertex is seen.

2) MonotonePolys are always constructed with one edge, so
we always know their handedness (left/right).
MonotonePoly::addEdge() no longer detects when a monotone
is "done" (edge of opposite handedness); this is handled
by Poly::addEdge(), so MonotonePoly::addEdge() has no
return value.

GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2029243002

Review-Url: https://codereview.chromium.org/2029243002

1 files changed, 21 insertions, 0 deletions

diff --git a/gm/concavepaths.cpp b/gm/concavepaths.cpp
index 4008a6457e..ad87d255ca 100644
--- a/gm/concavepaths.cpp
+++ b/gm/concavepaths.cpp
@@ -166,6 +166,26 @@ void test_overlapping(SkCanvas* canvas, const SkPaint& paint) {
     canvas->restore();
 }
 
+// Two "island" triangles inside a containing rect.
+// This exercises the partnering code in the tessellator.
+void test_partners(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    canvas->save();
+    canvas->translate(300, 200);
+    path.moveTo(20, 80);
+    path.lineTo(80, 80);
+    path.lineTo(80, 20);
+    path.lineTo(20, 20);
+    path.moveTo(30, 30);
+    path.lineTo(45, 50);
+    path.lineTo(30, 70);
+    path.moveTo(70, 30);
+    path.lineTo(70, 70);
+    path.lineTo(55, 50);
+    canvas->drawPath(path, paint);
+    canvas->restore();
+}
+
 // Monotone test 1 (point in the middle)
 void test_monotone_1(SkCanvas* canvas, const SkPaint& paint) {
     SkPath path;
@@ -370,6 +390,7 @@ protected:
         test_stairstep(canvas, paint);
         test_stairstep2(canvas, paint);
         test_overlapping(canvas, paint);
+        test_partners(canvas, paint);
         test_monotone_1(canvas, paint);
         test_monotone_2(canvas, paint);
         test_monotone_3(canvas, paint);