caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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" |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 10 | #include "SkTSort.h" |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 11 | |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 12 | bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 13 | const SkIntersections& ts, bool swap) { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 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 | } |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 23 | SkCoincidence& coincidence = fCoincidences.push_back(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 24 | coincidence.fOther = other; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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]; |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 31 | coincidence.fPts[0] = pt0; |
| 32 | coincidence.fPts[1] = pt1; |
| 33 | return true; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 34 | } |
| 35 | |
| 36 | SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) { |
| 37 | int segmentCount = fSortedSegments.count(); |
| 38 | SkASSERT(segmentCount > 0); |
| 39 | for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) { |
| 40 | SkOpSegment* testSegment = fSortedSegments[sortedIndex]; |
| 41 | if (testSegment->done()) { |
| 42 | continue; |
| 43 | } |
| 44 | *start = *end = 0; |
| 45 | while (testSegment->nextCandidate(start, end)) { |
| 46 | if (!testSegment->isVertical(*start, *end)) { |
| 47 | return testSegment; |
| 48 | } |
| 49 | } |
| 50 | } |
| 51 | return NULL; |
| 52 | } |
| 53 | |
| 54 | // first pass, add missing T values |
| 55 | // second pass, determine winding values of overlaps |
| 56 | void SkOpContour::addCoincidentPoints() { |
| 57 | int count = fCoincidences.count(); |
| 58 | for (int index = 0; index < count; ++index) { |
| 59 | SkCoincidence& coincidence = fCoincidences[index]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 60 | int thisIndex = coincidence.fSegments[0]; |
| 61 | SkOpSegment& thisOne = fSegments[thisIndex]; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 62 | SkOpContour* otherContour = coincidence.fOther; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 63 | int otherIndex = coincidence.fSegments[1]; |
| 64 | SkOpSegment& other = otherContour->fSegments[otherIndex]; |
| 65 | if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { |
| 66 | // OPTIMIZATION: remove from array |
| 67 | continue; |
| 68 | } |
| 69 | #if DEBUG_CONCIDENT |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 70 | thisOne.debugShowTs("-"); |
| 71 | other.debugShowTs("o"); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 72 | #endif |
| 73 | double startT = coincidence.fTs[0][0]; |
| 74 | double endT = coincidence.fTs[0][1]; |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 75 | bool startSwapped, oStartSwapped, cancelers; |
| 76 | if ((cancelers = startSwapped = startT > endT)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 77 | SkTSwap(startT, endT); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 78 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 79 | if (startT == endT) { // if one is very large the smaller may have collapsed to nothing |
| 80 | if (endT <= 1 - FLT_EPSILON) { |
| 81 | endT += FLT_EPSILON; |
| 82 | SkASSERT(endT <= 1); |
| 83 | } else { |
| 84 | startT -= FLT_EPSILON; |
| 85 | SkASSERT(startT >= 0); |
| 86 | } |
| 87 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 88 | SkASSERT(!approximately_negative(endT - startT)); |
| 89 | double oStartT = coincidence.fTs[1][0]; |
| 90 | double oEndT = coincidence.fTs[1][1]; |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 91 | if ((oStartSwapped = oStartT > oEndT)) { |
| 92 | SkTSwap(oStartT, oEndT); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 93 | cancelers ^= true; |
| 94 | } |
| 95 | SkASSERT(!approximately_negative(oEndT - oStartT)); |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 96 | if (cancelers) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 97 | // make sure startT and endT have t entries |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 98 | const SkPoint& startPt = coincidence.fPts[startSwapped]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 99 | if (startT > 0 || oEndT < 1 |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 100 | || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) { |
| 101 | thisOne.addTPair(startT, &other, oEndT, true, startPt); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 102 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 103 | const SkPoint& oStartPt = coincidence.fPts[oStartSwapped]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 104 | if (oStartT > 0 || endT < 1 |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 105 | || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) { |
| 106 | other.addTPair(oStartT, &thisOne, endT, true, oStartPt); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 107 | } |
| 108 | } else { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 109 | const SkPoint& startPt = coincidence.fPts[startSwapped]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 110 | if (startT > 0 || oStartT > 0 |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 111 | || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) { |
| 112 | thisOne.addTPair(startT, &other, oStartT, true, startPt); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 113 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 114 | const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 115 | if (endT < 1 || oEndT < 1 |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 116 | || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) { |
| 117 | other.addTPair(oEndT, &thisOne, endT, true, oEndPt); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 118 | } |
| 119 | } |
| 120 | #if DEBUG_CONCIDENT |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 121 | thisOne.debugShowTs("+"); |
| 122 | other.debugShowTs("o"); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 123 | #endif |
| 124 | } |
| 125 | } |
| 126 | |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 127 | bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 128 | const SkIntersections& ts, int ptIndex, bool swap) { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 129 | SkPoint pt0 = ts.pt(ptIndex).asSkPoint(); |
| 130 | SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint(); |
| 131 | if (SkDPoint::ApproximatelyEqual(pt0, pt1)) { |
| 132 | // FIXME: one could imagine a case where it would be incorrect to ignore this |
| 133 | // suppose two self-intersecting cubics overlap to form a partial coincidence -- |
| 134 | // although it isn't clear why the regular coincidence could wouldn't pick this up |
| 135 | // this is exceptional enough to ignore for now |
| 136 | return false; |
| 137 | } |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 138 | SkCoincidence& coincidence = fPartialCoincidences.push_back(); |
| 139 | coincidence.fOther = other; |
| 140 | coincidence.fSegments[0] = index; |
| 141 | coincidence.fSegments[1] = otherIndex; |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 142 | coincidence.fTs[swap][0] = ts[0][ptIndex]; |
| 143 | coincidence.fTs[swap][1] = ts[0][ptIndex + 1]; |
| 144 | coincidence.fTs[!swap][0] = ts[1][ptIndex]; |
| 145 | coincidence.fTs[!swap][1] = ts[1][ptIndex + 1]; |
| 146 | coincidence.fPts[0] = pt0; |
| 147 | coincidence.fPts[1] = pt1; |
| 148 | return true; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 149 | } |
| 150 | |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame^] | 151 | bool SkOpContour::calcAngles() { |
| 152 | int segmentCount = fSegments.count(); |
| 153 | for (int test = 0; test < segmentCount; ++test) { |
| 154 | if (!fSegments[test].calcAngles()) { |
| 155 | return false; |
| 156 | } |
| 157 | } |
| 158 | return true; |
| 159 | } |
| 160 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 161 | void SkOpContour::calcCoincidentWinding() { |
| 162 | int count = fCoincidences.count(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 163 | #if DEBUG_CONCIDENT |
| 164 | if (count > 0) { |
| 165 | SkDebugf("%s count=%d\n", __FUNCTION__, count); |
| 166 | } |
| 167 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 168 | for (int index = 0; index < count; ++index) { |
| 169 | SkCoincidence& coincidence = fCoincidences[index]; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 170 | calcCommonCoincidentWinding(coincidence); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 171 | } |
| 172 | } |
| 173 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 174 | void SkOpContour::calcPartialCoincidentWinding() { |
| 175 | int count = fPartialCoincidences.count(); |
| 176 | #if DEBUG_CONCIDENT |
| 177 | if (count > 0) { |
| 178 | SkDebugf("%s count=%d\n", __FUNCTION__, count); |
| 179 | } |
| 180 | #endif |
| 181 | for (int index = 0; index < count; ++index) { |
| 182 | SkCoincidence& coincidence = fPartialCoincidences[index]; |
| 183 | calcCommonCoincidentWinding(coincidence); |
| 184 | } |
| 185 | } |
| 186 | |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 187 | void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) { |
| 188 | int count = coincidences.count(); |
| 189 | #if DEBUG_CONCIDENT |
| 190 | if (count > 0) { |
| 191 | SkDebugf("%s count=%d\n", __FUNCTION__, count); |
| 192 | } |
| 193 | #endif |
| 194 | // look for a lineup where the partial implies another adjoining coincidence |
| 195 | for (int index = 0; index < count; ++index) { |
| 196 | const SkCoincidence& coincidence = coincidences[index]; |
| 197 | int thisIndex = coincidence.fSegments[0]; |
| 198 | SkOpSegment& thisOne = fSegments[thisIndex]; |
| 199 | SkOpContour* otherContour = coincidence.fOther; |
| 200 | int otherIndex = coincidence.fSegments[1]; |
| 201 | SkOpSegment& other = otherContour->fSegments[otherIndex]; |
| 202 | double startT = coincidence.fTs[0][0]; |
| 203 | double endT = coincidence.fTs[0][1]; |
| 204 | if (startT == endT) { // this can happen in very large compares |
| 205 | continue; |
| 206 | } |
| 207 | double oStartT = coincidence.fTs[1][0]; |
| 208 | double oEndT = coincidence.fTs[1][1]; |
| 209 | if (oStartT == oEndT) { |
| 210 | continue; |
| 211 | } |
| 212 | bool swapStart = startT > endT; |
| 213 | bool swapOther = oStartT > oEndT; |
| 214 | if (swapStart) { |
| 215 | SkTSwap<double>(startT, endT); |
| 216 | SkTSwap<double>(oStartT, oEndT); |
| 217 | } |
| 218 | bool cancel = swapOther != swapStart; |
| 219 | int step = swapStart ? -1 : 1; |
| 220 | int oStep = swapOther ? -1 : 1; |
| 221 | double oMatchStart = cancel ? oEndT : oStartT; |
| 222 | if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) { |
| 223 | bool added = false; |
| 224 | if (oMatchStart != 0) { |
commit-bot@chromium.org | 866f4e3 | 2013-11-21 17:04:29 +0000 | [diff] [blame] | 225 | added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel); |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 226 | } |
commit-bot@chromium.org | 866f4e3 | 2013-11-21 17:04:29 +0000 | [diff] [blame] | 227 | if (!cancel && startT != 0 && !added) { |
| 228 | (void) other.joinCoincidence(&thisOne, startT, step, cancel); |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 229 | } |
| 230 | } |
| 231 | double oMatchEnd = cancel ? oStartT : oEndT; |
| 232 | if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) { |
| 233 | bool added = false; |
commit-bot@chromium.org | 866f4e3 | 2013-11-21 17:04:29 +0000 | [diff] [blame] | 234 | if (cancel && endT != 1 && !added) { |
| 235 | (void) other.joinCoincidence(&thisOne, endT, -step, cancel); |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 236 | } |
| 237 | } |
| 238 | } |
| 239 | } |
| 240 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 241 | void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { |
| 242 | int thisIndex = coincidence.fSegments[0]; |
| 243 | SkOpSegment& thisOne = fSegments[thisIndex]; |
| 244 | if (thisOne.done()) { |
| 245 | return; |
| 246 | } |
| 247 | SkOpContour* otherContour = coincidence.fOther; |
| 248 | int otherIndex = coincidence.fSegments[1]; |
| 249 | SkOpSegment& other = otherContour->fSegments[otherIndex]; |
| 250 | if (other.done()) { |
| 251 | return; |
| 252 | } |
| 253 | double startT = coincidence.fTs[0][0]; |
| 254 | double endT = coincidence.fTs[0][1]; |
| 255 | const SkPoint* startPt = &coincidence.fPts[0]; |
| 256 | const SkPoint* endPt = &coincidence.fPts[1]; |
| 257 | bool cancelers; |
| 258 | if ((cancelers = startT > endT)) { |
| 259 | SkTSwap<double>(startT, endT); |
| 260 | SkTSwap<const SkPoint*>(startPt, endPt); |
| 261 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 262 | if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing |
| 263 | if (endT <= 1 - FLT_EPSILON) { |
| 264 | endT += FLT_EPSILON; |
| 265 | SkASSERT(endT <= 1); |
| 266 | } else { |
| 267 | startT -= FLT_EPSILON; |
| 268 | SkASSERT(startT >= 0); |
| 269 | } |
| 270 | } |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 271 | SkASSERT(!approximately_negative(endT - startT)); |
| 272 | double oStartT = coincidence.fTs[1][0]; |
| 273 | double oEndT = coincidence.fTs[1][1]; |
| 274 | if (oStartT > oEndT) { |
| 275 | SkTSwap<double>(oStartT, oEndT); |
| 276 | cancelers ^= true; |
| 277 | } |
| 278 | SkASSERT(!approximately_negative(oEndT - oStartT)); |
| 279 | if (cancelers) { |
| 280 | thisOne.addTCancel(*startPt, *endPt, &other); |
| 281 | } else { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 282 | thisOne.addTCoincident(*startPt, *endPt, endT, &other); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 283 | } |
| 284 | #if DEBUG_CONCIDENT |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 285 | thisOne.debugShowTs("p"); |
| 286 | other.debugShowTs("o"); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 287 | #endif |
| 288 | } |
| 289 | |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame^] | 290 | void SkOpContour::sortAngles() { |
| 291 | int segmentCount = fSegments.count(); |
| 292 | for (int test = 0; test < segmentCount; ++test) { |
| 293 | fSegments[test].sortAngles(); |
| 294 | } |
| 295 | } |
| 296 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 297 | void SkOpContour::sortSegments() { |
| 298 | int segmentCount = fSegments.count(); |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 299 | fSortedSegments.push_back_n(segmentCount); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 300 | for (int test = 0; test < segmentCount; ++test) { |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 301 | fSortedSegments[test] = &fSegments[test]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 302 | } |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 303 | SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 304 | fFirstSorted = 0; |
| 305 | } |
| 306 | |
| 307 | void SkOpContour::toPath(SkPathWriter* path) const { |
| 308 | int segmentCount = fSegments.count(); |
| 309 | const SkPoint& pt = fSegments.front().pts()[0]; |
| 310 | path->deferredMove(pt); |
| 311 | for (int test = 0; test < segmentCount; ++test) { |
| 312 | fSegments[test].addCurveTo(0, 1, path, true); |
| 313 | } |
| 314 | path->close(); |
| 315 | } |
| 316 | |
| 317 | void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, |
| 318 | SkOpSegment** topStart) { |
| 319 | int segmentCount = fSortedSegments.count(); |
| 320 | SkASSERT(segmentCount > 0); |
| 321 | int sortedIndex = fFirstSorted; |
| 322 | fDone = true; // may be cleared below |
| 323 | for ( ; sortedIndex < segmentCount; ++sortedIndex) { |
| 324 | SkOpSegment* testSegment = fSortedSegments[sortedIndex]; |
| 325 | if (testSegment->done()) { |
| 326 | if (sortedIndex == fFirstSorted) { |
| 327 | ++fFirstSorted; |
| 328 | } |
| 329 | continue; |
| 330 | } |
| 331 | fDone = false; |
| 332 | SkPoint testXY = testSegment->activeLeftTop(true, NULL); |
| 333 | if (*topStart) { |
| 334 | if (testXY.fY < topLeft.fY) { |
| 335 | continue; |
| 336 | } |
| 337 | if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { |
| 338 | continue; |
| 339 | } |
| 340 | if (bestXY->fY < testXY.fY) { |
| 341 | continue; |
| 342 | } |
| 343 | if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) { |
| 344 | continue; |
| 345 | } |
| 346 | } |
| 347 | *topStart = testSegment; |
| 348 | *bestXY = testXY; |
| 349 | } |
| 350 | } |
| 351 | |
| 352 | SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) { |
| 353 | int segmentCount = fSegments.count(); |
| 354 | for (int test = 0; test < segmentCount; ++test) { |
| 355 | SkOpSegment* testSegment = &fSegments[test]; |
| 356 | if (testSegment->done()) { |
| 357 | continue; |
| 358 | } |
| 359 | testSegment->undoneSpan(start, end); |
| 360 | return testSegment; |
| 361 | } |
| 362 | return NULL; |
| 363 | } |
| 364 | |
| 365 | #if DEBUG_SHOW_WINDING |
| 366 | int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) { |
| 367 | int count = fSegments.count(); |
| 368 | int sum = 0; |
| 369 | for (int index = 0; index < count; ++index) { |
| 370 | sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest); |
| 371 | } |
| 372 | // SkDebugf("%s sum=%d\n", __FUNCTION__, sum); |
| 373 | return sum; |
| 374 | } |
| 375 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 376 | void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 377 | // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; |
| 378 | // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; |
| 379 | int ofInterest = 1 << 5 | 1 << 8; |
| 380 | int total = 0; |
| 381 | int index; |
| 382 | for (index = 0; index < contourList.count(); ++index) { |
| 383 | total += contourList[index]->segments().count(); |
| 384 | } |
| 385 | int sum = 0; |
| 386 | for (index = 0; index < contourList.count(); ++index) { |
| 387 | sum += contourList[index]->debugShowWindingValues(total, ofInterest); |
| 388 | } |
| 389 | // SkDebugf("%s total=%d\n", __FUNCTION__, sum); |
| 390 | } |
| 391 | #endif |
| 392 | |
| 393 | void SkOpContour::setBounds() { |
| 394 | int count = fSegments.count(); |
| 395 | if (count == 0) { |
| 396 | SkDebugf("%s empty contour\n", __FUNCTION__); |
| 397 | SkASSERT(0); |
| 398 | // FIXME: delete empty contour? |
| 399 | return; |
| 400 | } |
| 401 | fBounds = fSegments.front().bounds(); |
| 402 | for (int index = 1; index < count; ++index) { |
| 403 | fBounds.add(fSegments[index].bounds()); |
| 404 | } |
| 405 | } |