1 #include "CubicIntersection_TestData.h" 2 #include "CubicUtilities.h" 3 #include "Intersection_Tests.h" 4 #include "QuadraticIntersection_TestData.h" 5 #include "TestUtilities.h" 6 #include "SkGeometry.h" 7 8 static void test(const Cubic* cubics, const char* name, int firstTest, size_t testCount) { 9 SkTDArray<Quadratic> quads; 10 for (size_t index = firstTest; index < testCount; ++index) { 11 const Cubic& cubic = cubics[index]; 12 double precision = calcPrecision(cubic); 13 (void) cubic_to_quadratics(cubic, precision, quads); 14 if (quads.count() != 1) { 15 printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index, 16 quads.count()); 17 } 18 } 19 } 20 21 static void test(const Quadratic* quadTests, const char* name, int firstTest, size_t testCount) { 22 SkTDArray<Quadratic> quads; 23 for (size_t index = firstTest; index < testCount; ++index) { 24 const Quadratic& quad = quadTests[index]; 25 Cubic cubic; 26 quad_to_cubic(quad, cubic); 27 double precision = calcPrecision(cubic); 28 (void) cubic_to_quadratics(cubic, precision, quads); 29 if (quads.count() != 1) { 30 printf("%s [%d] cubic to quadratics failed count=%d\n", name, (int) index, 31 quads.count()); 32 } 33 } 34 } 35 36 static void testC(const Cubic* cubics, const char* name, int firstTest, size_t testCount) { 37 SkTDArray<Quadratic> quads; 38 // test if computed line end points are valid 39 for (size_t index = firstTest; index < testCount; ++index) { 40 const Cubic& cubic = cubics[index]; 41 double precision = calcPrecision(cubic); 42 int order = cubic_to_quadratics(cubic, precision, quads); 43 SkASSERT(order != 4); 44 if (order < 3) { 45 continue; 46 } 47 if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x) 48 || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) { 49 printf("[%d] unmatched start\n", (int) index); 50 } 51 int last = quads.count() - 1; 52 if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x) 53 || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) { 54 printf("[%d] unmatched end\n", (int) index); 55 } 56 } 57 } 58 59 static void testC(const Cubic(* cubics)[2], const char* name, int firstTest, size_t testCount) { 60 SkTDArray<Quadratic> quads; 61 for (size_t index = firstTest; index < testCount; ++index) { 62 for (int idx2 = 0; idx2 < 2; ++idx2) { 63 const Cubic& cubic = cubics[index][idx2]; 64 double precision = calcPrecision(cubic); 65 int order = cubic_to_quadratics(cubic, precision, quads); 66 SkASSERT(order != 4); 67 if (order < 3) { 68 continue; 69 } 70 if (!AlmostEqualUlps(cubic[0].x, quads[0][0].x) 71 || !AlmostEqualUlps(cubic[0].y, quads[0][0].y)) { 72 printf("[%d][%d] unmatched start\n", (int) index, idx2); 73 } 74 int last = quads.count() - 1; 75 if (!AlmostEqualUlps(cubic[3].x, quads[last][2].x) 76 || !AlmostEqualUlps(cubic[3].y, quads[last][2].y)) { 77 printf("[%d][%d] unmatched end\n", (int) index, idx2); 78 } 79 } 80 } 81 } 82 83 void CubicToQuadratics_Test() { 84 enum { 85 RunAll, 86 RunPointDegenerates, 87 RunNotPointDegenerates, 88 RunLines, 89 RunNotLines, 90 RunModEpsilonLines, 91 RunLessEpsilonLines, 92 RunNegEpsilonLines, 93 RunQuadraticLines, 94 RunQuadraticModLines, 95 RunComputedLines, 96 RunComputedTests, 97 RunNone 98 } run = RunAll; 99 int firstTestIndex = 0; 100 #if 0 101 run = RunComputedLines; 102 firstTestIndex = 18; 103 #endif 104 int firstPointDegeneratesTest = run == RunAll ? 0 : run == RunPointDegenerates ? firstTestIndex : SK_MaxS32; 105 int firstNotPointDegeneratesTest = run == RunAll ? 0 : run == RunNotPointDegenerates ? firstTestIndex : SK_MaxS32; 106 int firstLinesTest = run == RunAll ? 0 : run == RunLines ? firstTestIndex : SK_MaxS32; 107 int firstNotLinesTest = run == RunAll ? 0 : run == RunNotLines ? firstTestIndex : SK_MaxS32; 108 int firstModEpsilonTest = run == RunAll ? 0 : run == RunModEpsilonLines ? firstTestIndex : SK_MaxS32; 109 int firstLessEpsilonTest = run == RunAll ? 0 : run == RunLessEpsilonLines ? firstTestIndex : SK_MaxS32; 110 int firstNegEpsilonTest = run == RunAll ? 0 : run == RunNegEpsilonLines ? firstTestIndex : SK_MaxS32; 111 int firstQuadraticLineTest = run == RunAll ? 0 : run == RunQuadraticLines ? firstTestIndex : SK_MaxS32; 112 int firstQuadraticModLineTest = run == RunAll ? 0 : run == RunQuadraticModLines ? firstTestIndex : SK_MaxS32; 113 int firstComputedLinesTest = run == RunAll ? 0 : run == RunComputedLines ? firstTestIndex : SK_MaxS32; 114 int firstComputedCubicsTest = run == RunAll ? 0 : run == RunComputedTests ? firstTestIndex : SK_MaxS32; 115 116 test(pointDegenerates, "pointDegenerates", firstPointDegeneratesTest, pointDegenerates_count); 117 test(notPointDegenerates, "notPointDegenerates", firstNotPointDegeneratesTest, notPointDegenerates_count); 118 test(lines, "lines", firstLinesTest, lines_count); 119 test(notLines, "notLines", firstNotLinesTest, notLines_count); 120 test(modEpsilonLines, "modEpsilonLines", firstModEpsilonTest, modEpsilonLines_count); 121 test(lessEpsilonLines, "lessEpsilonLines", firstLessEpsilonTest, lessEpsilonLines_count); 122 test(negEpsilonLines, "negEpsilonLines", firstNegEpsilonTest, negEpsilonLines_count); 123 test(quadraticLines, "quadraticLines", firstQuadraticLineTest, quadraticLines_count); 124 test(quadraticModEpsilonLines, "quadraticModEpsilonLines", firstQuadraticModLineTest, 125 quadraticModEpsilonLines_count); 126 testC(lines, "computed lines", firstComputedLinesTest, lines_count); 127 testC(tests, "computed tests", firstComputedCubicsTest, tests_count); 128 printf("%s end\n", __FUNCTION__); 129 } 130 131 static Cubic locals[] = { 132 {{0, 1}, {1.9274705288631189e-19, 1.0000000000000002}, {0.0017190297609673323, 0.99828097023903239}, 133 {0.0053709083094631276, 0.99505672974365911}}, 134 135 {{14.5975863, 41.632436}, {16.3518929, 26.2639684}, {18.5165519, 7.68775139}, {8.03767257, 89.1628526}}, 136 {{69.7292014, 38.6877352}, {24.7648688, 23.1501713}, {84.9283191, 90.2588441}, {80.392774, 61.3533852}}, 137 {{ 138 60.776536520932126, 139 71.249307306133829 140 }, { 141 87.107894191103014, 142 22.377669868235323 143 }, { 144 1.4974754310666936, 145 68.069569937917208 146 }, { 147 45.261946574441133, 148 17.536076632112298 149 }}, 150 }; 151 152 static size_t localsCount = sizeof(locals) / sizeof(locals[0]); 153 154 #define DEBUG_CRASH 0 155 #define TEST_AVERAGE_END_POINTS 0 // must take const off to test 156 extern const bool AVERAGE_END_POINTS; 157 158 static void oneOff(size_t x) { 159 const Cubic& cubic = locals[x]; 160 const SkPoint skcubic[4] = {{(float) cubic[0].x, (float) cubic[0].y}, 161 {(float) cubic[1].x, (float) cubic[1].y}, {(float) cubic[2].x, (float) cubic[2].y}, 162 {(float) cubic[3].x, (float) cubic[3].y}}; 163 SkScalar skinflect[2]; 164 int skin = SkFindCubicInflections(skcubic, skinflect); 165 SkDebugf("%s %d %1.9g\n", __FUNCTION__, skin, skinflect[0]); 166 SkTDArray<Quadratic> quads; 167 double precision = calcPrecision(cubic); 168 (void) cubic_to_quadratics(cubic, precision, quads); 169 SkDebugf("%s quads=%d\n", __FUNCTION__, quads.count()); 170 } 171 172 void CubicsToQuadratics_OneOffTests() { 173 for (size_t x = 0; x < localsCount; ++x) { 174 oneOff(x); 175 } 176 } 177 178 void CubicsToQuadratics_OneOffTest() { 179 oneOff(0); 180 } 181 182 void CubicsToQuadratics_RandTest() { 183 srand(0); 184 const int arrayMax = 8; 185 const int sampleMax = 10; 186 const int tests = 1000000; // 10000000; 187 int quadDist[arrayMax]; 188 bzero(quadDist, sizeof(quadDist)); 189 Cubic samples[arrayMax][sampleMax]; 190 int sampleCount[arrayMax]; 191 bzero(sampleCount, sizeof(sampleCount)); 192 for (int x = 0; x < tests; ++x) { 193 Cubic cubic; 194 for (int i = 0; i < 4; ++i) { 195 cubic[i].x = (double) rand() / RAND_MAX * 100; 196 cubic[i].y = (double) rand() / RAND_MAX * 100; 197 } 198 #if DEBUG_CRASH 199 char str[1024]; 200 sprintf(str, "{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", 201 cubic[0].x, cubic[0].y, cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y, 202 cubic[3].x, cubic[3].y); 203 #endif 204 SkTDArray<Quadratic> quads; 205 double precision = calcPrecision(cubic); 206 (void) cubic_to_quadratics(cubic, precision, quads); 207 int count = quads.count(); 208 SkASSERT(count > 0); 209 SkASSERT(--count < arrayMax); 210 quadDist[count]++; 211 int sCount = sampleCount[count]; 212 if (sCount < sampleMax) { 213 memcpy(samples[count][sCount], cubic, sizeof(Cubic)); 214 sampleCount[count]++; 215 } 216 } 217 for (int x = 0; x < arrayMax; ++x) { 218 if (!quadDist[x]) { 219 continue; 220 } 221 SkDebugf("%d %1.9g%%\n", x + 1, (double) quadDist[x] / tests * 100); 222 } 223 SkDebugf("\n"); 224 for (int x = 0; x < arrayMax; ++x) { 225 for (int y = 0; y < sampleCount[x]; ++y) { 226 #if TEST_AVERAGE_END_POINTS 227 for (int w = 0; w < 2; ++w) { 228 AVERAGE_END_POINTS = w; 229 #else 230 int w = 0; 231 #endif 232 SkDebugf("<div id=\"cubic%dx%d%s\">\n", x + 1, y, w ? "x" : ""); 233 const Cubic& cubic = samples[x][y]; 234 SkDebugf("{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", 235 cubic[0].x, cubic[0].y, cubic[1].x, cubic[1].y, cubic[2].x, cubic[2].y, 236 cubic[3].x, cubic[3].y); 237 SkTDArray<Quadratic> quads; 238 double precision = calcPrecision(cubic); 239 (void) cubic_to_quadratics(cubic, precision, quads); 240 for (int z = 0; z < quads.count(); ++z) { 241 const Quadratic& quad = quads[z]; 242 SkDebugf("{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}},\n", 243 quad[0].x, quad[0].y, quad[1].x, quad[1].y, quad[2].x, quad[2].y); 244 } 245 SkDebugf("</div>\n\n"); 246 #if TEST_AVERAGE_END_POINTS 247 } 248 #endif 249 } 250 } 251 SkDebugf("</div>\n\n"); 252 SkDebugf("<script type=\"text/javascript\">\n\n"); 253 SkDebugf("var testDivs = [\n"); 254 for (int x = 0; x < arrayMax; ++x) { 255 for (int y = 0; y < sampleCount[x]; ++y) { 256 #if TEST_AVERAGE_END_POINTS 257 for (int w = 0; w < 2; ++w) { 258 #else 259 int w = 0; 260 #endif 261 SkDebugf(" cubic%dx%d%s,\n", x + 1, y, w ? "x" : ""); 262 #if TEST_AVERAGE_END_POINTS 263 } 264 #endif 265 } 266 } 267 SkDebugf("\n\n\n"); 268 SkDebugf("%s end\n", __FUNCTION__); 269 } 270