• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2 * Copyright 2013 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 "SkIntersections.h"
8 #include "SkOpContour.h"
9 #include "SkPathWriter.h"
10 #include "SkTSort.h"
11 
addCoincident(int index,SkOpContour * other,int otherIndex,const SkIntersections & ts,bool swap)12 bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
13         const SkIntersections& ts, bool swap) {
14     SkPoint pt0 = ts.pt(0).asSkPoint();
15     SkPoint pt1 = ts.pt(1).asSkPoint();
16     if (pt0 == pt1) {
17         // FIXME: one could imagine a case where it would be incorrect to ignore this
18         // suppose two self-intersecting cubics overlap to be coincident --
19         // this needs to check that by some measure the t values are far enough apart
20         // or needs to check to see if the self-intersection bit was set on the cubic segment
21         return false;
22     }
23     SkCoincidence& coincidence = fCoincidences.push_back();
24     coincidence.fOther = other;
25     coincidence.fSegments[0] = index;
26     coincidence.fSegments[1] = otherIndex;
27     coincidence.fTs[swap][0] = ts[0][0];
28     coincidence.fTs[swap][1] = ts[0][1];
29     coincidence.fTs[!swap][0] = ts[1][0];
30     coincidence.fTs[!swap][1] = ts[1][1];
31     coincidence.fPts[swap][0] = pt0;
32     coincidence.fPts[swap][1] = pt1;
33     bool nearStart = ts.nearlySame(0);
34     bool nearEnd = ts.nearlySame(1);
35     coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0;
36     coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1;
37     coincidence.fNearly[0] = nearStart;
38     coincidence.fNearly[1] = nearEnd;
39     return true;
40 }
41 
nonVerticalSegment(int * start,int * end)42 SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
43     int segmentCount = fSortedSegments.count();
44     SkASSERT(segmentCount > 0);
45     for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
46         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
47         if (testSegment->done()) {
48             continue;
49         }
50         *start = *end = 0;
51         while (testSegment->nextCandidate(start, end)) {
52             if (!testSegment->isVertical(*start, *end)) {
53                 return testSegment;
54             }
55         }
56     }
57     return NULL;
58 }
59 
60 // if one is very large the smaller may have collapsed to nothing
bump_out_close_span(double * startTPtr,double * endTPtr)61 static void bump_out_close_span(double* startTPtr, double* endTPtr) {
62     double startT = *startTPtr;
63     double endT = *endTPtr;
64     if (approximately_negative(endT - startT)) {
65         if (endT <= 1 - FLT_EPSILON) {
66             *endTPtr += FLT_EPSILON;
67             SkASSERT(*endTPtr <= 1);
68         } else {
69             *startTPtr -= FLT_EPSILON;
70             SkASSERT(*startTPtr >= 0);
71         }
72     }
73 }
74 
75 // first pass, add missing T values
76 // second pass, determine winding values of overlaps
addCoincidentPoints()77 void SkOpContour::addCoincidentPoints() {
78     int count = fCoincidences.count();
79     for (int index = 0; index < count; ++index) {
80         SkCoincidence& coincidence = fCoincidences[index];
81         int thisIndex = coincidence.fSegments[0];
82         SkOpSegment& thisOne = fSegments[thisIndex];
83         SkOpContour* otherContour = coincidence.fOther;
84         int otherIndex = coincidence.fSegments[1];
85         SkOpSegment& other = otherContour->fSegments[otherIndex];
86         if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
87             // OPTIMIZATION: remove from array
88             continue;
89         }
90     #if DEBUG_CONCIDENT
91         thisOne.debugShowTs("-");
92         other.debugShowTs("o");
93     #endif
94         double startT = coincidence.fTs[0][0];
95         double endT = coincidence.fTs[0][1];
96         bool startSwapped, oStartSwapped, cancelers;
97         if ((cancelers = startSwapped = startT > endT)) {
98             SkTSwap(startT, endT);
99         }
100         bump_out_close_span(&startT, &endT);
101         SkASSERT(!approximately_negative(endT - startT));
102         double oStartT = coincidence.fTs[1][0];
103         double oEndT = coincidence.fTs[1][1];
104         if ((oStartSwapped = oStartT > oEndT)) {
105             SkTSwap(oStartT, oEndT);
106             cancelers ^= true;
107         }
108         bump_out_close_span(&oStartT, &oEndT);
109         SkASSERT(!approximately_negative(oEndT - oStartT));
110         const SkPoint& startPt = coincidence.fPts[0][startSwapped];
111         if (cancelers) {
112             // make sure startT and endT have t entries
113             if (startT > 0 || oEndT < 1
114                     || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
115                 thisOne.addTPair(startT, &other, oEndT, true, startPt,
116                         coincidence.fPts[1][startSwapped]);
117             }
118             const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped];
119             if (oStartT > 0 || endT < 1
120                     || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
121                 other.addTPair(oStartT, &thisOne, endT, true, oStartPt,
122                         coincidence.fPts[0][oStartSwapped]);
123             }
124         } else {
125             if (startT > 0 || oStartT > 0
126                     || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
127                 thisOne.addTPair(startT, &other, oStartT, true, startPt,
128                         coincidence.fPts[1][startSwapped]);
129             }
130             const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped];
131             if (endT < 1 || oEndT < 1
132                     || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
133                 other.addTPair(oEndT, &thisOne, endT, true, oEndPt,
134                         coincidence.fPts[0][!oStartSwapped]);
135             }
136         }
137     #if DEBUG_CONCIDENT
138         thisOne.debugShowTs("+");
139         other.debugShowTs("o");
140     #endif
141     }
142     // if there are multiple pairs of coincidence that share an edge, see if the opposite
143     // are also coincident
144     for (int index = 0; index < count - 1; ++index) {
145         const SkCoincidence& coincidence = fCoincidences[index];
146         int thisIndex = coincidence.fSegments[0];
147         SkOpContour* otherContour = coincidence.fOther;
148         int otherIndex = coincidence.fSegments[1];
149         for (int idx2 = 1; idx2 < count; ++idx2) {
150             const SkCoincidence& innerCoin = fCoincidences[idx2];
151             int innerThisIndex = innerCoin.fSegments[0];
152             if (thisIndex == innerThisIndex) {
153                 checkCoincidentPair(coincidence, 1, innerCoin, 1, false);
154             }
155             if (this == otherContour && otherIndex == innerThisIndex) {
156                 checkCoincidentPair(coincidence, 0, innerCoin, 1, false);
157             }
158             SkOpContour* innerOtherContour = innerCoin.fOther;
159             innerThisIndex = innerCoin.fSegments[1];
160             if (this == innerOtherContour && thisIndex == innerThisIndex) {
161                 checkCoincidentPair(coincidence, 1, innerCoin, 0, false);
162             }
163             if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
164                 checkCoincidentPair(coincidence, 0, innerCoin, 0, false);
165             }
166         }
167     }
168 }
169 
addPartialCoincident(int index,SkOpContour * other,int otherIndex,const SkIntersections & ts,int ptIndex,bool swap)170 bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
171         const SkIntersections& ts, int ptIndex, bool swap) {
172     SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
173     SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
174     if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
175         // FIXME: one could imagine a case where it would be incorrect to ignore this
176         // suppose two self-intersecting cubics overlap to form a partial coincidence --
177         // although it isn't clear why the regular coincidence could wouldn't pick this up
178         // this is exceptional enough to ignore for now
179         return false;
180     }
181     SkCoincidence& coincidence = fPartialCoincidences.push_back();
182     coincidence.fOther = other;
183     coincidence.fSegments[0] = index;
184     coincidence.fSegments[1] = otherIndex;
185     coincidence.fTs[swap][0] = ts[0][ptIndex];
186     coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
187     coincidence.fTs[!swap][0] = ts[1][ptIndex];
188     coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
189     coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0;
190     coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1;
191     coincidence.fNearly[0] = 0;
192     coincidence.fNearly[1] = 0;
193     return true;
194 }
195 
align(const SkOpSegment::AlignedSpan & aligned,bool swap,SkCoincidence * coincidence)196 void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap,
197         SkCoincidence* coincidence) {
198     for (int idx2 = 0; idx2 < 2; ++idx2) {
199         if (coincidence->fPts[0][idx2] == aligned.fOldPt
200                 && coincidence->fTs[swap][idx2] == aligned.fOldT) {
201             SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt));
202             coincidence->fPts[0][idx2] = aligned.fPt;
203             SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT));
204             coincidence->fTs[swap][idx2] = aligned.fT;
205         }
206     }
207 }
208 
alignCoincidence(const SkOpSegment::AlignedSpan & aligned,SkTArray<SkCoincidence,true> * coincidences)209 void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
210         SkTArray<SkCoincidence, true>* coincidences) {
211     int count = coincidences->count();
212     for (int index = 0; index < count; ++index) {
213         SkCoincidence& coincidence = (*coincidences)[index];
214         int thisIndex = coincidence.fSegments[0];
215         const SkOpSegment* thisOne = &fSegments[thisIndex];
216         const SkOpContour* otherContour = coincidence.fOther;
217         int otherIndex = coincidence.fSegments[1];
218         const SkOpSegment* other = &otherContour->fSegments[otherIndex];
219         if (thisOne == aligned.fOther1 && other == aligned.fOther2) {
220             align(aligned, false, &coincidence);
221         } else if (thisOne == aligned.fOther2 && other == aligned.fOther1) {
222             align(aligned, true, &coincidence);
223         }
224     }
225 }
226 
alignTPt(int segmentIndex,const SkOpContour * other,int otherIndex,bool swap,int tIndex,SkIntersections * ts,SkPoint * point) const227 void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex,
228         bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const {
229     int zeroPt;
230     if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) {
231         alignPt(segmentIndex, point, zeroPt);
232     }
233     if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) {
234         other->alignPt(otherIndex, point, zeroPt);
235     }
236 }
237 
alignPt(int index,SkPoint * point,int zeroPt) const238 void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const {
239     const SkOpSegment& segment = fSegments[index];
240     if (0 == zeroPt) {
241         *point = segment.pts()[0];
242     } else {
243         *point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
244     }
245 }
246 
alignT(bool swap,int tIndex,SkIntersections * ts) const247 int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const {
248     double tVal = (*ts)[swap][tIndex];
249     if (tVal != 0 && precisely_zero(tVal)) {
250         ts->set(swap, tIndex, 0);
251         return 0;
252     }
253      if (tVal != 1 && precisely_equal(tVal, 1)) {
254         ts->set(swap, tIndex, 1);
255         return 1;
256     }
257     return -1;
258 }
259 
calcAngles()260 bool SkOpContour::calcAngles() {
261     int segmentCount = fSegments.count();
262     for (int test = 0; test < segmentCount; ++test) {
263         if (!fSegments[test].calcAngles()) {
264             return false;
265         }
266     }
267     return true;
268 }
269 
calcCoincidentWinding()270 bool SkOpContour::calcCoincidentWinding() {
271     int count = fCoincidences.count();
272 #if DEBUG_CONCIDENT
273     if (count > 0) {
274         SkDebugf("%s count=%d\n", __FUNCTION__, count);
275     }
276 #endif
277     for (int index = 0; index < count; ++index) {
278         SkCoincidence& coincidence = fCoincidences[index];
279         if (!calcCommonCoincidentWinding(coincidence)) {
280             return false;
281         }
282     }
283     return true;
284 }
285 
calcPartialCoincidentWinding()286 void SkOpContour::calcPartialCoincidentWinding() {
287     int count = fPartialCoincidences.count();
288 #if DEBUG_CONCIDENT
289     if (count > 0) {
290         SkDebugf("%s count=%d\n", __FUNCTION__, count);
291     }
292 #endif
293     for (int index = 0; index < count; ++index) {
294         SkCoincidence& coincidence = fPartialCoincidences[index];
295         calcCommonCoincidentWinding(coincidence);
296     }
297     // if there are multiple pairs of partial coincidence that share an edge, see if the opposite
298     // are also coincident
299     for (int index = 0; index < count - 1; ++index) {
300         const SkCoincidence& coincidence = fPartialCoincidences[index];
301         int thisIndex = coincidence.fSegments[0];
302         SkOpContour* otherContour = coincidence.fOther;
303         int otherIndex = coincidence.fSegments[1];
304         for (int idx2 = 1; idx2 < count; ++idx2) {
305             const SkCoincidence& innerCoin = fPartialCoincidences[idx2];
306             int innerThisIndex = innerCoin.fSegments[0];
307             if (thisIndex == innerThisIndex) {
308                 checkCoincidentPair(coincidence, 1, innerCoin, 1, true);
309             }
310             if (this == otherContour && otherIndex == innerThisIndex) {
311                 checkCoincidentPair(coincidence, 0, innerCoin, 1, true);
312             }
313             SkOpContour* innerOtherContour = innerCoin.fOther;
314             innerThisIndex = innerCoin.fSegments[1];
315             if (this == innerOtherContour && thisIndex == innerThisIndex) {
316                 checkCoincidentPair(coincidence, 1, innerCoin, 0, true);
317             }
318             if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
319                 checkCoincidentPair(coincidence, 0, innerCoin, 0, true);
320             }
321         }
322     }
323 }
324 
checkCoincidentPair(const SkCoincidence & oneCoin,int oneIdx,const SkCoincidence & twoCoin,int twoIdx,bool partial)325 void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
326         const SkCoincidence& twoCoin, int twoIdx, bool partial) {
327     SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther));
328     SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]);
329     // look for common overlap
330     double min = SK_ScalarMax;
331     double max = SK_ScalarMin;
332     double min1 = oneCoin.fTs[!oneIdx][0];
333     double max1 = oneCoin.fTs[!oneIdx][1];
334     double min2 = twoCoin.fTs[!twoIdx][0];
335     double max2 = twoCoin.fTs[!twoIdx][1];
336     bool cancelers = (min1 < max1) != (min2 < max2);
337     if (min1 > max1) {
338         SkTSwap(min1, max1);
339     }
340     if (min2 > max2) {
341         SkTSwap(min2, max2);
342     }
343     if (between(min1, min2, max1)) {
344         min = min2;
345     }
346     if (between(min1, max2, max1)) {
347         max = max2;
348     }
349     if (between(min2, min1, max2)) {
350         min = SkTMin(min, min1);
351     }
352     if (between(min2, max1, max2)) {
353         max = SkTMax(max, max1);
354     }
355     if (min >= max) {
356         return;  // no overlap
357     }
358     // look to see if opposite are different segments
359     int seg1Index = oneCoin.fSegments[oneIdx];
360     int seg2Index = twoCoin.fSegments[twoIdx];
361     if (seg1Index == seg2Index) {
362         return;
363     }
364     SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this;
365     SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this;
366     SkOpSegment* segment1 = &contour1->fSegments[seg1Index];
367     SkOpSegment* segment2 = &contour2->fSegments[seg2Index];
368     // find opposite t value ranges corresponding to reference min/max range
369     const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther;
370     const int refSegIndex = oneCoin.fSegments[!oneIdx];
371     const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex];
372     int seg1Start = segment1->findOtherT(min, refSegment);
373     int seg1End = segment1->findOtherT(max, refSegment);
374     int seg2Start = segment2->findOtherT(min, refSegment);
375     int seg2End = segment2->findOtherT(max, refSegment);
376     // if the opposite pairs already contain min/max, we're done
377     if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) {
378         return;
379     }
380     double loEnd = SkTMin(min1, min2);
381     double hiEnd = SkTMax(max1, max2);
382     // insert the missing coincident point(s)
383     double missingT1 = -1;
384     double otherT1 = -1;
385     if (seg1Start < 0) {
386         if (seg2Start < 0) {
387             return;
388         }
389         missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
390                 segment2, seg1End);
391         if (missingT1 < 0) {
392             return;
393         }
394         const SkOpSpan* missingSpan = &segment2->span(seg2Start);
395         otherT1 = missingSpan->fT;
396     } else if (seg2Start < 0) {
397         SkASSERT(seg1Start >= 0);
398         missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
399                 segment1, seg2End);
400         if (missingT1 < 0) {
401             return;
402         }
403         const SkOpSpan* missingSpan = &segment1->span(seg1Start);
404         otherT1 = missingSpan->fT;
405     }
406     SkPoint missingPt1;
407     SkOpSegment* addTo1 = NULL;
408     SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1;
409     int minTIndex = refSegment->findExactT(min, addOther1);
410     SkASSERT(minTIndex >= 0);
411     if (missingT1 >= 0) {
412         missingPt1 = refSegment->span(minTIndex).fPt;
413         addTo1 = seg1Start < 0 ? segment1 : segment2;
414     }
415     double missingT2 = -1;
416     double otherT2 = -1;
417     if (seg1End < 0) {
418         if (seg2End < 0) {
419             return;
420         }
421         missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
422                 segment2, seg1Start);
423         if (missingT2 < 0) {
424             return;
425         }
426         const SkOpSpan* missingSpan = &segment2->span(seg2End);
427         otherT2 = missingSpan->fT;
428     } else if (seg2End < 0) {
429         SkASSERT(seg1End >= 0);
430         missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
431                 segment1, seg2Start);
432         if (missingT2 < 0) {
433             return;
434         }
435         const SkOpSpan* missingSpan = &segment1->span(seg1End);
436         otherT2 = missingSpan->fT;
437     }
438     SkPoint missingPt2;
439     SkOpSegment* addTo2 = NULL;
440     SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1;
441     int maxTIndex = refSegment->findExactT(max, addOther2);
442     SkASSERT(maxTIndex >= 0);
443     if (missingT2 >= 0) {
444         missingPt2 = refSegment->span(maxTIndex).fPt;
445         addTo2 = seg1End < 0 ? segment1 : segment2;
446     }
447     if (missingT1 >= 0) {
448         addTo1->pinT(missingPt1, &missingT1);
449         addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1);
450     } else {
451         SkASSERT(minTIndex >= 0);
452         missingPt1 = refSegment->span(minTIndex).fPt;
453     }
454     if (missingT2 >= 0) {
455         addTo2->pinT(missingPt2, &missingT2);
456         addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2);
457     } else {
458         SkASSERT(minTIndex >= 0);
459         missingPt2 = refSegment->span(maxTIndex).fPt;
460     }
461     if (!partial) {
462         return;
463     }
464     if (cancelers) {
465         if (missingT1 >= 0) {
466             if (addTo1->reversePoints(missingPt1, missingPt2)) {
467                 SkTSwap(missingPt1, missingPt2);
468             }
469             addTo1->addTCancel(missingPt1, missingPt2, addOther1);
470         } else {
471             if (addTo2->reversePoints(missingPt1, missingPt2)) {
472                 SkTSwap(missingPt1, missingPt2);
473             }
474             addTo2->addTCancel(missingPt1, missingPt2, addOther2);
475         }
476     } else if (missingT1 >= 0) {
477         SkAssertResult(addTo1->addTCoincident(missingPt1, missingPt2,
478                 addTo1 == addTo2 ? missingT2 : otherT2, addOther1));
479     } else {
480         SkAssertResult(addTo2->addTCoincident(missingPt2, missingPt1,
481                 addTo2 == addTo1 ? missingT1 : otherT1, addOther2));
482     }
483 }
484 
joinCoincidence(const SkTArray<SkCoincidence,true> & coincidences,bool partial)485 void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
486     int count = coincidences.count();
487 #if DEBUG_CONCIDENT
488     if (count > 0) {
489         SkDebugf("%s count=%d\n", __FUNCTION__, count);
490     }
491 #endif
492     // look for a lineup where the partial implies another adjoining coincidence
493     for (int index = 0; index < count; ++index) {
494         const SkCoincidence& coincidence = coincidences[index];
495         int thisIndex = coincidence.fSegments[0];
496         SkOpSegment& thisOne = fSegments[thisIndex];
497         if (thisOne.done()) {
498             continue;
499         }
500         SkOpContour* otherContour = coincidence.fOther;
501         int otherIndex = coincidence.fSegments[1];
502         SkOpSegment& other = otherContour->fSegments[otherIndex];
503         if (other.done()) {
504             continue;
505         }
506         double startT = coincidence.fTs[0][0];
507         double endT = coincidence.fTs[0][1];
508         if (startT == endT) {  // this can happen in very large compares
509             continue;
510         }
511         double oStartT = coincidence.fTs[1][0];
512         double oEndT = coincidence.fTs[1][1];
513         if (oStartT == oEndT) {
514             continue;
515         }
516         bool swapStart = startT > endT;
517         bool swapOther = oStartT > oEndT;
518         const SkPoint* startPt = &coincidence.fPts[0][0];
519         const SkPoint* endPt = &coincidence.fPts[0][1];
520         if (swapStart) {
521             SkTSwap(startT, endT);
522             SkTSwap(oStartT, oEndT);
523             SkTSwap(startPt, endPt);
524         }
525         bool cancel = swapOther != swapStart;
526         int step = swapStart ? -1 : 1;
527         int oStep = swapOther ? -1 : 1;
528         double oMatchStart = cancel ? oEndT : oStartT;
529         if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
530             bool added = false;
531             if (oMatchStart != 0) {
532                 const SkPoint& oMatchStartPt = cancel ? *endPt : *startPt;
533                 added = thisOne.joinCoincidence(&other, oMatchStart, oMatchStartPt, oStep, cancel);
534             }
535             if (!cancel && startT != 0 && !added) {
536                 (void) other.joinCoincidence(&thisOne, startT, *startPt, step, cancel);
537             }
538         }
539         double oMatchEnd = cancel ? oStartT : oEndT;
540         if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
541             bool added = false;
542             if (cancel && endT != 1 && !added) {
543                 (void) other.joinCoincidence(&thisOne, endT, *endPt, -step, cancel);
544             }
545         }
546     }
547 }
548 
calcCommonCoincidentWinding(const SkCoincidence & coincidence)549 bool SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
550     if (coincidence.fNearly[0] && coincidence.fNearly[1]) {
551         return true;
552     }
553     int thisIndex = coincidence.fSegments[0];
554     SkOpSegment& thisOne = fSegments[thisIndex];
555     if (thisOne.done()) {
556         return true;
557     }
558     SkOpContour* otherContour = coincidence.fOther;
559     int otherIndex = coincidence.fSegments[1];
560     SkOpSegment& other = otherContour->fSegments[otherIndex];
561     if (other.done()) {
562         return true;
563     }
564     double startT = coincidence.fTs[0][0];
565     double endT = coincidence.fTs[0][1];
566     const SkPoint* startPt = &coincidence.fPts[0][0];
567     const SkPoint* endPt = &coincidence.fPts[0][1];
568     bool cancelers;
569     if ((cancelers = startT > endT)) {
570         SkTSwap<double>(startT, endT);
571         SkTSwap<const SkPoint*>(startPt, endPt);
572     }
573     bump_out_close_span(&startT, &endT);
574     SkASSERT(!approximately_negative(endT - startT));
575     double oStartT = coincidence.fTs[1][0];
576     double oEndT = coincidence.fTs[1][1];
577     if (oStartT > oEndT) {
578         SkTSwap<double>(oStartT, oEndT);
579         cancelers ^= true;
580     }
581     bump_out_close_span(&oStartT, &oEndT);
582     SkASSERT(!approximately_negative(oEndT - oStartT));
583     bool success = true;
584     if (cancelers) {
585         thisOne.addTCancel(*startPt, *endPt, &other);
586     } else {
587         success = thisOne.addTCoincident(*startPt, *endPt, endT, &other);
588     }
589 #if DEBUG_CONCIDENT
590     thisOne.debugShowTs("p");
591     other.debugShowTs("o");
592 #endif
593     return success;
594 }
595 
resolveNearCoincidence()596 void SkOpContour::resolveNearCoincidence() {
597     int count = fCoincidences.count();
598     for (int index = 0; index < count; ++index) {
599         SkCoincidence& coincidence = fCoincidences[index];
600         if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) {
601             continue;
602         }
603         int thisIndex = coincidence.fSegments[0];
604         SkOpSegment& thisOne = fSegments[thisIndex];
605         SkOpContour* otherContour = coincidence.fOther;
606         int otherIndex = coincidence.fSegments[1];
607         SkOpSegment& other = otherContour->fSegments[otherIndex];
608         if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
609             // OPTIMIZATION: remove from coincidence array
610             continue;
611         }
612     #if DEBUG_CONCIDENT
613         thisOne.debugShowTs("-");
614         other.debugShowTs("o");
615     #endif
616         double startT = coincidence.fTs[0][0];
617         double endT = coincidence.fTs[0][1];
618         bool cancelers;
619         if ((cancelers = startT > endT)) {
620             SkTSwap<double>(startT, endT);
621         }
622         if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
623             if (endT <= 1 - FLT_EPSILON) {
624                 endT += FLT_EPSILON;
625                 SkASSERT(endT <= 1);
626             } else {
627                 startT -= FLT_EPSILON;
628                 SkASSERT(startT >= 0);
629             }
630         }
631         SkASSERT(!approximately_negative(endT - startT));
632         double oStartT = coincidence.fTs[1][0];
633         double oEndT = coincidence.fTs[1][1];
634         if (oStartT > oEndT) {
635             SkTSwap<double>(oStartT, oEndT);
636             cancelers ^= true;
637         }
638         SkASSERT(!approximately_negative(oEndT - oStartT));
639         if (cancelers) {
640             thisOne.blindCancel(coincidence, &other);
641         } else {
642             thisOne.blindCoincident(coincidence, &other);
643         }
644     }
645 }
646 
sortAngles()647 void SkOpContour::sortAngles() {
648     int segmentCount = fSegments.count();
649     for (int test = 0; test < segmentCount; ++test) {
650         fSegments[test].sortAngles();
651     }
652 }
653 
sortSegments()654 void SkOpContour::sortSegments() {
655     int segmentCount = fSegments.count();
656     fSortedSegments.push_back_n(segmentCount);
657     for (int test = 0; test < segmentCount; ++test) {
658         fSortedSegments[test] = &fSegments[test];
659     }
660     SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
661     fFirstSorted = 0;
662 }
663 
toPath(SkPathWriter * path) const664 void SkOpContour::toPath(SkPathWriter* path) const {
665     int segmentCount = fSegments.count();
666     const SkPoint& pt = fSegments.front().pts()[0];
667     path->deferredMove(pt);
668     for (int test = 0; test < segmentCount; ++test) {
669         fSegments[test].addCurveTo(0, 1, path, true);
670     }
671     path->close();
672 }
673 
topSortableSegment(const SkPoint & topLeft,SkPoint * bestXY,SkOpSegment ** topStart)674 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
675         SkOpSegment** topStart) {
676     int segmentCount = fSortedSegments.count();
677     SkASSERT(segmentCount > 0);
678     int sortedIndex = fFirstSorted;
679     fDone = true;  // may be cleared below
680     for ( ; sortedIndex < segmentCount; ++sortedIndex) {
681         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
682         if (testSegment->done()) {
683             if (sortedIndex == fFirstSorted) {
684                 ++fFirstSorted;
685             }
686             continue;
687         }
688         fDone = false;
689         SkPoint testXY = testSegment->activeLeftTop(NULL);
690         if (*topStart) {
691             if (testXY.fY < topLeft.fY) {
692                 continue;
693             }
694             if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) {
695                 continue;
696             }
697             if (bestXY->fY < testXY.fY) {
698                 continue;
699             }
700             if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
701                 continue;
702             }
703         }
704         *topStart = testSegment;
705         *bestXY = testXY;
706     }
707 }
708 
undoneSegment(int * start,int * end)709 SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
710     int segmentCount = fSegments.count();
711     for (int test = 0; test < segmentCount; ++test) {
712         SkOpSegment* testSegment = &fSegments[test];
713         if (testSegment->done()) {
714             continue;
715         }
716         testSegment->undoneSpan(start, end);
717         return testSegment;
718     }
719     return NULL;
720 }
721 
722 #if DEBUG_SHOW_WINDING
debugShowWindingValues(int totalSegments,int ofInterest)723 int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
724     int count = fSegments.count();
725     int sum = 0;
726     for (int index = 0; index < count; ++index) {
727         sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
728     }
729 //      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
730     return sum;
731 }
732 
debugShowWindingValues(const SkTArray<SkOpContour *,true> & contourList)733 void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
734 //     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
735 //    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
736     int ofInterest = 1 << 5 | 1 << 8;
737     int total = 0;
738     int index;
739     for (index = 0; index < contourList.count(); ++index) {
740         total += contourList[index]->segments().count();
741     }
742     int sum = 0;
743     for (index = 0; index < contourList.count(); ++index) {
744         sum += contourList[index]->debugShowWindingValues(total, ofInterest);
745     }
746 //       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
747 }
748 #endif
749 
setBounds()750 void SkOpContour::setBounds() {
751     int count = fSegments.count();
752     if (count == 0) {
753         SkDebugf("%s empty contour\n", __FUNCTION__);
754         SkASSERT(0);
755         // FIXME: delete empty contour?
756         return;
757     }
758     fBounds = fSegments.front().bounds();
759     for (int index = 1; index < count; ++index) {
760         fBounds.add(fSegments[index].bounds());
761     }
762 }
763