SkAddIntersections.cpp revision 27c46a08a9210e9306b8ea1b00349ec198153c38 
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 (AlmostLessUlps(test->bounds().fBottom, next->bounds().fTop)) {
180            return false;
181        }
182        // OPTIMIZATION: outset contour bounds a smidgen instead?
183        if (!SkPathOpsBounds::Intersects(test->bounds(), next->bounds())) {
184            return true;
185        }
186    }
187    SkIntersectionHelper wt;
188    wt.init(test);
189    bool foundCommonContour = test == next;
190    do {
191        SkIntersectionHelper wn;
192        wn.init(next);
193        if (test == next && !wn.startAfter(wt)) {
194            continue;
195        }
196        do {
197            if (!SkPathOpsBounds::Intersects(wt.bounds(), wn.bounds())) {
198                continue;
199            }
200            int pts = 0;
201            SkIntersections ts;
202            bool swap = false;
203            switch (wt.segmentType()) {
204                case SkIntersectionHelper::kHorizontalLine_Segment:
205                    swap = true;
206                    switch (wn.segmentType()) {
207                        case SkIntersectionHelper::kHorizontalLine_Segment:
208                        case SkIntersectionHelper::kVerticalLine_Segment:
209                        case SkIntersectionHelper::kLine_Segment: {
210                            pts = ts.lineHorizontal(wn.pts(), wt.left(),
211                                    wt.right(), wt.y(), wt.xFlipped());
212                            debugShowLineIntersection(pts, wn, wt, ts);
213                            break;
214                        }
215                        case SkIntersectionHelper::kQuad_Segment: {
216                            pts = ts.quadHorizontal(wn.pts(), wt.left(),
217                                    wt.right(), wt.y(), wt.xFlipped());
218                            debugShowQuadLineIntersection(pts, wn, wt, ts);
219                            break;
220                        }
221                        case SkIntersectionHelper::kCubic_Segment: {
222                            pts = ts.cubicHorizontal(wn.pts(), wt.left(),
223                                    wt.right(), wt.y(), wt.xFlipped());
224                            debugShowCubicLineIntersection(pts, wn, wt, ts);
225                            break;
226                        }
227                        default:
228                            SkASSERT(0);
229                    }
230                    break;
231                case SkIntersectionHelper::kVerticalLine_Segment:
232                    swap = true;
233                    switch (wn.segmentType()) {
234                        case SkIntersectionHelper::kHorizontalLine_Segment:
235                        case SkIntersectionHelper::kVerticalLine_Segment:
236                        case SkIntersectionHelper::kLine_Segment: {
237                            pts = ts.lineVertical(wn.pts(), wt.top(),
238                                    wt.bottom(), wt.x(), wt.yFlipped());
239                            debugShowLineIntersection(pts, wn, wt, ts);
240                            break;
241                        }
242                        case SkIntersectionHelper::kQuad_Segment: {
243                            pts = ts.quadVertical(wn.pts(), wt.top(),
244                                    wt.bottom(), wt.x(), wt.yFlipped());
245                            debugShowQuadLineIntersection(pts, wn, wt, ts);
246                            break;
247                        }
248                        case SkIntersectionHelper::kCubic_Segment: {
249                            pts = ts.cubicVertical(wn.pts(), wt.top(),
250                                    wt.bottom(), wt.x(), wt.yFlipped());
251                            debugShowCubicLineIntersection(pts, wn, wt, ts);
252                            break;
253                        }
254                        default:
255                            SkASSERT(0);
256                    }
257                    break;
258                case SkIntersectionHelper::kLine_Segment:
259                    switch (wn.segmentType()) {
260                        case SkIntersectionHelper::kHorizontalLine_Segment:
261                            pts = ts.lineHorizontal(wt.pts(), wn.left(),
262                                    wn.right(), wn.y(), wn.xFlipped());
263                            debugShowLineIntersection(pts, wt, wn, ts);
264                            break;
265                        case SkIntersectionHelper::kVerticalLine_Segment:
266                            pts = ts.lineVertical(wt.pts(), wn.top(),
267                                    wn.bottom(), wn.x(), wn.yFlipped());
268                            debugShowLineIntersection(pts, wt, wn, ts);
269                            break;
270                        case SkIntersectionHelper::kLine_Segment: {
271                            pts = ts.lineLine(wt.pts(), wn.pts());
272                            debugShowLineIntersection(pts, wt, wn, ts);
273                            break;
274                        }
275                        case SkIntersectionHelper::kQuad_Segment: {
276                            swap = true;
277                            pts = ts.quadLine(wn.pts(), wt.pts());
278                            debugShowQuadLineIntersection(pts, wn, wt, ts);
279                            break;
280                        }
281                        case SkIntersectionHelper::kCubic_Segment: {
282                            swap = true;
283                            pts = ts.cubicLine(wn.pts(), wt.pts());
284                            debugShowCubicLineIntersection(pts, wn, wt,  ts);
285                            break;
286                        }
287                        default:
288                            SkASSERT(0);
289                    }
290                    break;
291                case SkIntersectionHelper::kQuad_Segment:
292                    switch (wn.segmentType()) {
293                        case SkIntersectionHelper::kHorizontalLine_Segment:
294                            pts = ts.quadHorizontal(wt.pts(), wn.left(),
295                                    wn.right(), wn.y(), wn.xFlipped());
296                            debugShowQuadLineIntersection(pts, wt, wn, ts);
297                            break;
298                        case SkIntersectionHelper::kVerticalLine_Segment:
299                            pts = ts.quadVertical(wt.pts(), wn.top(),
300                                    wn.bottom(), wn.x(), wn.yFlipped());
301                            debugShowQuadLineIntersection(pts, wt, wn, ts);
302                            break;
303                        case SkIntersectionHelper::kLine_Segment: {
304                            pts = ts.quadLine(wt.pts(), wn.pts());
305                            debugShowQuadLineIntersection(pts, wt, wn, ts);
306                            break;
307                        }
308                        case SkIntersectionHelper::kQuad_Segment: {
309                            pts = ts.quadQuad(wt.pts(), wn.pts());
310                            debugShowQuadIntersection(pts, wt, wn, ts);
311                            break;
312                        }
313                        case SkIntersectionHelper::kCubic_Segment: {
314                            swap = true;
315                            pts = ts.cubicQuad(wn.pts(), wt.pts());
316                            debugShowCubicQuadIntersection(pts, wn, wt, ts);
317                            break;
318                        }
319                        default:
320                            SkASSERT(0);
321                    }
322                    break;
323                case SkIntersectionHelper::kCubic_Segment:
324                    switch (wn.segmentType()) {
325                        case SkIntersectionHelper::kHorizontalLine_Segment:
326                            pts = ts.cubicHorizontal(wt.pts(), wn.left(),
327                                    wn.right(), wn.y(), wn.xFlipped());
328                            debugShowCubicLineIntersection(pts, wt, wn, ts);
329                            break;
330                        case SkIntersectionHelper::kVerticalLine_Segment:
331                            pts = ts.cubicVertical(wt.pts(), wn.top(),
332                                    wn.bottom(), wn.x(), wn.yFlipped());
333                            debugShowCubicLineIntersection(pts, wt, wn, ts);
334                            break;
335                        case SkIntersectionHelper::kLine_Segment: {
336                            pts = ts.cubicLine(wt.pts(), wn.pts());
337                            debugShowCubicLineIntersection(pts, wt, wn, ts);
338                            break;
339                        }
340                        case SkIntersectionHelper::kQuad_Segment: {
341                            pts = ts.cubicQuad(wt.pts(), wn.pts());
342                            debugShowCubicQuadIntersection(pts, wt, wn, ts);
343                            break;
344                        }
345                        case SkIntersectionHelper::kCubic_Segment: {
346                            pts = ts.cubicCubic(wt.pts(), wn.pts());
347                            debugShowCubicIntersection(pts, wt, wn, ts);
348                            break;
349                        }
350                        default:
351                            SkASSERT(0);
352                    }
353                    break;
354                default:
355                    SkASSERT(0);
356            }
357            if (!foundCommonContour && pts > 0) {
358                test->addCross(next);
359                next->addCross(test);
360                foundCommonContour = true;
361            }
362            // in addition to recording T values, record matching segment
363            if (pts == 2) {
364                if (wn.segmentType() <= SkIntersectionHelper::kLine_Segment
365                        && wt.segmentType() <= SkIntersectionHelper::kLine_Segment) {
366                    if (wt.addCoincident(wn, ts, swap)) {
367                        continue;
368                    }
369                    ts.cleanUpCoincidence();  // prefer (t == 0 or t == 1)
370                    pts = 1;
371                } else if (wn.segmentType() >= SkIntersectionHelper::kQuad_Segment
372                        && wt.segmentType() >= SkIntersectionHelper::kQuad_Segment
373                        && ts.isCoincident(0)) {
374                    SkASSERT(ts.coincidentUsed() == 2);
375                    if (wt.addCoincident(wn, ts, swap)) {
376                        continue;
377                    }
378                    ts.cleanUpCoincidence();  // prefer (t == 0 or t == 1)
379                    pts = 1;
380                }
381            }
382            if (pts >= 2) {
383                for (int pt = 0; pt < pts - 1; ++pt) {
384                    const SkDPoint& point = ts.pt(pt);
385                    const SkDPoint& next = ts.pt(pt + 1);
386                    if (wt.isPartial(ts[swap][pt], ts[swap][pt + 1], point, next)
387                            && wn.isPartial(ts[!swap][pt], ts[!swap][pt + 1], point, next)) {
388                        if (!wt.addPartialCoincident(wn, ts, pt, swap)) {
389                            // remove extra point if two map to same float values
390                            ts.cleanUpCoincidence();  // prefer (t == 0 or t == 1)
391                            pts = 1;
392                        }
393                    }
394                }
395            }
396            for (int pt = 0; pt < pts; ++pt) {
397                SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1);
398                SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1);
399                SkPoint point = ts.pt(pt).asSkPoint();
400                wt.alignTPt(wn, swap, pt, &ts, &point);
401                int testTAt = wt.addT(wn, point, ts[swap][pt]);
402                int nextTAt = wn.addT(wt, point, ts[!swap][pt]);
403                wt.addOtherT(testTAt, ts[!swap][pt], nextTAt);
404                wn.addOtherT(nextTAt, ts[swap][pt], testTAt);
405            }
406        } while (wn.advance());
407    } while (wt.advance());
408    return true;
409}
410
411void AddSelfIntersectTs(SkOpContour* test) {
412    SkIntersectionHelper wt;
413    wt.init(test);
414    do {
415        if (wt.segmentType() != SkIntersectionHelper::kCubic_Segment) {
416            continue;
417        }
418        SkIntersections ts;
419        int pts = ts.cubic(wt.pts());
420        debugShowCubicIntersection(pts, wt, ts);
421        if (!pts) {
422            continue;
423        }
424        SkASSERT(pts == 1);
425        SkASSERT(ts[0][0] >= 0 && ts[0][0] <= 1);
426        SkASSERT(ts[1][0] >= 0 && ts[1][0] <= 1);
427        SkPoint point = ts.pt(0).asSkPoint();
428        int testTAt = wt.addSelfT(point, ts[0][0]);
429        int nextTAt = wt.addSelfT(point, ts[1][0]);
430        wt.addOtherT(testTAt, ts[1][0], nextTAt);
431        wt.addOtherT(nextTAt, ts[0][0], testTAt);
432    } while (wt.advance());
433}
434
435// resolve any coincident pairs found while intersecting, and
436// see if coincidence is formed by clipping non-concident segments
437bool CoincidenceCheck(SkTArray<SkOpContour*, true>* contourList, int total) {
438    int contourCount = (*contourList).count();
439    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
440        SkOpContour* contour = (*contourList)[cIndex];
441        contour->resolveNearCoincidence();
442    }
443    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
444        SkOpContour* contour = (*contourList)[cIndex];
445        contour->addCoincidentPoints();
446    }
447    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
448        SkOpContour* contour = (*contourList)[cIndex];
449        if (!contour->calcCoincidentWinding()) {
450            return false;
451        }
452    }
453    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
454        SkOpContour* contour = (*contourList)[cIndex];
455        contour->calcPartialCoincidentWinding();
456    }
457    return true;
458}
459