caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | */ |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 7 | #include "SkAddIntersections.h" |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 8 | #include "SkOpCoincidence.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 9 | #include "SkOpEdgeBuilder.h" |
| 10 | #include "SkPathOpsCommon.h" |
| 11 | #include "SkPathWriter.h" |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 12 | #include "SkTSort.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 13 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 14 | static int contourRangeCheckY(const SkTDArray<SkOpContour* >& contourList, |
| 15 | SkOpSegment** currentPtr, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, |
| 16 | double* bestHit, SkScalar* bestDx, bool* tryAgain, double* midPtr, bool opp) { |
| 17 | SkOpSpanBase* start = *startPtr; |
| 18 | SkOpSpanBase* end = *endPtr; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 19 | const double mid = *midPtr; |
| 20 | const SkOpSegment* current = *currentPtr; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 21 | double tAtMid = SkOpSegment::TAtMid(start, end, mid); |
caryclark@google.com | 4fdbb22 | 2013-07-23 15:27:41 +0000 | [diff] [blame] | 22 | SkPoint basePt = current->ptAtT(tAtMid); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 23 | int contourCount = contourList.count(); |
| 24 | SkScalar bestY = SK_ScalarMin; |
| 25 | SkOpSegment* bestSeg = NULL; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 26 | SkOpSpan* bestTSpan = NULL; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 27 | bool bestOpp; |
| 28 | bool hitSomething = false; |
| 29 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 30 | SkOpContour* contour = contourList[cTest]; |
| 31 | bool testOpp = contour->operand() ^ current->operand() ^ opp; |
| 32 | if (basePt.fY < contour->bounds().fTop) { |
| 33 | continue; |
| 34 | } |
| 35 | if (bestY > contour->bounds().fBottom) { |
| 36 | continue; |
| 37 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 38 | SkOpSegment* testSeg = contour->first(); |
| 39 | SkASSERT(testSeg); |
| 40 | do { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 41 | SkScalar testY = bestY; |
| 42 | double testHit; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 43 | bool vertical; |
| 44 | SkOpSpan* testTSpan = testSeg->crossedSpanY(basePt, tAtMid, testOpp, |
| 45 | testSeg == current, &testY, &testHit, &hitSomething, &vertical); |
| 46 | if (!testTSpan) { |
| 47 | if (vertical) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 48 | hitSomething = true; |
| 49 | bestSeg = NULL; |
| 50 | goto abortContours; // vertical encountered, return and try different point |
| 51 | } |
| 52 | continue; |
| 53 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 54 | if (testSeg == current && SkOpSegment::BetweenTs(start, testHit, end)) { |
| 55 | double baseT = start->t(); |
| 56 | double endT = end->t(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 57 | double newMid = (testHit - baseT) / (endT - baseT); |
| 58 | #if DEBUG_WINDING |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 59 | double midT = SkOpSegment::TAtMid(start, end, mid); |
| 60 | SkPoint midXY = current->ptAtT(midT); |
| 61 | double newMidT = SkOpSegment::TAtMid(start, end, newMid); |
| 62 | SkPoint newXY = current->ptAtT(newMidT); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 63 | SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)" |
| 64 | " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, |
| 65 | current->debugID(), mid, newMid, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 66 | baseT, start->pt().fX, start->pt().fY, |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 67 | baseT + mid * (endT - baseT), midXY.fX, midXY.fY, |
| 68 | baseT + newMid * (endT - baseT), newXY.fX, newXY.fY, |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 69 | endT, end->pt().fX, end->pt().fY); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 70 | #endif |
| 71 | *midPtr = newMid * 2; // calling loop with divide by 2 before continuing |
| 72 | return SK_MinS32; |
| 73 | } |
| 74 | bestSeg = testSeg; |
| 75 | *bestHit = testHit; |
| 76 | bestOpp = testOpp; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 77 | bestTSpan = testTSpan; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 78 | bestY = testY; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 79 | } while ((testSeg = testSeg->next())); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 80 | } |
| 81 | abortContours: |
| 82 | int result; |
| 83 | if (!bestSeg) { |
| 84 | result = hitSomething ? SK_MinS32 : 0; |
| 85 | } else { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 86 | if (bestTSpan->windSum() == SK_MinS32) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 87 | *currentPtr = bestSeg; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 88 | *startPtr = bestTSpan; |
| 89 | *endPtr = bestTSpan->next(); |
| 90 | SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 91 | *tryAgain = true; |
| 92 | return 0; |
| 93 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 94 | result = bestSeg->windingAtT(*bestHit, bestTSpan, bestOpp, bestDx); |
caryclark@google.com | f11a5af | 2013-04-10 18:55:11 +0000 | [diff] [blame] | 95 | SkASSERT(result == SK_MinS32 || *bestDx); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 96 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 97 | double baseT = (*startPtr)->t(); |
| 98 | double endT = (*endPtr)->t(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 99 | *bestHit = baseT + mid * (endT - baseT); |
| 100 | return result; |
| 101 | } |
| 102 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 103 | SkOpSegment* FindUndone(SkTDArray<SkOpContour* >& contourList, SkOpSpanBase** startPtr, |
| 104 | SkOpSpanBase** endPtr) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 105 | int contourCount = contourList.count(); |
| 106 | SkOpSegment* result; |
| 107 | for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 108 | SkOpContour* contour = contourList[cIndex]; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 109 | result = contour->undoneSegment(startPtr, endPtr); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 110 | if (result) { |
| 111 | return result; |
| 112 | } |
| 113 | } |
| 114 | return NULL; |
| 115 | } |
| 116 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 117 | SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, |
| 118 | SkOpSpanBase** endPtr) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 119 | while (chase->count()) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 120 | SkOpSpanBase* span; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 121 | chase->pop(&span); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 122 | SkOpSegment* segment = span->segment(); |
| 123 | *startPtr = span->ptT()->next()->span(); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 124 | bool sortable = true; |
| 125 | bool done = true; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 126 | *endPtr = NULL; |
| 127 | if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done, |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 128 | &sortable)) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 129 | if (last->unorderable()) { |
| 130 | continue; |
| 131 | } |
| 132 | *startPtr = last->start(); |
| 133 | *endPtr = last->end(); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 134 | #if TRY_ROTATE |
| 135 | *chase->insert(0) = span; |
| 136 | #else |
| 137 | *chase->append() = span; |
| 138 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 139 | return last->segment(); |
| 140 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 141 | if (done) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 142 | continue; |
| 143 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 144 | if (!sortable) { |
| 145 | continue; |
| 146 | } |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 147 | // find first angle, initialize winding to computed wind sum |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 148 | const SkOpAngle* angle = segment->spanToAngle(*startPtr, *endPtr); |
| 149 | if (!angle) { |
| 150 | continue; |
| 151 | } |
| 152 | const SkOpAngle* firstAngle = angle; |
| 153 | bool loop = false; |
| 154 | int winding = SK_MinS32; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 155 | do { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 156 | angle = angle->next(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 157 | if (angle == firstAngle && loop) { |
| 158 | break; // if we get here, there's no winding, loop is unorderable |
| 159 | } |
| 160 | loop |= angle == firstAngle; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 161 | segment = angle->segment(); |
| 162 | winding = segment->windSum(angle); |
| 163 | } while (winding == SK_MinS32); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 164 | if (winding == SK_MinS32) { |
| 165 | continue; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 166 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 167 | int sumWinding = segment->updateWindingReverse(angle); |
| 168 | SkOpSegment* first = NULL; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 169 | firstAngle = angle; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 170 | while ((angle = angle->next()) != firstAngle) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 171 | segment = angle->segment(); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 172 | SkOpSpanBase* start = angle->start(); |
| 173 | SkOpSpanBase* end = angle->end(); |
| 174 | int maxWinding; |
| 175 | segment->setUpWinding(start, end, &maxWinding, &sumWinding); |
| 176 | if (!segment->done(angle)) { |
| 177 | if (!first) { |
| 178 | first = segment; |
| 179 | *startPtr = start; |
| 180 | *endPtr = end; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 181 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 182 | // OPTIMIZATION: should this also add to the chase? |
| 183 | (void) segment->markAngle(maxWinding, sumWinding, angle); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 184 | } |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 185 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 186 | if (first) { |
| 187 | #if TRY_ROTATE |
| 188 | *chase->insert(0) = span; |
| 189 | #else |
| 190 | *chase->append() = span; |
| 191 | #endif |
| 192 | return first; |
| 193 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 194 | } |
| 195 | return NULL; |
| 196 | } |
| 197 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 198 | #if DEBUG_ACTIVE_SPANS |
| 199 | void DebugShowActiveSpans(SkTDArray<SkOpContour* >& contourList) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 200 | int index; |
| 201 | for (index = 0; index < contourList.count(); ++ index) { |
| 202 | contourList[index]->debugShowActiveSpans(); |
| 203 | } |
| 204 | } |
| 205 | #endif |
| 206 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 207 | static SkOpSegment* findTopSegment(const SkTDArray<SkOpContour* >& contourList, |
| 208 | bool firstPass, SkOpSpanBase** start, SkOpSpanBase** end, SkPoint* topLeft, |
| 209 | bool* unsortable, bool* done, SkChunkAlloc* allocator) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 210 | SkOpSegment* result; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 211 | const SkOpSegment* lastTopStart = NULL; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 212 | SkOpSpanBase* lastStart = NULL, * lastEnd = NULL; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 213 | do { |
| 214 | SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; |
| 215 | int contourCount = contourList.count(); |
| 216 | SkOpSegment* topStart = NULL; |
| 217 | *done = true; |
| 218 | for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 219 | SkOpContour* contour = contourList[cIndex]; |
| 220 | if (contour->done()) { |
| 221 | continue; |
| 222 | } |
| 223 | const SkPathOpsBounds& bounds = contour->bounds(); |
| 224 | if (bounds.fBottom < topLeft->fY) { |
| 225 | *done = false; |
| 226 | continue; |
| 227 | } |
| 228 | if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) { |
| 229 | *done = false; |
| 230 | continue; |
| 231 | } |
| 232 | contour->topSortableSegment(*topLeft, &bestXY, &topStart); |
| 233 | if (!contour->done()) { |
| 234 | *done = false; |
| 235 | } |
| 236 | } |
| 237 | if (!topStart) { |
| 238 | return NULL; |
| 239 | } |
| 240 | *topLeft = bestXY; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 241 | result = topStart->findTop(firstPass, start, end, unsortable, allocator); |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 242 | if (!result) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 243 | if (lastTopStart == topStart && lastStart == *start && lastEnd == *end) { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 244 | *done = true; |
| 245 | return NULL; |
| 246 | } |
| 247 | lastTopStart = topStart; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 248 | lastStart = *start; |
| 249 | lastEnd = *end; |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 250 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 251 | } while (!result); |
| 252 | return result; |
| 253 | } |
| 254 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 255 | static int rightAngleWinding(const SkTDArray<SkOpContour* >& contourList, |
| 256 | SkOpSegment** currentPtr, SkOpSpanBase** start, SkOpSpanBase** end, double* tHit, |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 257 | SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 258 | double test = 0.9; |
| 259 | int contourWinding; |
| 260 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 261 | contourWinding = contourRangeCheckY(contourList, currentPtr, start, end, |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 262 | tHit, hitDx, tryAgain, &test, opp); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 263 | if (contourWinding != SK_MinS32 || *tryAgain) { |
| 264 | return contourWinding; |
| 265 | } |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 266 | if (*currentPtr && (*currentPtr)->isVertical()) { |
| 267 | *onlyVertical = true; |
| 268 | return contourWinding; |
| 269 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 270 | test /= 2; |
| 271 | } while (!approximately_negative(test)); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 272 | SkASSERT(0); // FIXME: incomplete functionality |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 273 | return contourWinding; |
| 274 | } |
| 275 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 276 | static void skipVertical(const SkTDArray<SkOpContour* >& contourList, |
| 277 | SkOpSegment** current, SkOpSpanBase** start, SkOpSpanBase** end) { |
| 278 | if (!(*current)->isVertical(*start, *end)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 279 | return; |
| 280 | } |
| 281 | int contourCount = contourList.count(); |
| 282 | for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 283 | SkOpContour* contour = contourList[cIndex]; |
| 284 | if (contour->done()) { |
| 285 | continue; |
| 286 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 287 | SkOpSegment* nonVertical = contour->nonVerticalSegment(start, end); |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 288 | if (nonVertical) { |
| 289 | *current = nonVertical; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 290 | return; |
| 291 | } |
| 292 | } |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 293 | return; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 294 | } |
| 295 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 296 | struct SortableTop2 { // error if local in pre-C++11 |
| 297 | SkOpSpanBase* fStart; |
| 298 | SkOpSpanBase* fEnd; |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 299 | }; |
| 300 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 301 | SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour* >& contourList, bool firstPass, |
| 302 | SkOpAngle::IncludeType angleIncludeType, bool* firstContour, SkOpSpanBase** startPtr, |
| 303 | SkOpSpanBase** endPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical, |
| 304 | SkChunkAlloc* allocator) { |
| 305 | SkOpSegment* current = findTopSegment(contourList, firstPass, startPtr, endPtr, topLeft, |
| 306 | unsortable, done, allocator); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 307 | if (!current) { |
| 308 | return NULL; |
| 309 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 310 | SkOpSpanBase* start = *startPtr; |
| 311 | SkOpSpanBase* end = *endPtr; |
| 312 | SkASSERT(current == start->segment()); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 313 | if (*firstContour) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 314 | current->initWinding(start, end, angleIncludeType); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 315 | *firstContour = false; |
| 316 | return current; |
| 317 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 318 | SkOpSpan* minSpan = start->starter(end); |
| 319 | int sumWinding = minSpan->windSum(); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 320 | if (sumWinding == SK_MinS32) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 321 | SkOpSpanBase* iSpan = end; |
| 322 | SkOpSpanBase* oSpan = start; |
| 323 | do { |
| 324 | bool checkFrom = oSpan->t() < iSpan->t(); |
| 325 | if ((checkFrom ? iSpan->fromAngle() : iSpan->upCast()->toAngle()) == NULL) { |
| 326 | iSpan->addSimpleAngle(checkFrom, allocator); |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 327 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 328 | sumWinding = current->computeSum(oSpan, iSpan, angleIncludeType); |
| 329 | SkTSwap(iSpan, oSpan); |
| 330 | } while (sumWinding == SK_MinS32 && iSpan == start); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 331 | } |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 332 | if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 333 | return current; |
| 334 | } |
| 335 | int contourWinding; |
| 336 | int oppContourWinding = 0; |
| 337 | // the simple upward projection of the unresolved points hit unsortable angles |
| 338 | // shoot rays at right angles to the segment to find its winding, ignoring angle cases |
| 339 | bool tryAgain; |
| 340 | double tHit; |
| 341 | SkScalar hitDx = 0; |
| 342 | SkScalar hitOppDx = 0; |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 343 | // keep track of subsequent returns to detect infinite loops |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 344 | SkTDArray<SortableTop2> sortableTops; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 345 | do { |
| 346 | // if current is vertical, find another candidate which is not |
| 347 | // if only remaining candidates are vertical, then they can be marked done |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 348 | SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); |
| 349 | SkASSERT(current == (*startPtr)->segment()); |
| 350 | skipVertical(contourList, ¤t, startPtr, endPtr); |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 351 | SkASSERT(current); // FIXME: if null, all remaining are vertical |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 352 | SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); |
| 353 | SkASSERT(current == (*startPtr)->segment()); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 354 | tryAgain = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 355 | contourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 356 | &hitDx, &tryAgain, onlyVertical, false); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 357 | SkASSERT(current == (*startPtr)->segment()); |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 358 | if (tryAgain) { |
| 359 | bool giveUp = false; |
| 360 | int count = sortableTops.count(); |
| 361 | for (int index = 0; index < count; ++index) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 362 | const SortableTop2& prev = sortableTops[index]; |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 363 | if (giveUp) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 364 | prev.fStart->segment()->markDone(prev.fStart->starter(prev.fEnd)); |
| 365 | } else if (prev.fStart == *startPtr || prev.fEnd == *endPtr) { |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 366 | // remaining edges are non-vertical and cannot have their winding computed |
| 367 | // mark them as done and return, and hope that assembly can fill the holes |
| 368 | giveUp = true; |
| 369 | index = -1; |
| 370 | } |
| 371 | } |
| 372 | if (giveUp) { |
| 373 | *done = true; |
| 374 | return NULL; |
| 375 | } |
| 376 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 377 | SortableTop2* sortableTop = sortableTops.append(); |
| 378 | sortableTop->fStart = *startPtr; |
| 379 | sortableTop->fEnd = *endPtr; |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 380 | #if DEBUG_SORT |
| 381 | SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n", |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 382 | __FUNCTION__, current->debugID(), (*startPtr)->debugID(), (*endPtr)->debugID(), |
| 383 | tHit, hitDx, tryAgain, *onlyVertical); |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 384 | #endif |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 385 | if (*onlyVertical) { |
| 386 | return current; |
| 387 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 388 | if (tryAgain) { |
| 389 | continue; |
| 390 | } |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 391 | if (angleIncludeType < SkOpAngle::kBinarySingle) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 392 | break; |
| 393 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 394 | oppContourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 395 | &hitOppDx, &tryAgain, NULL, true); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 396 | SkASSERT(current == (*startPtr)->segment()); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 397 | } while (tryAgain); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 398 | bool success = current->initWinding(*startPtr, *endPtr, tHit, contourWinding, hitDx, |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 399 | oppContourWinding, hitOppDx); |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 400 | if (current->done()) { |
| 401 | return NULL; |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 402 | } else if (!success) { // check if the span has a valid winding |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 403 | SkOpSpan* minSpan = (*startPtr)->t() < (*endPtr)->t() ? (*startPtr)->upCast() |
| 404 | : (*endPtr)->upCast(); |
| 405 | if (minSpan->windSum() == SK_MinS32) { |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 406 | return NULL; |
| 407 | } |
commit-bot@chromium.org | 8cb1daa | 2014-04-25 12:59:11 +0000 | [diff] [blame] | 408 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 409 | return current; |
| 410 | } |
| 411 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 412 | void MakeContourList(SkOpContour* contour, SkTDArray<SkOpContour* >& list, |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 413 | bool evenOdd, bool oppEvenOdd) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 414 | do { |
| 415 | if (contour->count()) { |
| 416 | contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); |
| 417 | *list.append() = contour; |
| 418 | } |
| 419 | } while ((contour = contour->next())); |
| 420 | if (list.count() < 2) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 421 | return; |
| 422 | } |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 423 | SkTQSort<SkOpContour>(list.begin(), list.end() - 1); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 424 | } |
| 425 | |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 426 | class DistanceLessThan { |
| 427 | public: |
| 428 | DistanceLessThan(double* distances) : fDistances(distances) { } |
| 429 | double* fDistances; |
| 430 | bool operator()(const int one, const int two) { |
| 431 | return fDistances[one] < fDistances[two]; |
| 432 | } |
| 433 | }; |
| 434 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 435 | /* |
| 436 | check start and end of each contour |
| 437 | if not the same, record them |
| 438 | match them up |
| 439 | connect closest |
| 440 | reassemble contour pieces into new path |
| 441 | */ |
| 442 | void Assemble(const SkPathWriter& path, SkPathWriter* simple) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 443 | SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune |
| 444 | SkOpContour contour; |
| 445 | SkOpGlobalState globalState(NULL PATH_OPS_DEBUG_PARAMS(&contour)); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 446 | #if DEBUG_PATH_CONSTRUCTION |
| 447 | SkDebugf("%s\n", __FUNCTION__); |
| 448 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 449 | SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); |
| 450 | builder.finish(&allocator); |
| 451 | SkTDArray<const SkOpContour* > runs; // indices of partial contours |
| 452 | const SkOpContour* eContour = builder.head(); |
| 453 | do { |
| 454 | if (!eContour->count()) { |
| 455 | continue; |
| 456 | } |
| 457 | const SkPoint& eStart = eContour->start(); |
| 458 | const SkPoint& eEnd = eContour->end(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 459 | #if DEBUG_ASSEMBLE |
| 460 | SkDebugf("%s contour", __FUNCTION__); |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 461 | if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 462 | SkDebugf("[%d]", runs.count()); |
| 463 | } else { |
| 464 | SkDebugf(" "); |
| 465 | } |
| 466 | SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", |
| 467 | eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); |
| 468 | #endif |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 469 | if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 470 | eContour->toPath(simple); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 471 | continue; |
| 472 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 473 | *runs.append() = eContour; |
| 474 | } while ((eContour = eContour->next())); |
| 475 | int count = runs.count(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 476 | if (count == 0) { |
| 477 | return; |
| 478 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 479 | SkTDArray<int> sLink, eLink; |
| 480 | sLink.append(count); |
| 481 | eLink.append(count); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 482 | int rIndex, iIndex; |
| 483 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 484 | sLink[rIndex] = eLink[rIndex] = SK_MaxS32; |
| 485 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 486 | const int ends = count * 2; // all starts and ends |
| 487 | const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 488 | SkTDArray<double> distances; |
| 489 | distances.append(entries); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 490 | for (rIndex = 0; rIndex < ends - 1; ++rIndex) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 491 | const SkOpContour* oContour = runs[rIndex >> 1]; |
| 492 | const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 493 | const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) |
| 494 | * ends - rIndex - 1; |
| 495 | for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 496 | const SkOpContour* iContour = runs[iIndex >> 1]; |
| 497 | const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 498 | double dx = iPt.fX - oPt.fX; |
| 499 | double dy = iPt.fY - oPt.fY; |
| 500 | double dist = dx * dx + dy * dy; |
| 501 | distances[row + iIndex] = dist; // oStart distance from iStart |
| 502 | } |
| 503 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 504 | SkTDArray<int> sortedDist; |
| 505 | sortedDist.append(entries); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 506 | for (rIndex = 0; rIndex < entries; ++rIndex) { |
| 507 | sortedDist[rIndex] = rIndex; |
| 508 | } |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 509 | SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin())); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 510 | int remaining = count; // number of start/end pairs |
| 511 | for (rIndex = 0; rIndex < entries; ++rIndex) { |
| 512 | int pair = sortedDist[rIndex]; |
| 513 | int row = pair / ends; |
| 514 | int col = pair - row * ends; |
| 515 | int thingOne = row < col ? row : ends - row - 2; |
| 516 | int ndxOne = thingOne >> 1; |
| 517 | bool endOne = thingOne & 1; |
| 518 | int* linkOne = endOne ? eLink.begin() : sLink.begin(); |
| 519 | if (linkOne[ndxOne] != SK_MaxS32) { |
| 520 | continue; |
| 521 | } |
| 522 | int thingTwo = row < col ? col : ends - row + col - 1; |
| 523 | int ndxTwo = thingTwo >> 1; |
| 524 | bool endTwo = thingTwo & 1; |
| 525 | int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); |
| 526 | if (linkTwo[ndxTwo] != SK_MaxS32) { |
| 527 | continue; |
| 528 | } |
| 529 | SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); |
| 530 | bool flip = endOne == endTwo; |
| 531 | linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; |
| 532 | linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; |
| 533 | if (!--remaining) { |
| 534 | break; |
| 535 | } |
| 536 | } |
| 537 | SkASSERT(!remaining); |
| 538 | #if DEBUG_ASSEMBLE |
| 539 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 540 | int s = sLink[rIndex]; |
| 541 | int e = eLink[rIndex]; |
| 542 | SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', |
| 543 | s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); |
| 544 | } |
| 545 | #endif |
| 546 | rIndex = 0; |
| 547 | do { |
| 548 | bool forward = true; |
| 549 | bool first = true; |
| 550 | int sIndex = sLink[rIndex]; |
| 551 | SkASSERT(sIndex != SK_MaxS32); |
| 552 | sLink[rIndex] = SK_MaxS32; |
| 553 | int eIndex; |
| 554 | if (sIndex < 0) { |
| 555 | eIndex = sLink[~sIndex]; |
| 556 | sLink[~sIndex] = SK_MaxS32; |
| 557 | } else { |
| 558 | eIndex = eLink[sIndex]; |
| 559 | eLink[sIndex] = SK_MaxS32; |
| 560 | } |
| 561 | SkASSERT(eIndex != SK_MaxS32); |
| 562 | #if DEBUG_ASSEMBLE |
| 563 | SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', |
| 564 | sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', |
| 565 | eIndex < 0 ? ~eIndex : eIndex); |
| 566 | #endif |
| 567 | do { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 568 | const SkOpContour* contour = runs[rIndex]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 569 | if (first) { |
| 570 | first = false; |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 571 | const SkPoint* startPtr = &contour->start(); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 572 | simple->deferredMove(startPtr[0]); |
| 573 | } |
| 574 | if (forward) { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 575 | contour->toPartialForward(simple); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 576 | } else { |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 577 | contour->toPartialBackward(simple); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 578 | } |
| 579 | #if DEBUG_ASSEMBLE |
| 580 | SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, |
| 581 | eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, |
| 582 | sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); |
| 583 | #endif |
| 584 | if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { |
| 585 | simple->close(); |
| 586 | break; |
| 587 | } |
| 588 | if (forward) { |
| 589 | eIndex = eLink[rIndex]; |
| 590 | SkASSERT(eIndex != SK_MaxS32); |
| 591 | eLink[rIndex] = SK_MaxS32; |
| 592 | if (eIndex >= 0) { |
| 593 | SkASSERT(sLink[eIndex] == rIndex); |
| 594 | sLink[eIndex] = SK_MaxS32; |
| 595 | } else { |
| 596 | SkASSERT(eLink[~eIndex] == ~rIndex); |
| 597 | eLink[~eIndex] = SK_MaxS32; |
| 598 | } |
| 599 | } else { |
| 600 | eIndex = sLink[rIndex]; |
| 601 | SkASSERT(eIndex != SK_MaxS32); |
| 602 | sLink[rIndex] = SK_MaxS32; |
| 603 | if (eIndex >= 0) { |
| 604 | SkASSERT(eLink[eIndex] == rIndex); |
| 605 | eLink[eIndex] = SK_MaxS32; |
| 606 | } else { |
| 607 | SkASSERT(sLink[~eIndex] == ~rIndex); |
| 608 | sLink[~eIndex] = SK_MaxS32; |
| 609 | } |
| 610 | } |
| 611 | rIndex = eIndex; |
| 612 | if (rIndex < 0) { |
| 613 | forward ^= 1; |
| 614 | rIndex = ~rIndex; |
| 615 | } |
| 616 | } while (true); |
| 617 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 618 | if (sLink[rIndex] != SK_MaxS32) { |
| 619 | break; |
| 620 | } |
| 621 | } |
| 622 | } while (rIndex < count); |
| 623 | #if DEBUG_ASSEMBLE |
| 624 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 625 | SkASSERT(sLink[rIndex] == SK_MaxS32); |
| 626 | SkASSERT(eLink[rIndex] == SK_MaxS32); |
| 627 | } |
| 628 | #endif |
| 629 | } |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 630 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 631 | static void align(SkTDArray<SkOpContour* >* contourList) { |
| 632 | int contourCount = (*contourList).count(); |
| 633 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 634 | SkOpContour* contour = (*contourList)[cTest]; |
| 635 | contour->align(); |
| 636 | } |
| 637 | } |
| 638 | |
| 639 | static void calcAngles(SkTDArray<SkOpContour* >* contourList, SkChunkAlloc* allocator) { |
| 640 | int contourCount = (*contourList).count(); |
| 641 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 642 | SkOpContour* contour = (*contourList)[cTest]; |
| 643 | contour->calcAngles(allocator); |
| 644 | } |
| 645 | } |
| 646 | |
| 647 | static void missingCoincidence(SkTDArray<SkOpContour* >* contourList, |
| 648 | SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { |
| 649 | int contourCount = (*contourList).count(); |
| 650 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 651 | SkOpContour* contour = (*contourList)[cTest]; |
| 652 | contour->missingCoincidence(coincidence, allocator); |
| 653 | } |
| 654 | } |
| 655 | |
| 656 | static bool moveNearby(SkTDArray<SkOpContour* >* contourList) { |
| 657 | int contourCount = (*contourList).count(); |
| 658 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 659 | SkOpContour* contour = (*contourList)[cTest]; |
| 660 | if (!contour->moveNearby()) { |
| 661 | return false; |
| 662 | } |
| 663 | } |
| 664 | return true; |
| 665 | } |
| 666 | |
| 667 | static void sortAngles(SkTDArray<SkOpContour* >* contourList) { |
| 668 | int contourCount = (*contourList).count(); |
| 669 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 670 | SkOpContour* contour = (*contourList)[cTest]; |
| 671 | contour->sortAngles(); |
| 672 | } |
| 673 | } |
| 674 | |
| 675 | static void sortSegments(SkTDArray<SkOpContour* >* contourList) { |
| 676 | int contourCount = (*contourList).count(); |
| 677 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 678 | SkOpContour* contour = (*contourList)[cTest]; |
| 679 | contour->sortSegments(); |
| 680 | } |
| 681 | } |
| 682 | |
| 683 | bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence, |
| 684 | SkChunkAlloc* allocator, SkOpGlobalState* globalState) { |
| 685 | // move t values and points together to eliminate small/tiny gaps |
| 686 | if (!moveNearby(contourList)) { |
caryclark | 630240d | 2014-09-19 06:33:31 -0700 | [diff] [blame] | 687 | return false; |
| 688 | } |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 689 | align(contourList); // give all span members common values |
| 690 | #if DEBUG_VALIDATE |
| 691 | globalState->setPhase(SkOpGlobalState::kIntersecting); |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 692 | #endif |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 693 | coincidence->addMissing(allocator); |
| 694 | #if DEBUG_VALIDATE |
| 695 | globalState->setPhase(SkOpGlobalState::kWalking); |
| 696 | #endif |
| 697 | coincidence->expand(); // check to see if, loosely, coincident ranges may be expanded |
| 698 | coincidence->mark(); // mark spans of coincident segments as coincident |
| 699 | missingCoincidence(contourList, coincidence, allocator); // look for coincidence missed earlier |
| 700 | if (!coincidence->apply()) { // adjust the winding value to account for coincident edges |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 701 | return false; |
| 702 | } |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 703 | sortSegments(contourList); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 704 | calcAngles(contourList, allocator); |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame] | 705 | sortAngles(contourList); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame^] | 706 | if (globalState->angleCoincidence()) { |
| 707 | missingCoincidence(contourList, coincidence, allocator); |
| 708 | if (!coincidence->apply()) { |
| 709 | return false; |
| 710 | } |
| 711 | } |
| 712 | #if DEBUG_ACTIVE_SPANS |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 713 | DebugShowActiveSpans(*contourList); |
| 714 | #endif |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 715 | return true; |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 716 | } |