experimental/Intersection/thingsToDo.txt - skia - Git at Google

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 add unit test for quadratic horizontal intersection
 add unit test for cubic horizontal intersection with left/right
 add unit test for ActiveEdge::calcLeft (can currently loop forever)
 does ActiveEdge::isCoincidentWith need to support quad, cubic?
 figure out why variation in ActiveEdge::tooCloseToCall isn't better
 why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22?
 add code to promote quad to cubic, or add quad/cubic intersection
 figure out why testSimplifySkinnyTriangle13 fails

 for quadratics and cubics, once various T values are added, see if consecutive
 Ts have ys that go up instead of down. If so, the edge needs to be broken.

 when splitting curves at inflection pts, should I retain the original curve
 data and note that the first/last T are no longer 0/1 ?
 I need to figure this out before I can proceed

 would it make sense to leave the InEdge alone, and add multiple copies of
 ActiveEdge, pointing to the same InEdge, where the copy has only the subset
 of Ts that need to be walked in reverse order?


 -- A Digression Which Shows Why Resolving Coincidence Does Not Make Sense --

 Consider the following fine ASCII art:

   +------>-------+       +------>-------+
   |              |       |              |
   ^              V       ^              V
   |              |       |              |
   +------<-------+       +------<-------+
   +------>-------+       +------<-------+
   |              |       |              |
   ^              V       V              ^
   |              |       |              |
   +------<-------+       +------>-------+

 (assume the bottom and top of the stacked rectangles are coincident)

 Simplifying said rectangles, regardless of rectangle direction, and regardless
 of winding or even/odd, eliminates the coincident edge, i.e., the result is
 always:

   +------>-------+
   |              |
   |              |
   |              |
   ^              V
   |              |
   |              |
   |              |
   +------<-------+

 But when the rectangles are enclosed in a larger rectangle:

 +-------->---------+    +-------->---------+
 | +------>-------+ |    | +------>-------+ |
 | |              | |    | |              | |
 | ^              V |    | ^              V |
 | |              | |    | |              | |
 | +------<-------+ |    | +------<-------+ |
 | +------>-------+ |    | +------<-------+ |
 | |              | |    | |              | |
 | ^              V |    | V              ^ |
 | |              | |    | |              | |
 | +------<-------+ |    | +------>-------+ |
 +--------<---------+    +--------<---------+

 Simplifying them gives different results depending on the winding setting:

 winding:
 +-------->---------+    +-------->---------+
 |                  |    |                  |
 |                  |    |                  |
 |                  |    |                  |
 |                  |    |                  |
 |                  |    | +------<-------+ |
 |                  |    | |              | |
 |                  |    | V              ^ |
 |                  |    | |              | |
 |                  |    | +------>-------+ |
 +--------<---------+    +--------<---------+

 even odd:
 +-------->---------+    +-------->---------+
 | +------<-------+ |    | +------<-------+ |
 | |              | |    | |              | |
 | |              | |    | |              | |
 | |              | |    | |              | |
 | |              | |    | |              | |
 | V              ^ |    | V              ^ |
 | |              | |    | |              | |
 | |              | |    | |              | |
 | |              | |    | |              | |
 | +------>-------+ |    | +------>-------+ |
 +--------<---------+    +--------<---------+

 So, given the inner rectangles alone (e.g., given coincident pairs in some local
 context), we can't know whether to keep the coincident edges or not.


 -- Thoughts About Sortless Ops --

 I can't come up with anything truly sortless. It seems that the crossings need
 to be sorted to know which segment is next on the outside, although sometimes
 we can use that it is not coincident just to follow the direction.

 If it is coincident or if there's more than two crossing segments, sorting
 seems inevitable.

 Likewise, to resolve whether one contour is inside another, it seems that
 sorting is required. Given a pair of segments on different contours, to know
 if one is inside of the other, I need to know for each which side of the edge
 is the inside/filled side. When the outer contour is walked, it seems like I
 could record the inside info. I guess when the inner contour is found, its
 inside sense is reversed (inside is above the top). But how do I know if the
 next contour is inside another? Maybe shoot out a line and brute-force
 intersect it with all the segments in all the other contours? If every contour
 has an extra segment when the intersections are computed, this may not be as
 crazy as it seems.

 Suppose each contour has one extra segment shooting straight up from the top
 (or straight up from any point on the segment). This ray is not intersected
 with the home contour, but is intersected with all other contours as part of
 the normal intersection engine. If it is possible to get from the T values to
 the other segments to the other contours, it would be straightforward to
 count the contour crossings and determine if the home contour is in another
 contour or not (if the count is even, not, if odd, is inside). By itself that
 doesn't tell us about winding, but it's a start.


 Since intersecting these rays is unrelated to computing other intersections,
 it can be lazily done once the contour is found.

 So
 repeat the following
 find the top segment of all contours
 trace the outside, marking touching first and last segments as inside
 continue tracing the touched segments with reversed outside/inside sense
 once the edges are exhausted, remaining must be disjoint contours
 send a ray from a disjoint point through all other contours
 count the crossings, determine if disjoint is inside or outside, then continue

 ===

 On Quadratic (and Cubic) Intersections

 Currently, if only the end points touch, QuadracticIntersections does a lot of
 work to figure that out. Can I test for that up front, then short circuit the
 recursive search for the end points?

 Or, is there something defective in the current approach that makes the end
 point recursion go so deep? I'm seeing 56 stack frames (about 28 divides, but
 thankfully, no splits) to find one matching endpoint.


 Bezier curve focus may allow more quickly determining that end points with
 identical tangents are practically coicident for some range of T, but I don't
 understand the math yet to know.

 Another approach is to determine how flat the curve is to make good guesses
 about how far to move away in T before doing the intersection for the remainder
 and/or to determine whether one curve is to the inside or outside of another.
 According to Mike/Rob, the flatness for quadratics increases by 4 for each
 subdivision, and a crude guess of the curvature can be had by comparing P1 to
 (P0+P2)/2. By looking at the ULPS of the numbers, I can guess what value of
 T may be far enough that the curves diverge but don't cross.

 ====

 Code I May Not Need Any More

     static bool CoincidentCandidate(const Angle* current) {
         const Segment* segment = current->segment();
         int min = SkMin32(current->start(), current->end());
         do {
             const Span& span = segment->fTs[min];
             if (span.fCoincident == Span::kStart_Coincidence) {
                 return true;
             }
         } while (--min >= 0);
         return false;
     }

     static bool CoincidentHalf(const Angle* current, const Angle* next) {
         const Segment* other = next->segment();
         const Segment* segment = current->segment();
         int min = SkMin32(current->start(), current->end());
         const Span& minSpan = segment->fTs[min];
         if (minSpan.fOther == other) {
             return minSpan.fCoincident == Span::kStart_Coincidence;
         }
         int index = min;
         int spanCount = segment->fTs.count();
         while (++index < spanCount) {
             const Span& span = segment->fTs[index];
             if (minSpan.fT != span.fT) {
                 break;
             }
             if (span.fOther != other) {
                 continue;
             }
             return span.fCoincident == Span::kStart_Coincidence;
         }
         index = min;
         while (--index >= 0) {
             const Span& span = segment->fTs[index];
             if (span.fOther != other) {
                 continue;
             }
             return span.fCoincident == Span::kStart_Coincidence;
         }
         return false;
     }

     static bool Coincident(const Angle* current, const Angle* next) {
         return CoincidentHalf(current, next) &&
                 CoincidentHalf(next, current);
     }

     // If three lines cancel in a - b - c order, a - b may or may not
     // eliminate the edge that describes the b - c cancellation. Check done to
     // determine this.
     static bool CoincidentCancels(const Angle* current, const Angle* next) {
         int curMin = SkMin32(current->start(), current->end());
         if (current->segment()->fTs[curMin].fDone) {
             return false;
         }
         int nextMin = SkMin32(next->start(), next->end());
         if (next->segment()->fTs[nextMin].fDone) {
             return false;
         }
         return SkSign32(current->start() - current->end())
                 != SkSign32(next->start() - next->end());
     }

     // FIXME: at this point, just have two functions for the different steps
     int coincidentEnd(int from, int step) const {
         double fromT = fTs[from].fT;
         int count = fTs.count();
         int to = from;
         while (step > 0 ? ++to < count : --to >= 0) {
             const Span& span = fTs[to];
             if ((step > 0 ? span.fT - fromT : fromT - span.fT) >= FLT_EPSILON ) {
                 // FIXME: we assume that if the T changes, we don't care about
                 // coincident -- but in nextSpan, we require that both the T
                 // and actual loc change to represent a span. This asymettry may
                 // be OK or may be trouble -- if trouble, probably will need to
                 // detect coincidence earlier or sort differently
                 break;
             }
 #if 01
             if (span.fCoincident == (step < 0 ? Span::kStart_Coincidence :
                     Span::kEnd_Coincidence)) {
                 from = to;
             }
 #else
             from = to;
 #endif
         }
         return from;
     }

     // once past current span, if step>0, look for coicident==1
     // if step<0, look for coincident==-1
     int nextSpanEnd(int from, int step) const {
         int result = nextSpan(from, step);
         if (result < 0) {
             return result;
         }
         return coincidentEnd(result, step);
     }


     void adjustFirst(const SkTDArray<Angle*>& sorted, int& first, int& winding,
             bool outside) {
         int firstIndex = first;
         int angleCount = sorted.count();
         if (true || outside) {
             const Angle* angle = sorted[firstIndex];
             int prior = firstIndex;
             do {
                 if (--prior < 0) {
                     prior = angleCount - 1;
                 }
                 if (prior == firstIndex) { // all are coincident with each other
                     return;
                 }
                 if (!Coincident(sorted[prior], sorted[first])) {
                     return;
                 }
                 winding += angle->sign();
                 first = prior;
                 angle = sorted[prior];
                 winding -= angle->sign();
             } while (true);
         }
         do {
             int next = first + 1;
             if (next == angleCount) {
                 next = 0;
             }
             if (next == firstIndex) { // all are coincident with each other
                 return;
             }
             if (!Coincident(sorted[first], sorted[next])) {
                 return;
             }
             first = next;
         } while (true);
     }

             bool nextIsCoincident = CoincidentCandidate(nextAngle);
             bool finalOrNoCoincident = true;
             bool pairCoincides = false;
             bool pairCancels = false;
             if (nextIsCoincident) {
                 int followIndex = nextIndex + 1;
                 if (followIndex == angleCount) {
                     followIndex = 0;
                 }
                 const Angle* followAngle = sorted[followIndex];
                 finalOrNoCoincident = !Coincident(nextAngle, followAngle);
                 if ((pairCoincides = Coincident(angle, nextAngle))) {
                     pairCancels = CoincidentCancels(angle, nextAngle);
                 }
             }
             if (pairCancels && !foundAngle && !nextSegment->done()) {
                 Segment* aSeg = angle->segment();
       //          alreadyMarked |= aSeg == sorted[firstIndex]->segment();
                 aSeg->markAndChaseCoincident(angle->start(), angle->end(),
                         nextSegment);
                 if (firstEdge) {
                     return NULL;
                 }
             }
             if (pairCoincides) {
                 if (pairCancels) {
                     goto doNext;
                 }
                 int minT = SkMin32(nextAngle->start(), nextAngle->end());
                 bool markNext = abs(maxWinding) < abs(winding);
                 if (markNext) {
                     nextSegment->markDone(minT, winding);
                 }
                 int oldMinT = SkMin32(angle->start(), angle->end());
                 if (true || !foundAngle) {
                  //   SkASSERT(0); // do we ever get here?
                     Segment* aSeg = angle->segment();
         //            alreadyMarked |= aSeg == sorted[firstIndex]->segment();
                     aSeg->markDone(oldMinT, maxWinding);
                 }
             }

     // OPTIMIZATION: uses tail recursion. Unwise?
     void innerCoincidentChase(int step, Segment* other) {
         // find other at index
    //     SkASSERT(!done());
         const Span* start = NULL;
         const Span* end = NULL;
         int index, startIndex, endIndex;
         int count = fTs.count();
         for (index = 0; index < count; ++index) {
             const Span& span = fTs[index];
             if (!span.fCoincident || span.fOther != other) {
                 continue;
             }
             if (!start) {
                 startIndex = index;
                 start = &span;
             } else {
                 SkASSERT(!end);
                 endIndex = index;
                 end = &span;
             }
         }
         if (!end) {
             return;
         }
         bool thisDone = fTs[SkMin32(startIndex, endIndex)].fDone;
         bool otherDone = other->fTs[SkMin32(start->fOtherIndex,
                 end->fOtherIndex)].fDone;
         if (thisDone && otherDone) {
             return;
         }
         Segment* next;
         Segment* nextOther;
         if (step < 0) {
             next = start->fT == 0 ? NULL : this;
             nextOther = other->fTs[start->fOtherIndex].fT > 1 - FLT_EPSILON ? NULL : other;
         } else {
             next = end->fT == 1 ? NULL : this;
             nextOther = other->fTs[end->fOtherIndex].fT < FLT_EPSILON ? NULL : other;
         }
         SkASSERT(!next || !nextOther);
         for (index = 0; index < count; ++index) {
             const Span& span = fTs[index];
             if (span.fCoincident || span.fOther == other) {
                 continue;
             }
             bool checkNext = !next && (step < 0 ? span.fT < FLT_EPSILON
                 && span.fOtherT > 1 - FLT_EPSILON : span.fT > 1 - FLT_EPSILON
                 && span.fOtherT < FLT_EPSILON);
             bool checkOther = !nextOther && (step < 0 ? fabs(span.fT - start->fT) < FLT_EPSILON
                 && span.fOtherT < FLT_EPSILON : fabs(span.fT - end->fT) < FLT_EPSILON
                 && span.fOtherT > 1 - FLT_EPSILON);
             if (!checkNext && !checkOther) {
                 continue;
             }
             Segment* oSegment = span.fOther;
             if (oSegment->done()) {
                 continue;
             }
             int oCount = oSegment->fTs.count();
             for (int oIndex = 0; oIndex < oCount; ++oIndex) {
                 const Span& oSpan = oSegment->fTs[oIndex];
                 if (oSpan.fT >= FLT_EPSILON && oSpan.fT <= 1 - FLT_EPSILON) {
                     continue;
                 }
                 if (!oSpan.fCoincident) {
                     continue;
                 }
                 if (checkNext && (oSpan.fT < FLT_EPSILON ^ step < 0)) {
                     next = oSegment;
                     checkNext = false;
                 }
                 if (checkOther && (oSpan.fT > 1 - FLT_EPSILON ^ step < 0)) {
                     nextOther = oSegment;
                     checkOther = false;
                 }
             }
         }
         // this needs to walk both spans in lock step, skipping edges that
         // are already marked done on one or the other
         markCanceled(startIndex, endIndex);
         if (next && nextOther) {
             next->innerCoincidentChase(step, nextOther);
         }
     }

     // cancel coincident edges in lock step
     void markCanceled(int start, int end) {
         if (done()) {
             return;
         }
         Segment* other = fTs[start].fOther;
         if (other->done()) {
             return;
         }
         if (start > end) {
             SkTSwap<int>(start, end);
         }
         double maxT = fTs[end].fT - FLT_EPSILON;
         int spanCount = fTs.count();
         // since these cancel, this walks up and other walks down
         int oStart = fTs[start].fOtherIndex;
         double oStartT = other->fTs[oStart].fT;
         while (oStartT - other->fTs[--oStart].fT < FLT_EPSILON)
             ;
         double startT = fTs[start].fT;
         while (start > 0 && startT - fTs[start - 1].fT < FLT_EPSILON) {
             --start;
         }
         do {
             Span* span = &fTs[start];
             Span* oSpan = &other->fTs[oStart];
             // find start of each, and see if both are not done
             bool markDone = !span->fDone && !oSpan->fDone;
             double spanT = span->fT;
             do {
                 if (markDone) {
                     span->fCanceled = true;
                 #if DEBUG_MARK_DONE
                     const SkPoint& pt = xyAtT(span);
                     SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n",
                             __FUNCTION__, fID, start, span->fT, pt.fX, pt.fY);
                 #endif
                     SkASSERT(!span->fDone);
                     span->fDone = true;
                     span->fWinding = 0;
                     fDoneSpans++;
                 }
                 if (++start == spanCount) {
                     break;
                 }
                 span = &fTs[start];
             } while (span->fT - spanT < FLT_EPSILON);
             double oSpanT = oSpan->fT;
             do {
                 if (markDone) {
                     oSpan->fCanceled = true;
                 #if DEBUG_MARK_DONE
                     const SkPoint& oPt = xyAtT(oSpan);
                     SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n",
                             __FUNCTION__, other->fID, oStart, oSpan->fT,
                             oPt.fX, oPt.fY);
                 #endif
                     SkASSERT(!oSpan->fDone);
                     oSpan->fDone = true;
                     oSpan->fWinding = 0;
                     other->fDoneSpans++;
                 }
                 if (--oStart < 0) {
                     break;
                 }
                 oSpan = &other->fTs[oStart];
             } while (oSpanT - oSpan->fT < FLT_EPSILON);
         } while (fTs[start].fT <= maxT);
     }

     bool canceled(int start, int end) const {
         int min = SkMin32(start, end);
         return fTs[min].fCanceled;
     }

     void markAndChaseCoincident(int index, int endIndex, Segment* other) {
         int step = SkSign32(endIndex - index);
         innerCoincidentChase(step, other);
     }
	/*
	* Copyright 2012 Google Inc.
	*
	* Use of this source code is governed by a BSD-style license that can be
	* found in the LICENSE file.
	*/
	add unit test for quadratic horizontal intersection
	add unit test for cubic horizontal intersection with left/right
	add unit test for ActiveEdge::calcLeft (can currently loop forever)
	does ActiveEdge::isCoincidentWith need to support quad, cubic?
	figure out why variation in ActiveEdge::tooCloseToCall isn't better
	why does 'lastPtr - 2' in addIntersectingTs break testSimplifyTriangle22?
	add code to promote quad to cubic, or add quad/cubic intersection
	figure out why testSimplifySkinnyTriangle13 fails

	for quadratics and cubics, once various T values are added, see if consecutive
	Ts have ys that go up instead of down. If so, the edge needs to be broken.

	when splitting curves at inflection pts, should I retain the original curve
	data and note that the first/last T are no longer 0/1 ?
	I need to figure this out before I can proceed

	would it make sense to leave the InEdge alone, and add multiple copies of
	ActiveEdge, pointing to the same InEdge, where the copy has only the subset
	of Ts that need to be walked in reverse order?


	-- A Digression Which Shows Why Resolving Coincidence Does Not Make Sense --

	Consider the following fine ASCII art:

	+------>-------+ +------>-------+
	\| \| \| \|
	^ V ^ V
	\| \| \| \|
	+------<-------+ +------<-------+
	+------>-------+ +------<-------+
	\| \| \| \|
	^ V V ^
	\| \| \| \|
	+------<-------+ +------>-------+

	(assume the bottom and top of the stacked rectangles are coincident)

	Simplifying said rectangles, regardless of rectangle direction, and regardless
	of winding or even/odd, eliminates the coincident edge, i.e., the result is
	always:

	+------>-------+
	\| \|
	\| \|
	\| \|
	^ V
	\| \|
	\| \|
	\| \|
	+------<-------+

	But when the rectangles are enclosed in a larger rectangle:

	+-------->---------+ +-------->---------+
	\| +------>-------+ \| \| +------>-------+ \|
	\| \| \| \| \| \| \| \|
	\| ^ V \| \| ^ V \|
	\| \| \| \| \| \| \| \|
	\| +------<-------+ \| \| +------<-------+ \|
	\| +------>-------+ \| \| +------<-------+ \|
	\| \| \| \| \| \| \| \|
	\| ^ V \| \| V ^ \|
	\| \| \| \| \| \| \| \|
	\| +------<-------+ \| \| +------>-------+ \|
	+--------<---------+ +--------<---------+

	Simplifying them gives different results depending on the winding setting:

	winding:
	+-------->---------+ +-------->---------+
	\| \| \| \|
	\| \| \| \|
	\| \| \| \|
	\| \| \| \|
	\| \| \| +------<-------+ \|
	\| \| \| \| \| \|
	\| \| \| V ^ \|
	\| \| \| \| \| \|
	\| \| \| +------>-------+ \|
	+--------<---------+ +--------<---------+

	even odd:
	+-------->---------+ +-------->---------+
	\| +------<-------+ \| \| +------<-------+ \|
	\| \| \| \| \| \| \| \|
	\| \| \| \| \| \| \| \|
	\| \| \| \| \| \| \| \|
	\| \| \| \| \| \| \| \|
	\| V ^ \| \| V ^ \|
	\| \| \| \| \| \| \| \|
	\| \| \| \| \| \| \| \|
	\| \| \| \| \| \| \| \|
	\| +------>-------+ \| \| +------>-------+ \|
	+--------<---------+ +--------<---------+

	So, given the inner rectangles alone (e.g., given coincident pairs in some local
	context), we can't know whether to keep the coincident edges or not.


	-- Thoughts About Sortless Ops --

	I can't come up with anything truly sortless. It seems that the crossings need
	to be sorted to know which segment is next on the outside, although sometimes
	we can use that it is not coincident just to follow the direction.

	If it is coincident or if there's more than two crossing segments, sorting
	seems inevitable.

	Likewise, to resolve whether one contour is inside another, it seems that
	sorting is required. Given a pair of segments on different contours, to know
	if one is inside of the other, I need to know for each which side of the edge
	is the inside/filled side. When the outer contour is walked, it seems like I
	could record the inside info. I guess when the inner contour is found, its
	inside sense is reversed (inside is above the top). But how do I know if the
	next contour is inside another? Maybe shoot out a line and brute-force
	intersect it with all the segments in all the other contours? If every contour
	has an extra segment when the intersections are computed, this may not be as
	crazy as it seems.

	Suppose each contour has one extra segment shooting straight up from the top
	(or straight up from any point on the segment). This ray is not intersected
	with the home contour, but is intersected with all other contours as part of
	the normal intersection engine. If it is possible to get from the T values to
	the other segments to the other contours, it would be straightforward to
	count the contour crossings and determine if the home contour is in another
	contour or not (if the count is even, not, if odd, is inside). By itself that
	doesn't tell us about winding, but it's a start.


	Since intersecting these rays is unrelated to computing other intersections,
	it can be lazily done once the contour is found.

	So
	repeat the following
	find the top segment of all contours
	trace the outside, marking touching first and last segments as inside
	continue tracing the touched segments with reversed outside/inside sense
	once the edges are exhausted, remaining must be disjoint contours
	send a ray from a disjoint point through all other contours
	count the crossings, determine if disjoint is inside or outside, then continue

	===

	On Quadratic (and Cubic) Intersections

	Currently, if only the end points touch, QuadracticIntersections does a lot of
	work to figure that out. Can I test for that up front, then short circuit the
	recursive search for the end points?

	Or, is there something defective in the current approach that makes the end
	point recursion go so deep? I'm seeing 56 stack frames (about 28 divides, but
	thankfully, no splits) to find one matching endpoint.


	Bezier curve focus may allow more quickly determining that end points with
	identical tangents are practically coicident for some range of T, but I don't
	understand the math yet to know.

	Another approach is to determine how flat the curve is to make good guesses
	about how far to move away in T before doing the intersection for the remainder
	and/or to determine whether one curve is to the inside or outside of another.
	According to Mike/Rob, the flatness for quadratics increases by 4 for each
	subdivision, and a crude guess of the curvature can be had by comparing P1 to
	(P0+P2)/2. By looking at the ULPS of the numbers, I can guess what value of
	T may be far enough that the curves diverge but don't cross.

	====

	Code I May Not Need Any More

	static bool CoincidentCandidate(const Angle* current) {
	const Segment* segment = current->segment();
	int min = SkMin32(current->start(), current->end());
	do {
	const Span& span = segment->fTs[min];
	if (span.fCoincident == Span::kStart_Coincidence) {
	return true;
	}
	} while (--min >= 0);
	return false;
	}

	static bool CoincidentHalf(const Angle* current, const Angle* next) {
	const Segment* other = next->segment();
	const Segment* segment = current->segment();
	int min = SkMin32(current->start(), current->end());
	const Span& minSpan = segment->fTs[min];
	if (minSpan.fOther == other) {
	return minSpan.fCoincident == Span::kStart_Coincidence;
	}
	int index = min;
	int spanCount = segment->fTs.count();
	while (++index < spanCount) {
	const Span& span = segment->fTs[index];
	if (minSpan.fT != span.fT) {
	break;
	}
	if (span.fOther != other) {
	continue;
	}
	return span.fCoincident == Span::kStart_Coincidence;
	}
	index = min;
	while (--index >= 0) {
	const Span& span = segment->fTs[index];
	if (span.fOther != other) {
	continue;
	}
	return span.fCoincident == Span::kStart_Coincidence;
	}
	return false;
	}

	static bool Coincident(const Angle* current, const Angle* next) {
	return CoincidentHalf(current, next) &&
	CoincidentHalf(next, current);
	}

	// If three lines cancel in a - b - c order, a - b may or may not
	// eliminate the edge that describes the b - c cancellation. Check done to
	// determine this.
	static bool CoincidentCancels(const Angle* current, const Angle* next) {
	int curMin = SkMin32(current->start(), current->end());
	if (current->segment()->fTs[curMin].fDone) {
	return false;
	}
	int nextMin = SkMin32(next->start(), next->end());
	if (next->segment()->fTs[nextMin].fDone) {
	return false;
	}
	return SkSign32(current->start() - current->end())
	!= SkSign32(next->start() - next->end());
	}

	// FIXME: at this point, just have two functions for the different steps
	int coincidentEnd(int from, int step) const {
	double fromT = fTs[from].fT;
	int count = fTs.count();
	int to = from;
	while (step > 0 ? ++to < count : --to >= 0) {
	const Span& span = fTs[to];
	if ((step > 0 ? span.fT - fromT : fromT - span.fT) >= FLT_EPSILON ) {
	// FIXME: we assume that if the T changes, we don't care about
	// coincident -- but in nextSpan, we require that both the T
	// and actual loc change to represent a span. This asymettry may
	// be OK or may be trouble -- if trouble, probably will need to
	// detect coincidence earlier or sort differently
	break;
	}
	#if 01
	if (span.fCoincident == (step < 0 ? Span::kStart_Coincidence :
	Span::kEnd_Coincidence)) {
	from = to;
	}
	#else
	from = to;
	#endif
	}
	return from;
	}

	// once past current span, if step>0, look for coicident==1
	// if step<0, look for coincident==-1
	int nextSpanEnd(int from, int step) const {
	int result = nextSpan(from, step);
	if (result < 0) {
	return result;
	}
	return coincidentEnd(result, step);
	}


	void adjustFirst(const SkTDArray<Angle*>& sorted, int& first, int& winding,
	bool outside) {
	int firstIndex = first;
	int angleCount = sorted.count();
	if (true \|\| outside) {
	const Angle* angle = sorted[firstIndex];
	int prior = firstIndex;
	do {
	if (--prior < 0) {
	prior = angleCount - 1;
	}
	if (prior == firstIndex) { // all are coincident with each other
	return;
	}
	if (!Coincident(sorted[prior], sorted[first])) {
	return;
	}
	winding += angle->sign();
	first = prior;
	angle = sorted[prior];
	winding -= angle->sign();
	} while (true);
	}
	do {
	int next = first + 1;
	if (next == angleCount) {
	next = 0;
	}
	if (next == firstIndex) { // all are coincident with each other
	return;
	}
	if (!Coincident(sorted[first], sorted[next])) {
	return;
	}
	first = next;
	} while (true);
	}

	bool nextIsCoincident = CoincidentCandidate(nextAngle);
	bool finalOrNoCoincident = true;
	bool pairCoincides = false;
	bool pairCancels = false;
	if (nextIsCoincident) {
	int followIndex = nextIndex + 1;
	if (followIndex == angleCount) {
	followIndex = 0;
	}
	const Angle* followAngle = sorted[followIndex];
	finalOrNoCoincident = !Coincident(nextAngle, followAngle);
	if ((pairCoincides = Coincident(angle, nextAngle))) {
	pairCancels = CoincidentCancels(angle, nextAngle);
	}
	}
	if (pairCancels && !foundAngle && !nextSegment->done()) {
	Segment* aSeg = angle->segment();
	// alreadyMarked \|= aSeg == sorted[firstIndex]->segment();
	aSeg->markAndChaseCoincident(angle->start(), angle->end(),
	nextSegment);
	if (firstEdge) {
	return NULL;
	}
	}
	if (pairCoincides) {
	if (pairCancels) {
	goto doNext;
	}
	int minT = SkMin32(nextAngle->start(), nextAngle->end());
	bool markNext = abs(maxWinding) < abs(winding);
	if (markNext) {
	nextSegment->markDone(minT, winding);
	}
	int oldMinT = SkMin32(angle->start(), angle->end());
	if (true \|\| !foundAngle) {
	// SkASSERT(0); // do we ever get here?
	Segment* aSeg = angle->segment();
	// alreadyMarked \|= aSeg == sorted[firstIndex]->segment();
	aSeg->markDone(oldMinT, maxWinding);
	}
	}

	// OPTIMIZATION: uses tail recursion. Unwise?
	void innerCoincidentChase(int step, Segment* other) {
	// find other at index
	// SkASSERT(!done());
	const Span* start = NULL;
	const Span* end = NULL;
	int index, startIndex, endIndex;
	int count = fTs.count();
	for (index = 0; index < count; ++index) {
	const Span& span = fTs[index];
	if (!span.fCoincident \|\| span.fOther != other) {
	continue;
	}
	if (!start) {
	startIndex = index;
	start = &span;
	} else {
	SkASSERT(!end);
	endIndex = index;
	end = &span;
	}
	}
	if (!end) {
	return;
	}
	bool thisDone = fTs[SkMin32(startIndex, endIndex)].fDone;
	bool otherDone = other->fTs[SkMin32(start->fOtherIndex,
	end->fOtherIndex)].fDone;
	if (thisDone && otherDone) {
	return;
	}
	Segment* next;
	Segment* nextOther;
	if (step < 0) {
	next = start->fT == 0 ? NULL : this;
	nextOther = other->fTs[start->fOtherIndex].fT > 1 - FLT_EPSILON ? NULL : other;
	} else {
	next = end->fT == 1 ? NULL : this;
	nextOther = other->fTs[end->fOtherIndex].fT < FLT_EPSILON ? NULL : other;
	}
	SkASSERT(!next \|\| !nextOther);
	for (index = 0; index < count; ++index) {
	const Span& span = fTs[index];
	if (span.fCoincident \|\| span.fOther == other) {
	continue;
	}
	bool checkNext = !next && (step < 0 ? span.fT < FLT_EPSILON
	&& span.fOtherT > 1 - FLT_EPSILON : span.fT > 1 - FLT_EPSILON
	&& span.fOtherT < FLT_EPSILON);
	bool checkOther = !nextOther && (step < 0 ? fabs(span.fT - start->fT) < FLT_EPSILON
	&& span.fOtherT < FLT_EPSILON : fabs(span.fT - end->fT) < FLT_EPSILON
	&& span.fOtherT > 1 - FLT_EPSILON);
	if (!checkNext && !checkOther) {
	continue;
	}
	Segment* oSegment = span.fOther;
	if (oSegment->done()) {
	continue;
	}
	int oCount = oSegment->fTs.count();
	for (int oIndex = 0; oIndex < oCount; ++oIndex) {
	const Span& oSpan = oSegment->fTs[oIndex];
	if (oSpan.fT >= FLT_EPSILON && oSpan.fT <= 1 - FLT_EPSILON) {
	continue;
	}
	if (!oSpan.fCoincident) {
	continue;
	}
	if (checkNext && (oSpan.fT < FLT_EPSILON ^ step < 0)) {
	next = oSegment;
	checkNext = false;
	}
	if (checkOther && (oSpan.fT > 1 - FLT_EPSILON ^ step < 0)) {
	nextOther = oSegment;
	checkOther = false;
	}
	}
	}
	// this needs to walk both spans in lock step, skipping edges that
	// are already marked done on one or the other
	markCanceled(startIndex, endIndex);
	if (next && nextOther) {
	next->innerCoincidentChase(step, nextOther);
	}
	}

	// cancel coincident edges in lock step
	void markCanceled(int start, int end) {
	if (done()) {
	return;
	}
	Segment* other = fTs[start].fOther;
	if (other->done()) {
	return;
	}
	if (start > end) {
	SkTSwap<int>(start, end);
	}
	double maxT = fTs[end].fT - FLT_EPSILON;
	int spanCount = fTs.count();
	// since these cancel, this walks up and other walks down
	int oStart = fTs[start].fOtherIndex;
	double oStartT = other->fTs[oStart].fT;
	while (oStartT - other->fTs[--oStart].fT < FLT_EPSILON)
	;
	double startT = fTs[start].fT;
	while (start > 0 && startT - fTs[start - 1].fT < FLT_EPSILON) {
	--start;
	}
	do {
	Span* span = &fTs[start];
	Span* oSpan = &other->fTs[oStart];
	// find start of each, and see if both are not done
	bool markDone = !span->fDone && !oSpan->fDone;
	double spanT = span->fT;
	do {
	if (markDone) {
	span->fCanceled = true;
	#if DEBUG_MARK_DONE
	const SkPoint& pt = xyAtT(span);
	SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n",
	__FUNCTION__, fID, start, span->fT, pt.fX, pt.fY);
	#endif
	SkASSERT(!span->fDone);
	span->fDone = true;
	span->fWinding = 0;
	fDoneSpans++;
	}
	if (++start == spanCount) {
	break;
	}
	span = &fTs[start];
	} while (span->fT - spanT < FLT_EPSILON);
	double oSpanT = oSpan->fT;
	do {
	if (markDone) {
	oSpan->fCanceled = true;
	#if DEBUG_MARK_DONE
	const SkPoint& oPt = xyAtT(oSpan);
	SkDebugf("%s segment=%d index=%d t=%1.9g pt=(%1.9g,%1.9g)\n",
	__FUNCTION__, other->fID, oStart, oSpan->fT,
	oPt.fX, oPt.fY);
	#endif
	SkASSERT(!oSpan->fDone);
	oSpan->fDone = true;
	oSpan->fWinding = 0;
	other->fDoneSpans++;
	}
	if (--oStart < 0) {
	break;
	}
	oSpan = &other->fTs[oStart];
	} while (oSpanT - oSpan->fT < FLT_EPSILON);
	} while (fTs[start].fT <= maxT);
	}

	bool canceled(int start, int end) const {
	int min = SkMin32(start, end);
	return fTs[min].fCanceled;
	}

	void markAndChaseCoincident(int index, int endIndex, Segment* other) {
	int step = SkSign32(endIndex - index);
	innerCoincidentChase(step, other);
	}