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 "CurveIntersection.h" 8 #include "Intersection_Tests.h" 9 #include "IntersectionUtilities.h" 10 11 const Cubic convex[] = { 12 {{0, 0}, {2, 0}, {2, 1}, {0, 1}}, 13 {{1, 0}, {1, 1}, {0, 1}, {0, 0}}, 14 {{1, 1}, {0, 1}, {0, 0}, {1, 0}}, 15 {{0, 1}, {0, 0}, {1, 0}, {1, 1}}, 16 {{0, 0}, {10, 0}, {10, 10}, {5, 6}}, 17 }; 18 19 size_t convex_count = sizeof(convex) / sizeof(convex[0]); 20 21 const Cubic bowtie[] = { 22 {{0, 0}, {1, 1}, {1, 0}, {0, 1}}, 23 {{1, 0}, {0, 1}, {1, 1}, {0, 0}}, 24 {{1, 1}, {0, 0}, {0, 1}, {1, 0}}, 25 {{0, 1}, {1, 0}, {0, 0}, {1, 1}}, 26 }; 27 28 size_t bowtie_count = sizeof(bowtie) / sizeof(bowtie[0]); 29 30 const Cubic arrow[] = { 31 {{0, 0}, {10, 0}, {10, 10}, {5, 4}}, 32 {{10, 0}, {10, 10}, {5, 4}, {0, 0}}, 33 {{10, 10}, {5, 4}, {0, 0}, {10, 0}}, 34 {{5, 4}, {0, 0}, {10, 0}, {10, 10}}, 35 }; 36 37 size_t arrow_count = sizeof(arrow) / sizeof(arrow[0]); 38 39 const Cubic three[] = { 40 {{1, 0}, {1, 0}, {1, 1}, {0, 1}}, // 0 == 1 41 {{0, 0}, {1, 1}, {1, 1}, {0, 1}}, // 1 == 2 42 {{0, 0}, {1, 0}, {0, 1}, {0, 1}}, // 2 == 3 43 {{1, 0}, {1, 1}, {1, 0}, {0, 1}}, // 0 == 2 44 {{1, 0}, {1, 1}, {0, 1}, {1, 0}}, // 0 == 3 45 {{0, 0}, {1, 0}, {1, 1}, {1, 0}}, // 1 == 3 46 }; 47 48 size_t three_count = sizeof(three) / sizeof(three[0]); 49 50 const Cubic triangle[] = { 51 {{0, 0}, {1, 0}, {2, 0}, {0, 1}}, // extra point on horz 52 {{1, 0}, {2, 0}, {0, 1}, {0, 0}}, 53 {{2, 0}, {0, 1}, {0, 0}, {1, 0}}, 54 {{0, 1}, {0, 0}, {1, 0}, {2, 0}}, 55 56 {{0, 0}, {0, 1}, {0, 2}, {1, 1}}, // extra point on vert 57 {{0, 1}, {0, 2}, {1, 1}, {0, 0}}, 58 {{0, 2}, {1, 1}, {0, 0}, {0, 1}}, 59 {{1, 1}, {0, 0}, {0, 1}, {0, 2}}, 60 61 {{0, 0}, {1, 1}, {2, 2}, {2, 0}}, // extra point on diag 62 {{1, 1}, {2, 2}, {2, 0}, {0, 0}}, 63 {{2, 2}, {2, 0}, {0, 0}, {1, 1}}, 64 {{2, 0}, {0, 0}, {1, 1}, {2, 2}}, 65 66 {{0, 0}, {2, 0}, {2, 2}, {1, 1}}, // extra point on diag 67 {{2, 0}, {2, 2}, {1, 1}, {0, 0}}, 68 {{2, 2}, {1, 1}, {0, 0}, {2, 0}}, 69 {{1, 1}, {0, 0}, {2, 0}, {2, 2}}, 70 }; 71 72 size_t triangle_count = sizeof(triangle) / sizeof(triangle[0]); 73 74 const struct CubicDataSet { 75 const Cubic* data; 76 size_t size; 77 } cubicDataSet[] = { 78 { three, three_count }, 79 { convex, convex_count }, 80 { bowtie, bowtie_count }, 81 { arrow, arrow_count }, 82 { triangle, triangle_count }, 83 }; 84 85 size_t cubicDataSet_count = sizeof(cubicDataSet) / sizeof(cubicDataSet[0]); 86 87 typedef double Matrix3x2[3][2]; 88 89 static bool rotateToAxis(const _Point& a, const _Point& b, Matrix3x2& matrix) { 90 double dx = b.x - a.x; 91 double dy = b.y - a.y; 92 double length = sqrt(dx * dx + dy * dy); 93 if (length == 0) { 94 return false; 95 } 96 double invLength = 1 / length; 97 matrix[0][0] = dx * invLength; 98 matrix[1][0] = dy * invLength; 99 matrix[2][0] = 0; 100 matrix[0][1] = -dy * invLength; 101 matrix[1][1] = dx * invLength; 102 matrix[2][1] = 0; 103 return true; 104 } 105 106 static void transform(const Cubic& cubic, const Matrix3x2& matrix, Cubic& rotPath) { 107 for (int index = 0; index < 4; ++index) { 108 rotPath[index].x = cubic[index].x * matrix[0][0] 109 + cubic[index].y * matrix[1][0] + matrix[2][0]; 110 rotPath[index].y = cubic[index].x * matrix[0][1] 111 + cubic[index].y * matrix[1][1] + matrix[2][1]; 112 } 113 } 114 115 // brute force way to find convex hull: 116 // pick two points 117 // rotate all four until the two points are horizontal 118 // are the remaining two points both above or below the horizontal line? 119 // if so, the two points must be an edge of the convex hull 120 static int rotate_to_hull(const Cubic& cubic, char order[4], size_t idx, size_t inr) { 121 bool debug_rotate_to_hull = false; 122 int outsidePtSet[4]; 123 memset(outsidePtSet, -1, sizeof(outsidePtSet)); 124 for (int outer = 0; outer < 3; ++outer) { 125 for (int priorOuter = 0; priorOuter < outer; ++priorOuter) { 126 if (cubic[outer].approximatelyEqual(cubic[priorOuter])) { 127 goto skip; 128 } 129 } 130 for (int inner = outer + 1; inner < 4; ++inner) { 131 for (int priorInner = outer + 1; priorInner < inner; ++priorInner) { 132 if (cubic[inner].approximatelyEqual(cubic[priorInner])) { 133 goto skipInner; 134 } 135 } 136 if (cubic[outer].approximatelyEqual(cubic[inner])) { 137 continue; 138 } 139 Matrix3x2 matrix; 140 if (!rotateToAxis(cubic[outer], cubic[inner], matrix)) { 141 continue; 142 } 143 Cubic rotPath; 144 transform(cubic, matrix, rotPath); 145 int sides[3]; 146 int zeroes; 147 zeroes = -1; 148 bzero(sides, sizeof(sides)); 149 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] src=(%g,%g) rot=", __FUNCTION__, 150 (int)idx, (int)inr, (int)outer, (int)inner, 151 cubic[inner].x, cubic[inner].y); 152 for (int index = 0; index < 4; ++index) { 153 if (debug_rotate_to_hull) SkDebugf("(%g,%g) ", rotPath[index].x, rotPath[index].y); 154 sides[side(rotPath[index].y - rotPath[inner].y)]++; 155 if (index != outer && index != inner 156 && side(rotPath[index].y - rotPath[inner].y) == 1) 157 zeroes = index; 158 } 159 if (debug_rotate_to_hull) SkDebugf("sides=(%d,%d,%d)\n", sides[0], sides[1], sides[2]); 160 if (sides[0] && sides[2]) { 161 continue; 162 } 163 if (sides[1] == 3 && zeroes >= 0) { 164 // verify that third point is between outer, inner 165 // if either of remaining two equals outer or equal, pick lower 166 if (rotPath[zeroes].approximatelyEqual(rotPath[inner]) 167 && zeroes < inner) { 168 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] zeroes < inner\n", 169 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner); 170 continue; 171 } 172 if (rotPath[zeroes].approximatelyEqual(rotPath[outer]) 173 && zeroes < outer) { 174 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] zeroes < outer\n", 175 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner); 176 continue; 177 } 178 if (rotPath[zeroes].x < rotPath[inner].x 179 && rotPath[zeroes].x < rotPath[outer].x) { 180 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] zeroes < inner && outer\n", 181 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner); 182 continue; 183 } 184 if (rotPath[zeroes].x > rotPath[inner].x 185 && rotPath[zeroes].x > rotPath[outer].x) { 186 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] zeroes > inner && outer\n", 187 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner); 188 continue; 189 } 190 } 191 if (outsidePtSet[outer] < 0) { 192 outsidePtSet[outer] = inner; 193 } else { 194 if (outsidePtSet[inner] > 0) { 195 if (debug_rotate_to_hull) SkDebugf("%s [%d,%d] [o=%d,i=%d] too many rays from one point\n", 196 __FUNCTION__, (int)idx, (int)inr, (int)outer, (int)inner); 197 } 198 outsidePtSet[inner] = outer; 199 } 200 skipInner: 201 ; 202 } 203 skip: 204 ; 205 } 206 int totalSides = 0; 207 int first = 0; 208 for (; first < 4; ++first) { 209 if (outsidePtSet[first] >= 0) { 210 break; 211 } 212 } 213 if (first > 3) { 214 order[0] = 0; 215 return 1; 216 } 217 int next = first; 218 do { 219 order[totalSides++] = next; 220 next = outsidePtSet[next]; 221 } while (next != -1 && next != first); 222 return totalSides; 223 } 224 225 int firstIndex = 0; 226 int firstInner = 0; 227 228 void ConvexHull_Test() { 229 for (size_t index = firstIndex; index < cubicDataSet_count; ++index) { 230 const CubicDataSet& set = cubicDataSet[index]; 231 for (size_t inner = firstInner; inner < set.size; ++inner) { 232 const Cubic& cubic = set.data[inner]; 233 char order[4], cmpOrder[4]; 234 int cmp = rotate_to_hull(cubic, cmpOrder, index, inner); 235 if (cmp < 3) { 236 continue; 237 } 238 int result = convex_hull(cubic, order); 239 if (cmp != result) { 240 SkDebugf("%s [%d,%d] result=%d cmp=%d\n", __FUNCTION__, 241 (int)index, (int)inner, result, cmp); 242 continue; 243 } 244 // check for same indices 245 char pts = 0; 246 char cmpPts = 0; 247 int pt, bit; 248 for (pt = 0; pt < cmp; ++pt) { 249 if (pts & 1 << order[pt]) { 250 SkDebugf("%s [%d,%d] duplicate index in order: %d,%d,%d", 251 __FUNCTION__, (int)index, (int)inner, 252 order[0], order[1], order[2]); 253 if (cmp == 4) { 254 SkDebugf(",%d", order[3]); 255 } 256 SkDebugf("\n"); 257 goto next; 258 } 259 if (cmpPts & 1 << cmpOrder[pt]) { 260 SkDebugf("%s [%d,%d] duplicate index in order: %d,%d,%d", 261 __FUNCTION__, (int)index, (int)inner, 262 cmpOrder[0], cmpOrder[1], cmpOrder[2]); 263 if (cmp == 4) { 264 SkDebugf(",%d", cmpOrder[3]); 265 } 266 SkDebugf("\n"); 267 goto next; 268 } 269 pts |= 1 << order[pt]; 270 cmpPts |= 1 << cmpOrder[pt]; 271 } 272 for (bit = 0; bit < 4; ++bit) { 273 if (pts & 1 << bit) { 274 continue; 275 } 276 for (pt = 0; pt < cmp; ++pt) { 277 if (order[pt] == bit) { 278 continue; 279 } 280 if (cubic[order[pt]] == cubic[bit]) { 281 pts |= 1 << bit; 282 } 283 } 284 } 285 for (bit = 0; bit < 4; ++bit) { 286 if (cmpPts & 1 << bit) { 287 continue; 288 } 289 for (pt = 0; pt < cmp; ++pt) { 290 if (cmpOrder[pt] == bit) { 291 continue; 292 } 293 if (cubic[cmpOrder[pt]] == cubic[bit]) { 294 cmpPts |= 1 << bit; 295 } 296 } 297 } 298 if (pts != cmpPts) { 299 SkDebugf("%s [%d,%d] mismatch indices: order=%d,%d,%d", 300 __FUNCTION__, (int)index, (int)inner, 301 order[0], order[1], order[2]); 302 if (cmp == 4) { 303 SkDebugf(",%d", order[3]); 304 } 305 SkDebugf(" cmpOrder=%d,%d,%d", cmpOrder[0], cmpOrder[1], cmpOrder[2]); 306 if (cmp == 4) { 307 SkDebugf(",%d", cmpOrder[3]); 308 } 309 SkDebugf("\n"); 310 continue; 311 } 312 if (cmp == 4) { // check for bow ties 313 int match = 0; 314 while (cmpOrder[match] != order[0]) { 315 ++match; 316 } 317 if (cmpOrder[match ^ 2] != order[2]) { 318 SkDebugf("%s [%d,%d] bowtie mismatch: order=%d,%d,%d,%d" 319 " cmpOrder=%d,%d,%d,%d\n", 320 __FUNCTION__, (int)index, (int)inner, 321 order[0], order[1], order[2], order[3], 322 cmpOrder[0], cmpOrder[1], cmpOrder[2], cmpOrder[3]); 323 } 324 } 325 next: 326 ; 327 } 328 } 329 } 330 331 const double a = 1.0/3; 332 const double b = 2.0/3; 333 334 const Cubic x_cubic[] = { 335 {{0, 0}, {a, 0}, {b, 0}, {1, 0}}, // 0 336 {{0, 0}, {a, 0}, {b, 0}, {1, 1}}, // 1 337 {{0, 0}, {a, 0}, {b, 1}, {1, 0}}, // 2 338 {{0, 0}, {a, 0}, {b, 1}, {1, 1}}, // 3 339 {{0, 0}, {a, 1}, {b, 0}, {1, 0}}, // 4 340 {{0, 0}, {a, 1}, {b, 0}, {1, 1}}, // 5 341 {{0, 0}, {a, 1}, {b, 1}, {1, 0}}, // 6 342 {{0, 0}, {a, 1}, {b, 1}, {1, 1}}, // 7 343 {{0, 1}, {a, 0}, {b, 0}, {1, 0}}, // 8 344 {{0, 1}, {a, 0}, {b, 0}, {1, 1}}, // 9 345 {{0, 1}, {a, 0}, {b, 1}, {1, 0}}, // 10 346 {{0, 1}, {a, 0}, {b, 1}, {1, 1}}, // 11 347 {{0, 1}, {a, 1}, {b, 0}, {1, 0}}, // 12 348 {{0, 1}, {a, 1}, {b, 0}, {1, 1}}, // 13 349 {{0, 1}, {a, 1}, {b, 1}, {1, 0}}, // 14 350 {{0, 1}, {a, 1}, {b, 1}, {1, 1}}, // 15 351 }; 352 353 size_t x_cubic_count = sizeof(x_cubic) / sizeof(x_cubic[0]); 354 355 static int first_x_test = 0; 356 357 void ConvexHull_X_Test() { 358 for (size_t index = first_x_test; index < x_cubic_count; ++index) { 359 const Cubic& cubic = x_cubic[index]; 360 char connectTo0[2] = {-1, -1}; 361 char connectTo3[2] = {-1, -1}; 362 convex_x_hull(cubic, connectTo0, connectTo3); 363 int idx, cmp; 364 for (idx = 0; idx < 2; ++idx) { 365 if (connectTo0[idx] >= 1 && connectTo0[idx] < 4) { 366 continue; 367 } else { 368 SkDebugf("%s connectTo0[idx]=%d", __FUNCTION__, connectTo0[idx]); 369 } 370 if (connectTo3[idx] >= 0 && connectTo3[idx] < 3) { 371 continue; 372 } else { 373 SkDebugf("%s connectTo3[idx]=%d", __FUNCTION__, connectTo3[idx]); 374 } 375 goto nextTest; 376 } 377 char rOrder[4]; 378 char cmpOrder[4]; 379 cmp = rotate_to_hull(cubic, cmpOrder, index, 0); 380 if (index == 0 || index == 15) { 381 // FIXME: make rotate_to_hull work for degenerate 2 edge hull cases 382 cmpOrder[0] = 0; 383 cmpOrder[1] = 3; 384 cmp = 2; 385 } 386 if (cmp < 3) { 387 // FIXME: make rotate_to_hull work for index == 3 etc 388 continue; 389 } 390 for (idx = 0; idx < cmp; ++idx) { 391 if (cmpOrder[idx] == 0) { 392 rOrder[0] = cmpOrder[(idx + 1) % cmp]; 393 rOrder[1] = cmpOrder[(idx + cmp - 1) % cmp]; 394 } else if (cmpOrder[idx] == 3) { 395 rOrder[2] = cmpOrder[(idx + 1) % cmp]; 396 rOrder[3] = cmpOrder[(idx + cmp - 1) % cmp]; 397 } 398 } 399 if (connectTo0[0] != connectTo0[1]) { 400 if (rOrder[0] == rOrder[1]) { 401 SkDebugf("%s [%d] (1) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 402 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 403 connectTo3[0], connectTo3[1], 404 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 405 continue; 406 } 407 int unused = 6 - connectTo0[0] - connectTo0[1]; 408 int rUnused = 6 - rOrder[0] - rOrder[1]; 409 if (unused != rUnused) { 410 SkDebugf("%s [%d] (2) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 411 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 412 connectTo3[0], connectTo3[1], 413 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 414 continue; 415 } 416 } else { 417 if (rOrder[0] != rOrder[1]) { 418 SkDebugf("%s [%d] (3) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 419 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 420 connectTo3[0], connectTo3[1], 421 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 422 continue; 423 } 424 if (connectTo0[0] != rOrder[0]) { 425 SkDebugf("%s [%d] (4) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 426 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 427 connectTo3[0], connectTo3[1], 428 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 429 continue; 430 } 431 } 432 if (connectTo3[0] != connectTo3[1]) { 433 if (rOrder[2] == rOrder[3]) { 434 SkDebugf("%s [%d] (5) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 435 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 436 connectTo3[0], connectTo3[1], 437 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 438 continue; 439 } 440 int unused = 6 - connectTo3[0] - connectTo3[1]; 441 int rUnused = 6 - rOrder[2] - rOrder[3]; 442 if (unused != rUnused) { 443 SkDebugf("%s [%d] (6) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 444 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 445 connectTo3[0], connectTo3[1], 446 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 447 continue; 448 } 449 } else { 450 if (rOrder[2] != rOrder[3]) { 451 SkDebugf("%s [%d] (7) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 452 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 453 connectTo3[0], connectTo3[1], 454 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 455 continue; 456 } 457 if (connectTo3[1] != rOrder[3]) { 458 SkDebugf("%s [%d] (8) order=(%d,%d,%d,%d) r_order=(%d,%d,%d,%d)\n", 459 __FUNCTION__, (int)index, connectTo0[0], connectTo0[1], 460 connectTo3[0], connectTo3[1], 461 rOrder[0], rOrder[1], rOrder[2], rOrder[3]); 462 continue; 463 } 464 } 465 nextTest: 466 ; 467 } 468 } 469
