| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 #include "SkAddIntersections.h" | 7 #include "SkAddIntersections.h" |
| 8 #include "SkOpEdgeBuilder.h" | 8 #include "SkOpEdgeBuilder.h" |
| 9 #include "SkPathOpsCommon.h" | 9 #include "SkPathOpsCommon.h" |
| 10 #include "SkPathWriter.h" | 10 #include "SkPathWriter.h" |
| (...skipping 188 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 199 void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) { | 199 void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) { |
| 200 int index; | 200 int index; |
| 201 for (index = 0; index < contourList.count(); ++ index) { | 201 for (index = 0; index < contourList.count(); ++ index) { |
| 202 contourList[index]->debugShowActiveSpans(); | 202 contourList[index]->debugShowActiveSpans(); |
| 203 } | 203 } |
| 204 } | 204 } |
| 205 #endif | 205 #endif |
| 206 | 206 |
| 207 static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourL
ist, | 207 static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourL
ist, |
| 208 int* index, int* endIndex, SkPoint* topLeft,
bool* unsortable, | 208 int* index, int* endIndex, SkPoint* topLeft,
bool* unsortable, |
| 209 bool* done, bool onlySortable) { | 209 bool* done, bool firstPass) { |
| 210 SkOpSegment* result; | 210 SkOpSegment* result; |
| 211 const SkOpSegment* lastTopStart = NULL; | 211 const SkOpSegment* lastTopStart = NULL; |
| 212 int lastIndex = -1, lastEndIndex = -1; | 212 int lastIndex = -1, lastEndIndex = -1; |
| 213 do { | 213 do { |
| 214 SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; | 214 SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; |
| 215 int contourCount = contourList.count(); | 215 int contourCount = contourList.count(); |
| 216 SkOpSegment* topStart = NULL; | 216 SkOpSegment* topStart = NULL; |
| 217 *done = true; | 217 *done = true; |
| 218 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { | 218 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 219 SkOpContour* contour = contourList[cIndex]; | 219 SkOpContour* contour = contourList[cIndex]; |
| (...skipping 11 matching lines...) Expand all Loading... |
| 231 } | 231 } |
| 232 contour->topSortableSegment(*topLeft, &bestXY, &topStart); | 232 contour->topSortableSegment(*topLeft, &bestXY, &topStart); |
| 233 if (!contour->done()) { | 233 if (!contour->done()) { |
| 234 *done = false; | 234 *done = false; |
| 235 } | 235 } |
| 236 } | 236 } |
| 237 if (!topStart) { | 237 if (!topStart) { |
| 238 return NULL; | 238 return NULL; |
| 239 } | 239 } |
| 240 *topLeft = bestXY; | 240 *topLeft = bestXY; |
| 241 result = topStart->findTop(index, endIndex, unsortable); | 241 result = topStart->findTop(index, endIndex, unsortable, firstPass); |
| 242 if (!result) { | 242 if (!result) { |
| 243 if (lastTopStart == topStart && lastIndex == *index && lastEndIndex
== *endIndex) { | 243 if (lastTopStart == topStart && lastIndex == *index && lastEndIndex
== *endIndex) { |
| 244 *done = true; | 244 *done = true; |
| 245 return NULL; | 245 return NULL; |
| 246 } | 246 } |
| 247 lastTopStart = topStart; | 247 lastTopStart = topStart; |
| 248 lastIndex = *index; | 248 lastIndex = *index; |
| 249 lastEndIndex = *endIndex; | 249 lastEndIndex = *endIndex; |
| 250 } | 250 } |
| 251 } while (!result); | 251 } while (!result); |
| 252 #if 0 |
| 252 if (result) { | 253 if (result) { |
| 253 *unsortable = false; | 254 *unsortable = false; |
| 254 } | 255 } |
| 256 #endif |
| 255 return result; | 257 return result; |
| 256 } | 258 } |
| 257 | 259 |
| 258 static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList, | 260 static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList, |
| 259 SkOpSegment** current, int* index, int* endIndex, d
ouble* tHit, | 261 SkOpSegment** current, int* index, int* endIndex, d
ouble* tHit, |
| 260 SkScalar* hitDx, bool* tryAgain, bool opp) { | 262 SkScalar* hitDx, bool* tryAgain, bool opp) { |
| 261 double test = 0.9; | 263 double test = 0.9; |
| 262 int contourWinding; | 264 int contourWinding; |
| 263 do { | 265 do { |
| 264 contourWinding = contourRangeCheckY(contourList, current, index, endInde
x, tHit, hitDx, | 266 contourWinding = contourRangeCheckY(contourList, current, index, endInde
x, tHit, hitDx, |
| (...skipping 11 matching lines...) Expand all Loading... |
| 276 SkOpSegment** current, int* index, int* endIndex) { | 278 SkOpSegment** current, int* index, int* endIndex) { |
| 277 if (!(*current)->isVertical(*index, *endIndex)) { | 279 if (!(*current)->isVertical(*index, *endIndex)) { |
| 278 return; | 280 return; |
| 279 } | 281 } |
| 280 int contourCount = contourList.count(); | 282 int contourCount = contourList.count(); |
| 281 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { | 283 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 282 SkOpContour* contour = contourList[cIndex]; | 284 SkOpContour* contour = contourList[cIndex]; |
| 283 if (contour->done()) { | 285 if (contour->done()) { |
| 284 continue; | 286 continue; |
| 285 } | 287 } |
| 286 *current = contour->nonVerticalSegment(index, endIndex); | 288 SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex); |
| 287 if (*current) { | 289 if (nonVertical) { |
| 290 *current = nonVertical; |
| 288 return; | 291 return; |
| 289 } | 292 } |
| 290 } | 293 } |
| 294 return; |
| 291 } | 295 } |
| 292 | 296 |
| 293 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, | 297 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, |
| 294 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexP
tr, | 298 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexP
tr, |
| 295 int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done) { | 299 int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool f
irstPass) { |
| 296 SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, t
opLeft, unsortable, | 300 SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, t
opLeft, unsortable, |
| 297 done, true); | 301 done, firstPass); |
| 298 if (!current) { | 302 if (!current) { |
| 299 return NULL; | 303 return NULL; |
| 300 } | 304 } |
| 301 const int index = *indexPtr; | 305 const int index = *indexPtr; |
| 302 const int endIndex = *endIndexPtr; | 306 const int endIndex = *endIndexPtr; |
| 303 if (*firstContour) { | 307 if (*firstContour) { |
| 304 current->initWinding(index, endIndex, angleIncludeType); | 308 current->initWinding(index, endIndex, angleIncludeType); |
| 305 *firstContour = false; | 309 *firstContour = false; |
| 306 return current; | 310 return current; |
| 307 } | 311 } |
| (...skipping 17 matching lines...) Expand all Loading... |
| 325 // shoot rays at right angles to the segment to find its winding, ignoring a
ngle cases | 329 // shoot rays at right angles to the segment to find its winding, ignoring a
ngle cases |
| 326 bool tryAgain; | 330 bool tryAgain; |
| 327 double tHit; | 331 double tHit; |
| 328 SkScalar hitDx = 0; | 332 SkScalar hitDx = 0; |
| 329 SkScalar hitOppDx = 0; | 333 SkScalar hitOppDx = 0; |
| 330 do { | 334 do { |
| 331 // if current is vertical, find another candidate which is not | 335 // if current is vertical, find another candidate which is not |
| 332 // if only remaining candidates are vertical, then they can be marked do
ne | 336 // if only remaining candidates are vertical, then they can be marked do
ne |
| 333 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); | 337 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); |
| 334 skipVertical(contourList, ¤t, indexPtr, endIndexPtr); | 338 skipVertical(contourList, ¤t, indexPtr, endIndexPtr); |
| 335 | 339 SkASSERT(current); // FIXME: if null, all remaining are vertical |
| 336 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); | 340 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >=
0); |
| 337 tryAgain = false; | 341 tryAgain = false; |
| 338 contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endI
ndexPtr, &tHit, | 342 contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endI
ndexPtr, &tHit, |
| 339 &hitDx, &tryAgain, false); | 343 &hitDx, &tryAgain, false); |
| 340 if (tryAgain) { | 344 if (tryAgain) { |
| 341 continue; | 345 continue; |
| 342 } | 346 } |
| 343 if (angleIncludeType < SkOpAngle::kBinarySingle) { | 347 if (angleIncludeType < SkOpAngle::kBinarySingle) { |
| 344 break; | 348 break; |
| 345 } | 349 } |
| 346 oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, e
ndIndexPtr, &tHit, | 350 oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, e
ndIndexPtr, &tHit, |
| 347 &hitOppDx, &tryAgain, true); | 351 &hitOppDx, &tryAgain, true); |
| 348 } while (tryAgain); | 352 } while (tryAgain); |
| 349 current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, o
ppContourWinding, | 353 current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, o
ppContourWinding, |
| 350 hitOppDx); | 354 hitOppDx); |
| 355 if (current->done()) { |
| 356 return NULL; |
| 357 } |
| 351 return current; | 358 return current; |
| 352 } | 359 } |
| 353 | 360 |
| 354 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { | 361 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { |
| 355 int contourCount = (*contourList).count(); | 362 int contourCount = (*contourList).count(); |
| 356 for (int cTest = 0; cTest < contourCount; ++cTest) { | 363 for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 357 SkOpContour* contour = (*contourList)[cTest]; | 364 SkOpContour* contour = (*contourList)[cTest]; |
| 358 if (!contour->calcAngles()) { | 365 if (!contour->calcAngles()) { |
| 359 return false; | 366 return false; |
| 360 } | 367 } |
| (...skipping 316 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 677 sortSegments(contourList); | 684 sortSegments(contourList); |
| 678 if (!calcAngles(contourList)) { | 685 if (!calcAngles(contourList)) { |
| 679 return false; | 686 return false; |
| 680 } | 687 } |
| 681 sortAngles(contourList); | 688 sortAngles(contourList); |
| 682 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY | 689 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY |
| 683 DebugShowActiveSpans(*contourList); | 690 DebugShowActiveSpans(*contourList); |
| 684 #endif | 691 #endif |
| 685 return true; | 692 return true; |
| 686 } | 693 } |
| OLD | NEW |