1 /*
2  * Copyright 2012 Google Inc.
3  *
4  * Use of this source code is governed by a BSD-style license that can be
5  * found in the LICENSE file.
6  */
7 #include "SkAddIntersections.h"
8 #include "SkOpCoincidence.h"
9 #include "SkOpEdgeBuilder.h"
10 #include "SkPathOpsCommon.h"
11 #include "SkPathWriter.h"
12 #include "SkTSort.h"
13 
AngleWinding(SkOpSpanBase * start,SkOpSpanBase * end,int * windingPtr,bool * sortablePtr)14 const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
15         bool* sortablePtr) {
16     // find first angle, initialize winding to computed fWindSum
17     SkOpSegment* segment = start->segment();
18     const SkOpAngle* angle = segment->spanToAngle(start, end);
19     if (!angle) {
20         *windingPtr = SK_MinS32;
21         return NULL;
22     }
23     bool computeWinding = false;
24     const SkOpAngle* firstAngle = angle;
25     bool loop = false;
26     bool unorderable = false;
27     int winding = SK_MinS32;
28     do {
29         angle = angle->next();
30         unorderable |= angle->unorderable();
31         if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
32             break;    // if we get here, there's no winding, loop is unorderable
33         }
34         loop |= angle == firstAngle;
35         segment = angle->segment();
36         winding = segment->windSum(angle);
37     } while (winding == SK_MinS32);
38     // if the angle loop contains an unorderable span, the angle order may be useless
39     // directly compute the winding in this case for each span
40     if (computeWinding) {
41         firstAngle = angle;
42         winding = SK_MinS32;
43         do {
44             SkOpSpanBase* startSpan = angle->start();
45             SkOpSpanBase* endSpan = angle->end();
46             SkOpSpan* lesser = startSpan->starter(endSpan);
47             int testWinding = lesser->windSum();
48             if (testWinding == SK_MinS32) {
49                 testWinding = lesser->computeWindSum();
50             }
51             if (testWinding != SK_MinS32) {
52                 segment = angle->segment();
53                 winding = testWinding;
54             }
55             angle = angle->next();
56         } while (angle != firstAngle);
57     }
58     *sortablePtr = !unorderable;
59     *windingPtr = winding;
60     return angle;
61 }
62 
FindUndone(SkOpContourHead * contourList,SkOpSpanBase ** startPtr,SkOpSpanBase ** endPtr)63 SkOpSegment* FindUndone(SkOpContourHead* contourList, SkOpSpanBase** startPtr,
64          SkOpSpanBase** endPtr) {
65     SkOpSegment* result;
66     SkOpContour* contour = contourList;
67     do {
68         result = contour->undoneSegment(startPtr, endPtr);
69         if (result) {
70             return result;
71         }
72     } while ((contour = contour->next()));
73     return NULL;
74 }
75 
FindChase(SkTDArray<SkOpSpanBase * > * chase,SkOpSpanBase ** startPtr,SkOpSpanBase ** endPtr)76 SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
77         SkOpSpanBase** endPtr) {
78     while (chase->count()) {
79         SkOpSpanBase* span;
80         chase->pop(&span);
81         SkOpSegment* segment = span->segment();
82         *startPtr = span->ptT()->next()->span();
83         bool done = true;
84         *endPtr = NULL;
85         if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
86             *startPtr = last->start();
87             *endPtr = last->end();
88     #if TRY_ROTATE
89             *chase->insert(0) = span;
90     #else
91             *chase->append() = span;
92     #endif
93             return last->segment();
94         }
95         if (done) {
96             continue;
97         }
98         // find first angle, initialize winding to computed wind sum
99         int winding;
100         bool sortable;
101         const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
102         if (winding == SK_MinS32) {
103             continue;
104         }
105         int sumWinding SK_INIT_TO_AVOID_WARNING;
106         if (sortable) {
107             segment = angle->segment();
108             sumWinding = segment->updateWindingReverse(angle);
109         }
110         SkOpSegment* first = NULL;
111         const SkOpAngle* firstAngle = angle;
112         while ((angle = angle->next()) != firstAngle) {
113             segment = angle->segment();
114             SkOpSpanBase* start = angle->start();
115             SkOpSpanBase* end = angle->end();
116             int maxWinding;
117             if (sortable) {
118                 segment->setUpWinding(start, end, &maxWinding, &sumWinding);
119             }
120             if (!segment->done(angle)) {
121                 if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
122                     first = segment;
123                     *startPtr = start;
124                     *endPtr = end;
125                 }
126                 // OPTIMIZATION: should this also add to the chase?
127                 if (sortable) {
128                     (void) segment->markAngle(maxWinding, sumWinding, angle);
129                 }
130             }
131         }
132         if (first) {
133        #if TRY_ROTATE
134             *chase->insert(0) = span;
135        #else
136             *chase->append() = span;
137        #endif
138             return first;
139         }
140     }
141     return NULL;
142 }
143 
144 #if DEBUG_ACTIVE_SPANS
DebugShowActiveSpans(SkOpContourHead * contourList)145 void DebugShowActiveSpans(SkOpContourHead* contourList) {
146     SkOpContour* contour = contourList;
147     do {
148         contour->debugShowActiveSpans();
149     } while ((contour = contour->next()));
150 }
151 #endif
152 
SortContourList(SkOpContourHead ** contourList,bool evenOdd,bool oppEvenOdd)153 bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
154     SkTDArray<SkOpContour* > list;
155     SkOpContour* contour = *contourList;
156     do {
157         if (contour->count()) {
158             contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
159             *list.append() = contour;
160         }
161     } while ((contour = contour->next()));
162     int count = list.count();
163     if (!count) {
164         return false;
165     }
166     if (count > 1) {
167         SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
168     }
169     contour = list[0];
170     SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
171     contour->globalState()->setContourHead(contourHead);
172     *contourList = contourHead;
173     for (int index = 1; index < count; ++index) {
174         SkOpContour* next = list[index];
175         contour->setNext(next);
176         contour = next;
177     }
178     contour->setNext(NULL);
179     return true;
180 }
181 
182 class DistanceLessThan {
183 public:
DistanceLessThan(double * distances)184     DistanceLessThan(double* distances) : fDistances(distances) { }
185     double* fDistances;
operator ()(const int one,const int two)186     bool operator()(const int one, const int two) {
187         return fDistances[one] < fDistances[two];
188     }
189 };
190 
191     /*
192         check start and end of each contour
193         if not the same, record them
194         match them up
195         connect closest
196         reassemble contour pieces into new path
197     */
Assemble(const SkPathWriter & path,SkPathWriter * simple)198 void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
199     SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
200     SkOpContourHead contour;
201     SkOpGlobalState globalState(NULL, &contour);
202 #if DEBUG_SHOW_TEST_NAME
203     SkDebugf("</div>\n");
204 #endif
205 #if DEBUG_PATH_CONSTRUCTION
206     SkDebugf("%s\n", __FUNCTION__);
207 #endif
208     SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState);
209     builder.finish(&allocator);
210     SkTDArray<const SkOpContour* > runs;  // indices of partial contours
211     const SkOpContour* eContour = builder.head();
212     do {
213         if (!eContour->count()) {
214             continue;
215         }
216         const SkPoint& eStart = eContour->start();
217         const SkPoint& eEnd = eContour->end();
218 #if DEBUG_ASSEMBLE
219         SkDebugf("%s contour", __FUNCTION__);
220         if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
221             SkDebugf("[%d]", runs.count());
222         } else {
223             SkDebugf("   ");
224         }
225         SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
226                 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
227 #endif
228         if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
229             eContour->toPath(simple);
230             continue;
231         }
232         *runs.append() = eContour;
233     } while ((eContour = eContour->next()));
234     int count = runs.count();
235     if (count == 0) {
236         return;
237     }
238     SkTDArray<int> sLink, eLink;
239     sLink.append(count);
240     eLink.append(count);
241     int rIndex, iIndex;
242     for (rIndex = 0; rIndex < count; ++rIndex) {
243         sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
244     }
245     const int ends = count * 2;  // all starts and ends
246     const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
247     SkTDArray<double> distances;
248     distances.append(entries);
249     for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
250         const SkOpContour* oContour = runs[rIndex >> 1];
251         const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start();
252         const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
253                 * ends - rIndex - 1;
254         for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
255             const SkOpContour* iContour = runs[iIndex >> 1];
256             const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start();
257             double dx = iPt.fX - oPt.fX;
258             double dy = iPt.fY - oPt.fY;
259             double dist = dx * dx + dy * dy;
260             distances[row + iIndex] = dist;  // oStart distance from iStart
261         }
262     }
263     SkTDArray<int> sortedDist;
264     sortedDist.append(entries);
265     for (rIndex = 0; rIndex < entries; ++rIndex) {
266         sortedDist[rIndex] = rIndex;
267     }
268     SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
269     int remaining = count;  // number of start/end pairs
270     for (rIndex = 0; rIndex < entries; ++rIndex) {
271         int pair = sortedDist[rIndex];
272         int row = pair / ends;
273         int col = pair - row * ends;
274         int thingOne = row < col ? row : ends - row - 2;
275         int ndxOne = thingOne >> 1;
276         bool endOne = thingOne & 1;
277         int* linkOne = endOne ? eLink.begin() : sLink.begin();
278         if (linkOne[ndxOne] != SK_MaxS32) {
279             continue;
280         }
281         int thingTwo = row < col ? col : ends - row + col - 1;
282         int ndxTwo = thingTwo >> 1;
283         bool endTwo = thingTwo & 1;
284         int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
285         if (linkTwo[ndxTwo] != SK_MaxS32) {
286             continue;
287         }
288         SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
289         bool flip = endOne == endTwo;
290         linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
291         linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
292         if (!--remaining) {
293             break;
294         }
295     }
296     SkASSERT(!remaining);
297 #if DEBUG_ASSEMBLE
298     for (rIndex = 0; rIndex < count; ++rIndex) {
299         int s = sLink[rIndex];
300         int e = eLink[rIndex];
301         SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
302                 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
303     }
304 #endif
305     rIndex = 0;
306     do {
307         bool forward = true;
308         bool first = true;
309         int sIndex = sLink[rIndex];
310         SkASSERT(sIndex != SK_MaxS32);
311         sLink[rIndex] = SK_MaxS32;
312         int eIndex;
313         if (sIndex < 0) {
314             eIndex = sLink[~sIndex];
315             sLink[~sIndex] = SK_MaxS32;
316         } else {
317             eIndex = eLink[sIndex];
318             eLink[sIndex] = SK_MaxS32;
319         }
320         SkASSERT(eIndex != SK_MaxS32);
321 #if DEBUG_ASSEMBLE
322         SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
323                     sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
324                     eIndex < 0 ? ~eIndex : eIndex);
325 #endif
326         do {
327             const SkOpContour* contour = runs[rIndex];
328             if (first) {
329                 first = false;
330                 const SkPoint* startPtr = &contour->start();
331                 simple->deferredMove(startPtr[0]);
332             }
333             if (forward) {
334                 contour->toPartialForward(simple);
335             } else {
336                 contour->toPartialBackward(simple);
337             }
338 #if DEBUG_ASSEMBLE
339             SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
340                 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
341                 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
342 #endif
343             if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
344                 simple->close();
345                 break;
346             }
347             if (forward) {
348                 eIndex = eLink[rIndex];
349                 SkASSERT(eIndex != SK_MaxS32);
350                 eLink[rIndex] = SK_MaxS32;
351                 if (eIndex >= 0) {
352                     SkASSERT(sLink[eIndex] == rIndex);
353                     sLink[eIndex] = SK_MaxS32;
354                 } else {
355                     SkASSERT(eLink[~eIndex] == ~rIndex);
356                     eLink[~eIndex] = SK_MaxS32;
357                 }
358             } else {
359                 eIndex = sLink[rIndex];
360                 SkASSERT(eIndex != SK_MaxS32);
361                 sLink[rIndex] = SK_MaxS32;
362                 if (eIndex >= 0) {
363                     SkASSERT(eLink[eIndex] == rIndex);
364                     eLink[eIndex] = SK_MaxS32;
365                 } else {
366                     SkASSERT(sLink[~eIndex] == ~rIndex);
367                     sLink[~eIndex] = SK_MaxS32;
368                 }
369             }
370             rIndex = eIndex;
371             if (rIndex < 0) {
372                 forward ^= 1;
373                 rIndex = ~rIndex;
374             }
375         } while (true);
376         for (rIndex = 0; rIndex < count; ++rIndex) {
377             if (sLink[rIndex] != SK_MaxS32) {
378                 break;
379             }
380         }
381     } while (rIndex < count);
382 #if DEBUG_ASSEMBLE
383     for (rIndex = 0; rIndex < count; ++rIndex) {
384        SkASSERT(sLink[rIndex] == SK_MaxS32);
385        SkASSERT(eLink[rIndex] == SK_MaxS32);
386     }
387 #endif
388 }
389 
align(SkOpContourHead * contourList)390 static void align(SkOpContourHead* contourList) {
391     SkOpContour* contour = contourList;
392     do {
393         contour->align();
394     } while ((contour = contour->next()));
395 }
396 
calcAngles(SkOpContourHead * contourList,SkChunkAlloc * allocator)397 static void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) {
398     SkOpContour* contour = contourList;
399     do {
400         contour->calcAngles(allocator);
401     } while ((contour = contour->next()));
402 }
403 
missingCoincidence(SkOpContourHead * contourList,SkOpCoincidence * coincidence,SkChunkAlloc * allocator)404 static void missingCoincidence(SkOpContourHead* contourList,
405         SkOpCoincidence* coincidence, SkChunkAlloc* allocator) {
406     SkOpContour* contour = contourList;
407     do {
408         contour->missingCoincidence(coincidence, allocator);
409     } while ((contour = contour->next()));
410 }
411 
moveMultiples(SkOpContourHead * contourList)412 static void moveMultiples(SkOpContourHead* contourList) {
413     SkOpContour* contour = contourList;
414     do {
415         contour->moveMultiples();
416     } while ((contour = contour->next()));
417 }
418 
moveNearby(SkOpContourHead * contourList)419 static void moveNearby(SkOpContourHead* contourList) {
420     SkOpContour* contour = contourList;
421     do {
422         contour->moveNearby();
423     } while ((contour = contour->next()));
424 }
425 
sortAngles(SkOpContourHead * contourList)426 static void sortAngles(SkOpContourHead* contourList) {
427     SkOpContour* contour = contourList;
428     do {
429         contour->sortAngles();
430     } while ((contour = contour->next()));
431 }
432 
HandleCoincidence(SkOpContourHead * contourList,SkOpCoincidence * coincidence,SkChunkAlloc * allocator)433 bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence,
434         SkChunkAlloc* allocator) {
435     SkOpGlobalState* globalState = contourList->globalState();
436     // combine t values when multiple intersections occur on some segments but not others
437     moveMultiples(contourList);
438     // move t values and points together to eliminate small/tiny gaps
439     moveNearby(contourList);
440     align(contourList);  // give all span members common values
441 #if DEBUG_VALIDATE
442     globalState->setPhase(SkOpGlobalState::kIntersecting);
443 #endif
444     coincidence->addMissing(allocator);
445 #if DEBUG_VALIDATE
446     globalState->setPhase(SkOpGlobalState::kWalking);
447 #endif
448     coincidence->expand();  // check to see if, loosely, coincident ranges may be expanded
449     coincidence->mark();  // mark spans of coincident segments as coincident
450     missingCoincidence(contourList, coincidence, allocator);  // look for coincidence missed earlier
451     if (!coincidence->apply()) {  // adjust the winding value to account for coincident edges
452         return false;
453     }
454     calcAngles(contourList, allocator);
455     sortAngles(contourList);
456     if (globalState->angleCoincidence()) {
457         missingCoincidence(contourList, coincidence, allocator);
458         if (!coincidence->apply()) {
459             return false;
460         }
461     }
462 #if DEBUG_ACTIVE_SPANS
463     coincidence->debugShowCoincidence();
464     DebugShowActiveSpans(contourList);
465 #endif
466     return true;
467 }
468