154359294a7c9dc54802d512a5d891a35c1663392caryclark/* 254359294a7c9dc54802d512a5d891a35c1663392caryclark * Copyright 2015 Google Inc. 354359294a7c9dc54802d512a5d891a35c1663392caryclark * 454359294a7c9dc54802d512a5d891a35c1663392caryclark * Use of this source code is governed by a BSD-style license that can be 554359294a7c9dc54802d512a5d891a35c1663392caryclark * found in the LICENSE file. 654359294a7c9dc54802d512a5d891a35c1663392caryclark */ 754359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpCoincidence.h" 854359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkOpSegment.h" 954359294a7c9dc54802d512a5d891a35c1663392caryclark#include "SkPathOpsTSect.h" 1054359294a7c9dc54802d512a5d891a35c1663392caryclark 1155888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if coincident span's start and end are the same 1255888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::collapsed(const SkOpPtT* test) const { 1355888e44171ffd48b591d19256884a969fe4da17caryclark return (fCoinPtTStart == test && fCoinPtTEnd->contains(test)) 1455888e44171ffd48b591d19256884a969fe4da17caryclark || (fCoinPtTEnd == test && fCoinPtTStart->contains(test)) 1555888e44171ffd48b591d19256884a969fe4da17caryclark || (fOppPtTStart == test && fOppPtTEnd->contains(test)) 1655888e44171ffd48b591d19256884a969fe4da17caryclark || (fOppPtTEnd == test && fOppPtTStart->contains(test)); 1755888e44171ffd48b591d19256884a969fe4da17caryclark} 1855888e44171ffd48b591d19256884a969fe4da17caryclark 19db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 20db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::coinPtTEnd() const { 21db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fCoinPtTEnd; 22db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 23db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 24db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 25db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::coinPtTStart() const { 26db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fCoinPtTStart; 27db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 28db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 2955888e44171ffd48b591d19256884a969fe4da17caryclark// sets the span's end to the ptT referenced by the previous-next 3055888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::correctOneEnd( 3155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* (SkCoincidentSpans::* getEnd)() const, 3255888e44171ffd48b591d19256884a969fe4da17caryclark void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) { 3355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* origPtT = (this->*getEnd)(); 3455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* origSpan = origPtT->span(); 3555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = origSpan->prev(); 3655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT = prev ? prev->next()->ptT() 3755888e44171ffd48b591d19256884a969fe4da17caryclark : origSpan->upCast()->next()->prev()->ptT(); 3855888e44171ffd48b591d19256884a969fe4da17caryclark if (origPtT != testPtT) { 3955888e44171ffd48b591d19256884a969fe4da17caryclark (this->*setEnd)(testPtT); 4055888e44171ffd48b591d19256884a969fe4da17caryclark } 4155888e44171ffd48b591d19256884a969fe4da17caryclark} 4255888e44171ffd48b591d19256884a969fe4da17caryclark 43ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark/* Please keep this in sync with debugCorrectEnds */ 4455888e44171ffd48b591d19256884a969fe4da17caryclark// FIXME: member pointers have fallen out of favor and can be replaced with 4555888e44171ffd48b591d19256884a969fe4da17caryclark// an alternative approach. 4655888e44171ffd48b591d19256884a969fe4da17caryclark// makes all span ends agree with the segment's spans that define them 4755888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::correctEnds() { 4855888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart); 4955888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd); 5055888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart); 5155888e44171ffd48b591d19256884a969fe4da17caryclark this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd); 5255888e44171ffd48b591d19256884a969fe4da17caryclark} 5355888e44171ffd48b591d19256884a969fe4da17caryclark 5455888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugExpand */ 5555888e44171ffd48b591d19256884a969fe4da17caryclark// expand the range by checking adjacent spans for coincidence 5655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::expand() { 5755888e44171ffd48b591d19256884a969fe4da17caryclark bool expanded = false; 5855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* segment = coinPtTStart()->segment(); 5955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSegment = oppPtTStart()->segment(); 6055888e44171ffd48b591d19256884a969fe4da17caryclark do { 6155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* start = coinPtTStart()->span()->upCast(); 6255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = start->prev(); 6355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtT; 6455888e44171ffd48b591d19256884a969fe4da17caryclark if (!prev || !(oppPtT = prev->contains(oppSegment))) { 6555888e44171ffd48b591d19256884a969fe4da17caryclark break; 6655888e44171ffd48b591d19256884a969fe4da17caryclark } 6755888e44171ffd48b591d19256884a969fe4da17caryclark double midT = (prev->t() + start->t()) / 2; 6855888e44171ffd48b591d19256884a969fe4da17caryclark if (!segment->isClose(midT, oppSegment)) { 6955888e44171ffd48b591d19256884a969fe4da17caryclark break; 7055888e44171ffd48b591d19256884a969fe4da17caryclark } 7155888e44171ffd48b591d19256884a969fe4da17caryclark setStarts(prev->ptT(), oppPtT); 7255888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 7355888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 7455888e44171ffd48b591d19256884a969fe4da17caryclark do { 7555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coinPtTEnd()->span(); 7655888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); 77c6d855f7f3d548c52f450299dc6975820cda3387caryclark if (next && next->deleted()) { 78c6d855f7f3d548c52f450299dc6975820cda3387caryclark break; 79c6d855f7f3d548c52f450299dc6975820cda3387caryclark } 8055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtT; 8155888e44171ffd48b591d19256884a969fe4da17caryclark if (!next || !(oppPtT = next->contains(oppSegment))) { 8255888e44171ffd48b591d19256884a969fe4da17caryclark break; 8355888e44171ffd48b591d19256884a969fe4da17caryclark } 8455888e44171ffd48b591d19256884a969fe4da17caryclark double midT = (end->t() + next->t()) / 2; 8555888e44171ffd48b591d19256884a969fe4da17caryclark if (!segment->isClose(midT, oppSegment)) { 8655888e44171ffd48b591d19256884a969fe4da17caryclark break; 8755888e44171ffd48b591d19256884a969fe4da17caryclark } 8855888e44171ffd48b591d19256884a969fe4da17caryclark setEnds(next->ptT(), oppPtT); 8955888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 9055888e44171ffd48b591d19256884a969fe4da17caryclark } while (true); 9155888e44171ffd48b591d19256884a969fe4da17caryclark return expanded; 9255888e44171ffd48b591d19256884a969fe4da17caryclark} 9355888e44171ffd48b591d19256884a969fe4da17caryclark 9455888e44171ffd48b591d19256884a969fe4da17caryclark// increase the range of this span 9555888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 9655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 9755888e44171ffd48b591d19256884a969fe4da17caryclark bool result = false; 9855888e44171ffd48b591d19256884a969fe4da17caryclark if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped() 9955888e44171ffd48b591d19256884a969fe4da17caryclark ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) { 10055888e44171ffd48b591d19256884a969fe4da17caryclark this->setStarts(coinPtTStart, oppPtTStart); 10155888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 10255888e44171ffd48b591d19256884a969fe4da17caryclark } 10355888e44171ffd48b591d19256884a969fe4da17caryclark if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped() 10455888e44171ffd48b591d19256884a969fe4da17caryclark ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) { 10555888e44171ffd48b591d19256884a969fe4da17caryclark this->setEnds(coinPtTEnd, oppPtTEnd); 10655888e44171ffd48b591d19256884a969fe4da17caryclark result = true; 10755888e44171ffd48b591d19256884a969fe4da17caryclark } 10855888e44171ffd48b591d19256884a969fe4da17caryclark return result; 10955888e44171ffd48b591d19256884a969fe4da17caryclark} 11055888e44171ffd48b591d19256884a969fe4da17caryclark 11155888e44171ffd48b591d19256884a969fe4da17caryclark// set the range of this span 11255888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, 113ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 11455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart)); 11555888e44171ffd48b591d19256884a969fe4da17caryclark fNext = next; 11655888e44171ffd48b591d19256884a969fe4da17caryclark this->setStarts(coinPtTStart, oppPtTStart); 11755888e44171ffd48b591d19256884a969fe4da17caryclark this->setEnds(coinPtTEnd, oppPtTEnd); 11855888e44171ffd48b591d19256884a969fe4da17caryclark} 11955888e44171ffd48b591d19256884a969fe4da17caryclark 12055888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if both points are inside this 12155888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const { 12255888e44171ffd48b591d19256884a969fe4da17caryclark if (s->fT > e->fT) { 12355888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(s, e); 12455888e44171ffd48b591d19256884a969fe4da17caryclark } 12555888e44171ffd48b591d19256884a969fe4da17caryclark if (s->segment() == fCoinPtTStart->segment()) { 12655888e44171ffd48b591d19256884a969fe4da17caryclark return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT; 12755888e44171ffd48b591d19256884a969fe4da17caryclark } else { 12855888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(s->segment() == fOppPtTStart->segment()); 12955888e44171ffd48b591d19256884a969fe4da17caryclark double oppTs = fOppPtTStart->fT; 13055888e44171ffd48b591d19256884a969fe4da17caryclark double oppTe = fOppPtTEnd->fT; 13155888e44171ffd48b591d19256884a969fe4da17caryclark if (oppTs > oppTe) { 13255888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 13355888e44171ffd48b591d19256884a969fe4da17caryclark } 13455888e44171ffd48b591d19256884a969fe4da17caryclark return oppTs <= s->fT && e->fT <= oppTe; 13555888e44171ffd48b591d19256884a969fe4da17caryclark } 13655888e44171ffd48b591d19256884a969fe4da17caryclark} 13755888e44171ffd48b591d19256884a969fe4da17caryclark 138db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 139db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::oppPtTStart() const { 140db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fOppPtTStart; 141db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 142db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 143db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark// out of line since this function is referenced by address 144db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clarkconst SkOpPtT* SkCoincidentSpans::oppPtTEnd() const { 145db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark return fOppPtTEnd; 146db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark} 147db8f44f497f2b67b2500bbfc7b11ce7a510c5e5cCary Clark 14881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// A coincident span is unordered if the pairs of points in the main and opposite curves' 14981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// t values do not ascend or descend. For instance, if a tightly arced quadratic is 15081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark// coincident with another curve, it may intersect it out of order. 151a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkCoincidentSpans::ordered(bool* result) const { 15281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* start = this->coinPtTStart()->span(); 15381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* end = this->coinPtTEnd()->span(); 15481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSpanBase* next = start->upCast()->next(); 15581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (next == end) { 156a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = true; 15781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 15881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 15981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark bool flipped = this->flipped(); 16081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpSegment* oppSeg = this->oppPtTStart()->segment(); 16181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double oppLastT = fOppPtTStart->fT; 16281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark do { 16381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark const SkOpPtT* opp = next->contains(oppSeg); 16481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (!opp) { 165ab2d73b06fe6c518be1d399a79c9cc39db21abb6Cary Clark// SkOPOBJASSERT(start, 0); // may assert if coincident span isn't fully processed 166a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return false; 16781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 16881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if ((oppLastT > opp->fT) != flipped) { 169a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = false; 170a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 17181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 17281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark oppLastT = opp->fT; 17381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (next == end) { 17481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark break; 17581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 176bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark if (!next->upCastable()) { 177a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = false; 178a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 179bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark } 18081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark next = next->upCast()->next(); 18181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } while (true); 182a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark *result = true; 18381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 18481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark} 18581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark 18655888e44171ffd48b591d19256884a969fe4da17caryclark// if there is an existing pair that overlaps the addition, extend it 18755888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 18855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 18955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = fHead; 19055888e44171ffd48b591d19256884a969fe4da17caryclark if (!test) { 19155888e44171ffd48b591d19256884a969fe4da17caryclark return false; 19255888e44171ffd48b591d19256884a969fe4da17caryclark } 19355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg = coinPtTStart->segment(); 19455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSeg = oppPtTStart->segment(); 19555888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 19655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 19755888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, oppPtTStart); 19855888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTEnd, oppPtTEnd); 19955888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT > coinPtTEnd->fT) { 20055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, coinPtTEnd); 20155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppPtTStart, oppPtTEnd); 20255888e44171ffd48b591d19256884a969fe4da17caryclark } 20355888e44171ffd48b591d19256884a969fe4da17caryclark } 20455888e44171ffd48b591d19256884a969fe4da17caryclark double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 20555888e44171ffd48b591d19256884a969fe4da17caryclark SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT)); 20655888e44171ffd48b591d19256884a969fe4da17caryclark do { 20755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg != test->coinPtTStart()->segment()) { 20855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 20955888e44171ffd48b591d19256884a969fe4da17caryclark } 21055888e44171ffd48b591d19256884a969fe4da17caryclark if (oppSeg != test->oppPtTStart()->segment()) { 21155888e44171ffd48b591d19256884a969fe4da17caryclark continue; 21255888e44171ffd48b591d19256884a969fe4da17caryclark } 21355888e44171ffd48b591d19256884a969fe4da17caryclark double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 21455888e44171ffd48b591d19256884a969fe4da17caryclark double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 21555888e44171ffd48b591d19256884a969fe4da17caryclark // if debug check triggers, caller failed to check if extended already exists 21655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT 21755888e44171ffd48b591d19256884a969fe4da17caryclark || coinPtTEnd->fT > test->coinPtTEnd()->fT 21855888e44171ffd48b591d19256884a969fe4da17caryclark || oTestMinT > oppMinT || oppMaxT > oTestMaxT); 21955888e44171ffd48b591d19256884a969fe4da17caryclark if ((test->coinPtTStart()->fT <= coinPtTEnd->fT 22055888e44171ffd48b591d19256884a969fe4da17caryclark && coinPtTStart->fT <= test->coinPtTEnd()->fT) 22155888e44171ffd48b591d19256884a969fe4da17caryclark || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) { 22255888e44171ffd48b591d19256884a969fe4da17caryclark test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 22355888e44171ffd48b591d19256884a969fe4da17caryclark return true; 22455888e44171ffd48b591d19256884a969fe4da17caryclark } 22555888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 22655888e44171ffd48b591d19256884a969fe4da17caryclark return false; 22755888e44171ffd48b591d19256884a969fe4da17caryclark} 22855888e44171ffd48b591d19256884a969fe4da17caryclark 22955888e44171ffd48b591d19256884a969fe4da17caryclark// verifies that the coincidence hasn't already been added 23055888e44171ffd48b591d19256884a969fe4da17caryclarkstatic void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart, 23155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 23255888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE 23355888e44171ffd48b591d19256884a969fe4da17caryclark while (check) { 23455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd 23555888e44171ffd48b591d19256884a969fe4da17caryclark || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd); 23655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd 23755888e44171ffd48b591d19256884a969fe4da17caryclark || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd); 23855888e44171ffd48b591d19256884a969fe4da17caryclark check = check->next(); 23955888e44171ffd48b591d19256884a969fe4da17caryclark } 24055888e44171ffd48b591d19256884a969fe4da17caryclark#endif 24155888e44171ffd48b591d19256884a969fe4da17caryclark} 24255888e44171ffd48b591d19256884a969fe4da17caryclark 24355888e44171ffd48b591d19256884a969fe4da17caryclark// adds a new coincident pair 24455888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 24555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* oppPtTEnd) { 24655888e44171ffd48b591d19256884a969fe4da17caryclark // OPTIMIZE: caller should have already sorted 24755888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 24855888e44171ffd48b591d19256884a969fe4da17caryclark if (oppPtTStart->fT < oppPtTEnd->fT) { 24955888e44171ffd48b591d19256884a969fe4da17caryclark this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd); 25055888e44171ffd48b591d19256884a969fe4da17caryclark } else { 25155888e44171ffd48b591d19256884a969fe4da17caryclark this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart); 25255888e44171ffd48b591d19256884a969fe4da17caryclark } 25355888e44171ffd48b591d19256884a969fe4da17caryclark return; 25455888e44171ffd48b591d19256884a969fe4da17caryclark } 25555888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(Ordered(coinPtTStart, oppPtTStart)); 25655888e44171ffd48b591d19256884a969fe4da17caryclark // choose the ptT at the front of the list to track 25755888e44171ffd48b591d19256884a969fe4da17caryclark coinPtTStart = coinPtTStart->span()->ptT(); 25855888e44171ffd48b591d19256884a969fe4da17caryclark coinPtTEnd = coinPtTEnd->span()->ptT(); 25955888e44171ffd48b591d19256884a969fe4da17caryclark oppPtTStart = oppPtTStart->span()->ptT(); 26055888e44171ffd48b591d19256884a969fe4da17caryclark oppPtTEnd = oppPtTEnd->span()->ptT(); 261a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT); 26296dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT); 26330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!coinPtTStart->deleted()); 26430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!coinPtTEnd->deleted()); 26530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!oppPtTStart->deleted()); 26630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(!oppPtTEnd->deleted()); 26755888e44171ffd48b591d19256884a969fe4da17caryclark DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 26855888e44171ffd48b591d19256884a969fe4da17caryclark DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 269ecc364c42691f24b41a672de1636b3a5f181160aHerb Derby SkCoincidentSpans* coinRec = this->globalState()->allocator()->make<SkCoincidentSpans>(); 270fc560e09b3f777bb32dccb9f52d715383a10a620caryclark coinRec->init(SkDEBUGCODE(fGlobalState)); 271ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 27255888e44171ffd48b591d19256884a969fe4da17caryclark fHead = coinRec; 27355888e44171ffd48b591d19256884a969fe4da17caryclark} 27455888e44171ffd48b591d19256884a969fe4da17caryclark 27555888e44171ffd48b591d19256884a969fe4da17caryclark// description below 2761597628fa38d24f23ad505bfb40e70e7c8617457caryclarkbool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) { 27755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* testPtT = testSpan->ptT(); 27855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* stopPtT = testPtT; 27955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* baseSeg = base->segment(); 2804eed4c885050132b7131324ea336ad0f6d977fefCary Clark int escapeHatch = 100000; // this is 100 times larger than the debugLoopLimit test 28155888e44171ffd48b591d19256884a969fe4da17caryclark while ((testPtT = testPtT->next()) != stopPtT) { 2824eed4c885050132b7131324ea336ad0f6d977fefCary Clark if (--escapeHatch <= 0) { 2834eed4c885050132b7131324ea336ad0f6d977fefCary Clark return false; // if triggered (likely by a fuzz-generated test) too complex to succeed 2844eed4c885050132b7131324ea336ad0f6d977fefCary Clark } 28555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* testSeg = testPtT->segment(); 28655888e44171ffd48b591d19256884a969fe4da17caryclark if (testPtT->deleted()) { 28755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 28855888e44171ffd48b591d19256884a969fe4da17caryclark } 28955888e44171ffd48b591d19256884a969fe4da17caryclark if (testSeg == baseSeg) { 29055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 29155888e44171ffd48b591d19256884a969fe4da17caryclark } 292c6d855f7f3d548c52f450299dc6975820cda3387caryclark if (testPtT->span()->ptT() != testPtT) { 293c6d855f7f3d548c52f450299dc6975820cda3387caryclark continue; 294c6d855f7f3d548c52f450299dc6975820cda3387caryclark } 29555888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(baseSeg, testSeg, testPtT->fT)) { 29655888e44171ffd48b591d19256884a969fe4da17caryclark continue; 29755888e44171ffd48b591d19256884a969fe4da17caryclark } 29855888e44171ffd48b591d19256884a969fe4da17caryclark // intersect perp with base->ptT() with testPtT->segment() 29955888e44171ffd48b591d19256884a969fe4da17caryclark SkDVector dxdy = baseSeg->dSlopeAtT(base->t()); 30055888e44171ffd48b591d19256884a969fe4da17caryclark const SkPoint& pt = base->pt(); 30155888e44171ffd48b591d19256884a969fe4da17caryclark SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}}; 3024c76c41c981dd7ea95062a1895a6e3415b70bce1Cary Clark SkIntersections i SkDEBUGCODE((this->globalState())); 30355888e44171ffd48b591d19256884a969fe4da17caryclark (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i); 30455888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 0; index < i.used(); ++index) { 30555888e44171ffd48b591d19256884a969fe4da17caryclark double t = i[0][index]; 30655888e44171ffd48b591d19256884a969fe4da17caryclark if (!between(0, t, 1)) { 307bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 308bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 30955888e44171ffd48b591d19256884a969fe4da17caryclark SkDPoint oppPt = i.pt(index); 31055888e44171ffd48b591d19256884a969fe4da17caryclark if (!oppPt.approximatelyEqual(pt)) { 311bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 312bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 31355888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg); 31429b2563afb1677515739f1d24fb27733626eca92caryclark SkOpPtT* oppStart = writableSeg->addT(t); 31527c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark if (oppStart == testPtT) { 31627c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark continue; 31727c015dfcf4e2b8fb1abe327cc40204e2a4f452acaryclark } 31855888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpan* writableBase = const_cast<SkOpSpan*>(base); 31930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oppStart->span()->addOpp(writableBase); 32055888e44171ffd48b591d19256884a969fe4da17caryclark if (oppStart->deleted()) { 321bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark continue; 322bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 32355888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* coinSeg = base->segment(); 32455888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSegment* oppSeg = oppStart->segment(); 32555888e44171ffd48b591d19256884a969fe4da17caryclark double coinTs, coinTe, oppTs, oppTe; 3268016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (Ordered(coinSeg, oppSeg)) { 32755888e44171ffd48b591d19256884a969fe4da17caryclark coinTs = base->t(); 32855888e44171ffd48b591d19256884a969fe4da17caryclark coinTe = testSpan->t(); 32955888e44171ffd48b591d19256884a969fe4da17caryclark oppTs = oppStart->fT; 33055888e44171ffd48b591d19256884a969fe4da17caryclark oppTe = testPtT->fT; 33155888e44171ffd48b591d19256884a969fe4da17caryclark } else { 33255888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 33355888e44171ffd48b591d19256884a969fe4da17caryclark coinTs = oppStart->fT; 33455888e44171ffd48b591d19256884a969fe4da17caryclark coinTe = testPtT->fT; 33555888e44171ffd48b591d19256884a969fe4da17caryclark oppTs = base->t(); 33655888e44171ffd48b591d19256884a969fe4da17caryclark oppTe = testSpan->t(); 337bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 33855888e44171ffd48b591d19256884a969fe4da17caryclark if (coinTs > coinTe) { 33955888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinTs, coinTe); 34055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 341bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 34281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark bool added; 34381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) { 3441597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3451597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 34655888e44171ffd48b591d19256884a969fe4da17caryclark } 347bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark } 3481597628fa38d24f23ad505bfb40e70e7c8617457caryclark return true; 349bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark} 350bca19f77479adfd8ba2171753382bc8bf4c2b4cacaryclark 35155888e44171ffd48b591d19256884a969fe4da17caryclark// description below 35255888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { 353025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(!ptT->span()->upCastable()); 35455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* base = ptT->span()->upCast(); 35555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpan* prev = base->prev(); 356025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(!prev); 35755888e44171ffd48b591d19256884a969fe4da17caryclark if (!prev->isCanceled()) { 3581597628fa38d24f23ad505bfb40e70e7c8617457caryclark if (!this->addEndMovedSpans(base, base->prev())) { 3591597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3601597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 36155888e44171ffd48b591d19256884a969fe4da17caryclark } 36255888e44171ffd48b591d19256884a969fe4da17caryclark if (!base->isCanceled()) { 3631597628fa38d24f23ad505bfb40e70e7c8617457caryclark if (!this->addEndMovedSpans(base, base->next())) { 3641597628fa38d24f23ad505bfb40e70e7c8617457caryclark return false; 3651597628fa38d24f23ad505bfb40e70e7c8617457caryclark } 36655888e44171ffd48b591d19256884a969fe4da17caryclark } 36755888e44171ffd48b591d19256884a969fe4da17caryclark return true; 36854359294a7c9dc54802d512a5d891a35c1663392caryclark} 36954359294a7c9dc54802d512a5d891a35c1663392caryclark 37055888e44171ffd48b591d19256884a969fe4da17caryclark/* If A is coincident with B and B includes an endpoint, and A's matching point 37155888e44171ffd48b591d19256884a969fe4da17caryclark is not the endpoint (i.e., there's an implied line connecting B-end and A) 37255888e44171ffd48b591d19256884a969fe4da17caryclark then assume that the same implied line may intersect another curve close to B. 37355888e44171ffd48b591d19256884a969fe4da17caryclark Since we only care about coincidence that was undetected, look at the 37455888e44171ffd48b591d19256884a969fe4da17caryclark ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but 37555888e44171ffd48b591d19256884a969fe4da17caryclark next door) and see if the A matching point is close enough to form another 37655888e44171ffd48b591d19256884a969fe4da17caryclark coincident pair. If so, check for a new coincident span between B-end/A ptT loop 37755888e44171ffd48b591d19256884a969fe4da17caryclark and the adjacent ptT loop. 37855888e44171ffd48b591d19256884a969fe4da17caryclark*/ 379ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 380ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 38155888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* span = fHead; 38255888e44171ffd48b591d19256884a969fe4da17caryclark if (!span) { 38355888e44171ffd48b591d19256884a969fe4da17caryclark return true; 38455888e44171ffd48b591d19256884a969fe4da17caryclark } 38555888e44171ffd48b591d19256884a969fe4da17caryclark fTop = span; 38655888e44171ffd48b591d19256884a969fe4da17caryclark fHead = nullptr; 38755888e44171ffd48b591d19256884a969fe4da17caryclark do { 38855888e44171ffd48b591d19256884a969fe4da17caryclark if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { 389025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark FAIL_IF(1 == span->coinPtTStart()->fT); 39055888e44171ffd48b591d19256884a969fe4da17caryclark bool onEnd = span->coinPtTStart()->fT == 0; 39155888e44171ffd48b591d19256884a969fe4da17caryclark bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); 39255888e44171ffd48b591d19256884a969fe4da17caryclark if (onEnd) { 39355888e44171ffd48b591d19256884a969fe4da17caryclark if (!oOnEnd) { // if both are on end, any nearby intersect was already found 39455888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->oppPtTStart())) { 39555888e44171ffd48b591d19256884a969fe4da17caryclark return false; 39655888e44171ffd48b591d19256884a969fe4da17caryclark } 39755888e44171ffd48b591d19256884a969fe4da17caryclark } 39855888e44171ffd48b591d19256884a969fe4da17caryclark } else if (oOnEnd) { 39955888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->coinPtTStart())) { 40055888e44171ffd48b591d19256884a969fe4da17caryclark return false; 40155888e44171ffd48b591d19256884a969fe4da17caryclark } 40255888e44171ffd48b591d19256884a969fe4da17caryclark } 40355888e44171ffd48b591d19256884a969fe4da17caryclark } 40455888e44171ffd48b591d19256884a969fe4da17caryclark if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) { 40555888e44171ffd48b591d19256884a969fe4da17caryclark bool onEnd = span->coinPtTEnd()->fT == 1; 40655888e44171ffd48b591d19256884a969fe4da17caryclark bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT); 40755888e44171ffd48b591d19256884a969fe4da17caryclark if (onEnd) { 40855888e44171ffd48b591d19256884a969fe4da17caryclark if (!oOnEnd) { 40955888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->oppPtTEnd())) { 41055888e44171ffd48b591d19256884a969fe4da17caryclark return false; 41155888e44171ffd48b591d19256884a969fe4da17caryclark } 41255888e44171ffd48b591d19256884a969fe4da17caryclark } 41355888e44171ffd48b591d19256884a969fe4da17caryclark } else if (oOnEnd) { 41455888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->addEndMovedSpans(span->coinPtTEnd())) { 41555888e44171ffd48b591d19256884a969fe4da17caryclark return false; 41655888e44171ffd48b591d19256884a969fe4da17caryclark } 41755888e44171ffd48b591d19256884a969fe4da17caryclark } 41855888e44171ffd48b591d19256884a969fe4da17caryclark } 41955888e44171ffd48b591d19256884a969fe4da17caryclark } while ((span = span->next())); 42055888e44171ffd48b591d19256884a969fe4da17caryclark this->restoreHead(); 42155888e44171ffd48b591d19256884a969fe4da17caryclark return true; 42254359294a7c9dc54802d512a5d891a35c1663392caryclark} 42354359294a7c9dc54802d512a5d891a35c1663392caryclark 42455888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddExpanded */ 42555888e44171ffd48b591d19256884a969fe4da17caryclark// for each coincident pair, match the spans 42655888e44171ffd48b591d19256884a969fe4da17caryclark// if the spans don't match, add the missing pt to the segment and loop it in the opposite span 427ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 428ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 42927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* coin = this->fHead; 43055888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 43155888e44171ffd48b591d19256884a969fe4da17caryclark return true; 43255888e44171ffd48b591d19256884a969fe4da17caryclark } 43327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 43455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* startPtT = coin->coinPtTStart(); 43555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oStartPtT = coin->oppPtTStart(); 4368016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double priorT = startPtT->fT; 4378016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oPriorT = oStartPtT->fT; 438bbfe92bc1dd2b0a65e63b3caed9873dbc4df522acaryclark FAIL_IF(!startPtT->contains(oStartPtT)); 439c6d855f7f3d548c52f450299dc6975820cda3387caryclark SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd())); 44055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* start = startPtT->span(); 44155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oStart = oStartPtT->span(); 44255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 44355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span(); 44455888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(oEnd->deleted()); 445e25a4f6cbeaccfdc34cf031103f0fbc3e53a3ee5caryclark FAIL_IF(!start->upCastable()); 44655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* test = start->upCast()->next(); 447e7bb5b226662f01c91574b29f435acae71c76c46caryclark FAIL_IF(!coin->flipped() && !oStart->upCastable()); 44855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next(); 44930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!oTest); 4508016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* seg = start->segment(); 4518016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* oSeg = oStart->segment(); 45227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while (test != end || oTest != oEnd) { 4538016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* containedOpp = test->ptT()->contains(oSeg); 4548016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* containedThis = oTest->ptT()->contains(seg); 4558016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (!containedOpp || !containedThis) { 4568016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // choose the ends, or the first common pt-t list shared by both 4578016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double nextT, oNextT; 4588016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (containedOpp) { 4598016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = test->t(); 4608016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = containedOpp->fT; 4618016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } else if (containedThis) { 4628016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = containedThis->fT; 4638016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = oTest->t(); 4648016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } else { 4658016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // iterate through until a pt-t list found that contains the other 4668016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSpanBase* walk = test; 4678016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* walkOpp; 4688016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark do { 4698016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark FAIL_IF(!walk->upCastable()); 4708016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark walk = walk->upCast()->next(); 4718016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } while (!(walkOpp = walk->ptT()->contains(oSeg)) 4728016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark && walk != coin->coinPtTEnd()->span()); 4733fdf52cf389d58be9ce4b948dfecffd53edb5da2Cary Clark FAIL_IF(!walkOpp); 4748016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark nextT = walk->t(); 4758016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oNextT = walkOpp->fT; 4768016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 47727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // use t ranges to guess which one is missing 4788016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double startRange = nextT - priorT; 47955888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(!startRange); 4808016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double startPart = (test->t() - priorT) / startRange; 4818016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oStartRange = oNextT - oPriorT; 48255888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(!oStartRange); 4838016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double oStartPart = (oTest->t() - oPriorT) / oStartRange; 48455888e44171ffd48b591d19256884a969fe4da17caryclark FAIL_IF(startPart == oStartPart); 4858016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart 4868016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark : !!containedThis; 48755888e44171ffd48b591d19256884a969fe4da17caryclark bool startOver = false; 4888016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark bool success = addToOpp ? oSeg->addExpanded( 4898016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oPriorT + oStartRange * startPart, test, &startOver) 4908016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark : seg->addExpanded( 4918016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark priorT + startRange * oStartPart, oTest, &startOver); 49230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!success); 49355888e44171ffd48b591d19256884a969fe4da17caryclark if (startOver) { 49455888e44171ffd48b591d19256884a969fe4da17caryclark test = start; 49555888e44171ffd48b591d19256884a969fe4da17caryclark oTest = oStart; 49627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 49730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark end = coin->coinPtTEnd()->span(); 49830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark oEnd = coin->oppPtTEnd()->span(); 49927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 50027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (test != end) { 50130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!test->upCastable()); 5028016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark priorT = test->t(); 50327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark test = test->upCast()->next(); 50427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 50526ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark if (oTest != oEnd) { 5068016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oPriorT = oTest->t(); 50778a37a53365c24670b050acf993818c435922745caryclark if (coin->flipped()) { 50878a37a53365c24670b050acf993818c435922745caryclark oTest = oTest->prev(); 50978a37a53365c24670b050acf993818c435922745caryclark } else { 51078a37a53365c24670b050acf993818c435922745caryclark FAIL_IF(!oTest->upCastable()); 51178a37a53365c24670b050acf993818c435922745caryclark oTest = oTest->upCast()->next(); 51278a37a53365c24670b050acf993818c435922745caryclark } 51330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark FAIL_IF(!oTest); 51427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 5158016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark 51627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 51755888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 51826ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return true; 51927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 52027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 52155888e44171ffd48b591d19256884a969fe4da17caryclark// given a t span, map the same range on the coincident span 5228016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark/* 5238016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkthe curves may not scale linearly, so interpolation may only happen within known points 5248016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkremap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s 5258016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkthen repeat to capture over1e 5268016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark*/ 5278016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkdouble SkOpCoincidence::TRange(const SkOpPtT* overS, double t, 5288016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) { 5298016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSpanBase* work = overS->span(); 5308016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* foundStart = nullptr; 5318016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* foundEnd = nullptr; 5328016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* coinStart = nullptr; 5338016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* coinEnd = nullptr; 5348016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark do { 5358016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* contained = work->contains(coinSeg); 5368016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (!contained) { 537c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark if (work->final()) { 538c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark break; 539b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 5408016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark continue; 5418016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5428016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (work->t() <= t) { 5438016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinStart = contained; 5448016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark foundStart = work->ptT(); 5458016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5468016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (work->t() >= t) { 5478016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinEnd = contained; 5488016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark foundEnd = work->ptT(); 5498016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark break; 5508016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } 5518016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(work->ptT() != overE); 5528016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark } while ((work = work->upCast()->next())); 553c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark if (!coinStart || !coinEnd) { 554c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark return 1; 555c9b90d15df5fcee848812fbab3d714aba9e41e69caryclark } 5568016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark // while overS->fT <=t and overS contains coinSeg 5578016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double denom = foundEnd->fT - foundStart->fT; 5588016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark double sRatio = denom ? (t - foundStart->fT) / denom : 1; 5598016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio; 56055888e44171ffd48b591d19256884a969fe4da17caryclark} 56155888e44171ffd48b591d19256884a969fe4da17caryclark 56255888e44171ffd48b591d19256884a969fe4da17caryclark// return true if span overlaps existing and needs to adjust the coincident list 56355888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, 56455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, 56555888e44171ffd48b591d19256884a969fe4da17caryclark double coinTs, double coinTe, double oppTs, double oppTe, 56655888e44171ffd48b591d19256884a969fe4da17caryclark SkTDArray<SkCoincidentSpans*>* overlaps) const { 56755888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinSeg, oppSeg)) { 56855888e44171ffd48b591d19256884a969fe4da17caryclark if (oppTs < oppTe) { 56955888e44171ffd48b591d19256884a969fe4da17caryclark return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe, 57055888e44171ffd48b591d19256884a969fe4da17caryclark overlaps); 57155888e44171ffd48b591d19256884a969fe4da17caryclark } 57255888e44171ffd48b591d19256884a969fe4da17caryclark return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps); 57355888e44171ffd48b591d19256884a969fe4da17caryclark } 57455888e44171ffd48b591d19256884a969fe4da17caryclark bool swapOpp = oppTs > oppTe; 57555888e44171ffd48b591d19256884a969fe4da17caryclark if (swapOpp) { 57655888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 57755888e44171ffd48b591d19256884a969fe4da17caryclark } 57827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark do { 57955888e44171ffd48b591d19256884a969fe4da17caryclark if (check->coinPtTStart()->segment() != coinSeg) { 58055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 58127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 58255888e44171ffd48b591d19256884a969fe4da17caryclark if (check->oppPtTStart()->segment() != oppSeg) { 58355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 58427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 58555888e44171ffd48b591d19256884a969fe4da17caryclark double checkTs = check->coinPtTStart()->fT; 58655888e44171ffd48b591d19256884a969fe4da17caryclark double checkTe = check->coinPtTEnd()->fT; 58755888e44171ffd48b591d19256884a969fe4da17caryclark bool coinOutside = coinTe < checkTs || coinTs > checkTe; 58855888e44171ffd48b591d19256884a969fe4da17caryclark double oCheckTs = check->oppPtTStart()->fT; 58955888e44171ffd48b591d19256884a969fe4da17caryclark double oCheckTe = check->oppPtTEnd()->fT; 59055888e44171ffd48b591d19256884a969fe4da17caryclark if (swapOpp) { 59155888e44171ffd48b591d19256884a969fe4da17caryclark if (oCheckTs <= oCheckTe) { 59281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return false; 59355888e44171ffd48b591d19256884a969fe4da17caryclark } 59455888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oCheckTs, oCheckTe); 59555888e44171ffd48b591d19256884a969fe4da17caryclark } 59655888e44171ffd48b591d19256884a969fe4da17caryclark bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe; 59755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinOutside && oppOutside) { 59855888e44171ffd48b591d19256884a969fe4da17caryclark continue; 59955888e44171ffd48b591d19256884a969fe4da17caryclark } 60055888e44171ffd48b591d19256884a969fe4da17caryclark bool coinInside = coinTe <= checkTe && coinTs >= checkTs; 60155888e44171ffd48b591d19256884a969fe4da17caryclark bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs; 60281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (coinInside && oppInside) { // already included, do nothing 60381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return false; 60455888e44171ffd48b591d19256884a969fe4da17caryclark } 60555888e44171ffd48b591d19256884a969fe4da17caryclark *overlaps->append() = check; // partial overlap, extend existing entry 60655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((check = check->next())); 60726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark return true; 60827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 60927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 61055888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddIfMissing() */ 6118016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark// note that over1s, over1e, over2s, over2e are ordered 6128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclarkbool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s, 613ecc364c42691f24b41a672de1636b3a5f181160aHerb Derby double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added 6148016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) { 6158016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(tStart < tEnd); 6168016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->fT < over1e->fT); 6178016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over1s->fT, tStart, over1e->fT)); 6188016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over1s->fT, tEnd, over1e->fT)); 6198016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over2s->fT < over2e->fT); 6208016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over2s->fT, tStart, over2e->fT)); 6218016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(between(over2s->fT, tEnd, over2e->fT)); 6228016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() == over1e->segment()); 6238016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over2s->segment() == over2e->segment()); 6248016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() == over2s->segment()); 6258016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() != coinSeg); 6268016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(over1s->segment() != oppSeg); 6278016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(coinSeg != oppSeg); 62854359294a7c9dc54802d512a5d891a35c1663392caryclark double coinTs, coinTe, oppTs, oppTe; 6298016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e)); 6308016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e)); 63130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (coinSeg->collapsed(coinTs, coinTe)) { 63281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 63330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 6348016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); 6358016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); 63630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (oppSeg->collapsed(oppTs, oppTe)) { 63781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 63830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 6398016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (coinTs > coinTe) { 64055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinTs, coinTe); 64155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppTs, oppTe); 64255888e44171ffd48b591d19256884a969fe4da17caryclark } 64381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added); 64455888e44171ffd48b591d19256884a969fe4da17caryclark} 64555888e44171ffd48b591d19256884a969fe4da17caryclark 64655888e44171ffd48b591d19256884a969fe4da17caryclark/* Please keep this in sync with debugAddOrOverlap() */ 647025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark// If this is called by addEndMovedSpans(), a returned false propogates out to an abort. 648025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark// If this is called by AddIfMissing(), a returned false indicates there was nothing to add 64955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, 65081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark double coinTs, double coinTe, double oppTs, double oppTe, bool* added) { 65155888e44171ffd48b591d19256884a969fe4da17caryclark SkTDArray<SkCoincidentSpans*> overlaps; 65281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!fTop); 65355888e44171ffd48b591d19256884a969fe4da17caryclark if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { 65481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 65555888e44171ffd48b591d19256884a969fe4da17caryclark } 65655888e44171ffd48b591d19256884a969fe4da17caryclark if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, 65755888e44171ffd48b591d19256884a969fe4da17caryclark coinTe, oppTs, oppTe, &overlaps)) { 65881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 65955888e44171ffd48b591d19256884a969fe4da17caryclark } 66055888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; 66155888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing 66255888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = overlaps[index]; 66355888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) { 66455888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setCoinPtTStart(test->coinPtTStart()); 66554359294a7c9dc54802d512a5d891a35c1663392caryclark } 66655888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) { 66755888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setCoinPtTEnd(test->coinPtTEnd()); 66855888e44171ffd48b591d19256884a969fe4da17caryclark } 66955888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->flipped() 67055888e44171ffd48b591d19256884a969fe4da17caryclark ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT 67155888e44171ffd48b591d19256884a969fe4da17caryclark : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) { 67255888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setOppPtTStart(test->oppPtTStart()); 67354359294a7c9dc54802d512a5d891a35c1663392caryclark } 67455888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->flipped() 67555888e44171ffd48b591d19256884a969fe4da17caryclark ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT 67655888e44171ffd48b591d19256884a969fe4da17caryclark : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { 67755888e44171ffd48b591d19256884a969fe4da17caryclark overlap->setOppPtTEnd(test->oppPtTEnd()); 67855888e44171ffd48b591d19256884a969fe4da17caryclark } 67955888e44171ffd48b591d19256884a969fe4da17caryclark if (!fHead || !this->release(fHead, test)) { 68055888e44171ffd48b591d19256884a969fe4da17caryclark SkAssertResult(this->release(fTop, test)); 68155888e44171ffd48b591d19256884a969fe4da17caryclark } 68255888e44171ffd48b591d19256884a969fe4da17caryclark } 68355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); 68455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); 68581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (overlap && cs && ce && overlap->contains(cs, ce)) { 68681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 68781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 68881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs == ce && cs); 68955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); 69055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); 69181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (overlap && os && oe && overlap->contains(os, oe)) { 69281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 69381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 69455888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!cs || !cs->deleted()); 69555888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!os || !os->deleted()); 69655888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!ce || !ce->deleted()); 69755888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!oe || !oe->deleted()); 69855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; 69955888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; 70081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(csExisting && csExisting == ceExisting); 701e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark// FAIL_IF(csExisting && (csExisting == ce || 702e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark// csExisting->contains(ceExisting ? ceExisting : ce))); 70381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(ceExisting && (ceExisting == cs || 704025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark ceExisting->contains(csExisting ? csExisting : cs))); 70555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; 70655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; 70781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(osExisting && osExisting == oeExisting); 70881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(osExisting && (osExisting == oe || 709025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark osExisting->contains(oeExisting ? oeExisting : oe))); 71081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(oeExisting && (oeExisting == os || 711025b11ecde8733d9b3eee54e132cc50a5ce8eb78caryclark oeExisting->contains(osExisting ? osExisting : os))); 71255888e44171ffd48b591d19256884a969fe4da17caryclark // extra line in debug code 71355888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 71455888e44171ffd48b591d19256884a969fe4da17caryclark if (!cs || !os) { 71555888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) 71629b2563afb1677515739f1d24fb27733626eca92caryclark : coinSeg->addT(coinTs); 717e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark if (csWritable == ce) { 718e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark return true; 719e839e78443e48d4ccad89059b4bc4b3d894fcfddcaryclark } 72055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) 72129b2563afb1677515739f1d24fb27733626eca92caryclark : oppSeg->addT(oppTs); 72281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(!csWritable || !osWritable); 72330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark csWritable->span()->addOpp(osWritable->span()); 72455888e44171ffd48b591d19256884a969fe4da17caryclark cs = csWritable; 72530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark os = osWritable->active(); 72681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted())); 72754359294a7c9dc54802d512a5d891a35c1663392caryclark } 72855888e44171ffd48b591d19256884a969fe4da17caryclark if (!ce || !oe) { 72955888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) 73029b2563afb1677515739f1d24fb27733626eca92caryclark : coinSeg->addT(coinTe); 73155888e44171ffd48b591d19256884a969fe4da17caryclark SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) 73229b2563afb1677515739f1d24fb27733626eca92caryclark : oppSeg->addT(oppTe); 73330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark ceWritable->span()->addOpp(oeWritable->span()); 73455888e44171ffd48b591d19256884a969fe4da17caryclark ce = ceWritable; 73555888e44171ffd48b591d19256884a969fe4da17caryclark oe = oeWritable; 73654359294a7c9dc54802d512a5d891a35c1663392caryclark } 73755888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 73881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs->deleted()); 73981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(os->deleted()); 74081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(ce->deleted()); 74181a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(oe->deleted()); 74281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark FAIL_IF(cs->contains(ce) || os->contains(oe)); 74355888e44171ffd48b591d19256884a969fe4da17caryclark bool result = true; 74455888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap) { 74555888e44171ffd48b591d19256884a969fe4da17caryclark if (overlap->coinPtTStart()->segment() == coinSeg) { 74655888e44171ffd48b591d19256884a969fe4da17caryclark result = overlap->extend(cs, ce, os, oe); 74755888e44171ffd48b591d19256884a969fe4da17caryclark } else { 74855888e44171ffd48b591d19256884a969fe4da17caryclark if (os->fT > oe->fT) { 74955888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(cs, ce); 75055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(os, oe); 75155888e44171ffd48b591d19256884a969fe4da17caryclark } 75255888e44171ffd48b591d19256884a969fe4da17caryclark result = overlap->extend(os, oe, cs, ce); 75355888e44171ffd48b591d19256884a969fe4da17caryclark } 75455888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 75555888e44171ffd48b591d19256884a969fe4da17caryclark if (result) { 75655888e44171ffd48b591d19256884a969fe4da17caryclark overlaps[0]->debugShow(); 75755888e44171ffd48b591d19256884a969fe4da17caryclark } 75855888e44171ffd48b591d19256884a969fe4da17caryclark#endif 75955888e44171ffd48b591d19256884a969fe4da17caryclark } else { 76055888e44171ffd48b591d19256884a969fe4da17caryclark this->add(cs, ce, os, oe); 76155888e44171ffd48b591d19256884a969fe4da17caryclark#if DEBUG_COINCIDENCE_VERBOSE 76255888e44171ffd48b591d19256884a969fe4da17caryclark fHead->debugShow(); 76355888e44171ffd48b591d19256884a969fe4da17caryclark#endif 76455888e44171ffd48b591d19256884a969fe4da17caryclark } 76555888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 76681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark if (result) { 76781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark *added = true; 76881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark } 76981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 77054359294a7c9dc54802d512a5d891a35c1663392caryclark} 77154359294a7c9dc54802d512a5d891a35c1663392caryclark 77255888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugAddMissing() 77327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* detects overlaps of different coincident runs on same segment */ 77427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* does not detect overlaps for pairs without any segments in common */ 77555888e44171ffd48b591d19256884a969fe4da17caryclark// returns true if caller should loop again 776ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS()) { 77727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* outer = fHead; 77881a478ca6c36aac3e53ce0373a281ac8940f4780caryclark *added = false; 77954359294a7c9dc54802d512a5d891a35c1663392caryclark if (!outer) { 78081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 78154359294a7c9dc54802d512a5d891a35c1663392caryclark } 78227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark fTop = outer; 78396fcdcc219d2a0d3579719b84b28bede76efba64halcanary fHead = nullptr; 78454359294a7c9dc54802d512a5d891a35c1663392caryclark do { 78527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark // addifmissing can modify the list that this is walking 78626ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark // save head so that walker can iterate over old data unperturbed 78726ad22ab61539e3d3b6bc5e0da8dcebbd52a53decaryclark // addifmissing adds to head freely then add saved head in the end 7888016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ocs = outer->coinPtTStart(); 789a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(ocs->deleted()); 7908016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* outerCoin = ocs->segment(); 7918016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list 7928016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oos = outer->oppPtTStart(); 793b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (oos->deleted()) { 79481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 795b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 7968016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* outerOpp = oos->segment(); 7974c76c41c981dd7ea95062a1895a6e3415b70bce1Cary Clark SkOPASSERT(!outerOpp->done()); 7988016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin); 7998016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp); 80054359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* inner = outer; 80155888e44171ffd48b591d19256884a969fe4da17caryclark while ((inner = inner->next())) { 80255888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 80354359294a7c9dc54802d512a5d891a35c1663392caryclark double overS, overE; 8048016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ics = inner->coinPtTStart(); 805221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark FAIL_IF(ics->deleted()); 8068016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* innerCoin = ics->segment(); 807a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(innerCoin->done()); 8088016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ios = inner->oppPtTStart(); 809a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(ios->deleted()); 8108016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpSegment* innerOpp = ios->segment(); 8114c76c41c981dd7ea95062a1895a6e3415b70bce1Cary Clark SkOPASSERT(!innerOpp->done()); 8128016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin); 8138016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp); 81455888e44171ffd48b591d19256884a969fe4da17caryclark if (outerCoin == innerCoin) { 8158016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oce = outer->coinPtTEnd(); 816b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (oce->deleted()) { 81781a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 818b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 8198016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ice = inner->coinPtTEnd(); 820595ac28c3990ea89ee40ec14117dc1667acfc126caryclark FAIL_IF(ice->deleted()); 8218016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { 82281a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice), 82381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerOppWritable, innerOppWritable, added 8248016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ocs->debugEnder(oce)) 8258016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ics->debugEnder(ice))); 82655888e44171ffd48b591d19256884a969fe4da17caryclark } 82755888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerCoin == innerOpp) { 8288016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* oce = outer->coinPtTEnd(); 8298016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!oce->deleted()); 8308016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ioe = inner->oppPtTEnd(); 8318016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ioe->deleted()); 8328016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) { 83381a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe), 83481a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerOppWritable, innerCoinWritable, added 8358016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ocs->debugEnder(oce)) 8368016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ios->debugEnder(ioe))); 83755888e44171ffd48b591d19256884a969fe4da17caryclark } 83855888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerOpp == innerCoin) { 8398016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ooe = outer->oppPtTEnd(); 8408016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ooe->deleted()); 8418016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ice = inner->coinPtTEnd(); 8428016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ice->deleted()); 84355888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(outerCoin != innerOpp); 8448016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) { 84581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice), 84681a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerCoinWritable, innerOppWritable, added 8478016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(oos->debugEnder(ooe)) 8488016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ics->debugEnder(ice))); 84955888e44171ffd48b591d19256884a969fe4da17caryclark } 85055888e44171ffd48b591d19256884a969fe4da17caryclark } else if (outerOpp == innerOpp) { 8518016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ooe = outer->oppPtTEnd(); 8528016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkASSERT(!ooe->deleted()); 8538016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark const SkOpPtT* ioe = inner->oppPtTEnd(); 854b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark if (ioe->deleted()) { 85581a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 856b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark } 85755888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(outerCoin != innerCoin); 8588016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { 85981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe), 86081a478ca6c36aac3e53ce0373a281ac8940f4780caryclark overS, overE, outerCoinWritable, innerCoinWritable, added 8618016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(oos->debugEnder(ooe)) 8628016b264ceec2b11d2acbeb77a9fbe66e48368b9caryclark SkDEBUGPARAMS(ios->debugEnder(ioe))); 86354359294a7c9dc54802d512a5d891a35c1663392caryclark } 86454359294a7c9dc54802d512a5d891a35c1663392caryclark } 86555888e44171ffd48b591d19256884a969fe4da17caryclark this->debugValidate(); 86654359294a7c9dc54802d512a5d891a35c1663392caryclark } 86755888e44171ffd48b591d19256884a969fe4da17caryclark } while ((outer = outer->next())); 86855888e44171ffd48b591d19256884a969fe4da17caryclark this->restoreHead(); 86981a478ca6c36aac3e53ce0373a281ac8940f4780caryclark return true; 87027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 87127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 87255888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, 87355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* seg2, const SkOpSegment* seg2o, 87455888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overS, const SkOpPtT* overE) { 875e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* s1 = overS->find(seg1); 876e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* e1 = overE->find(seg1); 877087140153861f4c2a003ce6b22a612acc9cc3cf9caryclark FAIL_IF(!s1); 87840f23780e7ca36818660add0faf783fda81bf0b1Cary Clark FAIL_IF(!e1); 87927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s1->starter(e1)->span()->upCast()->windValue()) { 880e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark s1 = overS->find(seg1o); 881e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark e1 = overE->find(seg1o); 882221a4bb55b51a6ba3882811990581d4bdb6bd539caryclark FAIL_IF(!s1); 88340f23780e7ca36818660add0faf783fda81bf0b1Cary Clark FAIL_IF(!e1); 88427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s1->starter(e1)->span()->upCast()->windValue()) { 8853f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 88627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 88727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 888e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* s2 = overS->find(seg2); 889e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark const SkOpPtT* e2 = overE->find(seg2); 890826167111f80a4251266812cf720ad712bd29446caryclark FAIL_IF(!s2); 891a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!e2); 89227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s2->starter(e2)->span()->upCast()->windValue()) { 893e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark s2 = overS->find(seg2o); 894e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark e2 = overE->find(seg2o); 895a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!s2); 89678a37a53365c24670b050acf993818c435922745caryclark FAIL_IF(!e2); 89727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (!s2->starter(e2)->span()->upCast()->windValue()) { 8983f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 89927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 90027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 90127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (s1->segment() == s2->segment()) { 9023f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 90327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 90427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (s1->fT > e1->fT) { 90527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkTSwap(s1, e1); 90627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkTSwap(s2, e2); 90727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 90855888e44171ffd48b591d19256884a969fe4da17caryclark this->add(s1, e1, s2, e2); 9093f0753d3eccece8ac7f02f6af36d66a96c3dfb26caryclark return true; 91054359294a7c9dc54802d512a5d891a35c1663392caryclark} 91154359294a7c9dc54802d512a5d891a35c1663392caryclark 91255888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const { 91355888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(fHead, seg, opp, oppT)) { 91455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 91555888e44171ffd48b591d19256884a969fe4da17caryclark } 91655888e44171ffd48b591d19256884a969fe4da17caryclark if (this->contains(fTop, seg, opp, oppT)) { 91755888e44171ffd48b591d19256884a969fe4da17caryclark return true; 91855888e44171ffd48b591d19256884a969fe4da17caryclark } 91955888e44171ffd48b591d19256884a969fe4da17caryclark return false; 92055888e44171ffd48b591d19256884a969fe4da17caryclark} 92155888e44171ffd48b591d19256884a969fe4da17caryclark 92255888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg, 92355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* opp, double oppT) const { 92455888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 92555888e44171ffd48b591d19256884a969fe4da17caryclark return false; 92655888e44171ffd48b591d19256884a969fe4da17caryclark } 92755888e44171ffd48b591d19256884a969fe4da17caryclark do { 92855888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp 92955888e44171ffd48b591d19256884a969fe4da17caryclark && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) { 93054359294a7c9dc54802d512a5d891a35c1663392caryclark return true; 93154359294a7c9dc54802d512a5d891a35c1663392caryclark } 93255888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp 93355888e44171ffd48b591d19256884a969fe4da17caryclark && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) { 93455888e44171ffd48b591d19256884a969fe4da17caryclark return true; 93555888e44171ffd48b591d19256884a969fe4da17caryclark } 93655888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 93755888e44171ffd48b591d19256884a969fe4da17caryclark return false; 93855888e44171ffd48b591d19256884a969fe4da17caryclark} 93955888e44171ffd48b591d19256884a969fe4da17caryclark 94055888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 94155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { 94255888e44171ffd48b591d19256884a969fe4da17caryclark const SkCoincidentSpans* test = fHead; 94355888e44171ffd48b591d19256884a969fe4da17caryclark if (!test) { 94455888e44171ffd48b591d19256884a969fe4da17caryclark return false; 94555888e44171ffd48b591d19256884a969fe4da17caryclark } 94655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* coinSeg = coinPtTStart->segment(); 94755888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oppSeg = oppPtTStart->segment(); 94855888e44171ffd48b591d19256884a969fe4da17caryclark if (!Ordered(coinPtTStart, oppPtTStart)) { 94955888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinSeg, oppSeg); 95055888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, oppPtTStart); 95155888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTEnd, oppPtTEnd); 95255888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT > coinPtTEnd->fT) { 95355888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(coinPtTStart, coinPtTEnd); 95455888e44171ffd48b591d19256884a969fe4da17caryclark SkTSwap(oppPtTStart, oppPtTEnd); 95555888e44171ffd48b591d19256884a969fe4da17caryclark } 95655888e44171ffd48b591d19256884a969fe4da17caryclark } 95755888e44171ffd48b591d19256884a969fe4da17caryclark double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 95855888e44171ffd48b591d19256884a969fe4da17caryclark double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT); 95955888e44171ffd48b591d19256884a969fe4da17caryclark do { 96055888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg != test->coinPtTStart()->segment()) { 96155888e44171ffd48b591d19256884a969fe4da17caryclark continue; 96255888e44171ffd48b591d19256884a969fe4da17caryclark } 96355888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTStart->fT < test->coinPtTStart()->fT) { 96455888e44171ffd48b591d19256884a969fe4da17caryclark continue; 96555888e44171ffd48b591d19256884a969fe4da17caryclark } 96655888e44171ffd48b591d19256884a969fe4da17caryclark if (coinPtTEnd->fT > test->coinPtTEnd()->fT) { 96755888e44171ffd48b591d19256884a969fe4da17caryclark continue; 96855888e44171ffd48b591d19256884a969fe4da17caryclark } 96955888e44171ffd48b591d19256884a969fe4da17caryclark if (oppSeg != test->oppPtTStart()->segment()) { 97055888e44171ffd48b591d19256884a969fe4da17caryclark continue; 97155888e44171ffd48b591d19256884a969fe4da17caryclark } 97255888e44171ffd48b591d19256884a969fe4da17caryclark if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 97355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 97455888e44171ffd48b591d19256884a969fe4da17caryclark } 97555888e44171ffd48b591d19256884a969fe4da17caryclark if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 97655888e44171ffd48b591d19256884a969fe4da17caryclark continue; 97755888e44171ffd48b591d19256884a969fe4da17caryclark } 97855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 97955888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 98054359294a7c9dc54802d512a5d891a35c1663392caryclark return false; 98154359294a7c9dc54802d512a5d891a35c1663392caryclark} 98254359294a7c9dc54802d512a5d891a35c1663392caryclark 983ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkvoid SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 984ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 98555888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coin = fHead; 98655888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 98755888e44171ffd48b591d19256884a969fe4da17caryclark return; 98855888e44171ffd48b591d19256884a969fe4da17caryclark } 98955888e44171ffd48b591d19256884a969fe4da17caryclark do { 99055888e44171ffd48b591d19256884a969fe4da17caryclark coin->correctEnds(); 99155888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 99255888e44171ffd48b591d19256884a969fe4da17caryclark} 99355888e44171ffd48b591d19256884a969fe4da17caryclark 99454359294a7c9dc54802d512a5d891a35c1663392caryclark// walk span sets in parallel, moving winding from one to the other 995a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclarkbool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 996ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 99754359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 99854359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 999a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 100054359294a7c9dc54802d512a5d891a35c1663392caryclark } 100154359294a7c9dc54802d512a5d891a35c1663392caryclark do { 10025a2057aee9c6293c3dc78cfb013c06ea707d39e4Cary Clark SkOpSpanBase* startSpan = coin->coinPtTStartWritable()->span(); 10035a2057aee9c6293c3dc78cfb013c06ea707d39e4Cary Clark FAIL_IF(!startSpan->upCastable()); 10045a2057aee9c6293c3dc78cfb013c06ea707d39e4Cary Clark SkOpSpan* start = startSpan->upCast(); 1005182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (start->deleted()) { 1006182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1007182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 100855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 100954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(start == start->starter(end)); 101055888e44171ffd48b591d19256884a969fe4da17caryclark bool flipped = coin->flipped(); 101196dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable() 101296dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark : coin->oppPtTStartWritable())->span(); 101396dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!oStartBase->upCastable()); 101496dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark SkOpSpan* oStart = oStartBase->upCast(); 1015182b499cd75c971f85cdf52c1827b3c220cc9011caryclark if (oStart->deleted()) { 1016182b499cd75c971f85cdf52c1827b3c220cc9011caryclark continue; 1017182b499cd75c971f85cdf52c1827b3c220cc9011caryclark } 101855888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span(); 101954359294a7c9dc54802d512a5d891a35c1663392caryclark SkASSERT(oStart == oStart->starter(oEnd)); 102054359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* segment = start->segment(); 102154359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSegment* oSegment = oStart->segment(); 102254359294a7c9dc54802d512a5d891a35c1663392caryclark bool operandSwap = segment->operand() != oSegment->operand(); 102354359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 1024364a0074c33f91ded60232f173f7a57a312e9280caryclark if (oEnd->deleted()) { 1025364a0074c33f91ded60232f173f7a57a312e9280caryclark continue; 1026364a0074c33f91ded60232f173f7a57a312e9280caryclark } 102754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 102854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = oStart->next(); 102954359294a7c9dc54802d512a5d891a35c1663392caryclark if (oNext == oEnd) { 103054359294a7c9dc54802d512a5d891a35c1663392caryclark break; 103154359294a7c9dc54802d512a5d891a35c1663392caryclark } 103226ae5aba592d4169c1c53aa7fafa660589a4d554Cary Clark FAIL_IF(!oNext->upCastable()); 103354359294a7c9dc54802d512a5d891a35c1663392caryclark oStart = oNext->upCast(); 103454359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 103554359294a7c9dc54802d512a5d891a35c1663392caryclark } 103654359294a7c9dc54802d512a5d891a35c1663392caryclark do { 103754359294a7c9dc54802d512a5d891a35c1663392caryclark int windValue = start->windValue(); 103854359294a7c9dc54802d512a5d891a35c1663392caryclark int oppValue = start->oppValue(); 10391049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int oWindValue = oStart->windValue(); 104054359294a7c9dc54802d512a5d891a35c1663392caryclark int oOppValue = oStart->oppValue(); 104154359294a7c9dc54802d512a5d891a35c1663392caryclark // winding values are added or subtracted depending on direction and wind type 104254359294a7c9dc54802d512a5d891a35c1663392caryclark // same or opposite values are summed depending on the operand value 10431049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int windDiff = operandSwap ? oOppValue : oWindValue; 10441049f1246e7be4ccb68001361efceb8933e6f81ccaryclark int oWindDiff = operandSwap ? oppValue : windValue; 10451049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!flipped) { 10461049f1246e7be4ccb68001361efceb8933e6f81ccaryclark windDiff = -windDiff; 10471049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oWindDiff = -oWindDiff; 10481049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 104955888e44171ffd48b591d19256884a969fe4da17caryclark bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff 105055888e44171ffd48b591d19256884a969fe4da17caryclark && oWindValue <= oWindDiff)); 105155888e44171ffd48b591d19256884a969fe4da17caryclark if (addToStart ? start->done() : oStart->done()) { 105255888e44171ffd48b591d19256884a969fe4da17caryclark addToStart ^= true; 105355888e44171ffd48b591d19256884a969fe4da17caryclark } 105455888e44171ffd48b591d19256884a969fe4da17caryclark if (addToStart) { 105554359294a7c9dc54802d512a5d891a35c1663392caryclark if (operandSwap) { 105654359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oWindValue, oOppValue); 105754359294a7c9dc54802d512a5d891a35c1663392caryclark } 105854359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 105954359294a7c9dc54802d512a5d891a35c1663392caryclark windValue -= oWindValue; 106054359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue -= oOppValue; 106154359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 106254359294a7c9dc54802d512a5d891a35c1663392caryclark windValue += oWindValue; 106354359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue += oOppValue; 106454359294a7c9dc54802d512a5d891a35c1663392caryclark } 10651049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (segment->isXor()) { 106654359294a7c9dc54802d512a5d891a35c1663392caryclark windValue &= 1; 106754359294a7c9dc54802d512a5d891a35c1663392caryclark } 10681049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (segment->oppXor()) { 106954359294a7c9dc54802d512a5d891a35c1663392caryclark oppValue &= 1; 107054359294a7c9dc54802d512a5d891a35c1663392caryclark } 107154359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue = oOppValue = 0; 107254359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 107354359294a7c9dc54802d512a5d891a35c1663392caryclark if (operandSwap) { 107454359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(windValue, oppValue); 107554359294a7c9dc54802d512a5d891a35c1663392caryclark } 107654359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 107754359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue -= windValue; 107854359294a7c9dc54802d512a5d891a35c1663392caryclark oOppValue -= oppValue; 107954359294a7c9dc54802d512a5d891a35c1663392caryclark } else { 108054359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue += windValue; 108154359294a7c9dc54802d512a5d891a35c1663392caryclark oOppValue += oppValue; 108254359294a7c9dc54802d512a5d891a35c1663392caryclark } 10831049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (oSegment->isXor()) { 108454359294a7c9dc54802d512a5d891a35c1663392caryclark oWindValue &= 1; 108554359294a7c9dc54802d512a5d891a35c1663392caryclark } 10861049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (oSegment->oppXor()) { 10871049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oOppValue &= 1; 10881049f1246e7be4ccb68001361efceb8933e6f81ccaryclark } 108954359294a7c9dc54802d512a5d891a35c1663392caryclark windValue = oppValue = 0; 109054359294a7c9dc54802d512a5d891a35c1663392caryclark } 10916c3b9cdcb047afe963c7bcf34834ba2ecccacc33caryclark#if 0 && DEBUG_COINCIDENCE 109255888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(), 109355888e44171ffd48b591d19256884a969fe4da17caryclark start->debugID(), windValue, oppValue); 109455888e44171ffd48b591d19256884a969fe4da17caryclark SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(), 109555888e44171ffd48b591d19256884a969fe4da17caryclark oStart->debugID(), oWindValue, oOppValue); 109655888e44171ffd48b591d19256884a969fe4da17caryclark#endif 109754359294a7c9dc54802d512a5d891a35c1663392caryclark start->setWindValue(windValue); 109854359294a7c9dc54802d512a5d891a35c1663392caryclark start->setOppValue(oppValue); 1099a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(oWindValue == -1); 110054359294a7c9dc54802d512a5d891a35c1663392caryclark oStart->setWindValue(oWindValue); 110154359294a7c9dc54802d512a5d891a35c1663392caryclark oStart->setOppValue(oOppValue); 110254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!windValue && !oppValue) { 110354359294a7c9dc54802d512a5d891a35c1663392caryclark segment->markDone(start); 110454359294a7c9dc54802d512a5d891a35c1663392caryclark } 110554359294a7c9dc54802d512a5d891a35c1663392caryclark if (!oWindValue && !oOppValue) { 110654359294a7c9dc54802d512a5d891a35c1663392caryclark oSegment->markDone(oStart); 110754359294a7c9dc54802d512a5d891a35c1663392caryclark } 110854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = start->next(); 110954359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); 111054359294a7c9dc54802d512a5d891a35c1663392caryclark if (next == end) { 111154359294a7c9dc54802d512a5d891a35c1663392caryclark break; 111254359294a7c9dc54802d512a5d891a35c1663392caryclark } 111396dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!next->upCastable()); 111454359294a7c9dc54802d512a5d891a35c1663392caryclark start = next->upCast(); 11151049f1246e7be4ccb68001361efceb8933e6f81ccaryclark // if the opposite ran out too soon, just reuse the last span 11161049f1246e7be4ccb68001361efceb8933e6f81ccaryclark if (!oNext || !oNext->upCastable()) { 11171049f1246e7be4ccb68001361efceb8933e6f81ccaryclark oNext = oStart; 111854359294a7c9dc54802d512a5d891a35c1663392caryclark } 111954359294a7c9dc54802d512a5d891a35c1663392caryclark oStart = oNext->upCast(); 112054359294a7c9dc54802d512a5d891a35c1663392caryclark } while (true); 112155888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 1122a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark return true; 112354359294a7c9dc54802d512a5d891a35c1663392caryclark} 112454359294a7c9dc54802d512a5d891a35c1663392caryclark 112555888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugRelease() 112655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) { 112755888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 112896fcdcc219d2a0d3579719b84b28bede76efba64halcanary SkCoincidentSpans* prev = nullptr; 112954359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* next; 113054359294a7c9dc54802d512a5d891a35c1663392caryclark do { 113155888e44171ffd48b591d19256884a969fe4da17caryclark next = coin->next(); 113254359294a7c9dc54802d512a5d891a35c1663392caryclark if (coin == remove) { 113354359294a7c9dc54802d512a5d891a35c1663392caryclark if (prev) { 113455888e44171ffd48b591d19256884a969fe4da17caryclark prev->setNext(next); 113555888e44171ffd48b591d19256884a969fe4da17caryclark } else if (head == fHead) { 113654359294a7c9dc54802d512a5d891a35c1663392caryclark fHead = next; 113755888e44171ffd48b591d19256884a969fe4da17caryclark } else { 113855888e44171ffd48b591d19256884a969fe4da17caryclark fTop = next; 113954359294a7c9dc54802d512a5d891a35c1663392caryclark } 114054359294a7c9dc54802d512a5d891a35c1663392caryclark break; 114154359294a7c9dc54802d512a5d891a35c1663392caryclark } 114254359294a7c9dc54802d512a5d891a35c1663392caryclark prev = coin; 114354359294a7c9dc54802d512a5d891a35c1663392caryclark } while ((coin = next)); 114455888e44171ffd48b591d19256884a969fe4da17caryclark return coin != nullptr; 114555888e44171ffd48b591d19256884a969fe4da17caryclark} 114655888e44171ffd48b591d19256884a969fe4da17caryclark 114730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) { 114830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (!coin) { 114930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark return; 115030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 115130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* head = coin; 115230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* prev = nullptr; 115330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkCoincidentSpans* next; 115430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark do { 115530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark next = coin->next(); 115630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (coin->coinPtTStart()->deleted()) { 115730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() : 115830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark coin->oppPtTStart()->deleted()); 115930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark if (prev) { 116030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark prev->setNext(next); 116130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else if (head == fHead) { 116230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark fHead = next; 116330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 116430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark fTop = next; 116530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 116630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } else { 116730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() : 116830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark !coin->oppPtTStart()->deleted()); 116930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark prev = coin; 117030b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } 117130b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark } while ((coin = next)); 117230b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 117330b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 117430b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclarkvoid SkOpCoincidence::releaseDeleted() { 117530b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->releaseDeleted(fHead); 117630b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark this->releaseDeleted(fTop); 117730b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark} 117830b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark 117955888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::restoreHead() { 118055888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans** headPtr = &fHead; 118155888e44171ffd48b591d19256884a969fe4da17caryclark while (*headPtr) { 118255888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = (*headPtr)->nextPtr(); 118355888e44171ffd48b591d19256884a969fe4da17caryclark } 118455888e44171ffd48b591d19256884a969fe4da17caryclark *headPtr = fTop; 118555888e44171ffd48b591d19256884a969fe4da17caryclark fTop = nullptr; 118655888e44171ffd48b591d19256884a969fe4da17caryclark // segments may have collapsed in the meantime; remove empty referenced segments 118755888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = &fHead; 118855888e44171ffd48b591d19256884a969fe4da17caryclark while (*headPtr) { 118955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = *headPtr; 119055888e44171ffd48b591d19256884a969fe4da17caryclark if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) { 119155888e44171ffd48b591d19256884a969fe4da17caryclark *headPtr = test->next(); 119255888e44171ffd48b591d19256884a969fe4da17caryclark continue; 119355888e44171ffd48b591d19256884a969fe4da17caryclark } 119455888e44171ffd48b591d19256884a969fe4da17caryclark headPtr = (*headPtr)->nextPtr(); 119555888e44171ffd48b591d19256884a969fe4da17caryclark } 119655888e44171ffd48b591d19256884a969fe4da17caryclark} 119755888e44171ffd48b591d19256884a969fe4da17caryclark 119855888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugExpand() 119930b9fdd6a1d607bde20c793af65b5e2e8a1737cacaryclark// expand the range by checking adjacent spans for coincidence 1200ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clarkbool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1201ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 120254359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 120354359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 120427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return false; 120554359294a7c9dc54802d512a5d891a35c1663392caryclark } 120627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark bool expanded = false; 120754359294a7c9dc54802d512a5d891a35c1663392caryclark do { 120855888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->expand()) { 120955888e44171ffd48b591d19256884a969fe4da17caryclark // check to see if multiple spans expanded so they are now identical 121055888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* test = fHead; 121155888e44171ffd48b591d19256884a969fe4da17caryclark do { 121255888e44171ffd48b591d19256884a969fe4da17caryclark if (coin == test) { 121355888e44171ffd48b591d19256884a969fe4da17caryclark continue; 121455888e44171ffd48b591d19256884a969fe4da17caryclark } 121555888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart() == test->coinPtTStart() 121655888e44171ffd48b591d19256884a969fe4da17caryclark && coin->oppPtTStart() == test->oppPtTStart()) { 121755888e44171ffd48b591d19256884a969fe4da17caryclark this->release(fHead, test); 121855888e44171ffd48b591d19256884a969fe4da17caryclark break; 121955888e44171ffd48b591d19256884a969fe4da17caryclark } 122055888e44171ffd48b591d19256884a969fe4da17caryclark } while ((test = test->next())); 122155888e44171ffd48b591d19256884a969fe4da17caryclark expanded = true; 122227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 122355888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 122427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark return expanded; 122527c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 122627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 122740f23780e7ca36818660add0faf783fda81bf0b1Cary Clarkbool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps DEBUG_COIN_DECLARE_PARAMS()) const { 1228ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 122996fcdcc219d2a0d3579719b84b28bede76efba64halcanary overlaps->fHead = overlaps->fTop = nullptr; 123027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* outer = fHead; 123127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark while (outer) { 123255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); 123355888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); 123427c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkCoincidentSpans* inner = outer; 123555888e44171ffd48b591d19256884a969fe4da17caryclark while ((inner = inner->next())) { 123655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); 123727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark if (outerCoin == innerCoin) { 123827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; // both winners are the same segment, so there's no additional overlap 123954359294a7c9dc54802d512a5d891a35c1663392caryclark } 124055888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); 124155888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overlapS; 124255888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpPtT* overlapE; 124355888e44171ffd48b591d19256884a969fe4da17caryclark if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(), 124455888e44171ffd48b591d19256884a969fe4da17caryclark outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS, 124555888e44171ffd48b591d19256884a969fe4da17caryclark &overlapE)) 124655888e44171ffd48b591d19256884a969fe4da17caryclark || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(), 124755888e44171ffd48b591d19256884a969fe4da17caryclark outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 124827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark &overlapS, &overlapE)) 124955888e44171ffd48b591d19256884a969fe4da17caryclark || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(), 125055888e44171ffd48b591d19256884a969fe4da17caryclark outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 125127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark &overlapS, &overlapE))) { 125240f23780e7ca36818660add0faf783fda81bf0b1Cary Clark if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, 125340f23780e7ca36818660add0faf783fda81bf0b1Cary Clark overlapS, overlapE)) { 125440f23780e7ca36818660add0faf783fda81bf0b1Cary Clark return false; 125540f23780e7ca36818660add0faf783fda81bf0b1Cary Clark } 1256e47ae2998c1cf944db5743a416583dd0f042b6d9Cary Clark } 125727c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 125855888e44171ffd48b591d19256884a969fe4da17caryclark outer = outer->next(); 125927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark } 126040f23780e7ca36818660add0faf783fda81bf0b1Cary Clark return true; 126127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark} 126227c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 126355888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) { 1264b393a49e5fa7e69ba67692929e9fa2a4e1f6bbb1caryclark SkOPASSERT(deleted != kept); 126555888e44171ffd48b591d19256884a969fe4da17caryclark if (fHead) { 126655888e44171ffd48b591d19256884a969fe4da17caryclark this->fixUp(fHead, deleted, kept); 126755888e44171ffd48b591d19256884a969fe4da17caryclark } 126855888e44171ffd48b591d19256884a969fe4da17caryclark if (fTop) { 126955888e44171ffd48b591d19256884a969fe4da17caryclark this->fixUp(fTop, deleted, kept); 127054359294a7c9dc54802d512a5d891a35c1663392caryclark } 127155888e44171ffd48b591d19256884a969fe4da17caryclark} 127255888e44171ffd48b591d19256884a969fe4da17caryclark 127355888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) { 127455888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 127554359294a7c9dc54802d512a5d891a35c1663392caryclark do { 127655888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart() == deleted) { 127755888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTEnd()->span() == kept->span()) { 127855888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 127927c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 128054359294a7c9dc54802d512a5d891a35c1663392caryclark } 128155888e44171ffd48b591d19256884a969fe4da17caryclark coin->setCoinPtTStart(kept); 128254359294a7c9dc54802d512a5d891a35c1663392caryclark } 128355888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTEnd() == deleted) { 128455888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->span() == kept->span()) { 128555888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 128627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 128754359294a7c9dc54802d512a5d891a35c1663392caryclark } 128855888e44171ffd48b591d19256884a969fe4da17caryclark coin->setCoinPtTEnd(kept); 128955888e44171ffd48b591d19256884a969fe4da17caryclark } 129055888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart() == deleted) { 129155888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTEnd()->span() == kept->span()) { 129255888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 129327c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 129454359294a7c9dc54802d512a5d891a35c1663392caryclark } 129555888e44171ffd48b591d19256884a969fe4da17caryclark coin->setOppPtTStart(kept); 129654359294a7c9dc54802d512a5d891a35c1663392caryclark } 129755888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTEnd() == deleted) { 129855888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->oppPtTStart()->span() == kept->span()) { 129955888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 130027c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark continue; 130154359294a7c9dc54802d512a5d891a35c1663392caryclark } 130255888e44171ffd48b591d19256884a969fe4da17caryclark coin->setOppPtTEnd(kept); 130354359294a7c9dc54802d512a5d891a35c1663392caryclark } 130455888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 130554359294a7c9dc54802d512a5d891a35c1663392caryclark} 130654359294a7c9dc54802d512a5d891a35c1663392caryclark 130755888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep this in sync with debugMark() 130827c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ 1309e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclarkbool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1310ab87d7abf1df007c90bef2e916294ca325d81c81Cary Clark DEBUG_SET_PHASE(); 131154359294a7c9dc54802d512a5d891a35c1663392caryclark SkCoincidentSpans* coin = fHead; 131254359294a7c9dc54802d512a5d891a35c1663392caryclark if (!coin) { 1313e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark return true; 131454359294a7c9dc54802d512a5d891a35c1663392caryclark } 131554359294a7c9dc54802d512a5d891a35c1663392caryclark do { 1316e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span(); 1317e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!startBase->upCastable()); 1318e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark SkOpSpan* start = startBase->upCast(); 1319a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(start->deleted()); 132055888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); 132140f23780e7ca36818660add0faf783fda81bf0b1Cary Clark SkOPASSERT(!end->deleted()); 132255888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); 132340f23780e7ca36818660add0faf783fda81bf0b1Cary Clark SkOPASSERT(!oStart->deleted()); 132455888e44171ffd48b591d19256884a969fe4da17caryclark SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); 132555888e44171ffd48b591d19256884a969fe4da17caryclark SkASSERT(!oEnd->deleted()); 132655888e44171ffd48b591d19256884a969fe4da17caryclark bool flipped = coin->flipped(); 132754359294a7c9dc54802d512a5d891a35c1663392caryclark if (flipped) { 132854359294a7c9dc54802d512a5d891a35c1663392caryclark SkTSwap(oStart, oEnd); 132954359294a7c9dc54802d512a5d891a35c1663392caryclark } 133055888e44171ffd48b591d19256884a969fe4da17caryclark /* coin and opp spans may not match up. Mark the ends, and then let the interior 133155888e44171ffd48b591d19256884a969fe4da17caryclark get marked as many times as the spans allow */ 13329de097639f04e5a18da2d2b123dace9d24ab50e4Cary Clark FAIL_IF(!oStart->upCastable()); 133355888e44171ffd48b591d19256884a969fe4da17caryclark start->insertCoincidence(oStart->upCast()); 133455888e44171ffd48b591d19256884a969fe4da17caryclark end->insertCoinEnd(oEnd); 133555888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* segment = start->segment(); 133655888e44171ffd48b591d19256884a969fe4da17caryclark const SkOpSegment* oSegment = oStart->segment(); 133754359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* next = start; 133854359294a7c9dc54802d512a5d891a35c1663392caryclark SkOpSpanBase* oNext = oStart; 1339a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark bool ordered; 1340a35ab3e6e024d0b548ded26a2e3b8ecd838ead93caryclark FAIL_IF(!coin->ordered(&ordered)); 134155888e44171ffd48b591d19256884a969fe4da17caryclark while ((next = next->upCast()->next()) != end) { 1342e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!next->upCastable()); 134359ed482af72beec6812b28d833d8bdf80ba32df7Cary Clark FAIL_IF(!next->upCast()->insertCoincidence(oSegment, flipped, ordered)); 134455888e44171ffd48b591d19256884a969fe4da17caryclark } 134555888e44171ffd48b591d19256884a969fe4da17caryclark while ((oNext = oNext->upCast()->next()) != oEnd) { 134696dc1c9efaab4636e30f90aa377f25863f9bf3bacaryclark FAIL_IF(!oNext->upCastable()); 1347e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered)); 134855888e44171ffd48b591d19256884a969fe4da17caryclark } 134955888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 1350e6522ea38fa3bcfdf2d718ea5ad898b3b3d46e00caryclark return true; 135155888e44171ffd48b591d19256884a969fe4da17caryclark} 135255888e44171ffd48b591d19256884a969fe4da17caryclark 135355888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep in sync with debugMarkCollapsed() 135455888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) { 135555888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* head = coin; 135655888e44171ffd48b591d19256884a969fe4da17caryclark while (coin) { 135755888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->collapsed(test)) { 135855888e44171ffd48b591d19256884a969fe4da17caryclark if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) { 135955888e44171ffd48b591d19256884a969fe4da17caryclark coin->coinPtTStartWritable()->segment()->markAllDone(); 136054359294a7c9dc54802d512a5d891a35c1663392caryclark } 136155888e44171ffd48b591d19256884a969fe4da17caryclark if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) { 136255888e44171ffd48b591d19256884a969fe4da17caryclark coin->oppPtTStartWritable()->segment()->markAllDone(); 136355888e44171ffd48b591d19256884a969fe4da17caryclark } 136455888e44171ffd48b591d19256884a969fe4da17caryclark this->release(head, coin); 136555888e44171ffd48b591d19256884a969fe4da17caryclark } 136655888e44171ffd48b591d19256884a969fe4da17caryclark coin = coin->next(); 136755888e44171ffd48b591d19256884a969fe4da17caryclark } 136855888e44171ffd48b591d19256884a969fe4da17caryclark} 136955888e44171ffd48b591d19256884a969fe4da17caryclark 137055888e44171ffd48b591d19256884a969fe4da17caryclark// Please keep in sync with debugMarkCollapsed() 137155888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::markCollapsed(SkOpPtT* test) { 137255888e44171ffd48b591d19256884a969fe4da17caryclark markCollapsed(fHead, test); 137355888e44171ffd48b591d19256884a969fe4da17caryclark markCollapsed(fTop, test); 137455888e44171ffd48b591d19256884a969fe4da17caryclark} 137555888e44171ffd48b591d19256884a969fe4da17caryclark 137655888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) { 137755888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg->verb() < oppSeg->verb()) { 137855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 137955888e44171ffd48b591d19256884a969fe4da17caryclark } 138055888e44171ffd48b591d19256884a969fe4da17caryclark if (coinSeg->verb() > oppSeg->verb()) { 138155888e44171ffd48b591d19256884a969fe4da17caryclark return false; 138255888e44171ffd48b591d19256884a969fe4da17caryclark } 138355888e44171ffd48b591d19256884a969fe4da17caryclark int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2; 138455888e44171ffd48b591d19256884a969fe4da17caryclark const SkScalar* cPt = &coinSeg->pts()[0].fX; 138555888e44171ffd48b591d19256884a969fe4da17caryclark const SkScalar* oPt = &oppSeg->pts()[0].fX; 138655888e44171ffd48b591d19256884a969fe4da17caryclark for (int index = 0; index < count; ++index) { 138755888e44171ffd48b591d19256884a969fe4da17caryclark if (*cPt < *oPt) { 138855888e44171ffd48b591d19256884a969fe4da17caryclark return true; 138955888e44171ffd48b591d19256884a969fe4da17caryclark } 139055888e44171ffd48b591d19256884a969fe4da17caryclark if (*cPt > *oPt) { 139155888e44171ffd48b591d19256884a969fe4da17caryclark return false; 139255888e44171ffd48b591d19256884a969fe4da17caryclark } 139355888e44171ffd48b591d19256884a969fe4da17caryclark ++cPt; 139455888e44171ffd48b591d19256884a969fe4da17caryclark ++oPt; 139555888e44171ffd48b591d19256884a969fe4da17caryclark } 13965c5cfe24efe4c728e787447dabffe345080d1fb9caryclark return true; 139754359294a7c9dc54802d512a5d891a35c1663392caryclark} 139854359294a7c9dc54802d512a5d891a35c1663392caryclark 139955888e44171ffd48b591d19256884a969fe4da17caryclarkbool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 140054359294a7c9dc54802d512a5d891a35c1663392caryclark const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { 140127c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark SkASSERT(coin1s->segment() == coin2s->segment()); 140254359294a7c9dc54802d512a5d891a35c1663392caryclark *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); 140354359294a7c9dc54802d512a5d891a35c1663392caryclark *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); 140454359294a7c9dc54802d512a5d891a35c1663392caryclark return *overS < *overE; 140554359294a7c9dc54802d512a5d891a35c1663392caryclark} 140627c8eb8ffd7e221693d840c2b9279d53fe6f03d4caryclark 140755888e44171ffd48b591d19256884a969fe4da17caryclark// Commented-out lines keep this in sync with debugRelease() 140855888e44171ffd48b591d19256884a969fe4da17caryclarkvoid SkOpCoincidence::release(const SkOpSegment* deleted) { 140955888e44171ffd48b591d19256884a969fe4da17caryclark SkCoincidentSpans* coin = fHead; 141055888e44171ffd48b591d19256884a969fe4da17caryclark if (!coin) { 141155888e44171ffd48b591d19256884a969fe4da17caryclark return; 141255888e44171ffd48b591d19256884a969fe4da17caryclark } 141355888e44171ffd48b591d19256884a969fe4da17caryclark do { 141455888e44171ffd48b591d19256884a969fe4da17caryclark if (coin->coinPtTStart()->segment() == deleted 141555888e44171ffd48b591d19256884a969fe4da17caryclark || coin->coinPtTEnd()->segment() == deleted 141655888e44171ffd48b591d19256884a969fe4da17caryclark || coin->oppPtTStart()->segment() == deleted 141755888e44171ffd48b591d19256884a969fe4da17caryclark || coin->oppPtTEnd()->segment() == deleted) { 141855888e44171ffd48b591d19256884a969fe4da17caryclark this->release(fHead, coin); 141955888e44171ffd48b591d19256884a969fe4da17caryclark } 142055888e44171ffd48b591d19256884a969fe4da17caryclark } while ((coin = coin->next())); 142155888e44171ffd48b591d19256884a969fe4da17caryclark} 1422