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 | |
| 12 | void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, |
| 13 | const SkIntersections& ts, bool swap) { |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 14 | SkCoincidence& coincidence = fCoincidences.push_back(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame^] | 15 | coincidence.fOther = other; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 16 | coincidence.fSegments[0] = index; |
| 17 | coincidence.fSegments[1] = otherIndex; |
| 18 | coincidence.fTs[swap][0] = ts[0][0]; |
| 19 | coincidence.fTs[swap][1] = ts[0][1]; |
| 20 | coincidence.fTs[!swap][0] = ts[1][0]; |
| 21 | coincidence.fTs[!swap][1] = ts[1][1]; |
| 22 | coincidence.fPts[0] = ts.pt(0).asSkPoint(); |
| 23 | coincidence.fPts[1] = ts.pt(1).asSkPoint(); |
| 24 | } |
| 25 | |
| 26 | SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) { |
| 27 | int segmentCount = fSortedSegments.count(); |
| 28 | SkASSERT(segmentCount > 0); |
| 29 | for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) { |
| 30 | SkOpSegment* testSegment = fSortedSegments[sortedIndex]; |
| 31 | if (testSegment->done()) { |
| 32 | continue; |
| 33 | } |
| 34 | *start = *end = 0; |
| 35 | while (testSegment->nextCandidate(start, end)) { |
| 36 | if (!testSegment->isVertical(*start, *end)) { |
| 37 | return testSegment; |
| 38 | } |
| 39 | } |
| 40 | } |
| 41 | return NULL; |
| 42 | } |
| 43 | |
| 44 | // first pass, add missing T values |
| 45 | // second pass, determine winding values of overlaps |
| 46 | void SkOpContour::addCoincidentPoints() { |
| 47 | int count = fCoincidences.count(); |
| 48 | for (int index = 0; index < count; ++index) { |
| 49 | SkCoincidence& coincidence = fCoincidences[index]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 50 | int thisIndex = coincidence.fSegments[0]; |
| 51 | SkOpSegment& thisOne = fSegments[thisIndex]; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame^] | 52 | SkOpContour* otherContour = coincidence.fOther; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 53 | int otherIndex = coincidence.fSegments[1]; |
| 54 | SkOpSegment& other = otherContour->fSegments[otherIndex]; |
| 55 | if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) { |
| 56 | // OPTIMIZATION: remove from array |
| 57 | continue; |
| 58 | } |
| 59 | #if DEBUG_CONCIDENT |
| 60 | thisOne.debugShowTs(); |
| 61 | other.debugShowTs(); |
| 62 | #endif |
| 63 | double startT = coincidence.fTs[0][0]; |
| 64 | double endT = coincidence.fTs[0][1]; |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 65 | bool startSwapped, oStartSwapped, cancelers; |
| 66 | if ((cancelers = startSwapped = startT > endT)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 67 | SkTSwap(startT, endT); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 68 | } |
| 69 | SkASSERT(!approximately_negative(endT - startT)); |
| 70 | double oStartT = coincidence.fTs[1][0]; |
| 71 | double oEndT = coincidence.fTs[1][1]; |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 72 | if ((oStartSwapped = oStartT > oEndT)) { |
| 73 | SkTSwap(oStartT, oEndT); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 74 | cancelers ^= true; |
| 75 | } |
| 76 | SkASSERT(!approximately_negative(oEndT - oStartT)); |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 77 | if (cancelers) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 78 | // make sure startT and endT have t entries |
| 79 | if (startT > 0 || oEndT < 1 |
| 80 | || thisOne.isMissing(startT) || other.isMissing(oEndT)) { |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 81 | thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[startSwapped]); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 82 | } |
| 83 | if (oStartT > 0 || endT < 1 |
| 84 | || thisOne.isMissing(endT) || other.isMissing(oStartT)) { |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 85 | other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[oStartSwapped]); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 86 | } |
| 87 | } else { |
| 88 | if (startT > 0 || oStartT > 0 |
| 89 | || thisOne.isMissing(startT) || other.isMissing(oStartT)) { |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 90 | thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[startSwapped]); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 91 | } |
| 92 | if (endT < 1 || oEndT < 1 |
| 93 | || thisOne.isMissing(endT) || other.isMissing(oEndT)) { |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 94 | other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[!oStartSwapped]); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 95 | } |
| 96 | } |
| 97 | #if DEBUG_CONCIDENT |
| 98 | thisOne.debugShowTs(); |
| 99 | other.debugShowTs(); |
| 100 | #endif |
| 101 | } |
| 102 | } |
| 103 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame^] | 104 | void SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, |
| 105 | const SkIntersections& ts, int ptIndex, bool swap) { |
| 106 | SkCoincidence& coincidence = fPartialCoincidences.push_back(); |
| 107 | coincidence.fOther = other; |
| 108 | coincidence.fSegments[0] = index; |
| 109 | coincidence.fSegments[1] = otherIndex; |
| 110 | coincidence.fTs[swap][0] = ts[0][index]; |
| 111 | coincidence.fTs[swap][1] = ts[0][index + 1]; |
| 112 | coincidence.fTs[!swap][0] = ts[1][index]; |
| 113 | coincidence.fTs[!swap][1] = ts[1][index + 1]; |
| 114 | coincidence.fPts[0] = ts.pt(index).asSkPoint(); |
| 115 | coincidence.fPts[1] = ts.pt(index + 1).asSkPoint(); |
| 116 | } |
| 117 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 118 | void SkOpContour::calcCoincidentWinding() { |
| 119 | int count = fCoincidences.count(); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame^] | 120 | #if DEBUG_CONCIDENT |
| 121 | if (count > 0) { |
| 122 | SkDebugf("%s count=%d\n", __FUNCTION__, count); |
| 123 | } |
| 124 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 125 | for (int index = 0; index < count; ++index) { |
| 126 | SkCoincidence& coincidence = fCoincidences[index]; |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame^] | 127 | calcCommonCoincidentWinding(coincidence); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 128 | } |
| 129 | } |
| 130 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame^] | 131 | void SkOpContour::calcPartialCoincidentWinding() { |
| 132 | int count = fPartialCoincidences.count(); |
| 133 | #if DEBUG_CONCIDENT |
| 134 | if (count > 0) { |
| 135 | SkDebugf("%s count=%d\n", __FUNCTION__, count); |
| 136 | } |
| 137 | #endif |
| 138 | for (int index = 0; index < count; ++index) { |
| 139 | SkCoincidence& coincidence = fPartialCoincidences[index]; |
| 140 | calcCommonCoincidentWinding(coincidence); |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { |
| 145 | int thisIndex = coincidence.fSegments[0]; |
| 146 | SkOpSegment& thisOne = fSegments[thisIndex]; |
| 147 | if (thisOne.done()) { |
| 148 | return; |
| 149 | } |
| 150 | SkOpContour* otherContour = coincidence.fOther; |
| 151 | int otherIndex = coincidence.fSegments[1]; |
| 152 | SkOpSegment& other = otherContour->fSegments[otherIndex]; |
| 153 | if (other.done()) { |
| 154 | return; |
| 155 | } |
| 156 | double startT = coincidence.fTs[0][0]; |
| 157 | double endT = coincidence.fTs[0][1]; |
| 158 | const SkPoint* startPt = &coincidence.fPts[0]; |
| 159 | const SkPoint* endPt = &coincidence.fPts[1]; |
| 160 | bool cancelers; |
| 161 | if ((cancelers = startT > endT)) { |
| 162 | SkTSwap<double>(startT, endT); |
| 163 | SkTSwap<const SkPoint*>(startPt, endPt); |
| 164 | } |
| 165 | SkASSERT(!approximately_negative(endT - startT)); |
| 166 | double oStartT = coincidence.fTs[1][0]; |
| 167 | double oEndT = coincidence.fTs[1][1]; |
| 168 | if (oStartT > oEndT) { |
| 169 | SkTSwap<double>(oStartT, oEndT); |
| 170 | cancelers ^= true; |
| 171 | } |
| 172 | SkASSERT(!approximately_negative(oEndT - oStartT)); |
| 173 | if (cancelers) { |
| 174 | thisOne.addTCancel(*startPt, *endPt, &other); |
| 175 | } else { |
| 176 | thisOne.addTCoincident(*startPt, *endPt, &other); |
| 177 | } |
| 178 | #if DEBUG_CONCIDENT |
| 179 | thisOne.debugShowTs(); |
| 180 | other.debugShowTs(); |
| 181 | #endif |
| 182 | } |
| 183 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 184 | void SkOpContour::sortSegments() { |
| 185 | int segmentCount = fSegments.count(); |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 186 | fSortedSegments.push_back_n(segmentCount); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 187 | for (int test = 0; test < segmentCount; ++test) { |
caryclark@google.com | d892bd8 | 2013-06-17 14:10:36 +0000 | [diff] [blame] | 188 | fSortedSegments[test] = &fSegments[test]; |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 189 | } |
commit-bot@chromium.org | b76d3b6 | 2013-04-22 19:55:19 +0000 | [diff] [blame] | 190 | SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 191 | fFirstSorted = 0; |
| 192 | } |
| 193 | |
| 194 | void SkOpContour::toPath(SkPathWriter* path) const { |
| 195 | int segmentCount = fSegments.count(); |
| 196 | const SkPoint& pt = fSegments.front().pts()[0]; |
| 197 | path->deferredMove(pt); |
| 198 | for (int test = 0; test < segmentCount; ++test) { |
| 199 | fSegments[test].addCurveTo(0, 1, path, true); |
| 200 | } |
| 201 | path->close(); |
| 202 | } |
| 203 | |
| 204 | void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, |
| 205 | SkOpSegment** topStart) { |
| 206 | int segmentCount = fSortedSegments.count(); |
| 207 | SkASSERT(segmentCount > 0); |
| 208 | int sortedIndex = fFirstSorted; |
| 209 | fDone = true; // may be cleared below |
| 210 | for ( ; sortedIndex < segmentCount; ++sortedIndex) { |
| 211 | SkOpSegment* testSegment = fSortedSegments[sortedIndex]; |
| 212 | if (testSegment->done()) { |
| 213 | if (sortedIndex == fFirstSorted) { |
| 214 | ++fFirstSorted; |
| 215 | } |
| 216 | continue; |
| 217 | } |
| 218 | fDone = false; |
| 219 | SkPoint testXY = testSegment->activeLeftTop(true, NULL); |
| 220 | if (*topStart) { |
| 221 | if (testXY.fY < topLeft.fY) { |
| 222 | continue; |
| 223 | } |
| 224 | if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { |
| 225 | continue; |
| 226 | } |
| 227 | if (bestXY->fY < testXY.fY) { |
| 228 | continue; |
| 229 | } |
| 230 | if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) { |
| 231 | continue; |
| 232 | } |
| 233 | } |
| 234 | *topStart = testSegment; |
| 235 | *bestXY = testXY; |
| 236 | } |
| 237 | } |
| 238 | |
| 239 | SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) { |
| 240 | int segmentCount = fSegments.count(); |
| 241 | for (int test = 0; test < segmentCount; ++test) { |
| 242 | SkOpSegment* testSegment = &fSegments[test]; |
| 243 | if (testSegment->done()) { |
| 244 | continue; |
| 245 | } |
| 246 | testSegment->undoneSpan(start, end); |
| 247 | return testSegment; |
| 248 | } |
| 249 | return NULL; |
| 250 | } |
| 251 | |
| 252 | #if DEBUG_SHOW_WINDING |
| 253 | int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) { |
| 254 | int count = fSegments.count(); |
| 255 | int sum = 0; |
| 256 | for (int index = 0; index < count; ++index) { |
| 257 | sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest); |
| 258 | } |
| 259 | // SkDebugf("%s sum=%d\n", __FUNCTION__, sum); |
| 260 | return sum; |
| 261 | } |
| 262 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame^] | 263 | void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 264 | // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; |
| 265 | // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; |
| 266 | int ofInterest = 1 << 5 | 1 << 8; |
| 267 | int total = 0; |
| 268 | int index; |
| 269 | for (index = 0; index < contourList.count(); ++index) { |
| 270 | total += contourList[index]->segments().count(); |
| 271 | } |
| 272 | int sum = 0; |
| 273 | for (index = 0; index < contourList.count(); ++index) { |
| 274 | sum += contourList[index]->debugShowWindingValues(total, ofInterest); |
| 275 | } |
| 276 | // SkDebugf("%s total=%d\n", __FUNCTION__, sum); |
| 277 | } |
| 278 | #endif |
| 279 | |
| 280 | void SkOpContour::setBounds() { |
| 281 | int count = fSegments.count(); |
| 282 | if (count == 0) { |
| 283 | SkDebugf("%s empty contour\n", __FUNCTION__); |
| 284 | SkASSERT(0); |
| 285 | // FIXME: delete empty contour? |
| 286 | return; |
| 287 | } |
| 288 | fBounds = fSegments.front().bounds(); |
| 289 | for (int index = 1; index < count; ++index) { |
| 290 | fBounds.add(fSegments[index].bounds()); |
| 291 | } |
| 292 | } |