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 "src/pathops/SkAddIntersections.h"
8 #include "src/pathops/SkOpCoincidence.h"
9 #include "src/pathops/SkPathOpsBounds.h"
10
11 #include <utility>
12
13 #if DEBUG_ADD_INTERSECTING_TS
14
debugShowLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowQuadLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowConicLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowConicQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowConicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicConicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
217 #else
debugShowLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)218 static void debugShowLineIntersection(int , const SkIntersectionHelper& ,
219 const SkIntersectionHelper& , const SkIntersections& ) {
220 }
221
debugShowQuadLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)222 static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& ,
223 const SkIntersectionHelper& , const SkIntersections& ) {
224 }
225
debugShowQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)226 static void debugShowQuadIntersection(int , const SkIntersectionHelper& ,
227 const SkIntersectionHelper& , const SkIntersections& ) {
228 }
229
debugShowConicLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)230 static void debugShowConicLineIntersection(int , const SkIntersectionHelper& ,
231 const SkIntersectionHelper& , const SkIntersections& ) {
232 }
233
debugShowConicQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)234 static void debugShowConicQuadIntersection(int , const SkIntersectionHelper& ,
235 const SkIntersectionHelper& , const SkIntersections& ) {
236 }
237
debugShowConicIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)238 static void debugShowConicIntersection(int , const SkIntersectionHelper& ,
239 const SkIntersectionHelper& , const SkIntersections& ) {
240 }
241
debugShowCubicLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)242 static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& ,
243 const SkIntersectionHelper& , const SkIntersections& ) {
244 }
245
debugShowCubicQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)246 static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& ,
247 const SkIntersectionHelper& , const SkIntersections& ) {
248 }
249
debugShowCubicConicIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)250 static void debugShowCubicConicIntersection(int , const SkIntersectionHelper& ,
251 const SkIntersectionHelper& , const SkIntersections& ) {
252 }
253
debugShowCubicIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)254 static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
255 const SkIntersectionHelper& , const SkIntersections& ) {
256 }
257 #endif
258
AddIntersectTs(SkOpContour * test,SkOpContour * next,SkOpCoincidence * coincidence)259 bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coincidence) {
260 if (test != next) {
261 if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
262 return false;
263 }
264 // OPTIMIZATION: outset contour bounds a smidgen instead?
265 if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
266 return true;
267 }
268 }
269 SkIntersectionHelper wt;
270 wt.init(test);
271 do {
272 SkIntersectionHelper wn;
273 wn.init(next);
274 test->debugValidate();
275 next->debugValidate();
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;
284 SkIntersections ts { SkDEBUGCODE(test->globalState()) };
285 bool swap = false;
286 SkDQuad quad1, quad2;
287 SkDConic conic1, conic2;
288 SkDCubic cubic1, cubic2;
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:
295 case SkIntersectionHelper::kLine_Segment:
296 pts = ts.lineHorizontal(wn.pts(), wt.left(),
297 wt.right(), wt.y(), wt.xFlipped());
298 debugShowLineIntersection(pts, wn, wt, ts);
299 break;
300 case SkIntersectionHelper::kQuad_Segment:
301 pts = ts.quadHorizontal(wn.pts(), wt.left(),
302 wt.right(), wt.y(), wt.xFlipped());
303 debugShowQuadLineIntersection(pts, wn, wt, ts);
304 break;
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:
311 pts = ts.cubicHorizontal(wn.pts(), wt.left(),
312 wt.right(), wt.y(), wt.xFlipped());
313 debugShowCubicLineIntersection(pts, wn, wt, ts);
314 break;
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());
327 debugShowLineIntersection(pts, wn, wt, ts);
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 }
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 }
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;
364 case SkIntersectionHelper::kLine_Segment:
365 pts = ts.lineLine(wt.pts(), wn.pts());
366 debugShowLineIntersection(pts, wt, wn, ts);
367 break;
368 case SkIntersectionHelper::kQuad_Segment:
369 swap = true;
370 pts = ts.quadLine(wn.pts(), wt.pts());
371 debugShowQuadLineIntersection(pts, wn, wt, ts);
372 break;
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:
379 swap = true;
380 pts = ts.cubicLine(wn.pts(), wt.pts());
381 debugShowCubicLineIntersection(pts, wn, wt, ts);
382 break;
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;
399 case SkIntersectionHelper::kLine_Segment:
400 pts = ts.quadLine(wt.pts(), wn.pts());
401 debugShowQuadLineIntersection(pts, wt, wn, ts);
402 break;
403 case SkIntersectionHelper::kQuad_Segment: {
404 pts = ts.intersect(quad1.set(wt.pts()), quad2.set(wn.pts()));
405 debugShowQuadIntersection(pts, wt, wn, ts);
406 break;
407 }
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 }
415 case SkIntersectionHelper::kCubic_Segment: {
416 swap = true;
417 pts = ts.intersect(cubic2.set(wn.pts()), quad1.set(wt.pts()));
418 debugShowCubicQuadIntersection(pts, wn, wt, ts);
419 break;
420 }
421 default:
422 SkASSERT(0);
423 }
424 break;
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;
455 pts = ts.intersect(cubic2.set(wn.pts()
456 SkDEBUGPARAMS(ts.globalState())),
457 conic1.set(wt.pts(), wt.weight()
458 SkDEBUGPARAMS(ts.globalState())));
459 debugShowCubicConicIntersection(pts, wn, wt, ts);
460 break;
461 }
462 }
463 break;
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;
476 case SkIntersectionHelper::kLine_Segment:
477 pts = ts.cubicLine(wt.pts(), wn.pts());
478 debugShowCubicLineIntersection(pts, wt, wn, ts);
479 break;
480 case SkIntersectionHelper::kQuad_Segment: {
481 pts = ts.intersect(cubic1.set(wt.pts()), quad2.set(wn.pts()));
482 debugShowCubicQuadIntersection(pts, wt, wn, ts);
483 break;
484 }
485 case SkIntersectionHelper::kConic_Segment: {
486 pts = ts.intersect(cubic1.set(wt.pts()
487 SkDEBUGPARAMS(ts.globalState())),
488 conic2.set(wn.pts(), wn.weight()
489 SkDEBUGPARAMS(ts.globalState())));
490 debugShowCubicConicIntersection(pts, wt, wn, ts);
491 break;
492 }
493 case SkIntersectionHelper::kCubic_Segment: {
494 pts = ts.intersect(cubic1.set(wt.pts()), cubic2.set(wn.pts()));
495 debugShowCubicIntersection(pts, wt, wn, ts);
496 break;
497 }
498 default:
499 SkASSERT(0);
500 }
501 break;
502 default:
503 SkASSERT(0);
504 }
505 #if DEBUG_T_SECT_LOOP_COUNT
506 test->globalState()->debugAddLoopCount(&ts, wt, wn);
507 #endif
508 int coinIndex = -1;
509 SkOpPtT* coinPtT[2];
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);
513 wt.segment()->debugValidate();
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]);
522 wn.segment()->debugValidate();
523 SkOpPtT* nextTAt = iPtIsIntegral ? wn.segment()->addT(ts[!swap][pt], iPt)
524 : wn.segment()->addT(ts[!swap][pt]);
525 if (!testTAt->contains(nextTAt)) {
526 SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt); // Returns nullptr if pair
527 if (oppPrev) { // already share a pt-t loop.
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();
537 }
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) {
556 using std::swap;
557 swap(coinPtT[0], coinPtT[1]);
558 swap(testTAt, nextTAt);
559 }
560 SkASSERT(coincidence->globalState()->debugSkipAssert()
561 || coinPtT[0]->span()->t() < testTAt->span()->t());
562 if (coinPtT[0]->span()->deleted()) {
563 coinIndex = -1;
564 continue;
565 }
566 if (testTAt->span()->deleted()) {
567 coinIndex = -1;
568 continue;
569 }
570 coincidence->add(coinPtT[0], testTAt, coinPtT[1], nextTAt);
571 wt.segment()->debugValidate();
572 wn.segment()->debugValidate();
573 coinIndex = -1;
574 }
575 SkOPOBJASSERT(coincidence, coinIndex < 0); // expect coincidence to be paired
576 } while (wn.advance());
577 } while (wt.advance());
578 return true;
579 }
580