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 (test->bounds().fBottom < next->bounds().fTop) { 180 return false; 181 } 182 if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) { 183 return true; 184 } 185 } 186 SkIntersectionHelper wt; 187 wt.init(test); 188 bool foundCommonContour = test == next; 189 do { 190 SkIntersectionHelper wn; 191 wn.init(next); 192 if (test == next && !wn.startAfter(wt)) { 193 continue; 194 } 195 do { 196 if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) { 197 continue; 198 } 199 int pts = 0; 200 SkIntersections ts; 201 bool swap = false; 202 switch (wt.segmentType()) { 203 case SkIntersectionHelper::kHorizontalLine_Segment: 204 swap = true; 205 switch (wn.segmentType()) { 206 case SkIntersectionHelper::kHorizontalLine_Segment: 207 case SkIntersectionHelper::kVerticalLine_Segment: 208 case SkIntersectionHelper::kLine_Segment: { 209 pts = ts.lineHorizontal(wn.pts(), wt.left(), 210 wt.right(), wt.y(), wt.xFlipped()); 211 debugShowLineIntersection(pts, wn, wt, ts); 212 break; 213 } 214 case SkIntersectionHelper::kQuad_Segment: { 215 pts = ts.quadHorizontal(wn.pts(), wt.left(), 216 wt.right(), wt.y(), wt.xFlipped()); 217 debugShowQuadLineIntersection(pts, wn, wt, ts); 218 break; 219 } 220 case SkIntersectionHelper::kCubic_Segment: { 221 pts = ts.cubicHorizontal(wn.pts(), wt.left(), 222 wt.right(), wt.y(), wt.xFlipped()); 223 debugShowCubicLineIntersection(pts, wn, wt, ts); 224 break; 225 } 226 default: 227 SkASSERT(0); 228 } 229 break; 230 case SkIntersectionHelper::kVerticalLine_Segment: 231 swap = true; 232 switch (wn.segmentType()) { 233 case SkIntersectionHelper::kHorizontalLine_Segment: 234 case SkIntersectionHelper::kVerticalLine_Segment: 235 case SkIntersectionHelper::kLine_Segment: { 236 pts = ts.lineVertical(wn.pts(), wt.top(), 237 wt.bottom(), wt.x(), wt.yFlipped()); 238 debugShowLineIntersection(pts, wn, wt, ts); 239 break; 240 } 241 case SkIntersectionHelper::kQuad_Segment: { 242 pts = ts.quadVertical(wn.pts(), wt.top(), 243 wt.bottom(), wt.x(), wt.yFlipped()); 244 debugShowQuadLineIntersection(pts, wn, wt, ts); 245 break; 246 } 247 case SkIntersectionHelper::kCubic_Segment: { 248 pts = ts.cubicVertical(wn.pts(), wt.top(), 249 wt.bottom(), wt.x(), wt.yFlipped()); 250 debugShowCubicLineIntersection(pts, wn, wt, ts); 251 break; 252 } 253 default: 254 SkASSERT(0); 255 } 256 break; 257 case SkIntersectionHelper::kLine_Segment: 258 switch (wn.segmentType()) { 259 case SkIntersectionHelper::kHorizontalLine_Segment: 260 pts = ts.lineHorizontal(wt.pts(), wn.left(), 261 wn.right(), wn.y(), wn.xFlipped()); 262 debugShowLineIntersection(pts, wt, wn, ts); 263 break; 264 case SkIntersectionHelper::kVerticalLine_Segment: 265 pts = ts.lineVertical(wt.pts(), wn.top(), 266 wn.bottom(), wn.x(), wn.yFlipped()); 267 debugShowLineIntersection(pts, wt, wn, ts); 268 break; 269 case SkIntersectionHelper::kLine_Segment: { 270 pts = ts.lineLine(wt.pts(), wn.pts()); 271 debugShowLineIntersection(pts, wt, wn, ts); 272 break; 273 } 274 case SkIntersectionHelper::kQuad_Segment: { 275 swap = true; 276 pts = ts.quadLine(wn.pts(), wt.pts()); 277 debugShowQuadLineIntersection(pts, wn, wt, ts); 278 break; 279 } 280 case SkIntersectionHelper::kCubic_Segment: { 281 swap = true; 282 pts = ts.cubicLine(wn.pts(), wt.pts()); 283 debugShowCubicLineIntersection(pts, wn, wt, ts); 284 break; 285 } 286 default: 287 SkASSERT(0); 288 } 289 break; 290 case SkIntersectionHelper::kQuad_Segment: 291 switch (wn.segmentType()) { 292 case SkIntersectionHelper::kHorizontalLine_Segment: 293 pts = ts.quadHorizontal(wt.pts(), wn.left(), 294 wn.right(), wn.y(), wn.xFlipped()); 295 debugShowQuadLineIntersection(pts, wt, wn, ts); 296 break; 297 case SkIntersectionHelper::kVerticalLine_Segment: 298 pts = ts.quadVertical(wt.pts(), wn.top(), 299 wn.bottom(), wn.x(), wn.yFlipped()); 300 debugShowQuadLineIntersection(pts, wt, wn, ts); 301 break; 302 case SkIntersectionHelper::kLine_Segment: { 303 pts = ts.quadLine(wt.pts(), wn.pts()); 304 debugShowQuadLineIntersection(pts, wt, wn, ts); 305 break; 306 } 307 case SkIntersectionHelper::kQuad_Segment: { 308 pts = ts.quadQuad(wt.pts(), wn.pts()); 309 debugShowQuadIntersection(pts, wt, wn, ts); 310 break; 311 } 312 case SkIntersectionHelper::kCubic_Segment: { 313 swap = true; 314 pts = ts.cubicQuad(wn.pts(), wt.pts()); 315 debugShowCubicQuadIntersection(pts, wn, wt, ts); 316 break; 317 } 318 default: 319 SkASSERT(0); 320 } 321 break; 322 case SkIntersectionHelper::kCubic_Segment: 323 switch (wn.segmentType()) { 324 case SkIntersectionHelper::kHorizontalLine_Segment: 325 pts = ts.cubicHorizontal(wt.pts(), wn.left(), 326 wn.right(), wn.y(), wn.xFlipped()); 327 debugShowCubicLineIntersection(pts, wt, wn, ts); 328 break; 329 case SkIntersectionHelper::kVerticalLine_Segment: 330 pts = ts.cubicVertical(wt.pts(), wn.top(), 331 wn.bottom(), wn.x(), wn.yFlipped()); 332 debugShowCubicLineIntersection(pts, wt, wn, ts); 333 break; 334 case SkIntersectionHelper::kLine_Segment: { 335 pts = ts.cubicLine(wt.pts(), wn.pts()); 336 debugShowCubicLineIntersection(pts, wt, wn, ts); 337 break; 338 } 339 case SkIntersectionHelper::kQuad_Segment: { 340 pts = ts.cubicQuad(wt.pts(), wn.pts()); 341 debugShowCubicQuadIntersection(pts, wt, wn, ts); 342 break; 343 } 344 case SkIntersectionHelper::kCubic_Segment: { 345 pts = ts.cubicCubic(wt.pts(), wn.pts()); 346 debugShowCubicIntersection(pts, wt, wn, ts); 347 break; 348 } 349 default: 350 SkASSERT(0); 351 } 352 break; 353 default: 354 SkASSERT(0); 355 } 356 if (!foundCommonContour && pts > 0) { 357 test->addCross(next); 358 next->addCross(test); 359 foundCommonContour = true; 360 } 361 // in addition to recording T values, record matching segment 362 if (pts == 2) { 363 if (wn.segmentType() <= SkIntersectionHelper::kLine_Segment 364 && wt.segmentType() <= SkIntersectionHelper::kLine_Segment) { 365 wt.addCoincident(wn, ts, swap); 366 continue; 367 } 368 if (wn.segmentType() >= SkIntersectionHelper::kQuad_Segment 369 && wt.segmentType() >= SkIntersectionHelper::kQuad_Segment 370 && ts.isCoincident(0)) { 371 SkASSERT(ts.coincidentUsed() == 2); 372 wt.addCoincident(wn, ts, swap); 373 continue; 374 } 375 } 376 for (int pt = 0; pt < pts; ++pt) { 377 SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1); 378 SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1); 379 SkPoint point = ts.pt(pt).asSkPoint(); 380 int testTAt = wt.addT(wn, point, ts[swap][pt]); 381 int nextTAt = wn.addT(wt, point, ts[!swap][pt]); 382 wt.addOtherT(testTAt, ts[!swap][pt], nextTAt); 383 wn.addOtherT(nextTAt, ts[swap][pt], testTAt); 384 } 385 } while (wn.advance()); 386 } while (wt.advance()); 387 return true; 388 } 389 390 void AddSelfIntersectTs(SkOpContour* test) { 391 SkIntersectionHelper wt; 392 wt.init(test); 393 do { 394 if (wt.segmentType() != SkIntersectionHelper::kCubic_Segment) { 395 continue; 396 } 397 SkIntersections ts; 398 int pts = ts.cubic(wt.pts()); 399 debugShowCubicIntersection(pts, wt, ts); 400 if (!pts) { 401 continue; 402 } 403 SkASSERT(pts == 1); 404 SkASSERT(ts[0][0] >= 0 && ts[0][0] <= 1); 405 SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1); 406 SkPoint point = ts.pt(0).asSkPoint(); 407 int testTAt = wt.addSelfT(wt, point, ts[0][0]); 408 int nextTAt = wt.addT(wt, point, ts[1][0]); 409 wt.addOtherT(testTAt, ts[1][0], nextTAt); 410 wt.addOtherT(nextTAt, ts[0][0], testTAt); 411 } while (wt.advance()); 412 } 413 414 // resolve any coincident pairs found while intersecting, and 415 // see if coincidence is formed by clipping non-concident segments 416 void CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total) { 417 int contourCount = (*contourList).count(); 418 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 419 SkOpContour* contour = (*contourList)[cIndex]; 420 contour->addCoincidentPoints(); 421 } 422 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 423 SkOpContour* contour = (*contourList)[cIndex]; 424 contour->calcCoincidentWinding(); 425 } 426 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 427 SkOpContour* contour = (*contourList)[cIndex]; 428 contour->findTooCloseToCall(); 429 } 430 } 431
