Home | History | Annotate | Download | only in Intersection 
      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