12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138 |
- /*
- * Copyright 2014 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "src/pathops/SkPathOpsTSect.h"
- #define COINCIDENT_SPAN_COUNT 9
- void SkTCoincident::setPerp(const SkTCurve& c1, double t,
- const SkDPoint& cPt, const SkTCurve& c2) {
- SkDVector dxdy = c1.dxdyAtT(t);
- SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
- SkIntersections i SkDEBUGCODE((c1.globalState()));
- int used = i.intersectRay(c2, perp);
- // only keep closest
- if (used == 0 || used == 3) {
- this->init();
- return;
- }
- fPerpT = i[0][0];
- fPerpPt = i.pt(0);
- SkASSERT(used <= 2);
- if (used == 2) {
- double distSq = (fPerpPt - cPt).lengthSquared();
- double dist2Sq = (i.pt(1) - cPt).lengthSquared();
- if (dist2Sq < distSq) {
- fPerpT = i[0][1];
- fPerpPt = i.pt(1);
- }
- }
- #if DEBUG_T_SECT
- SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n",
- t, cPt.fX, cPt.fY,
- cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY);
- #endif
- fMatch = cPt.approximatelyEqual(fPerpPt);
- #if DEBUG_T_SECT
- if (fMatch) {
- SkDebugf(""); // allow setting breakpoint
- }
- #endif
- }
- void SkTSpan::addBounded(SkTSpan* span, SkArenaAlloc* heap) {
- SkTSpanBounded* bounded = heap->make<SkTSpanBounded>();
- bounded->fBounded = span;
- bounded->fNext = fBounded;
- fBounded = bounded;
- }
- SkTSpan* SkTSect::addFollowing(
- SkTSpan* prior) {
- SkTSpan* result = this->addOne();
- SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
- result->fStartT = prior ? prior->fEndT : 0;
- SkTSpan* next = prior ? prior->fNext : fHead;
- result->fEndT = next ? next->fStartT : 1;
- result->fPrev = prior;
- result->fNext = next;
- if (prior) {
- prior->fNext = result;
- } else {
- fHead = result;
- }
- if (next) {
- next->fPrev = result;
- }
- result->resetBounds(fCurve);
- // world may not be consistent to call validate here
- result->validate();
- return result;
- }
- void SkTSect::addForPerp(SkTSpan* span, double t) {
- if (!span->hasOppT(t)) {
- SkTSpan* priorSpan;
- SkTSpan* opp = this->spanAtT(t, &priorSpan);
- if (!opp) {
- opp = this->addFollowing(priorSpan);
- #if DEBUG_PERP
- SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ?
- priorSpan->debugID() : -1, t, opp->debugID());
- #endif
- }
- #if DEBUG_PERP
- opp->dump(); SkDebugf("\n");
- SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ?
- priorSpan->debugID() : -1, opp->debugID());
- #endif
- opp->addBounded(span, &fHeap);
- span->addBounded(opp, &fHeap);
- }
- this->validate();
- #if DEBUG_T_SECT
- span->validatePerpT(t);
- #endif
- }
- double SkTSpan::closestBoundedT(const SkDPoint& pt) const {
- double result = -1;
- double closest = DBL_MAX;
- const SkTSpanBounded* testBounded = fBounded;
- while (testBounded) {
- const SkTSpan* test = testBounded->fBounded;
- double startDist = test->pointFirst().distanceSquared(pt);
- if (closest > startDist) {
- closest = startDist;
- result = test->fStartT;
- }
- double endDist = test->pointLast().distanceSquared(pt);
- if (closest > endDist) {
- closest = endDist;
- result = test->fEndT;
- }
- testBounded = testBounded->fNext;
- }
- SkASSERT(between(0, result, 1));
- return result;
- }
- #ifdef SK_DEBUG
- bool SkTSpan::debugIsBefore(const SkTSpan* span) const {
- const SkTSpan* work = this;
- do {
- if (span == work) {
- return true;
- }
- } while ((work = work->fNext));
- return false;
- }
- #endif
- bool SkTSpan::contains(double t) const {
- const SkTSpan* work = this;
- do {
- if (between(work->fStartT, t, work->fEndT)) {
- return true;
- }
- } while ((work = work->fNext));
- return false;
- }
- const SkTSect* SkTSpan::debugOpp() const {
- return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr);
- }
- SkTSpan* SkTSpan::findOppSpan(
- const SkTSpan* opp) const {
- SkTSpanBounded* bounded = fBounded;
- while (bounded) {
- SkTSpan* test = bounded->fBounded;
- if (opp == test) {
- return test;
- }
- bounded = bounded->fNext;
- }
- return nullptr;
- }
- // returns 0 if no hull intersection
- // 1 if hulls intersect
- // 2 if hulls only share a common endpoint
- // -1 if linear and further checking is required
- int SkTSpan::hullCheck(const SkTSpan* opp,
- bool* start, bool* oppStart) {
- if (fIsLinear) {
- return -1;
- }
- bool ptsInCommon;
- if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) {
- SkASSERT(ptsInCommon);
- return 2;
- }
- bool linear;
- if (fPart->hullIntersects(*opp->fPart, &linear)) {
- if (!linear) { // check set true if linear
- return 1;
- }
- fIsLinear = true;
- fIsLine = fPart->controlsInside();
- return ptsInCommon ? 1 : -1;
- } else { // hull is not linear; check set true if intersected at the end points
- return ((int) ptsInCommon) << 1; // 0 or 2
- }
- return 0;
- }
- // OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
- // use line intersection to guess a better split than 0.5
- // OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
- int SkTSpan::hullsIntersect(SkTSpan* opp,
- bool* start, bool* oppStart) {
- if (!fBounds.intersects(opp->fBounds)) {
- return 0;
- }
- int hullSect = this->hullCheck(opp, start, oppStart);
- if (hullSect >= 0) {
- return hullSect;
- }
- hullSect = opp->hullCheck(this, oppStart, start);
- if (hullSect >= 0) {
- return hullSect;
- }
- return -1;
- }
- void SkTSpan::init(const SkTCurve& c) {
- fPrev = fNext = nullptr;
- fStartT = 0;
- fEndT = 1;
- fBounded = nullptr;
- resetBounds(c);
- }
- bool SkTSpan::initBounds(const SkTCurve& c) {
- if (SkDoubleIsNaN(fStartT) || SkDoubleIsNaN(fEndT)) {
- return false;
- }
- c.subDivide(fStartT, fEndT, fPart);
- fBounds.setBounds(*fPart);
- fCoinStart.init();
- fCoinEnd.init();
- fBoundsMax = SkTMax(fBounds.width(), fBounds.height());
- fCollapsed = fPart->collapsed();
- fHasPerp = false;
- fDeleted = false;
- #if DEBUG_T_SECT
- if (fCollapsed) {
- SkDebugf(""); // for convenient breakpoints
- }
- #endif
- return fBounds.valid();
- }
- bool SkTSpan::linearsIntersect(SkTSpan* span) {
- int result = this->linearIntersects(*span->fPart);
- if (result <= 1) {
- return SkToBool(result);
- }
- SkASSERT(span->fIsLinear);
- result = span->linearIntersects(*fPart);
- // SkASSERT(result <= 1);
- return SkToBool(result);
- }
- double SkTSpan::linearT(const SkDPoint& pt) const {
- SkDVector len = this->pointLast() - this->pointFirst();
- return fabs(len.fX) > fabs(len.fY)
- ? (pt.fX - this->pointFirst().fX) / len.fX
- : (pt.fY - this->pointFirst().fY) / len.fY;
- }
- int SkTSpan::linearIntersects(const SkTCurve& q2) const {
- // looks like q1 is near-linear
- int start = 0, end = fPart->pointLast(); // the outside points are usually the extremes
- if (!fPart->controlsInside()) {
- double dist = 0; // if there's any question, compute distance to find best outsiders
- for (int outer = 0; outer < this->pointCount() - 1; ++outer) {
- for (int inner = outer + 1; inner < this->pointCount(); ++inner) {
- double test = ((*fPart)[outer] - (*fPart)[inner]).lengthSquared();
- if (dist > test) {
- continue;
- }
- dist = test;
- start = outer;
- end = inner;
- }
- }
- }
- // see if q2 is on one side of the line formed by the extreme points
- double origX = (*fPart)[start].fX;
- double origY = (*fPart)[start].fY;
- double adj = (*fPart)[end].fX - origX;
- double opp = (*fPart)[end].fY - origY;
- double maxPart = SkTMax(fabs(adj), fabs(opp));
- double sign = 0; // initialization to shut up warning in release build
- for (int n = 0; n < q2.pointCount(); ++n) {
- double dx = q2[n].fY - origY;
- double dy = q2[n].fX - origX;
- double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy)));
- double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
- if (precisely_zero_when_compared_to(test, maxVal)) {
- return 1;
- }
- if (approximately_zero_when_compared_to(test, maxVal)) {
- return 3;
- }
- if (n == 0) {
- sign = test;
- continue;
- }
- if (test * sign < 0) {
- return 1;
- }
- }
- return 0;
- }
- bool SkTSpan::onlyEndPointsInCommon(const SkTSpan* opp,
- bool* start, bool* oppStart, bool* ptsInCommon) {
- if (opp->pointFirst() == this->pointFirst()) {
- *start = *oppStart = true;
- } else if (opp->pointFirst() == this->pointLast()) {
- *start = false;
- *oppStart = true;
- } else if (opp->pointLast() == this->pointFirst()) {
- *start = true;
- *oppStart = false;
- } else if (opp->pointLast() == this->pointLast()) {
- *start = *oppStart = false;
- } else {
- *ptsInCommon = false;
- return false;
- }
- *ptsInCommon = true;
- const SkDPoint* otherPts[4], * oppOtherPts[4];
- // const SkDPoint* otherPts[this->pointCount() - 1], * oppOtherPts[opp->pointCount() - 1];
- int baseIndex = *start ? 0 : fPart->pointLast();
- fPart->otherPts(baseIndex, otherPts);
- opp->fPart->otherPts(*oppStart ? 0 : opp->fPart->pointLast(), oppOtherPts);
- const SkDPoint& base = (*fPart)[baseIndex];
- for (int o1 = 0; o1 < this->pointCount() - 1; ++o1) {
- SkDVector v1 = *otherPts[o1] - base;
- for (int o2 = 0; o2 < opp->pointCount() - 1; ++o2) {
- SkDVector v2 = *oppOtherPts[o2] - base;
- if (v2.dot(v1) >= 0) {
- return false;
- }
- }
- }
- return true;
- }
- SkTSpan* SkTSpan::oppT(double t) const {
- SkTSpanBounded* bounded = fBounded;
- while (bounded) {
- SkTSpan* test = bounded->fBounded;
- if (between(test->fStartT, t, test->fEndT)) {
- return test;
- }
- bounded = bounded->fNext;
- }
- return nullptr;
- }
- bool SkTSpan::removeAllBounded() {
- bool deleteSpan = false;
- SkTSpanBounded* bounded = fBounded;
- while (bounded) {
- SkTSpan* opp = bounded->fBounded;
- deleteSpan |= opp->removeBounded(this);
- bounded = bounded->fNext;
- }
- return deleteSpan;
- }
- bool SkTSpan::removeBounded(const SkTSpan* opp) {
- if (fHasPerp) {
- bool foundStart = false;
- bool foundEnd = false;
- SkTSpanBounded* bounded = fBounded;
- while (bounded) {
- SkTSpan* test = bounded->fBounded;
- if (opp != test) {
- foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT);
- foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT);
- }
- bounded = bounded->fNext;
- }
- if (!foundStart || !foundEnd) {
- fHasPerp = false;
- fCoinStart.init();
- fCoinEnd.init();
- }
- }
- SkTSpanBounded* bounded = fBounded;
- SkTSpanBounded* prev = nullptr;
- while (bounded) {
- SkTSpanBounded* boundedNext = bounded->fNext;
- if (opp == bounded->fBounded) {
- if (prev) {
- prev->fNext = boundedNext;
- return false;
- } else {
- fBounded = boundedNext;
- return fBounded == nullptr;
- }
- }
- prev = bounded;
- bounded = boundedNext;
- }
- SkOPASSERT(0);
- return false;
- }
- bool SkTSpan::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) {
- fStartT = t;
- fEndT = work->fEndT;
- if (fStartT == fEndT) {
- fCollapsed = true;
- return false;
- }
- work->fEndT = t;
- if (work->fStartT == work->fEndT) {
- work->fCollapsed = true;
- return false;
- }
- fPrev = work;
- fNext = work->fNext;
- fIsLinear = work->fIsLinear;
- fIsLine = work->fIsLine;
- work->fNext = this;
- if (fNext) {
- fNext->fPrev = this;
- }
- this->validate();
- SkTSpanBounded* bounded = work->fBounded;
- fBounded = nullptr;
- while (bounded) {
- this->addBounded(bounded->fBounded, heap);
- bounded = bounded->fNext;
- }
- bounded = fBounded;
- while (bounded) {
- bounded->fBounded->addBounded(this, heap);
- bounded = bounded->fNext;
- }
- return true;
- }
- void SkTSpan::validate() const {
- #if DEBUG_VALIDATE
- SkASSERT(this != fPrev);
- SkASSERT(this != fNext);
- SkASSERT(fNext == nullptr || fNext != fPrev);
- SkASSERT(fNext == nullptr || this == fNext->fPrev);
- SkASSERT(fPrev == nullptr || this == fPrev->fNext);
- this->validateBounded();
- #endif
- #if DEBUG_T_SECT
- SkASSERT(fBounds.width() || fBounds.height() || fCollapsed);
- SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF);
- SkASSERT(0 <= fStartT);
- SkASSERT(fEndT <= 1);
- SkASSERT(fStartT <= fEndT);
- SkASSERT(fBounded || fCollapsed == 0xFF);
- if (fHasPerp) {
- if (fCoinStart.isMatch()) {
- validatePerpT(fCoinStart.perpT());
- validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt());
- }
- if (fCoinEnd.isMatch()) {
- validatePerpT(fCoinEnd.perpT());
- validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt());
- }
- }
- #endif
- }
- void SkTSpan::validateBounded() const {
- #if DEBUG_VALIDATE
- const SkTSpanBounded* testBounded = fBounded;
- while (testBounded) {
- SkDEBUGCODE(const SkTSpan* overlap = testBounded->fBounded);
- SkASSERT(!overlap->fDeleted);
- #if DEBUG_T_SECT
- SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1);
- SkASSERT(overlap->findOppSpan(this));
- #endif
- testBounded = testBounded->fNext;
- }
- #endif
- }
- void SkTSpan::validatePerpT(double oppT) const {
- const SkTSpanBounded* testBounded = fBounded;
- while (testBounded) {
- const SkTSpan* overlap = testBounded->fBounded;
- if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) {
- return;
- }
- testBounded = testBounded->fNext;
- }
- SkASSERT(0);
- }
- void SkTSpan::validatePerpPt(double t, const SkDPoint& pt) const {
- SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt);
- }
- SkTSect::SkTSect(const SkTCurve& c
- SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState)
- PATH_OPS_DEBUG_T_SECT_PARAMS(int id))
- : fCurve(c)
- , fHeap(sizeof(SkTSpan) * 4)
- , fCoincident(nullptr)
- , fDeleted(nullptr)
- , fActiveCount(0)
- , fHung(false)
- SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState))
- PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id))
- PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0))
- PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0))
- {
- this->resetRemovedEnds();
- fHead = this->addOne();
- SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState));
- fHead->init(c);
- }
- SkTSpan* SkTSect::addOne() {
- SkTSpan* result;
- if (fDeleted) {
- result = fDeleted;
- fDeleted = result->fNext;
- } else {
- result = fHeap.make<SkTSpan>(fCurve, fHeap);
- #if DEBUG_T_SECT
- ++fDebugAllocatedCount;
- #endif
- }
- result->reset();
- result->fHasPerp = false;
- result->fDeleted = false;
- ++fActiveCount;
- PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID);
- SkDEBUGCODE(result->fDebugSect = this);
- #ifdef SK_DEBUG
- result->debugInit(fCurve, fHeap);
- result->fCoinStart.debugInit();
- result->fCoinEnd.debugInit();
- result->fPrev = result->fNext = nullptr;
- result->fBounds.debugInit();
- result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN;
- result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF;
- #endif
- return result;
- }
- bool SkTSect::binarySearchCoin(SkTSect* sect2, double tStart,
- double tStep, double* resultT, double* oppT, SkTSpan** oppFirst) {
- SkTSpan work(fCurve, fHeap);
- double result = work.fStartT = work.fEndT = tStart;
- SkDEBUGCODE(work.fDebugSect = this);
- SkDPoint last = fCurve.ptAtT(tStart);
- SkDPoint oppPt;
- bool flip = false;
- bool contained = false;
- bool down = tStep < 0;
- const SkTCurve& opp = sect2->fCurve;
- do {
- tStep *= 0.5;
- work.fStartT += tStep;
- if (flip) {
- tStep = -tStep;
- flip = false;
- }
- work.initBounds(fCurve);
- if (work.fCollapsed) {
- return false;
- }
- if (last.approximatelyEqual(work.pointFirst())) {
- break;
- }
- last = work.pointFirst();
- work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp);
- if (work.fCoinStart.isMatch()) {
- #if DEBUG_T_SECT
- work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt());
- #endif
- double oppTTest = work.fCoinStart.perpT();
- if (sect2->fHead->contains(oppTTest)) {
- *oppT = oppTTest;
- oppPt = work.fCoinStart.perpPt();
- contained = true;
- if (down ? result <= work.fStartT : result >= work.fStartT) {
- *oppFirst = nullptr; // signal caller to fail
- return false;
- }
- result = work.fStartT;
- continue;
- }
- }
- tStep = -tStep;
- flip = true;
- } while (true);
- if (!contained) {
- return false;
- }
- if (last.approximatelyEqual(fCurve[0])) {
- result = 0;
- } else if (last.approximatelyEqual(this->pointLast())) {
- result = 1;
- }
- if (oppPt.approximatelyEqual(opp[0])) {
- *oppT = 0;
- } else if (oppPt.approximatelyEqual(sect2->pointLast())) {
- *oppT = 1;
- }
- *resultT = result;
- return true;
- }
- // OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
- // so that each quad sect has a pointer to the largest, and can update it as spans
- // are split
- SkTSpan* SkTSect::boundsMax() {
- SkTSpan* test = fHead;
- SkTSpan* largest = fHead;
- bool lCollapsed = largest->fCollapsed;
- int safetyNet = 10000;
- while ((test = test->fNext)) {
- if (!--safetyNet) {
- fHung = true;
- return nullptr;
- }
- bool tCollapsed = test->fCollapsed;
- if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed &&
- largest->fBoundsMax < test->fBoundsMax)) {
- largest = test;
- lCollapsed = test->fCollapsed;
- }
- }
- return largest;
- }
- bool SkTSect::coincidentCheck(SkTSect* sect2) {
- SkTSpan* first = fHead;
- if (!first) {
- return false;
- }
- SkTSpan* last, * next;
- do {
- int consecutive = this->countConsecutiveSpans(first, &last);
- next = last->fNext;
- if (consecutive < COINCIDENT_SPAN_COUNT) {
- continue;
- }
- this->validate();
- sect2->validate();
- this->computePerpendiculars(sect2, first, last);
- this->validate();
- sect2->validate();
- // check to see if a range of points are on the curve
- SkTSpan* coinStart = first;
- do {
- bool success = this->extractCoincident(sect2, coinStart, last, &coinStart);
- if (!success) {
- return false;
- }
- } while (coinStart && !last->fDeleted);
- if (!fHead || !sect2->fHead) {
- break;
- }
- if (!next || next->fDeleted) {
- break;
- }
- } while ((first = next));
- return true;
- }
- void SkTSect::coincidentForce(SkTSect* sect2,
- double start1s, double start1e) {
- SkTSpan* first = fHead;
- SkTSpan* last = this->tail();
- SkTSpan* oppFirst = sect2->fHead;
- SkTSpan* oppLast = sect2->tail();
- if (!last || !oppLast) {
- return;
- }
- bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
- deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
- this->removeSpanRange(first, last);
- sect2->removeSpanRange(oppFirst, oppLast);
- first->fStartT = start1s;
- first->fEndT = start1e;
- first->resetBounds(fCurve);
- first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve);
- first->fCoinEnd.setPerp(fCurve, start1e, this->pointLast(), sect2->fCurve);
- bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
- double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT());
- double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT());
- if (!oppMatched) {
- using std::swap;
- swap(oppStartT, oppEndT);
- }
- oppFirst->fStartT = oppStartT;
- oppFirst->fEndT = oppEndT;
- oppFirst->resetBounds(sect2->fCurve);
- this->removeCoincident(first, false);
- sect2->removeCoincident(oppFirst, true);
- if (deleteEmptySpans) {
- this->deleteEmptySpans();
- sect2->deleteEmptySpans();
- }
- }
- bool SkTSect::coincidentHasT(double t) {
- SkTSpan* test = fCoincident;
- while (test) {
- if (between(test->fStartT, t, test->fEndT)) {
- return true;
- }
- test = test->fNext;
- }
- return false;
- }
- int SkTSect::collapsed() const {
- int result = 0;
- const SkTSpan* test = fHead;
- while (test) {
- if (test->fCollapsed) {
- ++result;
- }
- test = test->next();
- }
- return result;
- }
- void SkTSect::computePerpendiculars(SkTSect* sect2,
- SkTSpan* first, SkTSpan* last) {
- if (!last) {
- return;
- }
- const SkTCurve& opp = sect2->fCurve;
- SkTSpan* work = first;
- SkTSpan* prior = nullptr;
- do {
- if (!work->fHasPerp && !work->fCollapsed) {
- if (prior) {
- work->fCoinStart = prior->fCoinEnd;
- } else {
- work->fCoinStart.setPerp(fCurve, work->fStartT, work->pointFirst(), opp);
- }
- if (work->fCoinStart.isMatch()) {
- double perpT = work->fCoinStart.perpT();
- if (sect2->coincidentHasT(perpT)) {
- work->fCoinStart.init();
- } else {
- sect2->addForPerp(work, perpT);
- }
- }
- work->fCoinEnd.setPerp(fCurve, work->fEndT, work->pointLast(), opp);
- if (work->fCoinEnd.isMatch()) {
- double perpT = work->fCoinEnd.perpT();
- if (sect2->coincidentHasT(perpT)) {
- work->fCoinEnd.init();
- } else {
- sect2->addForPerp(work, perpT);
- }
- }
- work->fHasPerp = true;
- }
- if (work == last) {
- break;
- }
- prior = work;
- work = work->fNext;
- SkASSERT(work);
- } while (true);
- }
- int SkTSect::countConsecutiveSpans(SkTSpan* first,
- SkTSpan** lastPtr) const {
- int consecutive = 1;
- SkTSpan* last = first;
- do {
- SkTSpan* next = last->fNext;
- if (!next) {
- break;
- }
- if (next->fStartT > last->fEndT) {
- break;
- }
- ++consecutive;
- last = next;
- } while (true);
- *lastPtr = last;
- return consecutive;
- }
- bool SkTSect::hasBounded(const SkTSpan* span) const {
- const SkTSpan* test = fHead;
- if (!test) {
- return false;
- }
- do {
- if (test->findOppSpan(span)) {
- return true;
- }
- } while ((test = test->next()));
- return false;
- }
- bool SkTSect::deleteEmptySpans() {
- SkTSpan* test;
- SkTSpan* next = fHead;
- int safetyHatch = 1000;
- while ((test = next)) {
- next = test->fNext;
- if (!test->fBounded) {
- if (!this->removeSpan(test)) {
- return false;
- }
- }
- if (--safetyHatch < 0) {
- return false;
- }
- }
- return true;
- }
- bool SkTSect::extractCoincident(
- SkTSect* sect2,
- SkTSpan* first, SkTSpan* last,
- SkTSpan** result) {
- first = findCoincidentRun(first, &last);
- if (!first || !last) {
- *result = nullptr;
- return true;
- }
- // march outwards to find limit of coincidence from here to previous and next spans
- double startT = first->fStartT;
- double oppStartT SK_INIT_TO_AVOID_WARNING;
- double oppEndT SK_INIT_TO_AVOID_WARNING;
- SkTSpan* prev = first->fPrev;
- SkASSERT(first->fCoinStart.isMatch());
- SkTSpan* oppFirst = first->findOppT(first->fCoinStart.perpT());
- SkOPASSERT(last->fCoinEnd.isMatch());
- bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT();
- double coinStart;
- SkDEBUGCODE(double coinEnd);
- SkTSpan* cutFirst;
- if (prev && prev->fEndT == startT
- && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart,
- &oppStartT, &oppFirst)
- && prev->fStartT < coinStart && coinStart < startT
- && (cutFirst = prev->oppT(oppStartT))) {
- oppFirst = cutFirst;
- first = this->addSplitAt(prev, coinStart);
- first->markCoincident();
- prev->fCoinEnd.markCoincident();
- if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) {
- SkTSpan* oppHalf = sect2->addSplitAt(oppFirst, oppStartT);
- if (oppMatched) {
- oppFirst->fCoinEnd.markCoincident();
- oppHalf->markCoincident();
- oppFirst = oppHalf;
- } else {
- oppFirst->markCoincident();
- oppHalf->fCoinStart.markCoincident();
- }
- }
- } else {
- if (!oppFirst) {
- return false;
- }
- SkDEBUGCODE(coinStart = first->fStartT);
- SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT);
- }
- // FIXME: incomplete : if we're not at the end, find end of coin
- SkTSpan* oppLast;
- SkOPASSERT(last->fCoinEnd.isMatch());
- oppLast = last->findOppT(last->fCoinEnd.perpT());
- SkDEBUGCODE(coinEnd = last->fEndT);
- #ifdef SK_DEBUG
- if (!this->globalState() || !this->globalState()->debugSkipAssert()) {
- oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT;
- }
- #endif
- if (!oppMatched) {
- using std::swap;
- swap(oppFirst, oppLast);
- swap(oppStartT, oppEndT);
- }
- SkOPASSERT(oppStartT < oppEndT);
- SkASSERT(coinStart == first->fStartT);
- SkASSERT(coinEnd == last->fEndT);
- if (!oppFirst) {
- *result = nullptr;
- return true;
- }
- SkOPASSERT(oppStartT == oppFirst->fStartT);
- if (!oppLast) {
- *result = nullptr;
- return true;
- }
- SkOPASSERT(oppEndT == oppLast->fEndT);
- // reduce coincident runs to single entries
- this->validate();
- sect2->validate();
- bool deleteEmptySpans = this->updateBounded(first, last, oppFirst);
- deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first);
- this->removeSpanRange(first, last);
- sect2->removeSpanRange(oppFirst, oppLast);
- first->fEndT = last->fEndT;
- first->resetBounds(this->fCurve);
- first->fCoinStart.setPerp(fCurve, first->fStartT, first->pointFirst(), sect2->fCurve);
- first->fCoinEnd.setPerp(fCurve, first->fEndT, first->pointLast(), sect2->fCurve);
- oppStartT = first->fCoinStart.perpT();
- oppEndT = first->fCoinEnd.perpT();
- if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) {
- if (!oppMatched) {
- using std::swap;
- swap(oppStartT, oppEndT);
- }
- oppFirst->fStartT = oppStartT;
- oppFirst->fEndT = oppEndT;
- oppFirst->resetBounds(sect2->fCurve);
- }
- this->validateBounded();
- sect2->validateBounded();
- last = first->fNext;
- if (!this->removeCoincident(first, false)) {
- return false;
- }
- if (!sect2->removeCoincident(oppFirst, true)) {
- return false;
- }
- if (deleteEmptySpans) {
- if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) {
- *result = nullptr;
- return false;
- }
- }
- this->validate();
- sect2->validate();
- *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr;
- return true;
- }
- SkTSpan* SkTSect::findCoincidentRun(
- SkTSpan* first, SkTSpan** lastPtr) {
- SkTSpan* work = first;
- SkTSpan* lastCandidate = nullptr;
- first = nullptr;
- // find the first fully coincident span
- do {
- if (work->fCoinStart.isMatch()) {
- #if DEBUG_T_SECT
- work->validatePerpT(work->fCoinStart.perpT());
- work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt());
- #endif
- SkOPASSERT(work->hasOppT(work->fCoinStart.perpT()));
- if (!work->fCoinEnd.isMatch()) {
- break;
- }
- lastCandidate = work;
- if (!first) {
- first = work;
- }
- } else if (first && work->fCollapsed) {
- *lastPtr = lastCandidate;
- return first;
- } else {
- lastCandidate = nullptr;
- SkOPASSERT(!first);
- }
- if (work == *lastPtr) {
- return first;
- }
- work = work->fNext;
- if (!work) {
- return nullptr;
- }
- } while (true);
- if (lastCandidate) {
- *lastPtr = lastCandidate;
- }
- return first;
- }
- int SkTSect::intersects(SkTSpan* span,
- SkTSect* opp,
- SkTSpan* oppSpan, int* oppResult) {
- bool spanStart, oppStart;
- int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart);
- if (hullResult >= 0) {
- if (hullResult == 2) { // hulls have one point in common
- if (!span->fBounded || !span->fBounded->fNext) {
- SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan);
- if (spanStart) {
- span->fEndT = span->fStartT;
- } else {
- span->fStartT = span->fEndT;
- }
- } else {
- hullResult = 1;
- }
- if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) {
- if (oppSpan->fBounded && oppSpan->fBounded->fBounded != span) {
- return 0;
- }
- if (oppStart) {
- oppSpan->fEndT = oppSpan->fStartT;
- } else {
- oppSpan->fStartT = oppSpan->fEndT;
- }
- *oppResult = 2;
- } else {
- *oppResult = 1;
- }
- } else {
- *oppResult = 1;
- }
- return hullResult;
- }
- if (span->fIsLine && oppSpan->fIsLine) {
- SkIntersections i;
- int sects = this->linesIntersect(span, opp, oppSpan, &i);
- if (sects == 2) {
- return *oppResult = 1;
- }
- if (!sects) {
- return -1;
- }
- this->removedEndCheck(span);
- span->fStartT = span->fEndT = i[0][0];
- opp->removedEndCheck(oppSpan);
- oppSpan->fStartT = oppSpan->fEndT = i[1][0];
- return *oppResult = 2;
- }
- if (span->fIsLinear || oppSpan->fIsLinear) {
- return *oppResult = (int) span->linearsIntersect(oppSpan);
- }
- return *oppResult = 1;
- }
- template<typename SkTCurve>
- static bool is_parallel(const SkDLine& thisLine, const SkTCurve& opp) {
- if (!opp.IsConic()) {
- return false; // FIXME : breaks a lot of stuff now
- }
- int finds = 0;
- SkDLine thisPerp;
- thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
- thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
- thisPerp.fPts[1] = thisLine.fPts[1];
- SkIntersections perpRayI;
- perpRayI.intersectRay(opp, thisPerp);
- for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
- finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]);
- }
- thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY);
- thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX);
- thisPerp.fPts[0] = thisLine.fPts[0];
- perpRayI.intersectRay(opp, thisPerp);
- for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) {
- finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]);
- }
- return finds >= 2;
- }
- // while the intersection points are sufficiently far apart:
- // construct the tangent lines from the intersections
- // find the point where the tangent line intersects the opposite curve
- int SkTSect::linesIntersect(SkTSpan* span,
- SkTSect* opp,
- SkTSpan* oppSpan, SkIntersections* i) {
- SkIntersections thisRayI SkDEBUGCODE((span->fDebugGlobalState));
- SkIntersections oppRayI SkDEBUGCODE((span->fDebugGlobalState));
- SkDLine thisLine = {{ span->pointFirst(), span->pointLast() }};
- SkDLine oppLine = {{ oppSpan->pointFirst(), oppSpan->pointLast() }};
- int loopCount = 0;
- double bestDistSq = DBL_MAX;
- if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
- return 0;
- }
- if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
- return 0;
- }
- // if the ends of each line intersect the opposite curve, the lines are coincident
- if (thisRayI.used() > 1) {
- int ptMatches = 0;
- for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) {
- for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) {
- ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]);
- }
- }
- if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) {
- return 2;
- }
- }
- if (oppRayI.used() > 1) {
- int ptMatches = 0;
- for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) {
- for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(oppLine.fPts); ++lIndex) {
- ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]);
- }
- }
- if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) {
- return 2;
- }
- }
- do {
- // pick the closest pair of points
- double closest = DBL_MAX;
- int closeIndex SK_INIT_TO_AVOID_WARNING;
- int oppCloseIndex SK_INIT_TO_AVOID_WARNING;
- for (int index = 0; index < oppRayI.used(); ++index) {
- if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) {
- continue;
- }
- for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) {
- if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) {
- continue;
- }
- double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex));
- if (closest > distSq) {
- closest = distSq;
- closeIndex = index;
- oppCloseIndex = oIndex;
- }
- }
- }
- if (closest == DBL_MAX) {
- break;
- }
- const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex);
- const SkDPoint& iPt = oppRayI.pt(closeIndex);
- if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT)
- && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT)
- && oppIPt.approximatelyEqual(iPt)) {
- i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex);
- return i->used();
- }
- double distSq = oppIPt.distanceSquared(iPt);
- if (bestDistSq < distSq || ++loopCount > 5) {
- return 0;
- }
- bestDistSq = distSq;
- double oppStart = oppRayI[0][closeIndex];
- thisLine[0] = fCurve.ptAtT(oppStart);
- thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart);
- if (!thisRayI.intersectRay(opp->fCurve, thisLine)) {
- break;
- }
- double start = thisRayI[0][oppCloseIndex];
- oppLine[0] = opp->fCurve.ptAtT(start);
- oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start);
- if (!oppRayI.intersectRay(this->fCurve, oppLine)) {
- break;
- }
- } while (true);
- // convergence may fail if the curves are nearly coincident
- SkTCoincident oCoinS, oCoinE;
- oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->pointFirst(), fCurve);
- oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->pointLast(), fCurve);
- double tStart = oCoinS.perpT();
- double tEnd = oCoinE.perpT();
- bool swap = tStart > tEnd;
- if (swap) {
- using std::swap;
- swap(tStart, tEnd);
- }
- tStart = SkTMax(tStart, span->fStartT);
- tEnd = SkTMin(tEnd, span->fEndT);
- if (tStart > tEnd) {
- return 0;
- }
- SkDVector perpS, perpE;
- if (tStart == span->fStartT) {
- SkTCoincident coinS;
- coinS.setPerp(fCurve, span->fStartT, span->pointFirst(), opp->fCurve);
- perpS = span->pointFirst() - coinS.perpPt();
- } else if (swap) {
- perpS = oCoinE.perpPt() - oppSpan->pointLast();
- } else {
- perpS = oCoinS.perpPt() - oppSpan->pointFirst();
- }
- if (tEnd == span->fEndT) {
- SkTCoincident coinE;
- coinE.setPerp(fCurve, span->fEndT, span->pointLast(), opp->fCurve);
- perpE = span->pointLast() - coinE.perpPt();
- } else if (swap) {
- perpE = oCoinS.perpPt() - oppSpan->pointFirst();
- } else {
- perpE = oCoinE.perpPt() - oppSpan->pointLast();
- }
- if (perpS.dot(perpE) >= 0) {
- return 0;
- }
- SkTCoincident coinW;
- double workT = tStart;
- double tStep = tEnd - tStart;
- SkDPoint workPt;
- do {
- tStep *= 0.5;
- if (precisely_zero(tStep)) {
- return 0;
- }
- workT += tStep;
- workPt = fCurve.ptAtT(workT);
- coinW.setPerp(fCurve, workT, workPt, opp->fCurve);
- double perpT = coinW.perpT();
- if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) {
- continue;
- }
- SkDVector perpW = workPt - coinW.perpPt();
- if ((perpS.dot(perpW) >= 0) == (tStep < 0)) {
- tStep = -tStep;
- }
- if (workPt.approximatelyEqual(coinW.perpPt())) {
- break;
- }
- } while (true);
- double oppTTest = coinW.perpT();
- if (!opp->fHead->contains(oppTTest)) {
- return 0;
- }
- i->setMax(1);
- i->insert(workT, oppTTest, workPt);
- return 1;
- }
- bool SkTSect::markSpanGone(SkTSpan* span) {
- if (--fActiveCount < 0) {
- return false;
- }
- span->fNext = fDeleted;
- fDeleted = span;
- SkOPASSERT(!span->fDeleted);
- span->fDeleted = true;
- return true;
- }
- bool SkTSect::matchedDirection(double t, const SkTSect* sect2,
- double t2) const {
- SkDVector dxdy = this->fCurve.dxdyAtT(t);
- SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2);
- return dxdy.dot(dxdy2) >= 0;
- }
- void SkTSect::matchedDirCheck(double t, const SkTSect* sect2,
- double t2, bool* calcMatched, bool* oppMatched) const {
- if (*calcMatched) {
- SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2));
- } else {
- *oppMatched = this->matchedDirection(t, sect2, t2);
- *calcMatched = true;
- }
- }
- void SkTSect::mergeCoincidence(SkTSect* sect2) {
- double smallLimit = 0;
- do {
- // find the smallest unprocessed span
- SkTSpan* smaller = nullptr;
- SkTSpan* test = fCoincident;
- do {
- if (!test) {
- return;
- }
- if (test->fStartT < smallLimit) {
- continue;
- }
- if (smaller && smaller->fEndT < test->fStartT) {
- continue;
- }
- smaller = test;
- } while ((test = test->fNext));
- if (!smaller) {
- return;
- }
- smallLimit = smaller->fEndT;
- // find next larger span
- SkTSpan* prior = nullptr;
- SkTSpan* larger = nullptr;
- SkTSpan* largerPrior = nullptr;
- test = fCoincident;
- do {
- if (test->fStartT < smaller->fEndT) {
- continue;
- }
- SkOPASSERT(test->fStartT != smaller->fEndT);
- if (larger && larger->fStartT < test->fStartT) {
- continue;
- }
- largerPrior = prior;
- larger = test;
- } while ((void) (prior = test), (test = test->fNext));
- if (!larger) {
- continue;
- }
- // check middle t value to see if it is coincident as well
- double midT = (smaller->fEndT + larger->fStartT) / 2;
- SkDPoint midPt = fCurve.ptAtT(midT);
- SkTCoincident coin;
- coin.setPerp(fCurve, midT, midPt, sect2->fCurve);
- if (coin.isMatch()) {
- smaller->fEndT = larger->fEndT;
- smaller->fCoinEnd = larger->fCoinEnd;
- if (largerPrior) {
- largerPrior->fNext = larger->fNext;
- largerPrior->validate();
- } else {
- fCoincident = larger->fNext;
- }
- }
- } while (true);
- }
- SkTSpan* SkTSect::prev(
- SkTSpan* span) const {
- SkTSpan* result = nullptr;
- SkTSpan* test = fHead;
- while (span != test) {
- result = test;
- test = test->fNext;
- SkASSERT(test);
- }
- return result;
- }
- void SkTSect::recoverCollapsed() {
- SkTSpan* deleted = fDeleted;
- while (deleted) {
- SkTSpan* delNext = deleted->fNext;
- if (deleted->fCollapsed) {
- SkTSpan** spanPtr = &fHead;
- while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
- spanPtr = &(*spanPtr)->fNext;
- }
- deleted->fNext = *spanPtr;
- *spanPtr = deleted;
- }
- deleted = delNext;
- }
- }
- void SkTSect::removeAllBut(const SkTSpan* keep,
- SkTSpan* span, SkTSect* opp) {
- const SkTSpanBounded* testBounded = span->fBounded;
- while (testBounded) {
- SkTSpan* bounded = testBounded->fBounded;
- const SkTSpanBounded* next = testBounded->fNext;
- // may have been deleted when opp did 'remove all but'
- if (bounded != keep && !bounded->fDeleted) {
- SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded));
- if (bounded->removeBounded(span)) {
- opp->removeSpan(bounded);
- }
- }
- testBounded = next;
- }
- SkASSERT(!span->fDeleted);
- SkASSERT(span->findOppSpan(keep));
- SkASSERT(keep->findOppSpan(span));
- }
- bool SkTSect::removeByPerpendicular(SkTSect* opp) {
- SkTSpan* test = fHead;
- SkTSpan* next;
- do {
- next = test->fNext;
- if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) {
- continue;
- }
- SkDVector startV = test->fCoinStart.perpPt() - test->pointFirst();
- SkDVector endV = test->fCoinEnd.perpPt() - test->pointLast();
- #if DEBUG_T_SECT
- SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__,
- startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV));
- #endif
- if (startV.dot(endV) <= 0) {
- continue;
- }
- if (!this->removeSpans(test, opp)) {
- return false;
- }
- } while ((test = next));
- return true;
- }
- bool SkTSect::removeCoincident(SkTSpan* span, bool isBetween) {
- if (!this->unlinkSpan(span)) {
- return false;
- }
- if (isBetween || between(0, span->fCoinStart.perpT(), 1)) {
- --fActiveCount;
- span->fNext = fCoincident;
- fCoincident = span;
- } else {
- this->markSpanGone(span);
- }
- return true;
- }
- void SkTSect::removedEndCheck(SkTSpan* span) {
- if (!span->fStartT) {
- fRemovedStartT = true;
- }
- if (1 == span->fEndT) {
- fRemovedEndT = true;
- }
- }
- bool SkTSect::removeSpan(SkTSpan* span) {\
- this->removedEndCheck(span);
- if (!this->unlinkSpan(span)) {
- return false;
- }
- return this->markSpanGone(span);
- }
- void SkTSect::removeSpanRange(SkTSpan* first,
- SkTSpan* last) {
- if (first == last) {
- return;
- }
- SkTSpan* span = first;
- SkASSERT(span);
- SkTSpan* final = last->fNext;
- SkTSpan* next = span->fNext;
- while ((span = next) && span != final) {
- next = span->fNext;
- this->markSpanGone(span);
- }
- if (final) {
- final->fPrev = first;
- }
- first->fNext = final;
- // world may not be ready for validation here
- first->validate();
- }
- bool SkTSect::removeSpans(SkTSpan* span,
- SkTSect* opp) {
- SkTSpanBounded* bounded = span->fBounded;
- while (bounded) {
- SkTSpan* spanBounded = bounded->fBounded;
- SkTSpanBounded* next = bounded->fNext;
- if (span->removeBounded(spanBounded)) { // shuffles last into position 0
- this->removeSpan(span);
- }
- if (spanBounded->removeBounded(span)) {
- opp->removeSpan(spanBounded);
- }
- if (span->fDeleted && opp->hasBounded(span)) {
- return false;
- }
- bounded = next;
- }
- return true;
- }
- SkTSpan* SkTSect::spanAtT(double t,
- SkTSpan** priorSpan) {
- SkTSpan* test = fHead;
- SkTSpan* prev = nullptr;
- while (test && test->fEndT < t) {
- prev = test;
- test = test->fNext;
- }
- *priorSpan = prev;
- return test && test->fStartT <= t ? test : nullptr;
- }
- SkTSpan* SkTSect::tail() {
- SkTSpan* result = fHead;
- SkTSpan* next = fHead;
- int safetyNet = 100000;
- while ((next = next->fNext)) {
- if (!--safetyNet) {
- return nullptr;
- }
- if (next->fEndT > result->fEndT) {
- result = next;
- }
- }
- return result;
- }
- /* Each span has a range of opposite spans it intersects. After the span is split in two,
- adjust the range to its new size */
- bool SkTSect::trim(SkTSpan* span,
- SkTSect* opp) {
- FAIL_IF(!span->initBounds(fCurve));
- const SkTSpanBounded* testBounded = span->fBounded;
- while (testBounded) {
- SkTSpan* test = testBounded->fBounded;
- const SkTSpanBounded* next = testBounded->fNext;
- int oppSects, sects = this->intersects(span, opp, test, &oppSects);
- if (sects >= 1) {
- if (oppSects == 2) {
- test->initBounds(opp->fCurve);
- opp->removeAllBut(span, test, this);
- }
- if (sects == 2) {
- span->initBounds(fCurve);
- this->removeAllBut(test, span, opp);
- return true;
- }
- } else {
- if (span->removeBounded(test)) {
- this->removeSpan(span);
- }
- if (test->removeBounded(span)) {
- opp->removeSpan(test);
- }
- }
- testBounded = next;
- }
- return true;
- }
- bool SkTSect::unlinkSpan(SkTSpan* span) {
- SkTSpan* prev = span->fPrev;
- SkTSpan* next = span->fNext;
- if (prev) {
- prev->fNext = next;
- if (next) {
- next->fPrev = prev;
- if (next->fStartT > next->fEndT) {
- return false;
- }
- // world may not be ready for validate here
- next->validate();
- }
- } else {
- fHead = next;
- if (next) {
- next->fPrev = nullptr;
- }
- }
- return true;
- }
- bool SkTSect::updateBounded(SkTSpan* first,
- SkTSpan* last, SkTSpan* oppFirst) {
- SkTSpan* test = first;
- const SkTSpan* final = last->next();
- bool deleteSpan = false;
- do {
- deleteSpan |= test->removeAllBounded();
- } while ((test = test->fNext) != final && test);
- first->fBounded = nullptr;
- first->addBounded(oppFirst, &fHeap);
- // cannot call validate until remove span range is called
- return deleteSpan;
- }
- void SkTSect::validate() const {
- #if DEBUG_VALIDATE
- int count = 0;
- double last = 0;
- if (fHead) {
- const SkTSpan* span = fHead;
- SkASSERT(!span->fPrev);
- const SkTSpan* next;
- do {
- span->validate();
- SkASSERT(span->fStartT >= last);
- last = span->fEndT;
- ++count;
- next = span->fNext;
- SkASSERT(next != span);
- } while ((span = next) != nullptr);
- }
- SkASSERT(count == fActiveCount);
- #endif
- #if DEBUG_T_SECT
- SkASSERT(fActiveCount <= fDebugAllocatedCount);
- int deletedCount = 0;
- const SkTSpan* deleted = fDeleted;
- while (deleted) {
- ++deletedCount;
- deleted = deleted->fNext;
- }
- const SkTSpan* coincident = fCoincident;
- while (coincident) {
- ++deletedCount;
- coincident = coincident->fNext;
- }
- SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
- #endif
- }
- void SkTSect::validateBounded() const {
- #if DEBUG_VALIDATE
- if (!fHead) {
- return;
- }
- const SkTSpan* span = fHead;
- do {
- span->validateBounded();
- } while ((span = span->fNext) != nullptr);
- #endif
- }
- int SkTSect::EndsEqual(const SkTSect* sect1,
- const SkTSect* sect2, SkIntersections* intersections) {
- int zeroOneSet = 0;
- if (sect1->fCurve[0] == sect2->fCurve[0]) {
- zeroOneSet |= kZeroS1Set | kZeroS2Set;
- intersections->insert(0, 0, sect1->fCurve[0]);
- }
- if (sect1->fCurve[0] == sect2->pointLast()) {
- zeroOneSet |= kZeroS1Set | kOneS2Set;
- intersections->insert(0, 1, sect1->fCurve[0]);
- }
- if (sect1->pointLast() == sect2->fCurve[0]) {
- zeroOneSet |= kOneS1Set | kZeroS2Set;
- intersections->insert(1, 0, sect1->pointLast());
- }
- if (sect1->pointLast() == sect2->pointLast()) {
- zeroOneSet |= kOneS1Set | kOneS2Set;
- intersections->insert(1, 1, sect1->pointLast());
- }
- // check for zero
- if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set))
- && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
- zeroOneSet |= kZeroS1Set | kZeroS2Set;
- intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
- }
- if (!(zeroOneSet & (kZeroS1Set | kOneS2Set))
- && sect1->fCurve[0].approximatelyEqual(sect2->pointLast())) {
- zeroOneSet |= kZeroS1Set | kOneS2Set;
- intersections->insertNear(0, 1, sect1->fCurve[0], sect2->pointLast());
- }
- // check for one
- if (!(zeroOneSet & (kOneS1Set | kZeroS2Set))
- && sect1->pointLast().approximatelyEqual(sect2->fCurve[0])) {
- zeroOneSet |= kOneS1Set | kZeroS2Set;
- intersections->insertNear(1, 0, sect1->pointLast(), sect2->fCurve[0]);
- }
- if (!(zeroOneSet & (kOneS1Set | kOneS2Set))
- && sect1->pointLast().approximatelyEqual(sect2->pointLast())) {
- zeroOneSet |= kOneS1Set | kOneS2Set;
- intersections->insertNear(1, 1, sect1->pointLast(), sect2->pointLast());
- }
- return zeroOneSet;
- }
- struct SkClosestRecord {
- bool operator<(const SkClosestRecord& rh) const {
- return fClosest < rh.fClosest;
- }
- void addIntersection(SkIntersections* intersections) const {
- double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT();
- double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT();
- intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
- }
- void findEnd(const SkTSpan* span1, const SkTSpan* span2,
- int c1Index, int c2Index) {
- const SkTCurve& c1 = span1->part();
- const SkTCurve& c2 = span2->part();
- if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
- return;
- }
- double dist = c1[c1Index].distanceSquared(c2[c2Index]);
- if (fClosest < dist) {
- return;
- }
- fC1Span = span1;
- fC2Span = span2;
- fC1StartT = span1->startT();
- fC1EndT = span1->endT();
- fC2StartT = span2->startT();
- fC2EndT = span2->endT();
- fC1Index = c1Index;
- fC2Index = c2Index;
- fClosest = dist;
- }
- bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i)) const {
- SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT()
- || mate.fC1Span->endT() <= fC1Span->startT());
- SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT()
- || mate.fC2Span->endT() <= fC2Span->startT());
- return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT()
- || fC1Span->startT() == mate.fC1Span->endT()
- || fC2Span == mate.fC2Span
- || fC2Span->endT() == mate.fC2Span->startT()
- || fC2Span->startT() == mate.fC2Span->endT();
- }
- void merge(const SkClosestRecord& mate) {
- fC1Span = mate.fC1Span;
- fC2Span = mate.fC2Span;
- fClosest = mate.fClosest;
- fC1Index = mate.fC1Index;
- fC2Index = mate.fC2Index;
- }
- void reset() {
- fClosest = FLT_MAX;
- SkDEBUGCODE(fC1Span = nullptr);
- SkDEBUGCODE(fC2Span = nullptr);
- SkDEBUGCODE(fC1Index = fC2Index = -1);
- }
- void update(const SkClosestRecord& mate) {
- fC1StartT = SkTMin(fC1StartT, mate.fC1StartT);
- fC1EndT = SkTMax(fC1EndT, mate.fC1EndT);
- fC2StartT = SkTMin(fC2StartT, mate.fC2StartT);
- fC2EndT = SkTMax(fC2EndT, mate.fC2EndT);
- }
- const SkTSpan* fC1Span;
- const SkTSpan* fC2Span;
- double fC1StartT;
- double fC1EndT;
- double fC2StartT;
- double fC2EndT;
- double fClosest;
- int fC1Index;
- int fC2Index;
- };
- struct SkClosestSect {
- SkClosestSect()
- : fUsed(0) {
- fClosest.push_back().reset();
- }
- bool find(const SkTSpan* span1, const SkTSpan* span2
- SkDEBUGPARAMS(SkIntersections* i)) {
- SkClosestRecord* record = &fClosest[fUsed];
- record->findEnd(span1, span2, 0, 0);
- record->findEnd(span1, span2, 0, span2->part().pointLast());
- record->findEnd(span1, span2, span1->part().pointLast(), 0);
- record->findEnd(span1, span2, span1->part().pointLast(), span2->part().pointLast());
- if (record->fClosest == FLT_MAX) {
- return false;
- }
- for (int index = 0; index < fUsed; ++index) {
- SkClosestRecord* test = &fClosest[index];
- if (test->matesWith(*record SkDEBUGPARAMS(i))) {
- if (test->fClosest > record->fClosest) {
- test->merge(*record);
- }
- test->update(*record);
- record->reset();
- return false;
- }
- }
- ++fUsed;
- fClosest.push_back().reset();
- return true;
- }
- void finish(SkIntersections* intersections) const {
- SkSTArray<SkDCubic::kMaxIntersections * 3,
- const SkClosestRecord*, true> closestPtrs;
- for (int index = 0; index < fUsed; ++index) {
- closestPtrs.push_back(&fClosest[index]);
- }
- SkTQSort<const SkClosestRecord >(closestPtrs.begin(), closestPtrs.end()
- - 1);
- for (int index = 0; index < fUsed; ++index) {
- const SkClosestRecord* test = closestPtrs[index];
- test->addIntersection(intersections);
- }
- }
- // this is oversized so that an extra records can merge into final one
- SkSTArray<SkDCubic::kMaxIntersections * 2, SkClosestRecord, true> fClosest;
- int fUsed;
- };
- // returns true if the rect is too small to consider
- void SkTSect::BinarySearch(SkTSect* sect1,
- SkTSect* sect2, SkIntersections* intersections) {
- #if DEBUG_T_SECT_DUMP > 1
- gDumpTSectNum = 0;
- #endif
- SkDEBUGCODE(sect1->fOppSect = sect2);
- SkDEBUGCODE(sect2->fOppSect = sect1);
- intersections->reset();
- intersections->setMax(sect1->fCurve.maxIntersections() + 4); // give extra for slop
- SkTSpan* span1 = sect1->fHead;
- SkTSpan* span2 = sect2->fHead;
- int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect);
- // SkASSERT(between(0, sect, 2));
- if (!sect) {
- return;
- }
- if (sect == 2 && oppSect == 2) {
- (void) EndsEqual(sect1, sect2, intersections);
- return;
- }
- span1->addBounded(span2, §1->fHeap);
- span2->addBounded(span1, §2->fHeap);
- const int kMaxCoinLoopCount = 8;
- int coinLoopCount = kMaxCoinLoopCount;
- double start1s SK_INIT_TO_AVOID_WARNING;
- double start1e SK_INIT_TO_AVOID_WARNING;
- do {
- // find the largest bounds
- SkTSpan* largest1 = sect1->boundsMax();
- if (!largest1) {
- if (sect1->fHung) {
- return;
- }
- break;
- }
- SkTSpan* largest2 = sect2->boundsMax();
- // split it
- if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
- || (!largest1->fCollapsed && largest2->fCollapsed)))) {
- if (sect2->fHung) {
- return;
- }
- if (largest1->fCollapsed) {
- break;
- }
- sect1->resetRemovedEnds();
- sect2->resetRemovedEnds();
- // trim parts that don't intersect the opposite
- SkTSpan* half1 = sect1->addOne();
- SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState()));
- if (!half1->split(largest1, §1->fHeap)) {
- break;
- }
- if (!sect1->trim(largest1, sect2)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- if (!sect1->trim(half1, sect2)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- } else {
- if (largest2->fCollapsed) {
- break;
- }
- sect1->resetRemovedEnds();
- sect2->resetRemovedEnds();
- // trim parts that don't intersect the opposite
- SkTSpan* half2 = sect2->addOne();
- SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState()));
- if (!half2->split(largest2, §2->fHeap)) {
- break;
- }
- if (!sect2->trim(largest2, sect1)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- if (!sect2->trim(half2, sect1)) {
- SkOPOBJASSERT(intersections, 0);
- return;
- }
- }
- sect1->validate();
- sect2->validate();
- #if DEBUG_T_SECT_LOOP_COUNT
- intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop);
- #endif
- // if there are 9 or more continuous spans on both sects, suspect coincidence
- if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
- && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
- if (coinLoopCount == kMaxCoinLoopCount) {
- start1s = sect1->fHead->fStartT;
- start1e = sect1->tail()->fEndT;
- }
- if (!sect1->coincidentCheck(sect2)) {
- return;
- }
- sect1->validate();
- sect2->validate();
- #if DEBUG_T_SECT_LOOP_COUNT
- intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop);
- #endif
- if (!--coinLoopCount && sect1->fHead && sect2->fHead) {
- /* All known working cases resolve in two tries. Sadly, cubicConicTests[0]
- gets stuck in a loop. It adds an extension to allow a coincident end
- perpendicular to track its intersection in the opposite curve. However,
- the bounding box of the extension does not intersect the original curve,
- so the extension is discarded, only to be added again the next time around. */
- sect1->coincidentForce(sect2, start1s, start1e);
- sect1->validate();
- sect2->validate();
- }
- }
- if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
- && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
- if (!sect1->fHead) {
- return;
- }
- sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail());
- if (!sect2->fHead) {
- return;
- }
- sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail());
- if (!sect1->removeByPerpendicular(sect2)) {
- return;
- }
- sect1->validate();
- sect2->validate();
- #if DEBUG_T_SECT_LOOP_COUNT
- intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop);
- #endif
- if (sect1->collapsed() > sect1->fCurve.maxIntersections()) {
- break;
- }
- }
- #if DEBUG_T_SECT_DUMP
- sect1->dumpBoth(sect2);
- #endif
- if (!sect1->fHead || !sect2->fHead) {
- break;
- }
- } while (true);
- SkTSpan* coincident = sect1->fCoincident;
- if (coincident) {
- // if there is more than one coincident span, check loosely to see if they should be joined
- if (coincident->fNext) {
- sect1->mergeCoincidence(sect2);
- coincident = sect1->fCoincident;
- }
- SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1
- do {
- if (!coincident) {
- return;
- }
- if (!coincident->fCoinStart.isMatch()) {
- continue;
- }
- if (!coincident->fCoinEnd.isMatch()) {
- continue;
- }
- double perpT = coincident->fCoinStart.perpT();
- if (perpT < 0) {
- return;
- }
- int index = intersections->insertCoincident(coincident->fStartT,
- perpT, coincident->pointFirst());
- if ((intersections->insertCoincident(coincident->fEndT,
- coincident->fCoinEnd.perpT(),
- coincident->pointLast()) < 0) && index >= 0) {
- intersections->clearCoincidence(index);
- }
- } while ((coincident = coincident->fNext));
- }
- int zeroOneSet = EndsEqual(sect1, sect2, intersections);
- // if (!sect1->fHead || !sect2->fHead) {
- // if the final iteration contains an end (0 or 1),
- if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) {
- SkTCoincident perp; // intersect perpendicular with opposite curve
- perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve);
- if (perp.isMatch()) {
- intersections->insert(0, perp.perpT(), perp.perpPt());
- }
- }
- if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) {
- SkTCoincident perp;
- perp.setPerp(sect1->fCurve, 1, sect1->pointLast(), sect2->fCurve);
- if (perp.isMatch()) {
- intersections->insert(1, perp.perpT(), perp.perpPt());
- }
- }
- if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) {
- SkTCoincident perp;
- perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve);
- if (perp.isMatch()) {
- intersections->insert(perp.perpT(), 0, perp.perpPt());
- }
- }
- if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) {
- SkTCoincident perp;
- perp.setPerp(sect2->fCurve, 1, sect2->pointLast(), sect1->fCurve);
- if (perp.isMatch()) {
- intersections->insert(perp.perpT(), 1, perp.perpPt());
- }
- }
- // }
- if (!sect1->fHead || !sect2->fHead) {
- return;
- }
- sect1->recoverCollapsed();
- sect2->recoverCollapsed();
- SkTSpan* result1 = sect1->fHead;
- // check heads and tails for zero and ones and insert them if we haven't already done so
- const SkTSpan* head1 = result1;
- if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
- const SkDPoint& start1 = sect1->fCurve[0];
- if (head1->isBounded()) {
- double t = head1->closestBoundedT(start1);
- if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
- intersections->insert(0, t, start1);
- }
- }
- }
- const SkTSpan* head2 = sect2->fHead;
- if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
- const SkDPoint& start2 = sect2->fCurve[0];
- if (head2->isBounded()) {
- double t = head2->closestBoundedT(start2);
- if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
- intersections->insert(t, 0, start2);
- }
- }
- }
- if (!(zeroOneSet & kOneS1Set)) {
- const SkTSpan* tail1 = sect1->tail();
- if (!tail1) {
- return;
- }
- if (approximately_greater_than_one(tail1->fEndT)) {
- const SkDPoint& end1 = sect1->pointLast();
- if (tail1->isBounded()) {
- double t = tail1->closestBoundedT(end1);
- if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
- intersections->insert(1, t, end1);
- }
- }
- }
- }
- if (!(zeroOneSet & kOneS2Set)) {
- const SkTSpan* tail2 = sect2->tail();
- if (!tail2) {
- return;
- }
- if (approximately_greater_than_one(tail2->fEndT)) {
- const SkDPoint& end2 = sect2->pointLast();
- if (tail2->isBounded()) {
- double t = tail2->closestBoundedT(end2);
- if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
- intersections->insert(t, 1, end2);
- }
- }
- }
- }
- SkClosestSect closest;
- do {
- while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) {
- result1 = result1->fNext;
- }
- if (!result1) {
- break;
- }
- SkTSpan* result2 = sect2->fHead;
- bool found = false;
- while (result2) {
- found |= closest.find(result1, result2 SkDEBUGPARAMS(intersections));
- result2 = result2->fNext;
- }
- } while ((result1 = result1->fNext));
- closest.finish(intersections);
- // if there is more than one intersection and it isn't already coincident, check
- int last = intersections->used() - 1;
- for (int index = 0; index < last; ) {
- if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) {
- ++index;
- continue;
- }
- double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2;
- SkDPoint midPt = sect1->fCurve.ptAtT(midT);
- // intersect perpendicular with opposite curve
- SkTCoincident perp;
- perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve);
- if (!perp.isMatch()) {
- ++index;
- continue;
- }
- if (intersections->isCoincident(index)) {
- intersections->removeOne(index);
- --last;
- } else if (intersections->isCoincident(index + 1)) {
- intersections->removeOne(index + 1);
- --last;
- } else {
- intersections->setCoincident(index++);
- }
- intersections->setCoincident(index);
- }
- SkOPOBJASSERT(intersections, intersections->used() <= sect1->fCurve.maxIntersections());
- }
- int SkIntersections::intersect(const SkDQuad& q1, const SkDQuad& q2) {
- SkTQuad quad1(q1);
- SkTQuad quad2(q2);
- SkTSect sect1(quad1 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect sect2(quad2 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect::BinarySearch(§1, §2, this);
- return used();
- }
- int SkIntersections::intersect(const SkDConic& c, const SkDQuad& q) {
- SkTConic conic(c);
- SkTQuad quad(q);
- SkTSect sect1(conic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect sect2(quad SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect::BinarySearch(§1, §2, this);
- return used();
- }
- int SkIntersections::intersect(const SkDConic& c1, const SkDConic& c2) {
- SkTConic conic1(c1);
- SkTConic conic2(c2);
- SkTSect sect1(conic1 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect sect2(conic2 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect::BinarySearch(§1, §2, this);
- return used();
- }
- int SkIntersections::intersect(const SkDCubic& c, const SkDQuad& q) {
- SkTCubic cubic(c);
- SkTQuad quad(q);
- SkTSect sect1(cubic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect sect2(quad SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect::BinarySearch(§1, §2, this);
- return used();
- }
- int SkIntersections::intersect(const SkDCubic& cu, const SkDConic& co) {
- SkTCubic cubic(cu);
- SkTConic conic(co);
- SkTSect sect1(cubic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect sect2(conic SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect::BinarySearch(§1, §2, this);
- return used();
- }
- int SkIntersections::intersect(const SkDCubic& c1, const SkDCubic& c2) {
- SkTCubic cubic1(c1);
- SkTCubic cubic2(c2);
- SkTSect sect1(cubic1 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(1));
- SkTSect sect2(cubic2 SkDEBUGPARAMS(globalState()) PATH_OPS_DEBUG_T_SECT_PARAMS(2));
- SkTSect::BinarySearch(§1, §2, this);
- return used();
- }
|