12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781 |
- /*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "src/core/SkPointPriv.h"
- #include "src/pathops/SkOpCoincidence.h"
- #include "src/pathops/SkOpContour.h"
- #include "src/pathops/SkOpSegment.h"
- #include "src/pathops/SkPathWriter.h"
- #include <utility>
- /*
- After computing raw intersections, post process all segments to:
- - find small collections of points that can be collapsed to a single point
- - find missing intersections to resolve differences caused by different algorithms
- Consider segments containing tiny or small intervals. Consider coincident segments
- because coincidence finds intersections through distance measurement that non-coincident
- intersection tests cannot.
- */
- #define F (false) // discard the edge
- #define T (true) // keep the edge
- static const bool gUnaryActiveEdge[2][2] = {
- // from=0 from=1
- // to=0,1 to=0,1
- {F, T}, {T, F},
- };
- static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = {
- // miFrom=0 miFrom=1
- // miTo=0 miTo=1 miTo=0 miTo=1
- // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
- // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
- {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
- {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
- {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
- {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
- };
- #undef F
- #undef T
- SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr,
- SkOpSpanBase** endPtr, bool* done) {
- if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) {
- return result;
- }
- if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) {
- return result;
- }
- return nullptr;
- }
- SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
- SkOpSpanBase** endPtr, bool* done) {
- SkOpSpan* upSpan = start->upCastable();
- if (upSpan) {
- if (upSpan->windValue() || upSpan->oppValue()) {
- SkOpSpanBase* next = upSpan->next();
- if (!*endPtr) {
- *startPtr = start;
- *endPtr = next;
- }
- if (!upSpan->done()) {
- if (upSpan->windSum() != SK_MinS32) {
- return spanToAngle(start, next);
- }
- *done = false;
- }
- } else {
- SkASSERT(upSpan->done());
- }
- }
- SkOpSpan* downSpan = start->prev();
- // edge leading into junction
- if (downSpan) {
- if (downSpan->windValue() || downSpan->oppValue()) {
- if (!*endPtr) {
- *startPtr = start;
- *endPtr = downSpan;
- }
- if (!downSpan->done()) {
- if (downSpan->windSum() != SK_MinS32) {
- return spanToAngle(start, downSpan);
- }
- *done = false;
- }
- } else {
- SkASSERT(downSpan->done());
- }
- }
- return nullptr;
- }
- SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
- SkOpSpanBase** endPtr, bool* done) {
- SkOpPtT* oPtT = start->ptT()->next();
- SkOpSegment* other = oPtT->segment();
- SkOpSpanBase* oSpan = oPtT->span();
- return other->activeAngleInner(oSpan, startPtr, endPtr, done);
- }
- bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
- SkPathOp op) {
- int sumMiWinding = this->updateWinding(end, start);
- int sumSuWinding = this->updateOppWinding(end, start);
- #if DEBUG_LIMIT_WIND_SUM
- SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
- SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
- #endif
- if (this->operand()) {
- using std::swap;
- swap(sumMiWinding, sumSuWinding);
- }
- return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding);
- }
- bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end,
- SkPathOp op, int* sumMiWinding, int* sumSuWinding) {
- int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
- this->setUpWindings(start, end, sumMiWinding, sumSuWinding,
- &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
- bool miFrom;
- bool miTo;
- bool suFrom;
- bool suTo;
- if (operand()) {
- miFrom = (oppMaxWinding & xorMiMask) != 0;
- miTo = (oppSumWinding & xorMiMask) != 0;
- suFrom = (maxWinding & xorSuMask) != 0;
- suTo = (sumWinding & xorSuMask) != 0;
- } else {
- miFrom = (maxWinding & xorMiMask) != 0;
- miTo = (sumWinding & xorMiMask) != 0;
- suFrom = (oppMaxWinding & xorSuMask) != 0;
- suTo = (oppSumWinding & xorSuMask) != 0;
- }
- bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
- #if DEBUG_ACTIVE_OP
- SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
- __FUNCTION__, debugID(), start->t(), end->t(),
- SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
- #endif
- return result;
- }
- bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
- int sumWinding = updateWinding(end, start);
- return activeWinding(start, end, &sumWinding);
- }
- bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) {
- int maxWinding;
- setUpWinding(start, end, &maxWinding, sumWinding);
- bool from = maxWinding != 0;
- bool to = *sumWinding != 0;
- bool result = gUnaryActiveEdge[from][to];
- return result;
- }
- bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
- SkPathWriter* path) const {
- const SkOpSpan* spanStart = start->starter(end);
- FAIL_IF(spanStart->alreadyAdded());
- const_cast<SkOpSpan*>(spanStart)->markAdded();
- SkDCurveSweep curvePart;
- start->segment()->subDivide(start, end, &curvePart.fCurve);
- curvePart.setCurveHullSweep(fVerb);
- SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb;
- path->deferredMove(start->ptT());
- switch (verb) {
- case SkPath::kLine_Verb:
- FAIL_IF(!path->deferredLine(end->ptT()));
- break;
- case SkPath::kQuad_Verb:
- path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT());
- break;
- case SkPath::kConic_Verb:
- path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(),
- curvePart.fCurve.fConic.fWeight);
- break;
- case SkPath::kCubic_Verb:
- path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(),
- curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT());
- break;
- default:
- SkASSERT(0);
- }
- return true;
- }
- const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const {
- const SkOpSpanBase* test = &fHead;
- const SkOpPtT* testPtT;
- SkPoint pt = this->ptAtT(t);
- do {
- testPtT = test->ptT();
- if (testPtT->fT == t) {
- break;
- }
- if (!this->match(testPtT, this, t, pt)) {
- if (t < testPtT->fT) {
- return nullptr;
- }
- continue;
- }
- if (!opp) {
- return testPtT;
- }
- const SkOpPtT* loop = testPtT->next();
- while (loop != testPtT) {
- if (loop->segment() == this && loop->fT == t && loop->fPt == pt) {
- goto foundMatch;
- }
- loop = loop->next();
- }
- return nullptr;
- } while ((test = test->upCast()->next()));
- foundMatch:
- return opp && !test->contains(opp) ? nullptr : testPtT;
- }
- // break the span so that the coincident part does not change the angle of the remainder
- bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) {
- if (this->contains(newT)) {
- return true;
- }
- this->globalState()->resetAllocatedOpSpan();
- FAIL_IF(!between(0, newT, 1));
- SkOpPtT* newPtT = this->addT(newT);
- *startOver |= this->globalState()->allocatedOpSpan();
- if (!newPtT) {
- return false;
- }
- newPtT->fPt = this->ptAtT(newT);
- SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT);
- if (oppPrev) {
- // const cast away to change linked list; pt/t values stays unchanged
- SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
- writableTest->mergeMatches(newPtT->span());
- writableTest->ptT()->addOpp(newPtT, oppPrev);
- writableTest->checkForCollapsedCoincidence();
- }
- return true;
- }
- // Please keep this in sync with debugAddT()
- SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) {
- debugValidate();
- SkOpSpanBase* spanBase = &fHead;
- do {
- SkOpPtT* result = spanBase->ptT();
- if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) {
- spanBase->bumpSpanAdds();
- return result;
- }
- if (t < result->fT) {
- SkOpSpan* prev = result->span()->prev();
- FAIL_WITH_NULL_IF(!prev);
- // marks in global state that new op span has been allocated
- SkOpSpan* span = this->insert(prev);
- span->init(this, prev, t, pt);
- this->debugValidate();
- #if DEBUG_ADD_T
- SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
- span->segment()->debugID(), span->debugID());
- #endif
- span->bumpSpanAdds();
- return span->ptT();
- }
- FAIL_WITH_NULL_IF(spanBase == &fTail);
- } while ((spanBase = spanBase->upCast()->next()));
- SkASSERT(0);
- return nullptr; // we never get here, but need this to satisfy compiler
- }
- SkOpPtT* SkOpSegment::addT(double t) {
- return addT(t, this->ptAtT(t));
- }
- void SkOpSegment::calcAngles() {
- bool activePrior = !fHead.isCanceled();
- if (activePrior && !fHead.simple()) {
- addStartSpan();
- }
- SkOpSpan* prior = &fHead;
- SkOpSpanBase* spanBase = fHead.next();
- while (spanBase != &fTail) {
- if (activePrior) {
- SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>();
- priorAngle->set(spanBase, prior);
- spanBase->setFromAngle(priorAngle);
- }
- SkOpSpan* span = spanBase->upCast();
- bool active = !span->isCanceled();
- SkOpSpanBase* next = span->next();
- if (active) {
- SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
- angle->set(span, next);
- span->setToAngle(angle);
- }
- activePrior = active;
- prior = span;
- spanBase = next;
- }
- if (activePrior && !fTail.simple()) {
- addEndSpan();
- }
- }
- // Please keep this in sync with debugClearAll()
- void SkOpSegment::clearAll() {
- SkOpSpan* span = &fHead;
- do {
- this->clearOne(span);
- } while ((span = span->next()->upCastable()));
- this->globalState()->coincidence()->release(this);
- }
- // Please keep this in sync with debugClearOne()
- void SkOpSegment::clearOne(SkOpSpan* span) {
- span->setWindValue(0);
- span->setOppValue(0);
- this->markDone(span);
- }
- SkOpSpanBase::Collapsed SkOpSegment::collapsed(double s, double e) const {
- const SkOpSpanBase* span = &fHead;
- do {
- SkOpSpanBase::Collapsed result = span->collapsed(s, e);
- if (SkOpSpanBase::Collapsed::kNo != result) {
- return result;
- }
- } while (span->upCastable() && (span = span->upCast()->next()));
- return SkOpSpanBase::Collapsed::kNo;
- }
- bool SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
- SkOpAngle::IncludeType includeType) {
- SkOpSegment* baseSegment = baseAngle->segment();
- int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
- int sumSuWinding;
- bool binary = includeType >= SkOpAngle::kBinarySingle;
- if (binary) {
- sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
- if (baseSegment->operand()) {
- using std::swap;
- swap(sumMiWinding, sumSuWinding);
- }
- }
- SkOpSegment* nextSegment = nextAngle->segment();
- int maxWinding, sumWinding;
- SkOpSpanBase* last = nullptr;
- if (binary) {
- int oppMaxWinding, oppSumWinding;
- nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
- &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
- if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
- nextAngle, &last)) {
- return false;
- }
- } else {
- nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
- &maxWinding, &sumWinding);
- if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) {
- return false;
- }
- }
- nextAngle->setLastMarked(last);
- return true;
- }
- bool SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
- SkOpAngle::IncludeType includeType) {
- SkOpSegment* baseSegment = baseAngle->segment();
- int sumMiWinding = baseSegment->updateWinding(baseAngle);
- int sumSuWinding;
- bool binary = includeType >= SkOpAngle::kBinarySingle;
- if (binary) {
- sumSuWinding = baseSegment->updateOppWinding(baseAngle);
- if (baseSegment->operand()) {
- using std::swap;
- swap(sumMiWinding, sumSuWinding);
- }
- }
- SkOpSegment* nextSegment = nextAngle->segment();
- int maxWinding, sumWinding;
- SkOpSpanBase* last = nullptr;
- if (binary) {
- int oppMaxWinding, oppSumWinding;
- nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
- &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
- if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
- nextAngle, &last)) {
- return false;
- }
- } else {
- nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
- &maxWinding, &sumWinding);
- if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) {
- return false;
- }
- }
- nextAngle->setLastMarked(last);
- return true;
- }
- // at this point, the span is already ordered, or unorderable
- int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
- SkOpAngle::IncludeType includeType) {
- SkASSERT(includeType != SkOpAngle::kUnaryXor);
- SkOpAngle* firstAngle = this->spanToAngle(end, start);
- if (nullptr == firstAngle || nullptr == firstAngle->next()) {
- return SK_NaN32;
- }
- // if all angles have a computed winding,
- // or if no adjacent angles are orderable,
- // or if adjacent orderable angles have no computed winding,
- // there's nothing to do
- // if two orderable angles are adjacent, and both are next to orderable angles,
- // and one has winding computed, transfer to the other
- SkOpAngle* baseAngle = nullptr;
- bool tryReverse = false;
- // look for counterclockwise transfers
- SkOpAngle* angle = firstAngle->previous();
- SkOpAngle* next = angle->next();
- firstAngle = next;
- do {
- SkOpAngle* prior = angle;
- angle = next;
- next = angle->next();
- SkASSERT(prior->next() == angle);
- SkASSERT(angle->next() == next);
- if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
- baseAngle = nullptr;
- continue;
- }
- int testWinding = angle->starter()->windSum();
- if (SK_MinS32 != testWinding) {
- baseAngle = angle;
- tryReverse = true;
- continue;
- }
- if (baseAngle) {
- ComputeOneSum(baseAngle, angle, includeType);
- baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
- }
- } while (next != firstAngle);
- if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) {
- firstAngle = baseAngle;
- tryReverse = true;
- }
- if (tryReverse) {
- baseAngle = nullptr;
- SkOpAngle* prior = firstAngle;
- do {
- angle = prior;
- prior = angle->previous();
- SkASSERT(prior->next() == angle);
- next = angle->next();
- if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
- baseAngle = nullptr;
- continue;
- }
- int testWinding = angle->starter()->windSum();
- if (SK_MinS32 != testWinding) {
- baseAngle = angle;
- continue;
- }
- if (baseAngle) {
- ComputeOneSumReverse(baseAngle, angle, includeType);
- baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
- }
- } while (prior != firstAngle);
- }
- return start->starter(end)->windSum();
- }
- bool SkOpSegment::contains(double newT) const {
- const SkOpSpanBase* spanBase = &fHead;
- do {
- if (spanBase->ptT()->contains(this, newT)) {
- return true;
- }
- if (spanBase == &fTail) {
- break;
- }
- spanBase = spanBase->upCast()->next();
- } while (true);
- return false;
- }
- void SkOpSegment::release(const SkOpSpan* span) {
- if (span->done()) {
- --fDoneCount;
- }
- --fCount;
- SkOPASSERT(fCount >= fDoneCount);
- }
- #if DEBUG_ANGLE
- // called only by debugCheckNearCoincidence
- double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
- SkDPoint testPt = this->dPtAtT(t);
- SkDLine testPerp = {{ testPt, testPt }};
- SkDVector slope = this->dSlopeAtT(t);
- testPerp[1].fX += slope.fY;
- testPerp[1].fY -= slope.fX;
- SkIntersections i;
- const SkOpSegment* oppSegment = oppAngle->segment();
- (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i);
- double closestDistSq = SK_ScalarInfinity;
- for (int index = 0; index < i.used(); ++index) {
- if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
- continue;
- }
- double testDistSq = testPt.distanceSquared(i.pt(index));
- if (closestDistSq > testDistSq) {
- closestDistSq = testDistSq;
- }
- }
- return closestDistSq;
- }
- #endif
- /*
- The M and S variable name parts stand for the operators.
- Mi stands for Minuend (see wiki subtraction, analogous to difference)
- Su stands for Subtrahend
- The Opp variable name part designates that the value is for the Opposite operator.
- Opposite values result from combining coincident spans.
- */
- SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
- SkOpSpanBase** nextEnd, bool* unsortable, bool* simple,
- SkPathOp op, int xorMiMask, int xorSuMask) {
- SkOpSpanBase* start = *nextStart;
- SkOpSpanBase* end = *nextEnd;
- SkASSERT(start != end);
- int step = start->step(end);
- SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
- if ((*simple = other)) {
- // mark the smaller of startIndex, endIndex done, and all adjacent
- // spans with the same T value (but not 'other' spans)
- #if DEBUG_WINDING
- SkDebugf("%s simple\n", __FUNCTION__);
- #endif
- SkOpSpan* startSpan = start->starter(end);
- if (startSpan->done()) {
- return nullptr;
- }
- markDone(startSpan);
- *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
- return other;
- }
- SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
- SkASSERT(endNear == end); // is this ever not end?
- SkASSERT(endNear);
- SkASSERT(start != endNear);
- SkASSERT((start->t() < endNear->t()) ^ (step < 0));
- // more than one viable candidate -- measure angles to find best
- int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp);
- bool sortable = calcWinding != SK_NaN32;
- if (!sortable) {
- *unsortable = true;
- markDone(start->starter(end));
- return nullptr;
- }
- SkOpAngle* angle = this->spanToAngle(end, start);
- if (angle->unorderable()) {
- *unsortable = true;
- markDone(start->starter(end));
- return nullptr;
- }
- #if DEBUG_SORT
- SkDebugf("%s\n", __FUNCTION__);
- angle->debugLoop();
- #endif
- int sumMiWinding = updateWinding(end, start);
- if (sumMiWinding == SK_MinS32) {
- *unsortable = true;
- markDone(start->starter(end));
- return nullptr;
- }
- int sumSuWinding = updateOppWinding(end, start);
- if (operand()) {
- using std::swap;
- swap(sumMiWinding, sumSuWinding);
- }
- SkOpAngle* nextAngle = angle->next();
- const SkOpAngle* foundAngle = nullptr;
- bool foundDone = false;
- // iterate through the angle, and compute everyone's winding
- SkOpSegment* nextSegment;
- int activeCount = 0;
- do {
- nextSegment = nextAngle->segment();
- bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
- nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
- if (activeAngle) {
- ++activeCount;
- if (!foundAngle || (foundDone && activeCount & 1)) {
- foundAngle = nextAngle;
- foundDone = nextSegment->done(nextAngle);
- }
- }
- if (nextSegment->done()) {
- continue;
- }
- if (!activeAngle) {
- (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr);
- }
- SkOpSpanBase* last = nextAngle->lastMarked();
- if (last) {
- SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
- *chase->append() = last;
- #if DEBUG_WINDING
- SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
- last->segment()->debugID(), last->debugID());
- if (!last->final()) {
- SkDebugf(" windSum=%d", last->upCast()->windSum());
- }
- SkDebugf("\n");
- #endif
- }
- } while ((nextAngle = nextAngle->next()) != angle);
- start->segment()->markDone(start->starter(end));
- if (!foundAngle) {
- return nullptr;
- }
- *nextStart = foundAngle->start();
- *nextEnd = foundAngle->end();
- nextSegment = foundAngle->segment();
- #if DEBUG_WINDING
- SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
- __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
- #endif
- return nextSegment;
- }
- SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase,
- SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) {
- SkOpSpanBase* start = *nextStart;
- SkOpSpanBase* end = *nextEnd;
- SkASSERT(start != end);
- int step = start->step(end);
- SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
- if (other) {
- // mark the smaller of startIndex, endIndex done, and all adjacent
- // spans with the same T value (but not 'other' spans)
- #if DEBUG_WINDING
- SkDebugf("%s simple\n", __FUNCTION__);
- #endif
- SkOpSpan* startSpan = start->starter(end);
- if (startSpan->done()) {
- return nullptr;
- }
- markDone(startSpan);
- *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
- return other;
- }
- SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
- SkASSERT(endNear == end); // is this ever not end?
- SkASSERT(endNear);
- SkASSERT(start != endNear);
- SkASSERT((start->t() < endNear->t()) ^ (step < 0));
- // more than one viable candidate -- measure angles to find best
- int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding);
- bool sortable = calcWinding != SK_NaN32;
- if (!sortable) {
- *unsortable = true;
- markDone(start->starter(end));
- return nullptr;
- }
- SkOpAngle* angle = this->spanToAngle(end, start);
- if (angle->unorderable()) {
- *unsortable = true;
- markDone(start->starter(end));
- return nullptr;
- }
- #if DEBUG_SORT
- SkDebugf("%s\n", __FUNCTION__);
- angle->debugLoop();
- #endif
- int sumWinding = updateWinding(end, start);
- SkOpAngle* nextAngle = angle->next();
- const SkOpAngle* foundAngle = nullptr;
- bool foundDone = false;
- // iterate through the angle, and compute everyone's winding
- SkOpSegment* nextSegment;
- int activeCount = 0;
- do {
- nextSegment = nextAngle->segment();
- bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
- &sumWinding);
- if (activeAngle) {
- ++activeCount;
- if (!foundAngle || (foundDone && activeCount & 1)) {
- foundAngle = nextAngle;
- foundDone = nextSegment->done(nextAngle);
- }
- }
- if (nextSegment->done()) {
- continue;
- }
- if (!activeAngle) {
- (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr);
- }
- SkOpSpanBase* last = nextAngle->lastMarked();
- if (last) {
- SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
- *chase->append() = last;
- #if DEBUG_WINDING
- SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
- last->segment()->debugID(), last->debugID());
- if (!last->final()) {
- SkDebugf(" windSum=%d", last->upCast()->windSum());
- }
- SkDebugf("\n");
- #endif
- }
- } while ((nextAngle = nextAngle->next()) != angle);
- start->segment()->markDone(start->starter(end));
- if (!foundAngle) {
- return nullptr;
- }
- *nextStart = foundAngle->start();
- *nextEnd = foundAngle->end();
- nextSegment = foundAngle->segment();
- #if DEBUG_WINDING
- SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
- __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
- #endif
- return nextSegment;
- }
- SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd,
- bool* unsortable) {
- SkOpSpanBase* start = *nextStart;
- SkOpSpanBase* end = *nextEnd;
- SkASSERT(start != end);
- int step = start->step(end);
- SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
- if (other) {
- // mark the smaller of startIndex, endIndex done, and all adjacent
- // spans with the same T value (but not 'other' spans)
- #if DEBUG_WINDING
- SkDebugf("%s simple\n", __FUNCTION__);
- #endif
- SkOpSpan* startSpan = start->starter(end);
- if (startSpan->done()) {
- return nullptr;
- }
- markDone(startSpan);
- *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
- return other;
- }
- SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \
- : (*nextStart)->prev());
- SkASSERT(endNear == end); // is this ever not end?
- SkASSERT(endNear);
- SkASSERT(start != endNear);
- SkASSERT((start->t() < endNear->t()) ^ (step < 0));
- SkOpAngle* angle = this->spanToAngle(end, start);
- if (!angle || angle->unorderable()) {
- *unsortable = true;
- markDone(start->starter(end));
- return nullptr;
- }
- #if DEBUG_SORT
- SkDebugf("%s\n", __FUNCTION__);
- angle->debugLoop();
- #endif
- SkOpAngle* nextAngle = angle->next();
- const SkOpAngle* foundAngle = nullptr;
- bool foundDone = false;
- // iterate through the angle, and compute everyone's winding
- SkOpSegment* nextSegment;
- int activeCount = 0;
- do {
- if (!nextAngle) {
- return nullptr;
- }
- nextSegment = nextAngle->segment();
- ++activeCount;
- if (!foundAngle || (foundDone && activeCount & 1)) {
- foundAngle = nextAngle;
- if (!(foundDone = nextSegment->done(nextAngle))) {
- break;
- }
- }
- nextAngle = nextAngle->next();
- } while (nextAngle != angle);
- start->segment()->markDone(start->starter(end));
- if (!foundAngle) {
- return nullptr;
- }
- *nextStart = foundAngle->start();
- *nextEnd = foundAngle->end();
- nextSegment = foundAngle->segment();
- #if DEBUG_WINDING
- SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
- __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
- #endif
- return nextSegment;
- }
- SkOpGlobalState* SkOpSegment::globalState() const {
- return contour()->globalState();
- }
- void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
- fContour = contour;
- fNext = nullptr;
- fPts = pts;
- fWeight = weight;
- fVerb = verb;
- fCount = 0;
- fDoneCount = 0;
- fVisited = false;
- SkOpSpan* zeroSpan = &fHead;
- zeroSpan->init(this, nullptr, 0, fPts[0]);
- SkOpSpanBase* oneSpan = &fTail;
- zeroSpan->setNext(oneSpan);
- oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
- SkDEBUGCODE(fID = globalState()->nextSegmentID());
- }
- bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
- SkDPoint cPt = this->dPtAtT(t);
- SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t);
- SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
- SkIntersections i;
- (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i);
- int used = i.used();
- for (int index = 0; index < used; ++index) {
- if (cPt.roughlyEqual(i.pt(index))) {
- return true;
- }
- }
- return false;
- }
- bool SkOpSegment::isXor() const {
- return fContour->isXor();
- }
- void SkOpSegment::markAllDone() {
- SkOpSpan* span = this->head();
- do {
- this->markDone(span);
- } while ((span = span->next()->upCastable()));
- }
- bool SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found) {
- int step = start->step(end);
- SkOpSpan* minSpan = start->starter(end);
- markDone(minSpan);
- SkOpSpanBase* last = nullptr;
- SkOpSegment* other = this;
- SkOpSpan* priorDone = nullptr;
- SkOpSpan* lastDone = nullptr;
- int safetyNet = 100000;
- while ((other = other->nextChase(&start, &step, &minSpan, &last))) {
- if (!--safetyNet) {
- return false;
- }
- if (other->done()) {
- SkASSERT(!last);
- break;
- }
- if (lastDone == minSpan || priorDone == minSpan) {
- if (found) {
- *found = nullptr;
- }
- return true;
- }
- other->markDone(minSpan);
- priorDone = lastDone;
- lastDone = minSpan;
- }
- if (found) {
- *found = last;
- }
- return true;
- }
- bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
- SkOpSpanBase** lastPtr) {
- SkOpSpan* spanStart = start->starter(end);
- int step = start->step(end);
- bool success = markWinding(spanStart, winding);
- SkOpSpanBase* last = nullptr;
- SkOpSegment* other = this;
- int safetyNet = 100000;
- while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
- if (!--safetyNet) {
- return false;
- }
- if (spanStart->windSum() != SK_MinS32) {
- // SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive?
- SkASSERT(!last);
- break;
- }
- (void) other->markWinding(spanStart, winding);
- }
- if (lastPtr) {
- *lastPtr = last;
- }
- return success;
- }
- bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end,
- int winding, int oppWinding, SkOpSpanBase** lastPtr) {
- SkOpSpan* spanStart = start->starter(end);
- int step = start->step(end);
- bool success = markWinding(spanStart, winding, oppWinding);
- SkOpSpanBase* last = nullptr;
- SkOpSegment* other = this;
- int safetyNet = 100000;
- while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
- if (!--safetyNet) {
- return false;
- }
- if (spanStart->windSum() != SK_MinS32) {
- if (this->operand() == other->operand()) {
- if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) {
- this->globalState()->setWindingFailed();
- return true; // ... but let it succeed anyway
- }
- } else {
- FAIL_IF(spanStart->windSum() != oppWinding);
- FAIL_IF(spanStart->oppSum() != winding);
- }
- SkASSERT(!last);
- break;
- }
- if (this->operand() == other->operand()) {
- (void) other->markWinding(spanStart, winding, oppWinding);
- } else {
- (void) other->markWinding(spanStart, oppWinding, winding);
- }
- }
- if (lastPtr) {
- *lastPtr = last;
- }
- return success;
- }
- bool SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle,
- SkOpSpanBase** result) {
- SkASSERT(angle->segment() == this);
- if (UseInnerWinding(maxWinding, sumWinding)) {
- maxWinding = sumWinding;
- }
- if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, result)) {
- return false;
- }
- #if DEBUG_WINDING
- SkOpSpanBase* last = *result;
- if (last) {
- SkDebugf("%s last seg=%d span=%d", __FUNCTION__,
- last->segment()->debugID(), last->debugID());
- if (!last->final()) {
- SkDebugf(" windSum=");
- SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
- }
- SkDebugf("\n");
- }
- #endif
- return true;
- }
- bool SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
- int oppSumWinding, const SkOpAngle* angle, SkOpSpanBase** result) {
- SkASSERT(angle->segment() == this);
- if (UseInnerWinding(maxWinding, sumWinding)) {
- maxWinding = sumWinding;
- }
- if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
- oppMaxWinding = oppSumWinding;
- }
- // caller doesn't require that this marks anything
- if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, result)) {
- return false;
- }
- #if DEBUG_WINDING
- if (result) {
- SkOpSpanBase* last = *result;
- if (last) {
- SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
- last->segment()->debugID(), last->debugID());
- if (!last->final()) {
- SkDebugf(" windSum=");
- SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
- }
- SkDebugf(" \n");
- }
- }
- #endif
- return true;
- }
- void SkOpSegment::markDone(SkOpSpan* span) {
- SkASSERT(this == span->segment());
- if (span->done()) {
- return;
- }
- #if DEBUG_MARK_DONE
- debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum());
- #endif
- span->setDone(true);
- ++fDoneCount;
- debugValidate();
- }
- bool SkOpSegment::markWinding(SkOpSpan* span, int winding) {
- SkASSERT(this == span->segment());
- SkASSERT(winding);
- if (span->done()) {
- return false;
- }
- #if DEBUG_MARK_DONE
- debugShowNewWinding(__FUNCTION__, span, winding);
- #endif
- span->setWindSum(winding);
- debugValidate();
- return true;
- }
- bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
- SkASSERT(this == span->segment());
- SkASSERT(winding || oppWinding);
- if (span->done()) {
- return false;
- }
- #if DEBUG_MARK_DONE
- debugShowNewWinding(__FUNCTION__, span, winding, oppWinding);
- #endif
- span->setWindSum(winding);
- span->setOppSum(oppWinding);
- debugValidate();
- return true;
- }
- bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
- const SkPoint& testPt) const {
- SkASSERT(this == base->segment());
- if (this == testParent) {
- if (precisely_equal(base->fT, testT)) {
- return true;
- }
- }
- if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
- return false;
- }
- return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
- }
- static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
- if (last) {
- *last = endSpan;
- }
- return nullptr;
- }
- SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr,
- SkOpSpanBase** last) const {
- SkOpSpanBase* origStart = *startPtr;
- int step = *stepPtr;
- SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev();
- SkASSERT(endSpan);
- SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle();
- SkOpSpanBase* foundSpan;
- SkOpSpanBase* otherEnd;
- SkOpSegment* other;
- if (angle == nullptr) {
- if (endSpan->t() != 0 && endSpan->t() != 1) {
- return nullptr;
- }
- SkOpPtT* otherPtT = endSpan->ptT()->next();
- other = otherPtT->segment();
- foundSpan = otherPtT->span();
- otherEnd = step > 0
- ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr
- : foundSpan->prev();
- } else {
- int loopCount = angle->loopCount();
- if (loopCount > 2) {
- return set_last(last, endSpan);
- }
- const SkOpAngle* next = angle->next();
- if (nullptr == next) {
- return nullptr;
- }
- #if DEBUG_WINDING
- if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor()
- && !next->segment()->contour()->isXor()) {
- SkDebugf("%s mismatched signs\n", __FUNCTION__);
- }
- #endif
- other = next->segment();
- foundSpan = endSpan = next->start();
- otherEnd = next->end();
- }
- if (!otherEnd) {
- return nullptr;
- }
- int foundStep = foundSpan->step(otherEnd);
- if (*stepPtr != foundStep) {
- return set_last(last, endSpan);
- }
- SkASSERT(*startPtr);
- // SkASSERT(otherEnd >= 0);
- SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast();
- SkOpSpan* foundMin = foundSpan->starter(otherEnd);
- if (foundMin->windValue() != origMin->windValue()
- || foundMin->oppValue() != origMin->oppValue()) {
- return set_last(last, endSpan);
- }
- *startPtr = foundSpan;
- *stepPtr = foundStep;
- if (minPtr) {
- *minPtr = foundMin;
- }
- return other;
- }
- // Please keep this in sync with DebugClearVisited()
- void SkOpSegment::ClearVisited(SkOpSpanBase* span) {
- // reset visited flag back to false
- do {
- SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
- while ((ptT = ptT->next()) != stopPtT) {
- SkOpSegment* opp = ptT->segment();
- opp->resetVisited();
- }
- } while (!span->final() && (span = span->upCast()->next()));
- }
- // Please keep this in sync with debugMissingCoincidence()
- // look for pairs of undetected coincident curves
- // assumes that segments going in have visited flag clear
- // Even though pairs of curves correct detect coincident runs, a run may be missed
- // if the coincidence is a product of multiple intersections. For instance, given
- // curves A, B, and C:
- // A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
- // the end of C that the intersection is replaced with the end of C.
- // Even though A-B correctly do not detect an intersection at point 2,
- // the resulting run from point 1 to point 2 is coincident on A and B.
- bool SkOpSegment::missingCoincidence() {
- if (this->done()) {
- return false;
- }
- SkOpSpan* prior = nullptr;
- SkOpSpanBase* spanBase = &fHead;
- bool result = false;
- int safetyNet = 100000;
- do {
- SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
- SkOPASSERT(ptT->span() == spanBase);
- while ((ptT = ptT->next()) != spanStopPtT) {
- if (!--safetyNet) {
- return false;
- }
- if (ptT->deleted()) {
- continue;
- }
- SkOpSegment* opp = ptT->span()->segment();
- if (opp->done()) {
- continue;
- }
- // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
- if (!opp->visited()) {
- continue;
- }
- if (spanBase == &fHead) {
- continue;
- }
- if (ptT->segment() == this) {
- continue;
- }
- SkOpSpan* span = spanBase->upCastable();
- // FIXME?: this assumes that if the opposite segment is coincident then no more
- // coincidence needs to be detected. This may not be true.
- if (span && span->containsCoincidence(opp)) {
- continue;
- }
- if (spanBase->containsCoinEnd(opp)) {
- continue;
- }
- SkOpPtT* priorPtT = nullptr, * priorStopPtT;
- // find prior span containing opp segment
- SkOpSegment* priorOpp = nullptr;
- SkOpSpan* priorTest = spanBase->prev();
- while (!priorOpp && priorTest) {
- priorStopPtT = priorPtT = priorTest->ptT();
- while ((priorPtT = priorPtT->next()) != priorStopPtT) {
- if (priorPtT->deleted()) {
- continue;
- }
- SkOpSegment* segment = priorPtT->span()->segment();
- if (segment == opp) {
- prior = priorTest;
- priorOpp = opp;
- break;
- }
- }
- priorTest = priorTest->prev();
- }
- if (!priorOpp) {
- continue;
- }
- if (priorPtT == ptT) {
- continue;
- }
- SkOpPtT* oppStart = prior->ptT();
- SkOpPtT* oppEnd = spanBase->ptT();
- bool swapped = priorPtT->fT > ptT->fT;
- if (swapped) {
- using std::swap;
- swap(priorPtT, ptT);
- swap(oppStart, oppEnd);
- }
- SkOpCoincidence* coincidences = this->globalState()->coincidence();
- SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
- SkOpPtT* rootPtT = ptT->span()->ptT();
- SkOpPtT* rootOppStart = oppStart->span()->ptT();
- SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
- if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
- goto swapBack;
- }
- if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
- // mark coincidence
- #if DEBUG_COINCIDENCE_VERBOSE
- SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
- rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
- rootOppEnd->debugID());
- #endif
- if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
- coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
- }
- #if DEBUG_COINCIDENCE
- SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd));
- #endif
- result = true;
- }
- swapBack:
- if (swapped) {
- using std::swap;
- swap(priorPtT, ptT);
- }
- }
- } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
- ClearVisited(&fHead);
- return result;
- }
- // please keep this in sync with debugMoveMultiples()
- // if a span has more than one intersection, merge the other segments' span as needed
- bool SkOpSegment::moveMultiples() {
- debugValidate();
- SkOpSpanBase* test = &fHead;
- do {
- int addCount = test->spanAddsCount();
- // FAIL_IF(addCount < 1);
- if (addCount <= 1) {
- continue;
- }
- SkOpPtT* startPtT = test->ptT();
- SkOpPtT* testPtT = startPtT;
- int safetyHatch = 1000000;
- do { // iterate through all spans associated with start
- if (!--safetyHatch) {
- return false;
- }
- SkOpSpanBase* oppSpan = testPtT->span();
- if (oppSpan->spanAddsCount() == addCount) {
- continue;
- }
- if (oppSpan->deleted()) {
- continue;
- }
- SkOpSegment* oppSegment = oppSpan->segment();
- if (oppSegment == this) {
- continue;
- }
- // find range of spans to consider merging
- SkOpSpanBase* oppPrev = oppSpan;
- SkOpSpanBase* oppFirst = oppSpan;
- while ((oppPrev = oppPrev->prev())) {
- if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
- break;
- }
- if (oppPrev->spanAddsCount() == addCount) {
- continue;
- }
- if (oppPrev->deleted()) {
- continue;
- }
- oppFirst = oppPrev;
- }
- SkOpSpanBase* oppNext = oppSpan;
- SkOpSpanBase* oppLast = oppSpan;
- while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
- if (!roughly_equal(oppNext->t(), oppSpan->t())) {
- break;
- }
- if (oppNext->spanAddsCount() == addCount) {
- continue;
- }
- if (oppNext->deleted()) {
- continue;
- }
- oppLast = oppNext;
- }
- if (oppFirst == oppLast) {
- continue;
- }
- SkOpSpanBase* oppTest = oppFirst;
- do {
- if (oppTest == oppSpan) {
- continue;
- }
- // check to see if the candidate meets specific criteria:
- // it contains spans of segments in test's loop but not including 'this'
- SkOpPtT* oppStartPtT = oppTest->ptT();
- SkOpPtT* oppPtT = oppStartPtT;
- while ((oppPtT = oppPtT->next()) != oppStartPtT) {
- SkOpSegment* oppPtTSegment = oppPtT->segment();
- if (oppPtTSegment == this) {
- goto tryNextSpan;
- }
- SkOpPtT* matchPtT = startPtT;
- do {
- if (matchPtT->segment() == oppPtTSegment) {
- goto foundMatch;
- }
- } while ((matchPtT = matchPtT->next()) != startPtT);
- goto tryNextSpan;
- foundMatch: // merge oppTest and oppSpan
- oppSegment->debugValidate();
- oppTest->mergeMatches(oppSpan);
- oppTest->addOpp(oppSpan);
- oppSegment->debugValidate();
- goto checkNextSpan;
- }
- tryNextSpan:
- ;
- } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
- } while ((testPtT = testPtT->next()) != startPtT);
- checkNextSpan:
- ;
- } while ((test = test->final() ? nullptr : test->upCast()->next()));
- debugValidate();
- return true;
- }
- // adjacent spans may have points close by
- bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan,
- bool* found) const {
- const SkOpPtT* refHead = refSpan->ptT();
- const SkOpPtT* checkHead = checkSpan->ptT();
- // if the first pt pair from adjacent spans are far apart, assume that all are far enough apart
- if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) {
- #if DEBUG_COINCIDENCE
- // verify that no combination of points are close
- const SkOpPtT* dBugRef = refHead;
- do {
- const SkOpPtT* dBugCheck = checkHead;
- do {
- SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
- dBugCheck = dBugCheck->next();
- } while (dBugCheck != checkHead);
- dBugRef = dBugRef->next();
- } while (dBugRef != refHead);
- #endif
- *found = false;
- return true;
- }
- // check only unique points
- SkScalar distSqBest = SK_ScalarMax;
- const SkOpPtT* refBest = nullptr;
- const SkOpPtT* checkBest = nullptr;
- const SkOpPtT* ref = refHead;
- do {
- if (ref->deleted()) {
- continue;
- }
- while (ref->ptAlreadySeen(refHead)) {
- ref = ref->next();
- if (ref == refHead) {
- goto doneCheckingDistance;
- }
- }
- const SkOpPtT* check = checkHead;
- const SkOpSegment* refSeg = ref->segment();
- int escapeHatch = 100000; // defend against infinite loops
- do {
- if (check->deleted()) {
- continue;
- }
- while (check->ptAlreadySeen(checkHead)) {
- check = check->next();
- if (check == checkHead) {
- goto nextRef;
- }
- }
- SkScalar distSq = SkPointPriv::DistanceToSqd(ref->fPt, check->fPt);
- if (distSqBest > distSq && (refSeg != check->segment()
- || !refSeg->ptsDisjoint(*ref, *check))) {
- distSqBest = distSq;
- refBest = ref;
- checkBest = check;
- }
- if (--escapeHatch <= 0) {
- return false;
- }
- } while ((check = check->next()) != checkHead);
- nextRef:
- ;
- } while ((ref = ref->next()) != refHead);
- doneCheckingDistance:
- *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT,
- checkBest->fPt);
- return true;
- }
- // Please keep this function in sync with debugMoveNearby()
- // Move nearby t values and pts so they all hang off the same span. Alignment happens later.
- bool SkOpSegment::moveNearby() {
- debugValidate();
- // release undeleted spans pointing to this seg that are linked to the primary span
- SkOpSpanBase* spanBase = &fHead;
- int escapeHatch = 9999; // the largest count for a regular test is 50; for a fuzzer, 500
- do {
- SkOpPtT* ptT = spanBase->ptT();
- const SkOpPtT* headPtT = ptT;
- while ((ptT = ptT->next()) != headPtT) {
- if (!--escapeHatch) {
- return false;
- }
- SkOpSpanBase* test = ptT->span();
- if (ptT->segment() == this && !ptT->deleted() && test != spanBase
- && test->ptT() == ptT) {
- if (test->final()) {
- if (spanBase == &fHead) {
- this->clearAll();
- return true;
- }
- spanBase->upCast()->release(ptT);
- } else if (test->prev()) {
- test->upCast()->release(headPtT);
- }
- break;
- }
- }
- spanBase = spanBase->upCast()->next();
- } while (!spanBase->final());
- // This loop looks for adjacent spans which are near by
- spanBase = &fHead;
- do { // iterate through all spans associated with start
- SkOpSpanBase* test = spanBase->upCast()->next();
- bool found;
- if (!this->spansNearby(spanBase, test, &found)) {
- return false;
- }
- if (found) {
- if (test->final()) {
- if (spanBase->prev()) {
- test->merge(spanBase->upCast());
- } else {
- this->clearAll();
- return true;
- }
- } else {
- spanBase->merge(test->upCast());
- }
- }
- spanBase = test;
- } while (!spanBase->final());
- debugValidate();
- return true;
- }
- bool SkOpSegment::operand() const {
- return fContour->operand();
- }
- bool SkOpSegment::oppXor() const {
- return fContour->oppXor();
- }
- bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const {
- if (fVerb == SkPath::kLine_Verb) {
- return false;
- }
- // quads (and cubics) can loop back to nearly a line so that an opposite curve
- // hits in two places with very different t values.
- // OPTIMIZATION: curves could be preflighted so that, for example, something like
- // 'controls contained by ends' could avoid this check for common curves
- // 'ends are extremes in x or y' is cheaper to compute and real-world common
- // on the other hand, the below check is relatively inexpensive
- double midT = (t1 + t2) / 2;
- SkPoint midPt = this->ptAtT(midT);
- double seDistSq = SkTMax(SkPointPriv::DistanceToSqd(pt1, pt2) * 2, FLT_EPSILON * 2);
- return SkPointPriv::DistanceToSqd(midPt, pt1) > seDistSq ||
- SkPointPriv::DistanceToSqd(midPt, pt2) > seDistSq;
- }
- void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
- int* maxWinding, int* sumWinding) {
- int deltaSum = SpanSign(start, end);
- *maxWinding = *sumMiWinding;
- *sumWinding = *sumMiWinding -= deltaSum;
- SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
- }
- void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
- int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding,
- int* oppSumWinding) {
- int deltaSum = SpanSign(start, end);
- int oppDeltaSum = OppSign(start, end);
- if (operand()) {
- *maxWinding = *sumSuWinding;
- *sumWinding = *sumSuWinding -= deltaSum;
- *oppMaxWinding = *sumMiWinding;
- *oppSumWinding = *sumMiWinding -= oppDeltaSum;
- } else {
- *maxWinding = *sumMiWinding;
- *sumWinding = *sumMiWinding -= deltaSum;
- *oppMaxWinding = *sumSuWinding;
- *oppSumWinding = *sumSuWinding -= oppDeltaSum;
- }
- SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
- SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
- }
- bool SkOpSegment::sortAngles() {
- SkOpSpanBase* span = &this->fHead;
- do {
- SkOpAngle* fromAngle = span->fromAngle();
- SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle();
- if (!fromAngle && !toAngle) {
- continue;
- }
- #if DEBUG_ANGLE
- bool wroteAfterHeader = false;
- #endif
- SkOpAngle* baseAngle = fromAngle;
- if (fromAngle && toAngle) {
- #if DEBUG_ANGLE
- SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(),
- span->debugID());
- wroteAfterHeader = true;
- #endif
- FAIL_IF(!fromAngle->insert(toAngle));
- } else if (!fromAngle) {
- baseAngle = toAngle;
- }
- SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
- int safetyNet = 1000000;
- do {
- if (!--safetyNet) {
- return false;
- }
- SkOpSpanBase* oSpan = ptT->span();
- if (oSpan == span) {
- continue;
- }
- SkOpAngle* oAngle = oSpan->fromAngle();
- if (oAngle) {
- #if DEBUG_ANGLE
- if (!wroteAfterHeader) {
- SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
- span->t(), span->debugID());
- wroteAfterHeader = true;
- }
- #endif
- if (!oAngle->loopContains(baseAngle)) {
- baseAngle->insert(oAngle);
- }
- }
- if (!oSpan->final()) {
- oAngle = oSpan->upCast()->toAngle();
- if (oAngle) {
- #if DEBUG_ANGLE
- if (!wroteAfterHeader) {
- SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
- span->t(), span->debugID());
- wroteAfterHeader = true;
- }
- #endif
- if (!oAngle->loopContains(baseAngle)) {
- baseAngle->insert(oAngle);
- }
- }
- }
- } while ((ptT = ptT->next()) != stopPtT);
- if (baseAngle->loopCount() == 1) {
- span->setFromAngle(nullptr);
- if (toAngle) {
- span->upCast()->setToAngle(nullptr);
- }
- baseAngle = nullptr;
- }
- #if DEBUG_SORT
- SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
- #endif
- } while (!span->final() && (span = span->upCast()->next()));
- return true;
- }
- bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
- SkDCurve* edge) const {
- SkASSERT(start != end);
- const SkOpPtT& startPtT = *start->ptT();
- const SkOpPtT& endPtT = *end->ptT();
- SkDEBUGCODE(edge->fVerb = fVerb);
- edge->fCubic[0].set(startPtT.fPt);
- int points = SkPathOpsVerbToPoints(fVerb);
- edge->fCubic[points].set(endPtT.fPt);
- if (fVerb == SkPath::kLine_Verb) {
- return false;
- }
- double startT = startPtT.fT;
- double endT = endPtT.fT;
- if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
- // don't compute midpoints if we already have them
- if (fVerb == SkPath::kQuad_Verb) {
- edge->fLine[1].set(fPts[1]);
- return false;
- }
- if (fVerb == SkPath::kConic_Verb) {
- edge->fConic[1].set(fPts[1]);
- edge->fConic.fWeight = fWeight;
- return false;
- }
- SkASSERT(fVerb == SkPath::kCubic_Verb);
- if (startT == 0) {
- edge->fCubic[1].set(fPts[1]);
- edge->fCubic[2].set(fPts[2]);
- return false;
- }
- edge->fCubic[1].set(fPts[2]);
- edge->fCubic[2].set(fPts[1]);
- return false;
- }
- if (fVerb == SkPath::kQuad_Verb) {
- edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT);
- } else if (fVerb == SkPath::kConic_Verb) {
- edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2],
- startT, endT, &edge->fConic.fWeight);
- } else {
- SkASSERT(fVerb == SkPath::kCubic_Verb);
- SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]);
- }
- return true;
- }
- bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
- const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const {
- // average t, find mid pt
- double midT = (prior->t() + spanBase->t()) / 2;
- SkPoint midPt = this->ptAtT(midT);
- bool coincident = true;
- // if the mid pt is not near either end pt, project perpendicular through opp seg
- if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
- && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
- if (priorPtT->span() == ptT->span()) {
- return false;
- }
- coincident = false;
- SkIntersections i;
- SkDCurve curvePart;
- this->subDivide(prior, spanBase, &curvePart);
- SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f);
- SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f);
- SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}};
- SkDCurve oppPart;
- opp->subDivide(priorPtT->span(), ptT->span(), &oppPart);
- (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i);
- // measure distance and see if it's small enough to denote coincidence
- for (int index = 0; index < i.used(); ++index) {
- if (!between(0, i[0][index], 1)) {
- continue;
- }
- SkDPoint oppPt = i.pt(index);
- if (oppPt.approximatelyDEqual(midPt)) {
- // the coincidence can occur at almost any angle
- coincident = true;
- }
- }
- }
- return coincident;
- }
- SkOpSpan* SkOpSegment::undoneSpan() {
- SkOpSpan* span = &fHead;
- SkOpSpanBase* next;
- do {
- next = span->next();
- if (!span->done()) {
- return span;
- }
- } while (!next->final() && (span = next->upCast()));
- return nullptr;
- }
- int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
- const SkOpSpan* lesser = start->starter(end);
- int oppWinding = lesser->oppSum();
- int oppSpanWinding = SkOpSegment::OppSign(start, end);
- if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
- && oppWinding != SK_MaxS32) {
- oppWinding -= oppSpanWinding;
- }
- return oppWinding;
- }
- int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
- const SkOpSpanBase* startSpan = angle->start();
- const SkOpSpanBase* endSpan = angle->end();
- return updateOppWinding(endSpan, startSpan);
- }
- int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
- const SkOpSpanBase* startSpan = angle->start();
- const SkOpSpanBase* endSpan = angle->end();
- return updateOppWinding(startSpan, endSpan);
- }
- int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
- SkOpSpan* lesser = start->starter(end);
- int winding = lesser->windSum();
- if (winding == SK_MinS32) {
- winding = lesser->computeWindSum();
- }
- if (winding == SK_MinS32) {
- return winding;
- }
- int spanWinding = SkOpSegment::SpanSign(start, end);
- if (winding && UseInnerWinding(winding - spanWinding, winding)
- && winding != SK_MaxS32) {
- winding -= spanWinding;
- }
- return winding;
- }
- int SkOpSegment::updateWinding(SkOpAngle* angle) {
- SkOpSpanBase* startSpan = angle->start();
- SkOpSpanBase* endSpan = angle->end();
- return updateWinding(endSpan, startSpan);
- }
- int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) {
- SkOpSpanBase* startSpan = angle->start();
- SkOpSpanBase* endSpan = angle->end();
- return updateWinding(startSpan, endSpan);
- }
- // OPTIMIZATION: does the following also work, and is it any faster?
- // return outerWinding * innerWinding > 0
- // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
- bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
- SkASSERT(outerWinding != SK_MaxS32);
- SkASSERT(innerWinding != SK_MaxS32);
- int absOut = SkTAbs(outerWinding);
- int absIn = SkTAbs(innerWinding);
- bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
- return result;
- }
- int SkOpSegment::windSum(const SkOpAngle* angle) const {
- const SkOpSpan* minSpan = angle->start()->starter(angle->end());
- return minSpan->windSum();
- }
|