SkAddIntersections.cpp revision 07393cab57ce74a4aae89a31fae9aaa9780fc19d 
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 "SkPathOpsBounds.h"
9
10#if DEBUG_ADD_INTERSECTING_TS
11
12static void debugShowLineIntersection(int pts, const SkIntersectionHelper& wt,
13                                      const SkIntersectionHelper& wn, const SkIntersections& i) {
14    SkASSERT(i.used() == pts);
15    if (!pts) {
16        SkDebugf("%s no intersect " LINE_DEBUG_STR " " LINE_DEBUG_STR "\n",
17                __FUNCTION__, LINE_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
18        return;
19    }
20    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " LINE_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
21            i[0][0], LINE_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
22    if (pts == 2) {
23        SkDebugf(" " T_DEBUG_STR(wtTs, 1) " " PT_DEBUG_STR, i[0][1], PT_DEBUG_DATA(i, 1));
24    }
25    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
26    if (pts == 2) {
27        SkDebugf(" " T_DEBUG_STR(wnTs, 1), i[1][1]);
28    }
29    SkDebugf("\n");
30}
31
32static void debugShowQuadLineIntersection(int pts, const SkIntersectionHelper& wt,
33                                          const SkIntersectionHelper& wn,
34                                          const SkIntersections& i) {
35    SkASSERT(i.used() == pts);
36    if (!pts) {
37        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " LINE_DEBUG_STR "\n",
38                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
39        return;
40    }
41    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
42            i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
43    for (int n = 1; n < pts; ++n) {
44        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
45    }
46    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
47    for (int n = 1; n < pts; ++n) {
48        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
49    }
50    SkDebugf("\n");
51}
52
53static void debugShowQuadIntersection(int pts, const SkIntersectionHelper& wt,
54        const SkIntersectionHelper& wn, const SkIntersections& i) {
55    SkASSERT(i.used() == pts);
56    if (!pts) {
57        SkDebugf("%s no intersect " QUAD_DEBUG_STR " " QUAD_DEBUG_STR "\n",
58                __FUNCTION__, QUAD_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
59        return;
60    }
61    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " QUAD_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
62            i[0][0], QUAD_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
63    for (int n = 1; n < pts; ++n) {
64        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
65    }
66    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
67    for (int n = 1; n < pts; ++n) {
68        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
69    }
70    SkDebugf("\n");
71}
72
73static void debugShowCubicLineIntersection(int pts, const SkIntersectionHelper& wt,
74        const SkIntersectionHelper& wn, const SkIntersections& i) {
75    SkASSERT(i.used() == pts);
76    if (!pts) {
77        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " LINE_DEBUG_STR "\n",
78                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), LINE_DEBUG_DATA(wn.pts()));
79        return;
80    }
81    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
82            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
83    for (int n = 1; n < pts; ++n) {
84        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
85    }
86    SkDebugf(" wnTs[0]=%g " LINE_DEBUG_STR, i[1][0], LINE_DEBUG_DATA(wn.pts()));
87    for (int n = 1; n < pts; ++n) {
88        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
89    }
90    SkDebugf("\n");
91}
92
93static void debugShowCubicQuadIntersection(int pts, const SkIntersectionHelper& wt,
94        const SkIntersectionHelper& wn, const SkIntersections& i) {
95    SkASSERT(i.used() == pts);
96    if (!pts) {
97        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " QUAD_DEBUG_STR "\n",
98                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), QUAD_DEBUG_DATA(wn.pts()));
99        return;
100    }
101    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
102            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
103    for (int n = 1; n < pts; ++n) {
104        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
105    }
106    SkDebugf(" wnTs[0]=%g " QUAD_DEBUG_STR, i[1][0], QUAD_DEBUG_DATA(wn.pts()));
107    for (int n = 1; n < pts; ++n) {
108        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
109    }
110    SkDebugf("\n");
111}
112
113static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt,
114        const SkIntersectionHelper& wn, const SkIntersections& i) {
115    SkASSERT(i.used() == pts);
116    if (!pts) {
117        SkDebugf("%s no intersect " CUBIC_DEBUG_STR " " CUBIC_DEBUG_STR "\n",
118                __FUNCTION__, CUBIC_DEBUG_DATA(wt.pts()), CUBIC_DEBUG_DATA(wn.pts()));
119        return;
120    }
121    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
122            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
123    for (int n = 1; n < pts; ++n) {
124        SkDebugf(" " TX_DEBUG_STR(wtTs) " " PT_DEBUG_STR, n, i[0][n], PT_DEBUG_DATA(i, n));
125    }
126    SkDebugf(" wnTs[0]=%g " CUBIC_DEBUG_STR, i[1][0], CUBIC_DEBUG_DATA(wn.pts()));
127    for (int n = 1; n < pts; ++n) {
128        SkDebugf(" " TX_DEBUG_STR(wnTs), n, i[1][n]);
129    }
130    SkDebugf("\n");
131}
132
133static void debugShowCubicIntersection(int pts, const SkIntersectionHelper& wt,
134        const SkIntersections& i) {
135    SkASSERT(i.used() == pts);
136    if (!pts) {
137        SkDebugf("%s no self intersect " CUBIC_DEBUG_STR "\n", __FUNCTION__,
138                CUBIC_DEBUG_DATA(wt.pts()));
139        return;
140    }
141    SkDebugf("%s " T_DEBUG_STR(wtTs, 0) " " CUBIC_DEBUG_STR " " PT_DEBUG_STR, __FUNCTION__,
142            i[0][0], CUBIC_DEBUG_DATA(wt.pts()), PT_DEBUG_DATA(i, 0));
143    SkDebugf(" " T_DEBUG_STR(wtTs, 1), i[1][0]);
144    SkDebugf("\n");
145}
146
147#else
148static void debugShowLineIntersection(int , const SkIntersectionHelper& ,
149        const SkIntersectionHelper& , const SkIntersections& ) {
150}
151
152static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& ,
153        const SkIntersectionHelper& , const SkIntersections& ) {
154}
155
156static void debugShowQuadIntersection(int , const SkIntersectionHelper& ,
157        const SkIntersectionHelper& , const SkIntersections& ) {
158}
159
160static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& ,
161        const SkIntersectionHelper& , const SkIntersections& ) {
162}
163
164static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& ,
165        const SkIntersectionHelper& , const SkIntersections& ) {
166}
167
168static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
169        const SkIntersectionHelper& , const SkIntersections& ) {
170}
171
172static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
173        const SkIntersections& ) {
174}
175#endif
176
177bool AddIntersectTs(SkOpContour* test, SkOpContour* next) {
178    if (test != next) {
179        if (test->bounds().fBottom < next->bounds().fTop) {
180            return false;
181        }
182        if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
183            return true;
184        }
185    }
186    SkIntersectionHelper wt;
187    wt.init(test);
188    bool foundCommonContour = test == next;
189    do {
190        SkIntersectionHelper wn;
191        wn.init(next);
192        if (test == next && !wn.startAfter(wt)) {
193            continue;
194        }
195        do {
196            if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
197                continue;
198            }
199            int pts = 0;
200            SkIntersections ts;
201            bool swap = false;
202            switch (wt.segmentType()) {
203                case SkIntersectionHelper::kHorizontalLine_Segment:
204                    swap = true;
205                    switch (wn.segmentType()) {
206                        case SkIntersectionHelper::kHorizontalLine_Segment:
207                        case SkIntersectionHelper::kVerticalLine_Segment:
208                        case SkIntersectionHelper::kLine_Segment: {
209                            pts = ts.lineHorizontal(wn.pts(), wt.left(),
210                                    wt.right(), wt.y(), wt.xFlipped());
211                            debugShowLineIntersection(pts, wt, wn, ts);
212                            break;
213                        }
214                        case SkIntersectionHelper::kQuad_Segment: {
215                            pts = ts.quadHorizontal(wn.pts(), wt.left(),
216                                    wt.right(), wt.y(), wt.xFlipped());
217                            debugShowQuadLineIntersection(pts, wn, wt, ts);
218                            break;
219                        }
220                        case SkIntersectionHelper::kCubic_Segment: {
221                            pts = ts.cubicHorizontal(wn.pts(), wt.left(),
222                                    wt.right(), wt.y(), wt.xFlipped());
223                            debugShowCubicLineIntersection(pts, wn, wt, ts);
224                            break;
225                        }
226                        default:
227                            SkASSERT(0);
228                    }
229                    break;
230                case SkIntersectionHelper::kVerticalLine_Segment:
231                    swap = true;
232                    switch (wn.segmentType()) {
233                        case SkIntersectionHelper::kHorizontalLine_Segment:
234                        case SkIntersectionHelper::kVerticalLine_Segment:
235                        case SkIntersectionHelper::kLine_Segment: {
236                            pts = ts.lineVertical(wn.pts(), wt.top(),
237                                    wt.bottom(), wt.x(), wt.yFlipped());
238                            debugShowLineIntersection(pts, wt, wn, ts);
239                            break;
240                        }
241                        case SkIntersectionHelper::kQuad_Segment: {
242                            pts = ts.quadVertical(wn.pts(), wt.top(),
243                                    wt.bottom(), wt.x(), wt.yFlipped());
244                            debugShowQuadLineIntersection(pts, wn, wt, ts);
245                            break;
246                        }
247                        case SkIntersectionHelper::kCubic_Segment: {
248                            pts = ts.cubicVertical(wn.pts(), wt.top(),
249                                    wt.bottom(), wt.x(), wt.yFlipped());
250                            debugShowCubicLineIntersection(pts, wn, wt, ts);
251                            break;
252                        }
253                        default:
254                            SkASSERT(0);
255                    }
256                    break;
257                case SkIntersectionHelper::kLine_Segment:
258                    switch (wn.segmentType()) {
259                        case SkIntersectionHelper::kHorizontalLine_Segment:
260                            pts = ts.lineHorizontal(wt.pts(), wn.left(),
261                                    wn.right(), wn.y(), wn.xFlipped());
262                            debugShowLineIntersection(pts, wt, wn, ts);
263                            break;
264                        case SkIntersectionHelper::kVerticalLine_Segment:
265                            pts = ts.lineVertical(wt.pts(), wn.top(),
266                                    wn.bottom(), wn.x(), wn.yFlipped());
267                            debugShowLineIntersection(pts, wt, wn, ts);
268                            break;
269                        case SkIntersectionHelper::kLine_Segment: {
270                            pts = ts.lineLine(wt.pts(), wn.pts());
271                            debugShowLineIntersection(pts, wt, wn, ts);
272                            break;
273                        }
274                        case SkIntersectionHelper::kQuad_Segment: {
275                            swap = true;
276                            pts = ts.quadLine(wn.pts(), wt.pts());
277                            debugShowQuadLineIntersection(pts, wn, wt, ts);
278                            break;
279                        }
280                        case SkIntersectionHelper::kCubic_Segment: {
281                            swap = true;
282                            pts = ts.cubicLine(wn.pts(), wt.pts());
283                            debugShowCubicLineIntersection(pts, wn, wt,  ts);
284                            break;
285                        }
286                        default:
287                            SkASSERT(0);
288                    }
289                    break;
290                case SkIntersectionHelper::kQuad_Segment:
291                    switch (wn.segmentType()) {
292                        case SkIntersectionHelper::kHorizontalLine_Segment:
293                            pts = ts.quadHorizontal(wt.pts(), wn.left(),
294                                    wn.right(), wn.y(), wn.xFlipped());
295                            debugShowQuadLineIntersection(pts, wt, wn, ts);
296                            break;
297                        case SkIntersectionHelper::kVerticalLine_Segment:
298                            pts = ts.quadVertical(wt.pts(), wn.top(),
299                                    wn.bottom(), wn.x(), wn.yFlipped());
300                            debugShowQuadLineIntersection(pts, wt, wn, ts);
301                            break;
302                        case SkIntersectionHelper::kLine_Segment: {
303                            pts = ts.quadLine(wt.pts(), wn.pts());
304                            debugShowQuadLineIntersection(pts, wt, wn, ts);
305                            break;
306                        }
307                        case SkIntersectionHelper::kQuad_Segment: {
308                            pts = ts.quadQuad(wt.pts(), wn.pts());
309                            debugShowQuadIntersection(pts, wt, wn, ts);
310                            break;
311                        }
312                        case SkIntersectionHelper::kCubic_Segment: {
313                            swap = true;
314                            pts = ts.cubicQuad(wn.pts(), wt.pts());
315                            debugShowCubicQuadIntersection(pts, wn, wt, ts);
316                            break;
317                        }
318                        default:
319                            SkASSERT(0);
320                    }
321                    break;
322                case SkIntersectionHelper::kCubic_Segment:
323                    switch (wn.segmentType()) {
324                        case SkIntersectionHelper::kHorizontalLine_Segment:
325                            pts = ts.cubicHorizontal(wt.pts(), wn.left(),
326                                    wn.right(), wn.y(), wn.xFlipped());
327                            debugShowCubicLineIntersection(pts, wt, wn, ts);
328                            break;
329                        case SkIntersectionHelper::kVerticalLine_Segment:
330                            pts = ts.cubicVertical(wt.pts(), wn.top(),
331                                    wn.bottom(), wn.x(), wn.yFlipped());
332                            debugShowCubicLineIntersection(pts, wt, wn, ts);
333                            break;
334                        case SkIntersectionHelper::kLine_Segment: {
335                            pts = ts.cubicLine(wt.pts(), wn.pts());
336                            debugShowCubicLineIntersection(pts, wt, wn, ts);
337                            break;
338                        }
339                        case SkIntersectionHelper::kQuad_Segment: {
340                            pts = ts.cubicQuad(wt.pts(), wn.pts());
341                            debugShowCubicQuadIntersection(pts, wt, wn, ts);
342                            break;
343                        }
344                        case SkIntersectionHelper::kCubic_Segment: {
345                            pts = ts.cubicCubic(wt.pts(), wn.pts());
346                            debugShowCubicIntersection(pts, wt, wn, ts);
347                            break;
348                        }
349                        default:
350                            SkASSERT(0);
351                    }
352                    break;
353                default:
354                    SkASSERT(0);
355            }
356            if (!foundCommonContour && pts > 0) {
357                test->addCross(next);
358                next->addCross(test);
359                foundCommonContour = true;
360            }
361            // in addition to recording T values, record matching segment
362            if (pts == 2) {
363                if (wn.segmentType() <= SkIntersectionHelper::kLine_Segment
364                        && wt.segmentType() <= SkIntersectionHelper::kLine_Segment) {
365                    wt.addCoincident(wn, ts, swap);
366                    continue;
367                }
368                if (wn.segmentType() >= SkIntersectionHelper::kQuad_Segment
369                        && wt.segmentType() >= SkIntersectionHelper::kQuad_Segment
370                        && ts.isCoincident(0)) {
371                    SkASSERT(ts.coincidentUsed() == 2);
372                    wt.addCoincident(wn, ts, swap);
373                    continue;
374                }
375            }
376            for (int pt = 0; pt < pts; ++pt) {
377                SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
378                SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
379                SkPoint point = ts.pt(pt).asSkPoint();
380                int testTAt = wt.addT(wn, point, ts[swap][pt]);
381                int nextTAt = wn.addT(wt, point, ts[!swap][pt]);
382                wt.addOtherT(testTAt, ts[!swap][pt], nextTAt);
383                wn.addOtherT(nextTAt, ts[swap][pt], testTAt);
384            }
385        } while (wn.advance());
386    } while (wt.advance());
387    return true;
388}
389
390void AddSelfIntersectTs(SkOpContour* test) {
391    SkIntersectionHelper wt;
392    wt.init(test);
393    do {
394        if (wt.segmentType() != SkIntersectionHelper::kCubic_Segment) {
395            continue;
396        }
397        SkIntersections ts;
398        int pts = ts.cubic(wt.pts());
399        debugShowCubicIntersection(pts, wt, ts);
400        if (!pts) {
401            continue;
402        }
403        SkASSERT(pts == 1);
404        SkASSERT(ts[0][0] >= 0 && ts[0][0] <= 1);
405        SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1);
406        SkPoint point = ts.pt(0).asSkPoint();
407        int testTAt = wt.addSelfT(wt, point, ts[0][0]);
408        int nextTAt = wt.addT(wt, point, ts[1][0]);
409        wt.addOtherT(testTAt, ts[1][0], nextTAt);
410        wt.addOtherT(nextTAt, ts[0][0], testTAt);
411    } while (wt.advance());
412}
413
414// resolve any coincident pairs found while intersecting, and
415// see if coincidence is formed by clipping non-concident segments
416void CoincidenceCheck(SkTDArray<SkOpContour*>* contourList, int total) {
417    int contourCount = (*contourList).count();
418    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
419        SkOpContour* contour = (*contourList)[cIndex];
420        contour->addCoincidentPoints();
421    }
422    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
423        SkOpContour* contour = (*contourList)[cIndex];
424        contour->calcCoincidentWinding();
425    }
426    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
427        SkOpContour* contour = (*contourList)[cIndex];
428        contour->findTooCloseToCall();
429    }
430}
431