offset angle check edge in common

When curves cross, their intersection points may be nearby, but not exactly the same.
Sort the angles formed by the crossing curves when all angles don't have the same
origin.

This sets up the framework to solve test case that currently fail (e.g., joel6) but
does not fix all related test cases (e.g., joel9).

All older existing test cases, including extended tests, pass.

Rework the test framework to better report when tests expected to produce failing
results now pass.

Add new point and vector operations to support offset angles.

TBR=reed@google.com
BUG=skia:6041

Change-Id: I67c651ded0a25e99ad93d55d6a35109b3ee3698e
Reviewed-on: https://skia-review.googlesource.com/6624
Commit-Queue: Cary Clark <caryclark@google.com>
Reviewed-by: Cary Clark <caryclark@google.com>

1 files changed, 269 insertions, 0 deletions

diff --git a/tests/PathOpsSimplifyFailTest.cpp b/tests/PathOpsSimplifyFailTest.cpp
index b6f210e8ea..44bb50ce94 100644
--- a/tests/PathOpsSimplifyFailTest.cpp
+++ b/tests/PathOpsSimplifyFailTest.cpp
@@ -215,9 +215,278 @@ path.close();
     testSimplifyFuzz(reporter, path, filename);
 }
 
+static void fuzz_twister(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path;
+    path.setFillType((SkPath::FillType) 0);
+path.moveTo(0, 600);
+path.lineTo(3.35544e+07f, 600);
+path.lineTo(3.35544e+07f, 0);
+path.lineTo(0, 0);
+path.lineTo(0, 600);
+path.close();
+path.moveTo(63, 600);
+path.lineTo(3.35545e+07f, 600);
+path.lineTo(3.35545e+07f, 0);
+path.lineTo(63, 0);
+path.lineTo(63, 600);
+path.close();
+path.moveTo(93, 600);
+path.lineTo(3.35545e+07f, 600);
+path.lineTo(3.35545e+07f, 0);
+path.lineTo(93, 0);
+path.lineTo(93, 600);
+path.close();
+path.moveTo(123, 600);
+path.lineTo(3.35546e+07f, 600);
+path.lineTo(3.35546e+07f, 0);
+path.lineTo(123, 0);
+path.lineTo(123, 600);
+path.close();
+    testSimplifyFuzz(reporter, path, filename);
+}
+
+static void fuzz_twister2(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path;
+
+path.moveTo(SkBits2Float(0x00000000), SkBits2Float(0x44160000));  // 0, 600
+path.lineTo(SkBits2Float(0x4bfffffe), SkBits2Float(0x44160000));  // 3.35544e+07f, 600
+path.lineTo(SkBits2Float(0x4bfffffe), SkBits2Float(0x00000000));  // 3.35544e+07f, 0
+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0
+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x44160000));  // 0, 600
+path.close();
+
+path.moveTo(SkBits2Float(0x427c0000), SkBits2Float(0x00000000));  // 63, 0
+path.lineTo(SkBits2Float(0x4c00000f), SkBits2Float(0x00000000));  // 3.35545e+07f, 0
+path.lineTo(SkBits2Float(0x4c00000f), SkBits2Float(0x00000000));  // 3.35545e+07f, 0
+path.lineTo(SkBits2Float(0x427c0000), SkBits2Float(0x00000000));  // 63, 0
+path.close();
+
+path.moveTo(SkBits2Float(0x42ba0000), SkBits2Float(0x00000000));  // 93, 0
+path.lineTo(SkBits2Float(0x4c000016), SkBits2Float(0x00000000));  // 3.35545e+07f, 0
+path.lineTo(SkBits2Float(0x4c000016), SkBits2Float(0x00000000));  // 3.35545e+07f, 0
+path.lineTo(SkBits2Float(0x42ba0000), SkBits2Float(0x00000000));  // 93, 0
+path.close();
+
+path.moveTo(SkBits2Float(0x42f60000), SkBits2Float(0x00000000));  // 123, 0
+path.lineTo(SkBits2Float(0x4c00001e), SkBits2Float(0x00000000));  // 3.35546e+07f, 0
+path.lineTo(SkBits2Float(0x4c00001e), SkBits2Float(0x00000000));  // 3.35546e+07f, 0
+path.lineTo(SkBits2Float(0x42f60000), SkBits2Float(0x00000000));  // 123, 0
+path.close();
+
+    testSimplifyFuzz(reporter, path, filename);
+}
+
+static void fuzz994s_11(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path;
+    path.setFillType((SkPath::FillType) 0);
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x42b40000));  // 110, 90
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x41f00000));  // 110, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x46ff4c00), SkBits2Float(0x41f00000));  // 32678, 30
+path.lineTo(SkBits2Float(0x46ff4c00), SkBits2Float(0x41f00000));  // 32678, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x4c000006));  // 10, 3.35545e+07f
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x4c000006));  // 110, 3.35545e+07f
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x41f00000));  // 110, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x4c000006));  // 10, 3.35545e+07f
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x439d8000));  // 10, 315
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x439d8000));  // 110, 315
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x437f0000));  // 110, 255
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x437f0000));  // 10, 255
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x439d8000));  // 10, 315
+path.close();
+path.moveTo(SkBits2Float(0x00000000), SkBits2Float(0x42700000));  // 0, 60
+path.lineTo(SkBits2Float(0x42c80000), SkBits2Float(0x42700000));  // 100, 60
+path.lineTo(SkBits2Float(0x42c80000), SkBits2Float(0x00000000));  // 100, 0
+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000));  // 0, 0
+path.lineTo(SkBits2Float(0x00000000), SkBits2Float(0x42700000));  // 0, 60
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x42b40000));  // 110, 90
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x41f00000));  // 110, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x4c000006));  // 10, 3.35545e+07f
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x4c000006));  // 110, 3.35545e+07f
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x41f00000));  // 110, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x4c000006));  // 10, 3.35545e+07f
+path.close();
+path.moveTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x42b40000));  // 110, 90
+path.lineTo(SkBits2Float(0x42dc0000), SkBits2Float(0x41f00000));  // 110, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x41f00000));  // 10, 30
+path.lineTo(SkBits2Float(0x41200000), SkBits2Float(0x42b40000));  // 10, 90
+path.close();
+
+    testSimplifyFuzz(reporter, path, filename);
+}
+
+static void fuzz994s_3414(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path;
+    path.setFillType((SkPath::FillType) 0);
+path.moveTo(SkBits2Float(0x42c80000), SkBits2Float(0x42480000));  // 100, 50
+path.conicTo(SkBits2Float(0x42c80000), SkBits2Float(0x00000000), SkBits2Float(0x42480000), SkBits2Float(0x00000000), SkBits2Float(0x3f3504f3));  // 100, 0, 50, 0, 0.707107f
+path.conicTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000), SkBits2Float(0x00000000), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 0, 0, 0, 50, 0.707107f
+path.conicTo(SkBits2Float(0x00000000), SkBits2Float(0x42c80000), SkBits2Float(0x42480000), SkBits2Float(0x42c80000), SkBits2Float(0x3f3504f3));  // 0, 100, 50, 100, 0.707107f
+path.conicTo(SkBits2Float(0x42c80000), SkBits2Float(0x42c80000), SkBits2Float(0x42c80000), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 100, 100, 100, 50, 0.707107f
+path.close();
+path.moveTo(SkBits2Float(0x42c84964), SkBits2Float(0x42480000));  // 100.143f, 50
+path.conicTo(SkBits2Float(0x42c84964), SkBits2Float(0x00000000), SkBits2Float(0x424892c8), SkBits2Float(0x00000000), SkBits2Float(0x3f3504f3));  // 100.143f, 0, 50.1433f, 0, 0.707107f
+path.conicTo(SkBits2Float(0x3e12c788), SkBits2Float(0x00000000), SkBits2Float(0x3e12c788), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 0.143339f, 0, 0.143339f, 50, 0.707107f
+path.conicTo(SkBits2Float(0x3e12c788), SkBits2Float(0x42c80000), SkBits2Float(0x424892c8), SkBits2Float(0x42c80000), SkBits2Float(0x3f3504f3));  // 0.143339f, 100, 50.1433f, 100, 0.707107f
+path.conicTo(SkBits2Float(0x42c84964), SkBits2Float(0x42c80000), SkBits2Float(0x42c84964), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 100.143f, 100, 100.143f, 50, 0.707107f
+path.close();
+path.moveTo(SkBits2Float(0x42c80000), SkBits2Float(0x42480000));  // 100, 50
+path.conicTo(SkBits2Float(0x42c80000), SkBits2Float(0x00000000), SkBits2Float(0x42480000), SkBits2Float(0x00000000), SkBits2Float(0x3f3504f3));  // 100, 0, 50, 0, 0.707107f
+path.conicTo(SkBits2Float(0x00000000), SkBits2Float(0x00000000), SkBits2Float(0x00000000), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 0, 0, 0, 50, 0.707107f
+path.conicTo(SkBits2Float(0x00000000), SkBits2Float(0x42c80000), SkBits2Float(0x42480000), SkBits2Float(0x42c80000), SkBits2Float(0x3f3504f3));  // 0, 100, 50, 100, 0.707107f
+path.conicTo(SkBits2Float(0x42c80000), SkBits2Float(0x42c80000), SkBits2Float(0x42c80000), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 100, 100, 100, 50, 0.707107f
+path.close();
+path.moveTo(SkBits2Float(0x4c00006b), SkBits2Float(0x424c0000));  // 3.35549e+07f, 51
+path.conicTo(SkBits2Float(0x4c00006b), SkBits2Float(0xcbffffe5), SkBits2Float(0x43d6e720), SkBits2Float(0xcbffffe5), SkBits2Float(0x3f3504f3));  // 3.35549e+07f, -3.35544e+07f, 429.806f, -3.35544e+07f, 0.707107f
+path.conicTo(SkBits2Float(0xcbffff28), SkBits2Float(0xcbffffe5), SkBits2Float(0xcbffff28), SkBits2Float(0x424c0000), SkBits2Float(0x3f3504f3));  // -3.3554e+07f, -3.35544e+07f, -3.3554e+07f, 51, 0.707107f
+path.conicTo(SkBits2Float(0xcbffff28), SkBits2Float(0x4c00000c), SkBits2Float(0x43d6e720), SkBits2Float(0x4c00000c), SkBits2Float(0x3f3504f3));  // -3.3554e+07f, 3.35545e+07f, 429.806f, 3.35545e+07f, 0.707107f
+path.conicTo(SkBits2Float(0x4c00006b), SkBits2Float(0x4c00000c), SkBits2Float(0x4c00006b), SkBits2Float(0x424c0000), SkBits2Float(0x3f3504f3));  // 3.35549e+07f, 3.35545e+07f, 3.35549e+07f, 51, 0.707107f
+path.close();
+path.moveTo(SkBits2Float(0x43ef6720), SkBits2Float(0x42480000));  // 478.806f, 50
+path.conicTo(SkBits2Float(0x43ef6720), SkBits2Float(0x00000000), SkBits2Float(0x43d66720), SkBits2Float(0x00000000), SkBits2Float(0x3f3504f3));  // 478.806f, 0, 428.806f, 0, 0.707107f
+path.conicTo(SkBits2Float(0x43bd6720), SkBits2Float(0x00000000), SkBits2Float(0x43bd6720), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 378.806f, 0, 378.806f, 50, 0.707107f
+path.conicTo(SkBits2Float(0x43bd6720), SkBits2Float(0x42c80000), SkBits2Float(0x43d66720), SkBits2Float(0x42c80000), SkBits2Float(0x3f3504f3));  // 378.806f, 100, 428.806f, 100, 0.707107f
+path.conicTo(SkBits2Float(0x43ef6720), SkBits2Float(0x42c80000), SkBits2Float(0x43ef6720), SkBits2Float(0x42480000), SkBits2Float(0x3f3504f3));  // 478.806f, 100, 478.806f, 50, 0.707107f
+path.close();
+
+    testSimplify(reporter, path, filename);
+}
+
+static void fuzz763_4713_b(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path;
+    path.setFillType((SkPath::FillType) 0);
+path.moveTo(SkBits2Float(0x42240000), SkBits2Float(0x42040000));
+path.quadTo(SkBits2Float(0x42240000), SkBits2Float(0x4211413d), SkBits2Float(0x421aa09e), SkBits2Float(0x421aa09e));
+path.quadTo(SkBits2Float(0x4211413d), SkBits2Float(0x42240000), SkBits2Float(0x42040000), SkBits2Float(0x42240000));
+path.quadTo(SkBits2Float(0x41ed7d86), SkBits2Float(0x42240000), SkBits2Float(0x41dabec3), SkBits2Float(0x421aa09e));
+path.quadTo(SkBits2Float(0x41c80000), SkBits2Float(0x4211413d), SkBits2Float(0x41c80000), SkBits2Float(0x42040000));
+path.quadTo(SkBits2Float(0x41c80000), SkBits2Float(0x41ed7d86), SkBits2Float(0x41dabec3), SkBits2Float(0x41dabec3));
+path.quadTo(SkBits2Float(0x41ed7d86), SkBits2Float(0x41c80000), SkBits2Float(0x42040000), SkBits2Float(0x41c80000));
+path.quadTo(SkBits2Float(0x4211413d), SkBits2Float(0x41c80000), SkBits2Float(0x421aa09e), SkBits2Float(0x41dabec3));
+path.quadTo(SkBits2Float(0x42240000), SkBits2Float(0x41ed7d86), SkBits2Float(0x42240000), SkBits2Float(0x42040000));
+path.close();
+
+path.moveTo(SkBits2Float(0x4204f72e), SkBits2Float(0x41c56cd2));
+path.quadTo(SkBits2Float(0x42123842), SkBits2Float(0x41c52adf), SkBits2Float(0x421baed7), SkBits2Float(0x41d7bac6));
+path.quadTo(SkBits2Float(0x4225256d), SkBits2Float(0x41ea4aad), SkBits2Float(0x42254667), SkBits2Float(0x4202666b));
+path.quadTo(SkBits2Float(0x42256760), SkBits2Float(0x420fa77f), SkBits2Float(0x421c1f6c), SkBits2Float(0x42191e14));
+path.quadTo(SkBits2Float(0x421bff97), SkBits2Float(0x42193e89), SkBits2Float(0x421bdf6b), SkBits2Float(0x42195eb8));
+path.quadTo(SkBits2Float(0x421bbff6), SkBits2Float(0x42197f32), SkBits2Float(0x421ba03b), SkBits2Float(0x42199f57));
+path.quadTo(SkBits2Float(0x421b605e), SkBits2Float(0x4219e00a), SkBits2Float(0x421b1fa8), SkBits2Float(0x421a1f22));
+path.quadTo(SkBits2Float(0x421ae0f1), SkBits2Float(0x421a604b), SkBits2Float(0x421aa09e), SkBits2Float(0x421aa09e));
+path.quadTo(SkBits2Float(0x4211413d), SkBits2Float(0x42240000), SkBits2Float(0x42040000), SkBits2Float(0x42240000));
+path.quadTo(SkBits2Float(0x41ed7d86), SkBits2Float(0x42240000), SkBits2Float(0x41dabec3), SkBits2Float(0x421aa09e));
+path.quadTo(SkBits2Float(0x41c80000), SkBits2Float(0x4211413d), SkBits2Float(0x41c80000), SkBits2Float(0x42040000));
+path.quadTo(SkBits2Float(0x41c80000), SkBits2Float(0x41ed7d86), SkBits2Float(0x41dabec3), SkBits2Float(0x41dabec3));
+path.quadTo(SkBits2Float(0x41db19b1), SkBits2Float(0x41da63d5), SkBits2Float(0x41db755b), SkBits2Float(0x41da0a9b));
+path.quadTo(SkBits2Float(0x41dbce01), SkBits2Float(0x41d9ae59), SkBits2Float(0x41dc285e), SkBits2Float(0x41d952ce));
+path.quadTo(SkBits2Float(0x41dc55b6), SkBits2Float(0x41d924df), SkBits2Float(0x41dc82cd), SkBits2Float(0x41d8f7cd));
+path.quadTo(SkBits2Float(0x41dcaf1e), SkBits2Float(0x41d8ca01), SkBits2Float(0x41dcdc4c), SkBits2Float(0x41d89bf0));
+path.quadTo(SkBits2Float(0x41ef6c33), SkBits2Float(0x41c5aec5), SkBits2Float(0x4204f72e), SkBits2Float(0x41c56cd2));
+path.close();
+testSimplify(reporter, path, filename);
+}
+
+static void fuzz864a(skiatest::Reporter* reporter,const char* filename) {
+    SkPath path;
+    path.moveTo(10, 90);
+    path.lineTo(10, 90);
+    path.lineTo(10, 30);
+    path.lineTo(10, 30);
+    path.lineTo(10, 90);
+    path.close();
+    path.moveTo(10, 90);
+    path.lineTo(10, 90);
+    path.lineTo(10, 30);
+    path.lineTo(10, 30);
+    path.lineTo(10, 90);
+    path.close();
+    path.moveTo(10, 90);
+    path.lineTo(110, 90);
+    path.lineTo(110, 30);
+    path.lineTo(10, 30);
+    path.lineTo(10, 90);
+    path.close();
+    path.moveTo(10, 30);
+    path.lineTo(32678, 30);
+    path.lineTo(32678, 30);
+    path.lineTo(10, 30);
+    path.close();
+    path.moveTo(10, 3.35545e+07f);
+    path.lineTo(110, 3.35545e+07f);
+    path.lineTo(110, 30);
+    path.lineTo(10, 30);
+    path.lineTo(10, 3.35545e+07f);
+    path.close();
+    path.moveTo(10, 315);
+    path.lineTo(110, 315);
+    path.lineTo(110, 255);
+    path.lineTo(10, 255);
+    path.lineTo(10, 315);
+    path.close();
+    path.moveTo(0, 60);
+    path.lineTo(100, 60);
+    path.lineTo(100, 0);
+    path.lineTo(0, 0);
+    path.lineTo(0, 60);
+    path.close();
+    path.moveTo(10, 90);
+    path.lineTo(110, 90);
+    path.lineTo(110, 30);
+    path.lineTo(10, 30);
+    path.lineTo(10, 90);
+    path.close();
+    path.moveTo(10, 3.35545e+07f);
+    path.lineTo(110, 3.35545e+07f);
+    path.lineTo(110, 30);
+    path.lineTo(10, 30);
+    path.lineTo(10, 3.35545e+07f);
+    path.close();
+    path.moveTo(10, 90);
+    path.lineTo(110, 90);
+    path.lineTo(110, 30);
+    path.lineTo(10, 30);
+    path.lineTo(10, 90);
+    path.close();
+    testSimplifyFuzz(reporter, path, filename);
+}
+
 #define TEST(test) test(reporter, #test)
 
 DEF_TEST(PathOpsSimplifyFail, reporter) {
+    TEST(fuzz864a);
+    TEST(fuzz763_4713_b);
+    TEST(fuzz994s_3414);
+    TEST(fuzz994s_11);
+    TEST(fuzz_twister2);
+    TEST(fuzz_twister);
     TEST(fuzz763_2);
     TEST(fuzz763_1);
     TEST(fuzz_x2);