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