Home | History | Annotate | Download | only in Intersection 
      1 /*
      2  * Copyright 2012 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 #include "CubicIntersection_TestData.h"
      8 #include <limits>
      9 
     10 const Cubic pointDegenerates[] = {
     11     {{0, 0}, {0, 0}, {0, 0}, {0, 0}},
     12     {{1, 1}, {1, 1}, {1, 1}, {1, 1}},
     13     {{1 + PointEpsilon - std::numeric_limits<double>::epsilon(), 1},
     14      {1, 1 + PointEpsilon - std::numeric_limits<double>::epsilon()}, {1, 1}, {1, 1}},
     15     {{1 + PointEpsilon/2 - std::numeric_limits<double>::epsilon(), 1},
     16      {1 - (PointEpsilon/2 - std::numeric_limits<double>::epsilon()), 1}, {1, 1}, {1, 1}}
     17 };
     18 
     19 const size_t pointDegenerates_count = sizeof(pointDegenerates) / sizeof(pointDegenerates[0]);
     20 
     21 const Cubic notPointDegenerates[] = {
     22     {{1 + PointEpsilon + std::numeric_limits<double>::epsilon(), 1}, {1, 1 + PointEpsilon}, {1, 1}, {1, 1}},
     23     {{1 + PointEpsilon/2 + std::numeric_limits<double>::epsilon(), 1}, {1 - PointEpsilon/2, 1}, {1, 1}, {1, 1}}
     24 };
     25 
     26 const size_t notPointDegenerates_count = sizeof(notPointDegenerates) / sizeof(notPointDegenerates[0]);
     27 
     28 // from http://www.truetex.com/bezint.htm
     29 const Cubic tests[][2] = {
     30     { // intersects in one place (data gives bezier clip fits
     31      {{0, 45},
     32       {6.0094158284751593, 51.610357411322688},
     33       {12.741093228940867, 55.981703949474607},
     34       {20.021417396476362, 58.652245509710262}},
     35      {{2.2070737699246674, 52.703494107327209},
     36       {31.591482272629477, 23.811002295222025},
     37       {76.824588616426425, 44.049473790502674},
     38       {119.25488947221436, 55.599248272955073}}
     39     },
     40     { // intersects in three places
     41         {{0, 45}, {50, 100}, {150,   0}, {200, 55}},
     42         {{0, 55}, {50,   0}, {150, 100}, {200, 45}}
     43     },
     44     { // intersects in one place, cross over is nearly parallel
     45         {{0,   0}, {0, 100}, {200,   0}, {200, 100}},
     46         {{0, 100}, {0,   0}, {200, 100}, {200,   0}}
     47     },
     48     { // intersects in two places
     49         {{0,   0}, {0, 100}, {200, 100}, {200,   0}},
     50         {{0, 100}, {0,   0}, {200,   0}, {200, 100}}
     51     },
     52     {
     53         {{150, 100}, {150 + 0.1, 150}, {150, 200}, {150, 250}},
     54         {{250, 150}, {200, 150 + 0.1}, {150, 150}, {100, 150}}
     55     },
     56     { // single intersection around 168,185
     57         {{200, 100}, {150, 100}, {150, 150}, {200, 150}},
     58         {{250, 150}, {250, 100}, {100, 100}, {100, 150}}
     59     },
     60     {
     61         {{1.0, 1.5}, {15.5, 0.5}, {-8.0, 3.5}, {5.0, 1.5}},
     62         {{4.0, 0.5}, {5.0, 15.0}, {2.0, -8.5}, {4.0, 4.5}}
     63     },
     64     {
     65         {{664.00168, 0},       {726.11545, 124.22757}, {736.89069, 267.89743}, {694.0017, 400.0002}},
     66         {{850.66843, 115.55563}, {728.515, 115.55563}, {725.21347, 275.15309}, {694.0017, 400.0002}}
     67     },
     68     {
     69         {{1, 1},   {12.5, 6.5}, {-4, 6.5}, {7.5, 1}},
     70         {{1, 6.5}, {12.5, 1},   {-4, 1},   {.5, 6}}
     71     },
     72     {
     73         {{315.748, 312.84}, {312.644, 318.134}, {305.836, 319.909}, {300.542, 316.804}},
     74         {{317.122, 309.05}, {316.112, 315.102}, {310.385, 319.19},  {304.332, 318.179}}
     75     },
     76     {
     77         {{1046.604051, 172.937967},  {1046.604051, 178.9763059}, {1041.76745,  183.9279165}, {1035.703842, 184.0432409}},
     78         {{1046.452235, 174.7640504}, {1045.544872, 180.1973817}, {1040.837966, 184.0469882}, {1035.505925, 184.0469882}}
     79     },
     80     {
     81         {{125.79356, 199.57382}, {51.16556, 128.93575}, {87.494,  16.67848}, {167.29361, 16.67848}},
     82         {{167.29361, 55.81876}, {100.36128, 55.81876}, {68.64099, 145.4755}, {125.7942, 199.57309}}
     83     }
     84 };
     85 
     86 const size_t tests_count = sizeof(tests) / sizeof(tests[0]);
     87 
     88 Cubic hexTests[][2] = {
     89     {
     90         {{0}} // placeholder for hex converted below
     91     }
     92 };
     93 
     94 const size_t hexTests_count = sizeof(hexTests) / sizeof(hexTests[0]);
     95 
     96 static const uint64_t testx[2][8] = {
     97     {
     98         0xf0d0d1ca63075a40LLU, 0x9408ce996a237740LLU, 0x6d5675460fbe5e40LLU, 0x6ef501e1b7487940LLU,
     99         0x9a71d2f8143d6540LLU, 0x6bc18bbe02907a40LLU, 0x5b94d92093aa6b40LLU, 0x6ac18bbe02907a40LLU
    100     },
    101     {
    102         0x92c56ed7b6145d40LLU, 0xede4f1255edb7740LLU, 0x1138c1101af75940LLU, 0x42e4f1255edb7740LLU,
    103         0x408e51603ad95640LLU, 0x1e2e8fe9dd927740LLU, 0x1cb4777cd3a75440LLU, 0x212e1390de017740LLU
    104     }
    105 };
    106 
    107 void convert_testx() {
    108     const uint64_t* inPtr = testx[0];
    109     double* outPtr = &hexTests[sizeof(tests) / sizeof(tests[0]) - 1][0][0].x;
    110     for (unsigned index = 0; index < sizeof(testx) / sizeof(testx[0][0]); ++index) {
    111         uint64_t input = *inPtr++;
    112         unsigned char* output = (unsigned char*) outPtr++;
    113         for (unsigned byte = 0; byte < sizeof(input); ++byte) {
    114             output[byte] = input >> (7 - byte) * 8;
    115         }
    116     }
    117 }
    118 
    119 const Cubic lines[] = {
    120     {{0, 0}, {0, 0}, {0, 0}, {1, 0}}, // 0: horizontal
    121     {{0, 0}, {0, 0}, {1, 0}, {0, 0}},
    122     {{0, 0}, {1, 0}, {0, 0}, {0, 0}},
    123     {{1, 0}, {0, 0}, {0, 0}, {0, 0}},
    124     {{1, 0}, {2, 0}, {3, 0}, {4, 0}},
    125     {{0, 0}, {0, 0}, {0, 0}, {0, 1}}, // 5: vertical
    126     {{0, 0}, {0, 0}, {0, 1}, {0, 0}},
    127     {{0, 0}, {0, 1}, {0, 0}, {0, 0}},
    128     {{0, 1}, {0, 0}, {0, 0}, {0, 0}},
    129     {{0, 1}, {0, 2}, {0, 3}, {0, 4}},
    130     {{0, 0}, {0, 0}, {0, 0}, {1, 1}}, // 10: 3 coincident
    131     {{0, 0}, {0, 0}, {1, 1}, {0, 0}},
    132     {{0, 0}, {1, 1}, {0, 0}, {0, 0}},
    133     {{1, 1}, {0, 0}, {0, 0}, {0, 0}},
    134     {{0, 0}, {0, 0}, {1, 1}, {2, 2}}, // 14: 2 coincident
    135     {{0, 0}, {1, 1}, {0, 0}, {2, 2}},
    136     {{0, 0}, {1, 1}, {2, 2}, {0, 0}},
    137     {{1, 1}, {0, 0}, {0, 0}, {2, 2}}, // 17:
    138     {{1, 1}, {0, 0}, {2, 2}, {0, 0}},
    139     {{1, 1}, {2, 2}, {0, 0}, {0, 0}},
    140     {{1, 1}, {2, 2}, {3, 3}, {2, 2}}, // middle-last coincident
    141     {{1, 1}, {2, 2}, {3, 3}, {3, 3}}, // middle-last coincident
    142     {{1, 1}, {1, 1}, {2, 2}, {2, 2}}, // 2 pairs coincident
    143     {{1, 1}, {2, 2}, {1, 1}, {2, 2}},
    144     {{1, 1}, {2, 2}, {2, 2}, {1, 1}},
    145     {{1, 1}, {1, 1}, {3, 3}, {3, 3}}, // first-middle middle-last coincident
    146     {{1, 1}, {2, 2}, {3, 3}, {4, 4}}, // no coincident
    147     {{1, 1}, {3, 3}, {2, 2}, {4, 4}},
    148     {{1, 1}, {2, 2}, {4, 4}, {3, 3}},
    149     {{1, 1}, {3, 3}, {4, 4}, {2, 2}},
    150     {{1, 1}, {4, 4}, {2, 2}, {3, 3}},
    151     {{1, 1}, {4, 4}, {3, 3}, {2, 2}},
    152     {{2, 2}, {1, 1}, {3, 3}, {4, 4}},
    153     {{2, 2}, {1, 1}, {4, 4}, {3, 3}},
    154     {{2, 2}, {3, 3}, {1, 1}, {4, 4}},
    155     {{2, 2}, {3, 3}, {4, 4}, {1, 1}},
    156     {{2, 2}, {4, 4}, {1, 1}, {3, 3}},
    157     {{2, 2}, {4, 4}, {3, 3}, {1, 1}},
    158 };
    159 
    160 const size_t lines_count = sizeof(lines) / sizeof(lines[0]);
    161 
    162 // 'not a line' tries to fool the line detection code
    163 const Cubic notLines[] = {
    164     {{0, 0}, {0, 0}, {0, 1}, {1, 0}},
    165     {{0, 0}, {0, 1}, {0, 0}, {1, 0}},
    166     {{0, 0}, {0, 1}, {1, 0}, {0, 0}},
    167     {{0, 1}, {0, 0}, {0, 0}, {1, 0}},
    168     {{0, 1}, {0, 0}, {1, 0}, {0, 0}},
    169     {{0, 1}, {1, 0}, {0, 0}, {0, 0}},
    170 };
    171 
    172 const size_t notLines_count = sizeof(notLines) / sizeof(notLines[0]);
    173 
    174 static const double E = PointEpsilon * 2;
    175 static const double F = PointEpsilon * 3;
    176 
    177 const Cubic modEpsilonLines[] = {
    178     {{0, E}, {0, 0}, {0, 0}, {1, 0}}, // horizontal
    179     {{0, 0}, {0, E}, {1, 0}, {0, 0}},
    180     {{0, 0}, {1, 0}, {0, E}, {0, 0}},
    181     {{1, 0}, {0, 0}, {0, 0}, {0, E}},
    182     {{1, E}, {2, 0}, {3, 0}, {4, 0}},
    183     {{E, 0}, {0, 0}, {0, 0}, {0, 1}}, // vertical
    184     {{0, 0}, {E, 0}, {0, 1}, {0, 0}},
    185     {{0, 0}, {0, 1}, {E, 0}, {0, 0}},
    186     {{0, 1}, {0, 0}, {0, 0}, {E, 0}},
    187     {{E, 1}, {0, 2}, {0, 3}, {0, 4}},
    188     {{E, 0}, {0, 0}, {0, 0}, {1, 1}}, // 3 coincident
    189     {{0, 0}, {E, 0}, {1, 1}, {0, 0}},
    190     {{0, 0}, {1, 1}, {E, 0}, {0, 0}},
    191     {{1, 1}, {0, 0}, {0, 0}, {E, 0}},
    192     {{0, E}, {0, 0}, {1, 1}, {2, 2}}, // 2 coincident
    193     {{0, 0}, {1, 1}, {0, E}, {2, 2}},
    194     {{0, 0}, {1, 1}, {2, 2}, {0, E}},
    195     {{1, 1}, {0, E}, {0, 0}, {2, 2}},
    196     {{1, 1}, {0, E}, {2, 2}, {0, 0}},
    197     {{1, 1}, {2, 2}, {E, 0}, {0, 0}},
    198     {{1, 1}, {2, 2+E}, {3, 3}, {2, 2}}, // middle-last coincident
    199     {{1, 1}, {2+E, 2}, {3, 3}, {3, 3}}, // middle-last coincident
    200     {{1, 1}, {1, 1}, {2, 2}, {2+E, 2}}, // 2 pairs coincident
    201     {{1, 1}, {2, 2}, {1, 1}, {2+E, 2}},
    202     {{1, 1}, {2, 2}, {2, 2+E}, {1, 1}},
    203     {{1, 1}, {1, 1+E}, {3, 3}, {3, 3}}, // first-middle middle-last coincident
    204     {{1, 1}, {2+E, 2}, {3, 3}, {4, 4}}, // no coincident
    205     {{1, 1}, {3, 3}, {2, 2}, {4, 4+F}}, // INVESTIGATE: why the epsilon is bigger
    206     {{1, 1+F}, {2, 2}, {4, 4}, {3, 3}}, // INVESTIGATE: why the epsilon is bigger
    207     {{1, 1}, {3, 3}, {4, 4+E}, {2, 2}},
    208     {{1, 1}, {4, 4}, {2, 2}, {3, 3+E}},
    209     {{1, 1}, {4, 4}, {3, 3}, {2+E, 2}},
    210     {{2, 2}, {1, 1}, {3+E, 3}, {4, 4}},
    211     {{2, 2}, {1+E, 1}, {4, 4}, {3, 3}},
    212     {{2, 2+E}, {3, 3}, {1, 1}, {4, 4}},
    213     {{2+E, 2}, {3, 3}, {4, 4}, {1, 1}},
    214     {{2, 2}, {4+E, 4}, {1, 1}, {3, 3}},
    215     {{2, 2}, {4, 4}, {3, 3}, {1, 1+E}},
    216 };
    217 
    218 const size_t modEpsilonLines_count = sizeof(modEpsilonLines) / sizeof(modEpsilonLines[0]);
    219 
    220 static const double D = PointEpsilon / 2;
    221 static const double G = PointEpsilon / 3;
    222 
    223 const Cubic lessEpsilonLines[] = {
    224     {{0, D}, {0, 0}, {0, 0}, {1, 0}}, // horizontal
    225     {{0, 0}, {0, D}, {1, 0}, {0, 0}},
    226     {{0, 0}, {1, 0}, {0, D}, {0, 0}},
    227     {{1, 0}, {0, 0}, {0, 0}, {0, D}},
    228     {{1, D}, {2, 0}, {3, 0}, {4, 0}},
    229     {{D, 0}, {0, 0}, {0, 0}, {0, 1}}, // vertical
    230     {{0, 0}, {D, 0}, {0, 1}, {0, 0}},
    231     {{0, 0}, {0, 1}, {D, 0}, {0, 0}},
    232     {{0, 1}, {0, 0}, {0, 0}, {D, 0}},
    233     {{D, 1}, {0, 2}, {0, 3}, {0, 4}},
    234     {{D, 0}, {0, 0}, {0, 0}, {1, 1}}, // 3 coincident
    235     {{0, 0}, {D, 0}, {1, 1}, {0, 0}},
    236     {{0, 0}, {1, 1}, {D, 0}, {0, 0}},
    237     {{1, 1}, {0, 0}, {0, 0}, {D, 0}},
    238     {{0, D}, {0, 0}, {1, 1}, {2, 2}}, // 2 coincident
    239     {{0, 0}, {1, 1}, {0, D}, {2, 2}},
    240     {{0, 0}, {1, 1}, {2, 2}, {0, D}},
    241     {{1, 1}, {0, D}, {0, 0}, {2, 2}},
    242     {{1, 1}, {0, D}, {2, 2}, {0, 0}},
    243     {{1, 1}, {2, 2}, {D, 0}, {0, 0}},
    244     {{1, 1}, {2, 2+D}, {3, 3}, {2, 2}}, // middle-last coincident
    245     {{1, 1}, {2+D, 2}, {3, 3}, {3, 3}}, // middle-last coincident
    246     {{1, 1}, {1, 1}, {2, 2}, {2+D, 2}}, // 2 pairs coincident
    247     {{1, 1}, {2, 2}, {1, 1}, {2+D, 2}},
    248     {{1, 1}, {2, 2}, {2, 2+D}, {1, 1}},
    249     {{1, 1}, {1, 1+D}, {3, 3}, {3, 3}}, // first-middle middle-last coincident
    250     {{1, 1}, {2+D/2, 2}, {3, 3}, {4, 4}}, // no coincident (FIXME: N as opposed to N/2 failed)
    251     {{1, 1}, {3, 3}, {2, 2}, {4, 4+D}},
    252     {{1, 1+D}, {2, 2}, {4, 4}, {3, 3}},
    253     {{1, 1}, {3, 3}, {4, 4+D}, {2, 2}},
    254     {{1, 1}, {4, 4}, {2, 2}, {3, 3+D}},
    255     {{1, 1}, {4, 4}, {3, 3}, {2+G, 2}}, // INVESTIGATE: why the epsilon is smaller
    256     {{2, 2}, {1, 1}, {3+D, 3}, {4, 4}},
    257     {{2, 2}, {1+D, 1}, {4, 4}, {3, 3}},
    258     {{2, 2+D}, {3, 3}, {1, 1}, {4, 4}},
    259     {{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}, // INVESTIGATE: why the epsilon is smaller
    260     {{2, 2}, {4+D, 4}, {1, 1}, {3, 3}},
    261     {{2, 2}, {4, 4}, {3, 3}, {1, 1+D}},
    262 };
    263 
    264 const size_t lessEpsilonLines_count = sizeof(lessEpsilonLines) / sizeof(lessEpsilonLines[0]);
    265 
    266 static const double N = -PointEpsilon / 2;
    267 static const double M = -PointEpsilon / 3;
    268 
    269 const Cubic negEpsilonLines[] = {
    270     {{0, N}, {0, 0}, {0, 0}, {1, 0}}, // horizontal
    271     {{0, 0}, {0, N}, {1, 0}, {0, 0}},
    272     {{0, 0}, {1, 0}, {0, N}, {0, 0}},
    273     {{1, 0}, {0, 0}, {0, 0}, {0, N}},
    274     {{1, N}, {2, 0}, {3, 0}, {4, 0}},
    275     {{N, 0}, {0, 0}, {0, 0}, {0, 1}}, // vertical
    276     {{0, 0}, {N, 0}, {0, 1}, {0, 0}},
    277     {{0, 0}, {0, 1}, {N, 0}, {0, 0}},
    278     {{0, 1}, {0, 0}, {0, 0}, {N, 0}},
    279     {{N, 1}, {0, 2}, {0, 3}, {0, 4}},
    280     {{N, 0}, {0, 0}, {0, 0}, {1, 1}}, // 3 coincident
    281     {{0, 0}, {N, 0}, {1, 1}, {0, 0}},
    282     {{0, 0}, {1, 1}, {N, 0}, {0, 0}},
    283     {{1, 1}, {0, 0}, {0, 0}, {N, 0}},
    284     {{0, N}, {0, 0}, {1, 1}, {2, 2}}, // 2 coincident
    285     {{0, 0}, {1, 1}, {0, N}, {2, 2}},
    286     {{0, 0}, {1, 1}, {2, 2}, {0, N}},
    287     {{1, 1}, {0, N}, {0, 0}, {2, 2}},
    288     {{1, 1}, {0, N}, {2, 2}, {0, 0}},
    289     {{1, 1}, {2, 2}, {N, 0}, {0, 0}},
    290     {{1, 1}, {2, 2+N}, {3, 3}, {2, 2}}, // middle-last coincident
    291     {{1, 1}, {2+N, 2}, {3, 3}, {3, 3}}, // middle-last coincident
    292     {{1, 1}, {1, 1}, {2, 2}, {2+N, 2}}, // 2 pairs coincident
    293     {{1, 1}, {2, 2}, {1, 1}, {2+N, 2}},
    294     {{1, 1}, {2, 2}, {2, 2+N}, {1, 1}},
    295     {{1, 1}, {1, 1+N}, {3, 3}, {3, 3}}, // first-middle middle-last coincident
    296     {{1, 1}, {2+N/2, 2}, {3, 3}, {4, 4}}, // no coincident (FIXME: N as opposed to N/2 failed)
    297     {{1, 1}, {3, 3}, {2, 2}, {4, 4+N}},
    298     {{1, 1+N}, {2, 2}, {4, 4}, {3, 3}},
    299     {{1, 1}, {3, 3}, {4, 4+N}, {2, 2}},
    300     {{1, 1}, {4, 4}, {2, 2}, {3, 3+N}},
    301     {{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}, // INVESTIGATE: why the epsilon is smaller
    302     {{2, 2}, {1, 1}, {3+N, 3}, {4, 4}},
    303     {{2, 2}, {1+N, 1}, {4, 4}, {3, 3}},
    304     {{2, 2+N}, {3, 3}, {1, 1}, {4, 4}},
    305     {{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}, // INVESTIGATE: why the epsilon is smaller
    306     {{2, 2}, {4+N, 4}, {1, 1}, {3, 3}},
    307     {{2, 2}, {4, 4}, {3, 3}, {1, 1+N}},
    308 };
    309 
    310 const size_t negEpsilonLines_count = sizeof(negEpsilonLines) / sizeof(negEpsilonLines[0]);
    311