| /* |
| * Copyright 2015 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| |
| // given a prospective edge, compute its initial winding by projecting a ray |
| // if the ray hits another edge |
| // if the edge doesn't have a winding yet, hop up to that edge and start over |
| // concern : check for hops forming a loop |
| // if the edge is unsortable, or |
| // the intersection is nearly at the ends, or |
| // the tangent at the intersection is nearly coincident to the ray, |
| // choose a different ray and try again |
| // concern : if it is unable to succeed after N tries, try another edge? direction? |
| // if no edge is hit, compute the winding directly |
| |
| // given the top span, project the most perpendicular ray and look for intersections |
| // let's try up and then down. What the hey |
| |
| // bestXY is initialized by caller with basePt |
| |
| #include "include/core/SkPath.h" |
| #include "include/core/SkPoint.h" |
| #include "include/core/SkRect.h" |
| #include "include/core/SkScalar.h" |
| #include "include/core/SkTypes.h" |
| #include "include/private/base/SkDebug.h" |
| #include "include/private/base/SkMalloc.h" |
| #include "include/private/base/SkMath.h" |
| #include "include/private/base/SkTArray.h" |
| #include "src/base/SkArenaAlloc.h" |
| #include "src/base/SkTSort.h" |
| #include "src/pathops/SkOpContour.h" |
| #include "src/pathops/SkOpSegment.h" |
| #include "src/pathops/SkOpSpan.h" |
| #include "src/pathops/SkPathOpsBounds.h" |
| #include "src/pathops/SkPathOpsCurve.h" |
| #include "src/pathops/SkPathOpsPoint.h" |
| #include "src/pathops/SkPathOpsTypes.h" |
| |
| #include <cmath> |
| #include <utility> |
| |
| enum class SkOpRayDir { |
| kLeft, |
| kTop, |
| kRight, |
| kBottom, |
| }; |
| |
| #if DEBUG_WINDING |
| const char* gDebugRayDirName[] = { |
| "kLeft", |
| "kTop", |
| "kRight", |
| "kBottom" |
| }; |
| #endif |
| |
| static int xy_index(SkOpRayDir dir) { |
| return static_cast<int>(dir) & 1; |
| } |
| |
| static SkScalar pt_xy(const SkPoint& pt, SkOpRayDir dir) { |
| return (&pt.fX)[xy_index(dir)]; |
| } |
| |
| static SkScalar pt_yx(const SkPoint& pt, SkOpRayDir dir) { |
| return (&pt.fX)[!xy_index(dir)]; |
| } |
| |
| static double pt_dxdy(const SkDVector& v, SkOpRayDir dir) { |
| return (&v.fX)[xy_index(dir)]; |
| } |
| |
| static double pt_dydx(const SkDVector& v, SkOpRayDir dir) { |
| return (&v.fX)[!xy_index(dir)]; |
| } |
| |
| static SkScalar rect_side(const SkRect& r, SkOpRayDir dir) { |
| return (&r.fLeft)[static_cast<int>(dir)]; |
| } |
| |
| static bool sideways_overlap(const SkRect& rect, const SkPoint& pt, SkOpRayDir dir) { |
| int i = !xy_index(dir); |
| return approximately_between((&rect.fLeft)[i], (&pt.fX)[i], (&rect.fRight)[i]); |
| } |
| |
| static bool less_than(SkOpRayDir dir) { |
| return static_cast<bool>((static_cast<int>(dir) & 2) == 0); |
| } |
| |
| static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) { |
| bool vPartPos = pt_dydx(v, dir) > 0; |
| bool leftBottom = ((static_cast<int>(dir) + 1) & 2) != 0; |
| return vPartPos == leftBottom; |
| } |
| |
| struct SkOpRayHit { |
| SkOpRayDir makeTestBase(SkOpSpan* span, double t) { |
| fNext = nullptr; |
| fSpan = span; |
| fT = span->t() * (1 - t) + span->next()->t() * t; |
| SkOpSegment* segment = span->segment(); |
| fSlope = segment->dSlopeAtT(fT); |
| fPt = segment->ptAtT(fT); |
| fValid = true; |
| return fabs(fSlope.fX) < fabs(fSlope.fY) ? SkOpRayDir::kLeft : SkOpRayDir::kTop; |
| } |
| |
| SkOpRayHit* fNext; |
| SkOpSpan* fSpan; |
| SkPoint fPt; |
| double fT; |
| SkDVector fSlope; |
| bool fValid; |
| }; |
| |
| void SkOpContour::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, |
| SkArenaAlloc* allocator) { |
| // if the bounds extreme is outside the best, we're done |
| SkScalar baseXY = pt_xy(base.fPt, dir); |
| SkScalar boundsXY = rect_side(fBounds, dir); |
| bool checkLessThan = less_than(dir); |
| if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { |
| return; |
| } |
| SkOpSegment* testSegment = &fHead; |
| do { |
| testSegment->rayCheck(base, dir, hits, allocator); |
| } while ((testSegment = testSegment->next())); |
| } |
| |
| void SkOpSegment::rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, |
| SkArenaAlloc* allocator) { |
| if (!sideways_overlap(fBounds, base.fPt, dir)) { |
| return; |
| } |
| SkScalar baseXY = pt_xy(base.fPt, dir); |
| SkScalar boundsXY = rect_side(fBounds, dir); |
| bool checkLessThan = less_than(dir); |
| if (!approximately_equal(baseXY, boundsXY) && (baseXY < boundsXY) == checkLessThan) { |
| return; |
| } |
| double tVals[3]; |
| SkScalar baseYX = pt_yx(base.fPt, dir); |
| int roots = (*CurveIntercept[fVerb * 2 + xy_index(dir)])(fPts, fWeight, baseYX, tVals); |
| for (int index = 0; index < roots; ++index) { |
| double t = tVals[index]; |
| if (base.fSpan->segment() == this && approximately_equal(base.fT, t)) { |
| continue; |
| } |
| SkDVector slope; |
| SkPoint pt; |
| SkDEBUGCODE(sk_bzero(&slope, sizeof(slope))); |
| bool valid = false; |
| if (approximately_zero(t)) { |
| pt = fPts[0]; |
| } else if (approximately_equal(t, 1)) { |
| pt = fPts[SkPathOpsVerbToPoints(fVerb)]; |
| } else { |
| SkASSERT(between(0, t, 1)); |
| pt = this->ptAtT(t); |
| if (SkDPoint::ApproximatelyEqual(pt, base.fPt)) { |
| if (base.fSpan->segment() == this) { |
| continue; |
| } |
| } else { |
| SkScalar ptXY = pt_xy(pt, dir); |
| if (!approximately_equal(baseXY, ptXY) && (baseXY < ptXY) == checkLessThan) { |
| continue; |
| } |
| slope = this->dSlopeAtT(t); |
| if (fVerb == SkPath::kCubic_Verb && base.fSpan->segment() == this |
| && roughly_equal(base.fT, t) |
| && SkDPoint::RoughlyEqual(pt, base.fPt)) { |
| #if DEBUG_WINDING |
| SkDebugf("%s (rarely expect this)\n", __FUNCTION__); |
| #endif |
| continue; |
| } |
| if (fabs(pt_dydx(slope, dir) * 10000) > fabs(pt_dxdy(slope, dir))) { |
| valid = true; |
| } |
| } |
| } |
| SkOpSpan* span = this->windingSpanAtT(t); |
| if (!span) { |
| valid = false; |
| } else if (!span->windValue() && !span->oppValue()) { |
| continue; |
| } |
| SkOpRayHit* newHit = allocator->make<SkOpRayHit>(); |
| newHit->fNext = *hits; |
| newHit->fPt = pt; |
| newHit->fSlope = slope; |
| newHit->fSpan = span; |
| newHit->fT = t; |
| newHit->fValid = valid; |
| *hits = newHit; |
| } |
| } |
| |
| SkOpSpan* SkOpSegment::windingSpanAtT(double tHit) { |
| SkOpSpan* span = &fHead; |
| SkOpSpanBase* next; |
| do { |
| next = span->next(); |
| if (approximately_equal(tHit, next->t())) { |
| return nullptr; |
| } |
| if (tHit < next->t()) { |
| return span; |
| } |
| } while (!next->final() && (span = next->upCast())); |
| return nullptr; |
| } |
| |
| static bool hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { |
| return a->fPt.fX < b->fPt.fX; |
| } |
| |
| static bool reverse_hit_compare_x(const SkOpRayHit* a, const SkOpRayHit* b) { |
| return b->fPt.fX < a->fPt.fX; |
| } |
| |
| static bool hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { |
| return a->fPt.fY < b->fPt.fY; |
| } |
| |
| static bool reverse_hit_compare_y(const SkOpRayHit* a, const SkOpRayHit* b) { |
| return b->fPt.fY < a->fPt.fY; |
| } |
| |
| static double get_t_guess(int tTry, int* dirOffset) { |
| double t = 0.5; |
| *dirOffset = tTry & 1; |
| int tBase = tTry >> 1; |
| int tBits = 0; |
| while (tTry >>= 1) { |
| t /= 2; |
| ++tBits; |
| } |
| if (tBits) { |
| int tIndex = (tBase - 1) & ((1 << tBits) - 1); |
| t += t * 2 * tIndex; |
| } |
| return t; |
| } |
| |
| bool SkOpSpan::sortableTop(SkOpContour* contourHead) { |
| SkSTArenaAlloc<1024> allocator; |
| int dirOffset; |
| double t = get_t_guess(fTopTTry++, &dirOffset); |
| SkOpRayHit hitBase; |
| SkOpRayDir dir = hitBase.makeTestBase(this, t); |
| if (hitBase.fSlope.fX == 0 && hitBase.fSlope.fY == 0) { |
| return false; |
| } |
| SkOpRayHit* hitHead = &hitBase; |
| dir = static_cast<SkOpRayDir>(static_cast<int>(dir) + dirOffset); |
| if (hitBase.fSpan && hitBase.fSpan->segment()->verb() > SkPath::kLine_Verb |
| && !pt_dydx(hitBase.fSlope, dir)) { |
| return false; |
| } |
| SkOpContour* contour = contourHead; |
| do { |
| if (!contour->count()) { |
| continue; |
| } |
| contour->rayCheck(hitBase, dir, &hitHead, &allocator); |
| } while ((contour = contour->next())); |
| // sort hits |
| SkSTArray<1, SkOpRayHit*> sorted; |
| SkOpRayHit* hit = hitHead; |
| while (hit) { |
| sorted.push_back(hit); |
| hit = hit->fNext; |
| } |
| int count = sorted.size(); |
| SkTQSort(sorted.begin(), sorted.end(), |
| xy_index(dir) ? less_than(dir) ? hit_compare_y : reverse_hit_compare_y |
| : less_than(dir) ? hit_compare_x : reverse_hit_compare_x); |
| // verify windings |
| #if DEBUG_WINDING |
| SkDebugf("%s dir=%s seg=%d t=%1.9g pt=(%1.9g,%1.9g)\n", __FUNCTION__, |
| gDebugRayDirName[static_cast<int>(dir)], hitBase.fSpan->segment()->debugID(), |
| hitBase.fT, hitBase.fPt.fX, hitBase.fPt.fY); |
| for (int index = 0; index < count; ++index) { |
| hit = sorted[index]; |
| SkOpSpan* span = hit->fSpan; |
| SkOpSegment* hitSegment = span ? span->segment() : nullptr; |
| bool operand = span ? hitSegment->operand() : false; |
| bool ccw = ccw_dxdy(hit->fSlope, dir); |
| SkDebugf("%s [%d] valid=%d operand=%d span=%d ccw=%d ", __FUNCTION__, index, |
| hit->fValid, operand, span ? span->debugID() : -1, ccw); |
| if (span) { |
| hitSegment->dumpPtsInner(); |
| } |
| SkDebugf(" t=%1.9g pt=(%1.9g,%1.9g) slope=(%1.9g,%1.9g)\n", hit->fT, |
| hit->fPt.fX, hit->fPt.fY, hit->fSlope.fX, hit->fSlope.fY); |
| } |
| #endif |
| const SkPoint* last = nullptr; |
| int wind = 0; |
| int oppWind = 0; |
| for (int index = 0; index < count; ++index) { |
| hit = sorted[index]; |
| if (!hit->fValid) { |
| return false; |
| } |
| bool ccw = ccw_dxdy(hit->fSlope, dir); |
| // SkASSERT(!approximately_zero(hit->fT) || !hit->fValid); |
| SkOpSpan* span = hit->fSpan; |
| if (!span) { |
| return false; |
| } |
| SkOpSegment* hitSegment = span->segment(); |
| if (span->windValue() == 0 && span->oppValue() == 0) { |
| continue; |
| } |
| if (last && SkDPoint::ApproximatelyEqual(*last, hit->fPt)) { |
| return false; |
| } |
| if (index < count - 1) { |
| const SkPoint& next = sorted[index + 1]->fPt; |
| if (SkDPoint::ApproximatelyEqual(next, hit->fPt)) { |
| return false; |
| } |
| } |
| bool operand = hitSegment->operand(); |
| if (operand) { |
| using std::swap; |
| swap(wind, oppWind); |
| } |
| int lastWind = wind; |
| int lastOpp = oppWind; |
| int windValue = ccw ? -span->windValue() : span->windValue(); |
| int oppValue = ccw ? -span->oppValue() : span->oppValue(); |
| wind += windValue; |
| oppWind += oppValue; |
| bool sumSet = false; |
| int spanSum = span->windSum(); |
| int windSum = SkOpSegment::UseInnerWinding(lastWind, wind) ? wind : lastWind; |
| if (spanSum == SK_MinS32) { |
| span->setWindSum(windSum); |
| sumSet = true; |
| } else { |
| // the need for this condition suggests that UseInnerWinding is flawed |
| // happened when last = 1 wind = -1 |
| #if 0 |
| SkASSERT((hitSegment->isXor() ? (windSum & 1) == (spanSum & 1) : windSum == spanSum) |
| || (abs(wind) == abs(lastWind) |
| && (windSum ^ wind ^ lastWind) == spanSum)); |
| #endif |
| } |
| int oSpanSum = span->oppSum(); |
| int oppSum = SkOpSegment::UseInnerWinding(lastOpp, oppWind) ? oppWind : lastOpp; |
| if (oSpanSum == SK_MinS32) { |
| span->setOppSum(oppSum); |
| } else { |
| #if 0 |
| SkASSERT(hitSegment->oppXor() ? (oppSum & 1) == (oSpanSum & 1) : oppSum == oSpanSum |
| || (abs(oppWind) == abs(lastOpp) |
| && (oppSum ^ oppWind ^ lastOpp) == oSpanSum)); |
| #endif |
| } |
| if (sumSet) { |
| if (this->globalState()->phase() == SkOpPhase::kFixWinding) { |
| hitSegment->contour()->setCcw(ccw); |
| } else { |
| (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, nullptr); |
| (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, nullptr); |
| } |
| } |
| if (operand) { |
| using std::swap; |
| swap(wind, oppWind); |
| } |
| last = &hit->fPt; |
| this->globalState()->bumpNested(); |
| } |
| return true; |
| } |
| |
| SkOpSpan* SkOpSegment::findSortableTop(SkOpContour* contourHead) { |
| SkOpSpan* span = &fHead; |
| SkOpSpanBase* next; |
| do { |
| next = span->next(); |
| if (span->done()) { |
| continue; |
| } |
| if (span->windSum() != SK_MinS32) { |
| return span; |
| } |
| if (span->sortableTop(contourHead)) { |
| return span; |
| } |
| } while (!next->final() && (span = next->upCast())); |
| return nullptr; |
| } |
| |
| SkOpSpan* SkOpContour::findSortableTop(SkOpContour* contourHead) { |
| bool allDone = true; |
| if (fCount) { |
| SkOpSegment* testSegment = &fHead; |
| do { |
| if (testSegment->done()) { |
| continue; |
| } |
| allDone = false; |
| SkOpSpan* result = testSegment->findSortableTop(contourHead); |
| if (result) { |
| return result; |
| } |
| } while ((testSegment = testSegment->next())); |
| } |
| if (allDone) { |
| fDone = true; |
| } |
| return nullptr; |
| } |
| |
| SkOpSpan* FindSortableTop(SkOpContourHead* contourHead) { |
| for (int index = 0; index < SkOpGlobalState::kMaxWindingTries; ++index) { |
| SkOpContour* contour = contourHead; |
| do { |
| if (contour->done()) { |
| continue; |
| } |
| SkOpSpan* result = contour->findSortableTop(contourHead); |
| if (result) { |
| return result; |
| } |
| } while ((contour = contour->next())); |
| } |
| return nullptr; |
| } |