SkOpSegment.cpp 62 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781
  1. /*
  2. * Copyright 2012 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "src/core/SkPointPriv.h"
  8. #include "src/pathops/SkOpCoincidence.h"
  9. #include "src/pathops/SkOpContour.h"
  10. #include "src/pathops/SkOpSegment.h"
  11. #include "src/pathops/SkPathWriter.h"
  12. #include <utility>
  13. /*
  14. After computing raw intersections, post process all segments to:
  15. - find small collections of points that can be collapsed to a single point
  16. - find missing intersections to resolve differences caused by different algorithms
  17. Consider segments containing tiny or small intervals. Consider coincident segments
  18. because coincidence finds intersections through distance measurement that non-coincident
  19. intersection tests cannot.
  20. */
  21. #define F (false) // discard the edge
  22. #define T (true) // keep the edge
  23. static const bool gUnaryActiveEdge[2][2] = {
  24. // from=0 from=1
  25. // to=0,1 to=0,1
  26. {F, T}, {T, F},
  27. };
  28. static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = {
  29. // miFrom=0 miFrom=1
  30. // miTo=0 miTo=1 miTo=0 miTo=1
  31. // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1
  32. // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1
  33. {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su
  34. {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su
  35. {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su
  36. {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su
  37. };
  38. #undef F
  39. #undef T
  40. SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr,
  41. SkOpSpanBase** endPtr, bool* done) {
  42. if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) {
  43. return result;
  44. }
  45. if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) {
  46. return result;
  47. }
  48. return nullptr;
  49. }
  50. SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr,
  51. SkOpSpanBase** endPtr, bool* done) {
  52. SkOpSpan* upSpan = start->upCastable();
  53. if (upSpan) {
  54. if (upSpan->windValue() || upSpan->oppValue()) {
  55. SkOpSpanBase* next = upSpan->next();
  56. if (!*endPtr) {
  57. *startPtr = start;
  58. *endPtr = next;
  59. }
  60. if (!upSpan->done()) {
  61. if (upSpan->windSum() != SK_MinS32) {
  62. return spanToAngle(start, next);
  63. }
  64. *done = false;
  65. }
  66. } else {
  67. SkASSERT(upSpan->done());
  68. }
  69. }
  70. SkOpSpan* downSpan = start->prev();
  71. // edge leading into junction
  72. if (downSpan) {
  73. if (downSpan->windValue() || downSpan->oppValue()) {
  74. if (!*endPtr) {
  75. *startPtr = start;
  76. *endPtr = downSpan;
  77. }
  78. if (!downSpan->done()) {
  79. if (downSpan->windSum() != SK_MinS32) {
  80. return spanToAngle(start, downSpan);
  81. }
  82. *done = false;
  83. }
  84. } else {
  85. SkASSERT(downSpan->done());
  86. }
  87. }
  88. return nullptr;
  89. }
  90. SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr,
  91. SkOpSpanBase** endPtr, bool* done) {
  92. SkOpPtT* oPtT = start->ptT()->next();
  93. SkOpSegment* other = oPtT->segment();
  94. SkOpSpanBase* oSpan = oPtT->span();
  95. return other->activeAngleInner(oSpan, startPtr, endPtr, done);
  96. }
  97. bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask,
  98. SkPathOp op) {
  99. int sumMiWinding = this->updateWinding(end, start);
  100. int sumSuWinding = this->updateOppWinding(end, start);
  101. #if DEBUG_LIMIT_WIND_SUM
  102. SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
  103. SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
  104. #endif
  105. if (this->operand()) {
  106. using std::swap;
  107. swap(sumMiWinding, sumSuWinding);
  108. }
  109. return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding);
  110. }
  111. bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end,
  112. SkPathOp op, int* sumMiWinding, int* sumSuWinding) {
  113. int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
  114. this->setUpWindings(start, end, sumMiWinding, sumSuWinding,
  115. &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
  116. bool miFrom;
  117. bool miTo;
  118. bool suFrom;
  119. bool suTo;
  120. if (operand()) {
  121. miFrom = (oppMaxWinding & xorMiMask) != 0;
  122. miTo = (oppSumWinding & xorMiMask) != 0;
  123. suFrom = (maxWinding & xorSuMask) != 0;
  124. suTo = (sumWinding & xorSuMask) != 0;
  125. } else {
  126. miFrom = (maxWinding & xorMiMask) != 0;
  127. miTo = (sumWinding & xorMiMask) != 0;
  128. suFrom = (oppMaxWinding & xorSuMask) != 0;
  129. suTo = (oppSumWinding & xorSuMask) != 0;
  130. }
  131. bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo];
  132. #if DEBUG_ACTIVE_OP
  133. SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n",
  134. __FUNCTION__, debugID(), start->t(), end->t(),
  135. SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result);
  136. #endif
  137. return result;
  138. }
  139. bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
  140. int sumWinding = updateWinding(end, start);
  141. return activeWinding(start, end, &sumWinding);
  142. }
  143. bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) {
  144. int maxWinding;
  145. setUpWinding(start, end, &maxWinding, sumWinding);
  146. bool from = maxWinding != 0;
  147. bool to = *sumWinding != 0;
  148. bool result = gUnaryActiveEdge[from][to];
  149. return result;
  150. }
  151. bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
  152. SkPathWriter* path) const {
  153. const SkOpSpan* spanStart = start->starter(end);
  154. FAIL_IF(spanStart->alreadyAdded());
  155. const_cast<SkOpSpan*>(spanStart)->markAdded();
  156. SkDCurveSweep curvePart;
  157. start->segment()->subDivide(start, end, &curvePart.fCurve);
  158. curvePart.setCurveHullSweep(fVerb);
  159. SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb;
  160. path->deferredMove(start->ptT());
  161. switch (verb) {
  162. case SkPath::kLine_Verb:
  163. FAIL_IF(!path->deferredLine(end->ptT()));
  164. break;
  165. case SkPath::kQuad_Verb:
  166. path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT());
  167. break;
  168. case SkPath::kConic_Verb:
  169. path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(),
  170. curvePart.fCurve.fConic.fWeight);
  171. break;
  172. case SkPath::kCubic_Verb:
  173. path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(),
  174. curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT());
  175. break;
  176. default:
  177. SkASSERT(0);
  178. }
  179. return true;
  180. }
  181. const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const {
  182. const SkOpSpanBase* test = &fHead;
  183. const SkOpPtT* testPtT;
  184. SkPoint pt = this->ptAtT(t);
  185. do {
  186. testPtT = test->ptT();
  187. if (testPtT->fT == t) {
  188. break;
  189. }
  190. if (!this->match(testPtT, this, t, pt)) {
  191. if (t < testPtT->fT) {
  192. return nullptr;
  193. }
  194. continue;
  195. }
  196. if (!opp) {
  197. return testPtT;
  198. }
  199. const SkOpPtT* loop = testPtT->next();
  200. while (loop != testPtT) {
  201. if (loop->segment() == this && loop->fT == t && loop->fPt == pt) {
  202. goto foundMatch;
  203. }
  204. loop = loop->next();
  205. }
  206. return nullptr;
  207. } while ((test = test->upCast()->next()));
  208. foundMatch:
  209. return opp && !test->contains(opp) ? nullptr : testPtT;
  210. }
  211. // break the span so that the coincident part does not change the angle of the remainder
  212. bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) {
  213. if (this->contains(newT)) {
  214. return true;
  215. }
  216. this->globalState()->resetAllocatedOpSpan();
  217. FAIL_IF(!between(0, newT, 1));
  218. SkOpPtT* newPtT = this->addT(newT);
  219. *startOver |= this->globalState()->allocatedOpSpan();
  220. if (!newPtT) {
  221. return false;
  222. }
  223. newPtT->fPt = this->ptAtT(newT);
  224. SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT);
  225. if (oppPrev) {
  226. // const cast away to change linked list; pt/t values stays unchanged
  227. SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
  228. writableTest->mergeMatches(newPtT->span());
  229. writableTest->ptT()->addOpp(newPtT, oppPrev);
  230. writableTest->checkForCollapsedCoincidence();
  231. }
  232. return true;
  233. }
  234. // Please keep this in sync with debugAddT()
  235. SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) {
  236. debugValidate();
  237. SkOpSpanBase* spanBase = &fHead;
  238. do {
  239. SkOpPtT* result = spanBase->ptT();
  240. if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) {
  241. spanBase->bumpSpanAdds();
  242. return result;
  243. }
  244. if (t < result->fT) {
  245. SkOpSpan* prev = result->span()->prev();
  246. FAIL_WITH_NULL_IF(!prev);
  247. // marks in global state that new op span has been allocated
  248. SkOpSpan* span = this->insert(prev);
  249. span->init(this, prev, t, pt);
  250. this->debugValidate();
  251. #if DEBUG_ADD_T
  252. SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
  253. span->segment()->debugID(), span->debugID());
  254. #endif
  255. span->bumpSpanAdds();
  256. return span->ptT();
  257. }
  258. FAIL_WITH_NULL_IF(spanBase == &fTail);
  259. } while ((spanBase = spanBase->upCast()->next()));
  260. SkASSERT(0);
  261. return nullptr; // we never get here, but need this to satisfy compiler
  262. }
  263. SkOpPtT* SkOpSegment::addT(double t) {
  264. return addT(t, this->ptAtT(t));
  265. }
  266. void SkOpSegment::calcAngles() {
  267. bool activePrior = !fHead.isCanceled();
  268. if (activePrior && !fHead.simple()) {
  269. addStartSpan();
  270. }
  271. SkOpSpan* prior = &fHead;
  272. SkOpSpanBase* spanBase = fHead.next();
  273. while (spanBase != &fTail) {
  274. if (activePrior) {
  275. SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>();
  276. priorAngle->set(spanBase, prior);
  277. spanBase->setFromAngle(priorAngle);
  278. }
  279. SkOpSpan* span = spanBase->upCast();
  280. bool active = !span->isCanceled();
  281. SkOpSpanBase* next = span->next();
  282. if (active) {
  283. SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>();
  284. angle->set(span, next);
  285. span->setToAngle(angle);
  286. }
  287. activePrior = active;
  288. prior = span;
  289. spanBase = next;
  290. }
  291. if (activePrior && !fTail.simple()) {
  292. addEndSpan();
  293. }
  294. }
  295. // Please keep this in sync with debugClearAll()
  296. void SkOpSegment::clearAll() {
  297. SkOpSpan* span = &fHead;
  298. do {
  299. this->clearOne(span);
  300. } while ((span = span->next()->upCastable()));
  301. this->globalState()->coincidence()->release(this);
  302. }
  303. // Please keep this in sync with debugClearOne()
  304. void SkOpSegment::clearOne(SkOpSpan* span) {
  305. span->setWindValue(0);
  306. span->setOppValue(0);
  307. this->markDone(span);
  308. }
  309. SkOpSpanBase::Collapsed SkOpSegment::collapsed(double s, double e) const {
  310. const SkOpSpanBase* span = &fHead;
  311. do {
  312. SkOpSpanBase::Collapsed result = span->collapsed(s, e);
  313. if (SkOpSpanBase::Collapsed::kNo != result) {
  314. return result;
  315. }
  316. } while (span->upCastable() && (span = span->upCast()->next()));
  317. return SkOpSpanBase::Collapsed::kNo;
  318. }
  319. bool SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
  320. SkOpAngle::IncludeType includeType) {
  321. SkOpSegment* baseSegment = baseAngle->segment();
  322. int sumMiWinding = baseSegment->updateWindingReverse(baseAngle);
  323. int sumSuWinding;
  324. bool binary = includeType >= SkOpAngle::kBinarySingle;
  325. if (binary) {
  326. sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle);
  327. if (baseSegment->operand()) {
  328. using std::swap;
  329. swap(sumMiWinding, sumSuWinding);
  330. }
  331. }
  332. SkOpSegment* nextSegment = nextAngle->segment();
  333. int maxWinding, sumWinding;
  334. SkOpSpanBase* last = nullptr;
  335. if (binary) {
  336. int oppMaxWinding, oppSumWinding;
  337. nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
  338. &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
  339. if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
  340. nextAngle, &last)) {
  341. return false;
  342. }
  343. } else {
  344. nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding,
  345. &maxWinding, &sumWinding);
  346. if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) {
  347. return false;
  348. }
  349. }
  350. nextAngle->setLastMarked(last);
  351. return true;
  352. }
  353. bool SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle,
  354. SkOpAngle::IncludeType includeType) {
  355. SkOpSegment* baseSegment = baseAngle->segment();
  356. int sumMiWinding = baseSegment->updateWinding(baseAngle);
  357. int sumSuWinding;
  358. bool binary = includeType >= SkOpAngle::kBinarySingle;
  359. if (binary) {
  360. sumSuWinding = baseSegment->updateOppWinding(baseAngle);
  361. if (baseSegment->operand()) {
  362. using std::swap;
  363. swap(sumMiWinding, sumSuWinding);
  364. }
  365. }
  366. SkOpSegment* nextSegment = nextAngle->segment();
  367. int maxWinding, sumWinding;
  368. SkOpSpanBase* last = nullptr;
  369. if (binary) {
  370. int oppMaxWinding, oppSumWinding;
  371. nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
  372. &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
  373. if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding,
  374. nextAngle, &last)) {
  375. return false;
  376. }
  377. } else {
  378. nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding,
  379. &maxWinding, &sumWinding);
  380. if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) {
  381. return false;
  382. }
  383. }
  384. nextAngle->setLastMarked(last);
  385. return true;
  386. }
  387. // at this point, the span is already ordered, or unorderable
  388. int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
  389. SkOpAngle::IncludeType includeType) {
  390. SkASSERT(includeType != SkOpAngle::kUnaryXor);
  391. SkOpAngle* firstAngle = this->spanToAngle(end, start);
  392. if (nullptr == firstAngle || nullptr == firstAngle->next()) {
  393. return SK_NaN32;
  394. }
  395. // if all angles have a computed winding,
  396. // or if no adjacent angles are orderable,
  397. // or if adjacent orderable angles have no computed winding,
  398. // there's nothing to do
  399. // if two orderable angles are adjacent, and both are next to orderable angles,
  400. // and one has winding computed, transfer to the other
  401. SkOpAngle* baseAngle = nullptr;
  402. bool tryReverse = false;
  403. // look for counterclockwise transfers
  404. SkOpAngle* angle = firstAngle->previous();
  405. SkOpAngle* next = angle->next();
  406. firstAngle = next;
  407. do {
  408. SkOpAngle* prior = angle;
  409. angle = next;
  410. next = angle->next();
  411. SkASSERT(prior->next() == angle);
  412. SkASSERT(angle->next() == next);
  413. if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
  414. baseAngle = nullptr;
  415. continue;
  416. }
  417. int testWinding = angle->starter()->windSum();
  418. if (SK_MinS32 != testWinding) {
  419. baseAngle = angle;
  420. tryReverse = true;
  421. continue;
  422. }
  423. if (baseAngle) {
  424. ComputeOneSum(baseAngle, angle, includeType);
  425. baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
  426. }
  427. } while (next != firstAngle);
  428. if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) {
  429. firstAngle = baseAngle;
  430. tryReverse = true;
  431. }
  432. if (tryReverse) {
  433. baseAngle = nullptr;
  434. SkOpAngle* prior = firstAngle;
  435. do {
  436. angle = prior;
  437. prior = angle->previous();
  438. SkASSERT(prior->next() == angle);
  439. next = angle->next();
  440. if (prior->unorderable() || angle->unorderable() || next->unorderable()) {
  441. baseAngle = nullptr;
  442. continue;
  443. }
  444. int testWinding = angle->starter()->windSum();
  445. if (SK_MinS32 != testWinding) {
  446. baseAngle = angle;
  447. continue;
  448. }
  449. if (baseAngle) {
  450. ComputeOneSumReverse(baseAngle, angle, includeType);
  451. baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr;
  452. }
  453. } while (prior != firstAngle);
  454. }
  455. return start->starter(end)->windSum();
  456. }
  457. bool SkOpSegment::contains(double newT) const {
  458. const SkOpSpanBase* spanBase = &fHead;
  459. do {
  460. if (spanBase->ptT()->contains(this, newT)) {
  461. return true;
  462. }
  463. if (spanBase == &fTail) {
  464. break;
  465. }
  466. spanBase = spanBase->upCast()->next();
  467. } while (true);
  468. return false;
  469. }
  470. void SkOpSegment::release(const SkOpSpan* span) {
  471. if (span->done()) {
  472. --fDoneCount;
  473. }
  474. --fCount;
  475. SkOPASSERT(fCount >= fDoneCount);
  476. }
  477. #if DEBUG_ANGLE
  478. // called only by debugCheckNearCoincidence
  479. double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
  480. SkDPoint testPt = this->dPtAtT(t);
  481. SkDLine testPerp = {{ testPt, testPt }};
  482. SkDVector slope = this->dSlopeAtT(t);
  483. testPerp[1].fX += slope.fY;
  484. testPerp[1].fY -= slope.fX;
  485. SkIntersections i;
  486. const SkOpSegment* oppSegment = oppAngle->segment();
  487. (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i);
  488. double closestDistSq = SK_ScalarInfinity;
  489. for (int index = 0; index < i.used(); ++index) {
  490. if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) {
  491. continue;
  492. }
  493. double testDistSq = testPt.distanceSquared(i.pt(index));
  494. if (closestDistSq > testDistSq) {
  495. closestDistSq = testDistSq;
  496. }
  497. }
  498. return closestDistSq;
  499. }
  500. #endif
  501. /*
  502. The M and S variable name parts stand for the operators.
  503. Mi stands for Minuend (see wiki subtraction, analogous to difference)
  504. Su stands for Subtrahend
  505. The Opp variable name part designates that the value is for the Opposite operator.
  506. Opposite values result from combining coincident spans.
  507. */
  508. SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart,
  509. SkOpSpanBase** nextEnd, bool* unsortable, bool* simple,
  510. SkPathOp op, int xorMiMask, int xorSuMask) {
  511. SkOpSpanBase* start = *nextStart;
  512. SkOpSpanBase* end = *nextEnd;
  513. SkASSERT(start != end);
  514. int step = start->step(end);
  515. SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
  516. if ((*simple = other)) {
  517. // mark the smaller of startIndex, endIndex done, and all adjacent
  518. // spans with the same T value (but not 'other' spans)
  519. #if DEBUG_WINDING
  520. SkDebugf("%s simple\n", __FUNCTION__);
  521. #endif
  522. SkOpSpan* startSpan = start->starter(end);
  523. if (startSpan->done()) {
  524. return nullptr;
  525. }
  526. markDone(startSpan);
  527. *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
  528. return other;
  529. }
  530. SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
  531. SkASSERT(endNear == end); // is this ever not end?
  532. SkASSERT(endNear);
  533. SkASSERT(start != endNear);
  534. SkASSERT((start->t() < endNear->t()) ^ (step < 0));
  535. // more than one viable candidate -- measure angles to find best
  536. int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp);
  537. bool sortable = calcWinding != SK_NaN32;
  538. if (!sortable) {
  539. *unsortable = true;
  540. markDone(start->starter(end));
  541. return nullptr;
  542. }
  543. SkOpAngle* angle = this->spanToAngle(end, start);
  544. if (angle->unorderable()) {
  545. *unsortable = true;
  546. markDone(start->starter(end));
  547. return nullptr;
  548. }
  549. #if DEBUG_SORT
  550. SkDebugf("%s\n", __FUNCTION__);
  551. angle->debugLoop();
  552. #endif
  553. int sumMiWinding = updateWinding(end, start);
  554. if (sumMiWinding == SK_MinS32) {
  555. *unsortable = true;
  556. markDone(start->starter(end));
  557. return nullptr;
  558. }
  559. int sumSuWinding = updateOppWinding(end, start);
  560. if (operand()) {
  561. using std::swap;
  562. swap(sumMiWinding, sumSuWinding);
  563. }
  564. SkOpAngle* nextAngle = angle->next();
  565. const SkOpAngle* foundAngle = nullptr;
  566. bool foundDone = false;
  567. // iterate through the angle, and compute everyone's winding
  568. SkOpSegment* nextSegment;
  569. int activeCount = 0;
  570. do {
  571. nextSegment = nextAngle->segment();
  572. bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(),
  573. nextAngle->end(), op, &sumMiWinding, &sumSuWinding);
  574. if (activeAngle) {
  575. ++activeCount;
  576. if (!foundAngle || (foundDone && activeCount & 1)) {
  577. foundAngle = nextAngle;
  578. foundDone = nextSegment->done(nextAngle);
  579. }
  580. }
  581. if (nextSegment->done()) {
  582. continue;
  583. }
  584. if (!activeAngle) {
  585. (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr);
  586. }
  587. SkOpSpanBase* last = nextAngle->lastMarked();
  588. if (last) {
  589. SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
  590. *chase->append() = last;
  591. #if DEBUG_WINDING
  592. SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
  593. last->segment()->debugID(), last->debugID());
  594. if (!last->final()) {
  595. SkDebugf(" windSum=%d", last->upCast()->windSum());
  596. }
  597. SkDebugf("\n");
  598. #endif
  599. }
  600. } while ((nextAngle = nextAngle->next()) != angle);
  601. start->segment()->markDone(start->starter(end));
  602. if (!foundAngle) {
  603. return nullptr;
  604. }
  605. *nextStart = foundAngle->start();
  606. *nextEnd = foundAngle->end();
  607. nextSegment = foundAngle->segment();
  608. #if DEBUG_WINDING
  609. SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
  610. __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
  611. #endif
  612. return nextSegment;
  613. }
  614. SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase,
  615. SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) {
  616. SkOpSpanBase* start = *nextStart;
  617. SkOpSpanBase* end = *nextEnd;
  618. SkASSERT(start != end);
  619. int step = start->step(end);
  620. SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
  621. if (other) {
  622. // mark the smaller of startIndex, endIndex done, and all adjacent
  623. // spans with the same T value (but not 'other' spans)
  624. #if DEBUG_WINDING
  625. SkDebugf("%s simple\n", __FUNCTION__);
  626. #endif
  627. SkOpSpan* startSpan = start->starter(end);
  628. if (startSpan->done()) {
  629. return nullptr;
  630. }
  631. markDone(startSpan);
  632. *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
  633. return other;
  634. }
  635. SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
  636. SkASSERT(endNear == end); // is this ever not end?
  637. SkASSERT(endNear);
  638. SkASSERT(start != endNear);
  639. SkASSERT((start->t() < endNear->t()) ^ (step < 0));
  640. // more than one viable candidate -- measure angles to find best
  641. int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding);
  642. bool sortable = calcWinding != SK_NaN32;
  643. if (!sortable) {
  644. *unsortable = true;
  645. markDone(start->starter(end));
  646. return nullptr;
  647. }
  648. SkOpAngle* angle = this->spanToAngle(end, start);
  649. if (angle->unorderable()) {
  650. *unsortable = true;
  651. markDone(start->starter(end));
  652. return nullptr;
  653. }
  654. #if DEBUG_SORT
  655. SkDebugf("%s\n", __FUNCTION__);
  656. angle->debugLoop();
  657. #endif
  658. int sumWinding = updateWinding(end, start);
  659. SkOpAngle* nextAngle = angle->next();
  660. const SkOpAngle* foundAngle = nullptr;
  661. bool foundDone = false;
  662. // iterate through the angle, and compute everyone's winding
  663. SkOpSegment* nextSegment;
  664. int activeCount = 0;
  665. do {
  666. nextSegment = nextAngle->segment();
  667. bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(),
  668. &sumWinding);
  669. if (activeAngle) {
  670. ++activeCount;
  671. if (!foundAngle || (foundDone && activeCount & 1)) {
  672. foundAngle = nextAngle;
  673. foundDone = nextSegment->done(nextAngle);
  674. }
  675. }
  676. if (nextSegment->done()) {
  677. continue;
  678. }
  679. if (!activeAngle) {
  680. (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr);
  681. }
  682. SkOpSpanBase* last = nextAngle->lastMarked();
  683. if (last) {
  684. SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last));
  685. *chase->append() = last;
  686. #if DEBUG_WINDING
  687. SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__,
  688. last->segment()->debugID(), last->debugID());
  689. if (!last->final()) {
  690. SkDebugf(" windSum=%d", last->upCast()->windSum());
  691. }
  692. SkDebugf("\n");
  693. #endif
  694. }
  695. } while ((nextAngle = nextAngle->next()) != angle);
  696. start->segment()->markDone(start->starter(end));
  697. if (!foundAngle) {
  698. return nullptr;
  699. }
  700. *nextStart = foundAngle->start();
  701. *nextEnd = foundAngle->end();
  702. nextSegment = foundAngle->segment();
  703. #if DEBUG_WINDING
  704. SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
  705. __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
  706. #endif
  707. return nextSegment;
  708. }
  709. SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd,
  710. bool* unsortable) {
  711. SkOpSpanBase* start = *nextStart;
  712. SkOpSpanBase* end = *nextEnd;
  713. SkASSERT(start != end);
  714. int step = start->step(end);
  715. SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart
  716. if (other) {
  717. // mark the smaller of startIndex, endIndex done, and all adjacent
  718. // spans with the same T value (but not 'other' spans)
  719. #if DEBUG_WINDING
  720. SkDebugf("%s simple\n", __FUNCTION__);
  721. #endif
  722. SkOpSpan* startSpan = start->starter(end);
  723. if (startSpan->done()) {
  724. return nullptr;
  725. }
  726. markDone(startSpan);
  727. *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev();
  728. return other;
  729. }
  730. SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \
  731. : (*nextStart)->prev());
  732. SkASSERT(endNear == end); // is this ever not end?
  733. SkASSERT(endNear);
  734. SkASSERT(start != endNear);
  735. SkASSERT((start->t() < endNear->t()) ^ (step < 0));
  736. SkOpAngle* angle = this->spanToAngle(end, start);
  737. if (!angle || angle->unorderable()) {
  738. *unsortable = true;
  739. markDone(start->starter(end));
  740. return nullptr;
  741. }
  742. #if DEBUG_SORT
  743. SkDebugf("%s\n", __FUNCTION__);
  744. angle->debugLoop();
  745. #endif
  746. SkOpAngle* nextAngle = angle->next();
  747. const SkOpAngle* foundAngle = nullptr;
  748. bool foundDone = false;
  749. // iterate through the angle, and compute everyone's winding
  750. SkOpSegment* nextSegment;
  751. int activeCount = 0;
  752. do {
  753. if (!nextAngle) {
  754. return nullptr;
  755. }
  756. nextSegment = nextAngle->segment();
  757. ++activeCount;
  758. if (!foundAngle || (foundDone && activeCount & 1)) {
  759. foundAngle = nextAngle;
  760. if (!(foundDone = nextSegment->done(nextAngle))) {
  761. break;
  762. }
  763. }
  764. nextAngle = nextAngle->next();
  765. } while (nextAngle != angle);
  766. start->segment()->markDone(start->starter(end));
  767. if (!foundAngle) {
  768. return nullptr;
  769. }
  770. *nextStart = foundAngle->start();
  771. *nextEnd = foundAngle->end();
  772. nextSegment = foundAngle->segment();
  773. #if DEBUG_WINDING
  774. SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n",
  775. __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd);
  776. #endif
  777. return nextSegment;
  778. }
  779. SkOpGlobalState* SkOpSegment::globalState() const {
  780. return contour()->globalState();
  781. }
  782. void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
  783. fContour = contour;
  784. fNext = nullptr;
  785. fPts = pts;
  786. fWeight = weight;
  787. fVerb = verb;
  788. fCount = 0;
  789. fDoneCount = 0;
  790. fVisited = false;
  791. SkOpSpan* zeroSpan = &fHead;
  792. zeroSpan->init(this, nullptr, 0, fPts[0]);
  793. SkOpSpanBase* oneSpan = &fTail;
  794. zeroSpan->setNext(oneSpan);
  795. oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]);
  796. SkDEBUGCODE(fID = globalState()->nextSegmentID());
  797. }
  798. bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const {
  799. SkDPoint cPt = this->dPtAtT(t);
  800. SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t);
  801. SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
  802. SkIntersections i;
  803. (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i);
  804. int used = i.used();
  805. for (int index = 0; index < used; ++index) {
  806. if (cPt.roughlyEqual(i.pt(index))) {
  807. return true;
  808. }
  809. }
  810. return false;
  811. }
  812. bool SkOpSegment::isXor() const {
  813. return fContour->isXor();
  814. }
  815. void SkOpSegment::markAllDone() {
  816. SkOpSpan* span = this->head();
  817. do {
  818. this->markDone(span);
  819. } while ((span = span->next()->upCastable()));
  820. }
  821. bool SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found) {
  822. int step = start->step(end);
  823. SkOpSpan* minSpan = start->starter(end);
  824. markDone(minSpan);
  825. SkOpSpanBase* last = nullptr;
  826. SkOpSegment* other = this;
  827. SkOpSpan* priorDone = nullptr;
  828. SkOpSpan* lastDone = nullptr;
  829. int safetyNet = 100000;
  830. while ((other = other->nextChase(&start, &step, &minSpan, &last))) {
  831. if (!--safetyNet) {
  832. return false;
  833. }
  834. if (other->done()) {
  835. SkASSERT(!last);
  836. break;
  837. }
  838. if (lastDone == minSpan || priorDone == minSpan) {
  839. if (found) {
  840. *found = nullptr;
  841. }
  842. return true;
  843. }
  844. other->markDone(minSpan);
  845. priorDone = lastDone;
  846. lastDone = minSpan;
  847. }
  848. if (found) {
  849. *found = last;
  850. }
  851. return true;
  852. }
  853. bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
  854. SkOpSpanBase** lastPtr) {
  855. SkOpSpan* spanStart = start->starter(end);
  856. int step = start->step(end);
  857. bool success = markWinding(spanStart, winding);
  858. SkOpSpanBase* last = nullptr;
  859. SkOpSegment* other = this;
  860. int safetyNet = 100000;
  861. while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
  862. if (!--safetyNet) {
  863. return false;
  864. }
  865. if (spanStart->windSum() != SK_MinS32) {
  866. // SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive?
  867. SkASSERT(!last);
  868. break;
  869. }
  870. (void) other->markWinding(spanStart, winding);
  871. }
  872. if (lastPtr) {
  873. *lastPtr = last;
  874. }
  875. return success;
  876. }
  877. bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end,
  878. int winding, int oppWinding, SkOpSpanBase** lastPtr) {
  879. SkOpSpan* spanStart = start->starter(end);
  880. int step = start->step(end);
  881. bool success = markWinding(spanStart, winding, oppWinding);
  882. SkOpSpanBase* last = nullptr;
  883. SkOpSegment* other = this;
  884. int safetyNet = 100000;
  885. while ((other = other->nextChase(&start, &step, &spanStart, &last))) {
  886. if (!--safetyNet) {
  887. return false;
  888. }
  889. if (spanStart->windSum() != SK_MinS32) {
  890. if (this->operand() == other->operand()) {
  891. if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) {
  892. this->globalState()->setWindingFailed();
  893. return true; // ... but let it succeed anyway
  894. }
  895. } else {
  896. FAIL_IF(spanStart->windSum() != oppWinding);
  897. FAIL_IF(spanStart->oppSum() != winding);
  898. }
  899. SkASSERT(!last);
  900. break;
  901. }
  902. if (this->operand() == other->operand()) {
  903. (void) other->markWinding(spanStart, winding, oppWinding);
  904. } else {
  905. (void) other->markWinding(spanStart, oppWinding, winding);
  906. }
  907. }
  908. if (lastPtr) {
  909. *lastPtr = last;
  910. }
  911. return success;
  912. }
  913. bool SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle,
  914. SkOpSpanBase** result) {
  915. SkASSERT(angle->segment() == this);
  916. if (UseInnerWinding(maxWinding, sumWinding)) {
  917. maxWinding = sumWinding;
  918. }
  919. if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, result)) {
  920. return false;
  921. }
  922. #if DEBUG_WINDING
  923. SkOpSpanBase* last = *result;
  924. if (last) {
  925. SkDebugf("%s last seg=%d span=%d", __FUNCTION__,
  926. last->segment()->debugID(), last->debugID());
  927. if (!last->final()) {
  928. SkDebugf(" windSum=");
  929. SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
  930. }
  931. SkDebugf("\n");
  932. }
  933. #endif
  934. return true;
  935. }
  936. bool SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding,
  937. int oppSumWinding, const SkOpAngle* angle, SkOpSpanBase** result) {
  938. SkASSERT(angle->segment() == this);
  939. if (UseInnerWinding(maxWinding, sumWinding)) {
  940. maxWinding = sumWinding;
  941. }
  942. if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) {
  943. oppMaxWinding = oppSumWinding;
  944. }
  945. // caller doesn't require that this marks anything
  946. if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, result)) {
  947. return false;
  948. }
  949. #if DEBUG_WINDING
  950. if (result) {
  951. SkOpSpanBase* last = *result;
  952. if (last) {
  953. SkDebugf("%s last segment=%d span=%d", __FUNCTION__,
  954. last->segment()->debugID(), last->debugID());
  955. if (!last->final()) {
  956. SkDebugf(" windSum=");
  957. SkPathOpsDebug::WindingPrintf(last->upCast()->windSum());
  958. }
  959. SkDebugf(" \n");
  960. }
  961. }
  962. #endif
  963. return true;
  964. }
  965. void SkOpSegment::markDone(SkOpSpan* span) {
  966. SkASSERT(this == span->segment());
  967. if (span->done()) {
  968. return;
  969. }
  970. #if DEBUG_MARK_DONE
  971. debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum());
  972. #endif
  973. span->setDone(true);
  974. ++fDoneCount;
  975. debugValidate();
  976. }
  977. bool SkOpSegment::markWinding(SkOpSpan* span, int winding) {
  978. SkASSERT(this == span->segment());
  979. SkASSERT(winding);
  980. if (span->done()) {
  981. return false;
  982. }
  983. #if DEBUG_MARK_DONE
  984. debugShowNewWinding(__FUNCTION__, span, winding);
  985. #endif
  986. span->setWindSum(winding);
  987. debugValidate();
  988. return true;
  989. }
  990. bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
  991. SkASSERT(this == span->segment());
  992. SkASSERT(winding || oppWinding);
  993. if (span->done()) {
  994. return false;
  995. }
  996. #if DEBUG_MARK_DONE
  997. debugShowNewWinding(__FUNCTION__, span, winding, oppWinding);
  998. #endif
  999. span->setWindSum(winding);
  1000. span->setOppSum(oppWinding);
  1001. debugValidate();
  1002. return true;
  1003. }
  1004. bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
  1005. const SkPoint& testPt) const {
  1006. SkASSERT(this == base->segment());
  1007. if (this == testParent) {
  1008. if (precisely_equal(base->fT, testT)) {
  1009. return true;
  1010. }
  1011. }
  1012. if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
  1013. return false;
  1014. }
  1015. return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
  1016. }
  1017. static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
  1018. if (last) {
  1019. *last = endSpan;
  1020. }
  1021. return nullptr;
  1022. }
  1023. SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr,
  1024. SkOpSpanBase** last) const {
  1025. SkOpSpanBase* origStart = *startPtr;
  1026. int step = *stepPtr;
  1027. SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev();
  1028. SkASSERT(endSpan);
  1029. SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle();
  1030. SkOpSpanBase* foundSpan;
  1031. SkOpSpanBase* otherEnd;
  1032. SkOpSegment* other;
  1033. if (angle == nullptr) {
  1034. if (endSpan->t() != 0 && endSpan->t() != 1) {
  1035. return nullptr;
  1036. }
  1037. SkOpPtT* otherPtT = endSpan->ptT()->next();
  1038. other = otherPtT->segment();
  1039. foundSpan = otherPtT->span();
  1040. otherEnd = step > 0
  1041. ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr
  1042. : foundSpan->prev();
  1043. } else {
  1044. int loopCount = angle->loopCount();
  1045. if (loopCount > 2) {
  1046. return set_last(last, endSpan);
  1047. }
  1048. const SkOpAngle* next = angle->next();
  1049. if (nullptr == next) {
  1050. return nullptr;
  1051. }
  1052. #if DEBUG_WINDING
  1053. if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor()
  1054. && !next->segment()->contour()->isXor()) {
  1055. SkDebugf("%s mismatched signs\n", __FUNCTION__);
  1056. }
  1057. #endif
  1058. other = next->segment();
  1059. foundSpan = endSpan = next->start();
  1060. otherEnd = next->end();
  1061. }
  1062. if (!otherEnd) {
  1063. return nullptr;
  1064. }
  1065. int foundStep = foundSpan->step(otherEnd);
  1066. if (*stepPtr != foundStep) {
  1067. return set_last(last, endSpan);
  1068. }
  1069. SkASSERT(*startPtr);
  1070. // SkASSERT(otherEnd >= 0);
  1071. SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast();
  1072. SkOpSpan* foundMin = foundSpan->starter(otherEnd);
  1073. if (foundMin->windValue() != origMin->windValue()
  1074. || foundMin->oppValue() != origMin->oppValue()) {
  1075. return set_last(last, endSpan);
  1076. }
  1077. *startPtr = foundSpan;
  1078. *stepPtr = foundStep;
  1079. if (minPtr) {
  1080. *minPtr = foundMin;
  1081. }
  1082. return other;
  1083. }
  1084. // Please keep this in sync with DebugClearVisited()
  1085. void SkOpSegment::ClearVisited(SkOpSpanBase* span) {
  1086. // reset visited flag back to false
  1087. do {
  1088. SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
  1089. while ((ptT = ptT->next()) != stopPtT) {
  1090. SkOpSegment* opp = ptT->segment();
  1091. opp->resetVisited();
  1092. }
  1093. } while (!span->final() && (span = span->upCast()->next()));
  1094. }
  1095. // Please keep this in sync with debugMissingCoincidence()
  1096. // look for pairs of undetected coincident curves
  1097. // assumes that segments going in have visited flag clear
  1098. // Even though pairs of curves correct detect coincident runs, a run may be missed
  1099. // if the coincidence is a product of multiple intersections. For instance, given
  1100. // curves A, B, and C:
  1101. // A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
  1102. // the end of C that the intersection is replaced with the end of C.
  1103. // Even though A-B correctly do not detect an intersection at point 2,
  1104. // the resulting run from point 1 to point 2 is coincident on A and B.
  1105. bool SkOpSegment::missingCoincidence() {
  1106. if (this->done()) {
  1107. return false;
  1108. }
  1109. SkOpSpan* prior = nullptr;
  1110. SkOpSpanBase* spanBase = &fHead;
  1111. bool result = false;
  1112. int safetyNet = 100000;
  1113. do {
  1114. SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
  1115. SkOPASSERT(ptT->span() == spanBase);
  1116. while ((ptT = ptT->next()) != spanStopPtT) {
  1117. if (!--safetyNet) {
  1118. return false;
  1119. }
  1120. if (ptT->deleted()) {
  1121. continue;
  1122. }
  1123. SkOpSegment* opp = ptT->span()->segment();
  1124. if (opp->done()) {
  1125. continue;
  1126. }
  1127. // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence
  1128. if (!opp->visited()) {
  1129. continue;
  1130. }
  1131. if (spanBase == &fHead) {
  1132. continue;
  1133. }
  1134. if (ptT->segment() == this) {
  1135. continue;
  1136. }
  1137. SkOpSpan* span = spanBase->upCastable();
  1138. // FIXME?: this assumes that if the opposite segment is coincident then no more
  1139. // coincidence needs to be detected. This may not be true.
  1140. if (span && span->containsCoincidence(opp)) {
  1141. continue;
  1142. }
  1143. if (spanBase->containsCoinEnd(opp)) {
  1144. continue;
  1145. }
  1146. SkOpPtT* priorPtT = nullptr, * priorStopPtT;
  1147. // find prior span containing opp segment
  1148. SkOpSegment* priorOpp = nullptr;
  1149. SkOpSpan* priorTest = spanBase->prev();
  1150. while (!priorOpp && priorTest) {
  1151. priorStopPtT = priorPtT = priorTest->ptT();
  1152. while ((priorPtT = priorPtT->next()) != priorStopPtT) {
  1153. if (priorPtT->deleted()) {
  1154. continue;
  1155. }
  1156. SkOpSegment* segment = priorPtT->span()->segment();
  1157. if (segment == opp) {
  1158. prior = priorTest;
  1159. priorOpp = opp;
  1160. break;
  1161. }
  1162. }
  1163. priorTest = priorTest->prev();
  1164. }
  1165. if (!priorOpp) {
  1166. continue;
  1167. }
  1168. if (priorPtT == ptT) {
  1169. continue;
  1170. }
  1171. SkOpPtT* oppStart = prior->ptT();
  1172. SkOpPtT* oppEnd = spanBase->ptT();
  1173. bool swapped = priorPtT->fT > ptT->fT;
  1174. if (swapped) {
  1175. using std::swap;
  1176. swap(priorPtT, ptT);
  1177. swap(oppStart, oppEnd);
  1178. }
  1179. SkOpCoincidence* coincidences = this->globalState()->coincidence();
  1180. SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
  1181. SkOpPtT* rootPtT = ptT->span()->ptT();
  1182. SkOpPtT* rootOppStart = oppStart->span()->ptT();
  1183. SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
  1184. if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
  1185. goto swapBack;
  1186. }
  1187. if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
  1188. // mark coincidence
  1189. #if DEBUG_COINCIDENCE_VERBOSE
  1190. SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
  1191. rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
  1192. rootOppEnd->debugID());
  1193. #endif
  1194. if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
  1195. coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
  1196. }
  1197. #if DEBUG_COINCIDENCE
  1198. SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd));
  1199. #endif
  1200. result = true;
  1201. }
  1202. swapBack:
  1203. if (swapped) {
  1204. using std::swap;
  1205. swap(priorPtT, ptT);
  1206. }
  1207. }
  1208. } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
  1209. ClearVisited(&fHead);
  1210. return result;
  1211. }
  1212. // please keep this in sync with debugMoveMultiples()
  1213. // if a span has more than one intersection, merge the other segments' span as needed
  1214. bool SkOpSegment::moveMultiples() {
  1215. debugValidate();
  1216. SkOpSpanBase* test = &fHead;
  1217. do {
  1218. int addCount = test->spanAddsCount();
  1219. // FAIL_IF(addCount < 1);
  1220. if (addCount <= 1) {
  1221. continue;
  1222. }
  1223. SkOpPtT* startPtT = test->ptT();
  1224. SkOpPtT* testPtT = startPtT;
  1225. int safetyHatch = 1000000;
  1226. do { // iterate through all spans associated with start
  1227. if (!--safetyHatch) {
  1228. return false;
  1229. }
  1230. SkOpSpanBase* oppSpan = testPtT->span();
  1231. if (oppSpan->spanAddsCount() == addCount) {
  1232. continue;
  1233. }
  1234. if (oppSpan->deleted()) {
  1235. continue;
  1236. }
  1237. SkOpSegment* oppSegment = oppSpan->segment();
  1238. if (oppSegment == this) {
  1239. continue;
  1240. }
  1241. // find range of spans to consider merging
  1242. SkOpSpanBase* oppPrev = oppSpan;
  1243. SkOpSpanBase* oppFirst = oppSpan;
  1244. while ((oppPrev = oppPrev->prev())) {
  1245. if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
  1246. break;
  1247. }
  1248. if (oppPrev->spanAddsCount() == addCount) {
  1249. continue;
  1250. }
  1251. if (oppPrev->deleted()) {
  1252. continue;
  1253. }
  1254. oppFirst = oppPrev;
  1255. }
  1256. SkOpSpanBase* oppNext = oppSpan;
  1257. SkOpSpanBase* oppLast = oppSpan;
  1258. while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) {
  1259. if (!roughly_equal(oppNext->t(), oppSpan->t())) {
  1260. break;
  1261. }
  1262. if (oppNext->spanAddsCount() == addCount) {
  1263. continue;
  1264. }
  1265. if (oppNext->deleted()) {
  1266. continue;
  1267. }
  1268. oppLast = oppNext;
  1269. }
  1270. if (oppFirst == oppLast) {
  1271. continue;
  1272. }
  1273. SkOpSpanBase* oppTest = oppFirst;
  1274. do {
  1275. if (oppTest == oppSpan) {
  1276. continue;
  1277. }
  1278. // check to see if the candidate meets specific criteria:
  1279. // it contains spans of segments in test's loop but not including 'this'
  1280. SkOpPtT* oppStartPtT = oppTest->ptT();
  1281. SkOpPtT* oppPtT = oppStartPtT;
  1282. while ((oppPtT = oppPtT->next()) != oppStartPtT) {
  1283. SkOpSegment* oppPtTSegment = oppPtT->segment();
  1284. if (oppPtTSegment == this) {
  1285. goto tryNextSpan;
  1286. }
  1287. SkOpPtT* matchPtT = startPtT;
  1288. do {
  1289. if (matchPtT->segment() == oppPtTSegment) {
  1290. goto foundMatch;
  1291. }
  1292. } while ((matchPtT = matchPtT->next()) != startPtT);
  1293. goto tryNextSpan;
  1294. foundMatch: // merge oppTest and oppSpan
  1295. oppSegment->debugValidate();
  1296. oppTest->mergeMatches(oppSpan);
  1297. oppTest->addOpp(oppSpan);
  1298. oppSegment->debugValidate();
  1299. goto checkNextSpan;
  1300. }
  1301. tryNextSpan:
  1302. ;
  1303. } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
  1304. } while ((testPtT = testPtT->next()) != startPtT);
  1305. checkNextSpan:
  1306. ;
  1307. } while ((test = test->final() ? nullptr : test->upCast()->next()));
  1308. debugValidate();
  1309. return true;
  1310. }
  1311. // adjacent spans may have points close by
  1312. bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan,
  1313. bool* found) const {
  1314. const SkOpPtT* refHead = refSpan->ptT();
  1315. const SkOpPtT* checkHead = checkSpan->ptT();
  1316. // if the first pt pair from adjacent spans are far apart, assume that all are far enough apart
  1317. if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) {
  1318. #if DEBUG_COINCIDENCE
  1319. // verify that no combination of points are close
  1320. const SkOpPtT* dBugRef = refHead;
  1321. do {
  1322. const SkOpPtT* dBugCheck = checkHead;
  1323. do {
  1324. SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
  1325. dBugCheck = dBugCheck->next();
  1326. } while (dBugCheck != checkHead);
  1327. dBugRef = dBugRef->next();
  1328. } while (dBugRef != refHead);
  1329. #endif
  1330. *found = false;
  1331. return true;
  1332. }
  1333. // check only unique points
  1334. SkScalar distSqBest = SK_ScalarMax;
  1335. const SkOpPtT* refBest = nullptr;
  1336. const SkOpPtT* checkBest = nullptr;
  1337. const SkOpPtT* ref = refHead;
  1338. do {
  1339. if (ref->deleted()) {
  1340. continue;
  1341. }
  1342. while (ref->ptAlreadySeen(refHead)) {
  1343. ref = ref->next();
  1344. if (ref == refHead) {
  1345. goto doneCheckingDistance;
  1346. }
  1347. }
  1348. const SkOpPtT* check = checkHead;
  1349. const SkOpSegment* refSeg = ref->segment();
  1350. int escapeHatch = 100000; // defend against infinite loops
  1351. do {
  1352. if (check->deleted()) {
  1353. continue;
  1354. }
  1355. while (check->ptAlreadySeen(checkHead)) {
  1356. check = check->next();
  1357. if (check == checkHead) {
  1358. goto nextRef;
  1359. }
  1360. }
  1361. SkScalar distSq = SkPointPriv::DistanceToSqd(ref->fPt, check->fPt);
  1362. if (distSqBest > distSq && (refSeg != check->segment()
  1363. || !refSeg->ptsDisjoint(*ref, *check))) {
  1364. distSqBest = distSq;
  1365. refBest = ref;
  1366. checkBest = check;
  1367. }
  1368. if (--escapeHatch <= 0) {
  1369. return false;
  1370. }
  1371. } while ((check = check->next()) != checkHead);
  1372. nextRef:
  1373. ;
  1374. } while ((ref = ref->next()) != refHead);
  1375. doneCheckingDistance:
  1376. *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT,
  1377. checkBest->fPt);
  1378. return true;
  1379. }
  1380. // Please keep this function in sync with debugMoveNearby()
  1381. // Move nearby t values and pts so they all hang off the same span. Alignment happens later.
  1382. bool SkOpSegment::moveNearby() {
  1383. debugValidate();
  1384. // release undeleted spans pointing to this seg that are linked to the primary span
  1385. SkOpSpanBase* spanBase = &fHead;
  1386. int escapeHatch = 9999; // the largest count for a regular test is 50; for a fuzzer, 500
  1387. do {
  1388. SkOpPtT* ptT = spanBase->ptT();
  1389. const SkOpPtT* headPtT = ptT;
  1390. while ((ptT = ptT->next()) != headPtT) {
  1391. if (!--escapeHatch) {
  1392. return false;
  1393. }
  1394. SkOpSpanBase* test = ptT->span();
  1395. if (ptT->segment() == this && !ptT->deleted() && test != spanBase
  1396. && test->ptT() == ptT) {
  1397. if (test->final()) {
  1398. if (spanBase == &fHead) {
  1399. this->clearAll();
  1400. return true;
  1401. }
  1402. spanBase->upCast()->release(ptT);
  1403. } else if (test->prev()) {
  1404. test->upCast()->release(headPtT);
  1405. }
  1406. break;
  1407. }
  1408. }
  1409. spanBase = spanBase->upCast()->next();
  1410. } while (!spanBase->final());
  1411. // This loop looks for adjacent spans which are near by
  1412. spanBase = &fHead;
  1413. do { // iterate through all spans associated with start
  1414. SkOpSpanBase* test = spanBase->upCast()->next();
  1415. bool found;
  1416. if (!this->spansNearby(spanBase, test, &found)) {
  1417. return false;
  1418. }
  1419. if (found) {
  1420. if (test->final()) {
  1421. if (spanBase->prev()) {
  1422. test->merge(spanBase->upCast());
  1423. } else {
  1424. this->clearAll();
  1425. return true;
  1426. }
  1427. } else {
  1428. spanBase->merge(test->upCast());
  1429. }
  1430. }
  1431. spanBase = test;
  1432. } while (!spanBase->final());
  1433. debugValidate();
  1434. return true;
  1435. }
  1436. bool SkOpSegment::operand() const {
  1437. return fContour->operand();
  1438. }
  1439. bool SkOpSegment::oppXor() const {
  1440. return fContour->oppXor();
  1441. }
  1442. bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const {
  1443. if (fVerb == SkPath::kLine_Verb) {
  1444. return false;
  1445. }
  1446. // quads (and cubics) can loop back to nearly a line so that an opposite curve
  1447. // hits in two places with very different t values.
  1448. // OPTIMIZATION: curves could be preflighted so that, for example, something like
  1449. // 'controls contained by ends' could avoid this check for common curves
  1450. // 'ends are extremes in x or y' is cheaper to compute and real-world common
  1451. // on the other hand, the below check is relatively inexpensive
  1452. double midT = (t1 + t2) / 2;
  1453. SkPoint midPt = this->ptAtT(midT);
  1454. double seDistSq = SkTMax(SkPointPriv::DistanceToSqd(pt1, pt2) * 2, FLT_EPSILON * 2);
  1455. return SkPointPriv::DistanceToSqd(midPt, pt1) > seDistSq ||
  1456. SkPointPriv::DistanceToSqd(midPt, pt2) > seDistSq;
  1457. }
  1458. void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
  1459. int* maxWinding, int* sumWinding) {
  1460. int deltaSum = SpanSign(start, end);
  1461. *maxWinding = *sumMiWinding;
  1462. *sumWinding = *sumMiWinding -= deltaSum;
  1463. SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
  1464. }
  1465. void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding,
  1466. int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding,
  1467. int* oppSumWinding) {
  1468. int deltaSum = SpanSign(start, end);
  1469. int oppDeltaSum = OppSign(start, end);
  1470. if (operand()) {
  1471. *maxWinding = *sumSuWinding;
  1472. *sumWinding = *sumSuWinding -= deltaSum;
  1473. *oppMaxWinding = *sumMiWinding;
  1474. *oppSumWinding = *sumMiWinding -= oppDeltaSum;
  1475. } else {
  1476. *maxWinding = *sumMiWinding;
  1477. *sumWinding = *sumMiWinding -= deltaSum;
  1478. *oppMaxWinding = *sumSuWinding;
  1479. *oppSumWinding = *sumSuWinding -= oppDeltaSum;
  1480. }
  1481. SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM);
  1482. SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM);
  1483. }
  1484. bool SkOpSegment::sortAngles() {
  1485. SkOpSpanBase* span = &this->fHead;
  1486. do {
  1487. SkOpAngle* fromAngle = span->fromAngle();
  1488. SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle();
  1489. if (!fromAngle && !toAngle) {
  1490. continue;
  1491. }
  1492. #if DEBUG_ANGLE
  1493. bool wroteAfterHeader = false;
  1494. #endif
  1495. SkOpAngle* baseAngle = fromAngle;
  1496. if (fromAngle && toAngle) {
  1497. #if DEBUG_ANGLE
  1498. SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(),
  1499. span->debugID());
  1500. wroteAfterHeader = true;
  1501. #endif
  1502. FAIL_IF(!fromAngle->insert(toAngle));
  1503. } else if (!fromAngle) {
  1504. baseAngle = toAngle;
  1505. }
  1506. SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
  1507. int safetyNet = 1000000;
  1508. do {
  1509. if (!--safetyNet) {
  1510. return false;
  1511. }
  1512. SkOpSpanBase* oSpan = ptT->span();
  1513. if (oSpan == span) {
  1514. continue;
  1515. }
  1516. SkOpAngle* oAngle = oSpan->fromAngle();
  1517. if (oAngle) {
  1518. #if DEBUG_ANGLE
  1519. if (!wroteAfterHeader) {
  1520. SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
  1521. span->t(), span->debugID());
  1522. wroteAfterHeader = true;
  1523. }
  1524. #endif
  1525. if (!oAngle->loopContains(baseAngle)) {
  1526. baseAngle->insert(oAngle);
  1527. }
  1528. }
  1529. if (!oSpan->final()) {
  1530. oAngle = oSpan->upCast()->toAngle();
  1531. if (oAngle) {
  1532. #if DEBUG_ANGLE
  1533. if (!wroteAfterHeader) {
  1534. SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(),
  1535. span->t(), span->debugID());
  1536. wroteAfterHeader = true;
  1537. }
  1538. #endif
  1539. if (!oAngle->loopContains(baseAngle)) {
  1540. baseAngle->insert(oAngle);
  1541. }
  1542. }
  1543. }
  1544. } while ((ptT = ptT->next()) != stopPtT);
  1545. if (baseAngle->loopCount() == 1) {
  1546. span->setFromAngle(nullptr);
  1547. if (toAngle) {
  1548. span->upCast()->setToAngle(nullptr);
  1549. }
  1550. baseAngle = nullptr;
  1551. }
  1552. #if DEBUG_SORT
  1553. SkASSERT(!baseAngle || baseAngle->loopCount() > 1);
  1554. #endif
  1555. } while (!span->final() && (span = span->upCast()->next()));
  1556. return true;
  1557. }
  1558. bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
  1559. SkDCurve* edge) const {
  1560. SkASSERT(start != end);
  1561. const SkOpPtT& startPtT = *start->ptT();
  1562. const SkOpPtT& endPtT = *end->ptT();
  1563. SkDEBUGCODE(edge->fVerb = fVerb);
  1564. edge->fCubic[0].set(startPtT.fPt);
  1565. int points = SkPathOpsVerbToPoints(fVerb);
  1566. edge->fCubic[points].set(endPtT.fPt);
  1567. if (fVerb == SkPath::kLine_Verb) {
  1568. return false;
  1569. }
  1570. double startT = startPtT.fT;
  1571. double endT = endPtT.fT;
  1572. if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) {
  1573. // don't compute midpoints if we already have them
  1574. if (fVerb == SkPath::kQuad_Verb) {
  1575. edge->fLine[1].set(fPts[1]);
  1576. return false;
  1577. }
  1578. if (fVerb == SkPath::kConic_Verb) {
  1579. edge->fConic[1].set(fPts[1]);
  1580. edge->fConic.fWeight = fWeight;
  1581. return false;
  1582. }
  1583. SkASSERT(fVerb == SkPath::kCubic_Verb);
  1584. if (startT == 0) {
  1585. edge->fCubic[1].set(fPts[1]);
  1586. edge->fCubic[2].set(fPts[2]);
  1587. return false;
  1588. }
  1589. edge->fCubic[1].set(fPts[2]);
  1590. edge->fCubic[2].set(fPts[1]);
  1591. return false;
  1592. }
  1593. if (fVerb == SkPath::kQuad_Verb) {
  1594. edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT);
  1595. } else if (fVerb == SkPath::kConic_Verb) {
  1596. edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2],
  1597. startT, endT, &edge->fConic.fWeight);
  1598. } else {
  1599. SkASSERT(fVerb == SkPath::kCubic_Verb);
  1600. SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]);
  1601. }
  1602. return true;
  1603. }
  1604. bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
  1605. const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const {
  1606. // average t, find mid pt
  1607. double midT = (prior->t() + spanBase->t()) / 2;
  1608. SkPoint midPt = this->ptAtT(midT);
  1609. bool coincident = true;
  1610. // if the mid pt is not near either end pt, project perpendicular through opp seg
  1611. if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
  1612. && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
  1613. if (priorPtT->span() == ptT->span()) {
  1614. return false;
  1615. }
  1616. coincident = false;
  1617. SkIntersections i;
  1618. SkDCurve curvePart;
  1619. this->subDivide(prior, spanBase, &curvePart);
  1620. SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f);
  1621. SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f);
  1622. SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}};
  1623. SkDCurve oppPart;
  1624. opp->subDivide(priorPtT->span(), ptT->span(), &oppPart);
  1625. (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i);
  1626. // measure distance and see if it's small enough to denote coincidence
  1627. for (int index = 0; index < i.used(); ++index) {
  1628. if (!between(0, i[0][index], 1)) {
  1629. continue;
  1630. }
  1631. SkDPoint oppPt = i.pt(index);
  1632. if (oppPt.approximatelyDEqual(midPt)) {
  1633. // the coincidence can occur at almost any angle
  1634. coincident = true;
  1635. }
  1636. }
  1637. }
  1638. return coincident;
  1639. }
  1640. SkOpSpan* SkOpSegment::undoneSpan() {
  1641. SkOpSpan* span = &fHead;
  1642. SkOpSpanBase* next;
  1643. do {
  1644. next = span->next();
  1645. if (!span->done()) {
  1646. return span;
  1647. }
  1648. } while (!next->final() && (span = next->upCast()));
  1649. return nullptr;
  1650. }
  1651. int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const {
  1652. const SkOpSpan* lesser = start->starter(end);
  1653. int oppWinding = lesser->oppSum();
  1654. int oppSpanWinding = SkOpSegment::OppSign(start, end);
  1655. if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding)
  1656. && oppWinding != SK_MaxS32) {
  1657. oppWinding -= oppSpanWinding;
  1658. }
  1659. return oppWinding;
  1660. }
  1661. int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const {
  1662. const SkOpSpanBase* startSpan = angle->start();
  1663. const SkOpSpanBase* endSpan = angle->end();
  1664. return updateOppWinding(endSpan, startSpan);
  1665. }
  1666. int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const {
  1667. const SkOpSpanBase* startSpan = angle->start();
  1668. const SkOpSpanBase* endSpan = angle->end();
  1669. return updateOppWinding(startSpan, endSpan);
  1670. }
  1671. int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) {
  1672. SkOpSpan* lesser = start->starter(end);
  1673. int winding = lesser->windSum();
  1674. if (winding == SK_MinS32) {
  1675. winding = lesser->computeWindSum();
  1676. }
  1677. if (winding == SK_MinS32) {
  1678. return winding;
  1679. }
  1680. int spanWinding = SkOpSegment::SpanSign(start, end);
  1681. if (winding && UseInnerWinding(winding - spanWinding, winding)
  1682. && winding != SK_MaxS32) {
  1683. winding -= spanWinding;
  1684. }
  1685. return winding;
  1686. }
  1687. int SkOpSegment::updateWinding(SkOpAngle* angle) {
  1688. SkOpSpanBase* startSpan = angle->start();
  1689. SkOpSpanBase* endSpan = angle->end();
  1690. return updateWinding(endSpan, startSpan);
  1691. }
  1692. int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) {
  1693. SkOpSpanBase* startSpan = angle->start();
  1694. SkOpSpanBase* endSpan = angle->end();
  1695. return updateWinding(startSpan, endSpan);
  1696. }
  1697. // OPTIMIZATION: does the following also work, and is it any faster?
  1698. // return outerWinding * innerWinding > 0
  1699. // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0)))
  1700. bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) {
  1701. SkASSERT(outerWinding != SK_MaxS32);
  1702. SkASSERT(innerWinding != SK_MaxS32);
  1703. int absOut = SkTAbs(outerWinding);
  1704. int absIn = SkTAbs(innerWinding);
  1705. bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn;
  1706. return result;
  1707. }
  1708. int SkOpSegment::windSum(const SkOpAngle* angle) const {
  1709. const SkOpSpan* minSpan = angle->start()->starter(angle->end());
  1710. return minSpan->windSum();
  1711. }