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" 10 #include "SkTSort.h" 11 12 void SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, 13 const SkIntersections& ts, bool swap) { 14 SkCoincidence& coincidence = fCoincidences.push_back(); 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 startSwapped, oStartSwapped, cancelers; 68 if ((cancelers = startSwapped = startT > endT)) { 69 SkTSwap(startT, endT); 70 } 71 SkASSERT(!approximately_negative(endT - startT)); 72 double oStartT = coincidence.fTs[1][0]; 73 double oEndT = coincidence.fTs[1][1]; 74 if ((oStartSwapped = oStartT > oEndT)) { 75 SkTSwap(oStartT, oEndT); 76 cancelers ^= true; 77 } 78 SkASSERT(!approximately_negative(oEndT - oStartT)); 79 if (cancelers) { 80 // make sure startT and endT have t entries 81 if (startT > 0 || oEndT < 1 82 || thisOne.isMissing(startT) || other.isMissing(oEndT)) { 83 thisOne.addTPair(startT, &other, oEndT, true, coincidence.fPts[startSwapped]); 84 } 85 if (oStartT > 0 || endT < 1 86 || thisOne.isMissing(endT) || other.isMissing(oStartT)) { 87 other.addTPair(oStartT, &thisOne, endT, true, coincidence.fPts[oStartSwapped]); 88 } 89 } else { 90 if (startT > 0 || oStartT > 0 91 || thisOne.isMissing(startT) || other.isMissing(oStartT)) { 92 thisOne.addTPair(startT, &other, oStartT, true, coincidence.fPts[startSwapped]); 93 } 94 if (endT < 1 || oEndT < 1 95 || thisOne.isMissing(endT) || other.isMissing(oEndT)) { 96 other.addTPair(oEndT, &thisOne, endT, true, coincidence.fPts[!oStartSwapped]); 97 } 98 } 99 #if DEBUG_CONCIDENT 100 thisOne.debugShowTs(); 101 other.debugShowTs(); 102 #endif 103 } 104 } 105 106 void SkOpContour::calcCoincidentWinding() { 107 int count = fCoincidences.count(); 108 for (int index = 0; index < count; ++index) { 109 SkCoincidence& coincidence = fCoincidences[index]; 110 SkASSERT(coincidence.fContours[0] == this); 111 int thisIndex = coincidence.fSegments[0]; 112 SkOpSegment& thisOne = fSegments[thisIndex]; 113 if (thisOne.done()) { 114 continue; 115 } 116 SkOpContour* otherContour = coincidence.fContours[1]; 117 int otherIndex = coincidence.fSegments[1]; 118 SkOpSegment& other = otherContour->fSegments[otherIndex]; 119 if (other.done()) { 120 continue; 121 } 122 double startT = coincidence.fTs[0][0]; 123 double endT = coincidence.fTs[0][1]; 124 bool cancelers; 125 if ((cancelers = startT > endT)) { 126 SkTSwap<double>(startT, endT); 127 } 128 SkASSERT(!approximately_negative(endT - startT)); 129 double oStartT = coincidence.fTs[1][0]; 130 double oEndT = coincidence.fTs[1][1]; 131 if (oStartT > oEndT) { 132 SkTSwap<double>(oStartT, oEndT); 133 cancelers ^= true; 134 } 135 SkASSERT(!approximately_negative(oEndT - oStartT)); 136 if (cancelers) { 137 // make sure startT and endT have t entries 138 if (!thisOne.done() && !other.done()) { 139 thisOne.addTCancel(startT, endT, &other, oStartT, oEndT); 140 } 141 } else { 142 if (!thisOne.done() && !other.done()) { 143 thisOne.addTCoincident(startT, endT, &other, oStartT, oEndT); 144 } 145 } 146 #if DEBUG_CONCIDENT 147 thisOne.debugShowTs(); 148 other.debugShowTs(); 149 #endif 150 } 151 } 152 153 void SkOpContour::sortSegments() { 154 int segmentCount = fSegments.count(); 155 fSortedSegments.push_back_n(segmentCount); 156 for (int test = 0; test < segmentCount; ++test) { 157 fSortedSegments[test] = &fSegments[test]; 158 } 159 SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1); 160 fFirstSorted = 0; 161 } 162 163 void SkOpContour::toPath(SkPathWriter* path) const { 164 int segmentCount = fSegments.count(); 165 const SkPoint& pt = fSegments.front().pts()[0]; 166 path->deferredMove(pt); 167 for (int test = 0; test < segmentCount; ++test) { 168 fSegments[test].addCurveTo(0, 1, path, true); 169 } 170 path->close(); 171 } 172 173 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, 174 SkOpSegment** topStart) { 175 int segmentCount = fSortedSegments.count(); 176 SkASSERT(segmentCount > 0); 177 int sortedIndex = fFirstSorted; 178 fDone = true; // may be cleared below 179 for ( ; sortedIndex < segmentCount; ++sortedIndex) { 180 SkOpSegment* testSegment = fSortedSegments[sortedIndex]; 181 if (testSegment->done()) { 182 if (sortedIndex == fFirstSorted) { 183 ++fFirstSorted; 184 } 185 continue; 186 } 187 fDone = false; 188 SkPoint testXY = testSegment->activeLeftTop(true, NULL); 189 if (*topStart) { 190 if (testXY.fY < topLeft.fY) { 191 continue; 192 } 193 if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { 194 continue; 195 } 196 if (bestXY->fY < testXY.fY) { 197 continue; 198 } 199 if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) { 200 continue; 201 } 202 } 203 *topStart = testSegment; 204 *bestXY = testXY; 205 } 206 } 207 208 SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) { 209 int segmentCount = fSegments.count(); 210 for (int test = 0; test < segmentCount; ++test) { 211 SkOpSegment* testSegment = &fSegments[test]; 212 if (testSegment->done()) { 213 continue; 214 } 215 testSegment->undoneSpan(start, end); 216 return testSegment; 217 } 218 return NULL; 219 } 220 221 #if DEBUG_SHOW_WINDING 222 int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) { 223 int count = fSegments.count(); 224 int sum = 0; 225 for (int index = 0; index < count; ++index) { 226 sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest); 227 } 228 // SkDebugf("%s sum=%d\n", __FUNCTION__, sum); 229 return sum; 230 } 231 232 static void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { 233 // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; 234 // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; 235 int ofInterest = 1 << 5 | 1 << 8; 236 int total = 0; 237 int index; 238 for (index = 0; index < contourList.count(); ++index) { 239 total += contourList[index]->segments().count(); 240 } 241 int sum = 0; 242 for (index = 0; index < contourList.count(); ++index) { 243 sum += contourList[index]->debugShowWindingValues(total, ofInterest); 244 } 245 // SkDebugf("%s total=%d\n", __FUNCTION__, sum); 246 } 247 #endif 248 249 void SkOpContour::setBounds() { 250 int count = fSegments.count(); 251 if (count == 0) { 252 SkDebugf("%s empty contour\n", __FUNCTION__); 253 SkASSERT(0); 254 // FIXME: delete empty contour? 255 return; 256 } 257 fBounds = fSegments.front().bounds(); 258 for (int index = 1; index < count; ++index) { 259 fBounds.add(fSegments[index].bounds()); 260 } 261 } 262
