aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2013-04-08 11:50:00 +0000
committerGravatar caryclark@google.com <caryclark@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>2013-04-08 11:50:00 +0000
commit9166dcb3a0e8784bea83d76ae01aa338c049ae05 (patch)
treea5c450613d4fa7d2153162b5ac9d4670b1b4f0bc
parent07393cab57ce74a4aae89a31fae9aaa9780fc19d (diff)
Add intersections for path ops
This CL depends on https://codereview.chromium.org/12827020/ "Add base types for path ops" The intersection of a line, quadratic, or cubic with another curve (or with itself) is found by solving the implicit equation for the curve pair. The curves are first reduced to find the simplest form that will describe the original, and to detect degenerate or special-case data like horizontal and vertical lines. For cubic self-intersection, and for a pair of cubics, the intersection is found by recursively approximating the cubic with a series of quadratics. The implicit solutions depend on the root finding contained in the DCubic and DQuad structs, and the quartic root finder included here. Review URL: https://codereview.chromium.org/12880016 git-svn-id: http://skia.googlecode.com/svn/trunk@8552 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat
-rw-r--r--tests/PathOpsCubicIntersectionTest.cpp513
-rw-r--r--tests/PathOpsCubicIntersectionTestData.cpp300
-rw-r--r--tests/PathOpsCubicIntersectionTestData.h30
-rw-r--r--tests/PathOpsCubicLineIntersectionTest.cpp61
-rw-r--r--tests/PathOpsCubicReduceOrderTest.cpp226
-rw-r--r--tests/PathOpsCubicToQuadsTest.cpp202
-rw-r--r--tests/PathOpsLineIntersectionTest.cpp61
-rw-r--r--tests/PathOpsLineParametetersTest.cpp80
-rw-r--r--tests/PathOpsQuadIntersectionTest.cpp468
-rw-r--r--tests/PathOpsQuadIntersectionTestData.cpp104
-rw-r--r--tests/PathOpsQuadIntersectionTestData.h17
-rw-r--r--tests/PathOpsQuadLineIntersectionTest.cpp132
-rw-r--r--tests/PathOpsQuadParameterizationTest.cpp53
13 files changed, 2247 insertions, 0 deletions
diff --git a/tests/PathOpsCubicIntersectionTest.cpp b/tests/PathOpsCubicIntersectionTest.cpp
new file mode 100644
index 0000000000..5a6a336a3f
--- /dev/null
+++ b/tests/PathOpsCubicIntersectionTest.cpp
@@ -0,0 +1,513 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "PathOpsCubicIntersectionTestData.h"
+#include "PathOpsTestCommon.h"
+#include "SkIntersections.h"
+#include "SkPathOpsRect.h"
+#include "SkReduceOrder.h"
+#include "Test.h"
+
+const int firstCubicIntersectionTest = 9;
+
+static void standardTestCases(skiatest::Reporter* reporter) {
+ for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index) {
+ int iIndex = static_cast<int>(index);
+ const SkDCubic& cubic1 = tests[index][0];
+ const SkDCubic& cubic2 = tests[index][1];
+ SkReduceOrder reduce1, reduce2;
+ int order1 = reduce1.reduce(cubic1, SkReduceOrder::kNo_Quadratics,
+ SkReduceOrder::kFill_Style);
+ int order2 = reduce2.reduce(cubic2, SkReduceOrder::kNo_Quadratics,
+ SkReduceOrder::kFill_Style);
+ const bool showSkipped = false;
+ if (order1 < 4) {
+ if (showSkipped) {
+ SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, iIndex, order1);
+ }
+ continue;
+ }
+ if (order2 < 4) {
+ if (showSkipped) {
+ SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, order2);
+ }
+ continue;
+ }
+ SkIntersections tIntersections;
+ tIntersections.intersect(cubic1, cubic2);
+ if (!tIntersections.used()) {
+ if (showSkipped) {
+ SkDebugf("%s [%d] no intersection\n", __FUNCTION__, iIndex);
+ }
+ continue;
+ }
+ if (tIntersections.isCoincident(0)) {
+ if (showSkipped) {
+ SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex);
+ }
+ continue;
+ }
+ for (int pt = 0; pt < tIntersections.used(); ++pt) {
+ double tt1 = tIntersections[0][pt];
+ SkDPoint xy1 = cubic1.xyAtT(tt1);
+ double tt2 = tIntersections[1][pt];
+ SkDPoint xy2 = cubic2.xyAtT(tt2);
+ if (!xy1.approximatelyEqual(xy2)) {
+ SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
+ __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY);
+ }
+ REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
+ }
+ }
+}
+
+static const SkDCubic testSet[] = {
+// FIXME: uncommenting these two will cause this to fail
+// this results in two curves very nearly but not exactly coincident
+#if 0
+{{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
+ {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
+{{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826},
+ {75.3863417, 18.24489}}},
+#endif
+
+{{{0, 0}, {0, 1}, {1, 1}, {1, 0}}},
+{{{1, 0}, {0, 0}, {0, 1}, {1, 1}}},
+
+{{{0, 1}, {4, 5}, {1, 0}, {5, 3}}},
+{{{0, 1}, {3, 5}, {1, 0}, {5, 4}}},
+
+{{{0, 1}, {1, 6}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {1, 0}, {6, 1}}},
+
+{{{0, 1}, {3, 4}, {1, 0}, {5, 1}}},
+{{{0, 1}, {1, 5}, {1, 0}, {4, 3}}},
+
+{{{0, 1}, {1, 2}, {1, 0}, {6, 1}}},
+{{{0, 1}, {1, 6}, {1, 0}, {2, 1}}},
+
+{{{0, 1}, {0, 5}, {1, 0}, {4, 0}}},
+{{{0, 1}, {0, 4}, {1, 0}, {5, 0}}},
+
+{{{0, 1}, {3, 4}, {1, 0}, {3, 0}}},
+{{{0, 1}, {0, 3}, {1, 0}, {4, 3}}},
+
+{{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
+{{{0, 0}, {1, 2}, {3, 4}, {4, 4}}},
+{{{4, 4}, {3, 4}, {1, 2}, {0, 0}}},
+
+{{{0, 1}, {2, 3}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {1, 0}, {3, 2}}},
+
+{{{0, 2}, {0, 1}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {2, 0}, {1, 0}}},
+
+{{{0, 1}, {0, 2}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {1, 0}, {2, 0}}},
+
+{{{0, 1}, {1, 6}, {1, 0}, {2, 0}}},
+{{{0, 1}, {0, 2}, {1, 0}, {6, 1}}},
+
+{{{0, 1}, {5, 6}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {1, 0}, {6, 5}}},
+
+{{{95.837747722788592, 45.025976907939643}, {16.564570095652982, 0.72959763963222402},
+ {63.209855865319199, 68.047528419665767}, {57.640240647662544, 59.524565264361243}}},
+{{{51.593891741518817, 38.53849970667553}, {62.34752929878772, 74.924924725166022},
+ {74.810149322641152, 34.17966562983564}, {29.368398119401373, 94.66719277886078}}},
+
+{{{39.765160968417838, 33.060396198677083}, {5.1922921581157908, 66.854301452103215},
+ {31.619281802149157, 25.269248720849514}, {81.541621071073038, 70.025341524754353}}},
+{{{46.078911165743556, 48.259962651999651}, {20.24450549867214, 49.403916182650214},
+ {0.26325131778756683, 24.46489805563581}, {15.915006546264051, 83.515023059917155}}},
+
+{{{65.454505973241524, 93.881892270353575}, {45.867360264932437, 92.723972719499827},
+ {2.1464054482739447, 74.636369140183717}, {33.774068594804994, 40.770872887582925}}},
+{{{72.963387832494163, 95.659300729473728}, {11.809496633619768, 82.209921247423594},
+ {13.456139067865974, 57.329313623406605}, {36.060621606214262, 70.867335643091849}}},
+
+{{{32.484981432782945, 75.082940782924624}, {42.467313093350882, 48.131159948246157},
+ {3.5963115764764657, 43.208665839959245}, {79.442476890721579, 89.709102357602262}}},
+{{{18.98573861410177, 93.308887208490106}, {40.405250173250792, 91.039661826118675},
+ {8.0467721950480584, 42.100282172719147}, {40.883324221187891, 26.030185504830527}}},
+
+{{{7.5374809128872498, 82.441702896003477}, {22.444346930107265, 22.138854312775123},
+ {66.76091829629658, 50.753805856571446}, {78.193478508942519, 97.7932997968948}}},
+{{{97.700573130371311, 53.53260215070685}, {87.72443481149358, 84.575876772671876},
+ {19.215031396232092, 47.032676472809484}, {11.989686410869325, 10.659507480757082}}},
+
+{{{26.192053931854691, 9.8504326817814416}, {10.174241480498686, 98.476562741434464},
+ {21.177712558385782, 33.814968789841501}, {75.329030899018534, 55.02231980442177}}},
+{{{56.222082700683771, 24.54395039218662}, {95.589995289030483, 81.050822735322086},
+ {28.180450866082897, 28.837706255185282}, {60.128952916771617, 87.311672180570511}}},
+
+{{{42.449716172390481, 52.379709366885805}, {27.896043159019225, 48.797373636065686},
+ {92.770268299044233, 89.899302036454571}, {12.102066544863426, 99.43241951960718}}},
+{{{45.77532924980639, 45.958701495993274}, {37.458701356062065, 68.393691335056758},
+ {37.569326692060258, 27.673713456687381}, {60.674866037757539, 62.47349659096146}}},
+
+{{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921306},
+ {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038969412}}},
+{{{61.336508189019057, 82.693132843213675}, {44.639380902349664, 54.074825790745592},
+ {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503699973002}}},
+
+{{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945},
+ {18.5656052, 32.1268808}}},
+{{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981},
+ {56.4860195, 60.529264}}},
+};
+
+const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
+
+static const SkDCubic newTestSet[] = {
+{{{0, 1}, {1, 5}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {1, 0}, {5, 1}}},
+
+{{{1, 3}, {5, 6}, {5, 3}, {5, 4}}},
+{{{3, 5}, {4, 5}, {3, 1}, {6, 5}}},
+
+{{{0, 5}, {0, 5}, {5, 4}, {6, 4}}},
+{{{4, 5}, {4, 6}, {5, 0}, {5, 0}}},
+
+{{{0, 4}, {1, 3}, {5, 4}, {4, 2}}},
+{{{4, 5}, {2, 4}, {4, 0}, {3, 1}}},
+
+{{{0, 2}, {1, 5}, {3, 2}, {4, 1}}},
+{{{2, 3}, {1, 4}, {2, 0}, {5, 1}}},
+
+{{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
+{{{1, 5}, {2, 3}, {2, 0}, {3, 2}}},
+
+{{{2, 6}, {4, 5}, {1, 0}, {6, 1}}},
+{{{0, 1}, {1, 6}, {6, 2}, {5, 4}}},
+
+{{{0, 1}, {1, 2}, {6, 5}, {5, 4}}},
+{{{5, 6}, {4, 5}, {1, 0}, {2, 1}}},
+
+{{{2.5119999999999996, 1.5710000000000002}, {2.6399999999999983, 1.6599999999999997},
+ {2.8000000000000007, 1.8000000000000003}, {3, 2}}},
+{{{2.4181876227114887, 1.9849772580462195}, {2.8269904869227211, 2.009330650246834},
+ {3.2004679292461624, 1.9942047174679169}, {3.4986199496818058, 2.0035994597094731}}},
+
+{{{2, 3}, {1, 4}, {1, 0}, {6, 0}}},
+{{{0, 1}, {0, 6}, {3, 2}, {4, 1}}},
+
+{{{0, 2}, {1, 5}, {1, 0}, {6, 1}}},
+{{{0, 1}, {1, 6}, {2, 0}, {5, 1}}},
+
+{{{0, 1}, {1, 5}, {2, 1}, {4, 0}}},
+{{{1, 2}, {0, 4}, {1, 0}, {5, 1}}},
+
+{{{0, 1}, {3, 5}, {2, 1}, {3, 1}}},
+{{{1, 2}, {1, 3}, {1, 0}, {5, 3}}},
+
+{{{0, 1}, {2, 5}, {6, 0}, {5, 3}}},
+{{{0, 6}, {3, 5}, {1, 0}, {5, 2}}},
+
+{{{0, 1}, {3, 6}, {1, 0}, {5, 2}}},
+{{{0, 1}, {2, 5}, {1, 0}, {6, 3}}},
+
+{{{1, 2}, {5, 6}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {2, 1}, {6, 5}}},
+
+{{{0, 6}, {1, 2}, {1, 0}, {1, 0}}},
+{{{0, 1}, {0, 1}, {6, 0}, {2, 1}}},
+
+{{{0, 2}, {0, 1}, {3, 0}, {1, 0}}},
+{{{0, 3}, {0, 1}, {2, 0}, {1, 0}}},
+};
+
+const size_t newTestSetCount = sizeof(newTestSet) / sizeof(newTestSet[0]);
+
+static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const SkDCubic& cubic2) {
+#if ONE_OFF_DEBUG
+ SkDebugf("computed quadratics given\n");
+ SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n",
+ cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY,
+ cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY);
+ SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n",
+ cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY,
+ cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY);
+#endif
+ SkTDArray<SkDQuad> quads1;
+ CubicToQuads(cubic1, cubic1.calcPrecision(), quads1);
+#if ONE_OFF_DEBUG
+ SkDebugf("computed quadratics set 1\n");
+ for (int index = 0; index < quads1.count(); ++index) {
+ const SkDQuad& q = quads1[index];
+ SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX, q[0].fY,
+ q[1].fX, q[1].fY, q[2].fX, q[2].fY);
+ }
+#endif
+ SkTDArray<SkDQuad> quads2;
+ CubicToQuads(cubic2, cubic2.calcPrecision(), quads2);
+#if ONE_OFF_DEBUG
+ SkDebugf("computed quadratics set 2\n");
+ for (int index = 0; index < quads2.count(); ++index) {
+ const SkDQuad& q = quads2[index];
+ SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", q[0].fX, q[0].fY,
+ q[1].fX, q[1].fY, q[2].fX, q[2].fY);
+ }
+#endif
+ SkIntersections intersections;
+ intersections.intersect(cubic1, cubic2);
+ double tt1, tt2;
+ SkDPoint xy1, xy2;
+ for (int pt3 = 0; pt3 < intersections.used(); ++pt3) {
+ tt1 = intersections[0][pt3];
+ xy1 = cubic1.xyAtT(tt1);
+ tt2 = intersections[1][pt3];
+ xy2 = cubic2.xyAtT(tt2);
+#if ONE_OFF_DEBUG
+ SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1.9g\n",
+ __FUNCTION__, tt1, xy1.fX, xy1.fY, intersections.pt(pt3).fX,
+ intersections.pt(pt3).fY, xy2.fX, xy2.fY, tt2);
+#endif
+ REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
+ }
+}
+
+static void oneOff(skiatest::Reporter* reporter, int outer, int inner) {
+ const SkDCubic& cubic1 = testSet[outer];
+ const SkDCubic& cubic2 = testSet[inner];
+ oneOff(reporter, cubic1, cubic2);
+}
+
+static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) {
+ const SkDCubic& cubic1 = newTestSet[outer];
+ const SkDCubic& cubic2 = newTestSet[inner];
+ oneOff(reporter, cubic1, cubic2);
+}
+
+static void oneOffTest(skiatest::Reporter* reporter) {
+ newOneOff(reporter, 0, 1);
+ oneOff(reporter, 0, 1);
+}
+
+static void oneOffTests(skiatest::Reporter* reporter) {
+ for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
+ for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
+ oneOff(reporter, outer, inner);
+ }
+ }
+ for (size_t outer = 0; outer < newTestSetCount - 1; ++outer) {
+ for (size_t inner = outer + 1; inner < newTestSetCount; ++inner) {
+ oneOff(reporter, outer, inner);
+ }
+ }
+}
+
+#define DEBUG_CRASH 0
+
+static void CubicIntersection_RandTest(skiatest::Reporter* reporter) {
+ srand(0);
+ const int tests = 10000000;
+#ifndef SK_BUILD_FOR_WIN
+ unsigned seed = 0;
+#endif
+ for (int test = 0; test < tests; ++test) {
+ SkDCubic cubic1, cubic2;
+ for (int i = 0; i < 4; ++i) {
+ cubic1[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
+ cubic1[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
+ cubic2[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
+ cubic2[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100;
+ }
+ #if DEBUG_CRASH
+ char str[1024];
+ snprintf(str, sizeof(str),
+ "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n"
+ "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},\n",
+ cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[2].fX, cubic1[2].fY,
+ cubic1[3].fX, cubic1[3].fY,
+ cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[2].fX, cubic2[2].fY,
+ cubic2[3].fX, cubic2[3].fY);
+ #endif
+ SkDRect rect1, rect2;
+ rect1.setBounds(cubic1);
+ rect2.setBounds(cubic2);
+ bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rect2.fRight
+ && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom;
+ if (test == -1) {
+ SkDebugf("ready...\n");
+ }
+ SkIntersections intersections2;
+ int newIntersects = intersections2.intersect(cubic1, cubic2);
+ if (!boundsIntersect && newIntersects) {
+ #if DEBUG_CRASH
+ SkDebugf("%s %d unexpected intersection boundsIntersect=%d "
+ " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsIntersect,
+ newIntersects, __FUNCTION__, str);
+ #endif
+ REPORTER_ASSERT(reporter, 0);
+ }
+ for (int pt = 0; pt < intersections2.used(); ++pt) {
+ double tt1 = intersections2[0][pt];
+ SkDPoint xy1 = cubic1.xyAtT(tt1);
+ double tt2 = intersections2[1][pt];
+ SkDPoint xy2 = cubic2.xyAtT(tt2);
+ REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
+ }
+ }
+}
+
+static void intersectionFinder(int index0, int index1, double t1Seed, double t2Seed,
+ double t1Step, double t2Step) {
+ const SkDCubic& cubic1 = newTestSet[index0];
+ const SkDCubic& cubic2 = newTestSet[index1];
+ SkDPoint t1[3], t2[3];
+ bool toggle = true;
+ do {
+ t1[0] = cubic1.xyAtT(t1Seed - t1Step);
+ t1[1] = cubic1.xyAtT(t1Seed);
+ t1[2] = cubic1.xyAtT(t1Seed + t1Step);
+ t2[0] = cubic2.xyAtT(t2Seed - t2Step);
+ t2[1] = cubic2.xyAtT(t2Seed);
+ t2[2] = cubic2.xyAtT(t2Seed + t2Step);
+ double dist[3][3];
+ dist[1][1] = t1[1].distance(t2[1]);
+ int best_i = 1, best_j = 1;
+ for (int i = 0; i < 3; ++i) {
+ for (int j = 0; j < 3; ++j) {
+ if (i == 1 && j == 1) {
+ continue;
+ }
+ dist[i][j] = t1[i].distance(t2[j]);
+ if (dist[best_i][best_j] > dist[i][j]) {
+ best_i = i;
+ best_j = j;
+ }
+ }
+ }
+ if (best_i == 0) {
+ t1Seed -= t1Step;
+ } else if (best_i == 2) {
+ t1Seed += t1Step;
+ }
+ if (best_j == 0) {
+ t2Seed -= t2Step;
+ } else if (best_j == 2) {
+ t2Seed += t2Step;
+ }
+ if (best_i == 1 && best_j == 1) {
+ if ((toggle ^= true)) {
+ t1Step /= 2;
+ } else {
+ t2Step /= 2;
+ }
+ }
+ } while (!t1[1].approximatelyEqual(t2[1]));
+ t1Step = t2Step = 0.1;
+ double t10 = t1Seed - t1Step * 2;
+ double t12 = t1Seed + t1Step * 2;
+ double t20 = t2Seed - t2Step * 2;
+ double t22 = t2Seed + t2Step * 2;
+ SkDPoint test;
+ while (!approximately_zero(t1Step)) {
+ test = cubic1.xyAtT(t10);
+ t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
+ t1Step /= 2;
+ }
+ t1Step = 0.1;
+ while (!approximately_zero(t1Step)) {
+ test = cubic1.xyAtT(t12);
+ t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
+ t1Step /= 2;
+ }
+ while (!approximately_zero(t2Step)) {
+ test = cubic2.xyAtT(t20);
+ t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
+ t2Step /= 2;
+ }
+ t2Step = 0.1;
+ while (!approximately_zero(t2Step)) {
+ test = cubic2.xyAtT(t22);
+ t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
+ t2Step /= 2;
+ }
+#if ONE_OFF_DEBUG
+ SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__,
+ t10, t1Seed, t12, t20, t2Seed, t22);
+ SkDPoint p10 = cubic1.xyAtT(t10);
+ SkDPoint p1Seed = cubic1.xyAtT(t1Seed);
+ SkDPoint p12 = cubic1.xyAtT(t12);
+ SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY);
+ SkDPoint p20 = cubic2.xyAtT(t20);
+ SkDPoint p2Seed = cubic2.xyAtT(t2Seed);
+ SkDPoint p22 = cubic2.xyAtT(t22);
+ SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY);
+#endif
+}
+
+static void CubicIntersection_IntersectionFinder() {
+// double t1Seed = 0.87;
+// double t2Seed = 0.87;
+ double t1Step = 0.000001;
+ double t2Step = 0.000001;
+ intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step);
+ intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step);
+ intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step);
+}
+
+static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) {
+ const SkDCubic selfSet[] = {
+ {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}},
+ {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}},
+ {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}},
+ {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}},
+ {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}},
+ {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}},
+ };
+ size_t selfSetCount = sizeof(selfSet) / sizeof(selfSet[0]);
+ size_t firstFail = 1;
+ for (size_t index = firstFail; index < selfSetCount; ++index) {
+ const SkDCubic& cubic = selfSet[index];
+ #if ONE_OFF_DEBUG
+ int idx2;
+ double max[3];
+ int ts = cubic.findMaxCurvature(max);
+ for (idx2 = 0; idx2 < ts; ++idx2) {
+ SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2,
+ max[idx2], cubic.xyAtT(max[idx2]).fX, cubic.xyAtT(max[idx2]).fY);
+ }
+ SkTDArray<double> ts1;
+ SkTDArray<SkDQuad> quads1;
+ cubic.toQuadraticTs(cubic.calcPrecision(), &ts1);
+ for (idx2 = 0; idx2 < ts1.count(); ++idx2) {
+ SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]);
+ }
+ CubicToQuads(cubic, cubic.calcPrecision(), quads1);
+ for (idx2 = 0; idx2 < quads1.count(); ++idx2) {
+ const SkDQuad& q = quads1[idx2];
+ SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n",
+ q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY);
+ }
+ SkDebugf("\n");
+ #endif
+ SkIntersections i;
+ int result = i.intersect(cubic);
+ REPORTER_ASSERT(reporter, result == 1);
+ REPORTER_ASSERT(reporter, i.used() == 1);
+ REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0]));
+ SkDPoint pt1 = cubic.xyAtT(i[0][0]);
+ SkDPoint pt2 = cubic.xyAtT(i[1][0]);
+ REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2));
+ }
+}
+
+static void TestCubicIntersection(skiatest::Reporter* reporter) {
+ oneOffTest(reporter);
+ oneOffTests(reporter);
+ cubicIntersectionSelfTest(reporter);
+ standardTestCases(reporter);
+ if (false) CubicIntersection_IntersectionFinder();
+ if (false) CubicIntersection_RandTest(reporter);
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsCubicIntersectionTest", CubicIntersectionTestClass, TestCubicIntersection)
diff --git a/tests/PathOpsCubicIntersectionTestData.cpp b/tests/PathOpsCubicIntersectionTestData.cpp
new file mode 100644
index 0000000000..04c46d5267
--- /dev/null
+++ b/tests/PathOpsCubicIntersectionTestData.cpp
@@ -0,0 +1,300 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "PathOpsCubicIntersectionTestData.h"
+#include <limits>
+
+static const double D = FLT_EPSILON / 2;
+static const double G = FLT_EPSILON / 3;
+static const double N = -FLT_EPSILON / 2;
+static const double M = -FLT_EPSILON / 3;
+
+const SkDCubic pointDegenerates[] = {
+ {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}},
+ {{{1, 1}, {1, 1}, {1, 1}, {1, 1}}},
+ {{{1 + FLT_EPSILON_HALF, 1}, {1, 1 + FLT_EPSILON_HALF}, {1, 1}, {1, 1}}},
+ {{{1 + D, 1}, {1 - D, 1}, {1, 1}, {1, 1}}},
+ {{{0, 0}, {0, 0}, {1, 0}, {0, 0}}},
+ {{{0, 0}, {1, 0}, {0, 0}, {0, 0}}},
+ {{{0, 0}, {0, 0}, {0, 1}, {0, 0}}},
+ {{{0, 0}, {0, 1}, {0, 0}, {0, 0}}},
+ {{{0, 0}, {0, 0}, {1, 1}, {0, 0}}},
+ {{{0, 0}, {1, 1}, {0, 0}, {0, 0}}},
+ {{{0, 0}, {1, 1}, {2, 2}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {2, 2}, {1, 1}}},
+ {{{0, 0}, {0, D}, {1, 0}, {0, 0}}},
+ {{{0, 0}, {1, 0}, {0, D}, {0, 0}}},
+ {{{0, 0}, {D, 0}, {0, 1}, {0, 0}}},
+ {{{0, 0}, {0, 1}, {D, 0}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {2, 2+D}, {1, 1}}},
+ {{{0, 0}, {0, N}, {1, 0}, {0, 0}}},
+ {{{0, 0}, {1, 0}, {0, N}, {0, 0}}},
+ {{{0, 0}, {N, 0}, {0, 1}, {0, 0}}},
+ {{{0, 0}, {0, 1}, {N, 0}, {0, 0}}},
+ {{{0, 0}, {1, 1}, {N, 0}, {0, 0}}},
+ {{{0, 0}, {D, 0}, {1, 1}, {0, 0}}},
+ {{{0, 0}, {1, 1}, {D, 0}, {0, 0}}},
+ {{{0, 0}, {N, 0}, {1, 1}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {2, 2+N}, {1, 1}}},
+};
+
+const size_t pointDegenerates_count = sizeof(pointDegenerates) / sizeof(pointDegenerates[0]);
+
+const SkDCubic notPointDegenerates[] = {
+ {{{1 + FLT_EPSILON * 2, 1}, {1, FLT_EPSILON * 2}, {1, 1}, {1, 1}}},
+ {{{1 + FLT_EPSILON * 2, 1}, {1 - FLT_EPSILON * 2, 1}, {1, 1}, {1, 1}}}
+};
+
+const size_t notPointDegenerates_count =
+ sizeof(notPointDegenerates) / sizeof(notPointDegenerates[0]);
+
+// from http://www.truetex.com/bezint.htm
+const SkDCubic tests[][2] = {
+ { // intersects in one place (data gives bezier clip fits
+ {{{0, 45},
+ {6.0094158284751593, 51.610357411322688},
+ {12.741093228940867, 55.981703949474607},
+ {20.021417396476362, 58.652245509710262}}},
+ {{{2.2070737699246674, 52.703494107327209},
+ {31.591482272629477, 23.811002295222025},
+ {76.824588616426425, 44.049473790502674},
+ {119.25488947221436, 55.599248272955073}}}
+ }, { // intersects in three places
+ {{{0, 45}, {50, 100}, {150, 0}, {200, 55}}},
+ {{{0, 55}, {50, 0}, {150, 100}, {200, 45}}}
+ }, { // intersects in one place, cross over is nearly parallel
+ {{{0, 0}, {0, 100}, {200, 0}, {200, 100}}},
+ {{{0, 100}, {0, 0}, {200, 100}, {200, 0}}}
+ }, { // intersects in two places
+ {{{0, 0}, {0, 100}, {200, 100}, {200, 0}}},
+ {{{0, 100}, {0, 0}, {200, 0}, {200, 100}}}
+ }, {
+ {{{150, 100}, {150 + 0.1, 150}, {150, 200}, {150, 250}}},
+ {{{250, 150}, {200, 150 + 0.1}, {150, 150}, {100, 150}}}
+ }, { // single intersection around 168,185
+ {{{200, 100}, {150, 100}, {150, 150}, {200, 150}}},
+ {{{250, 150}, {250, 100}, {100, 100}, {100, 150}}}
+ }, {
+ {{{1.0, 1.5}, {15.5, 0.5}, {-8.0, 3.5}, {5.0, 1.5}}},
+ {{{4.0, 0.5}, {5.0, 15.0}, {2.0, -8.5}, {4.0, 4.5}}}
+ }, {
+ {{{664.00168, 0}, {726.11545, 124.22757}, {736.89069, 267.89743},
+ {694.0017, 400.0002}}},
+ {{{850.66843, 115.55563}, {728.515, 115.55563}, {725.21347, 275.15309},
+ {694.0017, 400.0002}}}
+ }, {
+ {{{1, 1}, {12.5, 6.5}, {-4, 6.5}, {7.5, 1}}},
+ {{{1, 6.5}, {12.5, 1}, {-4, 1}, {.5, 6}}}
+ }, {
+ {{{315.748, 312.84}, {312.644, 318.134}, {305.836, 319.909}, {300.542, 316.804}}},
+ {{{317.122, 309.05}, {316.112, 315.102}, {310.385, 319.19}, {304.332, 318.179}}}
+ }, {
+ {{{1046.604051, 172.937967}, {1046.604051, 178.9763059}, {1041.76745, 183.9279165}, {1035.703842, 184.0432409}}},
+ {{{1046.452235, 174.7640504}, {1045.544872, 180.1973817}, {1040.837966, 184.0469882}, {1035.505925, 184.0469882}}}
+ }, {
+ {{{125.79356, 199.57382}, {51.16556, 128.93575}, {87.494, 16.67848}, {167.29361, 16.67848}}},
+ {{{167.29361, 55.81876}, {100.36128, 55.81876}, {68.64099, 145.4755}, {125.7942, 199.57309}}}
+ }
+};
+
+const size_t tests_count = sizeof(tests) / sizeof(tests[0]);
+
+SkDCubic hexTests[][2] = {
+ {
+ // placeholder for hex converted below
+ {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}}, {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}}
+ }
+};
+
+const size_t hexTests_count = sizeof(hexTests) / sizeof(hexTests[0]);
+
+static const uint64_t testx[2][8] = {
+ {
+ 0xf0d0d1ca63075a40LLU, 0x9408ce996a237740LLU, 0x6d5675460fbe5e40LLU, 0x6ef501e1b7487940LLU,
+ 0x9a71d2f8143d6540LLU, 0x6bc18bbe02907a40LLU, 0x5b94d92093aa6b40LLU, 0x6ac18bbe02907a40LLU
+ },
+ {
+ 0x92c56ed7b6145d40LLU, 0xede4f1255edb7740LLU, 0x1138c1101af75940LLU, 0x42e4f1255edb7740LLU,
+ 0x408e51603ad95640LLU, 0x1e2e8fe9dd927740LLU, 0x1cb4777cd3a75440LLU, 0x212e1390de017740LLU
+ }
+};
+
+void convert_testx() {
+ const uint64_t* inPtr = testx[0];
+ double* outPtr = &hexTests[sizeof(tests) / sizeof(tests[0]) - 1][0][0].fX;
+ for (unsigned index = 0; index < sizeof(testx) / sizeof(testx[0][0]); ++index) {
+ uint64_t input = *inPtr++;
+ unsigned char* output = (unsigned char*) outPtr++;
+ for (unsigned byte = 0; byte < sizeof(input); ++byte) {
+ output[byte] = input >> (7 - byte) * 8;
+ }
+ }
+}
+
+const SkDCubic lines[] = {
+ {{{0, 0}, {0, 0}, {0, 0}, {1, 0}}}, // 0: horizontal
+ {{{1, 0}, {0, 0}, {0, 0}, {0, 0}}},
+ {{{1, 0}, {2, 0}, {3, 0}, {4, 0}}},
+ {{{0, 0}, {0, 0}, {0, 0}, {0, 1}}}, // 5: vertical
+ {{{0, 1}, {0, 0}, {0, 0}, {0, 0}}},
+ {{{0, 1}, {0, 2}, {0, 3}, {0, 4}}},
+ {{{0, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 10: 3 coincident
+ {{{1, 1}, {0, 0}, {0, 0}, {0, 0}}},
+ {{{0, 0}, {0, 0}, {1, 1}, {2, 2}}}, // 14: 2 coincident
+ {{{0, 0}, {1, 1}, {0, 0}, {2, 2}}},
+ {{{1, 1}, {0, 0}, {0, 0}, {2, 2}}}, // 17:
+ {{{1, 1}, {0, 0}, {2, 2}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {0, 0}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {3, 3}, {2, 2}}}, // middle-last coincident
+ {{{1, 1}, {2, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
+ {{{1, 1}, {1, 1}, {2, 2}, {2, 2}}}, // 2 pairs coincident
+ {{{1, 1}, {2, 2}, {1, 1}, {2, 2}}},
+ {{{1, 1}, {1, 1}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
+ {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}}, // no coincident
+ {{{1, 1}, {3, 3}, {2, 2}, {4, 4}}},
+ {{{1, 1}, {2, 2}, {4, 4}, {3, 3}}},
+ {{{1, 1}, {3, 3}, {4, 4}, {2, 2}}},
+ {{{1, 1}, {4, 4}, {2, 2}, {3, 3}}},
+ {{{1, 1}, {4, 4}, {3, 3}, {2, 2}}},
+ {{{2, 2}, {1, 1}, {3, 3}, {4, 4}}},
+ {{{2, 2}, {1, 1}, {4, 4}, {3, 3}}},
+ {{{2, 2}, {3, 3}, {1, 1}, {4, 4}}},
+ {{{2, 2}, {3, 3}, {4, 4}, {1, 1}}},
+ {{{2, 2}, {4, 4}, {1, 1}, {3, 3}}},
+ {{{2, 2}, {4, 4}, {3, 3}, {1, 1}}},
+};
+
+const size_t lines_count = sizeof(lines) / sizeof(lines[0]);
+
+// 'not a line' tries to fool the line detection code
+const SkDCubic notLines[] = {
+ {{{0, 0}, {0, 0}, {0, 1}, {1, 0}}},
+ {{{0, 0}, {0, 1}, {0, 0}, {1, 0}}},
+ {{{0, 0}, {0, 1}, {1, 0}, {0, 0}}},
+ {{{0, 1}, {0, 0}, {0, 0}, {1, 0}}},
+ {{{0, 1}, {0, 0}, {1, 0}, {0, 0}}},
+ {{{0, 1}, {1, 0}, {0, 0}, {0, 0}}},
+};
+
+const size_t notLines_count = sizeof(notLines) / sizeof(notLines[0]);
+
+static const double E = FLT_EPSILON * 2;
+static const double F = FLT_EPSILON * 3;
+
+const SkDCubic modEpsilonLines[] = {
+ {{{0, E}, {0, 0}, {0, 0}, {1, 0}}}, // horizontal
+ {{{0, 0}, {0, E}, {1, 0}, {0, 0}}},
+ {{{0, 0}, {1, 0}, {0, E}, {0, 0}}},
+ {{{1, 0}, {0, 0}, {0, 0}, {0, E}}},
+ {{{1, E}, {2, 0}, {3, 0}, {4, 0}}},
+ {{{E, 0}, {0, 0}, {0, 0}, {0, 1}}}, // vertical
+ {{{0, 0}, {E, 0}, {0, 1}, {0, 0}}},
+ {{{0, 0}, {0, 1}, {E, 0}, {0, 0}}},
+ {{{0, 1}, {0, 0}, {0, 0}, {E, 0}}},
+ {{{E, 1}, {0, 2}, {0, 3}, {0, 4}}},
+ {{{E, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 3 coincident
+ {{{0, 0}, {E, 0}, {1, 1}, {0, 0}}},
+ {{{0, 0}, {1, 1}, {E, 0}, {0, 0}}},
+ {{{1, 1}, {0, 0}, {0, 0}, {E, 0}}},
+ {{{0, E}, {0, 0}, {1, 1}, {2, 2}}}, // 2 coincident
+ {{{0, 0}, {1, 1}, {0, E}, {2, 2}}},
+ {{{0, 0}, {1, 1}, {2, 2}, {0, E}}},
+ {{{1, 1}, {0, E}, {0, 0}, {2, 2}}},
+ {{{1, 1}, {0, E}, {2, 2}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {E, 0}, {0, 0}}},
+ {{{1, 1}, {2, 2+E}, {3, 3}, {2, 2}}}, // middle-last coincident
+ {{{1, 1}, {2+E, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
+ {{{1, 1}, {1, 1}, {2, 2}, {2+E, 2}}}, // 2 pairs coincident
+ {{{1, 1}, {2, 2}, {1, 1}, {2+E, 2}}},
+ {{{1, 1}, {2, 2}, {2, 2+E}, {1, 1}}},
+ {{{1, 1}, {1, 1+E}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
+ {{{1, 1}, {2+E, 2}, {3, 3}, {4, 4}}}, // no coincident
+ {{{1, 1}, {3, 3}, {2, 2}, {4, 4+F}}}, // INVESTIGATE: why the epsilon is bigger
+ {{{1, 1+F}, {2, 2}, {4, 4}, {3, 3}}}, // INVESTIGATE: why the epsilon is bigger
+ {{{1, 1}, {3, 3}, {4, 4+E}, {2, 2}}},
+ {{{1, 1}, {4, 4}, {2, 2}, {3, 3+E}}},
+ {{{1, 1}, {4, 4}, {3, 3}, {2+E, 2}}},
+ {{{2, 2}, {1, 1}, {3+E, 3}, {4, 4}}},
+ {{{2, 2}, {1+E, 1}, {4, 4}, {3, 3}}},
+ {{{2, 2+E}, {3, 3}, {1, 1}, {4, 4}}},
+ {{{2+E, 2}, {3, 3}, {4, 4}, {1, 1}}},
+ {{{2, 2}, {4+E, 4}, {1, 1}, {3, 3}}},
+ {{{2, 2}, {4, 4}, {3, 3}, {1, 1+E}}},
+};
+
+const size_t modEpsilonLines_count = sizeof(modEpsilonLines) / sizeof(modEpsilonLines[0]);
+
+const SkDCubic lessEpsilonLines[] = {
+ {{{0, D}, {0, 0}, {0, 0}, {1, 0}}}, // horizontal
+ {{{1, 0}, {0, 0}, {0, 0}, {0, D}}},
+ {{{1, D}, {2, 0}, {3, 0}, {4, 0}}},
+ {{{D, 0}, {0, 0}, {0, 0}, {0, 1}}}, // vertical
+ {{{0, 1}, {0, 0}, {0, 0}, {D, 0}}},
+ {{{D, 1}, {0, 2}, {0, 3}, {0, 4}}},
+ {{{D, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 3 coincident
+ {{{1, 1}, {0, 0}, {0, 0}, {D, 0}}},
+ {{{0, D}, {0, 0}, {1, 1}, {2, 2}}}, // 2 coincident
+ {{{0, 0}, {1, 1}, {0, D}, {2, 2}}},
+ {{{0, 0}, {1, 1}, {2, 2}, {0, D}}},
+ {{{1, 1}, {0, D}, {0, 0}, {2, 2}}},
+ {{{1, 1}, {0, D}, {2, 2}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {D, 0}, {0, 0}}},
+ {{{1, 1}, {2, 2+D}, {3, 3}, {2, 2}}}, // middle-last coincident
+ {{{1, 1}, {2+D, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
+ {{{1, 1}, {1, 1}, {2, 2}, {2+D, 2}}}, // 2 pairs coincident
+ {{{1, 1}, {2, 2}, {1, 1}, {2+D, 2}}},
+ {{{1, 1}, {1, 1+D}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
+ {{{1, 1}, {2+D/2, 2}, {3, 3}, {4, 4}}}, // no coincident (FIXME: N as opposed to N/2 failed)
+ {{{1, 1}, {3, 3}, {2, 2}, {4, 4+D}}},
+ {{{1, 1+D}, {2, 2}, {4, 4}, {3, 3}}},
+ {{{1, 1}, {3, 3}, {4, 4+D}, {2, 2}}},
+ {{{1, 1}, {4, 4}, {2, 2}, {3, 3+D}}},
+ {{{1, 1}, {4, 4}, {3, 3}, {2+G, 2}}}, // INVESTIGATE: why the epsilon is smaller
+ {{{2, 2}, {1, 1}, {3+D, 3}, {4, 4}}},
+ {{{2, 2}, {1+D, 1}, {4, 4}, {3, 3}}},
+ {{{2, 2+D}, {3, 3}, {1, 1}, {4, 4}}},
+ {{{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}}, // INVESTIGATE: why the epsilon is smaller
+ {{{2, 2}, {4+D, 4}, {1, 1}, {3, 3}}},
+ {{{2, 2}, {4, 4}, {3, 3}, {1, 1+D}}},
+};
+
+const size_t lessEpsilonLines_count = sizeof(lessEpsilonLines) / sizeof(lessEpsilonLines[0]);
+
+const SkDCubic negEpsilonLines[] = {
+ {{{0, N}, {0, 0}, {0, 0}, {1, 0}}}, // horizontal
+ {{{1, 0}, {0, 0}, {0, 0}, {0, N}}},
+ {{{1, N}, {2, 0}, {3, 0}, {4, 0}}},
+ {{{N, 0}, {0, 0}, {0, 0}, {0, 1}}}, // vertical
+ {{{0, 1}, {0, 0}, {0, 0}, {N, 0}}},
+ {{{N, 1}, {0, 2}, {0, 3}, {0, 4}}},
+ {{{N, 0}, {0, 0}, {0, 0}, {1, 1}}}, // 3 coincident
+ {{{1, 1}, {0, 0}, {0, 0}, {N, 0}}},
+ {{{0, N}, {0, 0}, {1, 1}, {2, 2}}}, // 2 coincident
+ {{{0, 0}, {1, 1}, {0, N}, {2, 2}}},
+ {{{0, 0}, {1, 1}, {2, 2}, {0, N}}},
+ {{{1, 1}, {0, N}, {0, 0}, {2, 2}}},
+ {{{1, 1}, {0, N}, {2, 2}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {N, 0}, {0, 0}}},
+ {{{1, 1}, {2, 2+N}, {3, 3}, {2, 2}}}, // middle-last coincident
+ {{{1, 1}, {2+N, 2}, {3, 3}, {3, 3}}}, // middle-last coincident
+ {{{1, 1}, {1, 1}, {2, 2}, {2+N, 2}}}, // 2 pairs coincident
+ {{{1, 1}, {2, 2}, {1, 1}, {2+N, 2}}},
+ {{{1, 1}, {1, 1+N}, {3, 3}, {3, 3}}}, // first-middle middle-last coincident
+ {{{1, 1}, {2+N/2, 2}, {3, 3}, {4, 4}}}, // no coincident (FIXME: N as opposed to N/2 failed)
+ {{{1, 1}, {3, 3}, {2, 2}, {4, 4+N}}},
+ {{{1, 1+N}, {2, 2}, {4, 4}, {3, 3}}},
+ {{{1, 1}, {3, 3}, {4, 4+N}, {2, 2}}},
+ {{{1, 1}, {4, 4}, {2, 2}, {3, 3+N}}},
+ {{{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}}, // INVESTIGATE: why the epsilon is smaller
+ {{{2, 2}, {1, 1}, {3+N, 3}, {4, 4}}},
+ {{{2, 2}, {1+N, 1}, {4, 4}, {3, 3}}},
+ {{{2, 2+N}, {3, 3}, {1, 1}, {4, 4}}},
+ {{{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}}, // INVESTIGATE: why the epsilon is smaller
+ {{{2, 2}, {4+N, 4}, {1, 1}, {3, 3}}},
+ {{{2, 2}, {4, 4}, {3, 3}, {1, 1+N}}},
+};
+
+const size_t negEpsilonLines_count = sizeof(negEpsilonLines) / sizeof(negEpsilonLines[0]);
diff --git a/tests/PathOpsCubicIntersectionTestData.h b/tests/PathOpsCubicIntersectionTestData.h
new file mode 100644
index 0000000000..9e7ad7348e
--- /dev/null
+++ b/tests/PathOpsCubicIntersectionTestData.h
@@ -0,0 +1,30 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkPathOpsCubic.h"
+
+extern const SkDCubic pointDegenerates[];
+extern const SkDCubic notPointDegenerates[];
+extern const SkDCubic tests[][2];
+extern SkDCubic hexTests[][2];
+
+extern void convert_testx();
+
+extern const SkDCubic lines[];
+extern const SkDCubic notLines[];
+extern const SkDCubic modEpsilonLines[];
+extern const SkDCubic lessEpsilonLines[];
+extern const SkDCubic negEpsilonLines[];
+
+extern const size_t pointDegenerates_count;
+extern const size_t notPointDegenerates_count;
+extern const size_t tests_count;
+extern const size_t hexTests_count;
+extern const size_t lines_count;
+extern const size_t notLines_count;
+extern const size_t modEpsilonLines_count;
+extern const size_t lessEpsilonLines_count;
+extern const size_t negEpsilonLines_count;
diff --git a/tests/PathOpsCubicLineIntersectionTest.cpp b/tests/PathOpsCubicLineIntersectionTest.cpp
new file mode 100644
index 0000000000..874fff079d
--- /dev/null
+++ b/tests/PathOpsCubicLineIntersectionTest.cpp
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkIntersections.h"
+#include "SkPathOpsCubic.h"
+#include "SkPathOpsLine.h"
+#include "SkReduceOrder.h"
+#include "Test.h"
+
+static struct lineCubic {
+ SkDCubic cubic;
+ SkDLine line;
+} lineCubicTests[] = {
+ {{{{1, 2}, {2, 6}, {2, 0}, {1, 0}}}, {{{1, 0}, {1, 2}}}},
+ {{{{0, 0}, {0, 1}, {0, 1}, {1, 1}}}, {{{0, 1}, {1, 0}}}},
+};
+
+static const size_t lineCubicTests_count = sizeof(lineCubicTests) / sizeof(lineCubicTests[0]);
+
+static void CubicLineIntersectionTest(skiatest::Reporter* reporter) {
+ for (size_t index = 0; index < lineCubicTests_count; ++index) {
+ int iIndex = static_cast<int>(index);
+ const SkDCubic& cubic = lineCubicTests[index].cubic;
+ const SkDLine& line = lineCubicTests[index].line;
+ SkReduceOrder reduce1;
+ SkReduceOrder reduce2;
+ int order1 = reduce1.reduce(cubic, SkReduceOrder::kNo_Quadratics,
+ SkReduceOrder::kFill_Style);
+ int order2 = reduce2.reduce(line);
+ if (order1 < 4) {
+ SkDebugf("[%d] cubic order=%d\n", iIndex, order1);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ if (order2 < 2) {
+ SkDebugf("[%d] line order=%d\n", iIndex, order2);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ if (order1 == 4 && order2 == 2) {
+ SkIntersections i;
+ int roots = i.intersect(cubic, line);
+ for (int pt = 0; pt < roots; ++pt) {
+ double tt1 = i[0][pt];
+ SkDPoint xy1 = cubic.xyAtT(tt1);
+ double tt2 = i[1][pt];
+ SkDPoint xy2 = line.xyAtT(tt2);
+ if (!xy1.approximatelyEqual(xy2)) {
+ SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
+ __FUNCTION__, iIndex, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY);
+ }
+ REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
+ }
+ }
+ }
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsCubicLineIntersection", CubicLineIntersectionTestClass, \
+ CubicLineIntersectionTest)
diff --git a/tests/PathOpsCubicReduceOrderTest.cpp b/tests/PathOpsCubicReduceOrderTest.cpp
new file mode 100644
index 0000000000..25f6b2a475
--- /dev/null
+++ b/tests/PathOpsCubicReduceOrderTest.cpp
@@ -0,0 +1,226 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "PathOpsCubicIntersectionTestData.h"
+#include "PathOpsQuadIntersectionTestData.h"
+#include "SkIntersections.h"
+#include "SkPathOpsRect.h"
+#include "SkReduceOrder.h"
+#include "Test.h"
+
+static bool controls_inside(const SkDCubic& cubic) {
+ return between(cubic[0].fX, cubic[1].fX, cubic[3].fX)
+ && between(cubic[0].fX, cubic[2].fX, cubic[3].fX)
+ && between(cubic[0].fY, cubic[1].fY, cubic[3].fY)
+ && between(cubic[0].fY, cubic[2].fY, cubic[3].fY);
+}
+
+static bool tiny(const SkDCubic& cubic) {
+ int index, minX, maxX, minY, maxY;
+ minX = maxX = minY = maxY = 0;
+ for (index = 1; index < 4; ++index) {
+ if (cubic[minX].fX > cubic[index].fX) {
+ minX = index;
+ }
+ if (cubic[minY].fY > cubic[index].fY) {
+ minY = index;
+ }
+ if (cubic[maxX].fX < cubic[index].fX) {
+ maxX = index;
+ }
+ if (cubic[maxY].fY < cubic[index].fY) {
+ maxY = index;
+ }
+ }
+ return approximately_equal(cubic[maxX].fX, cubic[minX].fX)
+ && approximately_equal(cubic[maxY].fY, cubic[minY].fY);
+}
+
+static void find_tight_bounds(const SkDCubic& cubic, SkDRect& bounds) {
+ SkDCubicPair cubicPair = cubic.chopAt(0.5);
+ if (!tiny(cubicPair.first()) && !controls_inside(cubicPair.first())) {
+ find_tight_bounds(cubicPair.first(), bounds);
+ } else {
+ bounds.add(cubicPair.first()[0]);
+ bounds.add(cubicPair.first()[3]);
+ }
+ if (!tiny(cubicPair.second()) && !controls_inside(cubicPair.second())) {
+ find_tight_bounds(cubicPair.second(), bounds);
+ } else {
+ bounds.add(cubicPair.second()[0]);
+ bounds.add(cubicPair.second()[3]);
+ }
+}
+
+static void CubicReduceOrderTest(skiatest::Reporter* reporter) {
+ size_t index;
+ SkReduceOrder reducer;
+ int order;
+ enum {
+ RunAll,
+ RunPointDegenerates,
+ RunNotPointDegenerates,
+ RunLines,
+ RunNotLines,
+ RunModEpsilonLines,
+ RunLessEpsilonLines,
+ RunNegEpsilonLines,
+ RunQuadraticLines,
+ RunQuadraticPoints,
+ RunQuadraticModLines,
+ RunComputedLines,
+ RunNone
+ } run = RunAll;
+ int firstTestIndex = 0;
+#if 0
+ run = RunComputedLines;
+ firstTestIndex = 18;
+#endif
+ int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates
+ ? firstTestIndex : SK_MaxS32;
+ int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates
+ ? firstTestIndex : SK_MaxS32;
+ int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
+ int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
+ int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstQuadraticPointTest = run == RunAll ? 0 : run == RunQuadraticPoints
+ ? firstTestIndex : SK_MaxS32;
+ int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines
+ ? firstTestIndex : SK_MaxS32;
+
+ for (index = firstPointDegeneratesTest; index < pointDegenerates_count; ++index) {
+ const SkDCubic& cubic = pointDegenerates[index];
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order != 1) {
+ SkDebugf("[%d] pointDegenerates order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstNotPointDegeneratesTest; index < notPointDegenerates_count; ++index) {
+ const SkDCubic& cubic = notPointDegenerates[index];
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order == 1) {
+ SkDebugf("[%d] notPointDegenerates order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstLinesTest; index < lines_count; ++index) {
+ const SkDCubic& cubic = lines[index];
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order != 2) {
+ SkDebugf("[%d] lines order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstNotLinesTest; index < notLines_count; ++index) {
+ const SkDCubic& cubic = notLines[index];
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order == 2) {
+ SkDebugf("[%d] notLines order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstModEpsilonTest; index < modEpsilonLines_count; ++index) {
+ const SkDCubic& cubic = modEpsilonLines[index];
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order == 2) {
+ SkDebugf("[%d] line mod by epsilon order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstLessEpsilonTest; index < lessEpsilonLines_count; ++index) {
+ const SkDCubic& cubic = lessEpsilonLines[index];
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order != 2) {
+ SkDebugf("[%d] line less by epsilon/2 order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstNegEpsilonTest; index < negEpsilonLines_count; ++index) {
+ const SkDCubic& cubic = negEpsilonLines[index];
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order != 2) {
+ SkDebugf("[%d] line neg by epsilon/2 order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstQuadraticPointTest; index < quadraticPoints_count; ++index) {
+ const SkDQuad& quad = quadraticPoints[index];
+ SkDCubic cubic = quad.toCubic();
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order != 1) {
+ SkDebugf("[%d] point quad order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstQuadraticLineTest; index < quadraticLines_count; ++index) {
+ const SkDQuad& quad = quadraticLines[index];
+ SkDCubic cubic = quad.toCubic();
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order != 2) {
+ SkDebugf("[%d] line quad order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ for (index = firstQuadraticModLineTest; index < quadraticModEpsilonLines_count; ++index) {
+ const SkDQuad& quad = quadraticModEpsilonLines[index];
+ SkDCubic cubic = quad.toCubic();
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics, SkReduceOrder::kFill_Style);
+ if (order != 3) {
+ SkDebugf("[%d] line mod quad order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+
+ // test if computed line end points are valid
+ for (index = firstComputedLinesTest; index < lines_count; ++index) {
+ const SkDCubic& cubic = lines[index];
+ bool controlsInside = controls_inside(cubic);
+ order = reducer.reduce(cubic, SkReduceOrder::kAllow_Quadratics,
+ SkReduceOrder::kStroke_Style);
+ if (order == 2 && reducer.fLine[0] == reducer.fLine[1]) {
+ SkDebugf("[%d] line computed ends match order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ if (controlsInside) {
+ if ( (reducer.fLine[0].fX != cubic[0].fX && reducer.fLine[0].fX != cubic[3].fX)
+ || (reducer.fLine[0].fY != cubic[0].fY && reducer.fLine[0].fY != cubic[3].fY)
+ || (reducer.fLine[1].fX != cubic[0].fX && reducer.fLine[1].fX != cubic[3].fX)
+ || (reducer.fLine[1].fY != cubic[0].fY && reducer.fLine[1].fY != cubic[3].fY)) {
+ SkDebugf("[%d] line computed ends order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ } else {
+ // binary search for extrema, compare against actual results
+ // while a control point is outside of bounding box formed by end points, split
+ SkDRect bounds = {DBL_MAX, DBL_MAX, -DBL_MAX, -DBL_MAX};
+ find_tight_bounds(cubic, bounds);
+ if ( (!AlmostEqualUlps(reducer.fLine[0].fX, bounds.fLeft)
+ && !AlmostEqualUlps(reducer.fLine[0].fX, bounds.fRight))
+ || (!AlmostEqualUlps(reducer.fLine[0].fY, bounds.fTop)
+ && !AlmostEqualUlps(reducer.fLine[0].fY, bounds.fBottom))
+ || (!AlmostEqualUlps(reducer.fLine[1].fX, bounds.fLeft)
+ && !AlmostEqualUlps(reducer.fLine[1].fX, bounds.fRight))
+ || (!AlmostEqualUlps(reducer.fLine[1].fY, bounds.fTop)
+ && !AlmostEqualUlps(reducer.fLine[1].fY, bounds.fBottom))) {
+ SkDebugf("[%d] line computed tight bounds order=%d\n", static_cast<int>(index), order);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ }
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsReduceOrderCubic", ReduceOrderCubicTestClass, CubicReduceOrderTest)
diff --git a/tests/PathOpsCubicToQuadsTest.cpp b/tests/PathOpsCubicToQuadsTest.cpp
new file mode 100644
index 0000000000..4d332fe42c
--- /dev/null
+++ b/tests/PathOpsCubicToQuadsTest.cpp
@@ -0,0 +1,202 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "PathOpsCubicIntersectionTestData.h"
+#include "PathOpsQuadIntersectionTestData.h"
+#include "PathOpsTestCommon.h"
+#include "SkGeometry.h"
+#include "SkIntersections.h"
+#include "SkPathOpsRect.h"
+#include "SkReduceOrder.h"
+#include "Test.h"
+
+static void test(skiatest::Reporter* reporter, const SkDCubic* cubics, const char* name,
+ int firstTest, size_t testCount) {
+ for (size_t index = firstTest; index < testCount; ++index) {
+ const SkDCubic& cubic = cubics[index];
+ double precision = cubic.calcPrecision();
+ SkTDArray<SkDQuad> quads;
+ CubicToQuads(cubic, precision, quads);
+ if (quads.count() != 1) {
+ SkDebugf("%s [%d] cubic to quadratics failed count=%d\n", name, static_cast<int>(index),
+ quads.count());
+ }
+ REPORTER_ASSERT(reporter, quads.count() == 1);
+ }
+}
+
+static void test(skiatest::Reporter* reporter, const SkDQuad* quadTests, const char* name,
+ int firstTest, size_t testCount) {
+ for (size_t index = firstTest; index < testCount; ++index) {
+ const SkDQuad& quad = quadTests[index];
+ SkDCubic cubic = quad.toCubic();
+ double precision = cubic.calcPrecision();
+ SkTDArray<SkDQuad> quads;
+ CubicToQuads(cubic, precision, quads);
+ if (quads.count() != 1) {
+ SkDebugf("%s [%d] cubic to quadratics failed count=%d\n", name, static_cast<int>(index),
+ quads.count());
+ }
+ REPORTER_ASSERT(reporter, quads.count() == 1);
+ }
+}
+
+static void testC(skiatest::Reporter* reporter, const SkDCubic* cubics, const char* name,
+ int firstTest, size_t testCount) {
+ // test if computed line end points are valid
+ for (size_t index = firstTest; index < testCount; ++index) {
+ const SkDCubic& cubic = cubics[index];
+ double precision = cubic.calcPrecision();
+ SkTDArray<SkDQuad> quads;
+ CubicToQuads(cubic, precision, quads);
+ if (!AlmostEqualUlps(cubic[0].fX, quads[0][0].fX)
+ || !AlmostEqualUlps(cubic[0].fY, quads[0][0].fY)) {
+ SkDebugf("[%d] unmatched start\n", static_cast<int>(index));
+ REPORTER_ASSERT(reporter, 0);
+ }
+ int last = quads.count() - 1;
+ if (!AlmostEqualUlps(cubic[3].fX, quads[last][2].fX)
+ || !AlmostEqualUlps(cubic[3].fY, quads[last][2].fY)) {
+ SkDebugf("[%d] unmatched end\n", static_cast<int>(index));
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+}
+
+static void testC(skiatest::Reporter* reporter, const SkDCubic(* cubics)[2], const char* name,
+ int firstTest, size_t testCount) {
+ for (size_t index = firstTest; index < testCount; ++index) {
+ for (int idx2 = 0; idx2 < 2; ++idx2) {
+ const SkDCubic& cubic = cubics[index][idx2];
+ double precision = cubic.calcPrecision();
+ SkTDArray<SkDQuad> quads;
+ CubicToQuads(cubic, precision, quads);
+ if (!AlmostEqualUlps(cubic[0].fX, quads[0][0].fX)
+ || !AlmostEqualUlps(cubic[0].fY, quads[0][0].fY)) {
+ SkDebugf("[%d][%d] unmatched start\n", static_cast<int>(index), idx2);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ int last = quads.count() - 1;
+ if (!AlmostEqualUlps(cubic[3].fX, quads[last][2].fX)
+ || !AlmostEqualUlps(cubic[3].fY, quads[last][2].fY)) {
+ SkDebugf("[%d][%d] unmatched end\n", static_cast<int>(index), idx2);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ }
+}
+
+static void CubicToQuads_Test(skiatest::Reporter* reporter) {
+ enum {
+ RunAll,
+ RunPointDegenerates,
+ RunNotPointDegenerates,
+ RunLines,
+ RunNotLines,
+ RunModEpsilonLines,
+ RunLessEpsilonLines,
+ RunNegEpsilonLines,
+ RunQuadraticLines,
+ RunQuadraticModLines,
+ RunComputedLines,
+ RunComputedTests,
+ RunNone
+ } run = RunAll;
+ int firstTestIndex = 0;
+#if 0
+ run = RunComputedLines;
+ firstTestIndex = 18;
+#endif
+ int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates
+ ? firstTestIndex : SK_MaxS32;
+ int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates
+ ? firstTestIndex : SK_MaxS32;
+ int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32;
+ int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32;
+ int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines
+ ? firstTestIndex : SK_MaxS32;
+ int firstComputedCubicsTest = run == RunAll ? 0 : run == RunComputedTests
+ ? firstTestIndex : SK_MaxS32;
+
+ test(reporter, pointDegenerates, "pointDegenerates", firstPointDegeneratesTest,
+ pointDegenerates_count);
+ testC(reporter, notPointDegenerates, "notPointDegenerates", firstNotPointDegeneratesTest,
+ notPointDegenerates_count);
+ test(reporter, lines, "lines", firstLinesTest, lines_count);
+ testC(reporter, notLines, "notLines", firstNotLinesTest, notLines_count);
+ testC(reporter, modEpsilonLines, "modEpsilonLines", firstModEpsilonTest, modEpsilonLines_count);
+ test(reporter, lessEpsilonLines, "lessEpsilonLines", firstLessEpsilonTest,
+ lessEpsilonLines_count);
+ test(reporter, negEpsilonLines, "negEpsilonLines", firstNegEpsilonTest, negEpsilonLines_count);
+ test(reporter, quadraticLines, "quadraticLines", firstQuadraticLineTest, quadraticLines_count);
+ test(reporter, quadraticModEpsilonLines, "quadraticModEpsilonLines", firstQuadraticModLineTest,
+ quadraticModEpsilonLines_count);
+ testC(reporter, lines, "computed lines", firstComputedLinesTest, lines_count);
+ testC(reporter, tests, "computed tests", firstComputedCubicsTest, tests_count);
+}
+
+static SkDCubic locals[] = {
+ {{{0, 1}, {1.9274705288631189e-19, 1.0000000000000002},
+ {0.0017190297609673323, 0.99828097023903239},
+ {0.0053709083094631276, 0.99505672974365911}}},
+ {{{14.5975863, 41.632436}, {16.3518929, 26.2639684}, {18.5165519, 7.68775139},
+ {8.03767257, 89.1628526}}},
+ {{{69.7292014, 38.6877352}, {24.7648688, 23.1501713}, {84.9283191, 90.2588441},
+ {80.392774, 61.3533852}}},
+ {{{60.776536520932126, 71.249307306133829}, {87.107894191103014, 22.377669868235323},
+ {1.4974754310666936, 68.069569937917208}, {45.261946574441133, 17.536076632112298}}},
+};
+
+static size_t localsCount = sizeof(locals) / sizeof(locals[0]);
+
+#define DEBUG_CRASH 0
+#define TEST_AVERAGE_END_POINTS 0 // must take const off to test
+extern const bool AVERAGE_END_POINTS;
+
+static void oneOff(skiatest::Reporter* reporter, size_t x) {
+ const SkDCubic& cubic = locals[x];
+ const SkPoint skcubic[4] = {
+ {static_cast<float>(cubic[0].fX), static_cast<float>(cubic[0].fY)},
+ {static_cast<float>(cubic[1].fX), static_cast<float>(cubic[1].fY)},
+ {static_cast<float>(cubic[2].fX), static_cast<float>(cubic[2].fY)},
+ {static_cast<float>(cubic[3].fX), static_cast<float>(cubic[3].fY)}};
+ SkScalar skinflect[2];
+ int skin = SkFindCubicInflections(skcubic, skinflect);
+ if (false) SkDebugf("%s %d %1.9g\n", __FUNCTION__, skin, skinflect[0]);
+ SkTDArray<SkDQuad> quads;
+ double precision = cubic.calcPrecision();
+ CubicToQuads(cubic, precision, quads);
+ if (false) SkDebugf("%s quads=%d\n", __FUNCTION__, quads.count());
+}
+
+static void CubicsToQuadratics_OneOffTests(skiatest::Reporter* reporter) {
+ for (size_t x = 0; x < localsCount; ++x) {
+ oneOff(reporter, x);
+ }
+}
+
+static void CubicsToQuadratics_OneOffTest(skiatest::Reporter* reporter) {
+ oneOff(reporter, 0);
+}
+
+static void TestCubicToQuads(skiatest::Reporter* reporter) {
+ CubicToQuads_Test(reporter);
+ CubicsToQuadratics_OneOffTest(reporter);
+ CubicsToQuadratics_OneOffTests(reporter);
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsCubicToQuads", PathOpsCubicToQuads, TestCubicToQuads)
diff --git a/tests/PathOpsLineIntersectionTest.cpp b/tests/PathOpsLineIntersectionTest.cpp
new file mode 100644
index 0000000000..5ab336e55f
--- /dev/null
+++ b/tests/PathOpsLineIntersectionTest.cpp
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkIntersections.h"
+#include "SkPathOpsLine.h"
+#include "Test.h"
+
+// FIXME: add tests for intersecting, non-intersecting, degenerate, coincident
+static const SkDLine tests[][2] = {
+ {{{{0, 0}, {1, 0}}}, {{{1, 0}, {0, 0}}}},
+ {{{{0, 0}, {0, 0}}}, {{{0, 0}, {1, 0}}}},
+ {{{{0, 1}, {0, 1}}}, {{{0, 0}, {0, 2}}}},
+ {{{{0, 0}, {1, 0}}}, {{{0, 0}, {2, 0}}}},
+ {{{{1, 1}, {2, 2}}}, {{{0, 0}, {3, 3}}}},
+ {{{{166.86950047022856, 112.69654129527828}, {166.86948801592692, 112.69655741235339}}},
+ {{{166.86960700313026, 112.6965477747386}, {166.86925794355412, 112.69656471103423}}}}
+};
+
+static const size_t tests_count = sizeof(tests) / sizeof(tests[0]);
+
+static const SkDLine noIntersect[][2] = {
+ {{{{0, 0}, {1, 0}}}, {{{3, 0}, {2, 0}}}},
+ {{{{0, 0}, {0, 0}}}, {{{1, 0}, {2, 0}}}},
+ {{{{0, 1}, {0, 1}}}, {{{0, 3}, {0, 2}}}},
+ {{{{0, 0}, {1, 0}}}, {{{2, 0}, {3, 0}}}},
+ {{{{1, 1}, {2, 2}}}, {{{4, 4}, {3, 3}}}},
+};
+
+static const size_t noIntersect_count = sizeof(noIntersect) / sizeof(noIntersect[0]);
+
+static void TestLineIntersection(skiatest::Reporter* reporter) {
+ size_t index;
+ for (index = 0; index < tests_count; ++index) {
+ const SkDLine& line1 = tests[index][0];
+ const SkDLine& line2 = tests[index][1];
+ SkIntersections ts;
+ int pts = ts.intersect(line1, line2);
+ REPORTER_ASSERT(reporter, pts);
+ for (int i = 0; i < pts; ++i) {
+ SkDPoint result1 = line1.xyAtT(ts[0][i]);
+ SkDPoint result2 = line2.xyAtT(ts[1][i]);
+ if (!result1.approximatelyEqual(result2)) {
+ REPORTER_ASSERT(reporter, pts != 1);
+ result2 = line2.xyAtT(ts[1][i ^ 1]);
+ REPORTER_ASSERT(reporter, result1.approximatelyEqual(result2));
+ }
+ }
+ }
+ for (index = 0; index < noIntersect_count; ++index) {
+ const SkDLine& line1 = noIntersect[index][0];
+ const SkDLine& line2 = noIntersect[index][1];
+ SkIntersections ts;
+ int pts = ts.intersect(line1, line2);
+ REPORTER_ASSERT(reporter, !pts); }
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsLineIntersection", LineIntersectionTestClass, TestLineIntersection)
diff --git a/tests/PathOpsLineParametetersTest.cpp b/tests/PathOpsLineParametetersTest.cpp
new file mode 100644
index 0000000000..2dad1b2e2c
--- /dev/null
+++ b/tests/PathOpsLineParametetersTest.cpp
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkLineParameters.h"
+#include "Test.h"
+
+// tests to verify that distance calculations are coded correctly
+static const SkDCubic tests[] = {
+ {{{0, 0}, {1, 1}, {2, 2}, {0, 3}}},
+ {{{0, 0}, {1, 1}, {2, 2}, {3, 0}}},
+ {{{0, 0}, {5, 0}, {-2, 4}, {3, 4}}},
+ {{{0, 2}, {1, 0}, {2, 0}, {3, 0}}},
+ {{{0, .2}, {1, 0}, {2, 0}, {3, 0}}},
+ {{{0, .02}, {1, 0}, {2, 0}, {3, 0}}},
+ {{{0, .002}, {1, 0}, {2, 0}, {3, 0}}},
+ {{{0, .0002}, {1, 0}, {2, 0}, {3, 0}}},
+ {{{0, .00002}, {1, 0}, {2, 0}, {3, 0}}},
+ {{{0, FLT_EPSILON * 2}, {1, 0}, {2, 0}, {3, 0}}},
+};
+
+static const double answers[][2] = {
+ {1, 2},
+ {1, 2},
+ {4, 4},
+ {1.1094003924, 0.5547001962},
+ {0.133038021, 0.06651901052},
+ {0.0133330370, 0.006666518523},
+ {0.001333333037, 0.0006666665185},
+ {0.000133333333, 6.666666652e-05},
+ {1.333333333e-05, 6.666666667e-06},
+ {1.5894571940104115e-07, 7.9472859700520577e-08},
+};
+
+static const size_t tests_count = sizeof(tests) / sizeof(tests[0]);
+
+static void LineParameterTest(skiatest::Reporter* reporter) {
+ for (size_t index = 0; index < tests_count; ++index) {
+ SkLineParameters lineParameters;
+ const SkDCubic& cubic = tests[index];
+ lineParameters.cubicEndPoints(cubic);
+ double denormalizedDistance[2];
+ denormalizedDistance[0] = lineParameters.controlPtDistance(cubic, 1);
+ denormalizedDistance[1] = lineParameters.controlPtDistance(cubic, 2);
+ double normalSquared = lineParameters.normalSquared();
+ size_t inner;
+ for (inner = 0; inner < 2; ++inner) {
+ double distSq = denormalizedDistance[inner];
+ distSq *= distSq;
+ double answersSq = answers[index][inner];
+ answersSq *= answersSq;
+ if (AlmostEqualUlps(distSq, normalSquared * answersSq)) {
+ continue;
+ }
+ SkDebugf("%s [%d,%d] denormalizedDistance:%g != answer:%g"
+ " distSq:%g answerSq:%g normalSquared:%g\n",
+ __FUNCTION__, static_cast<int>(index), (int)inner,
+ denormalizedDistance[inner], answers[index][inner],
+ distSq, answersSq, normalSquared);
+ }
+ lineParameters.normalize();
+ double normalizedDistance[2];
+ normalizedDistance[0] = lineParameters.controlPtDistance(cubic, 1);
+ normalizedDistance[1] = lineParameters.controlPtDistance(cubic, 2);
+ for (inner = 0; inner < 2; ++inner) {
+ if (AlmostEqualUlps(fabs(normalizedDistance[inner]), answers[index][inner])) {
+ continue;
+ }
+ SkDebugf("%s [%d,%d] normalizedDistance:%1.10g != answer:%g\n",
+ __FUNCTION__, static_cast<int>(index), (int)inner,
+ normalizedDistance[inner], answers[index][inner]);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsLineParameters", PathOpsLineParametersClass, LineParameterTest)
diff --git a/tests/PathOpsQuadIntersectionTest.cpp b/tests/PathOpsQuadIntersectionTest.cpp
new file mode 100644
index 0000000000..437796d2fc
--- /dev/null
+++ b/tests/PathOpsQuadIntersectionTest.cpp
@@ -0,0 +1,468 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "PathOpsQuadIntersectionTestData.h"
+#include "SkIntersections.h"
+#include "SkPathOpsRect.h"
+#include "SkReduceOrder.h"
+#include "Test.h"
+
+static void standardTestCases(skiatest::Reporter* reporter) {
+ bool showSkipped = false;
+ for (size_t index = 0; index < quadraticTests_count; ++index) {
+ const SkDQuad& quad1 = quadraticTests[index][0];
+ const SkDQuad& quad2 = quadraticTests[index][1];
+ SkReduceOrder reduce1, reduce2;
+ int order1 = reduce1.reduce(quad1, SkReduceOrder::kFill_Style);
+ int order2 = reduce2.reduce(quad2, SkReduceOrder::kFill_Style);
+ if (order1 < 3) {
+ if (showSkipped) {
+ SkDebugf("[%d] quad1 order=%d\n", static_cast<int>(index), order1);
+ }
+ }
+ if (order2 < 3) {
+ if (showSkipped) {
+ SkDebugf("[%d] quad2 order=%d\n", static_cast<int>(index), order2);
+ }
+ }
+ if (order1 == 3 && order2 == 3) {
+ SkIntersections intersections;
+ intersections.intersect(quad1, quad2);
+ if (intersections.used() > 0) {
+ for (int pt = 0; pt < intersections.used(); ++pt) {
+ double tt1 = intersections[0][pt];
+ SkDPoint xy1 = quad1.xyAtT(tt1);
+ double tt2 = intersections[1][pt];
+ SkDPoint xy2 = quad2.xyAtT(tt2);
+ if (!xy1.approximatelyEqual(xy2)) {
+ SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
+ __FUNCTION__, static_cast<int>(index), pt, tt1, xy1.fX, xy1.fY,
+ tt2, xy2.fX, xy2.fY);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ }
+ }
+ }
+}
+
+static const SkDQuad testSet[] = {
+ {{{3.0774019473063863, 3.35198509346713}, {3.0757503498668397, 3.327320623945933},
+ {3.0744102085015879, 3.3025879417907196}}},
+ {{{3.053913680774329, 3.3310471586283938}, {3.0758730889691694, 3.3273466070370152},
+ {3.0975671980059394, 3.3235031316554351}}},
+
+ {{{3.39068129, 4.44939202}, {3.03659239, 3.81843234}, {3.06844529, 3.02100922}}},
+ {{{2.10714698, 3.44196686}, {3.12180288, 3.38575704}, {3.75968569, 3.1281838}}},
+
+ {{{2.74792918, 4.77711896}, {2.82236867, 4.23882547}, {2.82848144, 3.63729341}}},
+ {{{2.62772567, 3.64823958}, {3.46652495, 3.64258364}, {4.1425079, 3.48623815}}},
+
+ {{{1.34375, 2.03125}, {2.2734375, 2.6640625}, {3.25, 3.25}}},
+ {{{3.96875, 4.65625}, {3.3359375, 3.7265625}, {2.75, 2.75}}},
+
+ {{{0, 1}, {0.324417544, 2.27953848}, {0.664376547, 2.58940267}}},
+ {{{1, 2}, {0.62109375, 2.70703125}, {0.640625, 2.546875}}},
+
+ {{{1, 2}, {0.984375, 2.3359375}, {1.0625, 2.15625}}},
+ {{{0, 1}, {0.983539095, 2.30041152}, {1.47325103, 2.61316872}}},
+
+ {{{4.09011926, 2.20971038}, {4.74608133, 1.9335932}, {5.02469918, 2.00694987}}},
+ {{{2.79472921, 1.73568666}, {3.36246373, 1.21251209}, {5, 2}}},
+
+ {{{1.80814127, 2.41537795}, {2.23475077, 2.05922313}, {3.16529668, 1.98358763}}},
+ {{{2.16505631, 2.55782454}, {2.40541285, 2.02193091}, {2.99836023, 1.68247638}}},
+
+ {{{3, 1.875}, {3.375, 1.54296875}, {3.375, 1.421875}}},
+ {{{3.375, 1.421875}, {3.3749999999999996, 1.3007812499999998}, {3, 2}}},
+
+ {{{3.34, 8.98}, {2.83363281, 9.4265625}, {2.83796875, 9.363125}}},
+ {{{2.83796875, 9.363125}, {2.84230469, 9.2996875}, {3.17875, 9.1725}}},
+
+ {{{2.7279999999999998, 3.024}, {2.5600000000000005, 2.5600000000000005},
+ {2.1520000000000001, 1.8560000000000001}}},
+ {{{0.66666666666666652, 1.1481481481481481}, {1.3333333333333326, 1.3333333333333335},
+ {2.6666666666666665, 2.1851851851851851}}},
+
+ {{{2.728, 3.024}, {2.56, 2.56}, {2.152, 1.856}}},
+ {{{0.666666667, 1.14814815}, {1.33333333, 1.33333333}, {2.66666667, 2.18518519}}},
+
+ {{{0.875, 1.5}, {1.03125, 1.11022302e-16}, {1, 0}}},
+ {{{0.875, 0.859375}, {1.6875, 0.73046875}, {2.5, 0.625}}},
+
+ {{{1.64451042, 0.0942001592}, {1.53635465, 0.00152863961}, {1, 0}}},
+ {{{1.27672209, 0.15}, {1.32143477, 9.25185854e-17}, {1, 0}}},
+
+ {{{0, 0}, {0.51851851851851849, 1.0185185185185186}, {1.2592592592592591, 1.9259259259259258}}},
+ {{{1.2592592592592593, 1.9259259259259265}, {0.51851851851851893, 1.0185185185185195}, {0, 0}}},
+
+ {{{1.93281168, 2.58856757}, {2.38543691, 2.7096125}, {2.51967352, 2.34531784}}},
+ {{{2.51967352, 2.34531784}, {2.65263731, 2.00639194}, {3.1212119, 1.98608967}}},
+ {{{2.09544533, 2.51981963}, {2.33331524, 2.25252128}, {2.92003302, 2.39442311}}},
+
+ {{{0.924337655, 1.94072717}, {1.25185043, 1.52836494}, {1.71793901, 1.06149951}}},
+ {{{0.940798831, 1.67439357}, {1.25988251, 1.39778567}, {1.71791672, 1.06650313}}},
+
+ {{{0.924337655, 1.94072717}, {1.39158994, 1.32418496}, {2.14967426, 0.687365435}}},
+ {{{0.940798831, 1.67439357}, {1.48941875, 1.16280321}, {2.47884711, 0.60465921}}},
+
+ {{{1.7465749139282332, 1.9930452039527999}, {1.8320006564080331, 1.859481345189089},
+ {1.8731035127758437, 1.6344055934266613}}},
+ {{{1.8731035127758437, 1.6344055934266613}, {1.89928170345231, 1.5006405518943067},
+ {1.9223833226085514, 1.3495796165215643}}},
+ {{{1.74657491, 1.9930452}, {1.87407679, 1.76762853}, {1.92238332, 1.34957962}}},
+ {{{0.60797907, 1.68776977}, {1.0447864, 1.50810914}, {1.87464474, 1.63655092}}},
+ {{{1.87464474, 1.63655092}, {2.70450308, 1.76499271}, {4, 3}}},
+
+ {{{1.2071879545809394, 0.82163474041730045}, {1.1534203513372994, 0.52790870069930229},
+ {1.0880000000000001, 0.29599999999999982}}}, //t=0.63155333662549329,0.80000000000000004
+ {{{0.33333333333333326, 0.81481481481481488}, {0.63395173631977997, 0.68744136726313931},
+ {1.205684411948591, 0.81344322326274499}}},
+ {{{0.33333333333333326, 0.81481481481481488}, {0.63396444791444551, 0.68743368362444768},
+ {1.205732763658403, 0.81345617746834109}}}, //t=0.33333333333333331, 0.63396444791444551
+ {{{1.205684411948591, 0.81344322326274499}, {1.2057085875611198, 0.81344969999329253},
+ {1.205732763658403, 0.81345617746834109}}},
+
+ {{{1.20718795, 0.82163474}, {1.15342035, 0.527908701}, {1.088, 0.296}}},
+ {{{1.20568441, 0.813443223}, {1.20570859, 0.8134497}, {1.20573276, 0.813456177}}},
+
+ {{{41.5072916, 87.1234036}, {28.2747836, 80.9545395}, {23.5780771, 69.3344126}}},
+ {{{72.9633878, 95.6593007}, {42.7738746, 88.4730382}, {31.1932785, 80.2458029}}},
+
+ {{{31.1663962, 54.7302484}, {31.1662882, 54.7301074}, {31.1663969, 54.7302485}}},
+ {{{26.0404936, 45.4260361}, {27.7887523, 33.1863051}, {40.8833242, 26.0301855}}},
+
+ {{{29.9404074, 49.1672596}, {44.3131071, 45.3915253}, {58.1067559, 59.5061814}}},
+ {{{72.6510251, 64.2972928}, {53.6989659, 60.1862397}, {35.2053722, 44.8391126}}},
+
+ {{{52.14807018377202, 65.012420045148644}, {44.778669050208237, 66.315562705604378},
+ {51.619118408823567, 63.787827046262684}}},
+ {{{30.004993234763383, 93.921296668202288}, {53.384822003076991, 60.732180341802753},
+ {58.652998934338584, 43.111073088306185}}},
+
+ {{{80.897794748143198, 49.236332042718459}, {81.082078218891212, 64.066749904488631},
+ {69.972305057149981, 72.968595519850993}}},
+ {{{72.503745601281395, 32.952320736577882}, {88.030880716061645, 38.137194847810164},
+ {73.193774825517906, 67.773492479591397}}},
+
+ {{{67.426548091427676, 37.993772624988935}, {51.129513170665035, 57.542281234563646},
+ {44.594748190899189, 65.644267382683879}}},
+ {{{61.336508189019057, 82.693132843213675}, {54.825078921449354, 71.663932799212432},
+ {47.727444217558926, 61.4049645128392}}},
+
+ {{{67.4265481, 37.9937726}, {51.1295132, 57.5422812}, {44.5947482, 65.6442674}}},
+ {{{61.3365082, 82.6931328}, {54.8250789, 71.6639328}, {47.7274442, 61.4049645}}},
+
+ {{{53.774852327053594, 53.318060789841951}, {45.787877803416805, 51.393492026284981},
+ {46.703936967162392, 53.06860709822206}}},
+ {{{46.703936967162392, 53.06860709822206}, {47.619996130907957, 54.74372217015916},
+ {53.020051653535361, 48.633140968832024}}},
+
+ {{{50.934805397717923, 51.52391952648901}, {56.803308902971423, 44.246234610627596},
+ {69.776888596721406, 40.166645096692555}}},
+ {{{50.230212796400401, 38.386469101526998}, {49.855620812184917, 38.818990392153609},
+ {56.356567496227363, 47.229909093319407}}},
+
+ {{{36.148792695174222, 70.336952793070424}, {36.141613037691357, 70.711654739870085},
+ {36.154708826402597, 71.088492662905836}}},
+ {{{35.216235592661825, 70.580199617313212}, {36.244476835123969, 71.010897787304074},
+ {37.230244263238326, 71.423156953613102}}},
+
+ // this pair is nearly coincident, and causes the quartic code to produce bad
+ // data. Mathematica doesn't think they touch. Graphically, I can't tell.
+ // it may not be so bad to pretend that they don't touch, if I can detect that
+ {{{369.848602, 145.680267}, {382.360413, 121.298294}, {406.207703, 121.298294}}},
+ {{{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}}},
+
+ {{{33.567436351153468, 62.336347586395924}, {35.200980274619084, 65.038561460144479},
+ {36.479571811084995, 67.632178905412445}}},
+ {{{41.349524945572696, 67.886658677862641}, {39.125562529359087, 67.429772735149214},
+ {35.600314083992416, 66.705372160552685}}},
+
+ {{{67.25299631583178, 21.109080184767524}, {43.617595267398613, 33.658034168577529},
+ {33.38371819435676, 44.214192553988745}}},
+ {{{40.476838859398541, 39.543209911285999}, {36.701186108431131, 34.8817994016458},
+ {30.102144288878023, 26.739063172945315}}},
+
+ {{{25.367434474345036, 50.4712103169743}, {17.865013304933097, 37.356741010559439},
+ {16.818988838905465, 37.682915484123129}}},
+ {{{16.818988838905465, 37.682915484123129}, {15.772964372877833, 38.009089957686811},
+ {20.624104547604965, 41.825131596683121}}},
+
+ {{{26.440225044088567, 79.695009812848298}, {26.085525979582247, 83.717928354134784},
+ {27.075079976297072, 84.820633667838905}}},
+ {{{27.075079976297072, 84.820633667838905}, {28.276546859574015, 85.988574184029034},
+ {25.649263209500006, 87.166762066617025}}},
+
+ {{{34.879150914024962, 83.862726601601125}, {35.095810134304429, 83.693473210169543},
+ {35.359284111931586, 83.488069234177502}}},
+ {{{54.503204203015471, 76.094098492518242}, {51.366889541918894, 71.609856061299155},
+ {46.53086955445437, 69.949863036494207}}},
+
+ {{{0, 0}, {1, 0}, {0, 3}}},
+ {{{1, 0}, {0, 1}, {1, 1}}},
+ {{{369.961151, 137.980698}, {383.970093, 121.298294}, {406.213287, 121.298294}}},
+ {{{353.2948, 194.351074}, {353.2948, 173.767563}, {364.167572, 160.819855}}},
+ {{{360.416077, 166.795715}, {370.126831, 147.872162}, {388.635406, 147.872162}}},
+ {{{406.236359, 121.254936}, {409.445679, 121.254936}, {412.975952, 121.789818}}},
+ {{{406.235992, 121.254936}, {425.705902, 121.254936}, {439.71994, 137.087616}}},
+
+ {{{369.8543701171875, 145.66734313964844}, {382.36788940429688, 121.28203582763672},
+ {406.21844482421875, 121.28203582763672}}},
+ {{{369.96469116210938, 137.96672058105469}, {383.97555541992188, 121.28203582763672},
+ {406.2218017578125, 121.28203582763672}}},
+
+ {{{369.962311, 137.976044}, {383.971893, 121.29287}, {406.216125, 121.29287}}},
+
+ {{{400.121704, 149.468719}, {391.949493, 161.037186}, {391.949493, 181.202423}}},
+ {{{391.946747, 181.839218}, {391.946747, 155.62442}, {406.115479, 138.855438}}},
+ {{{360.048828125, 229.2578125}, {360.048828125, 224.4140625}, {362.607421875, 221.3671875}}},
+ {{{362.607421875, 221.3671875}, {365.166015625, 218.3203125}, {369.228515625, 218.3203125}}},
+ {{{8, 8}, {10, 10}, {8, -10}}},
+ {{{8, 8}, {12, 12}, {14, 4}}},
+ {{{8, 8}, {9, 9}, {10, 8}}}
+};
+
+const size_t testSetCount = sizeof(testSet) / sizeof(testSet[0]);
+
+static void oneOffTest1(skiatest::Reporter* reporter, size_t outer, size_t inner) {
+ const SkDQuad& quad1 = testSet[outer];
+ const SkDQuad& quad2 = testSet[inner];
+ SkIntersections intersections2;
+ intersections2.intersect(quad1, quad2);
+ for (int pt = 0; pt < intersections2.used(); ++pt) {
+ double tt1 = intersections2[0][pt];
+ SkDPoint xy1 = quad1.xyAtT(tt1);
+ double tt2 = intersections2[1][pt];
+ SkDPoint xy2 = quad2.xyAtT(tt2);
+ if (!xy1.approximatelyEqual(xy2)) {
+ SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n",
+ __FUNCTION__, static_cast<int>(outer), static_cast<int>(inner),
+ tt1, xy1.fX, xy1.fY, tt2, xy2.fX, xy2.fY);
+ REPORTER_ASSERT(reporter, 0);
+ }
+#if ONE_OFF_DEBUG
+ SkDebugf("%s [%d][%d] t1=%1.9g (%1.9g, %1.9g) t2=%1.9g\n", __FUNCTION__,
+ outer, inner, tt1, xy1.fX, xy1.fY, tt2);
+#endif
+ }
+}
+
+static void QuadraticIntersection_OneOffTest(skiatest::Reporter* reporter) {
+ oneOffTest1(reporter, 0, 1);
+ oneOffTest1(reporter, 1, 0);
+}
+
+static void oneOffTests(skiatest::Reporter* reporter) {
+ for (size_t outer = 0; outer < testSetCount - 1; ++outer) {
+ for (size_t inner = outer + 1; inner < testSetCount; ++inner) {
+ oneOffTest1(reporter, outer, inner);
+ }
+ }
+}
+
+static const SkDQuad coincidentTestSet[] = {
+ {{{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}}},
+ {{{369.850525, 145.675964}, {382.362915, 121.29287}, {406.211273, 121.29287}}},
+ {{{8, 8}, {10, 10}, {8, -10}}},
+ {{{8, -10}, {10, 10}, {8, 8}}},
+};
+
+const size_t coincidentTestSetCount = sizeof(coincidentTestSet) / sizeof(coincidentTestSet[0]);
+
+static void coincidentTest(skiatest::Reporter* reporter) {
+ for (size_t testIndex = 0; testIndex < coincidentTestSetCount - 1; testIndex += 2) {
+ const SkDQuad& quad1 = coincidentTestSet[testIndex];
+ const SkDQuad& quad2 = coincidentTestSet[testIndex + 1];
+ SkIntersections intersections2;
+ intersections2.intersect(quad1, quad2);
+ REPORTER_ASSERT(reporter, intersections2.coincidentUsed() == 2);
+ REPORTER_ASSERT(reporter, intersections2.used() == 2);
+ for (int pt = 0; pt < intersections2.coincidentUsed(); ++pt) {
+ double tt1 = intersections2[0][pt];
+ double tt2 = intersections2[1][pt];
+ REPORTER_ASSERT(reporter, approximately_equal(1, tt1) || approximately_zero(tt1));
+ REPORTER_ASSERT(reporter, approximately_equal(1, tt2) || approximately_zero(tt2));
+ }
+ }
+}
+
+static int floatSign(double x) {
+ return x < 0 ? -1 : x > 0 ? 1 : 0;
+}
+
+static const SkDQuad pointFinderTestSet[] = {
+ //>=0.633974464 0.633974846 <=
+{{{1.2071879545809394, 0.82163474041730045}, {1.1534203513372994, 0.52790870069930229},
+ {1.0880000000000001, 0.29599999999999982}}}, //t=0.63155333662549329, 0.80000000000000004
+{{{1.2071879545809394, 0.82163474041730045}, {1.2065040319428038, 0.81766753259119995},
+ {1.2058123269101506, 0.81370135061854221}}}, //t=0.63155333662549329, 0.6339049773632347
+{{{1.2058123269101506, 0.81370135061854221}, {1.152376363978022, 0.5244097415381026},
+ {1.0880000000000001, 0.29599999999999982}}}, //t=0.6339049773632347, 0.80000000000000004
+ //>=0.633974083 0.633975227 <=
+{{{0.33333333333333326, 0.81481481481481488}, {0.63395173631977997, 0.68744136726313931},
+ {1.205684411948591, 0.81344322326274499}}}, //t=0.33333333333333331, 0.63395173631977986
+{{{0.33333333333333326, 0.81481481481481488}, {0.63396444791444551, 0.68743368362444768},
+ {1.205732763658403, 0.81345617746834109}}}, //t=0.33333333333333331, 0.63396444791444551
+{{{1.205684411948591, 0.81344322326274499}, {1.2057085875611198, 0.81344969999329253},
+ {1.205732763658403, 0.81345617746834109}}}, //t=0.63395173631977986, 0.63396444791444551
+{{{1.205732763658403, 0.81345617746834109}, {1.267928895828891, 0.83008534558465619},
+ {1.3333333333333333, 0.85185185185185175}}}, //t=0.63396444791444551, 0.66666666666666663
+};
+
+static void pointFinder(const SkDQuad& q1, const SkDQuad& q2) {
+ for (int index = 0; index < 3; ++index) {
+ double t = q1.nearestT(q2[index]);
+ SkDPoint onQuad = q1.xyAtT(t);
+ SkDebugf("%s t=%1.9g (%1.9g,%1.9g) dist=%1.9g\n", __FUNCTION__, t, onQuad.fX, onQuad.fY,
+ onQuad.distance(q2[index]));
+ double left[3];
+ left[0] = ((const SkDLine&) q1[0]).isLeft(q2[index]);
+ left[1] = ((const SkDLine&) q1[1]).isLeft(q2[index]);
+ SkDLine diag = {{q1[0], q1[2]}};
+ left[2] = diag.isLeft(q2[index]);
+ SkDebugf("%s left=(%d, %d, %d) inHull=%s\n", __FUNCTION__, floatSign(left[0]),
+ floatSign(left[1]), floatSign(left[2]),
+ q1.pointInHull(q2[index]) ? "true" : "false");
+ }
+ SkDebugf("\n");
+}
+
+static void hullIntersect(const SkDQuad& q1, const SkDQuad& q2) {
+ SkDebugf("%s", __FUNCTION__);
+ SkIntersections ts;
+ for (int i1 = 0; i1 < 3; ++i1) {
+ SkDLine l1 = {{q1[i1], q1[(i1 + 1) % 3]}};
+ for (int i2 = 0; i2 < 3; ++i2) {
+ SkDLine l2 = {{q2[i2], q2[(i2 + 1) % 3]}};
+ if (ts.intersect(l1, l2)) {
+ SkDebugf(" [%d,%d]", i1, i2);
+ }
+ }
+ }
+ SkDebugf("\n");
+}
+
+static void QuadraticIntersection_PointFinder() {
+ pointFinder(pointFinderTestSet[0], pointFinderTestSet[4]);
+ pointFinder(pointFinderTestSet[4], pointFinderTestSet[0]);
+ pointFinder(pointFinderTestSet[0], pointFinderTestSet[6]);
+ pointFinder(pointFinderTestSet[6], pointFinderTestSet[0]);
+ hullIntersect(pointFinderTestSet[0], pointFinderTestSet[4]);
+ hullIntersect(pointFinderTestSet[0], pointFinderTestSet[6]);
+}
+
+static void intersectionFinder(int test1, int test2) {
+ const SkDQuad& quad1 = testSet[test1];
+ const SkDQuad& quad2 = testSet[test2];
+
+ double t1Seed = 0.5;
+ double t2Seed = 0.8;
+ double t1Step = 0.1;
+ double t2Step = 0.1;
+ SkDPoint t1[3], t2[3];
+ bool toggle = true;
+ do {
+ t1[0] = quad1.xyAtT(t1Seed - t1Step);
+ t1[1] = quad1.xyAtT(t1Seed);
+ t1[2] = quad1.xyAtT(t1Seed + t1Step);
+ t2[0] = quad2.xyAtT(t2Seed - t2Step);
+ t2[1] = quad2.xyAtT(t2Seed);
+ t2[2] = quad2.xyAtT(t2Seed + t2Step);
+ double dist[3][3];
+ dist[1][1] = t1[1].distance(t2[1]);
+ int best_i = 1, best_j = 1;
+ for (int i = 0; i < 3; ++i) {
+ for (int j = 0; j < 3; ++j) {
+ if (i == 1 && j == 1) {
+ continue;
+ }
+ dist[i][j] = t1[i].distance(t2[j]);
+ if (dist[best_i][best_j] > dist[i][j]) {
+ best_i = i;
+ best_j = j;
+ }
+ }
+ }
+ if (best_i == 0) {
+ t1Seed -= t1Step;
+ } else if (best_i == 2) {
+ t1Seed += t1Step;
+ }
+ if (best_j == 0) {
+ t2Seed -= t2Step;
+ } else if (best_j == 2) {
+ t2Seed += t2Step;
+ }
+ if (best_i == 1 && best_j == 1) {
+ if ((toggle ^= true)) {
+ t1Step /= 2;
+ } else {
+ t2Step /= 2;
+ }
+ }
+ } while (!t1[1].approximatelyEqual(t2[1]));
+ t1Step = t2Step = 0.1;
+ double t10 = t1Seed - t1Step * 2;
+ double t12 = t1Seed + t1Step * 2;
+ double t20 = t2Seed - t2Step * 2;
+ double t22 = t2Seed + t2Step * 2;
+ SkDPoint test;
+ while (!approximately_zero(t1Step)) {
+ test = quad1.xyAtT(t10);
+ t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
+ t1Step /= 2;
+ }
+ t1Step = 0.1;
+ while (!approximately_zero(t1Step)) {
+ test = quad1.xyAtT(t12);
+ t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step;
+ t1Step /= 2;
+ }
+ while (!approximately_zero(t2Step)) {
+ test = quad2.xyAtT(t20);
+ t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
+ t2Step /= 2;
+ }
+ t2Step = 0.1;
+ while (!approximately_zero(t2Step)) {
+ test = quad2.xyAtT(t22);
+ t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step;
+ t2Step /= 2;
+ }
+#if ONE_OFF_DEBUG
+ SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__,
+ t10, t1Seed, t12, t20, t2Seed, t22);
+ SkDPoint p10 = quad1.xyAtT(t10);
+ SkDPoint p1Seed = quad1.xyAtT(t1Seed);
+ SkDPoint p12 = quad1.xyAtT(t12);
+ SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY);
+ SkDPoint p20 = quad2.xyAtT(t20);
+ SkDPoint p2Seed = quad2.xyAtT(t2Seed);
+ SkDPoint p22 = quad2.xyAtT(t22);
+ SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__,
+ p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY);
+#endif
+}
+
+static void QuadraticIntersection_IntersectionFinder() {
+ intersectionFinder(0, 1);
+}
+
+static void TestQuadIntersection(skiatest::Reporter* reporter) {
+ oneOffTests(reporter);
+ coincidentTest(reporter);
+ standardTestCases(reporter);
+ if (false) QuadraticIntersection_IntersectionFinder();
+ if (false) QuadraticIntersection_PointFinder();
+ if (false) QuadraticIntersection_OneOffTest(reporter);
+}
+
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsQuadIntersection", QuadIntersectionTestClass, TestQuadIntersection)
+
diff --git a/tests/PathOpsQuadIntersectionTestData.cpp b/tests/PathOpsQuadIntersectionTestData.cpp
new file mode 100644
index 0000000000..3c3bcdf468
--- /dev/null
+++ b/tests/PathOpsQuadIntersectionTestData.cpp
@@ -0,0 +1,104 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "PathOpsQuadIntersectionTestData.h"
+
+const SkDQuad quadraticPoints[] = {
+ {{{0, 0}, {1, 0}, {0, 0}}},
+ {{{0, 0}, {0, 1}, {0, 0}}},
+ {{{0, 0}, {1, 1}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {1, 1}}},
+};
+
+const size_t quadraticPoints_count = sizeof(quadraticPoints) / sizeof(quadraticPoints[0]);
+
+const SkDQuad quadraticLines[] = {
+ {{{0, 0}, {0, 0}, {1, 0}}},
+ {{{1, 0}, {0, 0}, {0, 0}}},
+ {{{1, 0}, {2, 0}, {3, 0}}},
+ {{{0, 0}, {0, 0}, {0, 1}}},
+ {{{0, 1}, {0, 0}, {0, 0}}},
+ {{{0, 1}, {0, 2}, {0, 3}}},
+ {{{0, 0}, {0, 0}, {1, 1}}},
+ {{{1, 1}, {0, 0}, {0, 0}}},
+ {{{1, 1}, {2, 2}, {3, 3}}},
+ {{{1, 1}, {3, 3}, {3, 3}}},
+ {{{1, 1}, {1, 1}, {2, 2}}},
+ {{{1, 1}, {1, 1}, {3, 3}}},
+ {{{1, 1}, {2, 2}, {4, 4}}}, // no coincident
+ {{{1, 1}, {3, 3}, {4, 4}}},
+ {{{1, 1}, {3, 3}, {2, 2}}},
+ {{{1, 1}, {4, 4}, {2, 2}}},
+ {{{1, 1}, {4, 4}, {3, 3}}},
+ {{{2, 2}, {1, 1}, {3, 3}}},
+ {{{2, 2}, {1, 1}, {4, 4}}},
+ {{{2, 2}, {3, 3}, {1, 1}}},
+ {{{2, 2}, {3, 3}, {4, 4}}},
+ {{{2, 2}, {4, 4}, {1, 1}}},
+ {{{2, 2}, {4, 4}, {3, 3}}},
+};
+
+const size_t quadraticLines_count = sizeof(quadraticLines) / sizeof(quadraticLines[0]);
+
+static const double F = FLT_EPSILON * 3;
+static const double H = FLT_EPSILON * 4;
+static const double J = FLT_EPSILON * 5;
+static const double K = FLT_EPSILON * 8; // INVESTIGATE: why are larger multiples necessary?
+
+const SkDQuad quadraticModEpsilonLines[] = {
+ {{{0, F}, {0, 0}, {1, 0}}},
+ {{{0, 0}, {1, 0}, {0, F}}},
+ {{{1, 0}, {0, F}, {0, 0}}},
+ {{{1, H}, {2, 0}, {3, 0}}},
+ {{{F, 0}, {0, 0}, {0, 1}}},
+ {{{0, 0}, {0, 1}, {F, 0}}},
+ {{{0, 1}, {F, 0}, {0, 0}}},
+ {{{H, 1}, {0, 2}, {0, 3}}},
+ {{{0, F}, {0, 0}, {1, 1}}},
+ {{{0, 0}, {1, 1}, {F, 0}}},
+ {{{1, 1}, {F, 0}, {0, 0}}},
+ {{{1, 1+J}, {2, 2}, {3, 3}}},
+ {{{1, 1}, {3, 3}, {3+F, 3}}},
+ {{{1, 1}, {1+F, 1}, {2, 2}}},
+ {{{1, 1}, {2, 2}, {1, 1+F}}},
+ {{{1, 1}, {1, 1+F}, {3, 3}}},
+ {{{1+H, 1}, {2, 2}, {4, 4}}}, // no coincident
+ {{{1, 1+K}, {3, 3}, {4, 4}}},
+ {{{1, 1}, {3+F, 3}, {2, 2}}},
+ {{{1, 1}, {4, 4+F}, {2, 2}}},
+ {{{1, 1}, {4, 4}, {3+F, 3}}},
+ {{{2, 2}, {1, 1}, {3, 3+F}}},
+ {{{2+F, 2}, {1, 1}, {4, 4}}},
+ {{{2, 2+F}, {3, 3}, {1, 1}}},
+ {{{2, 2}, {3+F, 3}, {4, 4}}},
+ {{{2, 2}, {4, 4+F}, {1, 1}}},
+ {{{2, 2}, {4, 4}, {3+F, 3}}},
+};
+
+const size_t quadraticModEpsilonLines_count =
+ sizeof(quadraticModEpsilonLines) / sizeof(quadraticModEpsilonLines[0]);
+
+const SkDQuad quadraticTests[][2] = {
+ { // one intersection
+ {{{0, 0},
+ {0, 1},
+ {1, 1}}},
+ {{{0, 1},
+ {0, 0},
+ {1, 0}}}
+ },
+ { // four intersections
+ {{{1, 0},
+ {2, 6},
+ {3, 0}}},
+ {{{0, 1},
+ {6, 2},
+ {0, 3}}}
+ }
+};
+
+const size_t quadraticTests_count = sizeof(quadraticTests) / sizeof(quadraticTests[0]);
diff --git a/tests/PathOpsQuadIntersectionTestData.h b/tests/PathOpsQuadIntersectionTestData.h
new file mode 100644
index 0000000000..3090fc96dd
--- /dev/null
+++ b/tests/PathOpsQuadIntersectionTestData.h
@@ -0,0 +1,17 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkPathOpsQuad.h"
+
+extern const SkDQuad quadraticLines[];
+extern const SkDQuad quadraticPoints[];
+extern const SkDQuad quadraticModEpsilonLines[];
+extern const SkDQuad quadraticTests[][2];
+
+extern const size_t quadraticLines_count;
+extern const size_t quadraticPoints_count;
+extern const size_t quadraticModEpsilonLines_count;
+extern const size_t quadraticTests_count;
diff --git a/tests/PathOpsQuadLineIntersectionTest.cpp b/tests/PathOpsQuadLineIntersectionTest.cpp
new file mode 100644
index 0000000000..09c28c1cea
--- /dev/null
+++ b/tests/PathOpsQuadLineIntersectionTest.cpp
@@ -0,0 +1,132 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "PathOpsExtendedTest.h"
+#include "SkIntersections.h"
+#include "SkPathOpsLine.h"
+#include "SkPathOpsQuad.h"
+#include "SkReduceOrder.h"
+#include "Test.h"
+
+static struct lineQuad {
+ SkDQuad quad;
+ SkDLine line;
+ int result;
+ SkDPoint expected[2];
+} lineQuadTests[] = {
+ // quad line results
+ {{{{1, 1}, {2, 1}, {0, 2}}}, {{{0, 0}, {1, 1}}}, 1, {{1, 1}, {0, 0}} },
+ {{{{0, 0}, {1, 1}, {3, 1}}}, {{{0, 0}, {3, 1}}}, 2, {{0, 0}, {3, 1}} },
+ {{{{2, 0}, {1, 1}, {2, 2}}}, {{{0, 0}, {0, 2}}}, 0, {{0, 0}, {0, 0}} },
+ {{{{4, 0}, {0, 1}, {4, 2}}}, {{{3, 1}, {4, 1}}}, 0, {{0, 0}, {0, 0}} },
+ {{{{0, 0}, {0, 1}, {1, 1}}}, {{{0, 1}, {1, 0}}}, 1, {{.25, .75}, {0, 0}} },
+};
+
+static size_t lineQuadTests_count = sizeof(lineQuadTests) / sizeof(lineQuadTests[0]);
+
+static int doIntersect(SkIntersections& intersections, const SkDQuad& quad, const SkDLine& line,
+ bool& flipped) {
+ int result;
+ flipped = false;
+ if (line[0].fX == line[1].fX) {
+ double top = line[0].fY;
+ double bottom = line[1].fY;
+ flipped = top > bottom;
+ if (flipped) {
+ SkTSwap<double>(top, bottom);
+ }
+ result = intersections.vertical(quad, top, bottom, line[0].fX, flipped);
+ } else if (line[0].fY == line[1].fY) {
+ double left = line[0].fX;
+ double right = line[1].fX;
+ flipped = left > right;
+ if (flipped) {
+ SkTSwap<double>(left, right);
+ }
+ result = intersections.horizontal(quad, left, right, line[0].fY, flipped);
+ } else {
+ intersections.intersect(quad, line);
+ result = intersections.used();
+ }
+ return result;
+}
+
+static struct oneLineQuad {
+ SkDQuad quad;
+ SkDLine line;
+} oneOffs[] = {
+ {{{{369.848602, 145.680267}, {382.360413, 121.298294}, {406.207703, 121.298294}}},
+ {{{406.207703, 121.298294}, {348.781738, 123.864815}}}}
+ };
+
+static size_t oneOffs_count = sizeof(oneOffs) / sizeof(oneOffs[0]);
+
+static void testOneOffs(skiatest::Reporter* reporter) {
+ SkIntersections intersections;
+ bool flipped = false;
+ for (size_t index = 0; index < oneOffs_count; ++index) {
+ const SkDQuad& quad = oneOffs[index].quad;
+ const SkDLine& line = oneOffs[index].line;
+ int result = doIntersect(intersections, quad, line, flipped);
+ for (int inner = 0; inner < result; ++inner) {
+ double quadT = intersections[0][inner];
+ SkDPoint quadXY = quad.xyAtT(quadT);
+ double lineT = intersections[1][inner];
+ SkDPoint lineXY = line.xyAtT(lineT);
+ REPORTER_ASSERT(reporter, quadXY.approximatelyEqual(lineXY));
+ }
+ }
+}
+
+static void TestQuadLineIntersection(skiatest::Reporter* reporter) {
+ testOneOffs(reporter);
+ for (size_t index = 0; index < lineQuadTests_count; ++index) {
+ int iIndex = static_cast<int>(index);
+ const SkDQuad& quad = lineQuadTests[index].quad;
+ const SkDLine& line = lineQuadTests[index].line;
+ SkReduceOrder reducer1, reducer2;
+ int order1 = reducer1.reduce(quad, SkReduceOrder::kFill_Style);
+ int order2 = reducer2.reduce(line);
+ if (order1 < 3) {
+ SkDebugf("%s [%d] quad order=%d\n", __FUNCTION__, iIndex, order1);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ if (order2 < 2) {
+ SkDebugf("%s [%d] line order=%d\n", __FUNCTION__, iIndex, order2);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ SkIntersections intersections;
+ bool flipped = false;
+ int result = doIntersect(intersections, quad, line, flipped);
+ REPORTER_ASSERT(reporter, result == lineQuadTests[index].result);
+ if (intersections.used() <= 0) {
+ continue;
+ }
+ for (int pt = 0; pt < result; ++pt) {
+ double tt1 = intersections[0][pt];
+ REPORTER_ASSERT(reporter, tt1 >= 0 && tt1 <= 1);
+ SkDPoint t1 = quad.xyAtT(tt1);
+ double tt2 = intersections[1][pt];
+ REPORTER_ASSERT(reporter, tt2 >= 0 && tt2 <= 1);
+ SkDPoint t2 = line.xyAtT(tt2);
+ if (!t1.approximatelyEqual(t2)) {
+ SkDebugf("%s [%d,%d] x!= t1=%1.9g (%1.9g,%1.9g) t2=%1.9g (%1.9g,%1.9g)\n",
+ __FUNCTION__, iIndex, pt, tt1, t1.fX, t1.fY, tt2, t2.fX, t2.fY);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ if (!t1.approximatelyEqual(lineQuadTests[index].expected[0])
+ && (lineQuadTests[index].result == 1
+ || !t1.approximatelyEqual(lineQuadTests[index].expected[1]))) {
+ SkDebugf("%s t1=(%1.9g,%1.9g)\n", __FUNCTION__, t1.fX, t1.fY);
+ REPORTER_ASSERT(reporter, 0);
+ }
+ }
+ }
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsQuadLineIntersection", QuadLineIntersectionTestClass, \
+ TestQuadLineIntersection)
diff --git a/tests/PathOpsQuadParameterizationTest.cpp b/tests/PathOpsQuadParameterizationTest.cpp
new file mode 100644
index 0000000000..662871bb9e
--- /dev/null
+++ b/tests/PathOpsQuadParameterizationTest.cpp
@@ -0,0 +1,53 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkDQuadImplicit.h"
+#include "SkPathOpsQuad.h"
+#include "Test.h"
+
+static bool point_on_parameterized_curve(const SkDQuad& quad, const SkDPoint& point) {
+ SkDQuadImplicit q(quad);
+ double xx = q.x2() * point.fX * point.fX;
+ double xy = q.xy() * point.fX * point.fY;
+ double yy = q.y2() * point.fY * point.fY;
+ double x = q.x() * point.fX;
+ double y = q.y() * point.fY;
+ double c = q.c();
+ double sum = xx + xy + yy + x + y + c;
+ return approximately_zero(sum);
+}
+
+static const SkDQuad quadratics[] = {
+ {{{0, 0}, {1, 0}, {1, 1}}},
+};
+
+static const size_t quadratics_count = sizeof(quadratics) / sizeof(quadratics[0]);
+
+static void TestQuadraticCoincidence(skiatest::Reporter* reporter) {
+ // split large quadratic
+ // compare original, parts, to see if the are coincident
+ for (size_t index = 0; index < quadratics_count; ++index) {
+ const SkDQuad& test = quadratics[index];
+ SkDQuadPair split = test.chopAt(0.5);
+ SkDQuad midThird = test.subDivide(1.0/3, 2.0/3);
+ const SkDQuad* quads[] = {
+ &test, &midThird, &split.first(), &split.second()
+ };
+ size_t quadsCount = sizeof(quads) / sizeof(quads[0]);
+ for (size_t one = 0; one < quadsCount; ++one) {
+ for (size_t two = 0; two < quadsCount; ++two) {
+ for (size_t inner = 0; inner < 3; inner += 2) {
+ REPORTER_ASSERT(reporter, point_on_parameterized_curve(*quads[one],
+ (*quads[two])[inner]));
+ }
+ REPORTER_ASSERT(reporter, SkDQuadImplicit::Match(*quads[one], *quads[two]));
+ }
+ }
+ }
+}
+
+#include "TestClassDef.h"
+DEFINE_TESTCLASS("PathOpsQuadImplicit", QuadImplicitTestClass, TestQuadraticCoincidence)
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-07 11:34:25 +0000