1 /*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7 #include "SkAddIntersections.h"
8 #include "SkOpCoincidence.h"
9 #include "SkPathOpsBounds.h"
10
11 #if DEBUG_ADD_INTERSECTING_TS
12
debugShowLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowQuadLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowConicLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowConicQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowConicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicConicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
debugShowCubicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)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
215 #else
debugShowLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)216 static void debugShowLineIntersection(int , const SkIntersectionHelper& ,
217 const SkIntersectionHelper& , const SkIntersections& ) {
218 }
219
debugShowQuadLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)220 static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& ,
221 const SkIntersectionHelper& , const SkIntersections& ) {
222 }
223
debugShowQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)224 static void debugShowQuadIntersection(int , const SkIntersectionHelper& ,
225 const SkIntersectionHelper& , const SkIntersections& ) {
226 }
227
debugShowConicLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)228 static void debugShowConicLineIntersection(int , const SkIntersectionHelper& ,
229 const SkIntersectionHelper& , const SkIntersections& ) {
230 }
231
debugShowConicQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)232 static void debugShowConicQuadIntersection(int , const SkIntersectionHelper& ,
233 const SkIntersectionHelper& , const SkIntersections& ) {
234 }
235
debugShowConicIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)236 static void debugShowConicIntersection(int , const SkIntersectionHelper& ,
237 const SkIntersectionHelper& , const SkIntersections& ) {
238 }
239
debugShowCubicLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)240 static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& ,
241 const SkIntersectionHelper& , const SkIntersections& ) {
242 }
243
debugShowCubicQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)244 static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& ,
245 const SkIntersectionHelper& , const SkIntersections& ) {
246 }
247
debugShowCubicConicIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)248 static void debugShowCubicConicIntersection(int , const SkIntersectionHelper& ,
249 const SkIntersectionHelper& , const SkIntersections& ) {
250 }
251
debugShowCubicIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)252 static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
253 const SkIntersectionHelper& , const SkIntersections& ) {
254 }
255 #endif
256
AddIntersectTs(SkOpContour * test,SkOpContour * next,SkOpCoincidence * coincidence)257 bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coincidence) {
258 if (test != next) {
259 if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
260 return false;
261 }
262 // OPTIMIZATION: outset contour bounds a smidgen instead?
263 if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
264 return true;
265 }
266 }
267 SkIntersectionHelper wt;
268 wt.init(test);
269 do {
270 SkIntersectionHelper wn;
271 wn.init(next);
272 test->debugValidate();
273 next->debugValidate();
274 if (test == next && !wn.startAfter(wt)) {
275 continue;
276 }
277 do {
278 if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
279 continue;
280 }
281 int pts = 0;
282 SkIntersections ts { SkDEBUGCODE(test->globalState()) };
283 bool swap = false;
284 SkDQuad quad1, quad2;
285 SkDConic conic1, conic2;
286 SkDCubic cubic1, cubic2;
287 switch (wt.segmentType()) {
288 case SkIntersectionHelper::kHorizontalLine_Segment:
289 swap = true;
290 switch (wn.segmentType()) {
291 case SkIntersectionHelper::kHorizontalLine_Segment:
292 case SkIntersectionHelper::kVerticalLine_Segment:
293 case SkIntersectionHelper::kLine_Segment:
294 pts = ts.lineHorizontal(wn.pts(), wt.left(),
295 wt.right(), wt.y(), wt.xFlipped());
296 debugShowLineIntersection(pts, wn, wt, ts);
297 break;
298 case SkIntersectionHelper::kQuad_Segment:
299 pts = ts.quadHorizontal(wn.pts(), wt.left(),
300 wt.right(), wt.y(), wt.xFlipped());
301 debugShowQuadLineIntersection(pts, wn, wt, ts);
302 break;
303 case SkIntersectionHelper::kConic_Segment:
304 pts = ts.conicHorizontal(wn.pts(), wn.weight(), wt.left(),
305 wt.right(), wt.y(), wt.xFlipped());
306 debugShowConicLineIntersection(pts, wn, wt, ts);
307 break;
308 case SkIntersectionHelper::kCubic_Segment:
309 pts = ts.cubicHorizontal(wn.pts(), wt.left(),
310 wt.right(), wt.y(), wt.xFlipped());
311 debugShowCubicLineIntersection(pts, wn, wt, ts);
312 break;
313 default:
314 SkASSERT(0);
315 }
316 break;
317 case SkIntersectionHelper::kVerticalLine_Segment:
318 swap = true;
319 switch (wn.segmentType()) {
320 case SkIntersectionHelper::kHorizontalLine_Segment:
321 case SkIntersectionHelper::kVerticalLine_Segment:
322 case SkIntersectionHelper::kLine_Segment: {
323 pts = ts.lineVertical(wn.pts(), wt.top(),
324 wt.bottom(), wt.x(), wt.yFlipped());
325 debugShowLineIntersection(pts, wn, wt, ts);
326 break;
327 }
328 case SkIntersectionHelper::kQuad_Segment: {
329 pts = ts.quadVertical(wn.pts(), wt.top(),
330 wt.bottom(), wt.x(), wt.yFlipped());
331 debugShowQuadLineIntersection(pts, wn, wt, ts);
332 break;
333 }
334 case SkIntersectionHelper::kConic_Segment: {
335 pts = ts.conicVertical(wn.pts(), wn.weight(), wt.top(),
336 wt.bottom(), wt.x(), wt.yFlipped());
337 debugShowConicLineIntersection(pts, wn, wt, ts);
338 break;
339 }
340 case SkIntersectionHelper::kCubic_Segment: {
341 pts = ts.cubicVertical(wn.pts(), wt.top(),
342 wt.bottom(), wt.x(), wt.yFlipped());
343 debugShowCubicLineIntersection(pts, wn, wt, ts);
344 break;
345 }
346 default:
347 SkASSERT(0);
348 }
349 break;
350 case SkIntersectionHelper::kLine_Segment:
351 switch (wn.segmentType()) {
352 case SkIntersectionHelper::kHorizontalLine_Segment:
353 pts = ts.lineHorizontal(wt.pts(), wn.left(),
354 wn.right(), wn.y(), wn.xFlipped());
355 debugShowLineIntersection(pts, wt, wn, ts);
356 break;
357 case SkIntersectionHelper::kVerticalLine_Segment:
358 pts = ts.lineVertical(wt.pts(), wn.top(),
359 wn.bottom(), wn.x(), wn.yFlipped());
360 debugShowLineIntersection(pts, wt, wn, ts);
361 break;
362 case SkIntersectionHelper::kLine_Segment:
363 pts = ts.lineLine(wt.pts(), wn.pts());
364 debugShowLineIntersection(pts, wt, wn, ts);
365 break;
366 case SkIntersectionHelper::kQuad_Segment:
367 swap = true;
368 pts = ts.quadLine(wn.pts(), wt.pts());
369 debugShowQuadLineIntersection(pts, wn, wt, ts);
370 break;
371 case SkIntersectionHelper::kConic_Segment:
372 swap = true;
373 pts = ts.conicLine(wn.pts(), wn.weight(), wt.pts());
374 debugShowConicLineIntersection(pts, wn, wt, ts);
375 break;
376 case SkIntersectionHelper::kCubic_Segment:
377 swap = true;
378 pts = ts.cubicLine(wn.pts(), wt.pts());
379 debugShowCubicLineIntersection(pts, wn, wt, ts);
380 break;
381 default:
382 SkASSERT(0);
383 }
384 break;
385 case SkIntersectionHelper::kQuad_Segment:
386 switch (wn.segmentType()) {
387 case SkIntersectionHelper::kHorizontalLine_Segment:
388 pts = ts.quadHorizontal(wt.pts(), wn.left(),
389 wn.right(), wn.y(), wn.xFlipped());
390 debugShowQuadLineIntersection(pts, wt, wn, ts);
391 break;
392 case SkIntersectionHelper::kVerticalLine_Segment:
393 pts = ts.quadVertical(wt.pts(), wn.top(),
394 wn.bottom(), wn.x(), wn.yFlipped());
395 debugShowQuadLineIntersection(pts, wt, wn, ts);
396 break;
397 case SkIntersectionHelper::kLine_Segment:
398 pts = ts.quadLine(wt.pts(), wn.pts());
399 debugShowQuadLineIntersection(pts, wt, wn, ts);
400 break;
401 case SkIntersectionHelper::kQuad_Segment: {
402 pts = ts.intersect(quad1.set(wt.pts()), quad2.set(wn.pts()));
403 debugShowQuadIntersection(pts, wt, wn, ts);
404 break;
405 }
406 case SkIntersectionHelper::kConic_Segment: {
407 swap = true;
408 pts = ts.intersect(conic2.set(wn.pts(), wn.weight()),
409 quad1.set(wt.pts()));
410 debugShowConicQuadIntersection(pts, wn, wt, ts);
411 break;
412 }
413 case SkIntersectionHelper::kCubic_Segment: {
414 swap = true;
415 pts = ts.intersect(cubic2.set(wn.pts()), quad1.set(wt.pts()));
416 debugShowCubicQuadIntersection(pts, wn, wt, ts);
417 break;
418 }
419 default:
420 SkASSERT(0);
421 }
422 break;
423 case SkIntersectionHelper::kConic_Segment:
424 switch (wn.segmentType()) {
425 case SkIntersectionHelper::kHorizontalLine_Segment:
426 pts = ts.conicHorizontal(wt.pts(), wt.weight(), wn.left(),
427 wn.right(), wn.y(), wn.xFlipped());
428 debugShowConicLineIntersection(pts, wt, wn, ts);
429 break;
430 case SkIntersectionHelper::kVerticalLine_Segment:
431 pts = ts.conicVertical(wt.pts(), wt.weight(), wn.top(),
432 wn.bottom(), wn.x(), wn.yFlipped());
433 debugShowConicLineIntersection(pts, wt, wn, ts);
434 break;
435 case SkIntersectionHelper::kLine_Segment:
436 pts = ts.conicLine(wt.pts(), wt.weight(), wn.pts());
437 debugShowConicLineIntersection(pts, wt, wn, ts);
438 break;
439 case SkIntersectionHelper::kQuad_Segment: {
440 pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
441 quad2.set(wn.pts()));
442 debugShowConicQuadIntersection(pts, wt, wn, ts);
443 break;
444 }
445 case SkIntersectionHelper::kConic_Segment: {
446 pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
447 conic2.set(wn.pts(), wn.weight()));
448 debugShowConicIntersection(pts, wt, wn, ts);
449 break;
450 }
451 case SkIntersectionHelper::kCubic_Segment: {
452 swap = true;
453 pts = ts.intersect(cubic2.set(wn.pts()
454 SkDEBUGPARAMS(ts.globalState())),
455 conic1.set(wt.pts(), wt.weight()
456 SkDEBUGPARAMS(ts.globalState())));
457 debugShowCubicConicIntersection(pts, wn, wt, ts);
458 break;
459 }
460 }
461 break;
462 case SkIntersectionHelper::kCubic_Segment:
463 switch (wn.segmentType()) {
464 case SkIntersectionHelper::kHorizontalLine_Segment:
465 pts = ts.cubicHorizontal(wt.pts(), wn.left(),
466 wn.right(), wn.y(), wn.xFlipped());
467 debugShowCubicLineIntersection(pts, wt, wn, ts);
468 break;
469 case SkIntersectionHelper::kVerticalLine_Segment:
470 pts = ts.cubicVertical(wt.pts(), wn.top(),
471 wn.bottom(), wn.x(), wn.yFlipped());
472 debugShowCubicLineIntersection(pts, wt, wn, ts);
473 break;
474 case SkIntersectionHelper::kLine_Segment:
475 pts = ts.cubicLine(wt.pts(), wn.pts());
476 debugShowCubicLineIntersection(pts, wt, wn, ts);
477 break;
478 case SkIntersectionHelper::kQuad_Segment: {
479 pts = ts.intersect(cubic1.set(wt.pts()), quad2.set(wn.pts()));
480 debugShowCubicQuadIntersection(pts, wt, wn, ts);
481 break;
482 }
483 case SkIntersectionHelper::kConic_Segment: {
484 pts = ts.intersect(cubic1.set(wt.pts()
485 SkDEBUGPARAMS(ts.globalState())),
486 conic2.set(wn.pts(), wn.weight()
487 SkDEBUGPARAMS(ts.globalState())));
488 debugShowCubicConicIntersection(pts, wt, wn, ts);
489 break;
490 }
491 case SkIntersectionHelper::kCubic_Segment: {
492 pts = ts.intersect(cubic1.set(wt.pts()), cubic2.set(wn.pts()));
493 debugShowCubicIntersection(pts, wt, wn, ts);
494 break;
495 }
496 default:
497 SkASSERT(0);
498 }
499 break;
500 default:
501 SkASSERT(0);
502 }
503 #if DEBUG_T_SECT_LOOP_COUNT
504 test->globalState()->debugAddLoopCount(&ts, wt, wn);
505 #endif
506 int coinIndex = -1;
507 SkOpPtT* coinPtT[2];
508 for (int pt = 0; pt < pts; ++pt) {
509 SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
510 SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
511 wt.segment()->debugValidate();
512 // if t value is used to compute pt in addT, error may creep in and
513 // rect intersections may result in non-rects. if pt value from intersection
514 // is passed in, current tests break. As a workaround, pass in pt
515 // value from intersection only if pt.x and pt.y is integral
516 SkPoint iPt = ts.pt(pt).asSkPoint();
517 bool iPtIsIntegral = iPt.fX == floor(iPt.fX) && iPt.fY == floor(iPt.fY);
518 SkOpPtT* testTAt = iPtIsIntegral ? wt.segment()->addT(ts[swap][pt], iPt)
519 : wt.segment()->addT(ts[swap][pt]);
520 wn.segment()->debugValidate();
521 SkOpPtT* nextTAt = iPtIsIntegral ? wn.segment()->addT(ts[!swap][pt], iPt)
522 : wn.segment()->addT(ts[!swap][pt]);
523 if (!testTAt->contains(nextTAt)) {
524 SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt); // Returns nullptr if pair
525 if (oppPrev) { // already share a pt-t loop.
526 testTAt->span()->mergeMatches(nextTAt->span());
527 testTAt->addOpp(nextTAt, oppPrev);
528 }
529 if (testTAt->fPt != nextTAt->fPt) {
530 testTAt->span()->unaligned();
531 nextTAt->span()->unaligned();
532 }
533 wt.segment()->debugValidate();
534 wn.segment()->debugValidate();
535 }
536 if (!ts.isCoincident(pt)) {
537 continue;
538 }
539 if (coinIndex < 0) {
540 coinPtT[0] = testTAt;
541 coinPtT[1] = nextTAt;
542 coinIndex = pt;
543 continue;
544 }
545 if (coinPtT[0]->span() == testTAt->span()) {
546 coinIndex = -1;
547 continue;
548 }
549 if (coinPtT[1]->span() == nextTAt->span()) {
550 coinIndex = -1; // coincidence span collapsed
551 continue;
552 }
553 if (swap) {
554 SkTSwap(coinPtT[0], coinPtT[1]);
555 SkTSwap(testTAt, nextTAt);
556 }
557 SkASSERT(coincidence->globalState()->debugSkipAssert()
558 || coinPtT[0]->span()->t() < testTAt->span()->t());
559 if (coinPtT[0]->span()->deleted()) {
560 coinIndex = -1;
561 continue;
562 }
563 if (testTAt->span()->deleted()) {
564 coinIndex = -1;
565 continue;
566 }
567 coincidence->add(coinPtT[0], testTAt, coinPtT[1], nextTAt);
568 wt.segment()->debugValidate();
569 wn.segment()->debugValidate();
570 coinIndex = -1;
571 }
572 SkOPOBJASSERT(coincidence, coinIndex < 0); // expect coincidence to be paired
573 } while (wn.advance());
574 } while (wt.advance());
575 return true;
576 }
577