| /* | |
| * 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(); | |
| } | |
| SkOpGlobalState* SkOpPtT::globalState() const { | |
| return PATH_OPS_DEBUG_RELEASE(contour()->globalState(), 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->globalState()->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(this); | |
| fDeleted = true; | |
| return prev; | |
| } | |
| prev = next; | |
| } while (prev != this); | |
| SkASSERT(0); | |
| return NULL; | |
| } | |
| void SkOpPtT::removeNext(SkOpPtT* kept) { | |
| SkASSERT(this->fNext); | |
| SkOpPtT* next = this->fNext; | |
| this->fNext = next->fNext; | |
| SkOpSpanBase* span = next->span(); | |
| next->setDeleted(); | |
| if (span->ptT() == next) { | |
| span->upCast()->detach(kept); | |
| } | |
| } | |
| 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(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; | |
| } | |
| 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(); | |
| } | |
| SkOpGlobalState* SkOpSpanBase::globalState() const { | |
| return PATH_OPS_DEBUG_RELEASE(contour()->globalState(), 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 = ++globalState()->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(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) { | |
| if (next->segment() == segment) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| 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); | |
| if (this->coincident()) { | |
| this->globalState()->fCoincidence->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) { | |
| 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)); | |
| } |