new files for pathops geometric intersection

src/pathops/SkPathOpsPostSect.cpp

Index: src/pathops/SkPathOpsPostSect.cpp
diff --git a/src/pathops/SkPathOpsPostSect.cpp b/src/pathops/SkPathOpsPostSect.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..15a1900ce3b1ad48a8a62768d5564379873cda51
--- /dev/null
+++ b/src/pathops/SkPathOpsPostSect.cpp
@@ -0,0 +1,502 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+#include "SkOpCoincidence.h"
+#include "SkOpContour.h"
+#include "SkOpSegment.h"
+#include "SkPathWriter.h"
+
+bool SkOpPtT::alias() const {
+    return this->span()->ptT() != this;
+}
+
+SkOpContour* SkOpPtT::contour() const {
+    return segment()->contour();
+}
+
+SkOpDebugState* SkOpPtT::debugState() const {
+    return PATH_OPS_DEBUG_RELEASE(contour()->debugState(), NULL); 
+}
+
+void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
+    fT = t;
+    fPt = pt;
+    fSpan = span;
+    fNext = this;
+    fDuplicatePt = duplicate;
+    fDeleted = false;
+    PATH_OPS_DEBUG_CODE(fID = ++span->debugState()->fPtTID);
+}
+
+bool SkOpPtT::onEnd() const {
+    const SkOpSpanBase* span = this->span();
+    if (span->ptT() != this) {
+        return false;
+    }
+    const SkOpSegment* segment = this->segment();
+    return span == segment->head() || span == segment->tail();
+}
+
+SkOpPtT* SkOpPtT::remove() {
+    SkOpPtT* prev = this;
+    do {
+        SkOpPtT* next = prev->fNext;
+        if (next == this) {
+            prev->removeNext();
+            fDeleted = true;
+            return prev;
+        }
+        prev = next;
+    } while (prev != this);
+    SkASSERT(0);
+    return NULL;
+}
+
+void SkOpPtT::removeNext() {
+    SkASSERT(this->fNext);
+    SkOpPtT* next = this->fNext;
+    this->fNext = next->fNext;
+    SkOpSpanBase* span = next->span();
+    next->setDeleted();
+    if (span->ptT() == next) {
+        span->upCast()->detach();
+    }
+}
+
+const SkOpSegment* SkOpPtT::segment() const {
+    return span()->segment();
+}
+
+SkOpSegment* SkOpPtT::segment() {
+    return span()->segment();
+}
+
+// find the starting or ending span with an existing loop of angles
+// OPTIMIZE? remove the spans pointing to windValue==0 here or earlier?
+// FIXME? assert that only one other span has a valid windValue or oppValue
+void SkOpSpanBase::addSimpleAngle(bool checkFrom, SkChunkAlloc* allocator) {
+    SkOpAngle* angle;
+    if (checkFrom) {
+        SkASSERT(this->final());
+        if (this->fromAngle()) {
+            SkASSERT(this->fromAngle()->loopCount() == 2);
+            return;
+        }
+        angle = this->segment()->addEndSpan(allocator);
+    } else {
+        SkASSERT(this->t() == 0);
+        SkOpSpan* span = this->upCast();
+        if (span->toAngle()) {
+            SkASSERT(span->toAngle()->loopCount() == 2);
+            SkASSERT(!span->fromAngle());
+            span->setFromAngle(span->toAngle()->next());
+            return;
+        }
+        angle = this->segment()->addStartSpan(allocator);
+    }
+    SkOpPtT* ptT = this->ptT();
+    SkOpSpanBase* oSpanBase;
+    SkOpSpan* oSpan;
+    SkOpSegment* other;
+    do {
+        ptT = ptT->next();
+        oSpanBase = ptT->span();
+        oSpan = oSpanBase->upCastable();
+        other = oSpanBase->segment();
+        if (oSpan && oSpan->windValue()) {
+            break;
+        }
+        if (oSpanBase->t() == 0) {
+            continue;
+        }
+        SkOpSpan* oFromSpan = oSpanBase->prev();
+        SkASSERT(oFromSpan->t() < 1);
+        if (oFromSpan->windValue()) {
+            break;
+        }
+    } while (ptT != this->ptT());
+    SkOpAngle* oAngle;
+    if (checkFrom) {
+        oAngle = other->addStartSpan(allocator);
+        SkASSERT(oSpan && !oSpan->final());
+        SkASSERT(oAngle == oSpan->toAngle());
+    } else {
+        oAngle = other->addEndSpan(allocator);
+        SkASSERT(oAngle == oSpanBase->fromAngle());
+    }
+    angle->insert(oAngle);
+}
+
+void SkOpSpanBase::align() {
+    if (this->fAligned) {
+        return;
+    }
+    SkASSERT(!zero_or_one(this->fPtT.fT));
+    SkASSERT(this->fPtT.next());
+    // if a linked pt/t pair has a t of zero or one, use it as the base for alignment
+    SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
+    while ((ptT = ptT->next()) != stopPtT) {
+        if (zero_or_one(ptT->fT)) {
+            SkOpSegment* segment = ptT->segment();
+            SkASSERT(this->segment() != segment);
+            SkASSERT(segment->head()->ptT() == ptT || segment->tail()->ptT() == ptT);
+            if (ptT->fT) {
+                segment->tail()->alignEnd(1, segment->lastPt());
+            } else {
+                segment->head()->alignEnd(0, segment->pts()[0]);
+            }
+            return;
+        }
+    }
+    alignInner();
+    this->fAligned = true;
+}
+
+
+// FIXME: delete spans that collapse
+// delete segments that collapse
+// delete contours that collapse
+void SkOpSpanBase::alignEnd(double t, const SkPoint& pt) {
+    SkASSERT(zero_or_one(t));
+    SkOpSegment* segment = this->segment();
+    SkASSERT(t ? segment->lastPt() == pt : segment->pts()[0] == pt);
+    alignInner();
+    *segment->writablePt(!!t) = pt;
+    SkOpPtT* ptT = &this->fPtT;
+    SkASSERT(t == ptT->fT);
+    SkASSERT(pt == ptT->fPt);
+    SkOpPtT* test = ptT, * stopPtT = ptT;
+    while ((test = test->next()) != stopPtT) {
+        SkOpSegment* other = test->segment();
+        if (other == this->segment()) {
+            continue;
+        }
+        if (!zero_or_one(test->fT)) {
+            continue;
+        }
+        *other->writablePt(!!test->fT) = pt;
+    }
+    this->fAligned = true;
+}
+
+void SkOpSpanBase::alignInner() {
+    // force the spans to share points and t values
+    SkOpPtT* ptT = &this->fPtT, * stopPtT = ptT;
+    const SkPoint& pt = ptT->fPt;
+    do {
+        ptT->fPt = pt;
+        const SkOpSpanBase* span = ptT->span();
+        SkOpPtT* test = ptT;
+        do {
+            SkOpPtT* prev = test;
+            if ((test = test->next()) == stopPtT) {
+                break;
+            }
+            if (span == test->span() && !span->segment()->ptsDisjoint(*ptT, *test)) {
+                // omit aliases that alignment makes redundant
+                if ((!ptT->alias() || test->alias()) && (ptT->onEnd() || !test->onEnd())) {
+                    SkASSERT(test->alias());
+                    prev->removeNext();
+                    test = prev;
+                } else {
+                    SkASSERT(ptT->alias());
+                    stopPtT = ptT = ptT->remove();
+                    break;
+                }
+            }
+        } while (true);
+    } while ((ptT = ptT->next()) != stopPtT);
+}
+
+bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
+    const SkOpPtT* start = &fPtT;
+    const SkOpPtT* check = &span->fPtT;
+    SkASSERT(start != check);
+    const SkOpPtT* walk = start;
+    while ((walk = walk->next()) != start) {
+        if (walk == check) {
+            return true;
+        }
+    }
+    return false;
+}
+
+bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
+    SkASSERT(this->segment() != segment);
+    const SkOpSpanBase* next = this;
+    while ((next = next->fCoinEnd) != this) {
+        if (next->segment() == segment) {
+            return true;
+        }
+    }
+    return false;
+}
+
+SkOpContour* SkOpSpanBase::contour() const {
+    return segment()->contour();
+}
+
+SkOpDebugState* SkOpSpanBase::debugState() const {
+    return PATH_OPS_DEBUG_RELEASE(contour()->debugState(), NULL); 
+}
+
+void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
+    fSegment = segment;
+    fPtT.init(this, t, pt, false);
+    fCoinEnd = this;
+    fFromAngle = NULL;
+    fPrev = prev;
+    fAligned = true;
+    fChased = false;
+    PATH_OPS_DEBUG_CODE(fCount = 1);
+    PATH_OPS_DEBUG_CODE(fID = ++debugState()->fSpanID);
+}
+
+// this pair of spans share a common t value or point; merge them and eliminate duplicates
+// this does not compute the best t or pt value; this merely moves all data into a single list
+void SkOpSpanBase::merge(SkOpSpan* span) {
+    SkOpPtT* spanPtT = span->ptT();
+    SkASSERT(this->t() != spanPtT->fT);
+    SkASSERT(!zero_or_one(spanPtT->fT));
+    span->detach();
+    SkOpPtT* remainder = spanPtT->next();
+    ptT()->insert(spanPtT);
+    while (remainder != spanPtT) {
+        SkOpPtT* next = remainder->next();
+        SkOpPtT* compare = spanPtT->next();
+        while (compare != spanPtT) {
+            SkOpPtT* nextC = compare->next();
+            if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
+                goto tryNextRemainder;
+            }
+            compare = nextC;
+        }
+        spanPtT->insert(remainder);
+tryNextRemainder:
+        remainder = next;
+    }
+}
+
+void SkOpSpanBase::mergeBaseAttributes(SkOpSpanBase* span) {
+    SkASSERT(!span->fChased);
+    SkASSERT(!span->fFromAngle);
+    if (this->upCastable() && span->upCastable()) {
+        this->upCast()->mergeAttributes(span->upCast());
+    }
+}
+
+void SkOpSpan::applyCoincidence(SkOpSpan* opp) {
+    SkASSERT(!final());
+    SkASSERT(0);  // incomplete
+}
+
+bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
+    SkASSERT(this->segment() != segment);
+    const SkOpSpan* next = this;
+    while ((next = next->fCoincident) != this) {
+        if (next->segment() == segment) {
+            return true;
+        }
+    }
+    return false;
+}
+
+void SkOpSpan::detach() {
+    SkASSERT(!final());
+    SkOpSpan* prev = this->prev();
+    SkASSERT(prev);
+    SkOpSpanBase* next = this->next();
+    SkASSERT(next);
+    prev->setNext(next);
+    next->setPrev(prev);
+    this->segment()->detach(this);
+    this->ptT()->setDeleted();
+}
+
+void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
+    SkASSERT(t != 1);
+    initBase(segment, prev, t, pt);
+    fCoincident = this;
+    fToAngle = NULL;
+    fWindSum = fOppSum = SK_MinS32;
+    fWindValue = 1;
+    fOppValue = 0;
+    fChased = fDone = false;
+    segment->bumpCount();
+}
+
+void SkOpSpan::mergeAttributes(SkOpSpan* span) {
+    SkASSERT(!span->fToAngle);
+    if (span->fCoincident) {
+        this->insertCoincidence(span);
+    }
+}
+
+void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
+        SkOpPtT* oppPtTEnd, bool flipped, SkChunkAlloc* allocator) {
+    SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator);
+    SkOpSpanBase* coinEnd = coinPtTEnd->span();
+    SkOpSpanBase* oppEnd = oppPtTEnd->span();
+    SkOpSpan* coinStart = coinPtTStart->span()->upCast();
+    SkASSERT(coinStart == coinStart->starter(coinEnd));
+    SkOpSpan* oppStart = (flipped ? oppPtTEnd : oppPtTStart)->span()->upCast();
+    SkASSERT(oppStart == oppStart->starter(oppEnd));
+    coinStart->insertCoincidence(oppStart);
+    coinEnd->insertCoinEnd(oppEnd);
+    coinRec->fNext = this->fHead;
+    coinRec->fCoinPtTStart = coinPtTStart;
+    coinRec->fCoinPtTEnd = coinPtTEnd;
+    coinRec->fOppPtTStart = oppPtTStart;
+    coinRec->fOppPtTEnd = oppPtTEnd;
+    coinRec->fFlipped = flipped;
+    this->fHead = coinRec;
+}
+
+bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
+        SkOpPtT* oppPtTEnd, bool flipped) {
+    SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return false;
+    }
+    do {
+        if (coin->fCoinPtTStart == coinPtTStart &&  coin->fCoinPtTEnd == coinPtTEnd
+                && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd
+                && coin->fFlipped == flipped) {
+            return true;
+        }
+    } while ((coin = coin->fNext));
+    return false;
+}
+
+// walk span sets in parallel, moving winding from one to the other
+void SkOpCoincidence::apply() {
+    SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return;
+    }
+    do {
+        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
+        SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
+        SkASSERT(start == start->starter(end));
+        bool flipped = coin->fFlipped;
+        SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span();
+        SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast();
+        SkASSERT(oStart == oStart->starter(oEnd));
+        SkOpSegment* segment = start->segment();
+        SkOpSegment* oSegment = oStart->segment();
+        bool operandSwap = segment->operand() != oSegment->operand();
+        if (flipped) {
+            do {
+                SkOpSpanBase* oNext = oStart->next();
+                if (oNext == oEnd) {
+                    break;
+                }
+                oStart = oNext->upCast();
+            } while (true);
+        }
+        bool isXor = segment->isXor();
+        bool oppXor = oSegment->isXor();
+        do {
+            int windValue = start->windValue();
+            int oWindValue = oStart->windValue();
+            int oppValue = start->oppValue();
+            int oOppValue = oStart->oppValue();
+            // winding values are added or subtracted depending on direction and wind type
+            // same or opposite values are summed depending on the operand value
+            if (windValue >= oWindValue) {
+                if (operandSwap) {
+                    SkTSwap(oWindValue, oOppValue);
+                }
+                if (flipped) {
+                    windValue -= oWindValue;
+                    oppValue -= oOppValue;
+                } else {
+                    windValue += oWindValue;
+                    oppValue += oOppValue;
+                }
+                if (isXor) {
+                    windValue &= 1;
+                }
+                if (oppXor) {
+                    oppValue &= 1;
+                }
+                oWindValue = oOppValue = 0;
+            } else {
+                if (operandSwap) {
+                    SkTSwap(windValue, oppValue);
+                }
+                if (flipped) {
+                    oWindValue -= windValue;
+                    oOppValue -= oppValue;
+                } else {
+                    oWindValue += windValue;
+                    oOppValue += oppValue;
+                }
+                if (isXor) {
+                    oOppValue &= 1;
+                }
+                if (oppXor) {
+                    oWindValue &= 1;
+                }
+                windValue = oppValue = 0;
+            }
+            start->setWindValue(windValue);
+            start->setOppValue(oppValue);
+            oStart->setWindValue(oWindValue);
+            oStart->setOppValue(oOppValue);
+            if (!windValue && !oppValue) {
+                segment->markDone(start);
+            }
+            if (!oWindValue && !oOppValue) {
+                oSegment->markDone(oStart);
+            }
+            SkOpSpanBase* next = start->next();
+            SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
+            if (next == end) {
+                break;
+            }
+            start = next->upCast();
+            oStart = oNext->upCast();
+        } while (true);
+    } while ((coin = coin->fNext));
+}
+
+void SkOpCoincidence::mark() {
+    SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return;
+    }
+    do {
+        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
+        SkOpSpanBase* oldEnd = end;
+        SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end);
+        SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
+        SkOpSpanBase* oOldEnd = oEnd;
+        SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd);
+        bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
+        if (flipped) {
+            SkTSwap(oStart, oEnd);
+        }
+        SkOpSpanBase* next = start;
+        SkOpSpanBase* oNext = oStart;
+        do {
+            next = next->upCast()->next();
+            oNext = flipped ? oNext->prev() : oNext->upCast()->next();
+            if (next == end) {
+                SkASSERT(oNext == oEnd);
+                break;
+            }
+            if (!next->containsCoinEnd(oNext)) {
+                next->insertCoinEnd(oNext);
+            }
+            SkOpSpan* nextSpan = next->upCast();
+            SkOpSpan* oNextSpan = oNext->upCast();
+            if (!nextSpan->containsCoincidence(oNextSpan)) {
+                nextSpan->insertCoincidence(oNextSpan);
+            }
+        } while (true);
+    } while ((coin = coin->fNext));
+}