123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425 |
- /*
- * 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;
- }
|