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