src/pathops/SkPathOpsWinding.cpp - platform/external/skqp - Gitiles

 /*
  * 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 "SkOpContour.h"
 #include "SkOpSegment.h"
 #include "SkPathOpsCurve.h"

 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,
         SkChunkAlloc* 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,
         SkChunkAlloc* 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 = SkOpTAllocator<SkOpRayHit>::Allocate(allocator);
         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) {
     SkChunkAlloc allocator(1024);
     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_yx(hitBase.fSlope.asSkVector(), dir)) {
         return false;
     }
     SkOpContour* contour = contourHead;
     do {
         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) {
             SkTSwap(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) {
             SkTSwap(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) {
     SkOpSegment* testSegment = &fHead;
     bool allDone = true;
     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;
 }
	/*
	* 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 "SkOpContour.h"
	#include "SkOpSegment.h"
	#include "SkPathOpsCurve.h"

	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,
	SkChunkAlloc* 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,
	SkChunkAlloc* 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 = SkOpTAllocator<SkOpRayHit>::Allocate(allocator);
	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) {
	SkChunkAlloc allocator(1024);
	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_yx(hitBase.fSlope.asSkVector(), dir)) {
	return false;
	}
	SkOpContour* contour = contourHead;
	do {
	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) {
	SkTSwap(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) {
	SkTSwap(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) {
	SkOpSegment* testSegment = &fHead;
	bool allDone = true;
	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;
	}