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 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 151 | void SkOpContour::calcCoincidentWinding() { |
| 152 | int count = fCoincidences.count(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 153 | #if DEBUG_CONCIDENT |
| 154 | if (count > 0) { |
| 155 | SkDebugf("%s count=%d\n", __FUNCTION__, count); |
| 156 | } |
| 157 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 158 | for (int index = 0; index < count; ++index) { |
| 159 | SkCoincidence& coincidence = fCoincidences[index]; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 160 | calcCommonCoincidentWinding(coincidence); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 161 | } |
| 162 | } |
| 163 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 164 | void SkOpContour::calcPartialCoincidentWinding() { |
| 165 | int count = fPartialCoincidences.count(); |
| 166 | #if DEBUG_CONCIDENT |
| 167 | if (count > 0) { |
| 168 | SkDebugf("%s count=%d\n", __FUNCTION__, count); |
| 169 | } |
| 170 | #endif |
| 171 | for (int index = 0; index < count; ++index) { |
| 172 | SkCoincidence& coincidence = fPartialCoincidences[index]; |
| 173 | calcCommonCoincidentWinding(coincidence); |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { |
| 178 | int thisIndex = coincidence.fSegments[0]; |
| 179 | SkOpSegment& thisOne = fSegments[thisIndex]; |
| 180 | if (thisOne.done()) { |
| 181 | return; |
| 182 | } |
| 183 | SkOpContour* otherContour = coincidence.fOther; |
| 184 | int otherIndex = coincidence.fSegments[1]; |
| 185 | SkOpSegment& other = otherContour->fSegments[otherIndex]; |
| 186 | if (other.done()) { |
| 187 | return; |
| 188 | } |
| 189 | double startT = coincidence.fTs[0][0]; |
| 190 | double endT = coincidence.fTs[0][1]; |
| 191 | const SkPoint* startPt = &coincidence.fPts[0]; |
| 192 | const SkPoint* endPt = &coincidence.fPts[1]; |
| 193 | bool cancelers; |
| 194 | if ((cancelers = startT > endT)) { |
| 195 | SkTSwap<double>(startT, endT); |
| 196 | SkTSwap<const SkPoint*>(startPt, endPt); |
| 197 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 198 | if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing |
| 199 | if (endT <= 1 - FLT_EPSILON) { |
| 200 | endT += FLT_EPSILON; |
| 201 | SkASSERT(endT <= 1); |
| 202 | } else { |
| 203 | startT -= FLT_EPSILON; |
| 204 | SkASSERT(startT >= 0); |
| 205 | } |
| 206 | } |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 207 | SkASSERT(!approximately_negative(endT - startT)); |
| 208 | double oStartT = coincidence.fTs[1][0]; |
| 209 | double oEndT = coincidence.fTs[1][1]; |
| 210 | if (oStartT > oEndT) { |
| 211 | SkTSwap<double>(oStartT, oEndT); |
| 212 | cancelers ^= true; |
| 213 | } |
| 214 | SkASSERT(!approximately_negative(oEndT - oStartT)); |
| 215 | if (cancelers) { |
| 216 | thisOne.addTCancel(*startPt, *endPt, &other); |
| 217 | } else { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 218 | thisOne.addTCoincident(*startPt, *endPt, endT, &other); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 219 | } |
| 220 | #if DEBUG_CONCIDENT |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 221 | thisOne.debugShowTs("p"); |
| 222 | other.debugShowTs("o"); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 223 | #endif |
| 224 | } |
| 225 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 226 | void SkOpContour::sortSegments() { |
| 227 | int segmentCount = fSegments.count(); |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 228 | fSortedSegments.push_back_n(segmentCount); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 229 | for (int test = 0; test < segmentCount; ++test) { |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 230 | fSortedSegments[test] = &fSegments[test]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 231 | } |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 232 | SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 233 | fFirstSorted = 0; |
| 234 | } |
| 235 | |
| 236 | void SkOpContour::toPath(SkPathWriter* path) const { |
| 237 | int segmentCount = fSegments.count(); |
| 238 | const SkPoint& pt = fSegments.front().pts()[0]; |
| 239 | path->deferredMove(pt); |
| 240 | for (int test = 0; test < segmentCount; ++test) { |
| 241 | fSegments[test].addCurveTo(0, 1, path, true); |
| 242 | } |
| 243 | path->close(); |
| 244 | } |
| 245 | |
| 246 | void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, |
| 247 | SkOpSegment** topStart) { |
| 248 | int segmentCount = fSortedSegments.count(); |
| 249 | SkASSERT(segmentCount > 0); |
| 250 | int sortedIndex = fFirstSorted; |
| 251 | fDone = true; // may be cleared below |
| 252 | for ( ; sortedIndex < segmentCount; ++sortedIndex) { |
| 253 | SkOpSegment* testSegment = fSortedSegments[sortedIndex]; |
| 254 | if (testSegment->done()) { |
| 255 | if (sortedIndex == fFirstSorted) { |
| 256 | ++fFirstSorted; |
| 257 | } |
| 258 | continue; |
| 259 | } |
| 260 | fDone = false; |
| 261 | SkPoint testXY = testSegment->activeLeftTop(true, NULL); |
| 262 | if (*topStart) { |
| 263 | if (testXY.fY < topLeft.fY) { |
| 264 | continue; |
| 265 | } |
| 266 | if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { |
| 267 | continue; |
| 268 | } |
| 269 | if (bestXY->fY < testXY.fY) { |
| 270 | continue; |
| 271 | } |
| 272 | if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) { |
| 273 | continue; |
| 274 | } |
| 275 | } |
| 276 | *topStart = testSegment; |
| 277 | *bestXY = testXY; |
| 278 | } |
| 279 | } |
| 280 | |
| 281 | SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) { |
| 282 | int segmentCount = fSegments.count(); |
| 283 | for (int test = 0; test < segmentCount; ++test) { |
| 284 | SkOpSegment* testSegment = &fSegments[test]; |
| 285 | if (testSegment->done()) { |
| 286 | continue; |
| 287 | } |
| 288 | testSegment->undoneSpan(start, end); |
| 289 | return testSegment; |
| 290 | } |
| 291 | return NULL; |
| 292 | } |
| 293 | |
| 294 | #if DEBUG_SHOW_WINDING |
| 295 | int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) { |
| 296 | int count = fSegments.count(); |
| 297 | int sum = 0; |
| 298 | for (int index = 0; index < count; ++index) { |
| 299 | sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest); |
| 300 | } |
| 301 | // SkDebugf("%s sum=%d\n", __FUNCTION__, sum); |
| 302 | return sum; |
| 303 | } |
| 304 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 305 | void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 306 | // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; |
| 307 | // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; |
| 308 | int ofInterest = 1 << 5 | 1 << 8; |
| 309 | int total = 0; |
| 310 | int index; |
| 311 | for (index = 0; index < contourList.count(); ++index) { |
| 312 | total += contourList[index]->segments().count(); |
| 313 | } |
| 314 | int sum = 0; |
| 315 | for (index = 0; index < contourList.count(); ++index) { |
| 316 | sum += contourList[index]->debugShowWindingValues(total, ofInterest); |
| 317 | } |
| 318 | // SkDebugf("%s total=%d\n", __FUNCTION__, sum); |
| 319 | } |
| 320 | #endif |
| 321 | |
| 322 | void SkOpContour::setBounds() { |
| 323 | int count = fSegments.count(); |
| 324 | if (count == 0) { |
| 325 | SkDebugf("%s empty contour\n", __FUNCTION__); |
| 326 | SkASSERT(0); |
| 327 | // FIXME: delete empty contour? |
| 328 | return; |
| 329 | } |
| 330 | fBounds = fSegments.front().bounds(); |
| 331 | for (int index = 1; index < count; ++index) { |
| 332 | fBounds.add(fSegments[index].bounds()); |
| 333 | } |
| 334 | } |