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 "SkAddIntersections.h" 8 #include "SkPathOpsBounds.h" 9 10 #if DEBUG_ADD_INTERSECTING_TS 11 12 static void debugShowLineIntersection(int pts, const SkIntersectionHelper& wt, 13 const SkIntersectionHelper& wn, const SkIntersections& i) { 14 SkASSERT(i.used() == pts); 15 if (!pts) { 16 SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n", 17 __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); 18 return; 19 } 20 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, 21 i[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); 22 if (pts == 2) { 23 SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i[0][1], PT_DEBUG_DATA(i, 1)); 24 } 25 SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts())); 26 if (pts == 2) { 27 SkDebugf(" " T_DEBUG_STR(wnTs, 1), i[1][1]); 28 } 29 SkDebugf("\n"); 30 } 31 32 static void debugShowQuadLineIntersection(int pts, const SkIntersectionHelper& wt, 33 const SkIntersectionHelper& wn, 34 const SkIntersections& i) { 35 SkASSERT(i.used() == pts); 36 if (!pts) { 37 SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n", 38 __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); 39 return; 40 } 41 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, 42 i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); 43 for (int n = 1; n < pts; ++n) { 44 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); 45 } 46 SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts())); 47 for (int n = 1; n < pts; ++n) { 48 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); 49 } 50 SkDebugf("\n"); 51 } 52 53 static void debugShowQuadIntersection(int pts, const SkIntersectionHelper& wt, 54 const SkIntersectionHelper& wn, const SkIntersections& i) { 55 SkASSERT(i.used() == pts); 56 if (!pts) { 57 SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n", 58 __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts())); 59 return; 60 } 61 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, 62 i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); 63 for (int n = 1; n < pts; ++n) { 64 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); 65 } 66 SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts())); 67 for (int n = 1; n < pts; ++n) { 68 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); 69 } 70 SkDebugf("\n"); 71 } 72 73 static void debugShowCubicLineIntersection(int pts, const SkIntersectionHelper& wt, 74 const SkIntersectionHelper& wn, const SkIntersections& i) { 75 SkASSERT(i.used() == pts); 76 if (!pts) { 77 SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n", 78 __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); 79 return; 80 } 81 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, 82 i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); 83 for (int n = 1; n < pts; ++n) { 84 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); 85 } 86 SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts())); 87 for (int n = 1; n < pts; ++n) { 88 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); 89 } 90 SkDebugf("\n"); 91 } 92 93 static void debugShowCubicQuadIntersection(int pts, const SkIntersectionHelper& wt, 94 const SkIntersectionHelper& wn, const SkIntersections& i) { 95 SkASSERT(i.used() == pts); 96 if (!pts) { 97 SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n", 98 __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts())); 99 return; 100 } 101 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, 102 i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); 103 for (int n = 1; n < pts; ++n) { 104 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); 105 } 106 SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts())); 107 for (int n = 1; n < pts; ++n) { 108 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); 109 } 110 SkDebugf("\n"); 111 } 112 113 static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt, 114 const SkIntersectionHelper& wn, const SkIntersections& i) { 115 SkASSERT(i.used() == pts); 116 if (!pts) { 117 SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n", 118 __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts())); 119 return; 120 } 121 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, 122 i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); 123 for (int n = 1; n < pts; ++n) { 124 SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); 125 } 126 SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i[1][0], CUBIC_DEBUG_DATA(wn.pts())); 127 for (int n = 1; n < pts; ++n) { 128 SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); 129 } 130 SkDebugf("\n"); 131 } 132 133 static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt, 134 const SkIntersections& i) { 135 SkASSERT(i.used() == pts); 136 if (!pts) { 137 SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__, 138 CUBIC_DEBUG_DATA(wt.pts())); 139 return; 140 } 141 SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, 142 i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); 143 SkDebugf(" " T_DEBUG_STR(wtTs, 1), i[1][0]); 144 SkDebugf("\n"); 145 } 146 147 #else 148 static void debugShowLineIntersection(int , const SkIntersectionHelper& , 149 const SkIntersectionHelper& , const SkIntersections& ) { 150 } 151 152 static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& , 153 const SkIntersectionHelper& , const SkIntersections& ) { 154 } 155 156 static void debugShowQuadIntersection(int , const SkIntersectionHelper& , 157 const SkIntersectionHelper& , const SkIntersections& ) { 158 } 159 160 static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& , 161 const SkIntersectionHelper& , const SkIntersections& ) { 162 } 163 164 static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& , 165 const SkIntersectionHelper& , const SkIntersections& ) { 166 } 167 168 static void debugShowCubicIntersection(int , const SkIntersectionHelper& , 169 const SkIntersectionHelper& , const SkIntersections& ) { 170 } 171 172 static void debugShowCubicIntersection(int , const SkIntersectionHelper& , 173 const SkIntersections& ) { 174 } 175 #endif 176 177 bool AddIntersectTs(SkOpContour* test, SkOpContour* next) { 178 if (test != next) { 179 if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) { 180 return false; 181 } 182 // OPTIMIZATION: outset contour bounds a smidgen instead? 183 if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) { 184 return true; 185 } 186 } 187 SkIntersectionHelper wt; 188 wt.init(test); 189 bool foundCommonContour = test == next; 190 do { 191 SkIntersectionHelper wn; 192 wn.init(next); 193 if (test == next && !wn.startAfter(wt)) { 194 continue; 195 } 196 do { 197 if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) { 198 continue; 199 } 200 int pts = 0; 201 SkIntersections ts; 202 bool swap = false; 203 switch (wt.segmentType()) { 204 case SkIntersectionHelper::kHorizontalLine_Segment: 205 swap = true; 206 switch (wn.segmentType()) { 207 case SkIntersectionHelper::kHorizontalLine_Segment: 208 case SkIntersectionHelper::kVerticalLine_Segment: 209 case SkIntersectionHelper::kLine_Segment: { 210 pts = ts.lineHorizontal(wn.pts(), wt.left(), 211 wt.right(), wt.y(), wt.xFlipped()); 212 debugShowLineIntersection(pts, wn, wt, ts); 213 break; 214 } 215 case SkIntersectionHelper::kQuad_Segment: { 216 pts = ts.quadHorizontal(wn.pts(), wt.left(), 217 wt.right(), wt.y(), wt.xFlipped()); 218 debugShowQuadLineIntersection(pts, wn, wt, ts); 219 break; 220 } 221 case SkIntersectionHelper::kCubic_Segment: { 222 pts = ts.cubicHorizontal(wn.pts(), wt.left(), 223 wt.right(), wt.y(), wt.xFlipped()); 224 debugShowCubicLineIntersection(pts, wn, wt, ts); 225 break; 226 } 227 default: 228 SkASSERT(0); 229 } 230 break; 231 case SkIntersectionHelper::kVerticalLine_Segment: 232 swap = true; 233 switch (wn.segmentType()) { 234 case SkIntersectionHelper::kHorizontalLine_Segment: 235 case SkIntersectionHelper::kVerticalLine_Segment: 236 case SkIntersectionHelper::kLine_Segment: { 237 pts = ts.lineVertical(wn.pts(), wt.top(), 238 wt.bottom(), wt.x(), wt.yFlipped()); 239 debugShowLineIntersection(pts, wn, wt, ts); 240 break; 241 } 242 case SkIntersectionHelper::kQuad_Segment: { 243 pts = ts.quadVertical(wn.pts(), wt.top(), 244 wt.bottom(), wt.x(), wt.yFlipped()); 245 debugShowQuadLineIntersection(pts, wn, wt, ts); 246 break; 247 } 248 case SkIntersectionHelper::kCubic_Segment: { 249 pts = ts.cubicVertical(wn.pts(), wt.top(), 250 wt.bottom(), wt.x(), wt.yFlipped()); 251 debugShowCubicLineIntersection(pts, wn, wt, ts); 252 break; 253 } 254 default: 255 SkASSERT(0); 256 } 257 break; 258 case SkIntersectionHelper::kLine_Segment: 259 switch (wn.segmentType()) { 260 case SkIntersectionHelper::kHorizontalLine_Segment: 261 pts = ts.lineHorizontal(wt.pts(), wn.left(), 262 wn.right(), wn.y(), wn.xFlipped()); 263 debugShowLineIntersection(pts, wt, wn, ts); 264 break; 265 case SkIntersectionHelper::kVerticalLine_Segment: 266 pts = ts.lineVertical(wt.pts(), wn.top(), 267 wn.bottom(), wn.x(), wn.yFlipped()); 268 debugShowLineIntersection(pts, wt, wn, ts); 269 break; 270 case SkIntersectionHelper::kLine_Segment: { 271 pts = ts.lineLine(wt.pts(), wn.pts()); 272 debugShowLineIntersection(pts, wt, wn, ts); 273 break; 274 } 275 case SkIntersectionHelper::kQuad_Segment: { 276 swap = true; 277 pts = ts.quadLine(wn.pts(), wt.pts()); 278 debugShowQuadLineIntersection(pts, wn, wt, ts); 279 break; 280 } 281 case SkIntersectionHelper::kCubic_Segment: { 282 swap = true; 283 pts = ts.cubicLine(wn.pts(), wt.pts()); 284 debugShowCubicLineIntersection(pts, wn, wt, ts); 285 break; 286 } 287 default: 288 SkASSERT(0); 289 } 290 break; 291 case SkIntersectionHelper::kQuad_Segment: 292 switch (wn.segmentType()) { 293 case SkIntersectionHelper::kHorizontalLine_Segment: 294 pts = ts.quadHorizontal(wt.pts(), wn.left(), 295 wn.right(), wn.y(), wn.xFlipped()); 296 debugShowQuadLineIntersection(pts, wt, wn, ts); 297 break; 298 case SkIntersectionHelper::kVerticalLine_Segment: 299 pts = ts.quadVertical(wt.pts(), wn.top(), 300 wn.bottom(), wn.x(), wn.yFlipped()); 301 debugShowQuadLineIntersection(pts, wt, wn, ts); 302 break; 303 case SkIntersectionHelper::kLine_Segment: { 304 pts = ts.quadLine(wt.pts(), wn.pts()); 305 debugShowQuadLineIntersection(pts, wt, wn, ts); 306 break; 307 } 308 case SkIntersectionHelper::kQuad_Segment: { 309 pts = ts.quadQuad(wt.pts(), wn.pts()); 310 debugShowQuadIntersection(pts, wt, wn, ts); 311 break; 312 } 313 case SkIntersectionHelper::kCubic_Segment: { 314 swap = true; 315 pts = ts.cubicQuad(wn.pts(), wt.pts()); 316 debugShowCubicQuadIntersection(pts, wn, wt, ts); 317 break; 318 } 319 default: 320 SkASSERT(0); 321 } 322 break; 323 case SkIntersectionHelper::kCubic_Segment: 324 switch (wn.segmentType()) { 325 case SkIntersectionHelper::kHorizontalLine_Segment: 326 pts = ts.cubicHorizontal(wt.pts(), wn.left(), 327 wn.right(), wn.y(), wn.xFlipped()); 328 debugShowCubicLineIntersection(pts, wt, wn, ts); 329 break; 330 case SkIntersectionHelper::kVerticalLine_Segment: 331 pts = ts.cubicVertical(wt.pts(), wn.top(), 332 wn.bottom(), wn.x(), wn.yFlipped()); 333 debugShowCubicLineIntersection(pts, wt, wn, ts); 334 break; 335 case SkIntersectionHelper::kLine_Segment: { 336 pts = ts.cubicLine(wt.pts(), wn.pts()); 337 debugShowCubicLineIntersection(pts, wt, wn, ts); 338 break; 339 } 340 case SkIntersectionHelper::kQuad_Segment: { 341 pts = ts.cubicQuad(wt.pts(), wn.pts()); 342 debugShowCubicQuadIntersection(pts, wt, wn, ts); 343 break; 344 } 345 case SkIntersectionHelper::kCubic_Segment: { 346 pts = ts.cubicCubic(wt.pts(), wn.pts()); 347 debugShowCubicIntersection(pts, wt, wn, ts); 348 break; 349 } 350 default: 351 SkASSERT(0); 352 } 353 break; 354 default: 355 SkASSERT(0); 356 } 357 if (!foundCommonContour && pts > 0) { 358 test->addCross(next); 359 next->addCross(test); 360 foundCommonContour = true; 361 } 362 // in addition to recording T values, record matching segment 363 if (pts == 2) { 364 if (wn.segmentType() <= SkIntersectionHelper::kLine_Segment 365 && wt.segmentType() <= SkIntersectionHelper::kLine_Segment) { 366 if (wt.addCoincident(wn, ts, swap)) { 367 continue; 368 } 369 ts.cleanUpCoincidence(); // prefer (t == 0 or t == 1) 370 pts = 1; 371 } else if (wn.segmentType() >= SkIntersectionHelper::kQuad_Segment 372 && wt.segmentType() >= SkIntersectionHelper::kQuad_Segment 373 && ts.isCoincident(0)) { 374 SkASSERT(ts.coincidentUsed() == 2); 375 if (wt.addCoincident(wn, ts, swap)) { 376 continue; 377 } 378 ts.cleanUpCoincidence(); // prefer (t == 0 or t == 1) 379 pts = 1; 380 } 381 } 382 if (pts >= 2) { 383 for (int pt = 0; pt < pts - 1; ++pt) { 384 const SkDPoint& point = ts.pt(pt); 385 const SkDPoint& next = ts.pt(pt + 1); 386 if (wt.isPartial(ts[swap][pt], ts[swap][pt + 1], point, next) 387 && wn.isPartial(ts[!swap][pt], ts[!swap][pt + 1], point, next)) { 388 if (!wt.addPartialCoincident(wn, ts, pt, swap)) { 389 // remove extra point if two map to same float values 390 ts.cleanUpCoincidence(); // prefer (t == 0 or t == 1) 391 pts = 1; 392 } 393 } 394 } 395 } 396 for (int pt = 0; pt < pts; ++pt) { 397 SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1); 398 SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1); 399 SkPoint point = ts.pt(pt).asSkPoint(); 400 int testTAt = wt.addT(wn, point, ts[swap][pt]); 401 int nextTAt = wn.addT(wt, point, ts[!swap][pt]); 402 wt.addOtherT(testTAt, ts[!swap][pt], nextTAt); 403 wn.addOtherT(nextTAt, ts[swap][pt], testTAt); 404 } 405 } while (wn.advance()); 406 } while (wt.advance()); 407 return true; 408 } 409 410 void AddSelfIntersectTs(SkOpContour* test) { 411 SkIntersectionHelper wt; 412 wt.init(test); 413 do { 414 if (wt.segmentType() != SkIntersectionHelper::kCubic_Segment) { 415 continue; 416 } 417 SkIntersections ts; 418 int pts = ts.cubic(wt.pts()); 419 debugShowCubicIntersection(pts, wt, ts); 420 if (!pts) { 421 continue; 422 } 423 SkASSERT(pts == 1); 424 SkASSERT(ts[0][0] >= 0 && ts[0][0] <= 1); 425 SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1); 426 SkPoint point = ts.pt(0).asSkPoint(); 427 int testTAt = wt.addSelfT(wt, point, ts[0][0]); 428 int nextTAt = wt.addT(wt, point, ts[1][0]); 429 wt.addOtherT(testTAt, ts[1][0], nextTAt); 430 wt.addOtherT(nextTAt, ts[0][0], testTAt); 431 } while (wt.advance()); 432 } 433 434 // resolve any coincident pairs found while intersecting, and 435 // see if coincidence is formed by clipping non-concident segments 436 void CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total) { 437 int contourCount = (*contourList).count(); 438 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 439 SkOpContour* contour = (*contourList)[cIndex]; 440 contour->addCoincidentPoints(); 441 } 442 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 443 SkOpContour* contour = (*contourList)[cIndex]; 444 contour->calcCoincidentWinding(); 445 } 446 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 447 SkOpContour* contour = (*contourList)[cIndex]; 448 contour->calcPartialCoincidentWinding(); 449 } 450 } 451
