blob: 5687dd415f9fb7caf949f7a2313ceefc905fbbc9 [file] [log] [blame]
/*
* 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"
bool SkOpCoincidence::extend(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
SkOpPtT* oppPtTEnd) {
// if there is an existing pair that overlaps the addition, extend it
SkCoincidentSpans* coinRec = fHead;
if (coinRec) {
do {
if (coinRec->fCoinPtTStart->segment() != coinPtTStart->segment()) {
continue;
}
if (coinRec->fOppPtTStart->segment() != oppPtTStart->segment()) {
continue;
}
if (coinRec->fCoinPtTStart->fT > coinPtTEnd->fT) {
continue;
}
if (coinRec->fCoinPtTEnd->fT < coinPtTStart->fT) {
continue;
}
if (coinRec->fCoinPtTStart->fT > coinPtTStart->fT) {
coinRec->fCoinPtTStart = coinPtTStart;
coinRec->fOppPtTStart = oppPtTStart;
}
if (coinRec->fCoinPtTEnd->fT < coinPtTEnd->fT) {
coinRec->fCoinPtTEnd = coinPtTEnd;
coinRec->fOppPtTEnd = oppPtTEnd;
}
return true;
} while ((coinRec = coinRec->fNext));
}
return false;
}
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;
SkDEBUGCODE(coinRec->fID = fDebugState->nextCoinID());
this->fHead = coinRec;
}
static void t_range(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::addExpanded(SkChunkAlloc* allocator
PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) {
#if DEBUG_VALIDATE
globalState->setPhase(SkOpGlobalState::kIntersecting);
#endif
// for each coincident pair, match the spans
// if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
SkCoincidentSpans* coin = this->fHead;
SkASSERT(coin);
do {
SkOpPtT* startPtT = coin->fCoinPtTStart;
SkOpPtT* oStartPtT = coin->fOppPtTStart;
SkASSERT(startPtT->contains(oStartPtT));
SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
SkOpSpanBase* start = startPtT->span();
SkOpSpanBase* oStart = oStartPtT->span();
const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
if (oEnd->deleted()) {
return false;
}
SkOpSpanBase* test = start->upCast()->next();
SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
while (test != end || oTest != oEnd) {
if (!test->ptT()->contains(oTest->ptT())) {
// use t ranges to guess which one is missing
double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
if (!startRange) {
return false;
}
double startPart = (test->t() - startPtT->fT) / startRange;
double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
if (!oStartRange) {
return false;
}
double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
if (startPart == oStartPart) {
return false;
}
SkOpPtT* newPt;
if (startPart < oStartPart) {
double newT = oStartPtT->fT + oStartRange * startPart;
newPt = oStart->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
if (!newPt) {
return false;
}
newPt->fPt = test->pt();
test->ptT()->addOpp(newPt);
} else {
double newT = startPtT->fT + startRange * oStartPart;
newPt = start->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
if (!newPt) {
return false;
}
newPt->fPt = oTest->pt();
oTest->ptT()->addOpp(newPt);
}
// start over
test = start;
oTest = oStart;
}
if (test != end) {
test = test->upCast()->next();
}
if (oTest != oEnd) {
oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
}
}
} while ((coin = coin->fNext));
#if DEBUG_VALIDATE
globalState->setPhase(SkOpGlobalState::kWalking);
#endif
return true;
}
bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s,
SkOpPtT* over1e, SkChunkAlloc* allocator) {
SkCoincidentSpans* check = this->fTop;
do {
if (check->fCoinPtTStart->span() == over1s->span()
&& check->fOppPtTStart->span() == outer->fOppPtTStart->span()) {
SkASSERT(check->fCoinPtTEnd->span() == over1e->span()
|| !fDebugState->debugRunFail());
SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span()
|| !fDebugState->debugRunFail());
return false;
}
if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span()
&& check->fOppPtTStart->span() == over1s->span()) {
SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span()
|| !fDebugState->debugRunFail());
SkASSERT(check->fOppPtTEnd->span() == over1e->span()
|| !fDebugState->debugRunFail());
return false;
}
} while ((check = check->fNext));
this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocator);
#if 0
// FIXME: up to four flavors could be added -- do we need only one?
#endif
return true;
}
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;
t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
SkOpSegment* coinSeg = coinPtTStart->segment();
SkOpSegment* oppSeg = oppPtTStart->segment();
SkASSERT(coinSeg != oppSeg);
SkCoincidentSpans* check = this->fTop;
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 false;
}
} 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);
SkASSERT(cs != ce);
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;
}
/* detects overlaps of different coincident runs on same segment */
/* does not detect overlaps for pairs without any segments in common */
bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) {
SkCoincidentSpans* outer = fHead;
if (!outer) {
return true;
}
bool added = false;
fTop = outer;
fHead = nullptr;
do {
// addifmissing can modify the list that this is walking
// save head so that walker can iterate over old data unperturbed
// addifmissing adds to head freely then add saved head in the end
const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
SkCoincidentSpans* inner = outer;
while ((inner = inner->fNext)) {
double overS, overE;
const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
SkASSERT(innerCoin == inner->fCoinPtTEnd->segment());
const SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
SkASSERT(innerOpp == inner->fOppPtTEnd->segment());
if (outerCoin == innerCoin
&& this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
} else if (outerCoin == innerOpp
&& this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
} else if (outerOpp == innerCoin
&& this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
} else if (outerOpp == innerOpp
&& this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
outer->fCoinPtTStart, outer->fCoinPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
} else if (outerCoin != innerCoin) {
// check to see if outer span overlaps the inner span
// look for inner segment in pt-t list
// if present, and if t values are in coincident range
// add two pairs of new coincidence
SkOpPtT* testS = outer->fCoinPtTStart->contains(innerCoin);
SkOpPtT* testE = outer->fCoinPtTEnd->contains(innerCoin);
if (testS && testS->fT >= inner->fCoinPtTStart->fT
&& testE && testE->fT <= inner->fCoinPtTEnd->fT
&& this->testForCoincidence(outer, testS, testE)) {
added |= this->addIfMissing(outer, testS, testE, allocator);
} else {
testS = inner->fCoinPtTStart->contains(outerCoin);
testE = inner->fCoinPtTEnd->contains(outerCoin);
if (testS && testS->fT >= outer->fCoinPtTStart->fT
&& testE && testE->fT <= outer->fCoinPtTEnd->fT
&& this->testForCoincidence(inner, testS, testE)) {
added |= this->addIfMissing(inner, testS, testE, allocator);
}
}
}
#if 0 && DEBUG_COINCIDENCE
SkString miss;
miss.printf("addMissing inner=%d outer=%d", inner->debugID(), outer->debugID());
DEBUG_COINCIDENCE_HEALTH(fDebugState->contourHead(), miss.c_str());
#endif
}
} while ((outer = outer->fNext));
SkCoincidentSpans** headPtr = &fHead;
while (*headPtr) {
SkCoincidentSpans** headNext = &(*headPtr)->fNext;
if (*headNext) {
break;
}
headPtr = headNext;
}
*headPtr = fTop;
return added;
}
void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2,
SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* allocator) {
SkOpPtT* s1 = overS->find(seg1);
SkOpPtT* e1 = overE->find(seg1);
if (!s1->starter(e1)->span()->upCast()->windValue()) {
s1 = overS->find(seg1o);
e1 = overE->find(seg1o);
if (!s1->starter(e1)->span()->upCast()->windValue()) {
return;
}
}
SkOpPtT* s2 = overS->find(seg2);
SkOpPtT* e2 = overE->find(seg2);
if (!s2->starter(e2)->span()->upCast()->windValue()) {
s2 = overS->find(seg2o);
e2 = overE->find(seg2o);
if (!s2->starter(e2)->span()->upCast()->windValue()) {
return;
}
}
if (s1->segment() == s2->segment()) {
return;
}
if (s1->fT > e1->fT) {
SkTSwap(s1, e1);
SkTSwap(s2, e2);
}
this->add(s1, e1, s2, e2, allocator);
}
bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const {
const 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 {
SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
if (start->deleted()) {
continue;
}
SkOpSpanBase* end = coin->fCoinPtTEnd->span();
SkASSERT(start == start->starter(end));
bool flipped = coin->fFlipped;
SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast();
if (oStart->deleted()) {
continue;
}
SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span();
SkASSERT(oStart == oStart->starter(oEnd));
SkOpSegment* segment = start->segment();
SkOpSegment* oSegment = oStart->segment();
bool operandSwap = segment->operand() != oSegment->operand();
if (flipped) {
if (oEnd->deleted()) {
continue;
}
do {
SkOpSpanBase* oNext = oStart->next();
if (oNext == oEnd) {
break;
}
oStart = oNext->upCast();
} while (true);
}
do {
int windValue = start->windValue();
int oppValue = start->oppValue();
int oWindValue = oStart->windValue();
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
int windDiff = operandSwap ? oOppValue : oWindValue;
int oWindDiff = operandSwap ? oppValue : windValue;
if (!flipped) {
windDiff = -windDiff;
oWindDiff = -oWindDiff;
}
if (windValue && (windValue > windDiff || (windValue == windDiff
&& oWindValue <= oWindDiff))) {
if (operandSwap) {
SkTSwap(oWindValue, oOppValue);
}
if (flipped) {
windValue -= oWindValue;
oppValue -= oOppValue;
} else {
windValue += oWindValue;
oppValue += oOppValue;
}
if (segment->isXor()) {
windValue &= 1;
}
if (segment->oppXor()) {
oppValue &= 1;
}
oWindValue = oOppValue = 0;
} else {
if (operandSwap) {
SkTSwap(windValue, oppValue);
}
if (flipped) {
oWindValue -= windValue;
oOppValue -= oppValue;
} else {
oWindValue += windValue;
oOppValue += oppValue;
}
if (oSegment->isXor()) {
oWindValue &= 1;
}
if (oSegment->oppXor()) {
oOppValue &= 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;
}
if (!next->upCastable()) {
return false;
}
start = next->upCast();
// if the opposite ran out too soon, just reuse the last span
if (!oNext || !oNext->upCastable()) {
oNext = oStart;
}
oStart = oNext->upCast();
} while (true);
} while ((coin = coin->fNext));
return true;
}
void SkOpCoincidence::detach(SkCoincidentSpans* remove) {
SkCoincidentSpans* coin = fHead;
SkCoincidentSpans* prev = nullptr;
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);
}
bool SkOpCoincidence::expand() {
SkCoincidentSpans* coin = fHead;
if (!coin) {
return false;
}
bool expanded = false;
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;
expanded = true;
}
}
SkOpSpanBase* next = end->final() ? nullptr : 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;
expanded = true;
}
}
} while ((coin = coin->fNext));
return expanded;
}
void SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps, SkChunkAlloc* allocator) const {
overlaps->fHead = overlaps->fTop = nullptr;
SkDEBUGCODE_(overlaps->debugSetGlobalState(fDebugState));
SkCoincidentSpans* outer = fHead;
while (outer) {
SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
SkCoincidentSpans* inner = outer;
while ((inner = inner->fNext)) {
SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
if (outerCoin == innerCoin) {
continue; // both winners are the same segment, so there's no additional overlap
}
SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
SkOpPtT* overlapS, * overlapE;
if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->fOppPtTStart, outer->fOppPtTEnd,
inner->fCoinPtTStart, inner->fCoinPtTEnd, &overlapS, &overlapE))
|| (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->fCoinPtTStart,
outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd,
&overlapS, &overlapE))
|| (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->fOppPtTStart,
outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd,
&overlapS, &overlapE))) {
overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
overlapS, overlapE, allocator);
}
}
outer = outer->fNext;
}
}
void SkOpCoincidence::fixAligned() {
SkCoincidentSpans* coin = fHead;
if (!coin) {
return;
}
do {
if (coin->fCoinPtTStart->deleted()) {
coin->fCoinPtTStart = coin->fCoinPtTStart->doppelganger();
}
if (coin->fCoinPtTEnd->deleted()) {
coin->fCoinPtTEnd = coin->fCoinPtTEnd->doppelganger();
}
if (coin->fOppPtTStart->deleted()) {
coin->fOppPtTStart = coin->fOppPtTStart->doppelganger();
}
if (coin->fOppPtTEnd->deleted()) {
coin->fOppPtTEnd = coin->fOppPtTEnd->doppelganger();
}
} while ((coin = coin->fNext));
coin = fHead;
SkCoincidentSpans** priorPtr = &fHead;
do {
if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)
|| coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
*priorPtr = coin->fNext;
continue;
}
priorPtr = &coin->fNext;
} 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()) {
this->detach(coin);
continue;
}
coin->fCoinPtTStart = kept;
}
if (coin->fCoinPtTEnd == deleted) {
if (coin->fCoinPtTStart->span() == kept->span()) {
this->detach(coin);
continue;
}
coin->fCoinPtTEnd = kept;
}
if (coin->fOppPtTStart == deleted) {
if (coin->fOppPtTEnd->span() == kept->span()) {
this->detach(coin);
continue;
}
coin->fOppPtTStart = kept;
}
if (coin->fOppPtTEnd == deleted) {
if (coin->fOppPtTStart->span() == kept->span()) {
this->detach(coin);
continue;
}
coin->fOppPtTEnd = kept;
}
} while ((coin = coin->fNext));
}
/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
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 || 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 {
SkASSERT(coin1s->segment() == coin2s->segment());
*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;
}
bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS,
const SkOpPtT* testE) const {
return testS->segment()->testForCoincidence(testS, testE, testS->span(),
testE->span(), outer->fCoinPtTStart->segment(), 120000); // FIXME: replace with tuned
}