SkOpCoincidence.cpp 54 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448
  1. /*
  2. * Copyright 2015 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/pathops/SkOpCoincidence.h"
  8. #include "src/pathops/SkOpSegment.h"
  9. #include "src/pathops/SkPathOpsTSect.h"
  10. #include <utility>
  11. // returns true if coincident span's start and end are the same
  12. bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const {
  13. return (fCoinPtTStart == test && fCoinPtTEnd->contains(test))
  14. || (fCoinPtTEnd == test && fCoinPtTStart->contains(test))
  15. || (fOppPtTStart == test && fOppPtTEnd->contains(test))
  16. || (fOppPtTEnd == test && fOppPtTStart->contains(test));
  17. }
  18. // out of line since this function is referenced by address
  19. const SkOpPtT* SkCoincidentSpans::coinPtTEnd() const {
  20. return fCoinPtTEnd;
  21. }
  22. // out of line since this function is referenced by address
  23. const SkOpPtT* SkCoincidentSpans::coinPtTStart() const {
  24. return fCoinPtTStart;
  25. }
  26. // sets the span's end to the ptT referenced by the previous-next
  27. void SkCoincidentSpans::correctOneEnd(
  28. const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
  29. void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) {
  30. const SkOpPtT* origPtT = (this->*getEnd)();
  31. const SkOpSpanBase* origSpan = origPtT->span();
  32. const SkOpSpan* prev = origSpan->prev();
  33. const SkOpPtT* testPtT = prev ? prev->next()->ptT()
  34. : origSpan->upCast()->next()->prev()->ptT();
  35. if (origPtT != testPtT) {
  36. (this->*setEnd)(testPtT);
  37. }
  38. }
  39. /* Please keep this in sync with debugCorrectEnds */
  40. // FIXME: member pointers have fallen out of favor and can be replaced with
  41. // an alternative approach.
  42. // makes all span ends agree with the segment's spans that define them
  43. void SkCoincidentSpans::correctEnds() {
  44. this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart);
  45. this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd);
  46. this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart);
  47. this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd);
  48. }
  49. /* Please keep this in sync with debugExpand */
  50. // expand the range by checking adjacent spans for coincidence
  51. bool SkCoincidentSpans::expand() {
  52. bool expanded = false;
  53. const SkOpSegment* segment = coinPtTStart()->segment();
  54. const SkOpSegment* oppSegment = oppPtTStart()->segment();
  55. do {
  56. const SkOpSpan* start = coinPtTStart()->span()->upCast();
  57. const SkOpSpan* prev = start->prev();
  58. const SkOpPtT* oppPtT;
  59. if (!prev || !(oppPtT = prev->contains(oppSegment))) {
  60. break;
  61. }
  62. double midT = (prev->t() + start->t()) / 2;
  63. if (!segment->isClose(midT, oppSegment)) {
  64. break;
  65. }
  66. setStarts(prev->ptT(), oppPtT);
  67. expanded = true;
  68. } while (true);
  69. do {
  70. const SkOpSpanBase* end = coinPtTEnd()->span();
  71. SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
  72. if (next && next->deleted()) {
  73. break;
  74. }
  75. const SkOpPtT* oppPtT;
  76. if (!next || !(oppPtT = next->contains(oppSegment))) {
  77. break;
  78. }
  79. double midT = (end->t() + next->t()) / 2;
  80. if (!segment->isClose(midT, oppSegment)) {
  81. break;
  82. }
  83. setEnds(next->ptT(), oppPtT);
  84. expanded = true;
  85. } while (true);
  86. return expanded;
  87. }
  88. // increase the range of this span
  89. bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
  90. const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
  91. bool result = false;
  92. if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped()
  93. ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) {
  94. this->setStarts(coinPtTStart, oppPtTStart);
  95. result = true;
  96. }
  97. if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped()
  98. ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) {
  99. this->setEnds(coinPtTEnd, oppPtTEnd);
  100. result = true;
  101. }
  102. return result;
  103. }
  104. // set the range of this span
  105. void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart,
  106. const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
  107. SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart));
  108. fNext = next;
  109. this->setStarts(coinPtTStart, oppPtTStart);
  110. this->setEnds(coinPtTEnd, oppPtTEnd);
  111. }
  112. // returns true if both points are inside this
  113. bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const {
  114. if (s->fT > e->fT) {
  115. using std::swap;
  116. swap(s, e);
  117. }
  118. if (s->segment() == fCoinPtTStart->segment()) {
  119. return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT;
  120. } else {
  121. SkASSERT(s->segment() == fOppPtTStart->segment());
  122. double oppTs = fOppPtTStart->fT;
  123. double oppTe = fOppPtTEnd->fT;
  124. if (oppTs > oppTe) {
  125. using std::swap;
  126. swap(oppTs, oppTe);
  127. }
  128. return oppTs <= s->fT && e->fT <= oppTe;
  129. }
  130. }
  131. // out of line since this function is referenced by address
  132. const SkOpPtT* SkCoincidentSpans::oppPtTStart() const {
  133. return fOppPtTStart;
  134. }
  135. // out of line since this function is referenced by address
  136. const SkOpPtT* SkCoincidentSpans::oppPtTEnd() const {
  137. return fOppPtTEnd;
  138. }
  139. // A coincident span is unordered if the pairs of points in the main and opposite curves'
  140. // t values do not ascend or descend. For instance, if a tightly arced quadratic is
  141. // coincident with another curve, it may intersect it out of order.
  142. bool SkCoincidentSpans::ordered(bool* result) const {
  143. const SkOpSpanBase* start = this->coinPtTStart()->span();
  144. const SkOpSpanBase* end = this->coinPtTEnd()->span();
  145. const SkOpSpanBase* next = start->upCast()->next();
  146. if (next == end) {
  147. *result = true;
  148. return true;
  149. }
  150. bool flipped = this->flipped();
  151. const SkOpSegment* oppSeg = this->oppPtTStart()->segment();
  152. double oppLastT = fOppPtTStart->fT;
  153. do {
  154. const SkOpPtT* opp = next->contains(oppSeg);
  155. if (!opp) {
  156. // SkOPOBJASSERT(start, 0); // may assert if coincident span isn't fully processed
  157. return false;
  158. }
  159. if ((oppLastT > opp->fT) != flipped) {
  160. *result = false;
  161. return true;
  162. }
  163. oppLastT = opp->fT;
  164. if (next == end) {
  165. break;
  166. }
  167. if (!next->upCastable()) {
  168. *result = false;
  169. return true;
  170. }
  171. next = next->upCast()->next();
  172. } while (true);
  173. *result = true;
  174. return true;
  175. }
  176. // if there is an existing pair that overlaps the addition, extend it
  177. bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
  178. const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
  179. SkCoincidentSpans* test = fHead;
  180. if (!test) {
  181. return false;
  182. }
  183. const SkOpSegment* coinSeg = coinPtTStart->segment();
  184. const SkOpSegment* oppSeg = oppPtTStart->segment();
  185. if (!Ordered(coinPtTStart, oppPtTStart)) {
  186. using std::swap;
  187. swap(coinSeg, oppSeg);
  188. swap(coinPtTStart, oppPtTStart);
  189. swap(coinPtTEnd, oppPtTEnd);
  190. if (coinPtTStart->fT > coinPtTEnd->fT) {
  191. swap(coinPtTStart, coinPtTEnd);
  192. swap(oppPtTStart, oppPtTEnd);
  193. }
  194. }
  195. double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
  196. SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT));
  197. do {
  198. if (coinSeg != test->coinPtTStart()->segment()) {
  199. continue;
  200. }
  201. if (oppSeg != test->oppPtTStart()->segment()) {
  202. continue;
  203. }
  204. double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
  205. double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT);
  206. // if debug check triggers, caller failed to check if extended already exists
  207. SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT
  208. || coinPtTEnd->fT > test->coinPtTEnd()->fT
  209. || oTestMinT > oppMinT || oppMaxT > oTestMaxT);
  210. if ((test->coinPtTStart()->fT <= coinPtTEnd->fT
  211. && coinPtTStart->fT <= test->coinPtTEnd()->fT)
  212. || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) {
  213. test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
  214. return true;
  215. }
  216. } while ((test = test->next()));
  217. return false;
  218. }
  219. // verifies that the coincidence hasn't already been added
  220. static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart,
  221. const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
  222. #if DEBUG_COINCIDENCE
  223. while (check) {
  224. SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd
  225. || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd);
  226. SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd
  227. || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd);
  228. check = check->next();
  229. }
  230. #endif
  231. }
  232. // adds a new coincident pair
  233. void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
  234. SkOpPtT* oppPtTEnd) {
  235. // OPTIMIZE: caller should have already sorted
  236. if (!Ordered(coinPtTStart, oppPtTStart)) {
  237. if (oppPtTStart->fT < oppPtTEnd->fT) {
  238. this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd);
  239. } else {
  240. this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart);
  241. }
  242. return;
  243. }
  244. SkASSERT(Ordered(coinPtTStart, oppPtTStart));
  245. // choose the ptT at the front of the list to track
  246. coinPtTStart = coinPtTStart->span()->ptT();
  247. coinPtTEnd = coinPtTEnd->span()->ptT();
  248. oppPtTStart = oppPtTStart->span()->ptT();
  249. oppPtTEnd = oppPtTEnd->span()->ptT();
  250. SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT);
  251. SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT);
  252. SkOPASSERT(!coinPtTStart->deleted());
  253. SkOPASSERT(!coinPtTEnd->deleted());
  254. SkOPASSERT(!oppPtTStart->deleted());
  255. SkOPASSERT(!oppPtTEnd->deleted());
  256. DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
  257. DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
  258. SkCoincidentSpans* coinRec = this->globalState()->allocator()->make<SkCoincidentSpans>();
  259. coinRec->init(SkDEBUGCODE(fGlobalState));
  260. coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
  261. fHead = coinRec;
  262. }
  263. // description below
  264. bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) {
  265. const SkOpPtT* testPtT = testSpan->ptT();
  266. const SkOpPtT* stopPtT = testPtT;
  267. const SkOpSegment* baseSeg = base->segment();
  268. int escapeHatch = 100000; // this is 100 times larger than the debugLoopLimit test
  269. while ((testPtT = testPtT->next()) != stopPtT) {
  270. if (--escapeHatch <= 0) {
  271. return false; // if triggered (likely by a fuzz-generated test) too complex to succeed
  272. }
  273. const SkOpSegment* testSeg = testPtT->segment();
  274. if (testPtT->deleted()) {
  275. continue;
  276. }
  277. if (testSeg == baseSeg) {
  278. continue;
  279. }
  280. if (testPtT->span()->ptT() != testPtT) {
  281. continue;
  282. }
  283. if (this->contains(baseSeg, testSeg, testPtT->fT)) {
  284. continue;
  285. }
  286. // intersect perp with base->ptT() with testPtT->segment()
  287. SkDVector dxdy = baseSeg->dSlopeAtT(base->t());
  288. const SkPoint& pt = base->pt();
  289. SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}};
  290. SkIntersections i SkDEBUGCODE((this->globalState()));
  291. (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i);
  292. for (int index = 0; index < i.used(); ++index) {
  293. double t = i[0][index];
  294. if (!between(0, t, 1)) {
  295. continue;
  296. }
  297. SkDPoint oppPt = i.pt(index);
  298. if (!oppPt.approximatelyEqual(pt)) {
  299. continue;
  300. }
  301. SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
  302. SkOpPtT* oppStart = writableSeg->addT(t);
  303. if (oppStart == testPtT) {
  304. continue;
  305. }
  306. SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
  307. oppStart->span()->addOpp(writableBase);
  308. if (oppStart->deleted()) {
  309. continue;
  310. }
  311. SkOpSegment* coinSeg = base->segment();
  312. SkOpSegment* oppSeg = oppStart->segment();
  313. double coinTs, coinTe, oppTs, oppTe;
  314. if (Ordered(coinSeg, oppSeg)) {
  315. coinTs = base->t();
  316. coinTe = testSpan->t();
  317. oppTs = oppStart->fT;
  318. oppTe = testPtT->fT;
  319. } else {
  320. using std::swap;
  321. swap(coinSeg, oppSeg);
  322. coinTs = oppStart->fT;
  323. coinTe = testPtT->fT;
  324. oppTs = base->t();
  325. oppTe = testSpan->t();
  326. }
  327. if (coinTs > coinTe) {
  328. using std::swap;
  329. swap(coinTs, coinTe);
  330. swap(oppTs, oppTe);
  331. }
  332. bool added;
  333. FAIL_IF(!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added));
  334. }
  335. }
  336. return true;
  337. }
  338. // description below
  339. bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
  340. FAIL_IF(!ptT->span()->upCastable());
  341. const SkOpSpan* base = ptT->span()->upCast();
  342. const SkOpSpan* prev = base->prev();
  343. FAIL_IF(!prev);
  344. if (!prev->isCanceled()) {
  345. if (!this->addEndMovedSpans(base, base->prev())) {
  346. return false;
  347. }
  348. }
  349. if (!base->isCanceled()) {
  350. if (!this->addEndMovedSpans(base, base->next())) {
  351. return false;
  352. }
  353. }
  354. return true;
  355. }
  356. /* If A is coincident with B and B includes an endpoint, and A's matching point
  357. is not the endpoint (i.e., there's an implied line connecting B-end and A)
  358. then assume that the same implied line may intersect another curve close to B.
  359. Since we only care about coincidence that was undetected, look at the
  360. ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but
  361. next door) and see if the A matching point is close enough to form another
  362. coincident pair. If so, check for a new coincident span between B-end/A ptT loop
  363. and the adjacent ptT loop.
  364. */
  365. bool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
  366. DEBUG_SET_PHASE();
  367. SkCoincidentSpans* span = fHead;
  368. if (!span) {
  369. return true;
  370. }
  371. fTop = span;
  372. fHead = nullptr;
  373. do {
  374. if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) {
  375. FAIL_IF(1 == span->coinPtTStart()->fT);
  376. bool onEnd = span->coinPtTStart()->fT == 0;
  377. bool oOnEnd = zero_or_one(span->oppPtTStart()->fT);
  378. if (onEnd) {
  379. if (!oOnEnd) { // if both are on end, any nearby intersect was already found
  380. if (!this->addEndMovedSpans(span->oppPtTStart())) {
  381. return false;
  382. }
  383. }
  384. } else if (oOnEnd) {
  385. if (!this->addEndMovedSpans(span->coinPtTStart())) {
  386. return false;
  387. }
  388. }
  389. }
  390. if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) {
  391. bool onEnd = span->coinPtTEnd()->fT == 1;
  392. bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT);
  393. if (onEnd) {
  394. if (!oOnEnd) {
  395. if (!this->addEndMovedSpans(span->oppPtTEnd())) {
  396. return false;
  397. }
  398. }
  399. } else if (oOnEnd) {
  400. if (!this->addEndMovedSpans(span->coinPtTEnd())) {
  401. return false;
  402. }
  403. }
  404. }
  405. } while ((span = span->next()));
  406. this->restoreHead();
  407. return true;
  408. }
  409. /* Please keep this in sync with debugAddExpanded */
  410. // for each coincident pair, match the spans
  411. // if the spans don't match, add the missing pt to the segment and loop it in the opposite span
  412. bool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
  413. DEBUG_SET_PHASE();
  414. SkCoincidentSpans* coin = this->fHead;
  415. if (!coin) {
  416. return true;
  417. }
  418. do {
  419. const SkOpPtT* startPtT = coin->coinPtTStart();
  420. const SkOpPtT* oStartPtT = coin->oppPtTStart();
  421. double priorT = startPtT->fT;
  422. double oPriorT = oStartPtT->fT;
  423. FAIL_IF(!startPtT->contains(oStartPtT));
  424. SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd()));
  425. const SkOpSpanBase* start = startPtT->span();
  426. const SkOpSpanBase* oStart = oStartPtT->span();
  427. const SkOpSpanBase* end = coin->coinPtTEnd()->span();
  428. const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span();
  429. FAIL_IF(oEnd->deleted());
  430. FAIL_IF(!start->upCastable());
  431. const SkOpSpanBase* test = start->upCast()->next();
  432. FAIL_IF(!coin->flipped() && !oStart->upCastable());
  433. const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
  434. FAIL_IF(!oTest);
  435. SkOpSegment* seg = start->segment();
  436. SkOpSegment* oSeg = oStart->segment();
  437. while (test != end || oTest != oEnd) {
  438. const SkOpPtT* containedOpp = test->ptT()->contains(oSeg);
  439. const SkOpPtT* containedThis = oTest->ptT()->contains(seg);
  440. if (!containedOpp || !containedThis) {
  441. // choose the ends, or the first common pt-t list shared by both
  442. double nextT, oNextT;
  443. if (containedOpp) {
  444. nextT = test->t();
  445. oNextT = containedOpp->fT;
  446. } else if (containedThis) {
  447. nextT = containedThis->fT;
  448. oNextT = oTest->t();
  449. } else {
  450. // iterate through until a pt-t list found that contains the other
  451. const SkOpSpanBase* walk = test;
  452. const SkOpPtT* walkOpp;
  453. do {
  454. FAIL_IF(!walk->upCastable());
  455. walk = walk->upCast()->next();
  456. } while (!(walkOpp = walk->ptT()->contains(oSeg))
  457. && walk != coin->coinPtTEnd()->span());
  458. FAIL_IF(!walkOpp);
  459. nextT = walk->t();
  460. oNextT = walkOpp->fT;
  461. }
  462. // use t ranges to guess which one is missing
  463. double startRange = nextT - priorT;
  464. FAIL_IF(!startRange);
  465. double startPart = (test->t() - priorT) / startRange;
  466. double oStartRange = oNextT - oPriorT;
  467. FAIL_IF(!oStartRange);
  468. double oStartPart = (oTest->t() - oPriorT) / oStartRange;
  469. FAIL_IF(startPart == oStartPart);
  470. bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart
  471. : !!containedThis;
  472. bool startOver = false;
  473. bool success = addToOpp ? oSeg->addExpanded(
  474. oPriorT + oStartRange * startPart, test, &startOver)
  475. : seg->addExpanded(
  476. priorT + startRange * oStartPart, oTest, &startOver);
  477. FAIL_IF(!success);
  478. if (startOver) {
  479. test = start;
  480. oTest = oStart;
  481. }
  482. end = coin->coinPtTEnd()->span();
  483. oEnd = coin->oppPtTEnd()->span();
  484. }
  485. if (test != end) {
  486. FAIL_IF(!test->upCastable());
  487. priorT = test->t();
  488. test = test->upCast()->next();
  489. }
  490. if (oTest != oEnd) {
  491. oPriorT = oTest->t();
  492. if (coin->flipped()) {
  493. oTest = oTest->prev();
  494. } else {
  495. FAIL_IF(!oTest->upCastable());
  496. oTest = oTest->upCast()->next();
  497. }
  498. FAIL_IF(!oTest);
  499. }
  500. }
  501. } while ((coin = coin->next()));
  502. return true;
  503. }
  504. // given a t span, map the same range on the coincident span
  505. /*
  506. the curves may not scale linearly, so interpolation may only happen within known points
  507. remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s
  508. then repeat to capture over1e
  509. */
  510. double SkOpCoincidence::TRange(const SkOpPtT* overS, double t,
  511. const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) {
  512. const SkOpSpanBase* work = overS->span();
  513. const SkOpPtT* foundStart = nullptr;
  514. const SkOpPtT* foundEnd = nullptr;
  515. const SkOpPtT* coinStart = nullptr;
  516. const SkOpPtT* coinEnd = nullptr;
  517. do {
  518. const SkOpPtT* contained = work->contains(coinSeg);
  519. if (!contained) {
  520. if (work->final()) {
  521. break;
  522. }
  523. continue;
  524. }
  525. if (work->t() <= t) {
  526. coinStart = contained;
  527. foundStart = work->ptT();
  528. }
  529. if (work->t() >= t) {
  530. coinEnd = contained;
  531. foundEnd = work->ptT();
  532. break;
  533. }
  534. SkASSERT(work->ptT() != overE);
  535. } while ((work = work->upCast()->next()));
  536. if (!coinStart || !coinEnd) {
  537. return 1;
  538. }
  539. // while overS->fT <=t and overS contains coinSeg
  540. double denom = foundEnd->fT - foundStart->fT;
  541. double sRatio = denom ? (t - foundStart->fT) / denom : 1;
  542. return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio;
  543. }
  544. // return true if span overlaps existing and needs to adjust the coincident list
  545. bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check,
  546. const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
  547. double coinTs, double coinTe, double oppTs, double oppTe,
  548. SkTDArray<SkCoincidentSpans*>* overlaps) const {
  549. if (!Ordered(coinSeg, oppSeg)) {
  550. if (oppTs < oppTe) {
  551. return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe,
  552. overlaps);
  553. }
  554. return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps);
  555. }
  556. bool swapOpp = oppTs > oppTe;
  557. if (swapOpp) {
  558. using std::swap;
  559. swap(oppTs, oppTe);
  560. }
  561. do {
  562. if (check->coinPtTStart()->segment() != coinSeg) {
  563. continue;
  564. }
  565. if (check->oppPtTStart()->segment() != oppSeg) {
  566. continue;
  567. }
  568. double checkTs = check->coinPtTStart()->fT;
  569. double checkTe = check->coinPtTEnd()->fT;
  570. bool coinOutside = coinTe < checkTs || coinTs > checkTe;
  571. double oCheckTs = check->oppPtTStart()->fT;
  572. double oCheckTe = check->oppPtTEnd()->fT;
  573. if (swapOpp) {
  574. if (oCheckTs <= oCheckTe) {
  575. return false;
  576. }
  577. using std::swap;
  578. swap(oCheckTs, oCheckTe);
  579. }
  580. bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe;
  581. if (coinOutside && oppOutside) {
  582. continue;
  583. }
  584. bool coinInside = coinTe <= checkTe && coinTs >= checkTs;
  585. bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs;
  586. if (coinInside && oppInside) { // already included, do nothing
  587. return false;
  588. }
  589. *overlaps->append() = check; // partial overlap, extend existing entry
  590. } while ((check = check->next()));
  591. return true;
  592. }
  593. /* Please keep this in sync with debugAddIfMissing() */
  594. // note that over1s, over1e, over2s, over2e are ordered
  595. bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
  596. double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added
  597. SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) {
  598. SkASSERT(tStart < tEnd);
  599. SkASSERT(over1s->fT < over1e->fT);
  600. SkASSERT(between(over1s->fT, tStart, over1e->fT));
  601. SkASSERT(between(over1s->fT, tEnd, over1e->fT));
  602. SkASSERT(over2s->fT < over2e->fT);
  603. SkASSERT(between(over2s->fT, tStart, over2e->fT));
  604. SkASSERT(between(over2s->fT, tEnd, over2e->fT));
  605. SkASSERT(over1s->segment() == over1e->segment());
  606. SkASSERT(over2s->segment() == over2e->segment());
  607. SkASSERT(over1s->segment() == over2s->segment());
  608. SkASSERT(over1s->segment() != coinSeg);
  609. SkASSERT(over1s->segment() != oppSeg);
  610. SkASSERT(coinSeg != oppSeg);
  611. double coinTs, coinTe, oppTs, oppTe;
  612. coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e));
  613. coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e));
  614. SkOpSpanBase::Collapsed result = coinSeg->collapsed(coinTs, coinTe);
  615. if (SkOpSpanBase::Collapsed::kNo != result) {
  616. return SkOpSpanBase::Collapsed::kYes == result;
  617. }
  618. oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e));
  619. oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e));
  620. result = oppSeg->collapsed(oppTs, oppTe);
  621. if (SkOpSpanBase::Collapsed::kNo != result) {
  622. return SkOpSpanBase::Collapsed::kYes == result;
  623. }
  624. if (coinTs > coinTe) {
  625. using std::swap;
  626. swap(coinTs, coinTe);
  627. swap(oppTs, oppTe);
  628. }
  629. (void) this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added);
  630. return true;
  631. }
  632. /* Please keep this in sync with debugAddOrOverlap() */
  633. // If this is called by addEndMovedSpans(), a returned false propogates out to an abort.
  634. // If this is called by AddIfMissing(), a returned false indicates there was nothing to add
  635. bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
  636. double coinTs, double coinTe, double oppTs, double oppTe, bool* added) {
  637. SkTDArray<SkCoincidentSpans*> overlaps;
  638. FAIL_IF(!fTop);
  639. if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) {
  640. return true;
  641. }
  642. if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs,
  643. coinTe, oppTs, oppTe, &overlaps)) {
  644. return true;
  645. }
  646. SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr;
  647. for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing
  648. SkCoincidentSpans* test = overlaps[index];
  649. if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) {
  650. overlap->setCoinPtTStart(test->coinPtTStart());
  651. }
  652. if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) {
  653. overlap->setCoinPtTEnd(test->coinPtTEnd());
  654. }
  655. if (overlap->flipped()
  656. ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT
  657. : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) {
  658. overlap->setOppPtTStart(test->oppPtTStart());
  659. }
  660. if (overlap->flipped()
  661. ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT
  662. : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) {
  663. overlap->setOppPtTEnd(test->oppPtTEnd());
  664. }
  665. if (!fHead || !this->release(fHead, test)) {
  666. SkAssertResult(this->release(fTop, test));
  667. }
  668. }
  669. const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg);
  670. const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg);
  671. if (overlap && cs && ce && overlap->contains(cs, ce)) {
  672. return true;
  673. }
  674. FAIL_IF(cs == ce && cs);
  675. const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg);
  676. const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg);
  677. if (overlap && os && oe && overlap->contains(os, oe)) {
  678. return true;
  679. }
  680. FAIL_IF(cs && cs->deleted());
  681. FAIL_IF(os && os->deleted());
  682. FAIL_IF(ce && ce->deleted());
  683. FAIL_IF(oe && oe->deleted());
  684. const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr;
  685. const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr;
  686. FAIL_IF(csExisting && csExisting == ceExisting);
  687. // FAIL_IF(csExisting && (csExisting == ce ||
  688. // csExisting->contains(ceExisting ? ceExisting : ce)));
  689. FAIL_IF(ceExisting && (ceExisting == cs ||
  690. ceExisting->contains(csExisting ? csExisting : cs)));
  691. const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
  692. const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
  693. FAIL_IF(osExisting && osExisting == oeExisting);
  694. FAIL_IF(osExisting && (osExisting == oe ||
  695. osExisting->contains(oeExisting ? oeExisting : oe)));
  696. FAIL_IF(oeExisting && (oeExisting == os ||
  697. oeExisting->contains(osExisting ? osExisting : os)));
  698. // extra line in debug code
  699. this->debugValidate();
  700. if (!cs || !os) {
  701. SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs)
  702. : coinSeg->addT(coinTs);
  703. if (csWritable == ce) {
  704. return true;
  705. }
  706. SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
  707. : oppSeg->addT(oppTs);
  708. FAIL_IF(!csWritable || !osWritable);
  709. csWritable->span()->addOpp(osWritable->span());
  710. cs = csWritable;
  711. os = osWritable->active();
  712. FAIL_IF(!os);
  713. FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted()));
  714. }
  715. if (!ce || !oe) {
  716. SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
  717. : coinSeg->addT(coinTe);
  718. SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe)
  719. : oppSeg->addT(oppTe);
  720. FAIL_IF(!ceWritable->span()->addOpp(oeWritable->span()));
  721. ce = ceWritable;
  722. oe = oeWritable;
  723. }
  724. this->debugValidate();
  725. FAIL_IF(cs->deleted());
  726. FAIL_IF(os->deleted());
  727. FAIL_IF(ce->deleted());
  728. FAIL_IF(oe->deleted());
  729. FAIL_IF(cs->contains(ce) || os->contains(oe));
  730. bool result = true;
  731. if (overlap) {
  732. if (overlap->coinPtTStart()->segment() == coinSeg) {
  733. result = overlap->extend(cs, ce, os, oe);
  734. } else {
  735. if (os->fT > oe->fT) {
  736. using std::swap;
  737. swap(cs, ce);
  738. swap(os, oe);
  739. }
  740. result = overlap->extend(os, oe, cs, ce);
  741. }
  742. #if DEBUG_COINCIDENCE_VERBOSE
  743. if (result) {
  744. overlaps[0]->debugShow();
  745. }
  746. #endif
  747. } else {
  748. this->add(cs, ce, os, oe);
  749. #if DEBUG_COINCIDENCE_VERBOSE
  750. fHead->debugShow();
  751. #endif
  752. }
  753. this->debugValidate();
  754. if (result) {
  755. *added = true;
  756. }
  757. return true;
  758. }
  759. // Please keep this in sync with debugAddMissing()
  760. /* detects overlaps of different coincident runs on same segment */
  761. /* does not detect overlaps for pairs without any segments in common */
  762. // returns true if caller should loop again
  763. bool SkOpCoincidence::addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS()) {
  764. SkCoincidentSpans* outer = fHead;
  765. *added = false;
  766. if (!outer) {
  767. return true;
  768. }
  769. fTop = outer;
  770. fHead = nullptr;
  771. do {
  772. // addifmissing can modify the list that this is walking
  773. // save head so that walker can iterate over old data unperturbed
  774. // addifmissing adds to head freely then add saved head in the end
  775. const SkOpPtT* ocs = outer->coinPtTStart();
  776. FAIL_IF(ocs->deleted());
  777. const SkOpSegment* outerCoin = ocs->segment();
  778. FAIL_IF(outerCoin->done());
  779. const SkOpPtT* oos = outer->oppPtTStart();
  780. if (oos->deleted()) {
  781. return true;
  782. }
  783. const SkOpSegment* outerOpp = oos->segment();
  784. SkOPASSERT(!outerOpp->done());
  785. SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin);
  786. SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp);
  787. SkCoincidentSpans* inner = outer;
  788. #ifdef IS_FUZZING_WITH_LIBFUZZER
  789. int safetyNet = 1000;
  790. #endif
  791. while ((inner = inner->next())) {
  792. #ifdef IS_FUZZING_WITH_LIBFUZZER
  793. if (!--safetyNet) {
  794. return false;
  795. }
  796. #endif
  797. this->debugValidate();
  798. double overS, overE;
  799. const SkOpPtT* ics = inner->coinPtTStart();
  800. FAIL_IF(ics->deleted());
  801. const SkOpSegment* innerCoin = ics->segment();
  802. FAIL_IF(innerCoin->done());
  803. const SkOpPtT* ios = inner->oppPtTStart();
  804. FAIL_IF(ios->deleted());
  805. const SkOpSegment* innerOpp = ios->segment();
  806. SkOPASSERT(!innerOpp->done());
  807. SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin);
  808. SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp);
  809. if (outerCoin == innerCoin) {
  810. const SkOpPtT* oce = outer->coinPtTEnd();
  811. if (oce->deleted()) {
  812. return true;
  813. }
  814. const SkOpPtT* ice = inner->coinPtTEnd();
  815. FAIL_IF(ice->deleted());
  816. if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) {
  817. FAIL_IF(!this->addIfMissing(ocs->starter(oce), ics->starter(ice),
  818. overS, overE, outerOppWritable, innerOppWritable, added
  819. SkDEBUGPARAMS(ocs->debugEnder(oce))
  820. SkDEBUGPARAMS(ics->debugEnder(ice))));
  821. }
  822. } else if (outerCoin == innerOpp) {
  823. const SkOpPtT* oce = outer->coinPtTEnd();
  824. FAIL_IF(oce->deleted());
  825. const SkOpPtT* ioe = inner->oppPtTEnd();
  826. FAIL_IF(ioe->deleted());
  827. if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) {
  828. FAIL_IF(!this->addIfMissing(ocs->starter(oce), ios->starter(ioe),
  829. overS, overE, outerOppWritable, innerCoinWritable, added
  830. SkDEBUGPARAMS(ocs->debugEnder(oce))
  831. SkDEBUGPARAMS(ios->debugEnder(ioe))));
  832. }
  833. } else if (outerOpp == innerCoin) {
  834. const SkOpPtT* ooe = outer->oppPtTEnd();
  835. FAIL_IF(ooe->deleted());
  836. const SkOpPtT* ice = inner->coinPtTEnd();
  837. FAIL_IF(ice->deleted());
  838. SkASSERT(outerCoin != innerOpp);
  839. if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) {
  840. FAIL_IF(!this->addIfMissing(oos->starter(ooe), ics->starter(ice),
  841. overS, overE, outerCoinWritable, innerOppWritable, added
  842. SkDEBUGPARAMS(oos->debugEnder(ooe))
  843. SkDEBUGPARAMS(ics->debugEnder(ice))));
  844. }
  845. } else if (outerOpp == innerOpp) {
  846. const SkOpPtT* ooe = outer->oppPtTEnd();
  847. FAIL_IF(ooe->deleted());
  848. const SkOpPtT* ioe = inner->oppPtTEnd();
  849. if (ioe->deleted()) {
  850. return true;
  851. }
  852. SkASSERT(outerCoin != innerCoin);
  853. if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) {
  854. FAIL_IF(!this->addIfMissing(oos->starter(ooe), ios->starter(ioe),
  855. overS, overE, outerCoinWritable, innerCoinWritable, added
  856. SkDEBUGPARAMS(oos->debugEnder(ooe))
  857. SkDEBUGPARAMS(ios->debugEnder(ioe))));
  858. }
  859. }
  860. this->debugValidate();
  861. }
  862. } while ((outer = outer->next()));
  863. this->restoreHead();
  864. return true;
  865. }
  866. bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
  867. const SkOpSegment* seg2, const SkOpSegment* seg2o,
  868. const SkOpPtT* overS, const SkOpPtT* overE) {
  869. const SkOpPtT* s1 = overS->find(seg1);
  870. const SkOpPtT* e1 = overE->find(seg1);
  871. FAIL_IF(!s1);
  872. FAIL_IF(!e1);
  873. if (!s1->starter(e1)->span()->upCast()->windValue()) {
  874. s1 = overS->find(seg1o);
  875. e1 = overE->find(seg1o);
  876. FAIL_IF(!s1);
  877. FAIL_IF(!e1);
  878. if (!s1->starter(e1)->span()->upCast()->windValue()) {
  879. return true;
  880. }
  881. }
  882. const SkOpPtT* s2 = overS->find(seg2);
  883. const SkOpPtT* e2 = overE->find(seg2);
  884. FAIL_IF(!s2);
  885. FAIL_IF(!e2);
  886. if (!s2->starter(e2)->span()->upCast()->windValue()) {
  887. s2 = overS->find(seg2o);
  888. e2 = overE->find(seg2o);
  889. FAIL_IF(!s2);
  890. FAIL_IF(!e2);
  891. if (!s2->starter(e2)->span()->upCast()->windValue()) {
  892. return true;
  893. }
  894. }
  895. if (s1->segment() == s2->segment()) {
  896. return true;
  897. }
  898. if (s1->fT > e1->fT) {
  899. using std::swap;
  900. swap(s1, e1);
  901. swap(s2, e2);
  902. }
  903. this->add(s1, e1, s2, e2);
  904. return true;
  905. }
  906. bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const {
  907. if (this->contains(fHead, seg, opp, oppT)) {
  908. return true;
  909. }
  910. if (this->contains(fTop, seg, opp, oppT)) {
  911. return true;
  912. }
  913. return false;
  914. }
  915. bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
  916. const SkOpSegment* opp, double oppT) const {
  917. if (!coin) {
  918. return false;
  919. }
  920. do {
  921. if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp
  922. && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) {
  923. return true;
  924. }
  925. if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp
  926. && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) {
  927. return true;
  928. }
  929. } while ((coin = coin->next()));
  930. return false;
  931. }
  932. bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
  933. const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const {
  934. const SkCoincidentSpans* test = fHead;
  935. if (!test) {
  936. return false;
  937. }
  938. const SkOpSegment* coinSeg = coinPtTStart->segment();
  939. const SkOpSegment* oppSeg = oppPtTStart->segment();
  940. if (!Ordered(coinPtTStart, oppPtTStart)) {
  941. using std::swap;
  942. swap(coinSeg, oppSeg);
  943. swap(coinPtTStart, oppPtTStart);
  944. swap(coinPtTEnd, oppPtTEnd);
  945. if (coinPtTStart->fT > coinPtTEnd->fT) {
  946. swap(coinPtTStart, coinPtTEnd);
  947. swap(oppPtTStart, oppPtTEnd);
  948. }
  949. }
  950. double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT);
  951. double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT);
  952. do {
  953. if (coinSeg != test->coinPtTStart()->segment()) {
  954. continue;
  955. }
  956. if (coinPtTStart->fT < test->coinPtTStart()->fT) {
  957. continue;
  958. }
  959. if (coinPtTEnd->fT > test->coinPtTEnd()->fT) {
  960. continue;
  961. }
  962. if (oppSeg != test->oppPtTStart()->segment()) {
  963. continue;
  964. }
  965. if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
  966. continue;
  967. }
  968. if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) {
  969. continue;
  970. }
  971. return true;
  972. } while ((test = test->next()));
  973. return false;
  974. }
  975. void SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
  976. DEBUG_SET_PHASE();
  977. SkCoincidentSpans* coin = fHead;
  978. if (!coin) {
  979. return;
  980. }
  981. do {
  982. coin->correctEnds();
  983. } while ((coin = coin->next()));
  984. }
  985. // walk span sets in parallel, moving winding from one to the other
  986. bool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
  987. DEBUG_SET_PHASE();
  988. SkCoincidentSpans* coin = fHead;
  989. if (!coin) {
  990. return true;
  991. }
  992. do {
  993. SkOpSpanBase* startSpan = coin->coinPtTStartWritable()->span();
  994. FAIL_IF(!startSpan->upCastable());
  995. SkOpSpan* start = startSpan->upCast();
  996. if (start->deleted()) {
  997. continue;
  998. }
  999. const SkOpSpanBase* end = coin->coinPtTEnd()->span();
  1000. FAIL_IF(start != start->starter(end));
  1001. bool flipped = coin->flipped();
  1002. SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable()
  1003. : coin->oppPtTStartWritable())->span();
  1004. FAIL_IF(!oStartBase->upCastable());
  1005. SkOpSpan* oStart = oStartBase->upCast();
  1006. if (oStart->deleted()) {
  1007. continue;
  1008. }
  1009. const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span();
  1010. SkASSERT(oStart == oStart->starter(oEnd));
  1011. SkOpSegment* segment = start->segment();
  1012. SkOpSegment* oSegment = oStart->segment();
  1013. bool operandSwap = segment->operand() != oSegment->operand();
  1014. if (flipped) {
  1015. if (oEnd->deleted()) {
  1016. continue;
  1017. }
  1018. do {
  1019. SkOpSpanBase* oNext = oStart->next();
  1020. if (oNext == oEnd) {
  1021. break;
  1022. }
  1023. FAIL_IF(!oNext->upCastable());
  1024. oStart = oNext->upCast();
  1025. } while (true);
  1026. }
  1027. do {
  1028. int windValue = start->windValue();
  1029. int oppValue = start->oppValue();
  1030. int oWindValue = oStart->windValue();
  1031. int oOppValue = oStart->oppValue();
  1032. // winding values are added or subtracted depending on direction and wind type
  1033. // same or opposite values are summed depending on the operand value
  1034. int windDiff = operandSwap ? oOppValue : oWindValue;
  1035. int oWindDiff = operandSwap ? oppValue : windValue;
  1036. if (!flipped) {
  1037. windDiff = -windDiff;
  1038. oWindDiff = -oWindDiff;
  1039. }
  1040. bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff
  1041. && oWindValue <= oWindDiff));
  1042. if (addToStart ? start->done() : oStart->done()) {
  1043. addToStart ^= true;
  1044. }
  1045. if (addToStart) {
  1046. if (operandSwap) {
  1047. using std::swap;
  1048. swap(oWindValue, oOppValue);
  1049. }
  1050. if (flipped) {
  1051. windValue -= oWindValue;
  1052. oppValue -= oOppValue;
  1053. } else {
  1054. windValue += oWindValue;
  1055. oppValue += oOppValue;
  1056. }
  1057. if (segment->isXor()) {
  1058. windValue &= 1;
  1059. }
  1060. if (segment->oppXor()) {
  1061. oppValue &= 1;
  1062. }
  1063. oWindValue = oOppValue = 0;
  1064. } else {
  1065. if (operandSwap) {
  1066. using std::swap;
  1067. swap(windValue, oppValue);
  1068. }
  1069. if (flipped) {
  1070. oWindValue -= windValue;
  1071. oOppValue -= oppValue;
  1072. } else {
  1073. oWindValue += windValue;
  1074. oOppValue += oppValue;
  1075. }
  1076. if (oSegment->isXor()) {
  1077. oWindValue &= 1;
  1078. }
  1079. if (oSegment->oppXor()) {
  1080. oOppValue &= 1;
  1081. }
  1082. windValue = oppValue = 0;
  1083. }
  1084. #if 0 && DEBUG_COINCIDENCE
  1085. SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(),
  1086. start->debugID(), windValue, oppValue);
  1087. SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(),
  1088. oStart->debugID(), oWindValue, oOppValue);
  1089. #endif
  1090. FAIL_IF(windValue <= -1);
  1091. start->setWindValue(windValue);
  1092. start->setOppValue(oppValue);
  1093. FAIL_IF(oWindValue <= -1);
  1094. oStart->setWindValue(oWindValue);
  1095. oStart->setOppValue(oOppValue);
  1096. if (!windValue && !oppValue) {
  1097. segment->markDone(start);
  1098. }
  1099. if (!oWindValue && !oOppValue) {
  1100. oSegment->markDone(oStart);
  1101. }
  1102. SkOpSpanBase* next = start->next();
  1103. SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next();
  1104. if (next == end) {
  1105. break;
  1106. }
  1107. FAIL_IF(!next->upCastable());
  1108. start = next->upCast();
  1109. // if the opposite ran out too soon, just reuse the last span
  1110. if (!oNext || !oNext->upCastable()) {
  1111. oNext = oStart;
  1112. }
  1113. oStart = oNext->upCast();
  1114. } while (true);
  1115. } while ((coin = coin->next()));
  1116. return true;
  1117. }
  1118. // Please keep this in sync with debugRelease()
  1119. bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) {
  1120. SkCoincidentSpans* head = coin;
  1121. SkCoincidentSpans* prev = nullptr;
  1122. SkCoincidentSpans* next;
  1123. do {
  1124. next = coin->next();
  1125. if (coin == remove) {
  1126. if (prev) {
  1127. prev->setNext(next);
  1128. } else if (head == fHead) {
  1129. fHead = next;
  1130. } else {
  1131. fTop = next;
  1132. }
  1133. break;
  1134. }
  1135. prev = coin;
  1136. } while ((coin = next));
  1137. return coin != nullptr;
  1138. }
  1139. void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) {
  1140. if (!coin) {
  1141. return;
  1142. }
  1143. SkCoincidentSpans* head = coin;
  1144. SkCoincidentSpans* prev = nullptr;
  1145. SkCoincidentSpans* next;
  1146. do {
  1147. next = coin->next();
  1148. if (coin->coinPtTStart()->deleted()) {
  1149. SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() :
  1150. coin->oppPtTStart()->deleted());
  1151. if (prev) {
  1152. prev->setNext(next);
  1153. } else if (head == fHead) {
  1154. fHead = next;
  1155. } else {
  1156. fTop = next;
  1157. }
  1158. } else {
  1159. SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() :
  1160. !coin->oppPtTStart()->deleted());
  1161. prev = coin;
  1162. }
  1163. } while ((coin = next));
  1164. }
  1165. void SkOpCoincidence::releaseDeleted() {
  1166. this->releaseDeleted(fHead);
  1167. this->releaseDeleted(fTop);
  1168. }
  1169. void SkOpCoincidence::restoreHead() {
  1170. SkCoincidentSpans** headPtr = &fHead;
  1171. while (*headPtr) {
  1172. headPtr = (*headPtr)->nextPtr();
  1173. }
  1174. *headPtr = fTop;
  1175. fTop = nullptr;
  1176. // segments may have collapsed in the meantime; remove empty referenced segments
  1177. headPtr = &fHead;
  1178. while (*headPtr) {
  1179. SkCoincidentSpans* test = *headPtr;
  1180. if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) {
  1181. *headPtr = test->next();
  1182. continue;
  1183. }
  1184. headPtr = (*headPtr)->nextPtr();
  1185. }
  1186. }
  1187. // Please keep this in sync with debugExpand()
  1188. // expand the range by checking adjacent spans for coincidence
  1189. bool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
  1190. DEBUG_SET_PHASE();
  1191. SkCoincidentSpans* coin = fHead;
  1192. if (!coin) {
  1193. return false;
  1194. }
  1195. bool expanded = false;
  1196. do {
  1197. if (coin->expand()) {
  1198. // check to see if multiple spans expanded so they are now identical
  1199. SkCoincidentSpans* test = fHead;
  1200. do {
  1201. if (coin == test) {
  1202. continue;
  1203. }
  1204. if (coin->coinPtTStart() == test->coinPtTStart()
  1205. && coin->oppPtTStart() == test->oppPtTStart()) {
  1206. this->release(fHead, test);
  1207. break;
  1208. }
  1209. } while ((test = test->next()));
  1210. expanded = true;
  1211. }
  1212. } while ((coin = coin->next()));
  1213. return expanded;
  1214. }
  1215. bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps DEBUG_COIN_DECLARE_PARAMS()) const {
  1216. DEBUG_SET_PHASE();
  1217. overlaps->fHead = overlaps->fTop = nullptr;
  1218. SkCoincidentSpans* outer = fHead;
  1219. while (outer) {
  1220. const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
  1221. const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
  1222. SkCoincidentSpans* inner = outer;
  1223. while ((inner = inner->next())) {
  1224. const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
  1225. if (outerCoin == innerCoin) {
  1226. continue; // both winners are the same segment, so there's no additional overlap
  1227. }
  1228. const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
  1229. const SkOpPtT* overlapS;
  1230. const SkOpPtT* overlapE;
  1231. if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(),
  1232. outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS,
  1233. &overlapE))
  1234. || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(),
  1235. outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
  1236. &overlapS, &overlapE))
  1237. || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(),
  1238. outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
  1239. &overlapS, &overlapE))) {
  1240. if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
  1241. overlapS, overlapE)) {
  1242. return false;
  1243. }
  1244. }
  1245. }
  1246. outer = outer->next();
  1247. }
  1248. return true;
  1249. }
  1250. void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) {
  1251. SkOPASSERT(deleted != kept);
  1252. if (fHead) {
  1253. this->fixUp(fHead, deleted, kept);
  1254. }
  1255. if (fTop) {
  1256. this->fixUp(fTop, deleted, kept);
  1257. }
  1258. }
  1259. void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) {
  1260. SkCoincidentSpans* head = coin;
  1261. do {
  1262. if (coin->coinPtTStart() == deleted) {
  1263. if (coin->coinPtTEnd()->span() == kept->span()) {
  1264. this->release(head, coin);
  1265. continue;
  1266. }
  1267. coin->setCoinPtTStart(kept);
  1268. }
  1269. if (coin->coinPtTEnd() == deleted) {
  1270. if (coin->coinPtTStart()->span() == kept->span()) {
  1271. this->release(head, coin);
  1272. continue;
  1273. }
  1274. coin->setCoinPtTEnd(kept);
  1275. }
  1276. if (coin->oppPtTStart() == deleted) {
  1277. if (coin->oppPtTEnd()->span() == kept->span()) {
  1278. this->release(head, coin);
  1279. continue;
  1280. }
  1281. coin->setOppPtTStart(kept);
  1282. }
  1283. if (coin->oppPtTEnd() == deleted) {
  1284. if (coin->oppPtTStart()->span() == kept->span()) {
  1285. this->release(head, coin);
  1286. continue;
  1287. }
  1288. coin->setOppPtTEnd(kept);
  1289. }
  1290. } while ((coin = coin->next()));
  1291. }
  1292. // Please keep this in sync with debugMark()
  1293. /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */
  1294. bool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) {
  1295. DEBUG_SET_PHASE();
  1296. SkCoincidentSpans* coin = fHead;
  1297. if (!coin) {
  1298. return true;
  1299. }
  1300. do {
  1301. SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span();
  1302. FAIL_IF(!startBase->upCastable());
  1303. SkOpSpan* start = startBase->upCast();
  1304. FAIL_IF(start->deleted());
  1305. SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
  1306. SkOPASSERT(!end->deleted());
  1307. SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
  1308. SkOPASSERT(!oStart->deleted());
  1309. SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span();
  1310. FAIL_IF(oEnd->deleted());
  1311. bool flipped = coin->flipped();
  1312. if (flipped) {
  1313. using std::swap;
  1314. swap(oStart, oEnd);
  1315. }
  1316. /* coin and opp spans may not match up. Mark the ends, and then let the interior
  1317. get marked as many times as the spans allow */
  1318. FAIL_IF(!oStart->upCastable());
  1319. start->insertCoincidence(oStart->upCast());
  1320. end->insertCoinEnd(oEnd);
  1321. const SkOpSegment* segment = start->segment();
  1322. const SkOpSegment* oSegment = oStart->segment();
  1323. SkOpSpanBase* next = start;
  1324. SkOpSpanBase* oNext = oStart;
  1325. bool ordered;
  1326. FAIL_IF(!coin->ordered(&ordered));
  1327. while ((next = next->upCast()->next()) != end) {
  1328. FAIL_IF(!next->upCastable());
  1329. FAIL_IF(!next->upCast()->insertCoincidence(oSegment, flipped, ordered));
  1330. }
  1331. while ((oNext = oNext->upCast()->next()) != oEnd) {
  1332. FAIL_IF(!oNext->upCastable());
  1333. FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered));
  1334. }
  1335. } while ((coin = coin->next()));
  1336. return true;
  1337. }
  1338. // Please keep in sync with debugMarkCollapsed()
  1339. void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) {
  1340. SkCoincidentSpans* head = coin;
  1341. while (coin) {
  1342. if (coin->collapsed(test)) {
  1343. if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) {
  1344. coin->coinPtTStartWritable()->segment()->markAllDone();
  1345. }
  1346. if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) {
  1347. coin->oppPtTStartWritable()->segment()->markAllDone();
  1348. }
  1349. this->release(head, coin);
  1350. }
  1351. coin = coin->next();
  1352. }
  1353. }
  1354. // Please keep in sync with debugMarkCollapsed()
  1355. void SkOpCoincidence::markCollapsed(SkOpPtT* test) {
  1356. markCollapsed(fHead, test);
  1357. markCollapsed(fTop, test);
  1358. }
  1359. bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) {
  1360. if (coinSeg->verb() < oppSeg->verb()) {
  1361. return true;
  1362. }
  1363. if (coinSeg->verb() > oppSeg->verb()) {
  1364. return false;
  1365. }
  1366. int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2;
  1367. const SkScalar* cPt = &coinSeg->pts()[0].fX;
  1368. const SkScalar* oPt = &oppSeg->pts()[0].fX;
  1369. for (int index = 0; index < count; ++index) {
  1370. if (*cPt < *oPt) {
  1371. return true;
  1372. }
  1373. if (*cPt > *oPt) {
  1374. return false;
  1375. }
  1376. ++cPt;
  1377. ++oPt;
  1378. }
  1379. return true;
  1380. }
  1381. bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
  1382. const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const {
  1383. SkASSERT(coin1s->segment() == coin2s->segment());
  1384. *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT));
  1385. *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT));
  1386. return *overS < *overE;
  1387. }
  1388. // Commented-out lines keep this in sync with debugRelease()
  1389. void SkOpCoincidence::release(const SkOpSegment* deleted) {
  1390. SkCoincidentSpans* coin = fHead;
  1391. if (!coin) {
  1392. return;
  1393. }
  1394. do {
  1395. if (coin->coinPtTStart()->segment() == deleted
  1396. || coin->coinPtTEnd()->segment() == deleted
  1397. || coin->oppPtTStart()->segment() == deleted
  1398. || coin->oppPtTEnd()->segment() == deleted) {
  1399. this->release(fHead, coin);
  1400. }
  1401. } while ((coin = coin->next()));
  1402. }