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