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,SkChunkAlloc * allocator)257 bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coincidence,
258         SkChunkAlloc* allocator) {
259     if (test != next) {
260         if (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
261             return false;
262         }
263         // OPTIMIZATION: outset contour bounds a smidgen instead?
264         if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
265             return true;
266         }
267     }
268     SkIntersectionHelper wt;
269     wt.init(test);
270     do {
271         SkIntersectionHelper wn;
272         wn.init(next);
273         test->debugValidate();
274         next->debugValidate();
275         if (test == next && !wn.startAfter(wt)) {
276             continue;
277         }
278         do {
279             if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
280                 continue;
281             }
282             int pts = 0;
283             SkIntersections ts;
284             bool swap = false;
285             SkDQuad quad1, quad2;
286             SkDConic conic1, conic2;
287             SkDCubic cubic1, cubic2;
288             switch (wt.segmentType()) {
289                 case SkIntersectionHelper::kHorizontalLine_Segment:
290                     swap = true;
291                     switch (wn.segmentType()) {
292                         case SkIntersectionHelper::kHorizontalLine_Segment:
293                         case SkIntersectionHelper::kVerticalLine_Segment:
294                         case SkIntersectionHelper::kLine_Segment:
295                             pts = ts.lineHorizontal(wn.pts(), wt.left(),
296                                     wt.right(), wt.y(), wt.xFlipped());
297                             debugShowLineIntersection(pts, wn, wt, ts);
298                             break;
299                         case SkIntersectionHelper::kQuad_Segment:
300                             pts = ts.quadHorizontal(wn.pts(), wt.left(),
301                                     wt.right(), wt.y(), wt.xFlipped());
302                             debugShowQuadLineIntersection(pts, wn, wt, ts);
303                             break;
304                         case SkIntersectionHelper::kConic_Segment:
305                             pts = ts.conicHorizontal(wn.pts(), wn.weight(), wt.left(),
306                                     wt.right(), wt.y(), wt.xFlipped());
307                             debugShowConicLineIntersection(pts, wn, wt, ts);
308                             break;
309                         case SkIntersectionHelper::kCubic_Segment:
310                             pts = ts.cubicHorizontal(wn.pts(), wt.left(),
311                                     wt.right(), wt.y(), wt.xFlipped());
312                             debugShowCubicLineIntersection(pts, wn, wt, ts);
313                             break;
314                         default:
315                             SkASSERT(0);
316                     }
317                     break;
318                 case SkIntersectionHelper::kVerticalLine_Segment:
319                     swap = true;
320                     switch (wn.segmentType()) {
321                         case SkIntersectionHelper::kHorizontalLine_Segment:
322                         case SkIntersectionHelper::kVerticalLine_Segment:
323                         case SkIntersectionHelper::kLine_Segment: {
324                             pts = ts.lineVertical(wn.pts(), wt.top(),
325                                     wt.bottom(), wt.x(), wt.yFlipped());
326                             debugShowLineIntersection(pts, wn, wt, ts);
327                             break;
328                         }
329                         case SkIntersectionHelper::kQuad_Segment: {
330                             pts = ts.quadVertical(wn.pts(), wt.top(),
331                                     wt.bottom(), wt.x(), wt.yFlipped());
332                             debugShowQuadLineIntersection(pts, wn, wt, ts);
333                             break;
334                         }
335                         case SkIntersectionHelper::kConic_Segment: {
336                             pts = ts.conicVertical(wn.pts(), wn.weight(), wt.top(),
337                                     wt.bottom(), wt.x(), wt.yFlipped());
338                             debugShowConicLineIntersection(pts, wn, wt, ts);
339                             break;
340                         }
341                         case SkIntersectionHelper::kCubic_Segment: {
342                             pts = ts.cubicVertical(wn.pts(), wt.top(),
343                                     wt.bottom(), wt.x(), wt.yFlipped());
344                             debugShowCubicLineIntersection(pts, wn, wt, ts);
345                             break;
346                         }
347                         default:
348                             SkASSERT(0);
349                     }
350                     break;
351                 case SkIntersectionHelper::kLine_Segment:
352                     switch (wn.segmentType()) {
353                         case SkIntersectionHelper::kHorizontalLine_Segment:
354                             pts = ts.lineHorizontal(wt.pts(), wn.left(),
355                                     wn.right(), wn.y(), wn.xFlipped());
356                             debugShowLineIntersection(pts, wt, wn, ts);
357                             break;
358                         case SkIntersectionHelper::kVerticalLine_Segment:
359                             pts = ts.lineVertical(wt.pts(), wn.top(),
360                                     wn.bottom(), wn.x(), wn.yFlipped());
361                             debugShowLineIntersection(pts, wt, wn, ts);
362                             break;
363                         case SkIntersectionHelper::kLine_Segment:
364                             pts = ts.lineLine(wt.pts(), wn.pts());
365                             debugShowLineIntersection(pts, wt, wn, ts);
366                             break;
367                         case SkIntersectionHelper::kQuad_Segment:
368                             swap = true;
369                             pts = ts.quadLine(wn.pts(), wt.pts());
370                             debugShowQuadLineIntersection(pts, wn, wt, ts);
371                             break;
372                         case SkIntersectionHelper::kConic_Segment:
373                             swap = true;
374                             pts = ts.conicLine(wn.pts(), wn.weight(), wt.pts());
375                             debugShowConicLineIntersection(pts, wn, wt, ts);
376                             break;
377                         case SkIntersectionHelper::kCubic_Segment:
378                             swap = true;
379                             pts = ts.cubicLine(wn.pts(), wt.pts());
380                             debugShowCubicLineIntersection(pts, wn, wt, ts);
381                             break;
382                         default:
383                             SkASSERT(0);
384                     }
385                     break;
386                 case SkIntersectionHelper::kQuad_Segment:
387                     switch (wn.segmentType()) {
388                         case SkIntersectionHelper::kHorizontalLine_Segment:
389                             pts = ts.quadHorizontal(wt.pts(), wn.left(),
390                                     wn.right(), wn.y(), wn.xFlipped());
391                             debugShowQuadLineIntersection(pts, wt, wn, ts);
392                             break;
393                         case SkIntersectionHelper::kVerticalLine_Segment:
394                             pts = ts.quadVertical(wt.pts(), wn.top(),
395                                     wn.bottom(), wn.x(), wn.yFlipped());
396                             debugShowQuadLineIntersection(pts, wt, wn, ts);
397                             break;
398                         case SkIntersectionHelper::kLine_Segment:
399                             pts = ts.quadLine(wt.pts(), wn.pts());
400                             debugShowQuadLineIntersection(pts, wt, wn, ts);
401                             break;
402                         case SkIntersectionHelper::kQuad_Segment: {
403                             pts = ts.intersect(quad1.set(wt.pts()), quad2.set(wn.pts()));
404                             debugShowQuadIntersection(pts, wt, wn, ts);
405                             break;
406                         }
407                         case SkIntersectionHelper::kConic_Segment: {
408                             swap = true;
409                             pts = ts.intersect(conic2.set(wn.pts(), wn.weight()),
410                                     quad1.set(wt.pts()));
411                             debugShowConicQuadIntersection(pts, wn, wt, ts);
412                             break;
413                         }
414                         case SkIntersectionHelper::kCubic_Segment: {
415                             swap = true;
416                             pts = ts.intersect(cubic2.set(wn.pts()), quad1.set(wt.pts()));
417                             debugShowCubicQuadIntersection(pts, wn, wt, ts);
418                             break;
419                         }
420                         default:
421                             SkASSERT(0);
422                     }
423                     break;
424                 case SkIntersectionHelper::kConic_Segment:
425                     switch (wn.segmentType()) {
426                         case SkIntersectionHelper::kHorizontalLine_Segment:
427                             pts = ts.conicHorizontal(wt.pts(), wt.weight(), wn.left(),
428                                     wn.right(), wn.y(), wn.xFlipped());
429                             debugShowConicLineIntersection(pts, wt, wn, ts);
430                             break;
431                         case SkIntersectionHelper::kVerticalLine_Segment:
432                             pts = ts.conicVertical(wt.pts(), wt.weight(), wn.top(),
433                                     wn.bottom(), wn.x(), wn.yFlipped());
434                             debugShowConicLineIntersection(pts, wt, wn, ts);
435                             break;
436                         case SkIntersectionHelper::kLine_Segment:
437                             pts = ts.conicLine(wt.pts(), wt.weight(), wn.pts());
438                             debugShowConicLineIntersection(pts, wt, wn, ts);
439                             break;
440                         case SkIntersectionHelper::kQuad_Segment: {
441                             pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
442                                     quad2.set(wn.pts()));
443                             debugShowConicQuadIntersection(pts, wt, wn, ts);
444                             break;
445                         }
446                         case SkIntersectionHelper::kConic_Segment: {
447                             pts = ts.intersect(conic1.set(wt.pts(), wt.weight()),
448                                     conic2.set(wn.pts(), wn.weight()));
449                             debugShowConicIntersection(pts, wt, wn, ts);
450                             break;
451                         }
452                         case SkIntersectionHelper::kCubic_Segment: {
453                             swap = true;
454                             pts = ts.intersect(cubic2.set(wn.pts()),
455                                     conic1.set(wt.pts(), wt.weight()));
456                             debugShowCubicConicIntersection(pts, wn, wt, ts);
457                             break;
458                         }
459                     }
460                     break;
461                 case SkIntersectionHelper::kCubic_Segment:
462                     switch (wn.segmentType()) {
463                         case SkIntersectionHelper::kHorizontalLine_Segment:
464                             pts = ts.cubicHorizontal(wt.pts(), wn.left(),
465                                     wn.right(), wn.y(), wn.xFlipped());
466                             debugShowCubicLineIntersection(pts, wt, wn, ts);
467                             break;
468                         case SkIntersectionHelper::kVerticalLine_Segment:
469                             pts = ts.cubicVertical(wt.pts(), wn.top(),
470                                     wn.bottom(), wn.x(), wn.yFlipped());
471                             debugShowCubicLineIntersection(pts, wt, wn, ts);
472                             break;
473                         case SkIntersectionHelper::kLine_Segment:
474                             pts = ts.cubicLine(wt.pts(), wn.pts());
475                             debugShowCubicLineIntersection(pts, wt, wn, ts);
476                             break;
477                         case SkIntersectionHelper::kQuad_Segment: {
478                             pts = ts.intersect(cubic1.set(wt.pts()), quad2.set(wn.pts()));
479                             debugShowCubicQuadIntersection(pts, wt, wn, ts);
480                             break;
481                         }
482                         case SkIntersectionHelper::kConic_Segment: {
483                             pts = ts.intersect(cubic1.set(wt.pts()),
484                                     conic2.set(wn.pts(), wn.weight()));
485                             debugShowCubicConicIntersection(pts, wt, wn, ts);
486                             break;
487                         }
488                         case SkIntersectionHelper::kCubic_Segment: {
489                             pts = ts.intersect(cubic1.set(wt.pts()), cubic2.set(wn.pts()));
490                             debugShowCubicIntersection(pts, wt, wn, ts);
491                             break;
492                         }
493                         default:
494                             SkASSERT(0);
495                     }
496                     break;
497                 default:
498                     SkASSERT(0);
499             }
500             int coinIndex = -1;
501             SkOpPtT* coinPtT[2];
502             for (int pt = 0; pt < pts; ++pt) {
503                 SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
504                 SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
505                 wt.segment()->debugValidate();
506                 SkOpPtT* testTAt = wt.segment()->addT(ts[swap][pt], SkOpSegment::kAllowAlias,
507                         allocator);
508                 wn.segment()->debugValidate();
509                 SkOpPtT* nextTAt = wn.segment()->addT(ts[!swap][pt], SkOpSegment::kAllowAlias,
510                         allocator);
511                 testTAt->addOpp(nextTAt);
512                 if (testTAt->fPt != nextTAt->fPt) {
513                     testTAt->span()->unaligned();
514                     nextTAt->span()->unaligned();
515                 }
516                 wt.segment()->debugValidate();
517                 wn.segment()->debugValidate();
518                 if (!ts.isCoincident(pt)) {
519                     continue;
520                 }
521                 if (coinIndex < 0) {
522                     coinPtT[0] = testTAt;
523                     coinPtT[1] = nextTAt;
524                     coinIndex = pt;
525                     continue;
526                 }
527                 if (coinPtT[0]->span() == testTAt->span()) {
528                     coinIndex = -1;
529                     continue;
530                 }
531                 if (coinPtT[1]->span() == nextTAt->span()) {
532                     coinIndex = -1;  // coincidence span collapsed
533                     continue;
534                 }
535                 if (swap) {
536                     SkTSwap(coinPtT[0], coinPtT[1]);
537                     SkTSwap(testTAt, nextTAt);
538                 }
539                 SkASSERT(coinPtT[0]->span()->t() < testTAt->span()->t());
540                 coincidence->add(coinPtT[0], testTAt, coinPtT[1], nextTAt, allocator);
541                 wt.segment()->debugValidate();
542                 wn.segment()->debugValidate();
543                 coinIndex = -1;
544             }
545             SkASSERT(coinIndex < 0);  // expect coincidence to be paired
546         } while (wn.advance());
547     } while (wt.advance());
548     return true;
549 }
550