submodule/skia/tests/PathOpsCubicIntersectionTestData.cpp

   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
   8 #include "tests/PathOpsCubicIntersectionTestData.h"
   9
  10 #include <limits>
  11
  12 namespace PathOpsCubicIntersectionTestData {
  13
  14 static const double D = FLT_EPSILON / 2;
  15 static const double G = FLT_EPSILON / 3;
  16 static const double N = -FLT_EPSILON / 2;
  17 static const double M = -FLT_EPSILON / 3;
  18
  19 const CubicPts pointDegenerates[] = {
  20     {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}},
  21     {{{1, 1}, {1, 1}, {1, 1}, {1, 1}}},
  22     {{{1 + FLT_EPSILON_HALF, 1}, {1, 1 + FLT_EPSILON_HALF}, {1, 1}, {1, 1}}},
  23     {{{1 + D, 1}, {1 - D, 1}, {1, 1}, {1, 1}}},
  24     {{{0, 0}, {0, 0}, {1, 0}, {0, 0}}},
  25     {{{0, 0}, {1, 0}, {0, 0}, {0, 0}}},
  26     {{{0, 0}, {0, 0}, {0, 1}, {0, 0}}},
  27     {{{0, 0}, {0, 1}, {0, 0}, {0, 0}}},
  28     {{{0, 0}, {0, 0}, {1, 1}, {0, 0}}},
  29     {{{0, 0}, {1, 1}, {0, 0}, {0, 0}}},
  30     {{{0, 0}, {1, 1}, {2, 2}, {0, 0}}},
  31     {{{1, 1}, {2, 2}, {2, 2}, {1, 1}}},
  32     {{{0, 0}, {0, D}, {1, 0}, {0, 0}}},
  33     {{{0, 0}, {1, 0}, {0, D}, {0, 0}}},
  34     {{{0, 0}, {D, 0}, {0, 1}, {0, 0}}},
  35     {{{0, 0}, {0, 1}, {D, 0}, {0, 0}}},
  36     {{{1, 1}, {2, 2}, {2, 2+D}, {1, 1}}},
  37     {{{0, 0}, {0, N}, {1, 0}, {0, 0}}},
  38     {{{0, 0}, {1, 0}, {0, N}, {0, 0}}},
  39     {{{0, 0}, {N, 0}, {0, 1}, {0, 0}}},
  40     {{{0, 0}, {0, 1}, {N, 0}, {0, 0}}},
  41     {{{0, 0}, {1, 1}, {N, 0}, {0, 0}}},
  42     {{{0, 0}, {D, 0}, {1, 1}, {0, 0}}},
  43     {{{0, 0}, {1, 1}, {D, 0}, {0, 0}}},
  44     {{{0, 0}, {N, 0}, {1, 1}, {0, 0}}},
  45     {{{1, 1}, {2, 2}, {2, 2+N}, {1, 1}}},
  46 };
  47
  48 const size_t pointDegenerates_count = SK_ARRAY_COUNT(pointDegenerates);
  49
  50 const CubicPts notPointDegenerates[] = {
  51     {{{1 + FLT_EPSILON * 8, 1}, {1, FLT_EPSILON * 8}, {1, 1}, {1, 1}}},
  52     {{{1 + FLT_EPSILON * 8, 1}, {1 - FLT_EPSILON * 8, 1}, {1, 1}, {1, 1}}}
  53 };
  54
  55 const size_t notPointDegenerates_count =
  56         SK_ARRAY_COUNT(notPointDegenerates);
  57
  58 // from http://www.truetex.com/bezint.htm
  59 const CubicPts tests[][2] = {
  60     {  // intersects in one place (data gives bezier clip fits
  61      {{{0, 45},
  62       {6.0094158284751593, 51.610357411322688},
  63       {12.741093228940867, 55.981703949474607},
  64       {20.021417396476362, 58.652245509710262}}},
  65      {{{2.2070737699246674, 52.703494107327209},
  66       {31.591482272629477, 23.811002295222025},
  67       {76.824588616426425, 44.049473790502674},
  68       {119.25488947221436, 55.599248272955073}}}
  69     }, {  // intersects in three places
  70         {{{0, 45}, {50, 100}, {150,   0}, {200, 55}}},
  71         {{{0, 55}, {50,   0}, {150, 100}, {200, 45}}}
  72     }, {  // intersects in one place, cross over is nearly parallel
  73         {{{0,   0}, {0, 100}, {200,   0}, {200, 100}}},
  74         {{{0, 100}, {0,   0}, {200, 100}, {200,   0}}}
  75     }, {  // intersects in two places
  76         {{{0,   0}, {0, 100}, {200, 100}, {200,   0}}},
  77         {{{0, 100}, {0,   0}, {200,   0}, {200, 100}}}
  78     }, {
  79         {{{150, 100}, {150 + 0.1, 150}, {150, 200}, {150, 250}}},
  80         {{{250, 150}, {200, 150 + 0.1}, {150, 150}, {100, 150}}}
  81     }, {  // single intersection around 168,185
  82         {{{200, 100}, {150, 100}, {150, 150}, {200, 150}}},
  83         {{{250, 150}, {250, 100}, {100, 100}, {100, 150}}}
  84     }, {
  85         {{{1.0, 1.5}, {15.5, 0.5}, {-8.0, 3.5}, {5.0, 1.5}}},
  86         {{{4.0, 0.5}, {5.0, 15.0}, {2.0, -8.5}, {4.0, 4.5}}}
  87     }, {
  88         {{{664.00168, 0},       {726.11545, 124.22757}, {736.89069, 267.89743},
  89                 {694.0017, 400.0002}}},
  90         {{{850.66843, 115.55563}, {728.515, 115.55563}, {725.21347, 275.15309},
  91                 {694.0017, 400.0002}}}
  92     }, {
  93         {{{1, 1},   {12.5, 6.5}, {-4, 6.5}, {7.5, 1}}},
  94         {{{1, 6.5}, {12.5, 1},   {-4, 1},   {.5, 6}}}
  95     }, {
  96         {{{315.748, 312.84}, {312.644, 318.134}, {305.836, 319.909}, {300.542, 316.804}}},
  97         {{{317.122, 309.05}, {316.112, 315.102}, {310.385, 319.19},  {304.332, 318.179}}}
  98     }, {
  99         {{{1046.604051, 172.937967},  {1046.604051, 178.9763059}, {1041.76745,  183.9279165}, {1035.703842, 184.0432409}}},
 100         {{{1046.452235, 174.7640504}, {1045.544872, 180.1973817}, {1040.837966, 184.0469882}, {1035.505925, 184.0469882}}}
 101     }, {
 102         {{{125.79356, 199.57382}, {51.16556, 128.93575}, {87.494,  16.67848}, {167.29361, 16.67848}}},
 103         {{{167.29361, 55.81876}, {100.36128, 55.81876}, {68.64099, 145.4755}, {125.7942, 199.57309}}}
 104     }, {
 105         {{{104.11546583642826, 370.21352558595504}, {122.96968232592344, 404.54489231839295},
 106           {169.90881005384728, 425.00067000000007}, {221.33045999999999, 425.00067000000001}}},
 107         {{{116.32365976159625, 381.71048540582598}, {103.86096590870899, 381.71048540581626},
 108           {91.394188003200725, 377.17917781762833}, {82.622283093355179, 368.11683661930334}}}
 109     }
 110 };
 111
 112 const size_t tests_count = SK_ARRAY_COUNT(tests);
 113
 114 const CubicPts lines[] = {
 115     {{{0, 0}, {0, 0}, {0, 0}, {1, 0}}},  // 0: horizontal
 116     {{{1, 0}, {0, 0}, {0, 0}, {0, 0}}},
 117     {{{1, 0}, {2, 0}, {3, 0}, {4, 0}}},
 118     {{{0, 0}, {0, 0}, {0, 0}, {0, 1}}},  // 5: vertical
 119     {{{0, 1}, {0, 0}, {0, 0}, {0, 0}}},
 120     {{{0, 1}, {0, 2}, {0, 3}, {0, 4}}},
 121     {{{0, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 10: 3 coincident
 122     {{{1, 1}, {0, 0}, {0, 0}, {0, 0}}},
 123     {{{0, 0}, {0, 0}, {1, 1}, {2, 2}}},  // 14: 2 coincident
 124     {{{0, 0}, {1, 1}, {0, 0}, {2, 2}}},
 125     {{{1, 1}, {0, 0}, {0, 0}, {2, 2}}},  // 17:
 126     {{{1, 1}, {0, 0}, {2, 2}, {0, 0}}},
 127     {{{1, 1}, {2, 2}, {0, 0}, {0, 0}}},
 128     {{{1, 1}, {2, 2}, {3, 3}, {2, 2}}},  // middle-last coincident
 129     {{{1, 1}, {2, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
 130     {{{1, 1}, {1, 1}, {2, 2}, {2, 2}}},  // 2 pairs coincident
 131     {{{1, 1}, {2, 2}, {1, 1}, {2, 2}}},
 132     {{{1, 1}, {1, 1}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
 133     {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}},  // no coincident
 134     {{{1, 1}, {3, 3}, {2, 2}, {4, 4}}},
 135     {{{1, 1}, {2, 2}, {4, 4}, {3, 3}}},
 136     {{{1, 1}, {3, 3}, {4, 4}, {2, 2}}},
 137     {{{1, 1}, {4, 4}, {2, 2}, {3, 3}}},
 138     {{{1, 1}, {4, 4}, {3, 3}, {2, 2}}},
 139     {{{2, 2}, {1, 1}, {3, 3}, {4, 4}}},
 140     {{{2, 2}, {1, 1}, {4, 4}, {3, 3}}},
 141     {{{2, 2}, {3, 3}, {1, 1}, {4, 4}}},
 142     {{{2, 2}, {3, 3}, {4, 4}, {1, 1}}},
 143     {{{2, 2}, {4, 4}, {1, 1}, {3, 3}}},
 144     {{{2, 2}, {4, 4}, {3, 3}, {1, 1}}},
 145 };
 146
 147 const size_t lines_count = SK_ARRAY_COUNT(lines);
 148
 149 // 'not a line' tries to fool the line detection code
 150 const CubicPts notLines[] = {
 151     {{{0, 0}, {0, 0}, {0, 1}, {1, 0}}},
 152     {{{0, 0}, {0, 1}, {0, 0}, {1, 0}}},
 153     {{{0, 0}, {0, 1}, {1, 0}, {0, 0}}},
 154     {{{0, 1}, {0, 0}, {0, 0}, {1, 0}}},
 155     {{{0, 1}, {0, 0}, {1, 0}, {0, 0}}},
 156     {{{0, 1}, {1, 0}, {0, 0}, {0, 0}}},
 157 };
 158
 159 const size_t notLines_count = SK_ARRAY_COUNT(notLines);
 160
 161 static const double E = FLT_EPSILON * 8;
 162 static const double F = FLT_EPSILON * 8;
 163
 164 const CubicPts modEpsilonLines[] = {
 165     {{{0, E}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal
 166     {{{0, 0}, {0, E}, {1, 0}, {0, 0}}},
 167     {{{0, 0}, {1, 0}, {0, E}, {0, 0}}},
 168     {{{1, 0}, {0, 0}, {0, 0}, {0, E}}},
 169     {{{1, E}, {2, 0}, {3, 0}, {4, 0}}},
 170     {{{E, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical
 171     {{{0, 0}, {E, 0}, {0, 1}, {0, 0}}},
 172     {{{0, 0}, {0, 1}, {E, 0}, {0, 0}}},
 173     {{{0, 1}, {0, 0}, {0, 0}, {E, 0}}},
 174     {{{E, 1}, {0, 2}, {0, 3}, {0, 4}}},
 175     {{{E, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident
 176     {{{0, 0}, {E, 0}, {1, 1}, {0, 0}}},
 177     {{{0, 0}, {1, 1}, {E, 0}, {0, 0}}},
 178     {{{1, 1}, {0, 0}, {0, 0}, {E, 0}}},
 179     {{{0, E}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident
 180     {{{0, 0}, {1, 1}, {0, E}, {2, 2}}},
 181     {{{0, 0}, {1, 1}, {2, 2}, {0, E}}},
 182     {{{1, 1}, {0, E}, {0, 0}, {2, 2}}},
 183     {{{1, 1}, {0, E}, {2, 2}, {0, 0}}},
 184     {{{1, 1}, {2, 2}, {E, 0}, {0, 0}}},
 185     {{{1, 1}, {2, 2+E}, {3, 3}, {2, 2}}},  // middle-last coincident
 186     {{{1, 1}, {2+E, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
 187     {{{1, 1}, {1, 1}, {2, 2}, {2+E, 2}}},  // 2 pairs coincident
 188     {{{1, 1}, {2, 2}, {1, 1}, {2+E, 2}}},
 189     {{{1, 1}, {2, 2}, {2, 2+E}, {1, 1}}},
 190     {{{1, 1}, {1, 1+E}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
 191     {{{1, 1}, {2+E, 2}, {3, 3}, {4, 4}}},  // no coincident
 192     {{{1, 1}, {3, 3}, {2, 2}, {4, 4+F+F}}},  // INVESTIGATE: why the epsilon is bigger
 193     {{{1, 1+F+F}, {2, 2}, {4, 4}, {3, 3}}},  // INVESTIGATE: why the epsilon is bigger
 194     {{{1, 1}, {3, 3}, {4, 4+E}, {2, 2}}},
 195     {{{1, 1}, {4, 4}, {2, 2}, {3, 3+E}}},
 196     {{{1, 1}, {4, 4}, {3, 3}, {2+E, 2}}},
 197     {{{2, 2}, {1, 1}, {3+E, 3}, {4, 4}}},
 198     {{{2, 2}, {1+E, 1}, {4, 4}, {3, 3}}},
 199     {{{2, 2+E}, {3, 3}, {1, 1}, {4, 4}}},
 200     {{{2+E, 2}, {3, 3}, {4, 4}, {1, 1}}},
 201     {{{2, 2}, {4+E, 4}, {1, 1}, {3, 3}}},
 202     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+E}}},
 203 };
 204
 205 const size_t modEpsilonLines_count = SK_ARRAY_COUNT(modEpsilonLines);
 206
 207 const CubicPts lessEpsilonLines[] = {
 208     {{{0, D}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal
 209     {{{1, 0}, {0, 0}, {0, 0}, {0, D}}},
 210     {{{1, D}, {2, 0}, {3, 0}, {4, 0}}},
 211     {{{D, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical
 212     {{{0, 1}, {0, 0}, {0, 0}, {D, 0}}},
 213     {{{D, 1}, {0, 2}, {0, 3}, {0, 4}}},
 214     {{{D, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident
 215     {{{1, 1}, {0, 0}, {0, 0}, {D, 0}}},
 216     {{{0, D}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident
 217     {{{0, 0}, {1, 1}, {0, D}, {2, 2}}},
 218     {{{0, 0}, {1, 1}, {2, 2}, {1, 1+D}}},
 219     {{{1, 1}, {0, D}, {0, 0}, {2, 2}}},
 220     {{{1, 1}, {0, D}, {2, 2}, {0, 0}}},
 221     {{{1, 1}, {2, 2}, {D, 0}, {0, 0}}},
 222     {{{1, 1}, {2, 2+D}, {3, 3}, {2, 2}}},  // middle-last coincident
 223     {{{1, 1}, {2+D, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
 224     {{{1, 1}, {1, 1}, {2, 2}, {2+D, 2}}},  // 2 pairs coincident
 225     {{{1, 1}, {2, 2}, {1, 1}, {2+D, 2}}},
 226     {{{1, 1}, {1, 1+D}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
 227     {{{1, 1}, {2+D/2, 2}, {3, 3}, {4, 4}}},  // no coincident (FIXME: N as opposed to N/2 failed)
 228     {{{1, 1}, {3, 3}, {2, 2}, {4, 4+D}}},
 229     {{{1, 1+D}, {2, 2}, {4, 4}, {3, 3}}},
 230     {{{1, 1}, {3, 3}, {4, 4+D}, {2, 2}}},
 231     {{{1, 1}, {4, 4}, {2, 2}, {3, 3+D}}},
 232     {{{1, 1}, {4, 4}, {3, 3}, {2+G, 2}}},  // INVESTIGATE: why the epsilon is smaller
 233     {{{2, 2}, {1, 1}, {3+D, 3}, {4, 4}}},
 234     {{{2, 2}, {1+D, 1}, {4, 4}, {3, 3}}},
 235     {{{2, 2+D}, {3, 3}, {1, 1}, {4, 4}}},
 236     {{{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is smaller
 237     {{{2, 2}, {4+D, 4}, {1, 1}, {3, 3}}},
 238     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+D}}},
 239 };
 240
 241 const size_t lessEpsilonLines_count = SK_ARRAY_COUNT(lessEpsilonLines);
 242
 243 const CubicPts negEpsilonLines[] = {
 244     {{{0, N}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal
 245     {{{1, 0}, {0, 0}, {0, 0}, {0, N}}},
 246     {{{1, N}, {2, 0}, {3, 0}, {4, 0}}},
 247     {{{N, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical
 248     {{{0, 1}, {0, 0}, {0, 0}, {N, 0}}},
 249     {{{N, 1}, {0, 2}, {0, 3}, {0, 4}}},
 250     {{{N, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident
 251     {{{1, 1}, {0, 0}, {0, 0}, {N, 0}}},
 252     {{{0, N}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident
 253     {{{0, 0}, {1, 1}, {0, N}, {2, 2}}},
 254     {{{0, 0}, {1, 1}, {2, 2}, {1, 1+N}}},
 255     {{{1, 1}, {0, N}, {0, 0}, {2, 2}}},
 256     {{{1, 1}, {0, N}, {2, 2}, {0, 0}}},
 257     {{{1, 1}, {2, 2}, {N, 0}, {0, 0}}},
 258     {{{1, 1}, {2, 2+N}, {3, 3}, {2, 2}}},  // middle-last coincident
 259     {{{1, 1}, {2+N, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
 260     {{{1, 1}, {1, 1}, {2, 2}, {2+N, 2}}},  // 2 pairs coincident
 261     {{{1, 1}, {2, 2}, {1, 1}, {2+N, 2}}},
 262     {{{1, 1}, {1, 1+N}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
 263     {{{1, 1}, {2+N/2, 2}, {3, 3}, {4, 4}}},  // no coincident (FIXME: N as opposed to N/2 failed)
 264     {{{1, 1}, {3, 3}, {2, 2}, {4, 4+N}}},
 265     {{{1, 1+N}, {2, 2}, {4, 4}, {3, 3}}},
 266     {{{1, 1}, {3, 3}, {4, 4+N}, {2, 2}}},
 267     {{{1, 1}, {4, 4}, {2, 2}, {3, 3+N}}},
 268     {{{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}},  // INVESTIGATE: why the epsilon is smaller
 269     {{{2, 2}, {1, 1}, {3+N, 3}, {4, 4}}},
 270     {{{2, 2}, {1+N, 1}, {4, 4}, {3, 3}}},
 271     {{{2, 2+N}, {3, 3}, {1, 1}, {4, 4}}},
 272     {{{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is smaller
 273     {{{2, 2}, {4+N, 4}, {1, 1}, {3, 3}}},
 274     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+N}}},
 275 };
 276
 277 const size_t negEpsilonLines_count = SK_ARRAY_COUNT(negEpsilonLines);
 278
 279 }  // namespace PathOpsCubicIntersectionTestData