/* * 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 "src/pathops/SkOpContour.h" #include "src/pathops/SkOpSegment.h" #include "src/pathops/SkPathOpsCurve.h" #include 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(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(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((static_cast(dir) & 2) == 0); } static bool ccw_dxdy(const SkDVector& v, SkOpRayDir dir) { bool vPartPos = pt_dydx(v, dir) > 0; bool leftBottom = ((static_cast(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(); 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(static_cast(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.count(); SkTQSort(sorted.begin(), sorted.end() - 1, 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(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; }