123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333 |
- /*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "include/private/SkMacros.h"
- #include "src/core/SkTSort.h"
- #include "src/pathops/SkAddIntersections.h"
- #include "src/pathops/SkOpCoincidence.h"
- #include "src/pathops/SkOpEdgeBuilder.h"
- #include "src/pathops/SkPathOpsCommon.h"
- #include "src/pathops/SkPathWriter.h"
- const SkOpAngle* AngleWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* windingPtr,
- bool* sortablePtr) {
- // find first angle, initialize winding to computed fWindSum
- SkOpSegment* segment = start->segment();
- const SkOpAngle* angle = segment->spanToAngle(start, end);
- if (!angle) {
- *windingPtr = SK_MinS32;
- return nullptr;
- }
- bool computeWinding = false;
- const SkOpAngle* firstAngle = angle;
- bool loop = false;
- bool unorderable = false;
- int winding = SK_MinS32;
- do {
- angle = angle->next();
- if (!angle) {
- return nullptr;
- }
- unorderable |= angle->unorderable();
- if ((computeWinding = unorderable || (angle == firstAngle && loop))) {
- break; // if we get here, there's no winding, loop is unorderable
- }
- loop |= angle == firstAngle;
- segment = angle->segment();
- winding = segment->windSum(angle);
- } while (winding == SK_MinS32);
- // if the angle loop contains an unorderable span, the angle order may be useless
- // directly compute the winding in this case for each span
- if (computeWinding) {
- firstAngle = angle;
- winding = SK_MinS32;
- do {
- SkOpSpanBase* startSpan = angle->start();
- SkOpSpanBase* endSpan = angle->end();
- SkOpSpan* lesser = startSpan->starter(endSpan);
- int testWinding = lesser->windSum();
- if (testWinding == SK_MinS32) {
- testWinding = lesser->computeWindSum();
- }
- if (testWinding != SK_MinS32) {
- segment = angle->segment();
- winding = testWinding;
- }
- angle = angle->next();
- } while (angle != firstAngle);
- }
- *sortablePtr = !unorderable;
- *windingPtr = winding;
- return angle;
- }
- SkOpSpan* FindUndone(SkOpContourHead* contourHead) {
- SkOpContour* contour = contourHead;
- do {
- if (contour->done()) {
- continue;
- }
- SkOpSpan* result = contour->undoneSpan();
- if (result) {
- return result;
- }
- } while ((contour = contour->next()));
- return nullptr;
- }
- SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
- SkOpSpanBase** endPtr) {
- while (chase->count()) {
- SkOpSpanBase* span;
- chase->pop(&span);
- SkOpSegment* segment = span->segment();
- *startPtr = span->ptT()->next()->span();
- bool done = true;
- *endPtr = nullptr;
- if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done)) {
- *startPtr = last->start();
- *endPtr = last->end();
- #if TRY_ROTATE
- *chase->insert(0) = span;
- #else
- *chase->append() = span;
- #endif
- return last->segment();
- }
- if (done) {
- continue;
- }
- // find first angle, initialize winding to computed wind sum
- int winding;
- bool sortable;
- const SkOpAngle* angle = AngleWinding(*startPtr, *endPtr, &winding, &sortable);
- if (!angle) {
- return nullptr;
- }
- if (winding == SK_MinS32) {
- continue;
- }
- int sumWinding SK_INIT_TO_AVOID_WARNING;
- if (sortable) {
- segment = angle->segment();
- sumWinding = segment->updateWindingReverse(angle);
- }
- SkOpSegment* first = nullptr;
- const SkOpAngle* firstAngle = angle;
- while ((angle = angle->next()) != firstAngle) {
- segment = angle->segment();
- SkOpSpanBase* start = angle->start();
- SkOpSpanBase* end = angle->end();
- int maxWinding SK_INIT_TO_AVOID_WARNING;
- if (sortable) {
- segment->setUpWinding(start, end, &maxWinding, &sumWinding);
- }
- if (!segment->done(angle)) {
- if (!first && (sortable || start->starter(end)->windSum() != SK_MinS32)) {
- first = segment;
- *startPtr = start;
- *endPtr = end;
- }
- // OPTIMIZATION: should this also add to the chase?
- if (sortable) {
- // TODO: add error handling
- SkAssertResult(segment->markAngle(maxWinding, sumWinding, angle, nullptr));
- }
- }
- }
- if (first) {
- #if TRY_ROTATE
- *chase->insert(0) = span;
- #else
- *chase->append() = span;
- #endif
- return first;
- }
- }
- return nullptr;
- }
- bool SortContourList(SkOpContourHead** contourList, bool evenOdd, bool oppEvenOdd) {
- SkTDArray<SkOpContour* > list;
- SkOpContour* contour = *contourList;
- do {
- if (contour->count()) {
- contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
- *list.append() = contour;
- }
- } while ((contour = contour->next()));
- int count = list.count();
- if (!count) {
- return false;
- }
- if (count > 1) {
- SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
- }
- contour = list[0];
- SkOpContourHead* contourHead = static_cast<SkOpContourHead*>(contour);
- contour->globalState()->setContourHead(contourHead);
- *contourList = contourHead;
- for (int index = 1; index < count; ++index) {
- SkOpContour* next = list[index];
- contour->setNext(next);
- contour = next;
- }
- contour->setNext(nullptr);
- return true;
- }
- static void calc_angles(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
- DEBUG_STATIC_SET_PHASE(contourList);
- SkOpContour* contour = contourList;
- do {
- contour->calcAngles();
- } while ((contour = contour->next()));
- }
- static bool missing_coincidence(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
- DEBUG_STATIC_SET_PHASE(contourList);
- SkOpContour* contour = contourList;
- bool result = false;
- do {
- result |= contour->missingCoincidence();
- } while ((contour = contour->next()));
- return result;
- }
- static bool move_multiples(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
- DEBUG_STATIC_SET_PHASE(contourList);
- SkOpContour* contour = contourList;
- do {
- if (!contour->moveMultiples()) {
- return false;
- }
- } while ((contour = contour->next()));
- return true;
- }
- static bool move_nearby(SkOpContourHead* contourList DEBUG_COIN_DECLARE_PARAMS()) {
- DEBUG_STATIC_SET_PHASE(contourList);
- SkOpContour* contour = contourList;
- do {
- if (!contour->moveNearby()) {
- return false;
- }
- } while ((contour = contour->next()));
- return true;
- }
- static bool sort_angles(SkOpContourHead* contourList) {
- SkOpContour* contour = contourList;
- do {
- if (!contour->sortAngles()) {
- return false;
- }
- } while ((contour = contour->next()));
- return true;
- }
- bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidence) {
- SkOpGlobalState* globalState = contourList->globalState();
- // match up points within the coincident runs
- if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kIntersecting))) {
- return false;
- }
- // combine t values when multiple intersections occur on some segments but not others
- if (!move_multiples(contourList DEBUG_PHASE_PARAMS(kWalking))) {
- return false;
- }
- // move t values and points together to eliminate small/tiny gaps
- if (!move_nearby(contourList DEBUG_COIN_PARAMS())) {
- return false;
- }
- // add coincidence formed by pairing on curve points and endpoints
- coincidence->correctEnds(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
- if (!coincidence->addEndMovedSpans(DEBUG_COIN_ONLY_PARAMS())) {
- return false;
- }
- const int SAFETY_COUNT = 3;
- int safetyHatch = SAFETY_COUNT;
- // look for coincidence present in A-B and A-C but missing in B-C
- do {
- bool added;
- if (!coincidence->addMissing(&added DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
- return false;
- }
- if (!added) {
- break;
- }
- if (!--safetyHatch) {
- SkASSERT(globalState->debugSkipAssert());
- return false;
- }
- move_nearby(contourList DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch - 1));
- } while (true);
- // check to see if, loosely, coincident ranges may be expanded
- if (coincidence->expand(DEBUG_COIN_ONLY_PARAMS())) {
- bool added;
- if (!coincidence->addMissing(&added DEBUG_COIN_PARAMS())) {
- return false;
- }
- if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
- return false;
- }
- if (!move_multiples(contourList DEBUG_COIN_PARAMS())) {
- return false;
- }
- move_nearby(contourList DEBUG_COIN_PARAMS());
- }
- // the expanded ranges may not align -- add the missing spans
- if (!coincidence->addExpanded(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
- return false;
- }
- // mark spans of coincident segments as coincident
- coincidence->mark(DEBUG_COIN_ONLY_PARAMS());
- // look for coincidence lines and curves undetected by intersection
- if (missing_coincidence(contourList DEBUG_COIN_PARAMS())) {
- (void) coincidence->expand(DEBUG_PHASE_ONLY_PARAMS(kIntersecting));
- if (!coincidence->addExpanded(DEBUG_COIN_ONLY_PARAMS())) {
- return false;
- }
- if (!coincidence->mark(DEBUG_PHASE_ONLY_PARAMS(kWalking))) {
- return false;
- }
- } else {
- (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
- }
- (void) coincidence->expand(DEBUG_COIN_ONLY_PARAMS());
- SkOpCoincidence overlaps(globalState);
- safetyHatch = SAFETY_COUNT;
- do {
- SkOpCoincidence* pairs = overlaps.isEmpty() ? coincidence : &overlaps;
- // adjust the winding value to account for coincident edges
- if (!pairs->apply(DEBUG_ITER_ONLY_PARAMS(SAFETY_COUNT - safetyHatch))) {
- return false;
- }
- // For each coincident pair that overlaps another, when the receivers (the 1st of the pair)
- // are different, construct a new pair to resolve their mutual span
- if (!pairs->findOverlaps(&overlaps DEBUG_ITER_PARAMS(SAFETY_COUNT - safetyHatch))) {
- return false;
- }
- if (!--safetyHatch) {
- SkASSERT(globalState->debugSkipAssert());
- return false;
- }
- } while (!overlaps.isEmpty());
- calc_angles(contourList DEBUG_COIN_PARAMS());
- if (!sort_angles(contourList)) {
- return false;
- }
- #if DEBUG_COINCIDENCE_VERBOSE
- coincidence->debugShowCoincidence();
- #endif
- #if DEBUG_COINCIDENCE
- coincidence->debugValidate();
- #endif
- SkPathOpsDebug::ShowActiveSpans(contourList);
- return true;
- }
|