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 nullptr;
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 nullptr;
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 = nullptr;
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 = nullptr;
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 nullptr;
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(nullptr);
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(nullptr, &contour SkDEBUGPARAMS(nullptr));
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
addAlignIntersections(SkOpContourHead * contourList,SkChunkAlloc * allocator)397 static void addAlignIntersections(SkOpContourHead* contourList, SkChunkAlloc* allocator) {
398 SkOpContour* contour = contourList;
399 do {
400 contour->addAlignIntersections(contourList, allocator);
401 } while ((contour = contour->next()));
402 }
403
calcAngles(SkOpContourHead * contourList,SkChunkAlloc * allocator)404 static void calcAngles(SkOpContourHead* contourList, SkChunkAlloc* allocator) {
405 SkOpContour* contour = contourList;
406 do {
407 contour->calcAngles(allocator);
408 } while ((contour = contour->next()));
409 }
410
findCollapsed(SkOpContourHead * contourList)411 static void findCollapsed(SkOpContourHead* contourList) {
412 SkOpContour* contour = contourList;
413 do {
414 contour->findCollapsed();
415 } while ((contour = contour->next()));
416 }
417
missingCoincidence(SkOpContourHead * contourList,SkOpCoincidence * coincidence,SkChunkAlloc * allocator)418 static bool missingCoincidence(SkOpContourHead* contourList,
419 SkOpCoincidence* coincidence, SkChunkAlloc* allocator) {
420 SkOpContour* contour = contourList;
421 bool result = false;
422 do {
423 result |= contour->missingCoincidence(coincidence, allocator);
424 } while ((contour = contour->next()));
425 return result;
426 }
427
moveMultiples(SkOpContourHead * contourList)428 static bool moveMultiples(SkOpContourHead* contourList) {
429 SkOpContour* contour = contourList;
430 do {
431 if (!contour->moveMultiples()) {
432 return false;
433 }
434 } while ((contour = contour->next()));
435 return true;
436 }
437
moveNearby(SkOpContourHead * contourList)438 static void moveNearby(SkOpContourHead* contourList) {
439 SkOpContour* contour = contourList;
440 do {
441 contour->moveNearby();
442 } while ((contour = contour->next()));
443 }
444
sortAngles(SkOpContourHead * contourList)445 static void sortAngles(SkOpContourHead* contourList) {
446 SkOpContour* contour = contourList;
447 do {
448 contour->sortAngles();
449 } while ((contour = contour->next()));
450 }
451
HandleCoincidence(SkOpContourHead * contourList,SkOpCoincidence * coincidence,SkChunkAlloc * allocator)452 bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence,
453 SkChunkAlloc* allocator) {
454 SkOpGlobalState* globalState = contourList->globalState();
455 // combine t values when multiple intersections occur on some segments but not others
456 DEBUG_COINCIDENCE_HEALTH(contourList, "start");
457 if (!moveMultiples(contourList)) {
458 return false;
459 }
460 DEBUG_COINCIDENCE_HEALTH(contourList, "moveMultiples");
461 findCollapsed(contourList);
462 DEBUG_COINCIDENCE_HEALTH(contourList, "findCollapsed");
463 // move t values and points together to eliminate small/tiny gaps
464 moveNearby(contourList);
465 DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby");
466 align(contourList); // give all span members common values
467 DEBUG_COINCIDENCE_HEALTH(contourList, "align");
468 coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted
469 DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned");
470 #if DEBUG_VALIDATE
471 globalState->setPhase(SkOpGlobalState::kIntersecting);
472 #endif
473 // look for intersections on line segments formed by moving end points
474 addAlignIntersections(contourList, allocator);
475 DEBUG_COINCIDENCE_HEALTH(contourList, "addAlignIntersections");
476 if (coincidence->addMissing(allocator)) {
477 DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing");
478 moveNearby(contourList);
479 DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby2");
480 align(contourList); // give all span members common values
481 DEBUG_COINCIDENCE_HEALTH(contourList, "align2");
482 coincidence->fixAligned(); // aligning may have marked a coincidence pt-t deleted
483 DEBUG_COINCIDENCE_HEALTH(contourList, "fixAligned2");
484 }
485 #if DEBUG_VALIDATE
486 globalState->setPhase(SkOpGlobalState::kWalking);
487 #endif
488 // check to see if, loosely, coincident ranges may be expanded
489 if (coincidence->expand()) {
490 DEBUG_COINCIDENCE_HEALTH(contourList, "expand1");
491 if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) {
492 return false;
493 }
494 }
495 DEBUG_COINCIDENCE_HEALTH(contourList, "expand2");
496 // the expanded ranges may not align -- add the missing spans
497 if (!coincidence->mark()) { // mark spans of coincident segments as coincident
498 return false;
499 }
500 DEBUG_COINCIDENCE_HEALTH(contourList, "mark1");
501 // look for coincidence missed earlier
502 if (missingCoincidence(contourList, coincidence, allocator)) {
503 DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence1");
504 (void) coincidence->expand();
505 DEBUG_COINCIDENCE_HEALTH(contourList, "expand3");
506 if (!coincidence->addExpanded(allocator PATH_OPS_DEBUG_VALIDATE_PARAMS(globalState))) {
507 return false;
508 }
509 DEBUG_COINCIDENCE_HEALTH(contourList, "addExpanded2");
510 coincidence->mark();
511 }
512 DEBUG_COINCIDENCE_HEALTH(contourList, "missingCoincidence2");
513 SkOpCoincidence overlaps;
514 do {
515 SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
516 if (!pairs->apply()) { // adjust the winding value to account for coincident edges
517 return false;
518 }
519 DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->apply");
520 // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
521 // are different, construct a new pair to resolve their mutual span
522 pairs->findOverlaps(&overlaps, allocator);
523 DEBUG_COINCIDENCE_HEALTH(contourList, "pairs->findOverlaps");
524 } while (!overlaps.isEmpty());
525 calcAngles(contourList, allocator);
526 sortAngles(contourList);
527 if (globalState->angleCoincidence()) {
528 (void) missingCoincidence(contourList, coincidence, allocator);
529 if (!coincidence->apply()) {
530 return false;
531 }
532 }
533 #if DEBUG_ACTIVE_SPANS
534 coincidence->debugShowCoincidence();
535 DebugShowActiveSpans(contourList);
536 #endif
537 return true;
538 }
539