diff options
Diffstat (limited to 'gfx/skia/skia/src/pathops/SkPathOpsWinding.cpp')
| -rw-r--r-- | gfx/skia/skia/src/pathops/SkPathOpsWinding.cpp | 425 |
1 files changed, 425 insertions, 0 deletions
diff --git a/gfx/skia/skia/src/pathops/SkPathOpsWinding.cpp b/gfx/skia/skia/src/pathops/SkPathOpsWinding.cpp new file mode 100644 index 0000000000..4eb7298f3a --- /dev/null +++ b/gfx/skia/skia/src/pathops/SkPathOpsWinding.cpp @@ -0,0 +1,425 @@ +/* + * 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 <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.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<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; +} |