SkOpSpan.cpp 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484
  1. /*
  2. * Copyright 2014 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/SkOpContour.h"
  9. #include "src/pathops/SkOpSegment.h"
  10. #include "src/pathops/SkPathWriter.h"
  11. bool SkOpPtT::alias() const {
  12. return this->span()->ptT() != this;
  13. }
  14. const SkOpPtT* SkOpPtT::active() const {
  15. if (!fDeleted) {
  16. return this;
  17. }
  18. const SkOpPtT* ptT = this;
  19. const SkOpPtT* stopPtT = ptT;
  20. while ((ptT = ptT->next()) != stopPtT) {
  21. if (ptT->fSpan == fSpan && !ptT->fDeleted) {
  22. return ptT;
  23. }
  24. }
  25. return nullptr; // should never return deleted; caller must abort
  26. }
  27. bool SkOpPtT::contains(const SkOpPtT* check) const {
  28. SkOPASSERT(this != check);
  29. const SkOpPtT* ptT = this;
  30. const SkOpPtT* stopPtT = ptT;
  31. while ((ptT = ptT->next()) != stopPtT) {
  32. if (ptT == check) {
  33. return true;
  34. }
  35. }
  36. return false;
  37. }
  38. bool SkOpPtT::contains(const SkOpSegment* segment, const SkPoint& pt) const {
  39. SkASSERT(this->segment() != segment);
  40. const SkOpPtT* ptT = this;
  41. const SkOpPtT* stopPtT = ptT;
  42. while ((ptT = ptT->next()) != stopPtT) {
  43. if (ptT->fPt == pt && ptT->segment() == segment) {
  44. return true;
  45. }
  46. }
  47. return false;
  48. }
  49. bool SkOpPtT::contains(const SkOpSegment* segment, double t) const {
  50. const SkOpPtT* ptT = this;
  51. const SkOpPtT* stopPtT = ptT;
  52. while ((ptT = ptT->next()) != stopPtT) {
  53. if (ptT->fT == t && ptT->segment() == segment) {
  54. return true;
  55. }
  56. }
  57. return false;
  58. }
  59. const SkOpPtT* SkOpPtT::contains(const SkOpSegment* check) const {
  60. SkASSERT(this->segment() != check);
  61. const SkOpPtT* ptT = this;
  62. const SkOpPtT* stopPtT = ptT;
  63. while ((ptT = ptT->next()) != stopPtT) {
  64. if (ptT->segment() == check && !ptT->deleted()) {
  65. return ptT;
  66. }
  67. }
  68. return nullptr;
  69. }
  70. SkOpContour* SkOpPtT::contour() const {
  71. return segment()->contour();
  72. }
  73. const SkOpPtT* SkOpPtT::find(const SkOpSegment* segment) const {
  74. const SkOpPtT* ptT = this;
  75. const SkOpPtT* stopPtT = ptT;
  76. do {
  77. if (ptT->segment() == segment && !ptT->deleted()) {
  78. return ptT;
  79. }
  80. ptT = ptT->fNext;
  81. } while (stopPtT != ptT);
  82. // SkASSERT(0);
  83. return nullptr;
  84. }
  85. SkOpGlobalState* SkOpPtT::globalState() const {
  86. return contour()->globalState();
  87. }
  88. void SkOpPtT::init(SkOpSpanBase* span, double t, const SkPoint& pt, bool duplicate) {
  89. fT = t;
  90. fPt = pt;
  91. fSpan = span;
  92. fNext = this;
  93. fDuplicatePt = duplicate;
  94. fDeleted = false;
  95. fCoincident = false;
  96. SkDEBUGCODE(fID = span->globalState()->nextPtTID());
  97. }
  98. bool SkOpPtT::onEnd() const {
  99. const SkOpSpanBase* span = this->span();
  100. if (span->ptT() != this) {
  101. return false;
  102. }
  103. const SkOpSegment* segment = this->segment();
  104. return span == segment->head() || span == segment->tail();
  105. }
  106. bool SkOpPtT::ptAlreadySeen(const SkOpPtT* check) const {
  107. while (this != check) {
  108. if (this->fPt == check->fPt) {
  109. return true;
  110. }
  111. check = check->fNext;
  112. }
  113. return false;
  114. }
  115. SkOpPtT* SkOpPtT::prev() {
  116. SkOpPtT* result = this;
  117. SkOpPtT* next = this;
  118. while ((next = next->fNext) != this) {
  119. result = next;
  120. }
  121. SkASSERT(result->fNext == this);
  122. return result;
  123. }
  124. const SkOpSegment* SkOpPtT::segment() const {
  125. return span()->segment();
  126. }
  127. SkOpSegment* SkOpPtT::segment() {
  128. return span()->segment();
  129. }
  130. void SkOpPtT::setDeleted() {
  131. SkASSERT(this->span()->debugDeleted() || this->span()->ptT() != this);
  132. SkOPASSERT(!fDeleted);
  133. fDeleted = true;
  134. }
  135. bool SkOpSpanBase::addOpp(SkOpSpanBase* opp) {
  136. SkOpPtT* oppPrev = this->ptT()->oppPrev(opp->ptT());
  137. if (!oppPrev) {
  138. return true;
  139. }
  140. FAIL_IF(!this->mergeMatches(opp));
  141. this->ptT()->addOpp(opp->ptT(), oppPrev);
  142. this->checkForCollapsedCoincidence();
  143. return true;
  144. }
  145. SkOpSpanBase::Collapsed SkOpSpanBase::collapsed(double s, double e) const {
  146. const SkOpPtT* start = &fPtT;
  147. const SkOpPtT* startNext = nullptr;
  148. const SkOpPtT* walk = start;
  149. double min = walk->fT;
  150. double max = min;
  151. const SkOpSegment* segment = this->segment();
  152. int safetyNet = 100000;
  153. while ((walk = walk->next()) != start) {
  154. if (!--safetyNet) {
  155. return Collapsed::kError;
  156. }
  157. if (walk == startNext) {
  158. return Collapsed::kError;
  159. }
  160. if (walk->segment() != segment) {
  161. continue;
  162. }
  163. min = SkTMin(min, walk->fT);
  164. max = SkTMax(max, walk->fT);
  165. if (between(min, s, max) && between(min, e, max)) {
  166. return Collapsed::kYes;
  167. }
  168. startNext = start->next();
  169. }
  170. return Collapsed::kNo;
  171. }
  172. bool SkOpSpanBase::contains(const SkOpSpanBase* span) const {
  173. const SkOpPtT* start = &fPtT;
  174. const SkOpPtT* check = &span->fPtT;
  175. SkOPASSERT(start != check);
  176. const SkOpPtT* walk = start;
  177. while ((walk = walk->next()) != start) {
  178. if (walk == check) {
  179. return true;
  180. }
  181. }
  182. return false;
  183. }
  184. const SkOpPtT* SkOpSpanBase::contains(const SkOpSegment* segment) const {
  185. const SkOpPtT* start = &fPtT;
  186. const SkOpPtT* walk = start;
  187. while ((walk = walk->next()) != start) {
  188. if (walk->deleted()) {
  189. continue;
  190. }
  191. if (walk->segment() == segment && walk->span()->ptT() == walk) {
  192. return walk;
  193. }
  194. }
  195. return nullptr;
  196. }
  197. bool SkOpSpanBase::containsCoinEnd(const SkOpSegment* segment) const {
  198. SkASSERT(this->segment() != segment);
  199. const SkOpSpanBase* next = this;
  200. while ((next = next->fCoinEnd) != this) {
  201. if (next->segment() == segment) {
  202. return true;
  203. }
  204. }
  205. return false;
  206. }
  207. SkOpContour* SkOpSpanBase::contour() const {
  208. return segment()->contour();
  209. }
  210. SkOpGlobalState* SkOpSpanBase::globalState() const {
  211. return contour()->globalState();
  212. }
  213. void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
  214. fSegment = segment;
  215. fPtT.init(this, t, pt, false);
  216. fCoinEnd = this;
  217. fFromAngle = nullptr;
  218. fPrev = prev;
  219. fSpanAdds = 0;
  220. fAligned = true;
  221. fChased = false;
  222. SkDEBUGCODE(fCount = 1);
  223. SkDEBUGCODE(fID = globalState()->nextSpanID());
  224. SkDEBUGCODE(fDebugDeleted = false);
  225. }
  226. // this pair of spans share a common t value or point; merge them and eliminate duplicates
  227. // this does not compute the best t or pt value; this merely moves all data into a single list
  228. void SkOpSpanBase::merge(SkOpSpan* span) {
  229. SkOpPtT* spanPtT = span->ptT();
  230. SkASSERT(this->t() != spanPtT->fT);
  231. SkASSERT(!zero_or_one(spanPtT->fT));
  232. span->release(this->ptT());
  233. if (this->contains(span)) {
  234. SkOPASSERT(0); // check to see if this ever happens -- should have been found earlier
  235. return; // merge is already in the ptT loop
  236. }
  237. SkOpPtT* remainder = spanPtT->next();
  238. this->ptT()->insert(spanPtT);
  239. while (remainder != spanPtT) {
  240. SkOpPtT* next = remainder->next();
  241. SkOpPtT* compare = spanPtT->next();
  242. while (compare != spanPtT) {
  243. SkOpPtT* nextC = compare->next();
  244. if (nextC->span() == remainder->span() && nextC->fT == remainder->fT) {
  245. goto tryNextRemainder;
  246. }
  247. compare = nextC;
  248. }
  249. spanPtT->insert(remainder);
  250. tryNextRemainder:
  251. remainder = next;
  252. }
  253. fSpanAdds += span->fSpanAdds;
  254. }
  255. // please keep in sync with debugCheckForCollapsedCoincidence()
  256. void SkOpSpanBase::checkForCollapsedCoincidence() {
  257. SkOpCoincidence* coins = this->globalState()->coincidence();
  258. if (coins->isEmpty()) {
  259. return;
  260. }
  261. // the insert above may have put both ends of a coincident run in the same span
  262. // for each coincident ptT in loop; see if its opposite in is also in the loop
  263. // this implementation is the motivation for marking that a ptT is referenced by a coincident span
  264. SkOpPtT* head = this->ptT();
  265. SkOpPtT* test = head;
  266. do {
  267. if (!test->coincident()) {
  268. continue;
  269. }
  270. coins->markCollapsed(test);
  271. } while ((test = test->next()) != head);
  272. coins->releaseDeleted();
  273. }
  274. // please keep in sync with debugMergeMatches()
  275. // Look to see if pt-t linked list contains same segment more than once
  276. // if so, and if each pt-t is directly pointed to by spans in that segment,
  277. // merge them
  278. // keep the points, but remove spans so that the segment doesn't have 2 or more
  279. // spans pointing to the same pt-t loop at different loop elements
  280. bool SkOpSpanBase::mergeMatches(SkOpSpanBase* opp) {
  281. SkOpPtT* test = &fPtT;
  282. SkOpPtT* testNext;
  283. const SkOpPtT* stop = test;
  284. int safetyHatch = 1000000;
  285. do {
  286. if (!--safetyHatch) {
  287. return false;
  288. }
  289. testNext = test->next();
  290. if (test->deleted()) {
  291. continue;
  292. }
  293. SkOpSpanBase* testBase = test->span();
  294. SkASSERT(testBase->ptT() == test);
  295. SkOpSegment* segment = test->segment();
  296. if (segment->done()) {
  297. continue;
  298. }
  299. SkOpPtT* inner = opp->ptT();
  300. const SkOpPtT* innerStop = inner;
  301. do {
  302. if (inner->segment() != segment) {
  303. continue;
  304. }
  305. if (inner->deleted()) {
  306. continue;
  307. }
  308. SkOpSpanBase* innerBase = inner->span();
  309. SkASSERT(innerBase->ptT() == inner);
  310. // when the intersection is first detected, the span base is marked if there are
  311. // more than one point in the intersection.
  312. if (!zero_or_one(inner->fT)) {
  313. innerBase->upCast()->release(test);
  314. } else {
  315. SkOPASSERT(inner->fT != test->fT);
  316. if (!zero_or_one(test->fT)) {
  317. testBase->upCast()->release(inner);
  318. } else {
  319. segment->markAllDone(); // mark segment as collapsed
  320. SkDEBUGCODE(testBase->debugSetDeleted());
  321. test->setDeleted();
  322. SkDEBUGCODE(innerBase->debugSetDeleted());
  323. inner->setDeleted();
  324. }
  325. }
  326. #ifdef SK_DEBUG // assert if another undeleted entry points to segment
  327. const SkOpPtT* debugInner = inner;
  328. while ((debugInner = debugInner->next()) != innerStop) {
  329. if (debugInner->segment() != segment) {
  330. continue;
  331. }
  332. if (debugInner->deleted()) {
  333. continue;
  334. }
  335. SkOPASSERT(0);
  336. }
  337. #endif
  338. break;
  339. } while ((inner = inner->next()) != innerStop);
  340. } while ((test = testNext) != stop);
  341. this->checkForCollapsedCoincidence();
  342. return true;
  343. }
  344. int SkOpSpan::computeWindSum() {
  345. SkOpGlobalState* globals = this->globalState();
  346. SkOpContour* contourHead = globals->contourHead();
  347. int windTry = 0;
  348. while (!this->sortableTop(contourHead) && ++windTry < SkOpGlobalState::kMaxWindingTries) {
  349. }
  350. return this->windSum();
  351. }
  352. bool SkOpSpan::containsCoincidence(const SkOpSegment* segment) const {
  353. SkASSERT(this->segment() != segment);
  354. const SkOpSpan* next = fCoincident;
  355. do {
  356. if (next->segment() == segment) {
  357. return true;
  358. }
  359. } while ((next = next->fCoincident) != this);
  360. return false;
  361. }
  362. void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoint& pt) {
  363. SkASSERT(t != 1);
  364. initBase(segment, prev, t, pt);
  365. fCoincident = this;
  366. fToAngle = nullptr;
  367. fWindSum = fOppSum = SK_MinS32;
  368. fWindValue = 1;
  369. fOppValue = 0;
  370. fTopTTry = 0;
  371. fChased = fDone = false;
  372. segment->bumpCount();
  373. fAlreadyAdded = false;
  374. }
  375. // Please keep this in sync with debugInsertCoincidence()
  376. bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) {
  377. if (this->containsCoincidence(segment)) {
  378. return true;
  379. }
  380. SkOpPtT* next = &fPtT;
  381. while ((next = next->next()) != &fPtT) {
  382. if (next->segment() == segment) {
  383. SkOpSpan* span;
  384. SkOpSpanBase* base = next->span();
  385. if (!ordered) {
  386. const SkOpPtT* spanEndPtT = fNext->contains(segment);
  387. FAIL_IF(!spanEndPtT);
  388. const SkOpSpanBase* spanEnd = spanEndPtT->span();
  389. const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT());
  390. FAIL_IF(!start->span()->upCastable());
  391. span = const_cast<SkOpSpan*>(start->span()->upCast());
  392. } else if (flipped) {
  393. span = base->prev();
  394. FAIL_IF(!span);
  395. } else {
  396. FAIL_IF(!base->upCastable());
  397. span = base->upCast();
  398. }
  399. this->insertCoincidence(span);
  400. return true;
  401. }
  402. }
  403. #if DEBUG_COINCIDENCE
  404. SkASSERT(0); // FIXME? if we get here, the span is missing its opposite segment...
  405. #endif
  406. return true;
  407. }
  408. void SkOpSpan::release(const SkOpPtT* kept) {
  409. SkDEBUGCODE(fDebugDeleted = true);
  410. SkOPASSERT(kept->span() != this);
  411. SkASSERT(!final());
  412. SkOpSpan* prev = this->prev();
  413. SkASSERT(prev);
  414. SkOpSpanBase* next = this->next();
  415. SkASSERT(next);
  416. prev->setNext(next);
  417. next->setPrev(prev);
  418. this->segment()->release(this);
  419. SkOpCoincidence* coincidence = this->globalState()->coincidence();
  420. if (coincidence) {
  421. coincidence->fixUp(this->ptT(), kept);
  422. }
  423. this->ptT()->setDeleted();
  424. SkOpPtT* stopPtT = this->ptT();
  425. SkOpPtT* testPtT = stopPtT;
  426. const SkOpSpanBase* keptSpan = kept->span();
  427. do {
  428. if (this == testPtT->span()) {
  429. testPtT->setSpan(keptSpan);
  430. }
  431. } while ((testPtT = testPtT->next()) != stopPtT);
  432. }
  433. void SkOpSpan::setOppSum(int oppSum) {
  434. SkASSERT(!final());
  435. if (fOppSum != SK_MinS32 && fOppSum != oppSum) {
  436. this->globalState()->setWindingFailed();
  437. return;
  438. }
  439. SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(oppSum) <= DEBUG_LIMIT_WIND_SUM);
  440. fOppSum = oppSum;
  441. }
  442. void SkOpSpan::setWindSum(int windSum) {
  443. SkASSERT(!final());
  444. if (fWindSum != SK_MinS32 && fWindSum != windSum) {
  445. this->globalState()->setWindingFailed();
  446. return;
  447. }
  448. SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(windSum) <= DEBUG_LIMIT_WIND_SUM);
  449. fWindSum = windSum;
  450. }