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 |