caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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" |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 8 | #include "SkOpCoincidence.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 9 | #include "SkPathOpsBounds.h" |
| 10 | |
| 11 | #if DEBUG_ADD_INTERSECTING_TS |
| 12 | |
| 13 | static void debugShowLineIntersection(int pts, const SkIntersectionHelper& wt, |
| 14 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 15 | SkASSERT(i.used() == pts); |
| 16 | if (!pts) { |
| 17 | SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n", |
| 18 | __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); |
| 19 | return; |
| 20 | } |
| 21 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 22 | i[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); |
| 23 | if (pts == 2) { |
| 24 | SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i[0][1], PT_DEBUG_DATA(i, 1)); |
| 25 | } |
| 26 | SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts())); |
| 27 | if (pts == 2) { |
| 28 | SkDebugf(" " T_DEBUG_STR(wnTs, 1), i[1][1]); |
| 29 | } |
| 30 | SkDebugf("\n"); |
| 31 | } |
| 32 | |
| 33 | static void debugShowQuadLineIntersection(int pts, const SkIntersectionHelper& wt, |
| 34 | const SkIntersectionHelper& wn, |
| 35 | const SkIntersections& i) { |
| 36 | SkASSERT(i.used() == pts); |
| 37 | if (!pts) { |
| 38 | SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n", |
| 39 | __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); |
| 40 | return; |
| 41 | } |
| 42 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 43 | i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); |
| 44 | for (int n = 1; n < pts; ++n) { |
| 45 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 46 | } |
| 47 | SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts())); |
| 48 | for (int n = 1; n < pts; ++n) { |
| 49 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 50 | } |
| 51 | SkDebugf("\n"); |
| 52 | } |
| 53 | |
| 54 | static void debugShowQuadIntersection(int pts, const SkIntersectionHelper& wt, |
| 55 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 56 | SkASSERT(i.used() == pts); |
| 57 | if (!pts) { |
| 58 | SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n", |
| 59 | __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts())); |
| 60 | return; |
| 61 | } |
| 62 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 63 | i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); |
| 64 | for (int n = 1; n < pts; ++n) { |
| 65 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 66 | } |
| 67 | SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts())); |
| 68 | for (int n = 1; n < pts; ++n) { |
| 69 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 70 | } |
| 71 | SkDebugf("\n"); |
| 72 | } |
| 73 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 74 | static void debugShowConicLineIntersection(int pts, const SkIntersectionHelper& wt, |
| 75 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 76 | SkASSERT(i.used() == pts); |
| 77 | if (!pts) { |
| 78 | SkDebugf("%s no intersect " CONIC_DEBUG_STR " " LINE_DEBUG_STR "\n", |
| 79 | __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()), LINE_DEBUG_DATA(wn.pts())); |
| 80 | return; |
| 81 | } |
| 82 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 83 | i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0)); |
| 84 | for (int n = 1; n < pts; ++n) { |
| 85 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 86 | } |
| 87 | SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts())); |
| 88 | for (int n = 1; n < pts; ++n) { |
| 89 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 90 | } |
| 91 | SkDebugf("\n"); |
| 92 | } |
| 93 | |
| 94 | static void debugShowConicQuadIntersection(int pts, const SkIntersectionHelper& wt, |
| 95 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 96 | SkASSERT(i.used() == pts); |
| 97 | if (!pts) { |
| 98 | SkDebugf("%s no intersect " CONIC_DEBUG_STR " " QUAD_DEBUG_STR "\n", |
| 99 | __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()), QUAD_DEBUG_DATA(wn.pts())); |
| 100 | return; |
| 101 | } |
| 102 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 103 | i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0)); |
| 104 | for (int n = 1; n < pts; ++n) { |
| 105 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 106 | } |
| 107 | SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts())); |
| 108 | for (int n = 1; n < pts; ++n) { |
| 109 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 110 | } |
| 111 | SkDebugf("\n"); |
| 112 | } |
| 113 | |
| 114 | static void debugShowConicIntersection(int pts, const SkIntersectionHelper& wt, |
| 115 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 116 | SkASSERT(i.used() == pts); |
| 117 | if (!pts) { |
| 118 | SkDebugf("%s no intersect " CONIC_DEBUG_STR " " CONIC_DEBUG_STR "\n", |
| 119 | __FUNCTION__, CONIC_DEBUG_DATA(wt.pts(), wt.weight()), |
| 120 | CONIC_DEBUG_DATA(wn.pts(), wn.weight())); |
| 121 | return; |
| 122 | } |
| 123 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CONIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 124 | i[0][0], CONIC_DEBUG_DATA(wt.pts(), wt.weight()), PT_DEBUG_DATA(i, 0)); |
| 125 | for (int n = 1; n < pts; ++n) { |
| 126 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 127 | } |
| 128 | SkDebugf(" wnTs[0]=%g " CONIC_DEBUG_STR, i[1][0], CONIC_DEBUG_DATA(wn.pts(), wn.weight())); |
| 129 | for (int n = 1; n < pts; ++n) { |
| 130 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 131 | } |
| 132 | SkDebugf("\n"); |
| 133 | } |
| 134 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 135 | static void debugShowCubicLineIntersection(int pts, const SkIntersectionHelper& wt, |
| 136 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 137 | SkASSERT(i.used() == pts); |
| 138 | if (!pts) { |
| 139 | SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n", |
| 140 | __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts())); |
| 141 | return; |
| 142 | } |
| 143 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 144 | i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); |
| 145 | for (int n = 1; n < pts; ++n) { |
| 146 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 147 | } |
| 148 | SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts())); |
| 149 | for (int n = 1; n < pts; ++n) { |
| 150 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 151 | } |
| 152 | SkDebugf("\n"); |
| 153 | } |
| 154 | |
| 155 | static void debugShowCubicQuadIntersection(int pts, const SkIntersectionHelper& wt, |
| 156 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 157 | SkASSERT(i.used() == pts); |
| 158 | if (!pts) { |
| 159 | SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n", |
| 160 | __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts())); |
| 161 | return; |
| 162 | } |
| 163 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 164 | i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); |
| 165 | for (int n = 1; n < pts; ++n) { |
| 166 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 167 | } |
| 168 | SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts())); |
| 169 | for (int n = 1; n < pts; ++n) { |
| 170 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 171 | } |
| 172 | SkDebugf("\n"); |
| 173 | } |
| 174 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 175 | static void debugShowCubicConicIntersection(int pts, const SkIntersectionHelper& wt, |
| 176 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 177 | SkASSERT(i.used() == pts); |
| 178 | if (!pts) { |
| 179 | SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CONIC_DEBUG_STR "\n", |
| 180 | __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CONIC_DEBUG_DATA(wn.pts(), wn.weight())); |
| 181 | return; |
| 182 | } |
| 183 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 184 | i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); |
| 185 | for (int n = 1; n < pts; ++n) { |
| 186 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 187 | } |
| 188 | SkDebugf(" wnTs[0]=%g " CONIC_DEBUG_STR, i[1][0], CONIC_DEBUG_DATA(wn.pts(), wn.weight())); |
| 189 | for (int n = 1; n < pts; ++n) { |
| 190 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 191 | } |
| 192 | SkDebugf("\n"); |
| 193 | } |
| 194 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 195 | static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt, |
| 196 | const SkIntersectionHelper& wn, const SkIntersections& i) { |
| 197 | SkASSERT(i.used() == pts); |
| 198 | if (!pts) { |
| 199 | SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n", |
| 200 | __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts())); |
| 201 | return; |
| 202 | } |
| 203 | SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__, |
| 204 | i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0)); |
| 205 | for (int n = 1; n < pts; ++n) { |
| 206 | SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n)); |
| 207 | } |
| 208 | SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i[1][0], CUBIC_DEBUG_DATA(wn.pts())); |
| 209 | for (int n = 1; n < pts; ++n) { |
| 210 | SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]); |
| 211 | } |
| 212 | SkDebugf("\n"); |
| 213 | } |
| 214 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 215 | #else |
| 216 | static void debugShowLineIntersection(int , const SkIntersectionHelper& , |
| 217 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 218 | } |
| 219 | |
| 220 | static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& , |
| 221 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 222 | } |
| 223 | |
| 224 | static void debugShowQuadIntersection(int , const SkIntersectionHelper& , |
| 225 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 226 | } |
| 227 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 228 | static void debugShowConicLineIntersection(int , const SkIntersectionHelper& , |
| 229 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 230 | } |
| 231 | |
| 232 | static void debugShowConicQuadIntersection(int , const SkIntersectionHelper& , |
| 233 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 234 | } |
| 235 | |
| 236 | static void debugShowConicIntersection(int , const SkIntersectionHelper& , |
| 237 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 238 | } |
| 239 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 240 | static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& , |
| 241 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 242 | } |
| 243 | |
| 244 | static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& , |
| 245 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 246 | } |
| 247 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 248 | static void debugShowCubicConicIntersection(int , const SkIntersectionHelper& , |
| 249 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 250 | } |
| 251 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 252 | static void debugShowCubicIntersection(int , const SkIntersectionHelper& , |
| 253 | const SkIntersectionHelper& , const SkIntersections& ) { |
| 254 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 255 | #endif |
| 256 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 257 | bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coincidence, |
| 258 | SkChunkAlloc* allocator) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 259 | if (test != next) { |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 260 | if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 261 | return false; |
| 262 | } |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 263 | // OPTIMIZATION: outset contour bounds a smidgen instead? |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 264 | if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) { |
| 265 | return true; |
| 266 | } |
| 267 | } |
| 268 | SkIntersectionHelper wt; |
| 269 | wt.init(test); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 270 | do { |
| 271 | SkIntersectionHelper wn; |
| 272 | wn.init(next); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 273 | test->debugValidate(); |
| 274 | next->debugValidate(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 275 | if (test == next && !wn.startAfter(wt)) { |
| 276 | continue; |
| 277 | } |
| 278 | do { |
| 279 | if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) { |
| 280 | continue; |
| 281 | } |
| 282 | int pts = 0; |
| 283 | SkIntersections ts; |
| 284 | bool swap = false; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 285 | SkDQuad quad1, quad2; |
| 286 | SkDConic conic1, conic2; |
| 287 | SkDCubic cubic1, cubic2; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 288 | switch (wt.segmentType()) { |
| 289 | case SkIntersectionHelper::kHorizontalLine_Segment: |
| 290 | swap = true; |
| 291 | switch (wn.segmentType()) { |
| 292 | case SkIntersectionHelper::kHorizontalLine_Segment: |
| 293 | case SkIntersectionHelper::kVerticalLine_Segment: |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 294 | case SkIntersectionHelper::kLine_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 295 | pts = ts.lineHorizontal(wn.pts(), wt.left(), |
| 296 | wt.right(), wt.y(), wt.xFlipped()); |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 297 | debugShowLineIntersection(pts, wn, wt, ts); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 298 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 299 | case SkIntersectionHelper::kQuad_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 300 | pts = ts.quadHorizontal(wn.pts(), wt.left(), |
| 301 | wt.right(), wt.y(), wt.xFlipped()); |
| 302 | debugShowQuadLineIntersection(pts, wn, wt, ts); |
| 303 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 304 | case SkIntersectionHelper::kConic_Segment: |
| 305 | pts = ts.conicHorizontal(wn.pts(), wn.weight(), wt.left(), |
| 306 | wt.right(), wt.y(), wt.xFlipped()); |
| 307 | debugShowConicLineIntersection(pts, wn, wt, ts); |
| 308 | break; |
| 309 | case SkIntersectionHelper::kCubic_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 310 | pts = ts.cubicHorizontal(wn.pts(), wt.left(), |
| 311 | wt.right(), wt.y(), wt.xFlipped()); |
| 312 | debugShowCubicLineIntersection(pts, wn, wt, ts); |
| 313 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 314 | default: |
| 315 | SkASSERT(0); |
| 316 | } |
| 317 | break; |
| 318 | case SkIntersectionHelper::kVerticalLine_Segment: |
| 319 | swap = true; |
| 320 | switch (wn.segmentType()) { |
| 321 | case SkIntersectionHelper::kHorizontalLine_Segment: |
| 322 | case SkIntersectionHelper::kVerticalLine_Segment: |
| 323 | case SkIntersectionHelper::kLine_Segment: { |
| 324 | pts = ts.lineVertical(wn.pts(), wt.top(), |
| 325 | wt.bottom(), wt.x(), wt.yFlipped()); |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 326 | debugShowLineIntersection(pts, wn, wt, ts); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 327 | break; |
| 328 | } |
| 329 | case SkIntersectionHelper::kQuad_Segment: { |
| 330 | pts = ts.quadVertical(wn.pts(), wt.top(), |
| 331 | wt.bottom(), wt.x(), wt.yFlipped()); |
| 332 | debugShowQuadLineIntersection(pts, wn, wt, ts); |
| 333 | break; |
| 334 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 335 | case SkIntersectionHelper::kConic_Segment: { |
| 336 | pts = ts.conicVertical(wn.pts(), wn.weight(), wt.top(), |
| 337 | wt.bottom(), wt.x(), wt.yFlipped()); |
| 338 | debugShowConicLineIntersection(pts, wn, wt, ts); |
| 339 | break; |
| 340 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 341 | case SkIntersectionHelper::kCubic_Segment: { |
| 342 | pts = ts.cubicVertical(wn.pts(), wt.top(), |
| 343 | wt.bottom(), wt.x(), wt.yFlipped()); |
| 344 | debugShowCubicLineIntersection(pts, wn, wt, ts); |
| 345 | break; |
| 346 | } |
| 347 | default: |
| 348 | SkASSERT(0); |
| 349 | } |
| 350 | break; |
| 351 | case SkIntersectionHelper::kLine_Segment: |
| 352 | switch (wn.segmentType()) { |
| 353 | case SkIntersectionHelper::kHorizontalLine_Segment: |
| 354 | pts = ts.lineHorizontal(wt.pts(), wn.left(), |
| 355 | wn.right(), wn.y(), wn.xFlipped()); |
| 356 | debugShowLineIntersection(pts, wt, wn, ts); |
| 357 | break; |
| 358 | case SkIntersectionHelper::kVerticalLine_Segment: |
| 359 | pts = ts.lineVertical(wt.pts(), wn.top(), |
| 360 | wn.bottom(), wn.x(), wn.yFlipped()); |
| 361 | debugShowLineIntersection(pts, wt, wn, ts); |
| 362 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 363 | case SkIntersectionHelper::kLine_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 364 | pts = ts.lineLine(wt.pts(), wn.pts()); |
| 365 | debugShowLineIntersection(pts, wt, wn, ts); |
| 366 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 367 | case SkIntersectionHelper::kQuad_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 368 | swap = true; |
| 369 | pts = ts.quadLine(wn.pts(), wt.pts()); |
| 370 | debugShowQuadLineIntersection(pts, wn, wt, ts); |
| 371 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 372 | case SkIntersectionHelper::kConic_Segment: |
| 373 | swap = true; |
| 374 | pts = ts.conicLine(wn.pts(), wn.weight(), wt.pts()); |
| 375 | debugShowConicLineIntersection(pts, wn, wt, ts); |
| 376 | break; |
| 377 | case SkIntersectionHelper::kCubic_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 378 | swap = true; |
| 379 | pts = ts.cubicLine(wn.pts(), wt.pts()); |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 380 | debugShowCubicLineIntersection(pts, wn, wt, ts); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 381 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 382 | default: |
| 383 | SkASSERT(0); |
| 384 | } |
| 385 | break; |
| 386 | case SkIntersectionHelper::kQuad_Segment: |
| 387 | switch (wn.segmentType()) { |
| 388 | case SkIntersectionHelper::kHorizontalLine_Segment: |
| 389 | pts = ts.quadHorizontal(wt.pts(), wn.left(), |
| 390 | wn.right(), wn.y(), wn.xFlipped()); |
| 391 | debugShowQuadLineIntersection(pts, wt, wn, ts); |
| 392 | break; |
| 393 | case SkIntersectionHelper::kVerticalLine_Segment: |
| 394 | pts = ts.quadVertical(wt.pts(), wn.top(), |
| 395 | wn.bottom(), wn.x(), wn.yFlipped()); |
| 396 | debugShowQuadLineIntersection(pts, wt, wn, ts); |
| 397 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 398 | case SkIntersectionHelper::kLine_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 399 | pts = ts.quadLine(wt.pts(), wn.pts()); |
| 400 | debugShowQuadLineIntersection(pts, wt, wn, ts); |
| 401 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 402 | case SkIntersectionHelper::kQuad_Segment: { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 403 | pts = ts.intersect(quad1.set(wt.pts()), quad2.set(wn.pts())); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 404 | debugShowQuadIntersection(pts, wt, wn, ts); |
| 405 | break; |
| 406 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 407 | case SkIntersectionHelper::kConic_Segment: { |
| 408 | swap = true; |
| 409 | pts = ts.intersect(conic2.set(wn.pts(), wn.weight()), |
| 410 | quad1.set(wt.pts())); |
| 411 | debugShowConicQuadIntersection(pts, wn, wt, ts); |
| 412 | break; |
| 413 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 414 | case SkIntersectionHelper::kCubic_Segment: { |
| 415 | swap = true; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 416 | pts = ts.intersect(cubic2.set(wn.pts()), quad1.set(wt.pts())); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 417 | debugShowCubicQuadIntersection(pts, wn, wt, ts); |
| 418 | break; |
| 419 | } |
| 420 | default: |
| 421 | SkASSERT(0); |
| 422 | } |
| 423 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 424 | case SkIntersectionHelper::kConic_Segment: |
| 425 | switch (wn.segmentType()) { |
| 426 | case SkIntersectionHelper::kHorizontalLine_Segment: |
| 427 | pts = ts.conicHorizontal(wt.pts(), wt.weight(), wn.left(), |
| 428 | wn.right(), wn.y(), wn.xFlipped()); |
| 429 | debugShowConicLineIntersection(pts, wt, wn, ts); |
| 430 | break; |
| 431 | case SkIntersectionHelper::kVerticalLine_Segment: |
| 432 | pts = ts.conicVertical(wt.pts(), wt.weight(), wn.top(), |
| 433 | wn.bottom(), wn.x(), wn.yFlipped()); |
| 434 | debugShowConicLineIntersection(pts, wt, wn, ts); |
| 435 | break; |
| 436 | case SkIntersectionHelper::kLine_Segment: |
| 437 | pts = ts.conicLine(wt.pts(), wt.weight(), wn.pts()); |
| 438 | debugShowConicLineIntersection(pts, wt, wn, ts); |
| 439 | break; |
| 440 | case SkIntersectionHelper::kQuad_Segment: { |
| 441 | pts = ts.intersect(conic1.set(wt.pts(), wt.weight()), |
| 442 | quad2.set(wn.pts())); |
| 443 | debugShowConicQuadIntersection(pts, wt, wn, ts); |
| 444 | break; |
| 445 | } |
| 446 | case SkIntersectionHelper::kConic_Segment: { |
| 447 | pts = ts.intersect(conic1.set(wt.pts(), wt.weight()), |
| 448 | conic2.set(wn.pts(), wn.weight())); |
| 449 | debugShowConicIntersection(pts, wt, wn, ts); |
| 450 | break; |
| 451 | } |
| 452 | case SkIntersectionHelper::kCubic_Segment: { |
| 453 | swap = true; |
| 454 | pts = ts.intersect(cubic2.set(wn.pts()), |
| 455 | conic1.set(wt.pts(), wt.weight())); |
| 456 | debugShowCubicConicIntersection(pts, wn, wt, ts); |
| 457 | break; |
| 458 | } |
| 459 | } |
| 460 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 461 | case SkIntersectionHelper::kCubic_Segment: |
| 462 | switch (wn.segmentType()) { |
| 463 | case SkIntersectionHelper::kHorizontalLine_Segment: |
| 464 | pts = ts.cubicHorizontal(wt.pts(), wn.left(), |
| 465 | wn.right(), wn.y(), wn.xFlipped()); |
| 466 | debugShowCubicLineIntersection(pts, wt, wn, ts); |
| 467 | break; |
| 468 | case SkIntersectionHelper::kVerticalLine_Segment: |
| 469 | pts = ts.cubicVertical(wt.pts(), wn.top(), |
| 470 | wn.bottom(), wn.x(), wn.yFlipped()); |
| 471 | debugShowCubicLineIntersection(pts, wt, wn, ts); |
| 472 | break; |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 473 | case SkIntersectionHelper::kLine_Segment: |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 474 | pts = ts.cubicLine(wt.pts(), wn.pts()); |
| 475 | debugShowCubicLineIntersection(pts, wt, wn, ts); |
| 476 | break; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 477 | case SkIntersectionHelper::kQuad_Segment: { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 478 | pts = ts.intersect(cubic1.set(wt.pts()), quad2.set(wn.pts())); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 479 | debugShowCubicQuadIntersection(pts, wt, wn, ts); |
| 480 | break; |
| 481 | } |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 482 | case SkIntersectionHelper::kConic_Segment: { |
| 483 | pts = ts.intersect(cubic1.set(wt.pts()), |
| 484 | conic2.set(wn.pts(), wn.weight())); |
| 485 | debugShowCubicConicIntersection(pts, wt, wn, ts); |
| 486 | break; |
| 487 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 488 | case SkIntersectionHelper::kCubic_Segment: { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 489 | pts = ts.intersect(cubic1.set(wt.pts()), cubic2.set(wn.pts())); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 490 | debugShowCubicIntersection(pts, wt, wn, ts); |
| 491 | break; |
| 492 | } |
| 493 | default: |
| 494 | SkASSERT(0); |
| 495 | } |
| 496 | break; |
| 497 | default: |
| 498 | SkASSERT(0); |
| 499 | } |
caryclark | 26ad22a | 2015-10-16 09:03:38 -0700 | [diff] [blame] | 500 | #if DEBUG_T_SECT_LOOP_COUNT |
| 501 | test->globalState()->debugAddLoopCount(&ts, wt, wn); |
| 502 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 503 | int coinIndex = -1; |
| 504 | SkOpPtT* coinPtT[2]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 505 | for (int pt = 0; pt < pts; ++pt) { |
| 506 | SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1); |
| 507 | SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 508 | wt.segment()->debugValidate(); |
| 509 | SkOpPtT* testTAt = wt.segment()->addT(ts[swap][pt], SkOpSegment::kAllowAlias, |
| 510 | allocator); |
| 511 | wn.segment()->debugValidate(); |
| 512 | SkOpPtT* nextTAt = wn.segment()->addT(ts[!swap][pt], SkOpSegment::kAllowAlias, |
| 513 | allocator); |
| 514 | testTAt->addOpp(nextTAt); |
| 515 | if (testTAt->fPt != nextTAt->fPt) { |
| 516 | testTAt->span()->unaligned(); |
| 517 | nextTAt->span()->unaligned(); |
| 518 | } |
| 519 | wt.segment()->debugValidate(); |
| 520 | wn.segment()->debugValidate(); |
| 521 | if (!ts.isCoincident(pt)) { |
| 522 | continue; |
| 523 | } |
| 524 | if (coinIndex < 0) { |
| 525 | coinPtT[0] = testTAt; |
| 526 | coinPtT[1] = nextTAt; |
| 527 | coinIndex = pt; |
| 528 | continue; |
| 529 | } |
| 530 | if (coinPtT[0]->span() == testTAt->span()) { |
| 531 | coinIndex = -1; |
| 532 | continue; |
| 533 | } |
| 534 | if (coinPtT[1]->span() == nextTAt->span()) { |
| 535 | coinIndex = -1; // coincidence span collapsed |
| 536 | continue; |
| 537 | } |
| 538 | if (swap) { |
| 539 | SkTSwap(coinPtT[0], coinPtT[1]); |
| 540 | SkTSwap(testTAt, nextTAt); |
| 541 | } |
| 542 | SkASSERT(coinPtT[0]->span()->t() < testTAt->span()->t()); |
| 543 | coincidence->add(coinPtT[0], testTAt, coinPtT[1], nextTAt, allocator); |
| 544 | wt.segment()->debugValidate(); |
| 545 | wn.segment()->debugValidate(); |
| 546 | coinIndex = -1; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 547 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 548 | SkASSERT(coinIndex < 0); // expect coincidence to be paired |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 549 | } while (wn.advance()); |
| 550 | } while (wt.advance()); |
| 551 | return true; |
| 552 | } |