remove prototype pathops code

experimental/Intersection/thingsToDo.txt

Index: experimental/Intersection/thingsToDo.txt
diff --git a/experimental/Intersection/thingsToDo.txt b/experimental/Intersection/thingsToDo.txt
deleted file mode 100644
index f74d3ee1268f9fede56b2b8225809fcb5a47ff32..0000000000000000000000000000000000000000
--- a/experimental/Intersection/thingsToDo.txt
+++ /dev/null
@@ -1,525 +0,0 @@
-/*
- * 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);
-    }
-