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 bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex, 13 const SkIntersections& ts, bool swap) { 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 } 23 SkCoincidence& coincidence = fCoincidences.push_back(); 24 coincidence.fOther = other; 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]; 31 coincidence.fPts[0] = pt0; 32 coincidence.fPts[1] = pt1; 33 return true; 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]; 60 int thisIndex = coincidence.fSegments[0]; 61 SkOpSegment& thisOne = fSegments[thisIndex]; 62 SkOpContour* otherContour = coincidence.fOther; 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 70 thisOne.debugShowTs("-"); 71 other.debugShowTs("o"); 72 #endif 73 double startT = coincidence.fTs[0][0]; 74 double endT = coincidence.fTs[0][1]; 75 bool startSwapped, oStartSwapped, cancelers; 76 if ((cancelers = startSwapped = startT > endT)) { 77 SkTSwap(startT, endT); 78 } 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 } 88 SkASSERT(!approximately_negative(endT - startT)); 89 double oStartT = coincidence.fTs[1][0]; 90 double oEndT = coincidence.fTs[1][1]; 91 if ((oStartSwapped = oStartT > oEndT)) { 92 SkTSwap(oStartT, oEndT); 93 cancelers ^= true; 94 } 95 SkASSERT(!approximately_negative(oEndT - oStartT)); 96 if (cancelers) { 97 // make sure startT and endT have t entries 98 const SkPoint& startPt = coincidence.fPts[startSwapped]; 99 if (startT > 0 || oEndT < 1 100 || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) { 101 thisOne.addTPair(startT, &other, oEndT, true, startPt); 102 } 103 const SkPoint& oStartPt = coincidence.fPts[oStartSwapped]; 104 if (oStartT > 0 || endT < 1 105 || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) { 106 other.addTPair(oStartT, &thisOne, endT, true, oStartPt); 107 } 108 } else { 109 const SkPoint& startPt = coincidence.fPts[startSwapped]; 110 if (startT > 0 || oStartT > 0 111 || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) { 112 thisOne.addTPair(startT, &other, oStartT, true, startPt); 113 } 114 const SkPoint& oEndPt = coincidence.fPts[!oStartSwapped]; 115 if (endT < 1 || oEndT < 1 116 || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) { 117 other.addTPair(oEndT, &thisOne, endT, true, oEndPt); 118 } 119 } 120 #if DEBUG_CONCIDENT 121 thisOne.debugShowTs("+"); 122 other.debugShowTs("o"); 123 #endif 124 } 125 } 126 127 bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex, 128 const SkIntersections& ts, int ptIndex, bool swap) { 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 } 138 SkCoincidence& coincidence = fPartialCoincidences.push_back(); 139 coincidence.fOther = other; 140 coincidence.fSegments[0] = index; 141 coincidence.fSegments[1] = otherIndex; 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; 149 } 150 151 void SkOpContour::calcCoincidentWinding() { 152 int count = fCoincidences.count(); 153 #if DEBUG_CONCIDENT 154 if (count > 0) { 155 SkDebugf("%s count=%d\n", __FUNCTION__, count); 156 } 157 #endif 158 for (int index = 0; index < count; ++index) { 159 SkCoincidence& coincidence = fCoincidences[index]; 160 calcCommonCoincidentWinding(coincidence); 161 } 162 } 163 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::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) { 178 int count = coincidences.count(); 179 #if DEBUG_CONCIDENT 180 if (count > 0) { 181 SkDebugf("%s count=%d\n", __FUNCTION__, count); 182 } 183 #endif 184 // look for a lineup where the partial implies another adjoining coincidence 185 for (int index = 0; index < count; ++index) { 186 const SkCoincidence& coincidence = coincidences[index]; 187 int thisIndex = coincidence.fSegments[0]; 188 SkOpSegment& thisOne = fSegments[thisIndex]; 189 SkOpContour* otherContour = coincidence.fOther; 190 int otherIndex = coincidence.fSegments[1]; 191 SkOpSegment& other = otherContour->fSegments[otherIndex]; 192 double startT = coincidence.fTs[0][0]; 193 double endT = coincidence.fTs[0][1]; 194 if (startT == endT) { // this can happen in very large compares 195 continue; 196 } 197 double oStartT = coincidence.fTs[1][0]; 198 double oEndT = coincidence.fTs[1][1]; 199 if (oStartT == oEndT) { 200 continue; 201 } 202 bool swapStart = startT > endT; 203 bool swapOther = oStartT > oEndT; 204 if (swapStart) { 205 SkTSwap<double>(startT, endT); 206 SkTSwap<double>(oStartT, oEndT); 207 } 208 bool cancel = swapOther != swapStart; 209 int step = swapStart ? -1 : 1; 210 int oStep = swapOther ? -1 : 1; 211 double oMatchStart = cancel ? oEndT : oStartT; 212 if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) { 213 bool added = false; 214 if (oMatchStart != 0) { 215 added = thisOne.joinCoincidence(&other, oMatchStart, oStep, cancel); 216 } 217 if (!cancel && startT != 0 && !added) { 218 (void) other.joinCoincidence(&thisOne, startT, step, cancel); 219 } 220 } 221 double oMatchEnd = cancel ? oStartT : oEndT; 222 if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) { 223 bool added = false; 224 if (cancel && endT != 1 && !added) { 225 (void) other.joinCoincidence(&thisOne, endT, -step, cancel); 226 } 227 } 228 } 229 } 230 231 void SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) { 232 int thisIndex = coincidence.fSegments[0]; 233 SkOpSegment& thisOne = fSegments[thisIndex]; 234 if (thisOne.done()) { 235 return; 236 } 237 SkOpContour* otherContour = coincidence.fOther; 238 int otherIndex = coincidence.fSegments[1]; 239 SkOpSegment& other = otherContour->fSegments[otherIndex]; 240 if (other.done()) { 241 return; 242 } 243 double startT = coincidence.fTs[0][0]; 244 double endT = coincidence.fTs[0][1]; 245 const SkPoint* startPt = &coincidence.fPts[0]; 246 const SkPoint* endPt = &coincidence.fPts[1]; 247 bool cancelers; 248 if ((cancelers = startT > endT)) { 249 SkTSwap<double>(startT, endT); 250 SkTSwap<const SkPoint*>(startPt, endPt); 251 } 252 if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing 253 if (endT <= 1 - FLT_EPSILON) { 254 endT += FLT_EPSILON; 255 SkASSERT(endT <= 1); 256 } else { 257 startT -= FLT_EPSILON; 258 SkASSERT(startT >= 0); 259 } 260 } 261 SkASSERT(!approximately_negative(endT - startT)); 262 double oStartT = coincidence.fTs[1][0]; 263 double oEndT = coincidence.fTs[1][1]; 264 if (oStartT > oEndT) { 265 SkTSwap<double>(oStartT, oEndT); 266 cancelers ^= true; 267 } 268 SkASSERT(!approximately_negative(oEndT - oStartT)); 269 if (cancelers) { 270 thisOne.addTCancel(*startPt, *endPt, &other); 271 } else { 272 thisOne.addTCoincident(*startPt, *endPt, endT, &other); 273 } 274 #if DEBUG_CONCIDENT 275 thisOne.debugShowTs("p"); 276 other.debugShowTs("o"); 277 #endif 278 } 279 280 void SkOpContour::sortSegments() { 281 int segmentCount = fSegments.count(); 282 fSortedSegments.push_back_n(segmentCount); 283 for (int test = 0; test < segmentCount; ++test) { 284 fSortedSegments[test] = &fSegments[test]; 285 } 286 SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1); 287 fFirstSorted = 0; 288 } 289 290 void SkOpContour::toPath(SkPathWriter* path) const { 291 int segmentCount = fSegments.count(); 292 const SkPoint& pt = fSegments.front().pts()[0]; 293 path->deferredMove(pt); 294 for (int test = 0; test < segmentCount; ++test) { 295 fSegments[test].addCurveTo(0, 1, path, true); 296 } 297 path->close(); 298 } 299 300 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY, 301 SkOpSegment** topStart) { 302 int segmentCount = fSortedSegments.count(); 303 SkASSERT(segmentCount > 0); 304 int sortedIndex = fFirstSorted; 305 fDone = true; // may be cleared below 306 for ( ; sortedIndex < segmentCount; ++sortedIndex) { 307 SkOpSegment* testSegment = fSortedSegments[sortedIndex]; 308 if (testSegment->done()) { 309 if (sortedIndex == fFirstSorted) { 310 ++fFirstSorted; 311 } 312 continue; 313 } 314 fDone = false; 315 SkPoint testXY = testSegment->activeLeftTop(true, NULL); 316 if (*topStart) { 317 if (testXY.fY < topLeft.fY) { 318 continue; 319 } 320 if (testXY.fY == topLeft.fY && testXY.fX < topLeft.fX) { 321 continue; 322 } 323 if (bestXY->fY < testXY.fY) { 324 continue; 325 } 326 if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) { 327 continue; 328 } 329 } 330 *topStart = testSegment; 331 *bestXY = testXY; 332 } 333 } 334 335 SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) { 336 int segmentCount = fSegments.count(); 337 for (int test = 0; test < segmentCount; ++test) { 338 SkOpSegment* testSegment = &fSegments[test]; 339 if (testSegment->done()) { 340 continue; 341 } 342 testSegment->undoneSpan(start, end); 343 return testSegment; 344 } 345 return NULL; 346 } 347 348 #if DEBUG_SHOW_WINDING 349 int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) { 350 int count = fSegments.count(); 351 int sum = 0; 352 for (int index = 0; index < count; ++index) { 353 sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest); 354 } 355 // SkDebugf("%s sum=%d\n", __FUNCTION__, sum); 356 return sum; 357 } 358 359 void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) { 360 // int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13; 361 // int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16; 362 int ofInterest = 1 << 5 | 1 << 8; 363 int total = 0; 364 int index; 365 for (index = 0; index < contourList.count(); ++index) { 366 total += contourList[index]->segments().count(); 367 } 368 int sum = 0; 369 for (index = 0; index < contourList.count(); ++index) { 370 sum += contourList[index]->debugShowWindingValues(total, ofInterest); 371 } 372 // SkDebugf("%s total=%d\n", __FUNCTION__, sum); 373 } 374 #endif 375 376 void SkOpContour::setBounds() { 377 int count = fSegments.count(); 378 if (count == 0) { 379 SkDebugf("%s empty contour\n", __FUNCTION__); 380 SkASSERT(0); 381 // FIXME: delete empty contour? 382 return; 383 } 384 fBounds = fSegments.front().bounds(); 385 for (int index = 1; index < count; ++index) { 386 fBounds.add(fSegments[index].bounds()); 387 } 388 } 389
