cumulative pathops patch

src/pathops/SkOpSpan.cpp

 /*
  * 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); 
+SkOpGlobalState* SkOpPtT::globalState() const {
+    return contour()->globalState(); 
 }
 
 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);
+    PATH_OPS_DEBUG_CODE(fID = span->globalState()->nextPtTID());
 }
 
 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::prev() {
+    SkOpPtT* result = this;
+    SkOpPtT* next = this;
+    while ((next = next->fNext) != this) {
+        result = next;
+    }
+    SkASSERT(result->fNext == this);
+    return result;
+}
+
 SkOpPtT* SkOpPtT::remove() {
     SkOpPtT* prev = this;
     do {
         SkOpPtT* next = prev->fNext;
         if (next == this) {
-            prev->removeNext();
+            prev->removeNext(this);
+            SkASSERT(prev->fNext != prev);
             fDeleted = true;
             return prev;
         }
         prev = next;
     } while (prev != this);
     SkASSERT(0);
     return NULL;
 }
 
-void SkOpPtT::removeNext() {
+void SkOpPtT::removeNext(SkOpPtT* kept) {
     SkASSERT(this->fNext);
     SkOpPtT* next = this->fNext;
+    SkASSERT(this != next->fNext);
     this->fNext = next->fNext;
     SkOpSpanBase* span = next->span();
     next->setDeleted();
     if (span->ptT() == next) {
-        span->upCast()->detach();
+        span->upCast()->detach(kept);
     }
 }
 
 const SkOpSegment* SkOpPtT::segment() const {
     return span()->segment();
 }
 
 SkOpSegment* SkOpPtT::segment() {
     return span()->segment();
 }
@@ skipping 116 matching lines @@
         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();
+                    prev->removeNext(ptT);
                     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;
 }
 
+SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) {
+    SkOpPtT* start = &fPtT;
+    SkOpPtT* walk = start;
+    while ((walk = walk->next()) != start) {
+        if (walk->segment() == segment) {
+            return walk;
+        }
+    }
+    return NULL;
+}
+
 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); 
+SkOpGlobalState* SkOpSpanBase::globalState() const {
+    return contour()->globalState(); 
 }
 
 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);
+    PATH_OPS_DEBUG_CODE(fID = globalState()->nextSpanID());
 }
 
 // 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();
+    span->detach(this->ptT());
     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) {
+    const SkOpSpan* next = fCoincident;
+    do {
         if (next->segment() == segment) {
             return true;
         }
-    }
+    } while ((next = next->fCoincident) != this);
     return false;
 }
 
-void SkOpSpan::detach() {
+void SkOpSpan::detach(SkOpPtT* kept) {
     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->globalState()->coincidence()->fixUp(this->ptT(), kept);
     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) {
+void SkOpSpan::setOppSum(int oppSum) {
+    SkASSERT(!final());
+    if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
+        this->globalState()->setWindingFailed();
         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));
+    SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
+    fOppSum = oppSum;
 }
-
-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));
-}