pathops version two

R=reed@google.com

marked 'no commit' to attempt to get trybots to run

TBR=reed@google.com

Review URL: https://codereview.chromium.org/1002693002

1 files changed, 388 insertions, 0 deletions

diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
new file mode 100755
index 0000000000..45eee0a38e
--- /dev/null
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -0,0 +1,388 @@
+/*
+ * Copyright 2015 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 "SkOpSegment.h"
+#include "SkPathOpsTSect.h"
+
+void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
+        SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
+    SkASSERT(coinPtTStart->fT < coinPtTEnd->fT);
+    bool flipped = oppPtTStart->fT > oppPtTEnd->fT;
+    SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator);
+    coinRec->fNext = this->fHead;
+    coinRec->fCoinPtTStart = coinPtTStart;
+    coinRec->fCoinPtTEnd = coinPtTEnd;
+    coinRec->fOppPtTStart = oppPtTStart;
+    coinRec->fOppPtTEnd = oppPtTEnd;
+    coinRec->fFlipped = flipped;
+    this->fHead = coinRec;
+}
+
+static void tRange(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
+        const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
+    double denom = overE->fT - overS->fT;
+    double start = 0 < denom ? tStart : tEnd;
+    double end = 0 < denom ? tEnd : tStart;
+    double sRatio = (start - overS->fT) / denom;
+    double eRatio = (end - overS->fT) / denom;
+    *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
+    *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
+}
+
+bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
+                      const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
+        SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
+        SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
+    double coinTs, coinTe, oppTs, oppTe;
+    tRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
+    tRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
+    SkOpSegment* coinSeg = coinPtTStart->segment();
+    SkOpSegment* oppSeg = oppPtTStart->segment();
+    SkASSERT(coinSeg != oppSeg);
+    SkCoincidentSpans* check = this->fHead;
+    do {
+        const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
+        if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
+            continue;
+        }
+        const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment();
+        if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
+            continue;
+        }
+        int cTs = coinTs;
+        int cTe = coinTe;
+        int oTs = oppTs;
+        int oTe = oppTe;
+        if (checkCoinSeg != coinSeg) {
+            SkASSERT(checkOppSeg != oppSeg);
+            SkTSwap(cTs, oTs);
+            SkTSwap(cTe, oTe);
+        }
+        int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
+                       + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
+                       + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
+                       + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
+//        SkASSERT(tweenCount == 0 || tweenCount == 4);
+        if (tweenCount) {
+            return true;
+        }
+    } while ((check = check->fNext));
+    if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
+        SkTSwap(oppTs, oppTe);
+    }
+    if (coinTs > coinTe) {
+        SkTSwap(coinTs, coinTe);
+        SkTSwap(oppTs, oppTe);
+    }
+    SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator);
+    SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator);
+    if (cs == ce) {
+        return false;
+    }
+    SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator);
+    SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator);
+    SkASSERT(os != oe);
+    cs->addOpp(os);
+    ce->addOpp(oe);
+    this->add(cs, ce, os, oe, allocator);
+    return true;
+}
+
+bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) {
+    SkCoincidentSpans* outer = this->fHead;
+    if (!outer) {
+        return true;
+    }
+    do {
+        SkCoincidentSpans* inner = outer;
+        while ((inner = inner->fNext)) {
+            double overS, overE;
+            if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
+                if (!addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
+                        outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
+                    return false;
+                }
+            } else if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
+                if (!addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
+                        outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
+                    return false;
+                }
+            } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
+                    inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
+                if (!addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
+                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) {
+                    return false;
+                }
+            } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
+                    inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
+                if (!addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
+                        inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
+                        outer->fCoinPtTStart, outer->fCoinPtTEnd,
+                        inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) {
+                    return false;
+                }
+            }
+        }
+
+    } while ((outer = outer->fNext));
+    return true;
+}
+
+
+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
+bool SkOpCoincidence::apply() {
+    SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return true;
+    }
+    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();
+            if (!oNext) {
+                return false;
+            }
+            if (!oNext->upCastable()) {
+                return false;
+            }
+            oStart = oNext->upCast();
+        } while (true);
+    } while ((coin = coin->fNext));
+    return true;
+}
+
+void SkOpCoincidence::detach(SkCoincidentSpans* remove) {
+    SkCoincidentSpans* coin = fHead;
+    SkCoincidentSpans* prev = NULL;
+    SkCoincidentSpans* next;
+    do {
+        next = coin->fNext;
+        if (coin == remove) {
+            if (prev) {
+                prev->fNext = next;
+            } else {
+                fHead = next;
+            }
+            break;
+        }
+        prev = coin;
+    } while ((coin = next));
+    SkASSERT(coin);
+}
+
+void SkOpCoincidence::expand() {
+    SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return;
+    }
+    do {
+        SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
+        SkOpSpanBase* end = coin->fCoinPtTEnd->span();
+        SkOpSegment* segment = coin->fCoinPtTStart->segment();
+        SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
+        SkOpSpan* prev = start->prev();
+        SkOpPtT* oppPtT;
+        if (prev && (oppPtT = prev->contains(oppSegment))) {
+            double midT = (prev->t() + start->t()) / 2;
+            if (segment->isClose(midT, oppSegment)) {
+                coin->fCoinPtTStart = prev->ptT();
+                coin->fOppPtTStart = oppPtT;
+            }
+        }
+        SkOpSpanBase* next = end->final() ? NULL : end->upCast()->next();
+        if (next && (oppPtT = next->contains(oppSegment))) {
+            double midT = (end->t() + next->t()) / 2;
+            if (segment->isClose(midT, oppSegment)) {
+                coin->fCoinPtTEnd = next->ptT();
+                coin->fOppPtTEnd = oppPtT;
+            }
+        }
+    } while ((coin = coin->fNext));
+}
+
+void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) {
+    SkCoincidentSpans* coin = fHead;
+    if (!coin) {
+        return;
+    }
+    do {
+        if (coin->fCoinPtTStart == deleted) {
+            if (coin->fCoinPtTEnd->span() == kept->span()) {
+                return this->detach(coin);
+            }
+            coin->fCoinPtTStart = kept;
+        }
+        if (coin->fCoinPtTEnd == deleted) {
+            if (coin->fCoinPtTStart->span() == kept->span()) {
+                return this->detach(coin);
+            }
+            coin->fCoinPtTEnd = kept;
+        }
+        if (coin->fOppPtTStart == deleted) {
+            if (coin->fOppPtTEnd->span() == kept->span()) {
+                return this->detach(coin);
+            }
+            coin->fOppPtTStart = kept;
+        }
+        if (coin->fOppPtTEnd == deleted) {
+            if (coin->fOppPtTStart->span() == kept->span()) {
+                return this->detach(coin);
+            }
+            coin->fOppPtTEnd = kept;
+        }
+    } 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;
+        // check to see if coincident span could be bigger
+
+        do {
+            next = next->upCast()->next();
+            oNext = flipped ? oNext->prev() : oNext->upCast()->next();
+            if (next == end || 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));
+}
+
+bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 
+        const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
+    if (coin1s->segment() != coin2s->segment()) {
+        return false;
+    }
+    *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
+    *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
+    return *overS < *overE;
+}