/* * 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 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; SkDEBUGCODE(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(this); SkASSERT(prev->fNext != prev); 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; SkASSERT(this != next->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(); } 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; } 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(); } 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; fSpanAdds = 0; fAligned = true; fChased = false; SkDEBUGCODE(fCount = 1); SkDEBUGCODE(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(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; } fSpanAdds += span->fSpanAdds; } int SkOpSpan::computeWindSum() { SkOpGlobalState* globals = this->globalState(); SkOpContour* contourHead = globals->contourHead(); int windTry = 0; while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) { ; } return this->windSum(); } bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const { SkASSERT(this->segment() != segment); const SkOpSpan* next = fCoincident; do { if (next->segment() == segment) { return true; } } while ((next = next->fCoincident) != this); 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); 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; fTopTTry = 0; fChased = fDone = false; segment->bumpCount(); } void SkOpSpan::setOppSum(int oppSum) { SkASSERT(!final()); if (fOppSum != SK_MinS32 && fOppSum != oppSum) { this->globalState()->setWindingFailed(); return; } SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(oppSum) <= DEBUG_LIMIT_WIND_SUM); fOppSum = oppSum; } void SkOpSpan::setWindSum(int windSum) { SkASSERT(!final()); if (fWindSum != SK_MinS32 && fWindSum != windSum) { this->globalState()->setWindingFailed(); return; } SkASSERT(!DEBUG_LIMIT_WIND_SUM || abs(windSum) <= DEBUG_LIMIT_WIND_SUM); fWindSum = windSum; }