| OLD | NEW | 
|    1 /* |    1 /* | 
|    2  * Copyright 2012 Google Inc. |    2  * Copyright 2012 Google Inc. | 
|    3  * |    3  * | 
|    4  * Use of this source code is governed by a BSD-style license that can be |    4  * Use of this source code is governed by a BSD-style license that can be | 
|    5  * found in the LICENSE file. |    5  * found in the LICENSE file. | 
|    6  */ |    6  */ | 
|    7  |    7  | 
|    8 #include "PathOpsCubicIntersectionTestData.h" |    8 #include "PathOpsCubicIntersectionTestData.h" | 
|    9  |    9  | 
|   10 #include <limits> |   10 #include <limits> | 
|   11  |   11  | 
|   12 static const double D = FLT_EPSILON / 2; |   12 static const double D = FLT_EPSILON / 2; | 
|   13 static const double G = FLT_EPSILON / 3; |   13 static const double G = FLT_EPSILON / 3; | 
|   14 static const double N = -FLT_EPSILON / 2; |   14 static const double N = -FLT_EPSILON / 2; | 
|   15 static const double M = -FLT_EPSILON / 3; |   15 static const double M = -FLT_EPSILON / 3; | 
|   16  |   16  | 
|   17 const SkDCubic pointDegenerates[] = { |   17 const CubicPts pointDegenerates[] = { | 
|   18     {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}}, |   18     {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}}, | 
|   19     {{{1, 1}, {1, 1}, {1, 1}, {1, 1}}}, |   19     {{{1, 1}, {1, 1}, {1, 1}, {1, 1}}}, | 
|   20     {{{1 + FLT_EPSILON_HALF, 1}, {1, 1 + FLT_EPSILON_HALF}, {1, 1}, {1, 1}}}, |   20     {{{1 + FLT_EPSILON_HALF, 1}, {1, 1 + FLT_EPSILON_HALF}, {1, 1}, {1, 1}}}, | 
|   21     {{{1 + D, 1}, {1 - D, 1}, {1, 1}, {1, 1}}}, |   21     {{{1 + D, 1}, {1 - D, 1}, {1, 1}, {1, 1}}}, | 
|   22     {{{0, 0}, {0, 0}, {1, 0}, {0, 0}}}, |   22     {{{0, 0}, {0, 0}, {1, 0}, {0, 0}}}, | 
|   23     {{{0, 0}, {1, 0}, {0, 0}, {0, 0}}}, |   23     {{{0, 0}, {1, 0}, {0, 0}, {0, 0}}}, | 
|   24     {{{0, 0}, {0, 0}, {0, 1}, {0, 0}}}, |   24     {{{0, 0}, {0, 0}, {0, 1}, {0, 0}}}, | 
|   25     {{{0, 0}, {0, 1}, {0, 0}, {0, 0}}}, |   25     {{{0, 0}, {0, 1}, {0, 0}, {0, 0}}}, | 
|   26     {{{0, 0}, {0, 0}, {1, 1}, {0, 0}}}, |   26     {{{0, 0}, {0, 0}, {1, 1}, {0, 0}}}, | 
|   27     {{{0, 0}, {1, 1}, {0, 0}, {0, 0}}}, |   27     {{{0, 0}, {1, 1}, {0, 0}, {0, 0}}}, | 
| (...skipping 10 matching lines...) Expand all  Loading... | 
|   38     {{{0, 0}, {0, 1}, {N, 0}, {0, 0}}}, |   38     {{{0, 0}, {0, 1}, {N, 0}, {0, 0}}}, | 
|   39     {{{0, 0}, {1, 1}, {N, 0}, {0, 0}}}, |   39     {{{0, 0}, {1, 1}, {N, 0}, {0, 0}}}, | 
|   40     {{{0, 0}, {D, 0}, {1, 1}, {0, 0}}}, |   40     {{{0, 0}, {D, 0}, {1, 1}, {0, 0}}}, | 
|   41     {{{0, 0}, {1, 1}, {D, 0}, {0, 0}}}, |   41     {{{0, 0}, {1, 1}, {D, 0}, {0, 0}}}, | 
|   42     {{{0, 0}, {N, 0}, {1, 1}, {0, 0}}}, |   42     {{{0, 0}, {N, 0}, {1, 1}, {0, 0}}}, | 
|   43     {{{1, 1}, {2, 2}, {2, 2+N}, {1, 1}}}, |   43     {{{1, 1}, {2, 2}, {2, 2+N}, {1, 1}}}, | 
|   44 }; |   44 }; | 
|   45  |   45  | 
|   46 const size_t pointDegenerates_count = SK_ARRAY_COUNT(pointDegenerates); |   46 const size_t pointDegenerates_count = SK_ARRAY_COUNT(pointDegenerates); | 
|   47  |   47  | 
|   48 const SkDCubic notPointDegenerates[] = { |   48 const CubicPts notPointDegenerates[] = { | 
|   49     {{{1 + FLT_EPSILON * 8, 1}, {1, FLT_EPSILON * 8}, {1, 1}, {1, 1}}}, |   49     {{{1 + FLT_EPSILON * 8, 1}, {1, FLT_EPSILON * 8}, {1, 1}, {1, 1}}}, | 
|   50     {{{1 + FLT_EPSILON * 8, 1}, {1 - FLT_EPSILON * 8, 1}, {1, 1}, {1, 1}}} |   50     {{{1 + FLT_EPSILON * 8, 1}, {1 - FLT_EPSILON * 8, 1}, {1, 1}, {1, 1}}} | 
|   51 }; |   51 }; | 
|   52  |   52  | 
|   53 const size_t notPointDegenerates_count = |   53 const size_t notPointDegenerates_count = | 
|   54         SK_ARRAY_COUNT(notPointDegenerates); |   54         SK_ARRAY_COUNT(notPointDegenerates); | 
|   55  |   55  | 
|   56 // from http://www.truetex.com/bezint.htm |   56 // from http://www.truetex.com/bezint.htm | 
|   57 const SkDCubic tests[][2] = { |   57 const CubicPts tests[][2] = { | 
|   58     {  // intersects in one place (data gives bezier clip fits |   58     {  // intersects in one place (data gives bezier clip fits | 
|   59      {{{0, 45}, |   59      {{{0, 45}, | 
|   60       {6.0094158284751593, 51.610357411322688}, |   60       {6.0094158284751593, 51.610357411322688}, | 
|   61       {12.741093228940867, 55.981703949474607}, |   61       {12.741093228940867, 55.981703949474607}, | 
|   62       {20.021417396476362, 58.652245509710262}}}, |   62       {20.021417396476362, 58.652245509710262}}}, | 
|   63      {{{2.2070737699246674, 52.703494107327209}, |   63      {{{2.2070737699246674, 52.703494107327209}, | 
|   64       {31.591482272629477, 23.811002295222025}, |   64       {31.591482272629477, 23.811002295222025}, | 
|   65       {76.824588616426425, 44.049473790502674}, |   65       {76.824588616426425, 44.049473790502674}, | 
|   66       {119.25488947221436, 55.599248272955073}}} |   66       {119.25488947221436, 55.599248272955073}}} | 
|   67     }, {  // intersects in three places |   67     }, {  // intersects in three places | 
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
|  102     }, { |  102     }, { | 
|  103         {{{104.11546583642826, 370.21352558595504}, {122.96968232592344, 404.544
     89231839295}, |  103         {{{104.11546583642826, 370.21352558595504}, {122.96968232592344, 404.544
     89231839295}, | 
|  104           {169.90881005384728, 425.00067000000007}, {221.33045999999999, 425.000
     67000000001}}}, |  104           {169.90881005384728, 425.00067000000007}, {221.33045999999999, 425.000
     67000000001}}}, | 
|  105         {{{116.32365976159625, 381.71048540582598}, {103.86096590870899, 381.710
     48540581626}, |  105         {{{116.32365976159625, 381.71048540582598}, {103.86096590870899, 381.710
     48540581626}, | 
|  106           {91.394188003200725, 377.17917781762833}, {82.622283093355179, 368.116
     83661930334}}} |  106           {91.394188003200725, 377.17917781762833}, {82.622283093355179, 368.116
     83661930334}}} | 
|  107     } |  107     } | 
|  108 }; |  108 }; | 
|  109  |  109  | 
|  110 const size_t tests_count = SK_ARRAY_COUNT(tests); |  110 const size_t tests_count = SK_ARRAY_COUNT(tests); | 
|  111  |  111  | 
|  112 const SkDCubic lines[] = { |  112 const CubicPts lines[] = { | 
|  113     {{{0, 0}, {0, 0}, {0, 0}, {1, 0}}},  // 0: horizontal |  113     {{{0, 0}, {0, 0}, {0, 0}, {1, 0}}},  // 0: horizontal | 
|  114     {{{1, 0}, {0, 0}, {0, 0}, {0, 0}}}, |  114     {{{1, 0}, {0, 0}, {0, 0}, {0, 0}}}, | 
|  115     {{{1, 0}, {2, 0}, {3, 0}, {4, 0}}}, |  115     {{{1, 0}, {2, 0}, {3, 0}, {4, 0}}}, | 
|  116     {{{0, 0}, {0, 0}, {0, 0}, {0, 1}}},  // 5: vertical |  116     {{{0, 0}, {0, 0}, {0, 0}, {0, 1}}},  // 5: vertical | 
|  117     {{{0, 1}, {0, 0}, {0, 0}, {0, 0}}}, |  117     {{{0, 1}, {0, 0}, {0, 0}, {0, 0}}}, | 
|  118     {{{0, 1}, {0, 2}, {0, 3}, {0, 4}}}, |  118     {{{0, 1}, {0, 2}, {0, 3}, {0, 4}}}, | 
|  119     {{{0, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 10: 3 coincident |  119     {{{0, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 10: 3 coincident | 
|  120     {{{1, 1}, {0, 0}, {0, 0}, {0, 0}}}, |  120     {{{1, 1}, {0, 0}, {0, 0}, {0, 0}}}, | 
|  121     {{{0, 0}, {0, 0}, {1, 1}, {2, 2}}},  // 14: 2 coincident |  121     {{{0, 0}, {0, 0}, {1, 1}, {2, 2}}},  // 14: 2 coincident | 
|  122     {{{0, 0}, {1, 1}, {0, 0}, {2, 2}}}, |  122     {{{0, 0}, {1, 1}, {0, 0}, {2, 2}}}, | 
| (...skipping 15 matching lines...) Expand all  Loading... | 
|  138     {{{2, 2}, {1, 1}, {4, 4}, {3, 3}}}, |  138     {{{2, 2}, {1, 1}, {4, 4}, {3, 3}}}, | 
|  139     {{{2, 2}, {3, 3}, {1, 1}, {4, 4}}}, |  139     {{{2, 2}, {3, 3}, {1, 1}, {4, 4}}}, | 
|  140     {{{2, 2}, {3, 3}, {4, 4}, {1, 1}}}, |  140     {{{2, 2}, {3, 3}, {4, 4}, {1, 1}}}, | 
|  141     {{{2, 2}, {4, 4}, {1, 1}, {3, 3}}}, |  141     {{{2, 2}, {4, 4}, {1, 1}, {3, 3}}}, | 
|  142     {{{2, 2}, {4, 4}, {3, 3}, {1, 1}}}, |  142     {{{2, 2}, {4, 4}, {3, 3}, {1, 1}}}, | 
|  143 }; |  143 }; | 
|  144  |  144  | 
|  145 const size_t lines_count = SK_ARRAY_COUNT(lines); |  145 const size_t lines_count = SK_ARRAY_COUNT(lines); | 
|  146  |  146  | 
|  147 // 'not a line' tries to fool the line detection code |  147 // 'not a line' tries to fool the line detection code | 
|  148 const SkDCubic notLines[] = { |  148 const CubicPts notLines[] = { | 
|  149     {{{0, 0}, {0, 0}, {0, 1}, {1, 0}}}, |  149     {{{0, 0}, {0, 0}, {0, 1}, {1, 0}}}, | 
|  150     {{{0, 0}, {0, 1}, {0, 0}, {1, 0}}}, |  150     {{{0, 0}, {0, 1}, {0, 0}, {1, 0}}}, | 
|  151     {{{0, 0}, {0, 1}, {1, 0}, {0, 0}}}, |  151     {{{0, 0}, {0, 1}, {1, 0}, {0, 0}}}, | 
|  152     {{{0, 1}, {0, 0}, {0, 0}, {1, 0}}}, |  152     {{{0, 1}, {0, 0}, {0, 0}, {1, 0}}}, | 
|  153     {{{0, 1}, {0, 0}, {1, 0}, {0, 0}}}, |  153     {{{0, 1}, {0, 0}, {1, 0}, {0, 0}}}, | 
|  154     {{{0, 1}, {1, 0}, {0, 0}, {0, 0}}}, |  154     {{{0, 1}, {1, 0}, {0, 0}, {0, 0}}}, | 
|  155 }; |  155 }; | 
|  156  |  156  | 
|  157 const size_t notLines_count = SK_ARRAY_COUNT(notLines); |  157 const size_t notLines_count = SK_ARRAY_COUNT(notLines); | 
|  158  |  158  | 
|  159 static const double E = FLT_EPSILON * 8; |  159 static const double E = FLT_EPSILON * 8; | 
|  160 static const double F = FLT_EPSILON * 8; |  160 static const double F = FLT_EPSILON * 8; | 
|  161  |  161  | 
|  162 const SkDCubic modEpsilonLines[] = { |  162 const CubicPts modEpsilonLines[] = { | 
|  163     {{{0, E}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal |  163     {{{0, E}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal | 
|  164     {{{0, 0}, {0, E}, {1, 0}, {0, 0}}}, |  164     {{{0, 0}, {0, E}, {1, 0}, {0, 0}}}, | 
|  165     {{{0, 0}, {1, 0}, {0, E}, {0, 0}}}, |  165     {{{0, 0}, {1, 0}, {0, E}, {0, 0}}}, | 
|  166     {{{1, 0}, {0, 0}, {0, 0}, {0, E}}}, |  166     {{{1, 0}, {0, 0}, {0, 0}, {0, E}}}, | 
|  167     {{{1, E}, {2, 0}, {3, 0}, {4, 0}}}, |  167     {{{1, E}, {2, 0}, {3, 0}, {4, 0}}}, | 
|  168     {{{E, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical |  168     {{{E, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical | 
|  169     {{{0, 0}, {E, 0}, {0, 1}, {0, 0}}}, |  169     {{{0, 0}, {E, 0}, {0, 1}, {0, 0}}}, | 
|  170     {{{0, 0}, {0, 1}, {E, 0}, {0, 0}}}, |  170     {{{0, 0}, {0, 1}, {E, 0}, {0, 0}}}, | 
|  171     {{{0, 1}, {0, 0}, {0, 0}, {E, 0}}}, |  171     {{{0, 1}, {0, 0}, {0, 0}, {E, 0}}}, | 
|  172     {{{E, 1}, {0, 2}, {0, 3}, {0, 4}}}, |  172     {{{E, 1}, {0, 2}, {0, 3}, {0, 4}}}, | 
| (...skipping 22 matching lines...) Expand all  Loading... | 
|  195     {{{2, 2}, {1, 1}, {3+E, 3}, {4, 4}}}, |  195     {{{2, 2}, {1, 1}, {3+E, 3}, {4, 4}}}, | 
|  196     {{{2, 2}, {1+E, 1}, {4, 4}, {3, 3}}}, |  196     {{{2, 2}, {1+E, 1}, {4, 4}, {3, 3}}}, | 
|  197     {{{2, 2+E}, {3, 3}, {1, 1}, {4, 4}}}, |  197     {{{2, 2+E}, {3, 3}, {1, 1}, {4, 4}}}, | 
|  198     {{{2+E, 2}, {3, 3}, {4, 4}, {1, 1}}}, |  198     {{{2+E, 2}, {3, 3}, {4, 4}, {1, 1}}}, | 
|  199     {{{2, 2}, {4+E, 4}, {1, 1}, {3, 3}}}, |  199     {{{2, 2}, {4+E, 4}, {1, 1}, {3, 3}}}, | 
|  200     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+E}}}, |  200     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+E}}}, | 
|  201 }; |  201 }; | 
|  202  |  202  | 
|  203 const size_t modEpsilonLines_count = SK_ARRAY_COUNT(modEpsilonLines); |  203 const size_t modEpsilonLines_count = SK_ARRAY_COUNT(modEpsilonLines); | 
|  204  |  204  | 
|  205 const SkDCubic lessEpsilonLines[] = { |  205 const CubicPts lessEpsilonLines[] = { | 
|  206     {{{0, D}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal |  206     {{{0, D}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal | 
|  207     {{{1, 0}, {0, 0}, {0, 0}, {0, D}}}, |  207     {{{1, 0}, {0, 0}, {0, 0}, {0, D}}}, | 
|  208     {{{1, D}, {2, 0}, {3, 0}, {4, 0}}}, |  208     {{{1, D}, {2, 0}, {3, 0}, {4, 0}}}, | 
|  209     {{{D, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical |  209     {{{D, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical | 
|  210     {{{0, 1}, {0, 0}, {0, 0}, {D, 0}}}, |  210     {{{0, 1}, {0, 0}, {0, 0}, {D, 0}}}, | 
|  211     {{{D, 1}, {0, 2}, {0, 3}, {0, 4}}}, |  211     {{{D, 1}, {0, 2}, {0, 3}, {0, 4}}}, | 
|  212     {{{D, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident |  212     {{{D, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident | 
|  213     {{{1, 1}, {0, 0}, {0, 0}, {D, 0}}}, |  213     {{{1, 1}, {0, 0}, {0, 0}, {D, 0}}}, | 
|  214     {{{0, D}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident |  214     {{{0, D}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident | 
|  215     {{{0, 0}, {1, 1}, {0, D}, {2, 2}}}, |  215     {{{0, 0}, {1, 1}, {0, D}, {2, 2}}}, | 
| (...skipping 15 matching lines...) Expand all  Loading... | 
|  231     {{{2, 2}, {1, 1}, {3+D, 3}, {4, 4}}}, |  231     {{{2, 2}, {1, 1}, {3+D, 3}, {4, 4}}}, | 
|  232     {{{2, 2}, {1+D, 1}, {4, 4}, {3, 3}}}, |  232     {{{2, 2}, {1+D, 1}, {4, 4}, {3, 3}}}, | 
|  233     {{{2, 2+D}, {3, 3}, {1, 1}, {4, 4}}}, |  233     {{{2, 2+D}, {3, 3}, {1, 1}, {4, 4}}}, | 
|  234     {{{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is sm
     aller |  234     {{{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is sm
     aller | 
|  235     {{{2, 2}, {4+D, 4}, {1, 1}, {3, 3}}}, |  235     {{{2, 2}, {4+D, 4}, {1, 1}, {3, 3}}}, | 
|  236     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+D}}}, |  236     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+D}}}, | 
|  237 }; |  237 }; | 
|  238  |  238  | 
|  239 const size_t lessEpsilonLines_count = SK_ARRAY_COUNT(lessEpsilonLines); |  239 const size_t lessEpsilonLines_count = SK_ARRAY_COUNT(lessEpsilonLines); | 
|  240  |  240  | 
|  241 const SkDCubic negEpsilonLines[] = { |  241 const CubicPts negEpsilonLines[] = { | 
|  242     {{{0, N}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal |  242     {{{0, N}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal | 
|  243     {{{1, 0}, {0, 0}, {0, 0}, {0, N}}}, |  243     {{{1, 0}, {0, 0}, {0, 0}, {0, N}}}, | 
|  244     {{{1, N}, {2, 0}, {3, 0}, {4, 0}}}, |  244     {{{1, N}, {2, 0}, {3, 0}, {4, 0}}}, | 
|  245     {{{N, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical |  245     {{{N, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical | 
|  246     {{{0, 1}, {0, 0}, {0, 0}, {N, 0}}}, |  246     {{{0, 1}, {0, 0}, {0, 0}, {N, 0}}}, | 
|  247     {{{N, 1}, {0, 2}, {0, 3}, {0, 4}}}, |  247     {{{N, 1}, {0, 2}, {0, 3}, {0, 4}}}, | 
|  248     {{{N, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident |  248     {{{N, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident | 
|  249     {{{1, 1}, {0, 0}, {0, 0}, {N, 0}}}, |  249     {{{1, 1}, {0, 0}, {0, 0}, {N, 0}}}, | 
|  250     {{{0, N}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident |  250     {{{0, N}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident | 
|  251     {{{0, 0}, {1, 1}, {0, N}, {2, 2}}}, |  251     {{{0, 0}, {1, 1}, {0, N}, {2, 2}}}, | 
| (...skipping 14 matching lines...) Expand all  Loading... | 
|  266     {{{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}},  // INVESTIGATE: why the epsilon is sm
     aller |  266     {{{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}},  // INVESTIGATE: why the epsilon is sm
     aller | 
|  267     {{{2, 2}, {1, 1}, {3+N, 3}, {4, 4}}}, |  267     {{{2, 2}, {1, 1}, {3+N, 3}, {4, 4}}}, | 
|  268     {{{2, 2}, {1+N, 1}, {4, 4}, {3, 3}}}, |  268     {{{2, 2}, {1+N, 1}, {4, 4}, {3, 3}}}, | 
|  269     {{{2, 2+N}, {3, 3}, {1, 1}, {4, 4}}}, |  269     {{{2, 2+N}, {3, 3}, {1, 1}, {4, 4}}}, | 
|  270     {{{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is sm
     aller |  270     {{{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is sm
     aller | 
|  271     {{{2, 2}, {4+N, 4}, {1, 1}, {3, 3}}}, |  271     {{{2, 2}, {4+N, 4}, {1, 1}, {3, 3}}}, | 
|  272     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+N}}}, |  272     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+N}}}, | 
|  273 }; |  273 }; | 
|  274  |  274  | 
|  275 const size_t negEpsilonLines_count = SK_ARRAY_COUNT(negEpsilonLines); |  275 const size_t negEpsilonLines_count = SK_ARRAY_COUNT(negEpsilonLines); | 
| OLD | NEW |