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
debugShowLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)12 static 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
debugShowQuadLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)32 static 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
debugShowQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)53 static 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
debugShowCubicLineIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)73 static 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
debugShowCubicQuadIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)93 static 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
debugShowCubicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersectionHelper & wn,const SkIntersections & i)113 static 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
debugShowCubicIntersection(int pts,const SkIntersectionHelper & wt,const SkIntersections & i)133 static 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
debugShowLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)148 static void debugShowLineIntersection(int , const SkIntersectionHelper& ,
149 const SkIntersectionHelper& , const SkIntersections& ) {
150 }
151
debugShowQuadLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)152 static void debugShowQuadLineIntersection(int , const SkIntersectionHelper& ,
153 const SkIntersectionHelper& , const SkIntersections& ) {
154 }
155
debugShowQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)156 static void debugShowQuadIntersection(int , const SkIntersectionHelper& ,
157 const SkIntersectionHelper& , const SkIntersections& ) {
158 }
159
debugShowCubicLineIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)160 static void debugShowCubicLineIntersection(int , const SkIntersectionHelper& ,
161 const SkIntersectionHelper& , const SkIntersections& ) {
162 }
163
debugShowCubicQuadIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)164 static void debugShowCubicQuadIntersection(int , const SkIntersectionHelper& ,
165 const SkIntersectionHelper& , const SkIntersections& ) {
166 }
167
debugShowCubicIntersection(int,const SkIntersectionHelper &,const SkIntersectionHelper &,const SkIntersections &)168 static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
169 const SkIntersectionHelper& , const SkIntersections& ) {
170 }
171
debugShowCubicIntersection(int,const SkIntersectionHelper &,const SkIntersections &)172 static void debugShowCubicIntersection(int , const SkIntersectionHelper& ,
173 const SkIntersections& ) {
174 }
175 #endif
176
AddIntersectTs(SkOpContour * test,SkOpContour * next)177 bool 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
AddSelfIntersectTs(SkOpContour * test)411 void 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
CoincidenceCheck(SkTArray<SkOpContour *,true> * contourList,int total)437 void 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 contour->calcCoincidentWinding();
450 }
451 for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
452 SkOpContour* contour = (*contourList)[cIndex];
453 contour->calcPartialCoincidentWinding();
454 }
455 }
456