| 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 |