Tessellating GPU path renderer.

tests/ConcavePathTests.cpp

Index: tests/ConcavePathTests.cpp
diff --git a/tests/ConcavePathTests.cpp b/tests/ConcavePathTests.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..671fadf92f07f195038d4bd94bcc425f1d197811
--- /dev/null
+++ b/tests/ConcavePathTests.cpp
@@ -0,0 +1,278 @@
+/*
+ * Copyright 2015 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkBitmap.h"
+#include "SkBitmapDevice.h"
+#include "SkCanvas.h"
+#include "SkSurface.h"
+#include "Test.h"
+
+#if SK_SUPPORT_GPU
+#include "GrContextFactory.h"
+#include "SkGpuDevice.h"
+#endif
+
+/*
+ * These tests pass by not crashing, hanging or asserting in Debug.
+ */
+
+// Tests active edges made inactive by splitting.
+// Also tests active edge list forced into an invalid ordering by
+// splitting (mopped up in cleanup_active_edges()).
+static void draw_path_0(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo( 229.127044677734375,    67.34100341796875);

[reed1, 2015/02/19 20:52:23]

These are fantastically precise values. Can you in any way simplify them and
still make them useful.

Also, they are doubles as written, and will create warnings (at least on
Windows).

[Stephen White, 2015/02/20 21:58:41]

Sadly, no. Most were produced by fuzzing and animation, and trigger  floating
point issues which only occur with these exact values, down  to the ULP. (If
it's any consolation, many of the paths were originally hundreds of segments
long, and I whittled the paths down to the minimal reduction length.)
Fixed.

+    path.lineTo(187.8097381591796875, -6.7729740142822265625);
+    path.lineTo( 171.411407470703125, 50.94266510009765625);
+    path.lineTo(245.5253753662109375, 9.6253643035888671875);
+    path.moveTo(208.4683990478515625, 30.284009933471679688);
+    path.lineTo( 171.411407470703125, 50.94266510009765625);
+    path.lineTo(187.8097381591796875, -6.7729740142822265625);
+    canvas->drawPath(path, paint);
+}
+
+// Intersections which fall exactly on the current vertex, and require
+// a restart of the intersection checking.
+static void draw_path_1(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo( 314.483551025390625,  486.246002197265625);
+    path.lineTo(  385.41949462890625,    532.8087158203125);
+    path.lineTo( 373.232879638671875,   474.05938720703125);
+    path.lineTo(    326.670166015625,     544.995361328125);
+    path.moveTo( 349.951507568359375,         509.52734375);
+    path.lineTo( 373.232879638671875,   474.05938720703125);
+    path.lineTo(  385.41949462890625,    532.8087158203125);
+    canvas->drawPath(path, paint);
+}
+
+// Tests active edges which are removed by splitting.
+static void draw_path_2(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo( 343.107391357421875,   613.62176513671875);
+    path.lineTo( 426.632415771484375,    628.5740966796875);
+    path.lineTo(   392.3460693359375,      579.33544921875);
+    path.lineTo(  377.39373779296875,   662.86041259765625);
+    path.moveTo(    384.869873046875,     621.097900390625);
+    path.lineTo(   392.3460693359375,      579.33544921875);
+    path.lineTo( 426.632415771484375,    628.5740966796875);
+    canvas->drawPath(path, paint);
+}
+
+// Collinear edges merged in set_top().
+// Also, an intersection between left and right enclosing edges which
+// falls above the current vertex.
+static void draw_path_3(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(     545.95751953125,   791.69854736328125);
+    path.lineTo(  612.05816650390625,        738.494140625);
+    path.lineTo(   552.4056396484375,    732.0460205078125);
+    path.lineTo(  605.61004638671875,   798.14666748046875);
+    path.moveTo(  579.00787353515625,    765.0963134765625);
+    path.lineTo(   552.4056396484375,    732.0460205078125);
+    path.lineTo(  612.05816650390625,        738.494140625);
+    canvas->drawPath(path, paint);
+}
+
+// Tests active edges which are made inactive by set_top().
+static void draw_path_4(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(   819.2725830078125,   751.77447509765625);
+    path.lineTo(  820.70904541015625,     666.933837890625);
+    path.lineTo(  777.57049560546875,   708.63592529296875);
+    path.lineTo(      862.4111328125,    710.0723876953125);
+    path.moveTo(  819.99078369140625,    709.3541259765625);
+    path.lineTo(  777.57049560546875,   708.63592529296875);
+    path.lineTo(  820.70904541015625,     666.933837890625);
+    canvas->drawPath(path, paint);
+}
+
+static void draw_path_5(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(  823.33209228515625,        749.052734375);
+    path.lineTo(    823.494873046875,   664.20013427734375);
+    path.lineTo(   780.9871826171875,    706.5450439453125);
+    path.lineTo(   865.8397216796875,   706.70782470703125);
+    path.moveTo(   823.4134521484375,    706.6263427734375);
+    path.lineTo(   780.9871826171875,    706.5450439453125);
+    path.lineTo(    823.494873046875,   664.20013427734375);
+    canvas->drawPath(path, paint);
+}
+
+static void draw_path_6(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(    954.862548828125,       562.8349609375);
+    path.lineTo(  899.32818603515625,     498.679443359375);
+    path.lineTo(       895.017578125,   558.52435302734375);
+    path.lineTo(  959.17315673828125,  502.990081787109375);
+    path.moveTo(   927.0953369140625,    530.7572021484375);
+    path.lineTo(       895.017578125,   558.52435302734375);
+    path.lineTo(  899.32818603515625,     498.679443359375);
+    canvas->drawPath(path, paint);
+}
+
+static void draw_path_7(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(   958.5330810546875,   547.35516357421875);
+    path.lineTo(  899.93109130859375,     485.989013671875);
+    path.lineTo(  898.54901123046875,   545.97308349609375);
+    path.lineTo(   959.9151611328125,         487.37109375);
+    path.moveTo(   929.2320556640625,   516.67205810546875);
+    path.lineTo(  898.54901123046875,   545.97308349609375);
+    path.lineTo(  899.93109130859375,     485.989013671875);
+    canvas->drawPath(path, paint);
+}
+
+static void draw_path_8(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(   389.8609619140625,  369.326873779296875);

[reed1, 2015/02/19 20:52:23]

micro nit: this white-space formatting in fact makes it harder to compare the
actual numeric values, since the decimal-points don't align.

how about

lineTo(  470.12312321,   23.012321 );
lineTo(   70.12312321,  123.012321 );

[Stephen White, 2015/02/20 21:58:41]

Fixed (aligned on the decimal point).

+    path.lineTo(   470.6290283203125,   395.33697509765625);
+    path.lineTo( 443.250030517578125,    341.9478759765625);
+    path.lineTo( 417.239959716796875,    422.7159423828125);
+    path.moveTo( 430.244964599609375,    382.3319091796875);
+    path.lineTo( 443.250030517578125,    341.9478759765625);
+    path.lineTo(   470.6290283203125,   395.33697509765625);
+    canvas->drawPath(path, paint);
+}
+
+static void draw_path_9(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(20, 20);
+    path.lineTo(50, 80);
+    path.lineTo(20, 80);
+    path.moveTo(80, 50);
+    path.lineTo(50, 50);
+    path.lineTo(20, 50);
+    canvas->drawPath(path, paint);
+}
+
+static void draw_path_10(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(257.19439697265625, 320.876617431640625);
+    path.lineTo(190.113037109375,   320.58978271484375);
+    path.lineTo(203.64404296875,    293.8145751953125);
+    path.moveTo(203.357177734375,   360.896026611328125);
+    path.lineTo(216.88824462890625, 334.120819091796875);
+    path.lineTo(230.41925048828125, 307.345611572265625);
+    canvas->drawPath(path, paint);
+}
+
+// A degenerate segments case, where both upper and lower segments of
+// a split edge must remain active.
+static void draw_path_11(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(231.9331207275390625,    306.2012939453125);
+    path.lineTo(191.4859161376953125,   306.04547119140625);
+    path.lineTo(231.0659332275390625,    300.2642822265625);
+    path.moveTo( 189.946807861328125,        302.072265625);
+    path.lineTo(  179.79705810546875,  294.859771728515625);
+    path.lineTo(191.0016021728515625,  296.165679931640625);
+    path.moveTo(150.8942108154296875,     304.900146484375);
+    path.lineTo( 179.708892822265625,  297.849029541015625);
+    path.lineTo(190.4742279052734375,   299.11895751953125);
+    canvas->drawPath(path, paint);
+}
+
+// Handle the case where edge.dist(edge.fTop) != 0.0.
+static void draw_path_12(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(                   0,                  400);
+    path.lineTo(                 138,                  202);
+    path.lineTo(                   0,                  202);
+    path.moveTo(12.62693023681640625,   250.57464599609375);
+    path.lineTo( 8.13896942138671875,     254.556884765625);
+    path.lineTo(-18.15641021728515625,   220.40203857421875);
+    path.lineTo(-15.986493110656738281, 219.6513519287109375);
+    path.moveTo(36.931194305419921875,  282.485504150390625);
+    path.lineTo(15.617521286010742188,    261.2901611328125);
+    path.lineTo( 10.3829498291015625,  252.565765380859375);
+    path.lineTo(-16.165292739868164062,  222.646026611328125);
+    canvas->drawPath(path, paint);
+}
+
+// A degenerate segments case which exercises inactive edges being
+// made active by splitting.
+static void draw_path_13(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo(  690.62127685546875,   509.25555419921875);
+    path.lineTo(    699.336181640625,   511.71405029296875);
+    path.lineTo(    708.362548828125,    512.4349365234375);
+    path.lineTo(   729.9940185546875,    516.3114013671875);
+    path.lineTo(       738.708984375,   518.76995849609375);
+    path.lineTo(   678.3463134765625,    510.0819091796875);
+    path.lineTo(  681.21795654296875,   504.81378173828125);
+    path.moveTo(  758.52764892578125,   521.55963134765625);
+    path.lineTo(   719.1549072265625,   514.50372314453125);
+    path.lineTo(  689.59063720703125,    512.0628662109375);
+    path.lineTo(  679.78216552734375,  507.447845458984375);
+    canvas->drawPath(path, paint);
+}
+
+// Tests vertices which become "orphaned" (ie., no connected edges)
+// after simplification.
+static void draw_path_14(SkCanvas* canvas, const SkPaint& paint) {
+    SkPath path;
+    path.moveTo( 217.326019287109375, 166.4752960205078125);
+    path.lineTo( 226.279266357421875,  170.929473876953125);
+    path.lineTo(   234.3973388671875, 177.0623626708984375);
+    path.lineTo(   262.0921630859375,  188.746124267578125);
+    path.moveTo(  196.23638916015625, 174.0722198486328125);
+    path.lineTo(  416.15277099609375,  180.138214111328125);
+    path.lineTo( 192.651947021484375,    304.0228271484375);
+    canvas->drawPath(path, paint);
+}
+
+static void test_concave_paths(SkSurface* surface, skiatest::Reporter* reporter) {
+    SkCanvas* canvas = surface->getCanvas();
+    canvas->clear(0);
+
+    SkPaint paint;
+    paint.setAntiAlias(false);
+    draw_path_0(canvas, paint);
+    draw_path_1(canvas, paint);
+    draw_path_2(canvas, paint);
+    draw_path_3(canvas, paint);
+    draw_path_4(canvas, paint);
+    draw_path_5(canvas, paint);
+    draw_path_6(canvas, paint);
+    draw_path_7(canvas, paint);
+    draw_path_8(canvas, paint);
+    draw_path_9(canvas, paint);
+    draw_path_10(canvas, paint);
+    draw_path_11(canvas, paint);
+    draw_path_12(canvas, paint);
+    draw_path_13(canvas, paint);
+    draw_path_14(canvas, paint);
+}
+
+DEF_TEST(ConcavePathTests, reporter) {
+    SkBitmap temp;
+    SkImageInfo info = SkImageInfo::MakeN32Premul(800, 800);
+    temp.allocN32Pixels(800, 800);
+    SkBitmapDevice device(temp);
+    SkAutoTUnref<SkSurface> surface(
+        SkSurface::NewRasterDirect(info, temp.getPixels(), temp.rowBytes()));
+    test_concave_paths(surface.get(), reporter);
+}
+
+#if SK_SUPPORT_GPU
+const SkSurfaceProps gProps = SkSurfaceProps(SkSurfaceProps::kLegacyFontHost_InitType);
+
+DEF_GPUTEST(ConcavePathTestsGPU, reporter, factory) {
+    GrContext* context = factory->get(static_cast<GrContextFactory::GLContextType>(0));
+    GrSurfaceDesc desc;
+    desc.fFlags = kRenderTarget_GrSurfaceFlag;
+    desc.fWidth = 800;
+    desc.fHeight = 800;
+    desc.fConfig = kSkia8888_GrPixelConfig;
+    desc.fOrigin = kTopLeft_GrSurfaceOrigin;
+    SkAutoTUnref<GrTexture> texture(
+        context->refScratchTexture(desc, GrContext::kExact_ScratchTexMatch)
+    );
+    SkAutoTUnref<SkSurface> surface(SkSurface::NewRenderTargetDirect(texture->asRenderTarget()));
+    test_concave_paths(surface.get(), reporter);
+}
+#endif